Self-describing numbers: Difference between revisions

Content added Content deleted

Inline

Revision as of 12:18, 30 April 2020

This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.

There are several so-called "self-describing" or "self-descriptive" integers.

An integer is said to be "self-describing" if it has 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 are two 0s in the number;
position 1 has value 0 and there are no 1s in the number;
position 2 has value 2 and there are two 2s;
position 3 has value 0 and there are zero 3s.

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

Task Description

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

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:

ALGOL 68

Works with: ALGOL 68 version Revision 1 - no extensions to language used

Works with: ALGOL 68G version Any - tested with release 2.6.win32

<lang algol68>BEGIN

   # return TRUE if number is self describing, FALSE otherwise #
   OP SELFDESCRIBING = ( INT number )BOOL:
      BEGIN

          [10]INT counts := ( 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 );
          INT n          := number;
          INT digits     := 0;

          # count the occurances of each digit #
          WHILE
              n /= 0
          DO
              digits +:= 1;
              counts[ ( n MOD 10 ) + 1 ] +:= 1;
              n OVERAB 10
          OD;

          # construct the number that the counts would describe, #
          # if the number was self describing                    #

          INT described number := 0;
          FOR i TO digits
          DO
              described number *:= 10;
              described number +:= counts[ i ]
          OD;

          # if the described number is the input number, #
          # it is self describing #
          ( number = described number )
      END; # SELFDESCRIBING #

main: (

   FOR i TO 100 000 000
   DO
       IF SELFDESCRIBING i
       THEN
           print( ( i, " is self describing", newline ) )
       FI
   OD

)

END</lang>

Output:

      +1210 is self describing
      +2020 is self describing
     +21200 is self describing
   +3211000 is self describing
  +42101000 is self describing

AppleScript

<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({¬
       "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"}))
   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|

-- eq (==) :: Eq a => a -> a -> Bool on eq(a, b)

   a = b

end eq

-- 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</lang>

Output:

1210 -> true
1211 -> false
2020 -> true
2022 -> false
21200 -> true
21203 -> false
3211000 -> true
3211004 -> false

AutoHotkey

Uses CountSubString: Count occurrences of a substring#AutoHotkey <lang AutoHotkey>; The following directives and commands speed up execution:

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   
---------------------------

AWK

<lang AWK># syntax: GAWK -f SELF-DESCRIBING_NUMBERS.AWK BEGIN {

   for (n=1; n<=100000000; n++) {
     if (is_self_describing(n)) {
       print(n)
     }
   }
   exit(0)

} function is_self_describing(n, i) {

   for (i=1; i<=length(n); i++) {
     if (substr(n,i,1) != gsub(i-1,"&",n)) {
       return(0)
     }
   }
   return(1)

}</lang>

output:

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>

BBC BASIC

Works with: BBC BASIC for Windows

<lang bbcbasic> FOR N = 1 TO 5E7

       IF FNselfdescribing(N) PRINT N
     NEXT
     END
     
     DEF FNselfdescribing(N%)
     LOCAL D%(), I%, L%, O%
     DIM D%(9)
     O% = N%
     L% = LOG(N%)
     WHILE N%
       I% = N% MOD 10
       D%(I%) += 10^(L%-I%)
       N% DIV=10
     ENDWHILE
     = O% = SUM(D%())</lang>

Output:

Befunge

Translation of: ALGOL 68

Although we simply list the conforming numbers - nothing more.

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.

<lang befunge>>1+9:0>\#06#:p#-:#1_$v ?v6:%+55:\+1\<<<\0:::<

>g1+\6p55+/:#^_001p\v

^_@#!`<<v\+g6g10*+55\< >:*:*:*^>>:01g1+:01p`| ^_\#\:#+.#5\#5,#$:<-$<</lang>

Output:

C

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>

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). <lang c>#include <stdio.h>

include <stdlib.h>
include <string.h>

define BASE_MIN 2
define BASE_MAX 94

void selfdesc(unsigned long);

const char *ref = "!\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~"; char *digs; unsigned long *nums, *inds, inds_sum, inds_val, base;

int main(int argc, char *argv[]) { int used[BASE_MAX]; unsigned long digs_n, i; if (argc != 2) { fprintf(stderr, "Usage is %s <digits>\n", argv[0]); return EXIT_FAILURE; } digs = argv[1]; digs_n = strlen(digs); if (digs_n < BASE_MIN || digs_n > BASE_MAX) { fprintf(stderr, "Invalid number of digits\n"); return EXIT_FAILURE; } for (i = 0; i < BASE_MAX; i++) { used[i] = 0; } for (i = 0; i < digs_n && strchr(ref, digs[i]) && !used[digs[i]-*ref]; i++) { used[digs[i]-*ref] = 1; } if (i < digs_n) { fprintf(stderr, "Invalid digits\n"); return EXIT_FAILURE; } nums = calloc(digs_n, sizeof(unsigned long)); if (!nums) { fprintf(stderr, "Could not allocate memory for nums\n"); return EXIT_FAILURE; } inds = malloc(sizeof(unsigned long)*digs_n); if (!inds) { fprintf(stderr, "Could not allocate memory for inds\n"); free(nums); return EXIT_FAILURE; } inds_sum = 0; inds_val = 0; for (base = BASE_MIN; base <= digs_n; base++) { selfdesc(base); } free(inds); free(nums); return EXIT_SUCCESS; }

