Self-describing numbers

From Rosetta Code
Revision as of 22:11, 29 May 2012 by rosettacode>Gerard Schildberger (→‎{{header|REXX}}: addec comments, add DO-END labels, removed blank lines. -- ~~~~)
This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.
Task
Self-describing numbers
You are encouraged to solve this task according to the task description, using any language you may know.

There are several integers numbers called "self-describing".

Integers with the property that, when digit positions are labeled 0 to N-1, the digit in each position is equal to the number of times that that digit appears in the number.

For example 2020 is a four digit self describing number.

Position "0" has value 2 and there is two 0 in the number. Position "1" has value 0 because there are not 1's in the number. Position "2" has value 2 and there is two 2. And the position "3" has value 0 and there are zero 3's.

Self-describing numbers < 100.000.000: 1210 - 2020 - 21200 - 3211000 - 42101000

Task Description
  1. Write a function/routine/method/... that will check whether a given positive integer is self-describing.
  2. As an optional stretch goal - generate and display the set of self-describing numbers.

Ada

<lang Ada>with Ada.Text_IO; use Ada.Text_IO; procedure SelfDesc is

  subtype Desc_Int is Long_Integer range 0 .. 10**10-1;
  function isDesc (innum : Desc_Int) return Boolean is
     subtype S_Int is Natural range 0 .. 10;
     type S_Int_Arr is array (0 .. 9) of S_Int;
     ref, cnt : S_Int_Arr := (others => 0);
     n, digit : S_Int := 0;  num : Desc_Int := innum;
  begin
     loop
        digit := S_Int (num mod 10);
        ref (9 - n) := digit;  cnt (digit) := cnt (digit) + 1;
        num := num / 10; exit when num = 0; n := n + 1;
     end loop;
     return ref (9 - n .. 9) = cnt (0 .. n);
  end isDesc;

