Pancake numbers: Difference between revisions
Content added Content deleted
(added 12 incomplete tags) |
m (→Phix: added rhs flips and number found) |
||
Line 573: | Line 573: | ||
<lang Phix>function visitor(sequence stack, integer /*unused*/, sequence stacks) |
<lang Phix>function visitor(sequence stack, integer /*unused*/, sequence stacks) |
||
for pos=2 to length(stack) do |
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 = reverse(stack[1..pos])&stack[pos+1..$] |
||
-- sequence newstack = stack[1..pos]&reverse(stack[pos+1..$]) |
|||
if getd_index(newstack,stacks[1])=NULL then |
if getd_index(newstack,stacks[1])=NULL then |
||
setd(newstack,0,stacks[$]) -- (next round) |
setd(newstack,0,stacks[$]) -- (next round) |
||
Line 594: | Line 596: | ||
end while |
end while |
||
sequence eg = getd_partial_key(0,stacks[$-1],true) |
sequence eg = getd_partial_key(0,stacks[$-1],true) |
||
integer sz = dict_size(stacks[$-1]) |
|||
papply(stacks,destroy_dict) |
papply(stacks,destroy_dict) |
||
return {length(stacks)-2,eg} |
return {length(stacks)-2,eg,sz} |
||
end function |
end function |
||
atom t0 = time() |
atom t0 = time() |
||
for n=1 to 8 do -- (for <2s) |
for n=1 to 8 do -- (for <2s) |
||
{integer pn, sequence eg} = pancake(n) |
{integer pn, sequence eg, integer sz} = pancake(n) |
||
printf(1,"p(%d) = %d, example: %v (%s)\n",{n,pn,eg,elapsed(time()-t0)}) |
printf(1,"p(%d) = %d, example: %v (of %,d, %s)\n",{n,pn,eg,sz,elapsed(time()-t0)}) |
||
end for</lang> |
end for</lang> |
||
{{out}} |
{{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. |
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> |
<pre> |
||
p(1) = 0, example: {1} (0s) |
p(1) = 0, example: {1} (of 1, 0s) |
||
p(2) = 1, example: {2,1} (0.1s) |
p(2) = 1, example: {2,1} (of 1, 0.1s) |
||
p(3) = 3, example: {1,3,2} (0.1s) |
p(3) = 3, example: {1,3,2} (of 1, 0.1s) |
||
p(4) = 4, example: {4,2,3,1} (0.1s) |
p(4) = 4, example: {4,2,3,1} (of 3, 0.1s) |
||
p(5) = 5, example: {5,3,1,4,2} (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} (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} (0.2s) |
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} (1.8s) |
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} (19. |
p(9) = 10, example: {9,7,5,2,8,1,4,6,3} (of 5,804, 19.6s) |
||
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (4 minutes and |
p(10) = 11, example: {10,8,9,7,3,1,5,2,6,4} (of 73,232, 4 minutes and 7s) |
||
</pre> |
|||
⚫ | |||
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> |
</pre> |
||
⚫ | |||
=={{header|Raku}}== |
=={{header|Raku}}== |