void selfdesc(unsigned long i) { unsigned long diff_sum, upper_min, j, lower, upper, k; if (i) { diff_sum = base-inds_sum; upper_min = inds_sum ? diff_sum:base-1; j = i-1; if (j) { lower = 0; upper = (base-inds_val)/j; } else { lower = diff_sum; upper = diff_sum; } if (upper < upper_min) { upper_min = upper; } for (inds[j] = lower; inds[j] <= upper_min; inds[j]++) { nums[inds[j]]++; inds_sum += inds[j]; inds_val += inds[j]*j; for (k = base-1; k > j && nums[k] <= inds[k] && inds[k]-nums[k] <= i; k--); if (k == j) { selfdesc(i-1); } inds_val -= inds[j]*j; inds_sum -= inds[j]; nums[inds[j]]--; } } else { for (j = 0; j < base; j++) { putchar(digs[inds[j]]); } puts(""); } }</lang>

Output for base 36 <lang>$ time ./selfdesc.exe 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ 1210 2020 21200 3211000 42101000 521001000 6210001000 72100001000 821000001000 9210000001000 A2100000001000 B21000000001000 C210000000001000 D2100000000001000 E21000000000001000 F210000000000001000 G2100000000000001000 H21000000000000001000 I210000000000000001000 J2100000000000000001000 K21000000000000000001000 L210000000000000000001000 M2100000000000000000001000 N21000000000000000000001000 O210000000000000000000001000 P2100000000000000000000001000 Q21000000000000000000000001000 R210000000000000000000000001000 S2100000000000000000000000001000 T21000000000000000000000000001000 U210000000000000000000000000001000 V2100000000000000000000000000001000 W21000000000000000000000000000001000

real 0m0.094s user 0m0.046s sys 0m0.030s</lang>

C++

include <iostream>

//-------------------------------------------------------------------------------------------------- typedef unsigned long long bigint;

//-------------------------------------------------------------------------------------------------- using namespace std;

//-------------------------------------------------------------------------------------------------- class sdn { public:

   bool check( bigint n )
   {

int cc = digitsCount( n ); return compare( n, cc );

   }

   void displayAll( bigint s )
   {

for( bigint y = 1; y < s; y++ ) if( check( y ) ) cout << y << " is a Self-Describing Number." << endl;

private:

   bool compare( bigint n, int cc )
   {

bigint a; while( cc ) { cc--; a = n % 10; if( dig[cc] != a ) return false; n -= a; n /= 10; } return true;

   }

   int digitsCount( bigint n )
   {

int cc = 0; bigint a; memset( dig, 0, sizeof( dig ) ); while( n ) { a = n % 10; dig[a]++; cc++ ; n -= a; n /= 10; } return cc;

   }

   int dig[10];

}; //-------------------------------------------------------------------------------------------------- int main( int argc, char* argv[] ) {

   sdn s;
   s. displayAll( 1000000000000 );
   cout << endl << endl; system( "pause" );

   bigint n;
   while( true )
   {

system( "cls" ); cout << "Enter a positive whole number ( 0 to QUIT ): "; cin >> n; if( !n ) return 0; if( s.check( n ) ) cout << n << " is"; else cout << n << " is NOT"; cout << " a Self-Describing Number!" << endl << endl; system( "pause" );

   }

   return 0;

} </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.
[...]

Alternate version

Uses C++11. Build with

g++ -std=c++11 sdn.cpp

<lang cpp>#include <algorithm>

include <array>
include <iostream>

bool is_self_describing(unsigned long long int n) noexcept {

 if (n == 0) {
   return false;
 }

 std::array<char, 10> digits = {0}, counts = {0};
 std::size_t i = digits.size();

 do {
   counts[digits[--i] = n % 10]++;
 } while ((n /= 10) > 0 && i < digits.size());

 return n == 0 && std::equal(begin(digits) + i, end(digits), begin(counts));

}

int main() {

 for (unsigned long long int i = 0; i < 10000000000; ++i) {
   if (is_self_describing(i)) {
     std::cout << i << "\n";
   }
 }

}</lang> Output:

Common Lisp

