/* Eight coins problem in Picat. From Dave Richeson (@divbyzero) https://twitter.com/divbyzero/status/1732439422132502960 """ In 1884 P.G. Tait wrote about the following puzzle, which he encountered while riding on a train: Start with eight adjacent coins alternating heads and tails. By moving four pairs of neighboring coins (and without changing their order), rearrange the coins to obtain four tails followed by four heads with no gaps between any of the coins. ... Source: P.G. Tait, "Listing's Topologie," Philosophical Magazine, January 1884 """ For the eight coin problem (N=4) there are 5424 different solutions with the optimal number of 4 moves. Here are some of them. (The numbered list are the moves for 1..2*N.) Init = hthththt move [ 1, 2] to [ 2, 3]: hhtththt ([3,1,2,4,5,6,7,8]) move [ 1, 2] to [ 7, 8]: tthththh ([2,4,5,6,7,8,3,1]) move [ 2, 3] to [ 3, 4]: ttthhthh ([2,6,4,5,7,8,3,1]) move [ 4, 5] to [ 5, 6]: tttthhhh ([2,6,4,8,5,7,3,1]) cost = 4 move [ 1, 2] to [ 2, 3]: hhtththt ([3,1,2,4,5,6,7,8]) move [ 1, 2] to [ 3, 4]: tthhhtht ([2,4,3,1,5,6,7,8]) move [ 5, 6] to [ 6, 7]: tthhhhtt ([2,4,3,1,7,5,6,8]) move [ 7, 8] to [ 1, 2]: tttthhhh ([6,8,2,4,3,1,7,5]) cost = 4 move [ 1, 2] to [ 2, 3]: hhtththt ([3,1,2,4,5,6,7,8]) move [ 1, 2] to [ 3, 4]: tthhhtht ([2,4,3,1,5,6,7,8]) move [ 5, 6] to [ 6, 7]: tthhhhtt ([2,4,3,1,7,5,6,8]) move [ 7, 8] to [ 2, 3]: tttthhhh ([2,6,8,4,3,1,7,5]) cost = 4 ... Conjecture 1 ------------ * For N*2 coins there are minimum N moves needed. For example, here's a 10 move plan for 20 coins (N=10): move [ 1, 2] to [ 2, 3]: hhtththththththththt ([3,1,2,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]) move [ 1, 2] to [ 3, 4]: tthhhthththththththt ([2,4,3,1,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]) move [ 5, 6] to [ 6, 7]: tthhhhtththththththt ([2,4,3,1,7,5,6,8,9,10,11,12,13,14,15,16,17,18,19,20]) move [ 7, 8] to [ 1, 2]: tttthhhhhthththththt ([6,8,2,4,3,1,7,5,9,10,11,12,13,14,15,16,17,18,19,20]) move [ 9,10] to [18,19]: tttthhhhhththththhtt ([6,8,2,4,3,1,7,5,11,12,13,14,15,16,17,18,19,9,10,20]) move [19,20] to [ 1, 2]: tttttthhhhhththththh ([10,20,6,8,2,4,3,1,7,5,11,12,13,14,15,16,17,18,19,9]) move [12,13] to [ 7, 8]: ttttttthhhhhhthththh ([10,20,6,8,2,4,12,13,3,1,7,5,11,14,15,16,17,18,19,9]) move [14,15] to [ 8, 9]: tttttttthhhhhhhththh ([10,20,6,8,2,4,12,14,15,13,3,1,7,5,11,16,17,18,19,9]) move [16,17] to [ 9,10]: ttttttttthhhhhhhhthh ([10,20,6,8,2,4,12,14,16,17,15,13,3,1,7,5,11,18,19,9]) move [18,19] to [10,11]: tttttttttthhhhhhhhhh ([10,20,6,8,2,4,12,14,16,18,19,17,15,13,3,1,7,5,11,9]) cost = 10 Here is a 12 move plan for 24 coins (N=12): move [ 1, 2] to [ 2, 3]: hhtththththththththththt ([3,1,2,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24]) move [ 1, 2] to [ 3, 4]: tthhhthththththththththt ([2,4,3,1,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24]) move [ 5, 6] to [ 6, 7]: tthhhhtththththththththt ([2,4,3,1,7,5,6,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24]) move [ 7, 8] to [ 1, 2]: tttthhhhhthththththththt ([6,8,2,4,3,1,7,5,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24]) move [ 9,10] to [12,13]: tttthhhhhthhtthththththt ([6,8,2,4,3,1,7,5,11,12,13,9,10,14,15,16,17,18,19,20,21,22,23,24]) move [13,14] to [ 1, 2]: tttttthhhhhthhhththththt ([10,14,6,8,2,4,3,1,7,5,11,12,13,9,15,16,17,18,19,20,21,22,23,24]) move [15,16] to [22,23]: tttttthhhhhthhhthththhtt ([10,14,6,8,2,4,3,1,7,5,11,12,13,9,17,18,19,20,21,22,23,15,16,24]) move [23,24] to [ 1, 2]: tttttttthhhhhthhhthththh ([16,24,10,14,6,8,2,4,3,1,7,5,11,12,13,9,17,18,19,20,21,22,23,15]) move [14,15] to [ 9,10]: ttttttttthhhhhhhhthththh ([16,24,10,14,6,8,2,4,12,13,3,1,7,5,11,9,17,18,19,20,21,22,23,15]) move [18,19] to [10,11]: tttttttttthhhhhhhhhththh ([16,24,10,14,6,8,2,4,12,18,19,13,3,1,7,5,11,9,17,20,21,22,23,15]) move [20,21] to [11,12]: ttttttttttthhhhhhhhhhthh ([16,24,10,14,6,8,2,4,12,18,20,21,19,13,3,1,7,5,11,9,17,22,23,15]) move [22,23] to [12,13]: tttttttttttthhhhhhhhhhhh ([16,24,10,14,6,8,2,4,12,18,20,22,23,21,19,13,3,1,7,5,11,9,17,15]) cost = 12 Other values of K ================= It seems that for other K than 2, there are still the same optimal plan length as for K=2. Conjecture 2 ------------ * The optimal plan length is the same for any K (K >= N). Here's a solution for 8 coins (N=4) and K=3: move 1..3 to 2..4 : ththhtht ([4,1,2,3,5,6,7,8]) move 3..5 to 2..4 : tthhhtht ([4,2,3,5,1,6,7,8]) move 3..5 to 6..8 : ttththhh ([4,2,6,7,8,3,5,1]) move 2..4 to 3..5 : tttthhhh ([4,8,2,6,7,3,5,1]) cost = 4 14 coins (N=7) with K=3: move 1..3 to 2..4 : ththhththththt ([4,1,2,3,5,6,7,8,9,10,11,12,13,14]) move 3..5 to 2..4 : tthhhththththt ([4,2,3,5,1,6,7,8,9,10,11,12,13,14]) move 3..5 to 4..6 : ttthhhhthththt ([4,2,6,3,5,1,7,8,9,10,11,12,13,14]) move 6..8 to 11..13: ttthhhththhhtt ([4,2,6,3,5,9,10,11,12,13,1,7,8,14]) move 4..6 to 12..14: tttththhhtthhh ([4,2,6,10,11,12,13,1,7,8,14,3,5,9]) move 7..9 to 9..11: tttthttthhhhhh ([4,2,6,10,11,12,8,14,13,1,7,3,5,9]) move 3..5 to 6..8 : ttttttthhhhhhh ([4,2,12,8,14,6,10,11,13,1,7,3,5,9]) cost = 7 14 coins (N=7) with K=4: move 1..4 to 2..5 : hhthtththththt ([5,1,2,3,4,6,7,8,9,10,11,12,13,14]) move 1..4 to 3..6 : tthhthhthththt ([4,6,5,1,2,3,7,8,9,10,11,12,13,14]) move 1..4 to 2..5 : ttthhhhthththt ([2,4,6,5,1,3,7,8,9,10,11,12,13,14]) move 4..7 to 7..10: tttththhhhhtht ([2,4,6,8,9,10,5,1,3,7,11,12,13,14]) move 11..14 to 6..9 : tttthhthtthhhh ([2,4,6,8,9,11,12,13,14,10,5,1,3,7]) move 3..6 to 7..10: ttthtttthhhhhh ([2,4,12,13,14,10,6,8,9,11,5,1,3,7]) move 1..4 to 5..8 : ttttttthhhhhhh ([14,10,6,8,2,4,12,13,9,11,5,1,3,7]) cost = 7 See below (go3/0) for more of the number of optimal solutions. Note: This is quite slow even for relatively small number of coins, e.g. N=20 (40 coins). This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. import planner. main => go. go ?=> N = 4, % 2*N coins K = 2, % Number of coins to move each step println([n=N,k=K]), Init = [[h,t] : _ in 1..N].flatten, % h,t,h,t,... Final = sort_down(Init), % t,t,t,...h,h,h,... cl_facts($[final_state(Final)]), println(init=Init=Final), % best_plan_nondet([Init,K],Plan,Cost), % Show all optimal solutions % best_plan([Init,K],Plan,Cost), % best_plan_bin([Init,K],N,Plan,Cost), % best_plan_bb([Init,K],N,Plan,Cost), % best_plan_unbounded([Init,K],N,Plan,Cost), plan([Init,K],N,Plan,Cost), % Assuming conjecture 1 is correct, i.e. that we need minimum N moves. println(plan=Plan), X = 1..(2*N), foreach([move,F,to,T,To1] in Plan) X := move(X,K,F.first,T.first), % Replicate the move for integers 1..2*N % X := move2(X,K,F.first,T.first), % Replicate the move for integers 1..2*N F1 = F[1], F2 = F.last, T1 = T[1], T2 = T.last, if K == 2 then printf("move [%2d,%2d] to [%2d,%2d]: %w (%w)\n",F1,F2,T1,T2,To1,X) else printf("move %2d..%-2d to %2d..%-2d: %w (%w)\n",F1,F1+K-1,T1,T1+K-1,To1,X) end end, println(cost=Cost), nl, fail, nl. go => true. /* Show all the 5424 solutions for N=4 (8 coins) */ go2 ?=> N = 4, % 2*N coins K = 2, % Number of coins to move each step println([n=N,k=K]), Init = [[h,t] : _ in 1..N].flatten, % h,t,h,t,... Final = sort_down(Init), % t,t,t,...h,h,h,... cl_facts($[final_state(Final)]), println(init=Init=Final), best_plan_nondet([Init,K],Plan,Cost), % Show all optimal solutions % best_plan([Init,K],Plan,Cost), % best_plan_bin([Init,K],N,Plan,Cost), % best_plan_bb([Init,K],N,Plan,Cost), % best_plan_unbounded([Init,K],N,Plan,Cost), % plan([Init,K],N,Plan,Cost), % Assuming conjecture 1 is correct, i.e. that we need minimum N moves. println(plan=Plan), X = 1..(2*N), foreach([move,F,to,T,To1] in Plan) X := move(X,K,F.first,T.first), % Replicate the move for integers 1..2*N % X := move2(X,K,F.first,T.first), % Replicate the move for integers 1..2*N F1 = F[1], F2 = F.last, T1 = T[1], T2 = T.last, if K == 2 then printf("move [%2d,%2d] to [%2d,%2d]: %w (%w)\n",F1,F2,T1,T2,To1,X) else printf("move %2d..%-2d to %2d..%-2d: %w (%w)\n",F1,F1+K-1,T1,T1+K-1,To1,X) end end, println(cost=Cost), nl, fail, nl. go2 => true. /* Find the number of optimal solutions for N = 2..5 For eight coins(N=4) there are 5224 solutions. This is the original problem. For four coins(N=2) there are 6 solutions. For six coins(N=3) there are 84 solutions. For ten coins (N=5) there are 214704 solutions. K = 2 N coins optimal cost #sols --------------------- 1 2 - 0 2 4 2 6 3 6 3 84 4 8 4 5424 5 10 5 214704 [0,6,84,5424,214704] is not in OEIS. For other values of K (1,3,4): K = 1 N coins optimal cost #sols -------------------------- 1 2 1 2 2 4 2 20 3 6 3 480 4 8 4 20800 5 10 5 ? K = 3 N coins optimal cost #sols -------------------------- 1 2 - 0 2 4 - 0 3 6 3 54 4 8 4 3052 5 10 5 264834 K = 4 N coins optimal cost #sols -------------------------- 1 2 - 0 2 4 - 0 3 6 - 0 4 8 4 620 5 10 5 44908 2..4: 2min19.07s with move/4 <--- 2..4: 2min42.17s with move2/4 */ go3 => K = 2, % foreach(N in K..5) foreach(N in K..4) println(n=N), Init = [[h,t] : _ in 1..N].flatten, % h,t,h,t,... Final = sort_down(Init), % t,t,t,...h,h,h,... cl_facts($[final_state(Final)]), println(init=Init=Final), initialize_table, % clear previous tabling Count = count_all(best_plan_nondet([Init,K],N,_Plan,_Cost)), println(N=Count), nl end, nl. % TEST of different move*/4. go4 => N = 8, X = 1..N, foreach(From in 1..N-1, To in 1..N-1, From != To) T1 = move(X,2,From,To), % T2 = move2(X,2,From,To), T2 = move3(X,2,From,To), println([from=From,to=To=T1]), println([from=From,to=To=T2]), if T1 == T2 then println(ok) else println(not_ok) end, nl end, nl. final([From,_]) => final_state(From). % % In general it's faster with tabling (memoization) % but for larger problems it will eat RAM. % % table action([From,K],To,Move,Cost) => Len = From.len, between(1,Len-K+1,FromPos), between(1,Len-K+1,InsertPos), FromPos != InsertPos, To1 = move(From,K,FromPos,InsertPos), % To1 = move2(From,K,FromPos,InsertPos), % TEST To = [To1,K], Move = [move,FromPos..FromPos+K-1,to,InsertPos..InsertPos+K-1,To1], Cost = 1. % % Heuristic: number of t's not in final 1..N positions. % heuristic([From|_]) = [1 : I in 1..From.len div 2, From[I] != t].len. % % Move K (contiguous) pieces from FromPos to ToPos. % move(L,K,FromPos,ToPos) = L2 => if FromPos == ToPos then L2 = L else Ps = L[FromPos..FromPos+K-1], L2 = copy_term(L), foreach(I in FromPos..FromPos+K-1) L2[I] := 'x' end, Pos = cond(ToPos < FromPos,ToPos,ToPos+K), L2 := insert_all(L2,Pos,Ps).delete_all('x') end. % Trying to get a faster version % This is slower than move/4. move2(L,K,FromPos,ToPos) = L2 => if FromPos == ToPos then L2 = L else Len = L.len, if FromPos < ToPos then T = L[FromPos..ToPos+K-1], L2 = L[1..FromPos-1] ++ rotate_n(T,K) ++ L[ToPos+K..Len] else T = L[ToPos..FromPos+K-1], L2 = L[1..ToPos-1] ++ rotate_n(T,-K) ++ L[FromPos+K..Len] end end. /* % Another approach: TODO! move3(L,K,FromPos,ToPos) = L2 => println(correct=move(L,K,FromPos,ToPos)), if FromPos == ToPos then L2 = L else Len = L.len, L2 = new_list(Len), if FromPos < ToPos then println("from < to"), foreach(I in 1..Len) if I < FromPos ; I > ToPos+K-1 then L2[I] = L[I] end end, println(l2_1=L2), % Move From -> To foreach(I in 0..K-1) L2[ToPos+I] = L[FromPos+I] end, println(l2_2=L2), % Move the rest to FromPos... foreach(I in FromPos..ToPos-1) println(I=(FromPos+I-1)), L2[I] = L[ToPos+I-1] end, println(l2_3=L2), else % ToPos < FromPos println("to < from"), foreach(I in 1..Len) if I < ToPos ; I > FromPos+K-1 then L2[I] = L[I] end end, println(l2_1=L2), % Move From -> To foreach(I in 0..K-1) L2[ToPos+I] = L[FromPos+I] end, println(l2_2=L2), foreach(I in ToPos..FromPos-1) % println(i=I=L[I]=L[ToPos+I-1]), L2[ToPos+I-1] = L[I] end, println(l2_3=L2), end end. */ % % Rotate the list L N steps (either positive or negative N) % rotate(1..10,3) -> [4,5,6,7,8,9,10,1,2,3] % rotate(1..10,-3) -> [8,9,10,1,2,3,4,5,6,7] % rotate_n(L,N) = Rot => Len = L.length, R = cond(N < 0, Len + N, N), Rot = [L[I] : I in (R+1..Len) ++ 1..R].