begin

  for i in Desc_Int range 1 .. 100_000_000 loop
     if isDesc (i) then
        Put_Line (Desc_Int'Image (i));
     end if;
  end loop;

end SelfDesc;</lang>

Output:
1210
2020
21200
3211000
42101000

AutoHotkey

Uses CountSubString: http://rosettacode.org/wiki/Count_occurrences_of_a_substring#AutoHotkey <lang AutoHotkey>; The following directives and commands speed up execution:

  1. NoEnv

SetBatchlines -1 ListLines Off Process, Priority,, high

MsgBox % 2020 ": " IsSelfDescribing(2020) "`n" 1337 ": " IsSelfDescribing(1337) "`n" 1210 ": " IsSelfDescribing(1210) Loop 100000000

  If IsSelfDescribing(A_Index)
     list .= A_Index "`n"

MsgBox % "Self-describing numbers < 100000000 :`n" . list

CountSubstring(fullstring, substring){

  StringReplace, junk, fullstring, %substring%, , UseErrorLevel
  return errorlevel

}

IsSelfDescribing(number){

  Loop Parse, number
     If Not CountSubString(number, A_Index-1) = A_LoopField
        return false
  return true

}</lang> Output:

---------------------------
Self.ahk
---------------------------
Self-describing numbers < 100000000 :
1210
2020
21200
3211000
42101000

---------------------------
OK   
---------------------------

BASIC

<lang qbasic>Dim x, r, b, c, n, m As Integer Dim a, d As String Dim v(10), w(10) As Integer Cls For x = 1 To 5000000

  a$ = ltrim$(Str$(x))
  b = Len(a$)
  For c = 1 To b
     d$ = Mid$(a$, c, 1)
     v(Val(d$)) = v(Val(d$)) + 1
     w(c - 1) = Val(d$)
  Next c
  r = 0
  For n = 0 To 10
     If v(n) = w(n) Then r = r + 1 
     v(n) = 0 
     w(n) = 0
  Next n
  If r = 11 Then Print x; " Yes,is autodescriptive number"

Next x Print Print "End" sleep end</lang>

C

<lang c>#include <stdio.h>

int self_desc(char *s) { unsigned char cnt[10] = {0}; int i; for (i = 0; s[i] != '\0'; i++) cnt[s[i] - '0']++; for (i = 0; s[i] != '\0'; i++) if (cnt[i] + '0' != s[i]) return 0; return 1; }

void gen(int n) { char d[11]; int one, i; /* one = 0 may be confusing. 'one' is the number of digit 1s */ for (one = 0; one <= 2 && one < n - 2; one++) { for (i = 0; i <= n; d[i++] = 0);

if ((d[0] = n - 2 - one) != 2) { d[2] = d[d[0] - 0] = 1; d[1] = 2; } else { d[1] = one ? 1 : 0; d[2] = 2; }

for (i = 0; i < n; d[i++] += '0'); if (self_desc(d)) printf("%s\n", d); } }

int main() { int i; char *nums[] = { "1210", "1337", "2020", "21200", "3211000", "42101000", 0};

for (i = 0; nums[i]; i++) printf("%s is %sself describing\n", nums[i], self_desc(nums[i]) ? "" : "not ");

printf("\nAll autobiograph numbers:\n"); for (i = 0; i < 11; i++) gen(i); return 0; }</lang>output<lang>1210 is self describing 1337 is not self describing 2020 is self describing 21200 is self describing 3211000 is self describing 42101000 is self describing

All autobiograph numbers: 2020 1210 21200 3211000 42101000 521001000 6210001000</lang>

Alternative version

Using integers instead of strings. <lang c>#include <stdio.h>

inline int self_desc(unsigned long long xx) { register unsigned int d, x; unsigned char cnt[10] = {0}, dig[10] = {0};

for (d = 0; xx > ~0U; xx /= 10) cnt[ dig[d++] = xx % 10 ]++;

for (x = xx; x; x /= 10) cnt[ dig[d++] = x % 10 ]++;

while(d-- && dig[x++] == cnt[d]);

return d == -1; }

int main() { int i; for (i = 1; i < 100000000; i++) /* don't handle 0 */ if (self_desc(i)) printf("%d\n", i);

return 0; }</lang>output<lang>1210 2020 21200 3211000 42101000</lang>

D

A Functional Version

<lang d>import std.stdio, std.algorithm, std.range, std.conv;

bool isSelfDescribing(in long n) {

   auto nu = n.text().map!q{a - '0'}();
   return nu.equal( nu.length.iota().map!(a => count(nu, a))() );

}

void main() {

   writeln(iota(4_000_000).filter!isSelfDescribing());

}</lang>

Output:
[1210, 2020, 21200, 3211000]

(About 6.5 seconds run time.)

A Faster Version

<lang d>import std.stdio;

bool isSelfDescribing2(long n) {

 if (n <= 0)
   return false;
 __gshared static uint[10] digits, d;
 digits[] = 0;
 d[] = 0;
 int i;
 if (n < uint.max) {
   uint nu = cast(uint)n;
   for (i = 0; nu > 0 && i < digits.length; nu /= 10, i++) {
     d[i] = cast(ubyte)(nu % 10);
     digits[d[i]]++;
   }
   if (nu > 0)
     return false;
 } else {
   for (i = 0; n > 0 && i < digits.length; n /= 10, i++) {
     d[i] = cast(ubyte)(n % 10);
     digits[d[i]]++;
   }
   if (n > 0)
     return false;
 }
 foreach (k; 0 .. i)
   if (d[k] != digits[i - k - 1])
     return false;
 return true;

}

void main() {

 foreach (x; [1210, 2020, 21200, 3211000,
              42101000, 521001000, 6210001000])
   assert(isSelfDescribing2(x));

 foreach (i; 0 .. 4_000_000)
   if (isSelfDescribing2(i))
     writeln(i);

}</lang>

Output:
1210
2020
21200
3211000

(About 0.5 seconds run time for 4 million tests.)

Output with foreach(i;0..600_000_000):

1210
2020
21200
3211000
42101000
521001000

Forth

<lang forth>\ where unavailable.

third ( A b c -- A b c A ) >r over r> swap ;
(.) ( u -- c-addr u ) 0 <# #s #> ;

\ COUNT is a standard word with a very different meaning, so this \ would typically be beheaded, or given another name, or otherwise \ given a short lifespan, so to speak.

count ( c-addr1 u1 c -- c-addr1 u1 c+1 u )
 0 2over bounds do
   over i c@ = if 1+ then
 loop swap 1+ swap ;
self-descriptive? ( u -- f )
 (.) [char] 0 third third bounds ?do
   count i c@ [char] 0 - <> if drop 2drop false unloop exit then
 loop drop 2drop true ;</lang>

Go

<lang go>package main

import (

   "fmt"
   "strconv"
   "strings"

)

// task 1 requirement func sdn(n int64) bool {

   if n >= 1e10 {
       return false
   }
   s := strconv.FormatInt(n, 10)
   for d, p := range s {
       if int(p)-'0' != strings.Count(s, strconv.Itoa(d)) {
           return false
       }
   }
   return true

}