Not terribly speedy brute force. I played around with "counting" the digits directly into a number by adding in appropriate powers of 10 for each digit I see but trailing zeroes kind of gum up the works. I still think it's possible and 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. <lang lisp>(defun to-ascii (str) (mapcar #'char-code (coerce str 'list)))

(defun to-digits (n)

 (mapcar #'(lambda(v) (- v 48)) (to-ascii  (princ-to-string n))))

(defun count-digits (n)

 (do
     ((counts (make-array '(10) :initial-contents '(0 0 0 0 0 0 0 0 0 0)))
      (curlist (to-digits n) (cdr curlist)))
     ((null curlist) counts)
   (setf (aref counts (car curlist)) (+ 1 (aref counts (car curlist)))))))

(defun self-described-p (n)

 (if (not (numberp n))
     nil
 (do ((counts (count-digits n))
      (ipos 0 (+ 1 ipos))
      (digits (to-digits n) (cdr digits)))
     ((null digits) t)
   (if (not (eql (car digits) (aref counts ipos))) (return nil)))))</lang>

Output: <lang>(loop for i from 1 to 4000000 do (if (self-described-p i) (print i)))

1210 2020 21200 3211000 NIL</lang>

Crystal

Translation of: Ruby

<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) }</lang>
System: I5-2410m, 2.9 GHz, Linux Kernel 5.5.17, Crystal 0.34
Compil: $ crystal build selfdescribing.cr --release
Run as: $ time ./selfdescribing

Output:

1210 in 0.000405621 secs
2020 in 0.000260327 secs
21200 in 0.005639628 secs
3211000 in 0.799380182 secs
42101000 in 9.825958853 secs
521001000 in 127.339214639 secs
./selfdescribing  171.69s user 7.81s system 112% cpu 2:38.96 total

Translation of: Wren and Go

<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")</lang>

System: I5-2410m, 2.9 GHz, Linux Kernel 5.5.17, Crystal 0.34
Run as: $ crystal selfdescribing.cr --release

Output:

The self-describing numbers are:
1210 in 2.8282e-5 secs
2020 in 5.823e-5 secs
21200 in 0.000171366 secs
3211000 in 0.025022473 secs
42101000 in 0.279668575 secs
521001000 in 3.864771331 secs
6210001000 in 52.883335718 secs
Took 63.117831317 secs overall

D

Functional Version

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

bool isSelfDescribing(in long n) pure nothrow @safe {

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

}

void main() {

   4_000_000.iota.filter!isSelfDescribing.writeln;

}</lang>

Output:

[1210, 2020, 21200, 3211000]

A Faster Version

<lang d>bool isSelfDescribing2(ulong n) nothrow @nogc {

 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] = nu % 10;
     digits[d[i]]++;
   }
   if (nu > 0)
     return false;
 } else {
   for (i = 0; n > 0 && i < digits.length; n /= 10, i++) {
     d[i] = n % 10;
     digits[d[i]]++;
   }
   if (n > 0)
     return false;
 }

 foreach (immutable k; 0 .. i)
   if (d[k] != digits[i - k - 1])
     return false;
 return true;

}

void main() {

 import std.stdio;

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

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

}</lang>

Output:

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

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

Elixir

<lang elixir>defmodule Self_describing do

 def number(n) do
   digits = Integer.digits(n)
   Enum.map(0..length(digits)-1, fn s ->
     length(Enum.filter(digits, fn c -> c==s end))
   end) == digits
 end

end

m = 3300000 Enum.filter(0..m, fn n -> Self_describing.number(n) end)</lang>

Output:

[1210, 2020, 21200, 3211000]

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)).

</lang>

Factor

<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 .</lang>

Output:

V{ 1210 2020 21200 3211000 42101000 }

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>

FreeBASIC

<lang freebasic>' FB 1.05.0 Win64

Function selfDescribing (n As UInteger) As Boolean

  If n = 0 Then Return False
  Dim ns As String = Str(n)
  Dim count(0 To 9) As Integer  all elements zero by default
  While n > 0
    count(n Mod 10) += 1
    n \= 10
  Wend
  For i As Integer = 0 To Len(ns) - 1
    If ns[i] - 48 <> count(i) Then Return False  numerals have ascii values from 48 to 57
  Next
  Return True

End Function

Print "The self-describing numbers less than 100 million are:" For i As Integer = 0 To 99999999

 If selfDescribing(i) Then Print i; " ";

Next Print Print "Press any key to quit" Sleep</lang>

Output:

The self-describing numbers less than 100 million are:
 1210  2020  21200  3211000  42101000

Go

Original

<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:

Optimized

Uses the optimized loop from the Wren entry - 12 times faster than before. <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)

}</lang>

Output:

Timings are for an Intel Core i7-8565U machine running Go 1.14.2 on Ubuntu 18.04.

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

Haskell

<lang Haskell>import Data.Char

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

isSelfDescribing :: Integer -> Bool isSelfDescribing n = nu == f

 where
   nu = digitToInt <$> show n
   f = (`count` nu) <$> [0 .. length nu - 1]

