Self-describing numbers: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
(→{{header|Ruby}}: used Ruby 2.4 method digits) |
m (→{{header|Wren}}: Changed to Wren S/H) |
||
(79 intermediate revisions by 30 users not shown) | |||
Line 18:
# Write a function/routine/method/... that will check whether a given positive integer is self-describing.
# As an optional stretch goal - generate and display the set of self-describing numbers.
;Related tasks:
* [[Fours is the number of letters in the ...]]
* [[Look-and-say sequence]]
* [[Number names]]
* [[Self-referential sequence]]
* [[Spelling of ordinal numbers]]
<br><br>
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">F is_self_describing(n)
V s = String(n)
R all(enumerate(Array(s)).map((i, ch) -> @s.count(String(i)) == Int(ch)))
print((0.<4000000).filter(x -> is_self_describing(x)))</syntaxhighlight>
{{out}}
<pre>
[1210, 2020, 21200, 3211000]
</pre>
=={{header|360 Assembly}}==
<syntaxhighlight lang="360asm">* Self-describing numbers 26/04/2020
SELFDESC CSECT
USING SELFDESC,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
LA R8,1 k=1
DO WHILE=(C,R8,LE,=A(NN)) do k=1 to nn
CVD R8,DBLK binary to packed decimal (PL8)
MVC CK,MAK load mask
EDMK CK,DBLK+2 packed dec (PL5) to char (CL10)
S R1,=A(CK) number of blanks
LR R3,R1 "
LA R9,L'CK length(ck)
SR R9,R1 length of the number
LA R6,1 i=1
DO WHILE=(CR,R6,LE,R9) do i=1 to l
LA R10,0 n=0
LA R7,1 j=1
DO WHILE=(CR,R7,LE,R9) do j=1 to l
LA R1,CK-1 @ck
AR R1,R3 +space(k)
AR R1,R7 +j
MVC CJ,0(R1) substr(k,j,1)
IC R1,CJ ~
SLL R1,28 shift left 28
SRL R1,28 shift right 28
LR R2,R6 i
BCTR R2,0 i-1
IF CR,R1,EQ,R2 THEN if substr(k,j,1)=i-1 then
LA R10,1(R10) n++
ENDIF , endif
LA R7,1(R7) j++
ENDDO , enddo j
LA R1,CK-1 @ck
AR R1,R3 +space(k)
AR R1,R6 +i
MVC CI,0(R1) substr(k,i,1)
IC R1,CI ~
SLL R1,28 shift left 28
SRL R1,28 shift right 28
IF CR,R1,NE,R10 THEN if substr(k,i,1)<>n then
B ITERK iterate k
ENDIF , endif
LA R6,1(R6) i++
ENDDO , enddo i
XPRNT CK,L'CK print ck
ITERK LA R8,1(R8) k++
ENDDO , enddo k
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling save
NN EQU 5000000 nn
DBLK DS PL8 double word 15num
MAK DC X'402020202020202020202020' mask CL12 11num
CK DS CL12 ck 12num
CI DS C ci
CJ DS C cj
PG DS CL80 buffer
XDEC DS CL12 temp fo xdeco
REGEQU
END SELFDESC </syntaxhighlight>
{{out}}
<pre>
1210
2020
21200
3211000
</pre>
=={{header|Ada}}==
<
procedure SelfDesc is
subtype Desc_Int is Long_Integer range 0 .. 10**10-1;
Line 45 ⟶ 140:
end if;
end loop;
end SelfDesc;</
{{out}}
<pre>1210
Line 56 ⟶ 151:
{{works with|ALGOL 68|Revision 1 - no extensions to language used}}
{{works with|ALGOL 68G|Any - tested with release 2.6.win32}}
<
# return TRUE if number is self describing, FALSE otherwise #
Line 101 ⟶ 196:
)
END</
{{out}}
<pre>
Line 110 ⟶ 205:
+42101000 is self describing
</pre>
=={{header|AppleScript}}==
<syntaxhighlight lang="applescript">use AppleScript version "2.4"
use framework "Foundation"
use scripting additions
-- selfDescribes :: Int -> Bool
on selfDescribes(x)
set s to str(x)
set descripn to my str(|λ|(my groupBy(my eq, my sort(characters of s))) of my ¬
described(characters of "0123456789"))
1 = (offset of descripn in s) and ¬
0 = ((items ((length of descripn) + 1) thru -1 of s) as string as integer)
end selfDescribes
-- described :: [Char] -> [[Char]] -> [Char]
on described(digits)
script
on |λ|(groups)
if 0 < length of digits and 0 < length of groups then
set grp to item 1 of groups
set go to described(rest of digits)
if item 1 of digits = item 1 of (item 1 of grp) then
{item 1 of my str(length of grp)} & |λ|(rest of groups) of go
else
{"0"} & |λ|(groups) of go
end if
else
{}
end if
end |λ|
end script
end described
-------------------------- TEST ---------------------------
on run
script test
on |λ|(n)
str(n) & " -> " & str(selfDescribes(n))
end |λ|
end script
unlines(map(test, ¬
{1210, 1211, 2020, 2022, 21200, 21203, 3211000, 3211004}))
end run
-------------------- GENERIC FUNCTIONS --------------------
-- True if every value in the list is true.
-- and :: [Bool] -> Bool
on |and|(xs)
repeat with x in xs
if not (contents of x) then return false
end repeat
return true
end |and|
-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
if m ≤ n then
set lst to {}
repeat with i from m to n
set end of lst to i
end repeat
lst
else
{}
end if
end enumFromTo
-- eq (==) :: Eq a => a -> a -> Bool
on eq(a, b)
a = b
end eq
-- filter :: (a -> Bool) -> [a] -> [a]
on filter(p, xs)
tell mReturn(p)
set lst to {}
set lng to length of xs
repeat with i from 1 to lng
set v to item i of xs
if |λ|(v, i, xs) then set end of lst to v
end repeat
return lst
end tell
end filter
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- Typical usage: groupBy(on(eq, f), xs)
-- groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
on groupBy(f, xs)
set mf to mReturn(f)
script enGroup
on |λ|(a, x)
if length of (active of a) > 0 then
set h to item 1 of active of a
else
set h to missing value
end if
if h is not missing value and mf's |λ|(h, x) then
{active:(active of a) & {x}, sofar:sofar of a}
else
{active:{x}, sofar:(sofar of a) & {active of a}}
end if
end |λ|
end script
if length of xs > 0 then
set dct to foldl(enGroup, {active:{item 1 of xs}, sofar:{}}, rest of xs)
if length of (active of dct) > 0 then
sofar of dct & {active of dct}
else
sofar of dct
end if
else
{}
end if
end groupBy
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
-- The list obtained by applying f
-- to each element of xs.
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper.
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- sort :: Ord a => [a] -> [a]
on sort(xs)
((current application's NSArray's arrayWithArray:xs)'s ¬
sortedArrayUsingSelector:"compare:") as list
end sort
-- str :: a -> String
on str(x)
x as string
end str
-- unlines :: [String] -> String
on unlines(xs)
-- A single string formed by the intercalation
-- of a list of strings with the newline character.
set {dlm, my text item delimiters} to ¬
{my text item delimiters, linefeed}
set s to xs as text
set my text item delimiters to dlm
s
end unlines</syntaxhighlight>
{{Out}}
<pre>1210 -> true
1211 -> false
2020 -> true
2022 -> false
21200 -> true
21203 -> false
3211000 -> true
3211004 -> false</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">selfDescribing?: function [x][
digs: digits x
loop.with:'i digs 'd [
if d <> size select digs 'z [z=i]
-> return false
]
return true
]
print select 1..22000 => selfDescribing?</syntaxhighlight>
{{out}}
<pre>1210 2020 21200</pre>
=={{header|AutoHotkey}}==
Uses CountSubString: [[Count occurrences of a substring#AutoHotkey]]
<
#NoEnv
SetBatchlines -1
Line 135 ⟶ 452:
return false
return true
}</
Output:
<pre>---------------------------
Line 152 ⟶ 469:
=={{header|AWK}}==
<
BEGIN {
for (n=1; n<=100000000; n++) {
Line 168 ⟶ 485:
}
return(1)
}</
<p>output:</p>
<pre>
Line 179 ⟶ 496:
=={{header|BASIC}}==
<
Dim a, d As String
Dim v(10), w(10) As Integer
Line 202 ⟶ 519:
Print "End"
sleep
end</
=={{header|BBC BASIC}}==
{{works with|BBC BASIC for Windows}}
<
IF FNselfdescribing(N) PRINT N
NEXT
Line 221 ⟶ 538:
N% DIV=10
ENDWHILE
= O% = SUM(D%())</
Output:
<pre>
Line 236 ⟶ 553:
Be aware, though, that even with a fast interpreter, it's going to be a very long time before you see the full set of results.
<
?v6:%+55:\+1\<<<\0:::<
#>g1+\6p55+/:#^_001p\v
^_@#!`<<v\+g6g10*+55\<
>:*:*:*^>>:01g1+:01p`|
^_\#\:#+.#5\#5,#$:<-$<</
{{out}}
Line 252 ⟶ 569:
=={{header|C}}==
Using integers instead of strings.
<
inline int self_desc(unsigned long long xx)
Line 277 ⟶ 594:
return 0;
}</
2020
21200
3211000
42101000</
===Backtracking version===
Backtracks on each digit from right to left, takes advantage of constraints "sum of digit values = number of digits" and "sum of (digit index * digit value) = number of digits". It is using as argument the list of allowed digits (example 012345789 to run the program in standard base 10).
<
#include <stdlib.h>
#include <string.h>
Line 378 ⟶ 695:
puts("");
}
}</
Output for base 36
<syntaxhighlight lang="text">$ time ./selfdesc.exe 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ
1210
2020
Line 418 ⟶ 735:
real 0m0.094s
user 0m0.046s
sys 0m0.030s</
=={{header|C++}}==
<
#include <iostream>
Line 495 ⟶ 812:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 510 ⟶ 827:
Uses C++11. Build with
g++ -std=c++11 sdn.cpp
<
#include <array>
#include <iostream>
Line 535 ⟶ 852:
}
}
}</
Output:
<pre>
Line 546 ⟶ 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 553 ⟶ 905:
probably much faster because it wouldn't have to allocate an array and then
turn around and "interpret" it back out but I didn't really pursue it.
<
(defun to-digits (n)
Line 572 ⟶ 924:
(digits (to-digits n) (cdr digits)))
((null digits) t)
(if (not (eql (car digits) (aref counts ipos))) (return nil)))))</
Output:
<syntaxhighlight lang="text">(loop for i from 1 to 4000000 do (if (self-described-p i) (print i)))
1210
Line 581 ⟶ 933:
21200
3211000
NIL</
=={{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}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">def self_describing?(n)
digits = n.to_s.chars.map(&.to_i) # 12345 => [1, 2, 3, 4, 5]
digits.each_with_index.all? { |digit, idx| digits.count(idx) == digit }
end
t = Time.monotonic
600_000_000.times { |n| (puts "#{n} in #{(Time.monotonic - t).total_seconds} secs";\
t = Time.monotonic) if self_describing?(n) }</syntaxhighlight>
System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.6.17, Crystal 0.35
Compil: $ crystal build selfdescribing.cr --release
Run as: $ time ./selfdescribing
{{out}}
<pre>1210 in 0.000403914 secs
2020 in 0.000169698 secs
21200 in 0.003607744 secs
3211000 in 0.596545807 secs
42101000 in 7.246709658 secs
521001000 in 93.020066497 secs
./selfdescribing 168.47s user 17.24s system 159% cpu 1:56.07 total
</pre>
{{trans|Wren and Go}}
<syntaxhighlight lang="ruby">def selfDesc(n)
ns = n.to_s
nc = ns.size
count = Array.new(nc, 0)
sum = 0
while n > 0
d = n % 10
return false if d >= nc # can't have a digit >= number of digits
sum += d
return false if sum > nc
count[d] += 1
n //= 10
end
# to be self-describing sum of digits must equal number of digits
return false if sum != nc
return ns == count.join() # there must always be at least one zero
end
start = Time.monotonic
print("The self-describing numbers are:")
i = 10i64 # self-describing number must end in 0
pw = 10i64 # power of 10
fd = 1i64 # first digit
sd = 1i64 # second digit
dg = 2i64 # number of digits
mx = 11i64 # maximum for current batch
lim = 9_100_000_001i64 # sum of digits can't be more than 10
while i < lim
if selfDesc(i)
secs = (Time.monotonic - start).total_seconds
print("\n#{i} in #{secs} secs")
end
i += 10
if i > mx
fd += 1
sd -= 1
if sd >= 0
i = pw * fd
else
pw *= 10
dg += 1
i = pw
fd = 1
sd = dg - 1
end
mx = i + sd * pw // 10
end
end
osecs = (Time.monotonic - start).total_seconds
print("\nTook #{osecs} secs overall")</syntaxhighlight>
System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.6.17, Crystal 0.35
Run as: $ crystal run selfdescribing.cr --release
{{out}}
<pre>The self-describing numbers are:
1210 in 1.8045e-5 secs
2020 in 4.0684e-5 secs
21200 in 0.000105402 secs
3211000 in 0.013546922 secs
42101000 in 0.20069791 secs
521001000 in 2.775603351 secs
6210001000 in 37.813718839 secs
Took 45.138222133 secs overall</pre>
=={{header|D}}==
===Functional Version===
<
bool isSelfDescribing(in long n) pure nothrow @safe {
Line 594 ⟶ 1,087:
void main() {
4_000_000.iota.filter!isSelfDescribing.writeln;
}</
{{out}}
<pre>[1210, 2020, 21200, 3211000]</pre>
===A Faster Version===
<
if (n <= 0)
return false;
Line 641 ⟶ 1,134:
if (i.isSelfDescribing2)
i.writeln;
}</
{{out}}
<pre>1210
Line 656 ⟶ 1,149:
42101000
521001000</pre>
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
<syntaxhighlight lang="Delphi">
{This routine would normally be in a library. It is shown here for clarity.}
procedure GetDigitsRev(N: integer; var IA: TIntegerDynArray);
{Get an array of the integers in a number}
{Numbers returned from most to least significant}
var T,I,DC: integer;
begin
DC:=Trunc(Log10(N))+1;
SetLength(IA,DC);
for I:=DC-1 downto 0 do
begin
T:=N mod 10;
N:=N div 10;
IA[I]:=T;
end;
end;
function IsSelfDescribing(N: integer): boolean;
var IA: TIntegerDynArray;
var CA: array [0..9] of integer;
var I: integer;
begin
{Get digits, High-low order}
GetDigitsRev(N,IA);
for I:=0 to High(CA) do CA[I]:=0;
{Count number of each digit 0..9}
for I:=0 to High(IA) do
begin
CA[IA[I]]:=CA[IA[I]]+1;
end;
Result:=False;
{Compare original number with counts}
for I:=0 to High(IA) do
if IA[I]<>CA[I] then exit;
Result:=True;
end;
procedure SelfDescribingNumbers(Memo: TMemo);
var I: integer;
begin
for I:=0 to 100000000-1 do
if IsSelfDescribing(I) then
begin
Memo.Lines.Add(IntToStr(I));
end;
end;
</syntaxhighlight>
{{out}}
<pre>
1210
2020
21200
3211000
42101000
Elapsed Time: 23.584 Sec.
</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}}==
<
def number(n) do
digits = Integer.digits(n)
Line 668 ⟶ 1,279:
m = 3300000
Enum.filter(0..m, fn n -> Self_describing.number(n) end)</
{{out}}
Line 677 ⟶ 1,288:
=={{header|Erlang}}==
<
sdn(N) -> lists:map(fun(S)->length(lists:filter(fun(C)->C-$0==S end,N))+$0 end,lists:seq(0,length(N)-1))==N.
gen(M) -> lists:filter(fun(N)->sdn(integer_to_list(N)) end,lists:seq(0,M)).
</syntaxhighlight>
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: kernel math.parser prettyprint sequences ;
IN: rosetta-code.self-describing-numbers
: digits ( n -- seq ) number>string string>digits ;
: digit-count ( seq n -- m ) [ = ] curry count ;
: self-describing-number? ( n -- ? )
digits dup [ digit-count = ] with map-index [ t = ] all? ;
100,000,000 <iota> [ self-describing-number? ] filter .</syntaxhighlight>
{{out}}
<pre>
V{ 1210 2020 21200 3211000 42101000 }
</pre>
=={{header|Forth}}==
<
: third ( A b c -- A b c A ) >r over r> swap ;
: (.) ( u -- c-addr u ) 0 <# #s #> ;
Line 701 ⟶ 1,329:
(.) [char] 0 third third bounds ?do
count i c@ [char] 0 - <> if drop 2drop false unloop exit then
loop drop 2drop true ;</
=={{header|FreeBASIC}}==
<
Function selfDescribing (n As UInteger) As Boolean
Line 726 ⟶ 1,354:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 735 ⟶ 1,363:
=={{header|Go}}==
===Original===
<syntaxhighlight lang="go">package main
import (
Line 764 ⟶ 1,393:
}
}
}</
Output produced by above program:
<pre>
Line 774 ⟶ 1,403:
521001000
6210001000
</pre>
===Optimized===
Uses the optimized loop from the Wren entry - 12 times faster than before.
<syntaxhighlight lang="go">package main
import (
"fmt"
"strconv"
"strings"
"time"
)
func selfDesc(n uint64) bool {
if n >= 1e10 {
return false
}
s := strconv.FormatUint(n, 10)
for d, p := range s {
if int(p)-'0' != strings.Count(s, strconv.Itoa(d)) {
return false
}
}
return true
}
func main() {
start := time.Now()
fmt.Println("The self-describing numbers are:")
i := uint64(10) // self-describing number must end in 0
pw := uint64(10) // power of 10
fd := uint64(1) // first digit
sd := uint64(1) // second digit
dg := uint64(2) // number of digits
mx := uint64(11) // maximum for current batch
lim := uint64(9_100_000_001) // sum of digits can't be more than 10
for i < lim {
if selfDesc(i) {
secs := time.Since(start).Seconds()
fmt.Printf("%d (in %.1f secs)\n", i, secs)
}
i += 10
if i > mx {
fd++
sd--
if sd >= 0 {
i = fd * pw
} else {
pw *= 10
dg++
i = pw
fd = 1
sd = dg - 1
}
mx = i + sd*pw/10
}
}
osecs := time.Since(start).Seconds()
fmt.Printf("\nTook %.1f secs overall\n", osecs)
}</syntaxhighlight>
{{out}}
Timings are for an Intel Core i7-8565U machine running Go 1.14.2 on Ubuntu 18.04.
<pre>
The self-describing numbers are:
1210 (in 0.0 secs)
2020 (in 0.0 secs)
21200 (in 0.0 secs)
3211000 (in 0.0 secs)
42101000 (in 0.2 secs)
521001000 (in 2.5 secs)
6210001000 (in 29.9 secs)
Took 43.0 secs overall
</pre>
=={{header|Haskell}}==
<
count :: Int -> [Int] -> Int
Line 783 ⟶ 1,486:
isSelfDescribing :: Integer -> Bool
isSelfDescribing n = nu == f
main :: IO ()
main = do
print $
isSelfDescribing <$>
[1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000]
Output:
<pre>[True,True,True,True,True,True,True]
Line 798 ⟶ 1,502:
Here are functions for generating all the self-describing numbers of a certain length. We capitalize on the fact (from Wikipedia) that a self-describing number of length n is a base-n number (i.e. all digits are 0..n-1).
<
import
count :: Int -> [Int] -> Int
count x = length . filter (x ==)
--
--
-- one per digit
allBaseNNumsOfLength :: Int -> [[Int]]
allBaseNNumsOfLength
replicateM
<*> (enumFromTo 0 . subtract 1)
isSelfDescribing :: [Int] -> Bool
isSelfDescribing num =
all (\(i, x) -> x == count i num) $
zip [0 ..] num
--
decimalize :: [Int] -> Int
decimalize = read . map intToDigit
main
main =
(print . concat) $
map decimalize
. filter isSelfDescribing
. allBaseNNumsOfLength
<$> [1 .. 8]</syntaxhighlight>
{{Out}}
<pre>[1210,2020,21200,3211000,42101000]</pre>
=={{header|Icon}} and {{header|Unicon}}==
Line 824 ⟶ 1,539:
The following program contains the procedure <code>is_self_describing</code> to test if a number is a self-describing number, and the procedure <code>self_describing_numbers</code> to generate them.
<syntaxhighlight lang="icon">
procedure count (test_item, str)
result := 0
Line 853 ⟶ 1,568:
every write (self_describing_numbers ()\4)
end
</syntaxhighlight>
A slightly more concise solution can be derived from the above by taking
more advantage of Icon's (and Unicon's) automatic goal-directed
evaluation:
<
procedure is_self_describing (n)
ns := string (n) # convert to a string
Line 868 ⟶ 1,583:
procedure self_describing_numbers ()
suspend is_self_describing(seq())
end</
=={{header|J}}==
'''Solution''':<
counts =: _1 + [: #/.~ i.@:# , ]
selfdesc =: = counts&.digits"0 NB. Note use of "under"</
'''Example''':<
1 1 1 1 0 1</
'''Extra credit''':<
1210 2020 21200</
'''Discussion''': The use of <tt>&.</tt> here is a great example of its surprisingly broad applicability, and the elegance it can produce.
Line 888 ⟶ 1,603:
=={{header|Java}}==
<
public static boolean isSelfDescribing(int a){
String s = Integer.toString(a);
Line 914 ⟶ 1,629:
}
}
}</
=={{header|JavaScript}}==
{{works with|SpiderMonkey}}
<
var digits = Number(n).toString().split("").map(function(elem) {return Number(elem)});
var len = digits.length;
Line 946 ⟶ 1,661:
for (var i=1; i<=3300000; i++)
if (is_self_describing(i))
print(i);</
outputs
Line 956 ⟶ 1,671:
=={{header|jq}}==
{{works with|jq|1.4}}
<
# which is slightly less efficient:
def all(generator; condition):
reduce generator as $i (true; if . then $i | condition else . end);</
<
def count(value): reduce .[] as $i (0; if $i == value then . + 1 else . end);
def digits: tostring | explode | map(. - 48);
Line 968 ⟶ 1,683:
else . as $digits
| all ( range(0; length); . as $i | $digits | (.[$i] == count($i)) )
end;</
'''The task:'''
<
{{out}}
<
1210
2020
21200
3211000
42101000</
=={{header|Julia}}==
{{works with|Julia|0.6}}
<syntaxhighlight lang="julia">function selfie(x::Integer)
ds = reverse(digits(x))
if sum(ds) != length(ds) return false end
for (i, d) in enumerate(ds)
if d != sum(ds .== i - 1) return false end
end
return true
end
@show selfie(2021)
@time selfies(4000000)</syntaxhighlight>
{{out}}
<pre>1210
2020
21200
3211000
=={{header|K}}==
<
sdn 1210 2020 2121 21200 3211000 42101000
1 1 0 1 1 1
&sdn@!:1e6
1210 2020 21200</
=={{header|Kotlin}}==
<
fun selfDescribing(n: Int): Boolean {
Line 1,036 ⟶ 1,748:
for (i in 0..99999999) if (selfDescribing(i)) print("$i ")
println()
}</
{{out}}
Line 1,044 ⟶ 1,756:
</pre>
=={{
<
FOR x = 1 TO 5000000
a$ = TRIM$(STR$(x))
Line 1,063 ⟶ 1,775:
NEXT x
PRINT
PRINT "End"</
=={{
<
local tSelfD, tLen
put len(n) into tLen
Line 1,076 ⟶ 1,788:
end repeat
return tSelfD
end selfDescNumber</
To list the self-describing numbers to 10 million<
repeat with n = 0 to 10000000
if selfDescNumber(n) then
Line 1,085 ⟶ 1,797:
combine selfNum using comma
put selfNum
end mouseUp</
Output<syntaxhighlight lang
=={{header|Logo}}==
<
BT
MAKE "AA (ARRAY 10 0)
Line 1,114 ⟶ 1,826:
FOR [Z 0 9][SETITEM :Z :AA "0 SETITEM :Z :BB "0 ]]
PR [END]
END</
=={{header|Lua}}==
<
local s = tostring( n )
Line 1,137 ⟶ 1,849:
for i = 1, 999999999 do
print( Is_self_describing( i ) )
end</
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">isSelfDescribing[n_Integer] := (RotateRight[DigitCount[n]] == PadRight[IntegerDigits[n], 10])</syntaxhighlight>
<pre>Select[Range[10^10 - 1], isSelfDescribing]
-> {1210,2020,21200,3211000,42101000,521001000,6210001000}</pre>
=={{header|MATLAB}} / {{header|Octave}}==
<
s = int2str(n)-'0'; % convert to vector of digits
y = hist(s,0:9);
z = all(y(1:length(s))==s);
end;</
Test function:
<
if isSelfDescribing(k),
printf('%i\n',k);
end
end; </
Output:
Line 1,165 ⟶ 1,876:
21200
... </pre>
=={{header|MiniScript}}==
<syntaxhighlight lang="miniscript">numbers = [12, 1210, 1300, 2020, 21200, 5]
occurrences = function(test, values)
count = 0
for i in values
if i.val == test then count = count + 1
end for
return count
end function
for number in numbers
check = "" + number
digits = check.values
describing = true
for digit in digits.indexes
if digits[digit].val != occurrences(digit, digits) then
describing = false
end if
end for
if describing then
print number + " is self describing"
else
print number + " is not self describing"
end if
end for
</syntaxhighlight>
{{out}}
<pre>
12 is not self describing
1210 is self describing
1300 is not self describing
2020 is self describing
21200 is self describing
5 is not self describing
</pre>
=={{header|Modula-2}}==
{{trans|Pascal}}
{{works with|ADW Modula-2|any (Compile with the linker option ''Console Application'').}}
<syntaxhighlight lang="modula2">
MODULE SelfDescribingNumber;
FROM WholeStr IMPORT
CardToStr;
FROM STextIO IMPORT
WriteString, WriteLn;
FROM SWholeIO IMPORT
WriteCard;
PROCEDURE Check(Number: CARDINAL): BOOLEAN;
VAR
I, D: CARDINAL;
A: ARRAY [0 .. 9] OF CHAR;
Count, W: ARRAY [0 .. 9] OF CARDINAL;
Result: BOOLEAN;
BEGIN
CardToStr(Number, A);
FOR I := 0 TO 9 DO
Count[I] := 0;
W[I] := 0;
END;
FOR I := 0 TO LENGTH(A) - 1 DO
D := ORD(A[I]) - ORD("0");
INC(Count[D]);
W[I] := D;
END;
Result := TRUE;
I := 0;
WHILE Result AND (I <= 9) DO
Result := (Count[I] = W[I]);
INC(I);
END;
RETURN Result;
END Check;
VAR
X: CARDINAL;
BEGIN
WriteString("Autodescriptive numbers from 1 to 100000000:");
WriteLn;
FOR X := 1 TO 100000000 DO
IF Check(X) THEN
WriteString(" ");
WriteCard(X, 1);
WriteLn;
END;
END;
WriteString("Job done.");
WriteLn;
END SelfDescribingNumber.
</syntaxhighlight>
{{out}}
<pre>
Autodescriptive numbers from 1 to 100000000:
1210
2020
21200
3211000
42101000
Job done.
</pre>
=={{header|Nim}}==
This is a brute-force algorithm. To speed-up, it uses integers instead of strings and the variable “digits” is allocated once, placed in global scope and accessed directly by the two functions (something I generally avoid). We have been able to check until 1_000_000_000.
<syntaxhighlight lang="nim">import algorithm, sequtils, std/monotimes, times
type Digit = 0..9
var digits = newSeqOfCap[Digit](10)
proc getDigits(n: Positive) =
digits.setLen(0)
var n = n.int
while n != 0:
digits.add n mod 10
n = n div 10
digits.reverse()
proc isSelfDescribing(n: Natural): bool =
n.getDigits()
for i, d in digits:
if digits.count(i) != d:
return false
let t0 = getMonoTime()
for n in 1 .. 1_000_000_000:
if n.isSelfDescribing:
echo n, " in ", getMonoTime() - t0
echo "\nTotal time: ", getMonoTime() - t0</syntaxhighlight>
{{out}}
<pre>1210 in 154 microseconds and 723 nanoseconds
2020 in 376 microseconds and 687 nanoseconds
21200 in 2 milliseconds, 804 microseconds, and 259 nanoseconds
3211000 in 165 milliseconds, 490 microseconds, and 749 nanoseconds
42101000 in 2 seconds, 89 milliseconds, 515 microseconds, and 202 nanoseconds
521001000 in 27 seconds, 712 milliseconds, 35 microseconds, and 660 nanoseconds
Total time: 52 seconds, 969 milliseconds, 578 microseconds, and 698 nanoseconds</pre>
=={{header|ooRexx}}==
<syntaxhighlight lang="oorexx">
-- REXX program to check if a number (base 10) is self-describing.
parse arg x y .
Line 1,211 ⟶ 2,040:
say number "is a self describing number"
end
</syntaxhighlight>
'''output''' when using the input of: <tt> 0 999999999 </tt>
<pre style="overflow:scroll">
Line 1,225 ⟶ 2,054:
=={{header|PARI/GP}}==
This is a finite set...
<
isself(n)=vecsearch(S,n)</
=={{header|Pascal}}==
<
uses
Line 1,271 ⟶ 2,100:
writeln (' ', x);
writeln('Job done.');
end.</
Output:
<pre>
Line 1,288 ⟶ 2,117:
The number is self-descriptive If the arrays are equal.
<
{
local $_ = shift;
Line 1,299 ⟶ 2,128:
for (0 .. 100000, 3211000, 42101000) {
print "$_\n" if is_selfdesc($_);
}</
Output:
<pre>1210
Line 1,307 ⟶ 2,136:
42101000</pre>
=={{header|
{{Trans|Ada}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">self_desc</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">counts</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">digit</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">digit</span> <span style="color: #0000FF;">:=</span> <span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">10</span><span style="color: #0000FF;">-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">digit</span>
<span style="color: #000000;">digit</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">counts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digit</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">/</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">10</span><span style="color: #0000FF;">-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">..</span><span style="color: #000000;">10</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">counts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">10</span> <span style="color: #008080;">to</span> <span style="color: #000000;">100_000_000</span> <span style="color: #008080;">by</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">self_desc</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">i</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"done (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
1210
2020
21200
3211000
42101000
done (21.78s)
</pre>
===generator===
Not quite as fast as I hoped it would be, although a bazillion times faster than the above and a good five times faster than Python, the following self(20) completes in just over a second whereas self(24) takes nearly 9s, and it continues getting exponentially slower after that. Curiously, it is the early stages (same output) that slow down, whereas the latter ones always complete fairly quickly.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">impl</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span> <span style="color: #008080;">and</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">ds</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #008000;">'0'</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">></span><span style="color: #008000;">'9'</span> <span style="color: #008080;">then</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">+=</span> <span style="color: #008000;">'a'</span><span style="color: #0000FF;">-</span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">ds</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">ch</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ds</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dd</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">0</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">to</span> <span style="color: #000000;">m</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">dd</span><span style="color: #0000FF;">[$]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">i1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">l</span> <span style="color: #008080;">or</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i1</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">dd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">impl</span><span style="color: #0000FF;">(</span><span style="color: #000000;">dd</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">),</span><span style="color: #000000;">m</span><span style="color: #0000FF;">-</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">self</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">impl</span><span style="color: #0000FF;">({},</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">self</span><span style="color: #0000FF;">(</span><span style="color: #000000;">20</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,374 ⟶ 2,215:
3211000
42101000
521001000
6210001000
72100001000
821000001000
9210000001000
a2100000001000
b21000000001000
c210000000001000
d2100000000001000
e21000000000001000
f210000000000001000
g2100000000000001000
"1.2s"
</pre>
===even faster===
Finishes in less than a tenth of a second
{{trans|Seed7}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #004080;">string</span> <span style="color: #000000;">aleph</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'9'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">)&</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'z'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'a'</span><span style="color: #0000FF;">)&</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'Z'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- ie "0123456789abc..zABC..Z" (62 characters)</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">gen</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">ones</span><span style="color: #0000FF;">=</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">7</span><span style="color: #0000FF;">?</span><span style="color: #000000;">2</span><span style="color: #0000FF;">:</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">counts</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">ones</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]<></span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">2</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">ones</span><span style="color: #0000FF;"><></span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">d11</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span>
<span style="color: #000000;">counts</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d11</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">counts</span><span style="color: #0000FF;">=</span><span style="color: #000000;">digits</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">di</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">aleph</span><span style="color: #0000FF;">[</span><span style="color: #000000;">di</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">aleph</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">3</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">gen</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
as above plus
<pre>
h21000000000000001000
i210000000000000001000
...
z21000000000000000000000000000000001000
A210000000000000000000000000000000001000
...
Z2100000000000000000000000000000000000000000000000000000000001000
"0.0s"
</pre>
Line 1,380 ⟶ 2,287:
Works with: PHP 5.
<
function is_describing($number) {
Line 1,397 ⟶ 2,304:
}
?></
Output:
Line 1,405 ⟶ 2,312:
3211000
42101000</pre>
=={{header|Picat}}==
Here are three approaches. The latter two use a constraint modelling approach (a variant to the classic '''magic sequence''' problem, see below).
===Loop based approach===
<syntaxhighlight lang="picat">self_desc(Num,L) =>
L = [ I.to_integer() : I in Num.to_string()],
Len = L.len,
if sum(L) != Len then fail end,
foreach(J in L)
% cannot be a digit larger than the length of Num
if J >= Len then fail end
end,
foreach(I in 0..Len-1)
if sum([1 : J in L, I==J]) != L[I+1] then
fail
end
end.</syntaxhighlight>
===Constraint model 1===
Check if a number N is a self-describing number
<syntaxhighlight lang="picat">self_desc_cp(Num, Sequence) =>
N = length(Num.to_string()),
Sequence = new_list(N),
Sequence :: 0..N-1,
foreach(I in 0..N-1) count(I,Sequence,#=,Sequence[I+1]) end,
N #= sum(Sequence),
to_num(Sequence,10,Num),
scalar_product({ I : I in 0..N-1}, Sequence, N),
solve([ffd,updown], Sequence).</syntaxhighlight>
===Constraint model 2===
Same idea as <code>self_desc_cp/2</code> but a different usage: generate all solutions of a specific length Len.
<syntaxhighlight lang="picat">self_desc_cp_len(Len, Num) =>
Sequence = new_list(Len),
Sequence :: 0..Len-1,
Len #= sum(Sequence),
scalar_product({ I : I in 0..Len-1}, Sequence, Len),
to_num(Sequence,10,Num),
foreach(I in 0..Len-1) count(I,Sequence,#=,Sequence[I+1]) end,
solve([ffc,inout], Sequence).
%
% Converts a number Num to/from a list of integer List given a base Base
%
to_num(List, Base, Num) =>
Len = length(List),
Num #= sum([List[I]*Base**(Len-I) : I in 1..Len]).</syntaxhighlight>
===Testing===
Testing some numbers using <code>self_desc_cp/2</code>:
<syntaxhighlight lang="picat">go =>
List = [1210, 2020, 21200, 3211000, 42101000,
123456,98,10,-121,0,1,
9210000001000],
foreach(N in List)
printf("%w: %w\n", N, cond(self_desc_cp(N,_S),"self desc", "not self desc"))
end,
nl.</syntaxhighlight>
{{out}}
<pre>2020: self desc
21200: self desc
3211000: self desc
42101000: self desc
123456: not self desc
98: not self desc
10: not self desc
-121: not self desc
0: not self desc
1: not self desc
9210000001000: self desc
</pre>
===Generate all solutions of a specific length===
Using <code>self_desc_cp_len/3</code> to generates all solutions of length 1..13:
<syntaxhighlight lang="picat">go2 =>
Len :: 1..13,
println(findall(Num, (indomain(Len), self_desc_cp_len(Len,Num)))),
nl.
</syntaxhighlight>
{{out}}
<pre>[1210,2020,21200,3211000,42101000,521001000,6210001000,72100001000,821000001000,9210000001000]</pre>
===Magic sequence===
The two constraint modelling approaches are variations of the classic '''magic sequence''' problem:
''A magic sequence of length n is a sequence of integers x0 . . xn-1 between
0 and n-1, such that for all i in 0 to n-1, the number i occurs exactly xi
times in the sequence. For instance, 6,2,1,0,0,0,1,0,0,0 is a magic sequence
since 0 occurs 6 times in it, 1 occurs twice.''
Here is one way to model this magic sequence problem.
<syntaxhighlight lang="picat">go3 ?=>
member(N, 4..1000),
magic_sequenceN,Seq),
println(N=Seq),
fail,
nl.
go3 => true.
magic_sequence(N, Sequence) =>
Sequence = new_list(N),
Sequence :: 0..N-1,
foreach(I in 0..N-1)
Sequence[I+1] #= sum([Sequence[J] #= I : J in 1..N])
end,
sum(Sequence) #= N,
sum([I*Sequence[I+1] : I in 0..N-1]) #= N,
solve([ff,split], Sequence).</syntaxhighlight>
{{out}}
<pre>4 = [1,2,1,0]
4 = [2,0,2,0]
5 = [2,1,2,0,0]
7 = [3,2,1,1,0,0,0]
8 = [4,2,1,0,1,0,0,0]
9 = [5,2,1,0,0,1,0,0,0]
10 = [6,2,1,0,0,0,1,0,0,0]
11 = [7,2,1,0,0,0,0,1,0,0,0]
12 = [8,2,1,0,0,0,0,0,1,0,0,0]
13 = [9,2,1,0,0,0,0,0,0,1,0,0,0]
14 = [10,2,1,0,0,0,0,0,0,0,1,0,0,0]
15 = [11,2,1,0,0,0,0,0,0,0,0,1,0,0,0]
16 = [12,2,1,0,0,0,0,0,0,0,0,0,1,0,0,0]
17 = [13,2,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
18 = [14,2,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
19 = [15,2,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
20 = [16,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
21 = [17,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
22 = [18,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
23 = [19,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
24 = [20,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
25 = [21,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
26 = [22,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
27 = [23,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
28 = [24,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
29 = [25,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
30 = [26,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
31 = [27,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
32 = [28,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
33 = [29,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
34 = [30,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
35 = [31,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
36 = [32,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
37 = [33,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
38 = [34,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
39 = [35,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
40 = [36,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]
...</pre>
===Algorithmic approach===
Except for the self describing number 2020, these sequences can be found by the following "algorithmic" approach:
<syntaxhighlight lang="picat">magic_sequence_alg(N, Sequence) =>
Sequence = new_list(N,0),
Sequence[1] := N - 4,
Sequence[2] := 2,
Sequence[3] := 1,
Sequence[N-3] := 1.</syntaxhighlight>
=={{header|PicoLisp}}==
<
(fully '((D I) (= D (cnt = N (circ I))))
(setq N (mapcar format (chop N)))
(range 0 (length N)) ) )</
Output:
<pre>: (filter selfDescribing (range 1 4000000))
Line 1,418 ⟶ 2,492:
According to the Wiki definition, the sum of the products of the index and the
digit contained at the index should equal the number of digits in the number:
<syntaxhighlight lang="powershell">
function Test-SelfDescribing ([int]$Number)
{
Line 1,431 ⟶ 2,505:
$sum -eq $digits.Count
}
</syntaxhighlight>
<syntaxhighlight lang="powershell">
Test-SelfDescribing -Number 2020
</syntaxhighlight>
{{Out}}
<pre>
Line 1,440 ⟶ 2,514:
</pre>
It takes a very long while to test 100,000,000 numbers, and since they are already known just test a few:
<syntaxhighlight lang="powershell">
11,2020,21200,321100 | ForEach-Object {
[PSCustomObject]@{
Line 1,447 ⟶ 2,521:
}
} | Format-Table -AutoSize
</syntaxhighlight>
{{Out}}
<pre>
Line 1,460 ⟶ 2,534:
=={{header|Prolog}}==
Works with SWI-Prolog and library clpfd written by <b>Markus Triska</b>.
<
self_describling :-
Line 1,566 ⟶ 2,640:
run(Var,[Other|RRest], [1, Var],[Other|RRest]):-
dif(Var,Other).</
Output
Line 1,584 ⟶ 2,658:
=={{header|PureBasic}}==
<
;returns 1 if number is self-describing, otherwise it returns 0
Protected digitCount, digit, i, digitSum
Line 1,656 ⟶ 2,730:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf</
Sample output:
<pre>1210 is selfdescribing.
Line 1,711 ⟶ 2,785:
=={{header|Python}}==
<
s = str(n)
return all(s.count(str(i)) == int(ch) for i, ch in enumerate(s))
Line 1,718 ⟶ 2,792:
[1210, 2020, 21200, 3211000]
>>> [(x, isSelfDescribing(x)) for x in (1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000)]
[(1210, True), (2020, True), (21200, True), (3211000, True), (42101000, True), (521001000, True), (6210001000, True)]</
===Generator===
From [http://leetm.mingpao.com/cfm/Forum3.cfm?CategoryID=1&TopicID=1545&TopicOrder=Desc&TopicPage=1 here].
<
if m < 0: return
if d == c[:len(d)]: print d
Line 1,731 ⟶ 2,805:
def self(n): impl([], [0]*(n+1), n)
self(10)</
Output:
<pre>[]
Line 1,741 ⟶ 2,815:
[5, 2, 1, 0, 0, 1, 0, 0, 0]
[6, 2, 1, 0, 0, 0, 1, 0, 0, 0] </pre>
=={{header|Quackery}}==
<syntaxhighlight lang="quackery"> [ tuck over peek
1+ unrot poke ] is item++ ( n [ --> [ )
[ [] 10 times [ 0 join ]
swap
[ 10 /mod rot item++
swap dup 0 = until ]
drop ] is digitcount ( n --> [ )
[ 0 swap witheach + ] is sum ( [ --> n )
[ 0 swap
witheach
[ swap 10 * + ] ] is digits->n ( [ --> n )
[ dup digitcount
dup sum split drop
digits->n = ] is self-desc ( n --> b )
4000000 times
[ i^ self-desc if
[ i^ echo cr ] ]</syntaxhighlight>
{{out}}
<pre>1210
2020
21200
3211000
</pre>
=={{header|Racket}}==
<
(define (get-digits number (lst null))
(if (zero? number)
Line 1,756 ⟶ 2,863:
(and bool
(= (count (lambda (x) (= x i)) digits)
(list-ref digits i)))))))</
Sadly, the implementation is too slow for the optional task, taking somewhere around 3 minutes to check all numbers below 100.000.000
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>my @values = <1210 2020 21200 3211000
42101000 521001000 6210001000 27 115508>;
for @values -> $test {
say "$test is {sdn($test) ?? '' !! 'NOT ' }a self describing number.";
}
sub sdn($n) {
my $s = $n.Str;
my $chars = $s.chars;
my @a = +«$s.comb;
my @b;
for @a -> $i {
return False if $i >= $chars;
++@b[$i];
}
@b[$_] //= 0 for ^$chars;
@a eqv @b;
}
.say if .&sdn for ^9999999;</syntaxhighlight>
Output:
<pre>
1210 is a self describing number.
2020 is a self describing number.
21200 is a self describing number.
3211000 is a self describing number.
42101000 is a self describing number.
521001000 is a self describing number.
6210001000 is a self describing number.
27 is NOT a self describing number.
115508 is NOT a self describing number.
1210
2020
21200
3211000
</pre>
=={{header|Red}}==
<syntaxhighlight lang="red">Red []
;;-------------------------------------
count-dig: func ["count occurence of digit in number"
;;-------------------------------------
s [string!] "number as string"
sdig [char!] "search number as char"
][
cnt: #"0" ;; counter as char for performance optimization
while [s: find/tail s sdig][cnt: cnt + 1]
return cnt
]
;;-------------------------------------
isSDN?: func ["test if number is self describing number"
s [string!] "number to test as string "
][
;;-------------------------------------
ind: #"0" ;; use digit as char for performance optimization
foreach ele s [
if ele <> count-dig s ind [return false]
ind: ind + 1
]
return true
]
repeat i 4000000 [ if isSDN? to-string i [print i] ]
</syntaxhighlight>
'''output'''
<pre>1210
2020
21200
3211000
>>
</pre>
=={{header|REXX}}==
Line 1,764 ⟶ 2,951:
and [http://oeis.org/A138480 OEIS A138480].
===digit by digit test===
<
/*────────────────────────────────────────────────────── self─descriptive, */
/*────────────────────────────────────────────────────── autobiographical, or a */
Line 1,789 ⟶ 2,976:
if substr(?,j,1)\==L-length(space(translate(?,,j-1),0)) then return 1
end /*j*/
return 0 /*faster if used inverted truth table. */</
<pre>
╔══════════════════════════════════════════════════════════════════╗
Line 1,812 ⟶ 2,999:
===faster method===
(Uses table lookup.)
<
parse arg x y . /*obtain optional arguments from the CL*/
if x=='' | x=="," then exit /*Not specified? Then get out of Dodge*/
Line 1,830 ⟶ 3,017:
say right(n,w) 'is a self-describing number.'
end /*n*/
/*stick a fork in it, we're all done. */</
'''output''' is the same as the 1<sup>st</sup> REXX example.
Line 1,837 ⟶ 3,024:
(Results are instantaneous.)
<
parse arg x y . /*obtain optional arguments from the CL*/
if x=='' | x=="," then exit /*Not specified? Then get out of Dodge*/
Line 1,853 ⟶ 3,040:
if _<x | _>y then iterate /*if not self-describing, try again. */
say right(_, w) 'is a self-describing number.'
end /*n*/ /*stick a fork in it, we're all done. */</
'''output''' is the same as the 1<sup>st</sup> REXX example.
<br><br>
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : Self-describing numbers
for num = 1 to 45000000
res = 0
for n=1 to len(string(num))
temp = string(num)
pos = number(temp[n])
cnt = count(temp,string(n-1))
if cnt = pos
res = res + 1
ok
next
if res = len(string(num))
see num + nl
ok
next
func count(cString,dString)
sum = 0
while substr(cString,dString) > 0
sum = sum + 1
cString = substr(cString,substr(cString,dString)+len(string(sum)))
end
return sum
</syntaxhighlight>
Output:
<pre>
1210
2020
21200
3211000
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}}==
<
digits = n.digits.reverse
digits.each_with_index.all?{|digit, idx| digits.count(idx) == digit}
end
3_300_000.times {|n| puts n if self_describing?(n)}</
outputs
<pre>1210
Line 1,869 ⟶ 3,137:
21200
3211000</pre>
{{trans|Wren}}
<syntaxhighlight lang="ruby">def selfDesc(n)
ns = n.to_s
nc = ns.size
count = Array.new(nc, 0)
sum = 0
while n > 0
d = n % 10
return false if d >= nc # can't have a digit >= number of digits
sum += d
return false if sum > nc
count[d] += 1
n /= 10
end
# to be self-describing sum of digits must equal number of digits
return false if sum != nc
return ns == count.join() # there must always be at least one zero
end
start = Time.now
print("The self-describing numbers are:")
i = 10 # self-describing number must end in 0
pw = 10 # power of 10
fd = 1 # first digit
sd = 1 # second digit
dg = 2 # number of digits
mx = 11 # maximum for current batch
lim = 9_100_000_001 # sum of digits can't be more than 10
while i < lim
if selfDesc(i)
secs = (Time.now - start) #.total_seconds
print("\n#{i} in #{secs} secs")
end
i += 10
if i > mx
fd += 1
sd -= 1
if sd >= 0
i = pw * fd
else
pw *= 10
dg += 1
i = pw
fd = 1
sd = dg - 1
end
mx = i + sd * pw / 10
end
end
osecs = (Time.now - start)
print("\nTook #{osecs} secs overall")</syntaxhighlight>
System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.6.17, Ruby 2.7.1
Run as: $ ruby selfdescribing.rb
{{out}}
<pre>The self-describing numbers are:
1210 in 5.5602e-05 secs
2020 in 8.2552e-05 secs
21200 in 0.000755124 secs
3211000 in 0.096793633 secs
42101000 in 1.417997487 secs
521001000 in 19.847824233 secs
6210001000 in 278.414668197 secs
Took 332.50934836 secs overall</pre>
System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.6.17, JRuby 9.2.11.1
Run as: $ ruby selfdescribing.rb
{{out}}
<pre>The self-describing numbers are:
1210 in 0.01568 secs
2020 in 0.024242 secs
21200 in 0.037699 secs
3211000 in 0.297682 secs
42101000 in 1.156694 secs
521001000 in 13.114478 secs
6210001000 in 181.24703 secs
Took 216.292875 secs overall</pre>
System: I7-6700HQ, 3.5 GHz, Linux Kernel 5.6.17, TruffleRuby 20.1.0
Run as: $ ruby selfdescribing.rb
{{out}}
<pre>The self-describing numbers are:
1210 in 0.005 secs
2020 in 0.006 secs
21200 in 0.0130 secs
3211000 in 0.252 secs
42101000 in 0.642 secs
521001000 in 2.231 secs
6210001000 in 97.064 secs
Took 123.061 secs overall</pre>
=={{header|Run BASIC}}==
<
a$ = str$(i)
for c = 1 TO len(a$)
Line 1,887 ⟶ 3,246:
next i
print "== End =="
end</
=={{header|Rust}}==
<syntaxhighlight lang="rust">
fn is_self_desc(xx: u64) -> bool
{
let s: String = xx.to_string();
let mut count_vec = vec![0; 10];
for c in s.chars() {
count_vec[c.to_digit(10).unwrap() as usize] += 1;
}
for (i, c) in s.chars().enumerate() {
if count_vec[i] != c.to_digit(10).unwrap() as usize {
return false;
}
}
return true;
}
fn main() {
for i in 1..100000000 {
if is_self_desc(i) {
println!("{}", i)
}
}
}
</syntaxhighlight>
=={{header|Scala}}==
===Functional Programming===
<syntaxhighlight lang="scala">object SelfDescribingNumbers extends App {
def isSelfDescribing(a: Int): Boolean = {
val s = Integer.toString(a)
(0 until s.length).forall(i => s.count(_.toString.toInt == i) == s(i).toString.toInt)
}
println("Curious numbers n = x0 x1 x2...x9 such that xi is the number of digits equal to i in n.")
for (i <- 0 to 42101000 by 10
if isSelfDescribing(i)) println(i)
println("Successfully completed without errors.")
}</syntaxhighlight>
See it running in your browser by [https://scastie.scala-lang.org/vQv61PpoSLeWwyVipLUevQ Scastie (JVM)].
=={{header|Seed7}}==
<
const func boolean: selfDescr (in string: stri) is func
Line 1,955 ⟶ 3,359:
gen(number);
end for;
end func;</
Output:
Line 1,977 ⟶ 3,381:
=={{header|Sidef}}==
{{trans|
<
var b = [0]*n.len
var a = n.digits.flip
a.each { |i| b[i] := 0 ++ }
a == b
Line 1,993 ⟶ 3,397:
say "\nSelf-descriptive numbers less than 1e5 (in base 10):"
^1e5 -> each { |i| say i if sdn(i) }</
{{out}}
<pre>
Line 2,013 ⟶ 3,417:
'''Extra credit:''' this will generate all the self-describing numbers in bases 7 to 36:
<
var n = ((b-4) * b**(b-1) + 2*(b**(b-2)) + b**(b-3) + b**3 -> base(b))
say "base #{'%2d' % b}: #{n}"
}</
{{out}}
<pre>
Line 2,050 ⟶ 3,454:
base 36: w21000000000000000000000000000001000
</pre>
=={{header|Swift}}==
<syntaxhighlight lang="swift">import Foundation
extension BinaryInteger {
@inlinable
public var isSelfDescribing: Bool {
let stringChars = String(self).map({ String($0) })
let counts = stringChars.reduce(into: [Int: Int](), {res, char in res[Int(char), default: 0] += 1})
for (i, n) in stringChars.enumerated() where counts[i, default: 0] != Int(n) {
return false
}
return true
}
}
print("Self-describing numbers less than 100,000,000:")
DispatchQueue.concurrentPerform(iterations: 100_000_000) {i in
defer {
if i == 100_000_000 - 1 {
exit(0)
}
}
guard i.isSelfDescribing else {
return
}
print(i)
}
dispatchMain()</syntaxhighlight>
{{out}}
<pre>Self-describing numbers less than 100,000,000:
1210
2020
21200
3211000
42101000</pre>
=={{header|Tcl}}==
<
proc isSelfDescribing num {
set digits [split $num ""]
Line 2,067 ⟶ 3,516:
for {set i 0} {$i < 100000000} {incr i} {
if {[isSelfDescribing $i]} {puts $i}
}</
=={{header|UNIX Shell}}==
{{works with|bash}}
Seeking self-describing numbers up to 100,000,000 is very time consuming, so we'll just verify a few numbers.
<
local n=$1
local count=()
Line 2,091 ⟶ 3,540:
printf "%d\t%s\n" $n no
fi
done</
{{output}}
<pre>0 no
Line 2,106 ⟶ 3,555:
Takes a very, very long time to check 100M numbers that I have to terminate the script. But the function
works.
<syntaxhighlight lang="vb">
Function IsSelfDescribing(n)
IsSelfDescribing = False
Line 2,146 ⟶ 3,595:
end_time = Now
WScript.StdOut.WriteLine "Elapse Time: " & DateDiff("s",start_time,end_time) & " seconds"
</syntaxhighlight>
=={{header|Wren}}==
Heavily optimized to complete the search in a reasonable time for a scripting language.
<syntaxhighlight lang="wren">var selfDesc = Fn.new { |n|
var ns = "%(n)"
var nc = ns.count
var count = List.filled(nc, 0)
var sum = 0
while (n > 0) {
var d = n % 10
if (d >= nc) return false // can't have a digit >= number of digits
sum = sum + d
if (sum > nc) return false
count[d] = count[d] + 1
n = (n/10).floor
}
// to be self-describing sum of digits must equal number of digits
if (sum != nc) return false
return ns == count.join() // there must always be at least one zero
}
var start = System.clock
System.print("The self-describing numbers are:")
var i = 10 // self-describing number must end in 0
var pw = 10 // power of 10
var fd = 1 // first digit
var sd = 1 // second digit
var dg = 2 // number of digits
var mx = 11 // maximum for current batch
var lim = 9.1 * 1e9 + 1 // sum of digits can't be more than 10
while (i < lim) {
if (selfDesc.call(i)) {
var secs = ((System.clock - start) * 10).round / 10
System.print("%(i) (in %(secs) secs)")
}
i = i + 10
if (i > mx) {
fd = fd + 1
sd = sd - 1
if (sd >= 0) {
i = fd * pw
} else {
pw = pw * 10
dg = dg + 1
i = pw
fd = 1
sd = dg - 1
}
mx = i + sd*pw/10
}
}
var osecs = ((System.clock - start) * 10).round / 10
System.print("\nTook %(osecs) secs overall")</syntaxhighlight>
{{out}}
Timings are for an Intel Core i7-8565U machine running Wren 0.2.0 on Ubuntu 18.04.
<pre>
The self-describing numbers are:
1210 (in 0 secs)
2020 (in 0 secs)
21200 (in 0 secs)
3211000 (in 0.3 secs)
42101000 (in 4.8 secs)
521001000 (in 72.9 secs)
6210001000 (in 1162.5 secs)
Took 1392.1 secs overall
</pre>
=={{header|XPL0}}==
<
func SelfDesc(N); \Returns 'true' if N is self-describing
Line 2,183 ⟶ 3,700:
int N;
for N:= 0 to 100_000_000-1 do
if SelfDesc(N) then [IntOut(0, N); ChOut(0, ^ )]</
Output:
Line 2,189 ⟶ 3,706:
1210 2020 21200 3211000 42101000
</pre>
=={{header|Yabasic}}==
{{trans|BBC_BASIC}}
<syntaxhighlight lang="yabasic">FOR N = 1 TO 5E7
IF FNselfdescribing(N) PRINT N
NEXT
sub FNselfdescribing(N)
LOCAL D(9), I, L, O
O = N
L = INT(LOG(N, 10))
WHILE(N)
I = MOD(N, 10)
D(I) = D(I) + 10^(L-I)
N = INT(N / 10)
WEND
L = 0
FOR I = 0 TO 8 : L = L + D(I) : NEXT
RETURN O = L
END SUB</syntaxhighlight>
=={{header|Zig}}==
{{works with|Zig|0.11.0dev}}
<syntaxhighlight lang="zig">const std = @import("std");</syntaxhighlight>
<syntaxhighlight lang="zig">// Return true if number is self describing
fn isSelfDescribing(number: u32) bool {
var n = number; // Zig parameters are immutable, copy to var.
// 10 is the maximum number of decimal digits in a 32-bit integer.
var array: [10]u32 = undefined;
// Add digits to array.
var i: u32 = 0;
while (n != 0 or i == 0) : (n /= 10) {
array[i] = n % 10;
i += 1;
}
var digits = array[0..i]; // Slice to give just the digits added.
std.mem.reverse(u32, digits);
// Check digits. Brute force.
for (digits, 0..) |predicted_count, predicted_digit| {
var count: u8 = 0;
for (digits) |digit| {
if (digit == predicted_digit) count += 1;
}
if (count != predicted_count) return false;
}
return true;
}</syntaxhighlight>
<syntaxhighlight lang="zig">pub fn main() anyerror!void {
const stdout = std.io.getStdOut().writer();
for (0..100_000_000) |number| {
if (isSelfDescribing(@intCast(number)))
try stdout.print("{}\n", .{number});
}
}</syntaxhighlight>
{{out}}
<pre>1210
2020
21200
3211000
42101000</pre>
===Alternative With "Optimizations"===
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
fn isSelfDescribing(number: u32) bool {
// Get the digits (limit scope of variables in a Zig block expression)
// 1234 -> { 1, 2, 3, 4}
const digits = blk: {
var n = number; // Zig parameters are immutable, copy to var.
// 10 is the maximum number of decimal digits in a 32-bit integer.
var array: [10]u32 = undefined;
// Add base 10 digits to array.
var i: u32 = 0;
while (n != 0 or i == 0) : (n /= 10) {
array[i] = n % 10;
i += 1;
}
var slice = array[0..i]; // Slice to give only the digits added.
std.mem.reverse(u32, slice);
break :blk slice;
};
{
// wikipedia: last digit must be zero
if (digits[digits.len - 1] != 0) return false;
}
{
// cannot have a digit >= number of digits
for (digits) |n| if (n >= digits.len) return false;
}
{
// sum of digits must equal number of digits
var sum: u32 = 0;
for (digits) |n| sum += n; // > digits.len short-circuit ?
if (sum != digits.len) return false;
}
{
// sum of the products of the index and the digit contained at the index
// should equal the number of digits in the number
var sum: u32 = 0;
for (digits, 0..) |n, index| sum += n * @as(u32, @truncate(index));
if (sum != digits.len) return false;
}
// Final elimination. 100% effective. Brute force.
{
// Self describing check of digits.
for (digits, 0..) |expected_count, expected_digit| {
var count: u8 = 0;
for (digits) |digit| {
if (digit == expected_digit) count += 1;
}
if (count != expected_count) return false;
}
}
return true;
}</syntaxhighlight>
=={{header|zkl}}==
<
if (n.bitAnd(1)) return(False); // Wikipedia: last digit must be zero
nu:= n.toString();
ns:=["0".."9"].pump(String,nu.inCommon,"len"); //"12233".inCommon("2")-->"22"
(nu+"0000000000")[0,10] == ns; //"2020","2020000000"
}</
Since testing a humongous number of numbers is slow, chunk the task into a bunch of threads. Even so, it pegged my 8 way Ivy Bridge Linux box for quite some time (eg the Python & AWK solutions crush this one).
<
const N=0d500_000;
[1..0d100_000_000, N] // chunk and thread, 200 in this case
.apply(fcn(n){ n.filter(N,isSelfDescribing) }.future)
.filter().apply("noop").println();</
A future is a thread returning a [delayed] result, future.filter/future.noop will block until the future coughs up the result. Since the results are really sparse for the bigger numbers, filter out the empty results.
{{out}}
|