// task 2 code (takes a while to run) func main() {

   for n := int64(0); n < 1e10; n++ {
       if sdn(n) {
           fmt.Println(n)
       }
   }

}</lang> Output produced by above program:

1210
2020
21200
3211000
42101000
521001000
6210001000

Haskell

<lang Haskell>import Data.Char

count :: Int -> [Int] -> Int count x = length . filter (x ==)

isSelfDescribing :: Integer -> Bool isSelfDescribing n =

   nu == f where
           nu = map digitToInt (show n)
           f = map (\a -> count a nu) [0 .. ((length nu)-1)]

main = do

   let tests = [1210, 2020, 21200, 3211000,
                42101000, 521001000, 6210001000]
   print $ map isSelfDescribing tests
   print $ filter isSelfDescribing [0 .. 4000000]</lang>

Output:

[True,True,True,True,True,True,True]
[1210,2020,21200,3211000]

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). <lang haskell>import Data.Char (intToDigit) import Control.Monad (replicateM, forM_)

count :: Int -> [Int] -> Int count x = length . filter (x ==)

-- all the combinations of n digits of base n -- a base-n number are represented as a list of ints, one per digit allBaseNNumsOfLength :: Int -> Int allBaseNNumsOfLength n = replicateM n [0..n-1]

isSelfDescribing :: [Int] -> Bool isSelfDescribing num =

 all (\(i,x) -> x == count i num) $ zip [0..] num

-- translate it back into an integer in base-10 decimalize :: [Int] -> Int decimalize = read . map intToDigit

main = forM_ [1..7] $

 print . map decimalize . filter isSelfDescribing . allBaseNNumsOfLength</lang>

Icon and Unicon

The following program contains the procedure is_self_describing to test if a number is a self-describing number, and the procedure self_describing_numbers to generate them.

<lang Icon> procedure count (test_item, str)

 result := 0
 every item := !str do 
   if test_item == item then result +:= 1
 return result

end

procedure is_self_describing (n)

 ns := string (n) # convert to a string
 every i := 1 to *ns do {
   if count (string(i-1), ns) ~= ns[i] then fail
 }
 return 1 # success

end

  1. generator for creating self_describing_numbers

procedure self_describing_numbers ()

 n := 1
 repeat {
   if is_self_describing(n) then suspend n
   n +:= 1
 }

end

procedure main ()

 # write the first 4 self-describing numbers
 every write (self_describing_numbers ()\4)

end </lang> 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: <lang unicon> procedure is_self_describing (n)

 ns := string (n) # convert to a string
 every i := 1 to *ns do {
     if count (string(i-1), ns) ~= ns[i] then fail
     }
 return n # on success, return the self-described number

end

procedure self_describing_numbers ()

 suspend is_self_describing(seq())

end</lang>

J