main :: IO () main = do

 print $
   isSelfDescribing <$>
   [1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000]
 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 = replicateM <*> (enumFromTo 0 . subtract 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 :: IO () main =

 (print . concat) $
 map decimalize . filter isSelfDescribing . allBaseNNumsOfLength <$> [1 .. 8]</lang>

Output:

[1210,2020,21200,3211000,42101000]

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

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.

That said, note that this is an incomplete implementation of the extra-credit problem -- and, hypothetically speaking, numbers longer than 9 digits could be valid results in the extra-credit problem (we just have to be sure that digit positions which are not occupied by digits we can represent have 0 for their count). This might allow us to treat numbers up to just under 19 digits as self describing numbers. This is a slightly larger range of numbers than we get for positive integers from signed 64 bit representation. So a proper solution to this problem on currently available hardware (one that finds the complete result in some useful span of time) probably should use a non-brute-force solution.

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

jq

Works with: jq version 1.4

<lang jq># If your jq includes all/2 then comment out the following definition,

which is slightly less efficient:

def all(generator; condition):

 reduce generator as $i (true; if . then $i | condition else . end);</lang>

<lang jq>def selfie:

 def count(value): reduce .[] as $i (0; if $i == value then . + 1 else . end);
 def digits: tostring | explode | map(. - 48);

 digits
 | if  add != length then false
   else . as $digits
   | all ( range(0; length); . as $i | $digits | (.[$i] == count($i)) )
   end;</lang>

The task: <lang jq>range(0; 100000001) | select(selfie)</lang>

Output:

<lang sh>$ jq -n -f Self-describing_numbers.jq 1210 2020 21200 3211000 42101000</lang>

Julia

Works with: Julia version 0.6

<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(2020) @show selfie(2021)

selfies(x) = for i in 1:x selfie(i) && println(i) end @time selfies(4000000)</lang>

Output:

1210
2020
21200
3211000
  1.398922 seconds (8.01 M allocations: 1.049 GiB, 6.91% gc time)

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>

Kotlin

<lang scala>// version 1.0.6

fun selfDescribing(n: Int): Boolean {

   if (n <= 0) return false
   val ns = n.toString()
   val count = IntArray(10)
   var nn = n
   while (nn > 0) {
       count[nn % 10] += 1
       nn /= 10
   }
   for (i in 0 until ns.length) 
       if( ns[i] - '0' != count[i]) return false
   return true

}

fun main(args: Array<String>) {

   println("The self-describing numbers less than 100 million are:")
   for (i in 0..99999999) if (selfDescribing(i)) print("$i ")
   println()

}</lang>

Output:

The self-describing numbers less than 100 million are:
1210 2020 21200 3211000 42101000

Liberty BASIC

<lang lb>'adapted from BASIC solution FOR x = 1 TO 5000000

  a$ = TRIM$(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; " is a self-describing number"

NEXT x PRINT PRINT "End"</lang>

LiveCode

<lang LiveCode>function selfDescNumber n

   local tSelfD, tLen
   put len(n) into tLen
   repeat with x = 0 to (tLen - 1)
       put n into nCopy
       replace x with empty in nCopy 
       put char (x + 1) of n = (tLen - len(nCopy)) into tSelfD
       if not tSelfD then exit repeat
   end repeat
   return tSelfD

end selfDescNumber</lang> To list the self-describing numbers to 10 million<lang LiveCode>on mouseUp

   repeat with n = 0 to 10000000
       if selfDescNumber(n) then
           put n into selfNum[n]
       end if
   end repeat
   combine selfNum using comma
   put selfNum

end mouseUp</lang> Output<lang LiveCode>1210,2020,21200,3211000</lang>

Logo

<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:

MiniScript

<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 </lang>

Output:

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

Modula-2

Translation of: Pascal

Works with: ADW Modula-2 version any (Compile with the linker option Console Application).

<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. </lang>

Output:

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

Nim

<lang nim>import strutils

proc count(s, sub): int =

 var i = 0
 while true:
   i = s.find(sub, i)
   if i < 0:
     break
   inc i
   inc result

proc isSelfDescribing(n): bool =

 let s = $n
 for i, ch in s:
   if s.count($i) != parseInt("" & ch):
     return false
 return true

for x in 0 .. 4_000_000:

 if isSelfDescribing(x): echo x</lang>

Output:

ooRexx

<lang ooRexx> -- REXX program to check if a number (base 10) is self-describing. parse arg x y . if x== then exit if y== then y=x -- 10 digits is the maximum size number that works here, so cap it numeric digits 10 y=min(y, 9999999999)

loop number = x to y

 loop i = 1 to number~length
     digit = number~subchar(i)
     -- return on first failure
     if digit \= number~countstr(i - 1) then iterate number
  end
  say number "is a self describing number"

end </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.

PARI/GP

This is a finite set... <lang parigp>S=[1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000]; isself(n)=vecsearch(S,n)</lang>

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

The idea is to make two arrays: the first one contains the digits at their positions and the second one contains the digits counts.

The number is self-descriptive If the arrays are equal. <lang perl>sub is_selfdesc { local $_ = shift; my @b = (0) x length; $b[$_]++ for my @a = split //; return "@a" eq "@b"; }

check all numbers from 0 to 100k plus two 'big' ones

for (0 .. 100000, 3211000, 42101000) { print "$_\n" if is_selfdesc($_); }</lang> Output:

Phix

Translation of: Ada

<lang Phix>function self_desc(integer i) sequence digits = repeat(0,10), counts = repeat(0,10) integer n = 0, digit

   while 1 do
       digit := mod(i,10)
       digits[10-n] := digit
       counts[digit+1] += 1
       i = floor(i/10)
       if i=0 then exit end if
       n += 1
   end while
   return digits[10-n..10] = counts[1..n+1]

end function

atom t0 = time() for i=10 to 100_000_000 by 10 do

   if self_desc(i) then ?i end if

end for printf(1,"done (%3.2fs)",time()-t0)</lang>

Output:

1210
2020
21200
3211000
42101000
done (21.78s)

generator

Translation of: Python

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 half 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. <lang Phix>procedure impl(sequence d, c, integer m)

   if m>=0 then
       integer l = length(d)
       if l and d == c[1..l] then
           string ds = ""
           for i=1 to l do
               integer ch = d[i]+'0'
               if ch>'9' then ch += 'a'-'9'-1 end if
               ds &= ch
           end for
           printf(1,"%s\n",ds)
       end if
       sequence dd = d&0
       for i=c[l+1] to m do
           dd[$] = i
           if i>l or c[i+1]!=dd[i+1] then
               c[i+1] += 1
               impl(dd,c,m-i)
               c[i+1] -= 1
           end if
       end for 
   end if

end procedure

procedure self(integer n)

   impl({}, repeat(0,n+1), n)

end procedure self(20)</lang>

Output:

1210
2020
21200
3211000
42101000
521001000
6210001000
72100001000
821000001000
9210000001000
a2100000001000
b21000000001000
c210000000001000
d2100000000001000
e21000000000001000
f210000000000001000
g2100000000000001000

even faster

Finishes in less than a tenth of a second

Translation of: Seed7

<lang Phix>constant string aleph = tagset('9','0')&tagset('z','a')&tagset('Z','A')

procedure gen(integer n)

   for ones=0 to min(2,n-3) do
       sequence digits = repeat(0,n),
                counts = repeat(0,n)
       digits[1] := n-2-ones
       if digits[1]<>2 then
           digits[digits[1]+1] := 1
           digits[2] := 2
           digits[3] := 1
       else
           digits[2] := (ones<>0)
           digits[3] := 2
       end if
       for i=1 to n do
           counts[digits[i]+1] += 1
       end for
       if counts=digits then
           string s = ""
           for i=1 to n do
               integer di = digits[i]
               s &= aleph[di+1]
           end for
           printf(1,"%s\n",s)
       end if
   end for

end procedure

for n=1 to length(aleph)+3 do

   gen(n)

end for</lang>

Output:

as above plus

h21000000000000001000
i210000000000000001000
...
z21000000000000000000000000000000001000
A210000000000000000000000000000000001000
...
Z2100000000000000000000000000000000000000000000000000000000001000

PHP

Works with: PHP 5.

<lang PHP><?php

function is_describing($number) {

   foreach (str_split((int) $number) as $place => $value) {
       if (substr_count($number, $place) != $value) { 
           return false;
       }
   }    
   return true;

}

for ($i = 0; $i <= 50000000; $i += 10) {

   if (is_describing($i)) {
       echo $i . PHP_EOL;
   }

}

?></lang>

Output:

PicoLisp

<lang PicoLisp>(de selfDescribing (N)

  (fully '((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)

PowerShell

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: <lang PowerShell> function Test-SelfDescribing ([int]$Number) {

   [int[]]$digits = $Number.ToString().ToCharArray() | ForEach-Object {[Char]::GetNumericValue($_)}
   [int]$sum = 0

   for ($i = 0; $i -lt $digits.Count; $i++)
   { 
       $sum += $i * $digits[$i]
   }

   $sum -eq $digits.Count

} </lang> <lang PowerShell> Test-SelfDescribing -Number 2020 </lang>

Output:

True

It takes a very long while to test 100,000,000 numbers, and since they are already known just test a few: <lang PowerShell> 11,2020,21200,321100 | ForEach-Object {

   [PSCustomObject]@{
       Number = $_
       IsSelfDescribing = Test-SelfDescribing -Number $_
   }

} | Format-Table -AutoSize </lang>

Output:

Number IsSelfDescribing
------ ----------------
    11            False
  2020             True
 21200             True
321100            False

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]

Racket

<lang Racket>#lang racket (define (get-digits number (lst null))

 (if (zero? number)
     lst
     (get-digits (quotient number 10) (cons (remainder number 10) lst))))

(define (self-describing? number)

 (if (= number 0) #f
     (let ((digits (get-digits number)))
       (for/fold ((bool #t))
         ((i (in-range (length digits))))
         (and bool
              (= (count (lambda (x) (= x i)) digits)
                 (list-ref digits i)))))))</lang>

Sadly, the implementation is too slow for the optional task, taking somewhere around 3 minutes to check all numbers below 100.000.000

Raku

(formerly Perl 6) <lang perl6>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;</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

Red

<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] ] </lang> output

REXX

Also see: OEIS A46043 and OEIS A138480.

digit by digit test

<lang rexx>/*REXX program determines if a number (in base 10) is a self─describing, */ /*────────────────────────────────────────────────────── self─descriptive, */ /*────────────────────────────────────────────────────── autobiographical, or a */ /*────────────────────────────────────────────────────── curious number. */ parse arg x y . /*obtain optional arguments from the CL*/ if x== | x=="," then exit /*Not specified? Then get out of Dodge*/ if y== | y=="," then y=x /* " " Then use the X value.*/ w=length(y) /*use Y's width for aligned output. */ numeric digits max(9, w) /*ensure we can handle larger numbers. */ if x==y then do /*handle the case of a single number. */

             noYes=test_SDN(y)                  /*is it  or  ain't it?                 */
             say y  word("is isn't", noYes+1)  'a self-describing number.'
             exit
             end

        do n=x  to  y
        if test_SDN(n)  then iterate            /*if not self─describing,  try again.  */
        say  right(n,w)  'is a self-describing number.'                       /*is it? */
        end   /*n*/

exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ test_SDN: procedure; parse arg ?; L=length(?) /*obtain the argument and its length.*/

                   do j=L  to 1  by -1          /*parsing backwards is slightly faster.*/
                   if substr(?,j,1)\==L-length(space(translate(?,,j-1),0))  then return 1
                   end   /*j*/
         return 0                               /*faster if used inverted truth table. */</lang>

        ╔══════════════════════════════════════════════════════════════════╗
        ║ The method used above is to TRANSLATE the digit being queried to ║
        ║ blanks,  then use the  SPACE  BIF function to remove all blanks, ║
        ║ and then compare the new number's length to the original length. ║
        ║                                                                  ║
        ║ The difference in  length  is the  number of digits  translated. ║
        ╚══════════════════════════════════════════════════════════════════╝

output when using the input of: 0 9999999999

      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.

faster method

(Uses table lookup.) <lang rexx>/*REXX program determines if a number (in base 10) is a self-describing number.*/ parse arg x y . /*obtain optional arguments from the CL*/ if x== | x=="," then exit /*Not specified? Then get out of Dodge*/ if y== | y=="," then y=x /*Not specified? Then use the X value.*/ w=length(y) /*use Y's width for aligned output. */ numeric digits max(9, w) /*handle the possibility of larger #'s.*/ $= '1210 2020 21200 3211000 42101000 521001000 6210001000' /*the list of numbers.*/

                                                /*test for a  single  integer.         */

if x==y then do /*handle the case of a single number. */

             say word("isn't is",  wordpos(x, $) + 1)     'a self-describing number.'
             exit
             end
                                                /* [↓]  test for a  range  of integers.*/
        do n=x  to y;  parse var  n    -1  _  /*obtain the last decimal digit of  N. */
        if _\==0              then iterate
        if wordpos(n, $)==0   then iterate
        say  right(n,w)  'is a self-describing number.'
        end   /*n*/
                                                /*stick a fork in it,  we're all done. */</lang>

output is the same as the 1^st REXX example.

fastest method

(Uses a table look-up.)

(Results are instantaneous.) <lang rexx>/*REXX program determines if a number (in base 10) is a self-describing number.*/ parse arg x y . /*obtain optional arguments from the CL*/ if x== | x=="," then exit /*Not specified? Then get out of Dodge*/ if y== | y=="," then y=x /*Not specified? Then use the X value.*/ w=length(y) /*use Y's width for aligned output. */ numeric digits max(9, w) /*handle the possibility of larger #'s.*/ $= '1210 2020 21200 3211000 42101000 521001000 6210001000' /*the list of numbers.*/

                                                /*test for a  single  integer.         */

if x==y then do /*handle the case of a single number. */

             say word("isn't is",  wordpos(x, $) + 1)     'a self-describing number.'
             exit
             end
                                                /* [↓]  test for a  range  of integers.*/
        do n=1  for words($);     _=word($, n)  /*look for integers that are in range. */
        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. */</lang>

output is the same as the 1^st REXX example.

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

      sum = 0
      while substr(cString,dString) > 0
              sum = sum + 1
              cString = substr(cString,substr(cString,dString)+len(string(sum)))
      end
      return sum

</lang> Output:

Ruby

<lang ruby>def self_describing?(n)

 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)}</lang> outputs

Translation of: Wren

<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")</lang>

System: I5-2410m, 2.9 GHz, Linux Kernel 5.5.17, Ruby 2.7.1
Run as: $ ruby selfdescribing.rb

Output:

The self-describing numbers are:
1210 in 9.5517e-05 secs
2020 in 0.000175127 secs
21200 in 0.001102871 secs
3211000 in 0.129514701 secs
42101000 in 1.98685897 secs
521001000 in 29.109239987 secs
6210001000 in 409.844891982 secs
Took 489.148319843 secs overall

System: I5-2410m, 2.9 GHz, Linux Kernel 5.5.17, JRuby 9.2.11.1
Run as: $ ruby selfdescribing.rb

Output:

The self-describing numbers are:
1210 in 0.028907000000000002 secs
2020 in 0.044975999999999995 secs
21200 in 0.081773 secs
3211000 in 0.6109169999999999 secs
42101000 in 1.7770949999999999 secs
521001000 in 18.245994 secs
6210001000 in 250.319289 secs
Took 298.839834 secs overall

System: I5-2410m, 2.9 GHz, Linux Kernel 5.5.17, TruffleRuby 20.0.0
Run as: $ ruby selfdescribing.rb

Output:

The self-describing numbers are:
1210 in 0.01 secs
2020 in 0.012 secs
21200 in 0.029 secs
3211000 in 1.056 secs
42101000 in 1.793 secs
521001000 in 7.223 secs
6210001000 in 191.416 secs
Took 240.244 secs overall

Run BASIC

<lang Runbasic>for i = 0 to 50000000 step 10

  a$ = str$(i)
  for c = 1 TO len(a$)
     d      = val(mid$(a$, c, 1))
     j(d)   = j(d) + 1
     k(c-1) = d
  next c
  r = 0
  for n = 0 to 10
     r    = r + (j(n) = k(n)) 
     j(n) = 0 
     k(n) = 0
  next n
  if r = 11 then print i

next i print "== End ==" end</lang>

Rust

<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)
       }
   }

} </lang>

