Self-describing numbers: Difference between revisions

*   [[Spelling of ordinal numbers]]

<br><br>

 

=={{header|Ada}}==

procedure SelfDesc is

subtype Desc_Int is Long_Integer range 0 .. 10**10-1;

end if;

end loop;

{{out}}

<pre>1210

{{works with|ALGOL 68|Revision 1 - no extensions to language used}}

{{works with|ALGOL 68G|Any - tested with release 2.6.win32}}

 

# return TRUE if number is self describing, FALSE otherwise #

)

 

{{out}}

<pre>

+42101000 is self describing

</pre>

 

=={{header|AutoHotkey}}==

Uses CountSubString: [[Count occurrences of a substring#AutoHotkey]]

#NoEnv

SetBatchlines -1

return false

return true

Output:

<pre>---------------------------

 

=={{header|AWK}}==

BEGIN {

for (n=1; n<=100000000; n++) {

}

return(1)

<p>output:</p>

<pre>

 

=={{header|BASIC}}==

Dim a, d As String

Dim v(10), w(10) As Integer

Print "End"

sleep

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

IF FNselfdescribing(N) PRINT N

NEXT

N% DIV=10

ENDWHILE

Output:

<pre>

Be aware, though, that even with a fast interpreter, it's going to be a very long time before you see the full set of results.

 

?v6:%+55:\+1\<<<\0:::<

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

^_@#!`<<v\+g6g10*+55\<

>:*:*:*^>>:01g1+:01p`|

 

{{out}}

=={{header|C}}==

Using integers instead of strings.

 

inline int self_desc(unsigned long long xx)

return 0;

2020

21200

3211000

 

===Backtracking version===

Backtracks on each digit from right to left, takes advantage of constraints "sum of digit values = number of digits" and "sum of (digit index * digit value) = number of digits". It is using as argument the list of allowed digits (example 012345789 to run the program in standard base 10).

#include <stdlib.h>

#include <string.h>

puts("");

}

 

Output for base 36

1210

2020

real 0m0.094s

user 0m0.046s

 

=={{header|C++}}==

#include <iostream>

return 0;

}

{{out}}

<pre>

Uses C++11. Build with

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

#include <array>

#include <iostream>

}

}

Output:

<pre>

6210001000

</pre>

 

=={{header|Common Lisp}}==

probably much faster because it wouldn't have to allocate an array and then

turn around and "interpret" it back out but I didn't really pursue it.

 

(defun to-digits (n)

(digits (to-digits n) (cdr digits)))

((null digits) t)

 

Output:

 

1210

21200

3211000

 

=={{header|Crystal}}==

{{trans|Ruby}}

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 }

 

t = Time.monotonic

{{out}}

</pre>

 

=={{header|D}}==

===Functional Version===

 

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

void main() {

4_000_000.iota.filter!isSelfDescribing.writeln;

{{out}}

<pre>[1210, 2020, 21200, 3211000]</pre>

 

===A Faster Version===

if (n <= 0)

return false;

if (i.isSelfDescribing2)

i.writeln;

{{out}}

<pre>1210

42101000

521001000</pre>

 

=={{header|Elixir}}==

def number(n) do

digits = Integer.digits(n)

 

m = 3300000

 

{{out}}

=={{header|Erlang}}==

 

 

sdn(N) -> lists:map(fun(S)->length(lists:filter(fun(C)->C-$0==S end,N))+$0 end,lists:seq(0,length(N)-1))==N.

gen(M) -> lists:filter(fun(N)->sdn(integer_to_list(N)) end,lists:seq(0,M)).

 

 

=={{header|Factor}}==

IN: rosetta-code.self-describing-numbers

 

digits dup [ digit-count = ] with map-index [ t = ] all? ;

 

{{out}}

<pre>

=={{header|Forth}}==

 

: third ( A b c -- A b c A ) >r over r> swap ;

: (.) ( u -- c-addr u ) 0 <# #s #> ;

(.) [char] 0 third third bounds ?do

count i c@ [char] 0 - <> if drop 2drop false unloop exit then

 

=={{header|FreeBASIC}}==

 

Function selfDescribing (n As UInteger) As Boolean

Print

Print "Press any key to quit"

 

{{out}}

=={{header|Go}}==

===Original===

 

import (

}

}

Output produced by above program:

<pre>

===Optimized===

Uses the optimized loop from the Wren entry - 12 times faster than before.

 

import (

osecs := time.Since(start).Seconds()

fmt.Printf("\nTook %.1f secs overall\n", osecs)

 

{{out}}

 

=={{header|Haskell}}==

 

count :: Int -> [Int] -> Int

isSelfDescribing <$>

[1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000]

Output:

<pre>[True,True,True,True,True,True,True]

 

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

 

count :: Int -> [Int] -> Int

count x = length . filter (x ==)

 

allBaseNNumsOfLength :: Int -> [[Int]]

 

isSelfDescribing :: [Int] -> Bool

 

decimalize :: [Int] -> Int

decimalize = read . map intToDigit

main =

(print . concat) $

{{Out}}

<pre>[1210,2020,21200,3211000,42101000]</pre>

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

 

procedure count (test_item, str)

result := 0

every write (self_describing_numbers ()\4)

end

A slightly more concise solution can be derived from the above by taking

more advantage of Icon's (and Unicon's) automatic goal-directed

evaluation:

procedure is_self_describing (n)

ns := string (n) # convert to a string

procedure self_describing_numbers ()

suspend is_self_describing(seq())

 

=={{header|J}}==

 

counts =: _1 + [: #/.~ i.@:# , ]

'''Discussion''': The use of <tt>&.</tt> here is a great example of its surprisingly broad applicability, and the elegance it can produce.

 

 

=={{header|Java}}==

public static boolean isSelfDescribing(int a){

String s = Integer.toString(a);

}

}

 

=={{header|JavaScript}}==

{{works with|SpiderMonkey}}

 

var digits = Number(n).toString().split("").map(function(elem) {return Number(elem)});

var len = digits.length;

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

if (is_self_describing(i))

 

outputs

=={{header|jq}}==

{{works with|jq|1.4}}

# which is slightly less efficient:

def all(generator; condition):

def count(value): reduce .[] as $i (0; if $i == value then . + 1 else . end);

def digits: tostring | explode | map(. - 48);

else . as $digits

| all ( range(0; length); . as $i | $digits | (.[$i] == count($i)) )

'''The task:'''

{{out}}

1210

2020

21200

3211000

 

=={{header|Julia}}==

{{works with|Julia|0.6}}

 

ds = reverse(digits(x))

if sum(ds) != length(ds) return false end

 

selfies(x) = for i in 1:x selfie(i) && println(i) end

 

{{out}}

 

=={{header|K}}==

sdn 1210 2020 2121 21200 3211000 42101000

1 1 0 1 1 1

 

&sdn@!:1e6

 

=={{header|Kotlin}}==

 

fun selfDescribing(n: Int): Boolean {

for (i in 0..99999999) if (selfDescribing(i)) print("$i ")

println()

 

{{out}}

 

=={{header|Liberty BASIC}}==

FOR x = 1 TO 5000000

a$ = TRIM$(STR$(x))

NEXT x

PRINT

 

=={{header|LiveCode}}==

local tSelfD, tLen

put len(n) into tLen

end repeat

return tSelfD

repeat with n = 0 to 10000000

if selfDescNumber(n) then

combine selfNum using comma

put selfNum

 

=={{header|Logo}}==

BT

MAKE "AA (ARRAY 10 0)

FOR [Z 0 9][SETITEM :Z :AA "0 SETITEM :Z :BB "0 ]]

PR [END]

 

=={{header|Lua}}==

local s = tostring( n )

 

for i = 1, 999999999 do

print( Is_self_describing( i ) )

 

<pre>Select[Range[10^10 - 1], isSelfDescribing]

-> {1210,2020,21200,3211000,42101000,521001000,6210001000}</pre>

 

=={{header|MATLAB}} / {{header|Octave}}==

s = int2str(n)-'0'; % convert to vector of digits

y = hist(s,0:9);

z = all(y(1:length(s))==s);

 

Test function:

 

if isSelfDescribing(k),

printf('%i\n',k);

end

 

Output:

 

=={{header|MiniScript}}==

occurrences = function(test, values)

end if

end for

{{out}}

<pre>

{{trans|Pascal}}

{{works with|ADW Modula-2|any (Compile with the linker option ''Console Application'').}}

MODULE SelfDescribingNumber;

 

WriteLn;

END SelfDescribingNumber.

{{out}}

<pre>

 

=={{header|Nim}}==

 

 

return false

 

 

=={{header|ooRexx}}==

-- REXX program to check if a number (base 10) is self-describing.

parse arg x y .

say number "is a self describing number"

end

'''output''' when using the input of: <tt> 0 999999999 </tt>

<pre style="overflow:scroll">

=={{header|PARI/GP}}==

This is a finite set...

 

=={{header|Pascal}}==

 

uses

writeln (' ', x);

writeln('Job done.');

Output:

<pre>

 

The number is self-descriptive If the arrays are equal.

{

local $_ = shift;

for (0 .. 100000, 3211000, 42101000) {

print "$_\n" if is_selfdesc($_);

Output:

<pre>1210

=={{header|Phix}}==

{{Trans|Ada}}

{{out}}

<pre>

42101000

done (21.78s)

</pre>

 

Works with: PHP 5.

 

 

function is_describing($number) {

}

 

 

Output:

3211000

42101000</pre>

 

=={{header|PicoLisp}}==

(fully '((D I) (= D (cnt = N (circ I))))

(setq N (mapcar format (chop N)))

Output:

<pre>: (filter selfDescribing (range 1 4000000))

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:

function Test-SelfDescribing ([int]$Number)

{

$sum -eq $digits.Count

}

Test-SelfDescribing -Number 2020

{{Out}}

<pre>

</pre>

It takes a very long while to test 100,000,000 numbers, and since they are already known just test a few:

11,2020,21200,321100 | ForEach-Object {

[PSCustomObject]@{

}

} | Format-Table -AutoSize

{{Out}}

<pre>

=={{header|Prolog}}==

Works with SWI-Prolog and library clpfd written by <b>Markus Triska</b>.

 

self_describling :-

 

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

 

Output

 

=={{header|PureBasic}}==

;returns 1 if number is self-describing, otherwise it returns 0

Protected digitCount, digit, i, digitSum

Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()

CloseConsole()

Sample output:

<pre>1210 is selfdescribing.

 

=={{header|Python}}==

s = str(n)

return all(s.count(str(i)) == int(ch) for i, ch in enumerate(s))

[1210, 2020, 21200, 3211000]

>>> [(x, isSelfDescribing(x)) for x in (1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000)]

===Generator===

From [http://leetm.mingpao.com/cfm/Forum3.cfm?CategoryID=1&TopicID=1545&TopicOrder=Desc&TopicPage=1 here].

if m < 0: return

if d == c[:len(d)]: print d

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

Output:

<pre>[]

[5, 2, 1, 0, 0, 1, 0, 0, 0]

[6, 2, 1, 0, 0, 0, 1, 0, 0, 0] </pre>

 

=={{header|Racket}}==

(define (get-digits number (lst null))

(if (zero? number)

(and bool

(= (count (lambda (x) (= x i)) digits)

 

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

=={{header|Raku}}==

(formerly Perl 6)

42101000 521001000 6210001000 27 115508>;

 

}

 

Output:

<pre>

 

=={{header|Red}}==

 

;;-------------------------------------

 

repeat i 4000000 [ if isSDN? to-string i [print i] ]

'''output'''

<pre>1210

&nbsp; and &nbsp; [http://oeis.org/A138480 OEIS A138480].

===digit by digit test===

/*────────────────────────────────────────────────────── self─descriptive, */

/*────────────────────────────────────────────────────── autobiographical, or a */

if substr(?,j,1)\==L-length(space(translate(?,,j-1),0)) then return 1

end /*j*/

<pre>

╔══════════════════════════════════════════════════════════════════╗

===faster method===

(Uses table lookup.)

parse arg x y . /*obtain optional arguments from the CL*/

if x=='' | x=="," then exit /*Not specified? Then get out of Dodge*/

say right(n,w) 'is a self-describing number.'

end /*n*/

'''output''' &nbsp; is the same as the 1^st REXX example.

 

 

(Results are instantaneous.)

parse arg x y . /*obtain optional arguments from the CL*/

if x=='' | x=="," then exit /*Not specified? Then get out of Dodge*/

if _<x | _>y then iterate /*if not self-describing, try again. */

say right(_, w) 'is a self-describing number.'

'''output''' &nbsp; is the same as the 1^st REXX example.

<br><br>

 

=={{header|Ring}}==

# Project : Self-describing numbers

 

end

return sum

Output:

<pre>

42101000

</pre>

 

=={{header|Ruby}}==

digits = n.digits.reverse

digits.each_with_index.all?{|digit, idx| digits.count(idx) == digit}

end

 

outputs

<pre>1210

21200

3211000</pre>

 

=={{header|Run BASIC}}==

a$ = str$(i)

for c = 1 TO len(a$)

next i

print "== End =="

 

=={{header|Rust}}==

fn is_self_desc(xx: u64) -> bool

{

}

}

 

=={{header|Scala}}==

===Functional Programming===

def isSelfDescribing(a: Int): Boolean = {

val s = Integer.toString(a)

 

println("Successfully completed without errors.")

 

See it running in your browser by [https://scastie.scala-lang.org/vQv61PpoSLeWwyVipLUevQ Scastie (JVM)].

 

=={{header|Seed7}}==

 

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

gen(number);

end for;

 

Output:

=={{header|Sidef}}==

{{trans|Raku}}

var b = [0]*n.len

var a = n.digits.flip

 

say "\nSelf-descriptive numbers less than 1e5 (in base 10):"

{{out}}

<pre>

 

'''Extra credit:''' this will generate all the self-describing numbers in bases 7 to 36:

var n = ((b-4) * b**(b-1) + 2*(b**(b-2)) + b**(b-3) + b**3 -> base(b))

say "base #{'%2d' % b}: #{n}"

{{out}}

<pre>

=={{header|Swift}}==

 

 

extension BinaryInteger {

}

 

 

{{out}}

 

=={{header|Tcl}}==

proc isSelfDescribing num {

set digits [split $num ""]

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

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

 

=={{header|UNIX Shell}}==

{{works with|bash}}

Seeking self-describing numbers up to 100,000,000 is very time consuming, so we'll just verify a few numbers.

local n=$1

local count=()

printf "%d\t%s\n" $n no

fi

{{output}}

<pre>0 no

Takes a very, very long time to check 100M numbers that I have to terminate the script. But the function

works.

Function IsSelfDescribing(n)

IsSelfDescribing = False

end_time = Now

WScript.StdOut.WriteLine "Elapse Time: " & DateDiff("s",start_time,end_time) & " seconds"

 

=={{header|Wren}}==

Heavily optimized to complete the search in a reasonable time for a scripting language.

var ns = "%(n)"

var nc = ns.count

}

var osecs = ((System.clock - start) * 10).round / 10

 

{{out}}

 

=={{header|XPL0}}==

 

func SelfDesc(N); \Returns 'true' if N is self-describing

int N;

for N:= 0 to 100_000_000-1 do

 

Output:

=={{header|Yabasic}}==

{{trans|BBC_BASIC}}

IF FNselfdescribing(N) PRINT N

NEXT

FOR I = 0 TO 8 : L = L + D(I) : NEXT

RETURN O = L

 

=={{header|zkl}}==

if (n.bitAnd(1)) return(False); // Wikipedia: last digit must be zero

nu:= n.toString();

ns:=["0".."9"].pump(String,nu.inCommon,"len"); //"12233".inCommon("2")-->"22"

(nu+"0000000000")[0,10] == ns; //"2020","2020000000"

Since testing a humongous number of numbers is slow, chunk the task into a bunch of threads. Even so, it pegged my 8 way Ivy Bridge Linux box for quite some time (eg the Python & AWK solutions crush this one).

const N=0d500_000;

[1..0d100_000_000, N] // chunk and thread, 200 in this case

.apply(fcn(n){ n.filter(N,isSelfDescribing) }.future)

A future is a thread returning a [delayed] result, future.filter/future.noop will block until the future coughs up the result. Since the results are really sparse for the bigger numbers, filter out the empty results.

{{out}}