Solution:<lang j> digits =: 10&#.^:_1

  counts   =: _1 + [: #/.~ i.@:# , ]
  selfdesc =: = counts&.digits"0       NB.  Note use of "under"</lang>

Example:<lang j> selfdesc 2020 1210 21200 3211000 43101000 42101000 1 1 1 1 0 1</lang> Extra credit:<lang j> I.@:selfdesc i. 1e6 1210 2020 21200</lang> Discussion: The use of &. here is a great example of its surprisingly broad applicability, and the elegance it can produce.

The use of "0 is less satisfying, expressing an essentially scalar solution, and that such an approach runs against the grain of J becomes quite evident when executing the extra credit sentence.

It would not be difficult to rephrase the verb in a way that would take advantage of J's array mastery, but it would cost us of some of the simplicity and elegance of the existing solution. More gratifying would be some kind of closed-form, algebraic formula that could identify the SDNs directly, without test-and-filter.

Java

<lang Java> public class SelfDescribingNumbers {

       public static boolean isSelfDescribing(int a){
               String s = Integer.toString(a);
               for (int i = 0; i < s.length(); i++)
               {
                       String s0 = s.charAt(i) + "";
                       int b = Integer.parseInt(s0); // number of times i-th digit must occur for it to be a self describing number
                       int count = 0;
                       for (int j = 0; j < s.length(); j++){
                               int temp = Integer.parseInt(s.charAt(j) + "");
                               if (temp == i){
                                       count++;
                               }
                               if (count > b) return false;
                       }
                       if (count != b) return false;
               }
               return true;
       }
       public static void main(String[] args){
               for (int i = 0; i < 100000000; i++){
                       if (isSelfDescribing(i)){
                               System.out.println(i);
                       }
               }
       }

}</lang>

JavaScript

Works with: SpiderMonkey

<lang javascript>function is_self_describing(n) {

   var digits = Number(n).toString().split("").map(function(elem) {return Number(elem)});
   var len = digits.length;
   var count = digits.map(function(x){return 0});
   digits.forEach(function(digit, idx, ary) {
       if (digit >= count.length)
           return false
       count[digit] ++;
   });
   return digits.equals(count);

}

Array.prototype.equals = function(other) {

   if (this === other)
       return true;  // same object
   if (this.length != other.length)
       return false;
   for (idx in this)
       if (this[idx] !== other[idx])
           return false;
   return true;

}

for (var i=1; i<=3300000; i++)

   if (is_self_describing(i))
       print(i);</lang>

outputs

1210
2020
21200
3211000

K

<lang k> sdn: {n~+/'n=/:!#n:0$'$x}'

 sdn 1210 2020 2121 21200 3211000 42101000

1 1 0 1 1 1

 &sdn@!:1e6

1210 2020 21200</lang>

<lang logo>TO XX BT MAKE "AA (ARRAY 10 0) MAKE "BB (ARRAY 10 0) FOR [Z 0 9][SETITEM :Z :AA "0 SETITEM :Z :BB "0 ]

  FOR [A 1 50000][
     MAKE "B COUNT :A
     MAKE "Y 0
     MAKE "X 0
     MAKE "R 0
     MAKE "J 0
     MAKE "K 0
  FOR [C 1 :B][MAKE "D ITEM :C :A
     SETITEM :C - 1 :AA :D 
     MAKE "X ITEM :D :BB 
     MAKE "Y :X + 1 
     SETITEM :D :BB :Y 
     MAKE "R 0]
  FOR [Z 0 9][MAKE "J ITEM :Z :AA 
     MAKE "K ITEM :Z :BB
     IF :J = :K [MAKE "R :R + 1]]

IF :R = 10 [PR :A] FOR [Z 0 9][SETITEM :Z :AA "0 SETITEM :Z :BB "0 ]] PR [END] END</lang>

Lua

<lang lua>function Is_self_describing( n )

   local s = tostring( n )
   local t = {}
   for i = 0, 9 do t[i] = 0 end
   for i = 1, s:len() do

local idx = tonumber( s:sub(i,i) )

       t[idx] = t[idx] + 1
   end
   for i = 1, s:len() do
       if t[i-1] ~= tonumber( s:sub(i,i) ) then return false end
   end
   return true

end

for i = 1, 999999999 do

   print( Is_self_describing( i ) )

end</lang>

Mathematica

<lang Mathematica>isSelfDescribing[n_Integer] := (RotateRight[DigitCount[n]] == PadRight[IntegerDigits[n], 10])</lang>

Select[Range[10^10 - 1], isSelfDescribing]
-> {1210,2020,21200,3211000,42101000,521001000,6210001000}

MATLAB / Octave

<lang Matlab>function z = isSelfDescribing(n)

 s = int2str(n)-'0';    % convert to vector of digits
 y = hist(s,0:9);
 z = all(y(1:length(s))==s);

end;</lang>

Test function:

<lang Matlab>for k = 1:1e10,

  if isSelfDescribing(k),
     printf('%i\n',k); 
  end 

end; </lang>

Output:

  1210
  2020
  21200
  ... 

Pascal

<lang pascal>Program SelfDescribingNumber;

uses

 SysUtils;
 

function check(number: longint): boolean;

 var
   i, d: integer;
   a: string;
   count, w : array [0..9] of integer;
 begin
   a := intToStr(number);
   for i := 0 to 9 do
   begin
     count[i] := 0;
     w[i] := 0;
   end;
   for i := 1 to length(a) do
   begin
     d := ord(a[i]) - ord('0');
     inc(count[d]);
     w[i - 1] := d;
   end;
   check := true;
   i := 0;
   while check and (i <= 9) do
   begin
     check := count[i] = w[i];
     inc(i);
   end;
 end;

var

 x: longint;

begin

 writeln ('Autodescriptive numbers from 1 to 100000000:');
 for x := 1 to 100000000 do
   if check(x) then
     writeln (' ', x);
 writeln('Job done.');

end.</lang> Output:

:> ./SelfDescribingNumber
Autodescriptive numbers from 1 to 100000000:
 1210
 2020
 21200
 3211000
 42101000
Job done.

Perl 6

<lang perl6>my @values = <1210 2020 21200 3211000 42101000 521001000 6210001000 27 115508>;

for @values -> $test {

   say "$test is {$test.&sdn ??  !! 'NOT ' }a self describing number.";

}

sub sdn ($num) {

   my @digits;
   my $chars = $num.chars;
   @digits[$_]++ for $num.comb;
   return 0 if @digits.elems > $chars;
   @digits[$_] //= '0' for ^$chars;
   my $string =  join , @digits;
   return 1 if $num eq $string;

}

say $_ if $_.&sdn for ^9999999;</lang> Output:

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

PicoLisp

<lang PicoLisp>(de selfDescribing (N)

  (not
     (find '((D I) (<> D (cnt = N (circ I))))
        (setq N (mapcar format (chop N)))
        (range 0 (length N)) ) ) )</lang>

Output:

: (filter selfDescribing (range 1 4000000))
-> (1210 2020 21200 3211000)

Prolog

Works with SWI-Prolog and library clpfd written by Markus Triska. <lang Prolog>:- use_module(library(clpfd)).

self_describling :- forall(between(1, 10, I), (findall(N, self_describling(I,N), L), format('Len ~w, Numbers ~w~n', [I, L]))).

% search of the self_describling numbers of a given len self_describling(Len, N) :- length(L, Len), Len1 is Len - 1, L = [H|T],

% the first figure is greater than 0 H in 1..Len1,

% there is a least to figures so the number of these figures % is at most Len - 2 Len2 is Len - 2, T ins 0..Len2,

% the sum of the figures is equal to the len of the number sum(L, #=, Len),

% There is at least one figure corresponding to the number of zeros H1 #= H+1, element(H1, L, V), V #> 0,

% create the list label(L),

% test the list msort(L, LNS), packList(LNS,LNP), numlist(0, Len1, NumList), verif(LNP,NumList, L),

% list is OK, create the number maplist(atom_number, LA, L), number_chars(N, LA).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % testing a number (not use in this program) self_describling(N) :- number_chars(N, L), maplist(atom_number, L, LN), msort(LN, LNS), packList(LNS,LNP), !, length(L, Len), Len1 is Len - 1, numlist(0, Len1, NumList), verif(LNP,NumList, LN).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % verif(PackList, Order_of_Numeral, Numeral_of_the_nuber_to_test) % Packlist is of the form [[Number_of_Numeral, Order_of_Numeral]|_] % Test succeed when

% All lists are empty verif([], [], []).

% Packlist is empty and all lasting numerals are 0 verif([], [_N|S], [0|T]) :- verif([], S, T).

% Number of numerals N is V verif([[V, N]|R], [N|S], [V|T]) :- verif(R, S, T).

% Number of numerals N is 0 verif([[V, N1]|R], [N|S], [0|T]) :- N #< N1, verif([[V,N1]|R], S, T).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % ?- packList([a,a,a,b,c,c,c,d,d,e], L). % L = [[3,a],[1,b],[3,c],[2,d],[1,e]] . % ?- packList(R, [[3,a],[1,b],[3,c],[2,d],[1,e]]). % R = [a,a,a,b,c,c,c,d,d,e] . % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% packList([],[]).

packList([X],1,X) :- !.


packList([X|Rest],[XRun|Packed]):-

   run(X,Rest, XRun,RRest),
   packList(RRest,Packed).


run(Var,[],[1, Var],[]).

run(Var,[Var|LRest],[N1, Var],RRest):-

   N #> 0,
   N1 #= N + 1,
   run(Var,LRest,[N, Var],RRest).


run(Var,[Other|RRest], [1, Var],[Other|RRest]):-

   dif(Var,Other).</lang>

Output

 ?- self_describling.
Len 1, Numbers []
Len 2, Numbers []
Len 3, Numbers []
Len 4, Numbers [1210,2020]
Len 5, Numbers [21200]
Len 6, Numbers []
Len 7, Numbers [3211000]
Len 8, Numbers [42101000]
Len 9, Numbers [521001000]
Len 10, Numbers [6210001000]
true.

PureBasic

<lang PureBasic>Procedure isSelfDescribing(x.q)

 ;returns 1 if number is self-describing, otherwise it returns 0
 Protected digitCount, digit, i, digitSum
 Dim digitTally(10)
 Dim digitprediction(10)
 
 If x <= 0
   ProcedureReturn 0 ;number must be positive and non-zero
 EndIf 
 
 While x > 0 And i < 10
   digit = x % 10
   digitSum + digit
   If digitSum > 10
     ProcedureReturn 0 ;sum of digits' values exceeds maximum possible
   EndIf 
   digitprediction(i) = digit 
   digitTally(digit) + 1
   x / 10
   i + 1 
 Wend 
 digitCount = i - 1
 
 If digitSum < digitCount Or x > 0
   ProcedureReturn 0  ;sum of digits' values is too small or number has more than 10 digits
 EndIf 
 
 For i = 0 To digitCount
   If digitTally(i) <> digitprediction(digitCount - i)
     ProcedureReturn 0 ;number is not self-describing
   EndIf
 Next
 ProcedureReturn 1 ;number is self-describing

EndProcedure

Procedure displayAll()

 Protected i, j, t
 PrintN("Starting search for all self-describing numbers..." + #CRLF$)
 For j = 0 To 9
   PrintN(#CRLF$ + "Searching possibilites " + Str(j * 1000000000) + " -> " + Str((j + 1) * 1000000000 - 1)+ "...")
   t = ElapsedMilliseconds()
   For i = 0 To 999999999
     If isSelfDescribing(j * 1000000000 + i)
       PrintN(Str(j * 1000000000 + i))
     EndIf 
   Next
   PrintN("Time to search this range of possibilities: " + Str((ElapsedMilliseconds() - t) / 1000) + "s.")
 Next 
 PrintN(#CRLF$ + "Search complete.")

EndProcedure

If OpenConsole()

 DataSection
   Data.q 1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000, 3214314
 EndDataSection
 
 Define i, x.q
 For i = 1 To 8
   Read.q x
   Print(Str(x) + " is ")
   If Not isSelfDescribing(x)
     Print("not ")
   EndIf
   PrintN("selfdescribing.")
 Next 
 PrintN(#CRLF$)
 
 displayAll()
 
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
 CloseConsole()

EndIf</lang> Sample output:

1210 is selfdescribing.
2020 is selfdescribing.
21200 is selfdescribing.
3211000 is selfdescribing.
42101000 is selfdescribing.
521001000 is selfdescribing.
6210001000 is selfdescribing.
3214314 is not selfdescribing.


Starting search for all self-describing numbers...


Searching possibilites 0 -> 999999999...
1210
2020
21200
3211000
42101000
521001000
Time to search this range of possibilities: 615s.

Searching possibilites 1000000000 -> 1999999999...
Time to search this range of possibilities: 614s.

Searching possibilites 2000000000 -> 2999999999...
Time to search this range of possibilities: 628s.

Searching possibilites 3000000000 -> 3999999999...
Time to search this range of possibilities: 631s.

Searching possibilites 4000000000 -> 4999999999...
Time to search this range of possibilities: 630s.

Searching possibilites 5000000000 -> 5999999999...
Time to search this range of possibilities: 628s.

Searching possibilites 6000000000 -> 6999999999...
6210001000
Time to search this range of possibilities: 629s.

Searching possibilites 7000000000 -> 7999999999...
Time to search this range of possibilities: 631s.

Searching possibilites 8000000000 -> 8999999999...
Time to search this range of possibilities: 629s.

Searching possibilites 9000000000 -> 9999999999...
Time to search this range of possibilities: 629s.

Search complete.

Python

<lang python>>>> def isSelfDescribing(n): s = str(n) return all(s.count(str(i)) == int(ch) for i, ch in enumerate(s))

>>> [x for x in range(4000000) if isSelfDescribing(x)] [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)]</lang>

Generator

From here. <lang python>def impl(d, c, m):

   if m < 0: return
   if d == c[:len(d)]: print d
   for i in range(c[len(d)],m+1):
       dd = d+[i]
       if i<len(dd) and c[i]==dd[i]: continue
       impl(dd,c[:i]+[c[i]+1]+c[i+1:],m-i)

def self(n): impl([], [0]*(n+1), n)

self(10)</lang> Output:

[]
[1, 2, 1, 0]
[2, 0, 2, 0]
[2, 1, 2, 0, 0]
[3, 2, 1, 1, 0, 0, 0]
[4, 2, 1, 0, 1, 0, 0, 0]
[5, 2, 1, 0, 0, 1, 0, 0, 0]
[6, 2, 1, 0, 0, 0, 1, 0, 0, 0] 

REXX

No trees died to produce this output, but plenty of electrons died. <lang rexx>/*REXX program to check if a number (base 10) is self-describing. */ parse arg x y . /*get the user's args from the CL*/ if x== then exit /*if no X, then get out of Dodge.*/ if y== then y=x /*if no Y, then use the X value. */ y=min(y,999999999) w=length(y) /*use Y's width for pretty output*/ call time 'R' /*reset the REXX elapsed timer. */ /*──────────────────────────────────────test for a single number. */ if x==y then do

            noYes=test_sdn(y)
            say y word("is isn't",noYes+1) 'a self-describing number.'
            exit
            end

/*──────────────────────────────────────test for a range of numbers. */

        do n=x to y
        if test_sdn(n) then iterate   /*if ¬ self-describing, try again*/
        say right(n,w) 'is a self-describing number.',
                      format(time('E'),,2) "seconds."
        end   /*n*/

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────────TEST_SDN subroutine─────────────*/ test_sdn: procedure; parse arg x; L=length(x)

    do j=L  to 1  by -1               /*backwards is slightly faster.  */
    if substr(x,j,1)\==L-length(space(translate(x,,j-1),0)) then return 1
    end   /*j*/

return 0 /*faster if inverted truth table.*/ /* ┌──────────────────────────────────────────────────────────────────┐

  │ The method used above is to TRANSLATE the digit being queried to │
  │ blanks, then use the  SPACE  function to remove all blanks,  and │
  │ then compare the new   X's  length to the original length.  The  │
  │ difference in length is the number of digits translated.         │
  └──────────────────────────────────────────────────────────────────┘ */</lang>

output when using the input of: 0 999999999

      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.

Ruby

<lang ruby>def is_self_describing?(n)

 digits = n.to_s.chars.collect {|digit| digit.to_i}
 len = digits.length
 count = Array.new(len, 0)
 digits.each do |digit| 
   return false if digit >= len
   count[digit] = count[digit] + 1
 end
 digits.eql?(count)

end

3_300_000.times {|n| puts n if is_self_describing?(n)}</lang> outputs

1210
2020
21200
3211000

Tcl

<lang tcl>package require Tcl 8.5 proc isSelfDescribing num {

   set digits [split $num ""]
   set len [llength $digits]
   set count [lrepeat $len 0]
   foreach d $digits {

if {$d >= $len} {return false} lset count $d [expr {[lindex $count $d] + 1}]

   }
   foreach d $digits c $count {if {$c != $d} {return false}}
   return true

}

for {set i 0} {$i < 100000000} {incr i} {

   if {[isSelfDescribing $i]} {puts $i}

}</lang>