Summarize and say sequence: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 2,900: | Line 2,900: | ||
19182716152413228110 |
19182716152413228110 |
||
19281716151413427110</pre> |
19281716151413427110</pre> |
||
=={{header|Nim}}== |
|||
A version which uses a cache to store the number of iterations and thus avoids to compute the sequence for each permutation. The version without cache ran in 19s. This version runs in less than 500ms. |
|||
<lang Nim>import algorithm, sequtils, sets, strutils, tables |
|||
var cache: Table[string, int] # Cache seed -> number of iterations. |
|||
iterator sequence(seed: string): string = |
|||
## Yield the successive strings of a sequence. |
|||
var history: HashSet[string] |
|||
history.incl seed |
|||
var current = seed |
|||
yield current |
|||
while true: |
|||
var counts = current.toCountTable() |
|||
var next: string |
|||
for ch in sorted(toSeq(counts.keys), Descending): |
|||
next.add $counts[ch] & ch |
|||
if next in history: break |
|||
current = move(next) |
|||
history.incl current |
|||
yield current |
|||
proc seqLength(seed: string): int = |
|||
## Return the number of iterations for the given seed. |
|||
let seed = sorted(seed, Descending).join() |
|||
if seed in cache: return cache[seed] |
|||
result = toSeq(sequence($seed)).len |
|||
cache[seed] = result |
|||
var seeds: seq[int] |
|||
var itermax = 0 |
|||
for seed in 0..<1_000_000: |
|||
let itercount = seqLength($seed) |
|||
if itercount > itermax: |
|||
itermax = itercount |
|||
seeds = @[seed] |
|||
elif itercount == itermax: |
|||
seeds.add seed |
|||
echo "Maximum iterations: ", itermax |
|||
echo "Seed values: ", seeds.join(", ") |
|||
echo "Sequence for $#:".format(seeds[0]) |
|||
for s in sequence($seeds[0]): echo s</lang> |
|||
{{out}} |
|||
<pre>Maximum iterations: 21 |
|||
Seed values: 9009, 9090, 9900 |
|||
Sequence for 9009: |
|||
9009 |
|||
2920 |
|||
192210 |
|||
19222110 |
|||
19323110 |
|||
1923123110 |
|||
1923224110 |
|||
191413323110 |
|||
191433125110 |
|||
19151423125110 |
|||
19251413226110 |
|||
1916151413325110 |
|||
1916251423127110 |
|||
191716151413326110 |
|||
191726151423128110 |
|||
19181716151413327110 |
|||
19182716151423129110 |
|||
29181716151413328110 |
|||
19281716151423228110 |
|||
19281716151413427110 |
|||
19182716152413228110</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |