Anonymous user
Summarize and say sequence: Difference between revisions
→{{header|Nim}}
No edit summary |
|||
Line 2,900:
19182716152413228110
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}}==
| |||