Scala

Functional Programming

<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.")

}</lang>

See it running in your browser by Scastie (JVM).

Seed7

<lang seed>$ include "seed7_05.s7i";

const func boolean: selfDescr (in string: stri) is func

 result
   var boolean: check is TRUE;
 local
   var integer: idx is 0;
   var array integer: count is [0 .. 9] times 0;
 begin
   for idx range 1 to length(stri) do
     incr(count[ord(stri[idx]) - ord('0')]);
   end for;
   idx := 1;
   while check and idx <= length(stri) do
     check := count[pred(idx)] = ord(stri[idx]) - ord('0');
     incr(idx);
   end while;
 end func;

const proc: gen (in integer: n) is func

 local
   var array integer : digits is 0 times 0;
   var string: stri is "";
   var integer: numberOfOneDigits is 0;
   var integer: idx is 0;
 begin
   while numberOfOneDigits <= 2 and numberOfOneDigits < n - 2 do
     digits := n times 0;
     digits[1] := n - 2 - numberOfOneDigits;
     if digits[1] <> 2 then
       digits[digits[1] + 1] := 1;
       digits[2] := 2;
       digits[3] := 1;
     else
       digits[2] := ord(numberOfOneDigits <> 0);
       digits[3] := 2;
     end if;
     stri := "";
     for idx range 1 to n do
       stri &:= chr(ord(digits[idx]) + ord('0'));
     end for;
     if selfDescr(stri) then
       writeln(stri);
     end if;
     incr(numberOfOneDigits);
   end while;
 end func;

