Self-describing numbers: Difference between revisions

This is a brute-force algorithm. To speed-up, it uses integers instead of strings and the variable “digits” is allocated once, placed in global scope and accessed directly by the two functions (something I generally avoid). We have been able to check until 1_000_000_000.

<lang nim>import algorithm, sequtils, std/monotimes, times

type Digit = 0..9

var digits = newSeqOfCap[Digit](10)

proc getDigits(n: Positive) =

digits.setLen(0)

var n = n.int

while n != 0:

digits.add n mod 10

n = n div 10

digits.reverse()

proc isSelfDescribing(n: Natural): bool =

n.getDigits()

for i, d in digits:

if digits.count(i) != d:

result = true

let t0 = getMonoTime()

for n in 1 .. 1_000_000_000:

if n.isSelfDescribing:

echo n, " in ", getMonoTime() - t0

echo "\nTotal time: ", getMonoTime() - t0</lang>

{{out}}

<pre>1210 in 154 microseconds and 723 nanoseconds

2020 in 376 microseconds and 687 nanoseconds

21200 in 2 milliseconds, 804 microseconds, and 259 nanoseconds

3211000 in 165 milliseconds, 490 microseconds, and 749 nanoseconds

42101000 in 2 seconds, 89 milliseconds, 515 microseconds, and 202 nanoseconds

521001000 in 27 seconds, 712 milliseconds, 35 microseconds, and 660 nanoseconds

Total time: 52 seconds, 969 milliseconds, 578 microseconds, and 698 nanoseconds</pre>