Summarize and say sequence: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: added output) |
m (→{{header|Phix}}: syntax coloured, made p2js compatible) |
||
| Line 3,271: | Line 3,271: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Optimisation idea taken from CoffeeScript, completes in under a second. |
Optimisation idea taken from CoffeeScript, completes in under a second. |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"000000"</span> |
|||
function incn() |
|||
for i=length(n) to 1 by -1 do |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">incn</span><span style="color: #0000FF;">()</span> |
|||
if n[i]='9' then |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
if i=1 then return false end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'9'</span> <span style="color: #008080;">then</span> |
|||
n[i]='0' |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
else |
|||
<span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'0'</span> |
|||
n[i] += 1 |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
end if |
|||
<span style="color: #008080;">exit</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
return true |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
sequence res = {}, bestseen |
|||
integer maxcycle = 0 |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">bestseen</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">maxcycle</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
procedure srs() |
|||
sequence seen, this = n |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">srs</span><span style="color: #0000FF;">()</span> |
|||
integer cycle = 1 |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">curr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> |
|||
while length(this)>1 and this[1]='0' do |
|||
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">curr</span><span style="color: #0000FF;">)></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">curr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">do</span> |
|||
this = this[2..$] |
|||
<span style="color: #000000;">curr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">curr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
integer ch = this[1] |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">curr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> |
|||
for i=2 to length(this) do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">curr</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
if this[i]>ch then return end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">curr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]></span><span style="color: #000000;">ch</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
ch = this[i] |
|||
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">curr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
seen = {this} |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">seen</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">curr</span><span style="color: #0000FF;">}</span> |
|||
while 1 do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">cycle</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
sequence digits = repeat(0,10) |
|||
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> |
|||
for i=1 to length(this) do |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
|||
digits[this[i]-'0'+1] += 1 |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">curr</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
end for |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">idx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">curr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> |
|||
string next = "" |
|||
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
for i=length(digits) to 1 by -1 do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
if digits[i]!=0 then |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span> |
|||
next &= sprint(digits[i]) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
next &= i+'0'-1 |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">next</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
|||
end for |
|||
<span style="color: #000000;">next</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> |
|||
if find(next,seen) then exit end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
seen = append(seen,next) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
this = next |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next</span><span style="color: #0000FF;">,</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
cycle += 1 |
|||
<span style="color: #000000;">seen</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next</span><span style="color: #0000FF;">)</span> |
|||
end while |
|||
<span style="color: #000000;">curr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span> |
|||
if cycle>maxcycle then |
|||
<span style="color: #000000;">cycle</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
res = {seen[1]} |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
maxcycle = cycle |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">cycle</span><span style="color: #0000FF;">></span><span style="color: #000000;">maxcycle</span> <span style="color: #008080;">then</span> |
|||
bestseen = seen |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]}</span> |
|||
elsif cycle=maxcycle then |
|||
<span style="color: #000000;">maxcycle</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle</span> |
|||
res = append(res,seen[1]) |
|||
<span style="color: #000000;">bestseen</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">seen</span> |
|||
end if |
|||
<span style="color: #008080;">elsif</span> <span style="color: #000000;">cycle</span><span style="color: #0000FF;">=</span><span style="color: #000000;">maxcycle</span> <span style="color: #008080;">then</span> |
|||
end procedure |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
while 1 do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
srs() |
|||
if not incn() then exit end if |
|||
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> |
|||
end while |
|||
<span style="color: #000000;">srs</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">incn</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
-- add non-leading-0 perms: |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
for i=length(res) to 1 by -1 do |
|||
string ri = res[i] |
|||
<span style="color: #000080;font-style:italic;">-- add non-leading-0 perms:</span> |
|||
for p=1 to factorial(length(ri)) do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
string pri = permute(p,ri) |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">ri</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
if pri[1]!='0' and not find(pri,res) then |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">do</span> |
|||
res = append(res,pri) |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">pri</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">)</span> |
|||
end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">pri</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]!=</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">and</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pri</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
end for |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pri</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
?res |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
puts(1,"cycle length is ") ?maxcycle |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
pp(bestseen,{pp_Nest,1})</lang> |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">res</span> |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"cycle length is "</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">maxcycle</span> |
|||
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bestseen</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span> |
|||
<!--</lang>--> |
|||
<pre> |
<pre> |
||
{"9900","9009","9090"} |
{"9900","9009","9090"} |
||