const proc: main is func

 local
   const array integer: nums is [] (1210, 1337, 2020, 21200, 3211000, 42101000);
   var integer: number is 0;
 begin
   for number range nums do
     write(number <& " is ");
     if not selfDescr(str(number)) then
       write("not ");
     end if;
     writeln("self describing");
   end for;
   writeln;
   writeln("All autobiograph numbers:");
   for number range 1 to 10 do
     gen(number);
   end for;
 end func;</lang>

Output:

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

Sidef

Translation of: Raku

<lang ruby>func sdn(Number n) {

   var b = [0]*n.len
   var a = n.digits.flip
   a.each { |i| b[i] := 0 ++ }
   a == b

}

var values = [1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000, 27, 115508]

values.each { |test|

   say "#{test} is #{sdn(test) ?  : 'NOT ' }a self describing number."

}

say "\nSelf-descriptive numbers less than 1e5 (in base 10):" ^1e5 -> each { |i| say i if sdn(i) }</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.

Self-descriptive numbers less than 1e5 (in base 10):
1210
2020
21200

Extra credit: this will generate all the self-describing numbers in bases 7 to 36: <lang ruby>for b in (7 .. 36) {

   var n = ((b-4) * b**(b-1) + 2*(b**(b-2)) + b**(b-3) + b**3 -> base(b))
   say "base #{'%2d' % b}: #{n}"

}</lang>

