Pancake numbers: Difference between revisions
m
→Phix: added rhs flips and number found
(added 12 incomplete tags) |
m (→Phix: added rhs flips and number found) |
||
Line 573:
<lang Phix>function visitor(sequence stack, integer /*unused*/, sequence stacks)
for pos=2 to length(stack) do
-- for pos=0 to length(stack)-2 do
sequence newstack = reverse(stack[1..pos])&stack[pos+1..$]
-- sequence newstack = stack[1..pos]&reverse(stack[pos+1..$])
if getd_index(newstack,stacks[1])=NULL then
setd(newstack,0,stacks[$]) -- (next round)
Line 594 ⟶ 596:
end while
sequence eg = getd_partial_key(0,stacks[$-1],true)
integer sz = dict_size(stacks[$-1])
papply(stacks,destroy_dict)
return {length(stacks)-2,eg,sz}
end function
atom t0 = time()
for n=1 to 8 do -- (for <2s)
{integer pn, sequence eg, integer sz} = pancake(n)
printf(1,"p(%d) = %d, example: %v (of %,d, %s)\n",{n,pn,eg,sz,elapsed(time()-t0)})
end for</lang>
{{out}}
Note that we are only allowed to flip the left hand side, so [eg] we cannot solve p(3) by flipping the right hand pair.<br>
lhs flips, the "of nn" shows how many unique stacks we found that required p(n) flips.
<pre>
p(1) = 0, example: {1} (of 1, 0s)
p(2) = 1, example: {2,1} (of 1, 0.1s)
p(3) = 3, example: {1,3,2} (of 1, 0.1s)
p(4) = 4, example: {4,2,3,1} (of 3, 0.1s)
p(5) = 5, example: {5,3,1,4,2} (of 20, 0.1s)
p(6) = 7, example: {5,3,6,1,4,2} (of 2, 0.1s)
p(7) = 8, example: {7,3,1,5,2,6,4} (of 35, 0.2s)
p(8) = 9, example: {8,6,2,4,7,3,5,1} (of 455, 1.8s)
p(9) = 10, example: {9,7,5,2,8,1,4,6,3} (of 5,804, 19.
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (of 73,232, 4 minutes and
</pre>
After p(7), each subsequent p(n) takes about n times as long to complete.<br>▼
rhs flips, using the two commented-out alternative lines in visitor(), and again showing the last one found, is more similar than I expected.
<pre>
p(1) = 0, example: {1} (of 1, 0s)
p(2) = 1, example: {2,1} (of 1, 0.1s)
p(3) = 3, example: {2,1,3} (of 1, 0.1s)
p(4) = 4, example: {4,2,3,1} (of 3, 0.1s)
p(5) = 5, example: {5,3,1,4,2} (of 20, 0.1s)
p(6) = 7, example: {5,3,6,1,4,2} (of 2, 0.1s)
p(7) = 8, example: {7,2,4,1,6,3,5} (of 35, 0.3s)
p(8) = 9, example: {8,6,2,4,7,3,5,1} (of 455, 1.8s)
p(9) = 10, example: {9,7,5,2,8,1,4,6,3} (of 5,804, 19.2s)
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (of 73,232, 4 minutes and 1s)
</pre>
▲After p(7), each subsequent p(n) takes about n times as long to complete.
=={{header|Raku}}==
| |||