Self-describing numbers: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
Recombinant (talk | contribs) (Add Zig solution) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
| (11 intermediate revisions by 4 users not shown) | |||
Line 863:
6210001000
</pre>
=={{header|CLU}}==
<syntaxhighlight lang="clu">self_describing = proc (n: int) returns (bool)
digits: array[int] := array[int]$predict(10, 10)
counts: array[int] := array[int]$fill(0, 10, 0)
while n > 0 do
digit: int := n // 10
n := n/10
array[int]$addl(digits, digit)
counts[digit] := counts[digit] + 1
end
array[int]$set_low(digits, 0)
for pos: int in array[int]$indexes(digits) do
if counts[pos] ~= digits[pos] then return(false) end
end
return(true)
end self_describing
start_up = proc ()
po: stream := stream$primary_output()
for n: int in int$from_to(1, 100000000) do
if self_describing(n) then
stream$putl(po, int$unparse(n))
end
end
end start_up</syntaxhighlight>
{{out}}
<pre>1210
2020
21200
3211000
42101000</pre>
=={{header|Common Lisp}}==
Line 899 ⟶ 934:
3211000
NIL</syntaxhighlight>
=={{header|Cowgol}}==
<syntaxhighlight lang="cowgol">include "cowgol.coh";
sub Length(n: uint32): (l: uint8) is
l := 0;
while n > 0 loop
n := n/10;
l := l+1;
end loop;
end sub;
sub IsSelfDescribing(n: uint32): (r: uint8) is
var positions: uint8[10];
var digitCounts: uint8[10];
MemSet(&positions[0], 0, @bytesof positions);
MemSet(&digitCounts[0], 0, @bytesof digitCounts);
var pos: uint8 := Length(n) - 1;
while n > 0 loop
var digit := (n % 10) as uint8;
positions[pos] := digit;
digitCounts[digit] := digitCounts[digit] + 1;
pos := pos - 1;
n := n / 10;
end loop;
r := 1;
pos := 0;
while pos < 10 loop
if positions[pos] != digitCounts[pos] then
r := 0;
break;
end if;
pos := pos + 1;
end loop;
end sub;
var n: uint32 := 1;
while n < 100000000 loop
if IsSelfDescribing(n) != 0 then
print_i32(n);
print_nl();
end if;
n := n + 1;
end loop;</syntaxhighlight>
{{out}}
<pre>1210
2020
21200
3211000
42101000</pre>
=={{header|Crystal}}==
Line 1,132 ⟶ 1,220:
</pre>
=={{header|EasyLang}}==
Works with backtracking, iterative is too slow. Constraint: the sum of the digits count is the number of digits.
<syntaxhighlight lang="easylang">
proc test d[] . .
cnt[] = [ 0 0 0 0 0 0 0 0 0 0 ]
for d in d[]
cnt[d + 1] += 1
.
for i to len d[]
if cnt[i] <> d[i]
return
.
.
# found
for d in d[]
write d
.
print ""
.
proc backtr ind max . d[] .
if ind > len d[]
test d[]
return
.
for d = 0 to max
if d < 10
d[ind] = d
backtr ind + 1 max - d d[]
.
.
.
for i = 1 to 10
len d[] i
backtr 1 len d[] d[]
.
</syntaxhighlight>
{{out}}
<pre>
1210
2020
21200
3211000
42101000
521001000
6210001000
</pre>
=={{header|Elixir}}==
Line 2,944 ⟶ 3,079:
42101000
</pre>
=={{header|RPL}}==
With some reasoning, one can find that digits must be between 0 and 4: just try manually to make a SDN with a 5 or greater and you will see it's impossible. The task enumerator takes this into account by counting in base 5, skipping numbers whose digital root is not equal to the number of digits and adding a final zero. Brute force is 30 times slower.
{{works with|HP|49}}
≪ STR→ { }
1 PICK3 SIZE '''FOR''' j
OVER j DUP SUB STR→ + '''NEXT'''
1 SF
0 ROT SIZE 1 - '''FOR''' j
DUP j 1 + GET
'''IF''' OVER 1 ≪ j == ≫ DOLIST ∑LIST ≠ '''THEN'''
1 CF DUP SIZE 'j' STO '''END'''
'''NEXT''' NIP
1 FS?
≫ '<span style="color:blue">SELF?</span>' STO
≪ →STR
1 OVER SIZE 1 - SUB <span style="color:grey">@ remove final zero</span>
0
1 PICK 3 SIZE '''FOR''' j
5 * OVER j DUP SUB STR→ + '''NEXT''' <span style="color:grey">@ convert from base 5</span>
NIP DUP
'''DO'''
DROP 1 + DUP ""
'''DO''' SWAP 5 IDIV2 ROT + <span style="color:grey">@ convert to base 5</span>
'''UNTIL''' OVER NOT '''END'''
NIP STR→
'''UNTIL''' DUP 1 - 9 MOD OVER XPON 1 + == '''END''' <span style="color:grey">@ check digital root</span>
NIP 10 * <span style="color:grey">@ add final zero</span>
≫ '<span style="color:blue">NEXTCAND</span>' STO
≪ → max
≪ { } 10
'''WHILE''' DUP max < '''REPEAT'''
'''IF''' DUP <span style="color:blue">SELF?</span> '''THEN''' SWAP OVER + SWAP '''END'''
<span style="color:blue">NEXTCAND</span>
'''END''' DROP
≫ ≫ '<span style="color:blue">TASK</span>' STO
9999 <span style="color:blue">TASK</span>
{{out}}
<pre>
1: {1210 2020}
</pre>
Runs in 43 seconds on a HP-48G.
=={{header|Ruby}}==
Line 3,419 ⟶ 3,599:
=={{header|Wren}}==
Heavily optimized to complete the search in a reasonable time for a scripting language.
<syntaxhighlight lang="
var ns = "%(n)"
var nc = ns.count
Line 3,583 ⟶ 3,763:
for (0..100_000_000) |number| {
if (isSelfDescribing(@intCast(
}
}</syntaxhighlight>
Line 3,593 ⟶ 3,773:
3211000
42101000</pre>
===Alternative With "
Here is an alternative implementation of <em>isSelfDescribing()</em> that
illustrates additional computationally cheap ways of partially eliminating
integers that are not self describing. These ideas were filched from other
solutions on this page (primarily Wren & PowerShell). The code works.
Refactoring for speed is a further exercise.
<syntaxhighlight lang="zig">/// Return true if number is self describing
Line 3,637 ⟶ 3,817:
// should equal the number of digits in the number
var sum: u32 = 0;
for (digits, 0..) |n, index| sum += n * @
if (sum != digits.len) return false;
}
| |||