Output:

base  7: 3211000
base  8: 42101000
base  9: 521001000
base 10: 6210001000
base 11: 72100001000
base 12: 821000001000
base 13: 9210000001000
base 14: a2100000001000
base 15: b21000000001000
base 16: c210000000001000
base 17: d2100000000001000
base 18: e21000000000001000
base 19: f210000000000001000
base 20: g2100000000000001000
base 21: h21000000000000001000
base 22: i210000000000000001000
base 23: j2100000000000000001000
base 24: k21000000000000000001000
base 25: l210000000000000000001000
base 26: m2100000000000000000001000
base 27: n21000000000000000000001000
base 28: o210000000000000000000001000
base 29: p2100000000000000000000001000
base 30: q21000000000000000000000001000
base 31: r210000000000000000000000001000
base 32: s2100000000000000000000000001000
base 33: t21000000000000000000000000001000
base 34: u210000000000000000000000000001000
base 35: v2100000000000000000000000000001000
base 36: w21000000000000000000000000000001000

Swift

<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()</lang>

Output:

Self-describing numbers less than 100,000,000:
1210
2020
21200
3211000
42101000

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>

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. <lang bash>selfdescribing() {

   local n=$1
   local count=()
   local i
   for ((i=0; i<${#n}; i++)); do
       ((count[${n:i:1}]++))
   done
   for ((i=0; i<${#n}; i++)); do
       (( ${n:i:1} == ${count[i]:-0} )) || return 1
   done
   return 0

}

for n in 0 1 10 11 1210 2020 21200 3211000 42101000; do

   if selfdescribing $n; then
       printf "%d\t%s\n" $n yes
   else
       printf "%d\t%s\n" $n no
   fi

done</lang>

Output:

0	no
1	no
10	no
11	no
1210	yes
2020	yes
21200	yes
3211000	yes
42101000	yes

VBScript

Takes a very, very long time to check 100M numbers that I have to terminate the script. But the function works. <lang vb> Function IsSelfDescribing(n) IsSelfDescribing = False Set digit = CreateObject("Scripting.Dictionary") For i = 1 To Len(n) k = Mid(n,i,1) If digit.Exists(k) Then digit.Item(k) = digit.Item(k) + 1 Else digit.Add k,1 End If Next c = 0 For j = 0 To Len(n)-1 l = Mid(n,j+1,1) If digit.Exists(CStr(j)) Then If digit.Item(CStr(j)) = CInt(l) Then c = c + 1 End If ElseIf l = 0 Then c = c + 1 Else Exit For End If Next If c = Len(n) Then IsSelfDescribing = True End If End Function

'testing start_time = Now s = "" For m = 1 To 100000000 If IsSelfDescribing(m) Then WScript.StdOut.WriteLine m End If Next end_time = Now WScript.StdOut.WriteLine "Elapse Time: " & DateDiff("s",start_time,end_time) & " seconds" </lang>

Wren

Heavily optimized to complete the search in a reasonable time for a scripting language. <lang ecmascript>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")</lang>

Output:

Timings are for an Intel Core i7-8565U machine running Wren 0.2.0 on Ubuntu 18.04.

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

XPL0

<lang XPL0>code ChOut=8, IntOut=11;

func SelfDesc(N); \Returns 'true' if N is self-describing int N; int Len, \length = number of digits in N

   I, D;

char Digit(10), Count(10);

       proc Num2Str(N);        \Convert integer N to string in Digit
       int N;
       int R;
       [N:= N/10;
       R:= rem(0);
       if N then Num2Str(N);
       Digit(Len):= R;
       Len:= Len+1;
       ];

[Len:= 0; Num2Str(N); for I:= 0 to Len-1 do Count(I):= 0; for I:= 0 to Len-1 do

       [D:= Digit(I);
       if D >= Len then return false;
       Count(D):= Count(D)+1;
       ];

for I:= 0 to Len-1 do

       if Count(I) # Digit(I) then return false;

return true; ]; \SelfDesc

int N; for N:= 0 to 100_000_000-1 do

       if SelfDesc(N) then [IntOut(0, N);  ChOut(0, ^ )]</lang>

Output:

1210 2020 21200 3211000 42101000

Yabasic

Translation of: BBC_BASIC

<lang Yabasic>FOR N = 1 TO 5E7

   IF FNselfdescribing(N) PRINT 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</lang>

zkl

<lang zkl>fcn isSelfDescribing(n){

  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"

}</lang> 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). <lang zkl>//[1..0x4_000_000].filter(isSelfDescribing).println(); 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();</lang>

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.

Output:

L(L(1210,2020,21200),L(3211000),L(42101000))