/* 24 Game in Picat. From Rosetta Code http://rosettacode.org/wiki/24_game/Solve """ Write a function that given four digits subject to the rules of the 24 game, computes an expression to solve the game if possible. Show examples of solutions generated by the function """ Cf - 24_game.pi - my Gamble model gamble_24_game.rkt This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import ppl_distributions, ppl_utils. import util. % import ordset. main => go. /* [numbers = [1,2,3,4],target = 24] min_accepted_samples = 1000 Solutions: [1 * 2 = 2,2 * 3 = 6,6 * 4 = 24] [1 * 2 = 2,2 * 4 = 8,8 * 3 = 24] [1 * 3 = 3,3 * 2 = 6,6 * 4 = 24] [1 * 3 = 3,3 * 4 = 12,12 * 2 = 24] [1 * 4 = 4,4 * 2 = 8,8 * 3 = 24] [1 * 4 = 4,4 * 3 = 12,12 * 2 = 24] [1 + 2 = 3,3 + 3 = 6,6 * 4 = 24] [1 + 3 = 4,4 + 2 = 6,6 * 4 = 24] [2 * 1 = 2,2 * 3 = 6,6 * 4 = 24] [2 * 1 = 2,2 * 4 = 8,8 * 3 = 24] [2 * 3 = 6,6 * 1 = 6,6 * 4 = 24] [2 * 3 = 6,6 * 4 = 24,24 * 1 = 24] [2 * 3 = 6,6 * 4 = 24,24 / 1 = 24.0] [2 * 3 = 6,6 / 1 = 6.0,6.0 * 4 = 24.0] [2 * 4 = 8,8 * 1 = 8,8 * 3 = 24] [2 * 4 = 8,8 * 3 = 24,24 * 1 = 24] [2 * 4 = 8,8 * 3 = 24,24 / 1 = 24.0] [2 * 4 = 8,8 / 1 = 8.0,8.0 * 3 = 24.0] [2 + 1 = 3,3 + 3 = 6,6 * 4 = 24] [2 + 3 = 5,5 + 1 = 6,6 * 4 = 24] [2 / 1 = 2.0,2.0 * 3 = 6.0,6.0 * 4 = 24.0] [2 / 1 = 2.0,2.0 * 4 = 8.0,8.0 * 3 = 24.0] [3 * 1 = 3,3 * 2 = 6,6 * 4 = 24] [3 * 1 = 3,3 * 4 = 12,12 * 2 = 24] [3 * 2 = 6,6 * 1 = 6,6 * 4 = 24] [3 * 2 = 6,6 * 4 = 24,24 * 1 = 24] [3 * 2 = 6,6 * 4 = 24,24 / 1 = 24.0] [3 * 2 = 6,6 / 1 = 6.0,6.0 * 4 = 24.0] [3 * 4 = 12,12 * 1 = 12,12 * 2 = 24] [3 * 4 = 12,12 * 2 = 24,24 * 1 = 24] [3 * 4 = 12,12 * 2 = 24,24 / 1 = 24.0] [3 * 4 = 12,12 / 1 = 12.0,12.0 * 2 = 24.0] [3 + 1 = 4,4 + 2 = 6,6 * 4 = 24] [3 + 2 = 5,5 + 1 = 6,6 * 4 = 24] [3 / 1 = 3.0,3.0 * 2 = 6.0,6.0 * 4 = 24.0] [3 / 1 = 3.0,3.0 * 4 = 12.0,12.0 * 2 = 24.0] [4 * 1 = 4,4 * 2 = 8,8 * 3 = 24] [4 * 1 = 4,4 * 3 = 12,12 * 2 = 24] [4 * 2 = 8,8 * 1 = 8,8 * 3 = 24] [4 * 2 = 8,8 * 3 = 24,24 * 1 = 24] [4 * 2 = 8,8 * 3 = 24,24 / 1 = 24.0] [4 * 2 = 8,8 / 1 = 8.0,8.0 * 3 = 24.0] [4 * 3 = 12,12 * 1 = 12,12 * 2 = 24] [4 * 3 = 12,12 * 2 = 24,24 * 1 = 24] [4 * 3 = 12,12 * 2 = 24,24 / 1 = 24.0] [4 * 3 = 12,12 / 1 = 12.0,12.0 * 2 = 24.0] [4 / 1 = 4.0,4.0 * 2 = 8.0,8.0 * 3 = 24.0] [4 / 1 = 4.0,4.0 * 3 = 12.0,12.0 * 2 = 24.0] num_solutions = 48 With **, there are some more solutions (in total 66 solutions): [2 * 3 = 6,6 * 4 = 24,24 ** 1 = 24] [2 * 3 = 6,6 ** 1 = 6,6 * 4 = 24] [2 * 4 = 8,8 * 3 = 24,24 ** 1 = 24] [2 * 4 = 8,8 ** 1 = 8,8 * 3 = 24] [2 ** 1 = 2,2 * 3 = 6,6 * 4 = 24] [2 ** 1 = 2,2 * 4 = 8,8 * 3 = 24] [3 * 2 = 6,6 * 4 = 24,24 ** 1 = 24] [3 * 2 = 6,6 ** 1 = 6,6 * 4 = 24] [3 * 4 = 12,12 * 2 = 24,24 ** 1 = 24] [3 * 4 = 12,12 ** 1 = 12,12 * 2 = 24] [3 ** 1 = 3,3 * 2 = 6,6 * 4 = 24] [3 ** 1 = 3,3 * 4 = 12,12 * 2 = 24] [4 * 2 = 8,8 * 3 = 24,24 ** 1 = 24] [4 * 2 = 8,8 ** 1 = 8,8 * 3 = 24] [4 * 3 = 12,12 * 2 = 24,24 ** 1 = 24] [4 * 3 = 12,12 ** 1 = 12,12 * 2 = 24] [4 ** 1 = 4,4 * 2 = 8,8 * 3 = 24] [4 ** 1 = 4,4 * 3 = 12,12 * 2 = 24] */ go ?=> Numbers = 1..4, Target = 24, println([numbers=Numbers,target=Target]), reset_store, run_model(10_000,$model(Numbers,Target),[presentation=[], min_accepted_samples=1000 % ,show_accepted_samples=true ]), Store = get_store(), println("Solutions:"), C = 0, foreach(V in Store.get("res").remove_dups.sort) println(V.map(first)), C := C + 1, end, println(num_solutions=C), nl, nl. go => true. get_eq(Op,A,B,Eval) = to_fstring("%w %w %w = %w",A,Op,B,Eval). f_loop(Lst,Nums,Ops) = Res => if Nums == [] then Res = Lst else Val = Lst.last.last, Op = uniform_draw(Ops), Num = uniform_draw(Nums), F =.. [Op,Val,Num], Eval = F.apply, Res = f_loop(Lst ++ [[get_eq(Op,Val,Num,Eval),Eval]],Nums.delete(Num),Ops) end. f(Target,Numbers,Ops) = Res => InitNum = uniform_draw(Numbers), Res = f_loop([[InitNum]],Numbers.delete(InitNum),Ops). model(Numbers,Target) => Ops = $[+, -, *, (/) % , ** ], Res = f(Target,Numbers,Ops), LastVal = Res.last.last, observe(LastVal * 1.0 == Target * 1.0), if observed_ok then add("res",Res.rest), end. /* Checking the number of solutions for targets 0..25 with **. [numbers = [1,2,3,4],target = 0,num_solutions = 74] [numbers = [1,2,3,4],target = 1,num_solutions = 134] [numbers = [1,2,3,4],target = 2,num_solutions = 112] [numbers = [1,2,3,4],target = 3,num_solutions = 76] [numbers = [1,2,3,4],target = 4,num_solutions = 92] [numbers = [1,2,3,4],target = 5,num_solutions = 101] [numbers = [1,2,3,4],target = 6,num_solutions = 89] [numbers = [1,2,3,4],target = 7,num_solutions = 16] [numbers = [1,2,3,4],target = 8,num_solutions = 58] [numbers = [1,2,3,4],target = 9,num_solutions = 81] [numbers = [1,2,3,4],target = 10,num_solutions = 71] [numbers = [1,2,3,4],target = 11,num_solutions = 31] [numbers = [1,2,3,4],target = 12,num_solutions = 35] [numbers = [1,2,3,4],target = 13,num_solutions = 44] [numbers = [1,2,3,4],target = 14,num_solutions = 51] [numbers = [1,2,3,4],target = 15,num_solutions = 13] [numbers = [1,2,3,4],target = 16,num_solutions = 27] [numbers = [1,2,3,4],target = 17,num_solutions = 4] [numbers = [1,2,3,4],target = 18,num_solutions = 30] [numbers = [1,2,3,4],target = 19,num_solutions = 24] [numbers = [1,2,3,4],target = 20,num_solutions = 28] [numbers = [1,2,3,4],target = 21,num_solutions = 10] [numbers = [1,2,3,4],target = 22,num_solutions = 4] [numbers = [1,2,3,4],target = 23,num_solutions = 8] [numbers = [1,2,3,4],target = 24,num_solutions = 66] [numbers = [1,2,3,4],target = 25,num_solutions = 8] */ go2 ?=> Numbers = 1..4, member(Target,0..25), reset_store, run_model(10_000,$model(Numbers,Target),[presentation=[], min_accepted_samples=1000 % ,show_accepted_samples=true ]), Store = get_store(), C = 0, foreach(_V in Store.get("res").remove_dups.sort) % println(V.map(first)), C := C + 1, end, println([numbers=Numbers,target=Target,num_solutions=C]), fail, nl, nl. go2 => true. /* Random (20 samples) [numbers = [13,16,27,25,23,25,16],target = 92] [13 * 16 = 208,208 - 23 = 185,185 - 16 = 169,169 - 25 = 144,144 - 25 = 119,119 - 27 = 92] [13 * 16 = 208,208 - 27 = 181,181 - 16 = 165,165 - 25 = 140,140 - 23 = 117,117 - 25 = 92] [16 * 13 = 208,208 - 25 = 183,183 - 16 = 167,167 - 27 = 140,140 - 23 = 117,117 - 25 = 92] [16 * 13 = 208,208 - 27 = 181,181 - 16 = 165,165 - 25 = 140,140 - 23 = 117,117 - 25 = 92] [16 * 13 = 208,208 - 27 = 181,181 - 25 = 156,156 - 16 = 140,140 - 23 = 117,117 - 25 = 92] [16 * 13 = 208,208 - 27 = 181,181 - 25 = 156,156 - 23 = 133,133 - 16 = 117,117 - 25 = 92] [16 - 13 = 3,3 * 27 = 81,81 - 23 = 58,58 + 25 = 83,83 + 25 = 108,108 - 16 = 92] [16 - 16 = 0,0 / 25 = 0.0,0.0 + 25 = 25.0,25.0 + 27 = 52.0,52.0 / 13 = 4.0,4.0 * 23 = 92.0] [23 + 25 = 48,48 - 16 = 32,32 * 27 = 864,864 / 16 = 54.0,54.0 + 25 = 79.0,79.0 + 13 = 92.0] [23 - 16 = 7,7 + 25 = 32,32 - 27 = 5,5 * 16 = 80,80 + 25 = 105,105 - 13 = 92] [23 - 27 = -4,-4 * 25 = -100,-100 / 16 = -6.25,-6.25 + 25 = 18.75,18.75 - 13 = 5.75,5.75 * 16 = 92.0] [25 + 23 = 48,48 - 16 = 32,32 / 16 = 2.0,2.0 * 27 = 54.0,54.0 + 25 = 79.0,79.0 + 13 = 92.0] [25 + 23 = 48,48 - 27 = 21,21 - 16 = 5,5 * 16 = 80,80 - 13 = 67,67 + 25 = 92] [25 + 25 = 50,50 - 16 = 34,34 - 16 = 18,18 + 13 = 31,31 - 27 = 4,4 * 23 = 92] [25 - 16 = 9,9 - 27 = -18,-18 - 16 = -34,-34 + 13 = -21,-21 + 25 = 4,4 * 23 = 92] [25 - 23 = 2,2 * 27 = 54,54 + 25 = 79,79 + 16 = 95,95 + 13 = 108,108 - 16 = 92] [27 * 25 = 675,675 + 16 = 691,691 + 13 = 704,704 / 16 = 44.0,44.0 + 25 = 69.0,69.0 + 23 = 92.0] [27 - 25 = 2,2 * 16 = 32,32 - 25 = 7,7 - 16 = -9,-9 + 13 = 4,4 * 23 = 92] [27 - 25 = 2,2 * 25 = 50,50 + 16 = 66,66 + 16 = 82,82 - 13 = 69,69 + 23 = 92] num_solutions = 19 [numbers = [17,24,29,25,21,14,12],target = 86] [12 * 14 = 168,168 - 25 = 143,143 + 17 = 160,160 - 21 = 139,139 - 29 = 110,110 - 24 = 86] [12 * 17 = 204,204 / 24 = 8.5,8.5 * 14 = 119.0,119.0 - 25 = 94.0,94.0 - 29 = 65.0,65.0 + 21 = 86.0] [12 - 14 = -2,-2 + 29 = 27,27 - 25 = 2,2 * 24 = 48,48 + 17 = 65,65 + 21 = 86] [12 - 14 = -2,-2 + 29 = 27,27 - 25 = 2,2 * 24 = 48,48 + 21 = 69,69 + 17 = 86] [14 * 12 = 168,168 + 17 = 185,185 - 25 = 160,160 - 24 = 136,136 - 21 = 115,115 - 29 = 86] [14 * 12 = 168,168 - 21 = 147,147 + 17 = 164,164 - 24 = 140,140 - 25 = 115,115 - 29 = 86] [14 * 12 = 168,168 - 21 = 147,147 + 17 = 164,164 - 25 = 139,139 - 29 = 110,110 - 24 = 86] [14 * 12 = 168,168 - 21 = 147,147 - 29 = 118,118 - 25 = 93,93 + 17 = 110,110 - 24 = 86] [14 * 12 = 168,168 - 29 = 139,139 + 17 = 156,156 - 25 = 131,131 - 21 = 110,110 - 24 = 86] [14 - 21 = -7,-7 + 29 = 22,22 / 12 = 1.833333333333333,1.833333333333333 * 24 = 44.0,44.0 + 17 = 61.0,61.0 + 25 = 86.0] [17 * 12 = 204,204 / 24 = 8.5,8.5 * 14 = 119.0,119.0 - 25 = 94.0,94.0 + 21 = 115.0,115.0 - 29 = 86.0] [17 * 12 = 204,204 / 24 = 8.5,8.5 * 14 = 119.0,119.0 - 25 = 94.0,94.0 - 29 = 65.0,65.0 + 21 = 86.0] [17 - 21 = -4,-4 + 29 = 25,25 + 25 = 50,50 / 12 = 4.166666666666667,4.166666666666667 * 24 = 100.0,100.0 - 14 = 86.0] [24 - 14 = 10,10 * 12 = 120,120 + 29 = 149,149 - 25 = 124,124 - 17 = 107,107 - 21 = 86] [24 - 14 = 10,10 * 12 = 120,120 + 29 = 149,149 - 25 = 124,124 - 21 = 103,103 - 17 = 86] [29 + 17 = 46,46 - 21 = 25,25 + 25 = 50,50 * 24 = 1200,1200 / 12 = 100.0,100.0 - 14 = 86.0] [29 + 17 = 46,46 - 21 = 25,25 + 25 = 50,50 / 12 = 4.166666666666667,4.166666666666667 * 24 = 100.0,100.0 - 14 = 86.0] [29 - 17 = 12,12 * 14 = 168,168 - 25 = 143,143 - 12 = 131,131 - 24 = 107,107 - 21 = 86] [29 - 21 = 8,8 * 17 = 136,136 - 14 = 122,122 * 12 = 1464,1464 / 24 = 61.0,61.0 + 25 = 86.0] [29 - 25 = 4,4 + 21 = 25,25 - 17 = 8,8 * 12 = 96,96 + 14 = 110,110 - 24 = 86] num_solutions = 20 [numbers = [14,5,25,28,6,7,8,5,16],target = 56] [14 * 5 = 70,70 - 6 = 64,64 + 5 = 69,69 + 8 = 77,77 - 28 = 49,49 - 25 = 24,24 - 16 = 8,8 * 7 = 56] [14 * 5 = 70,70 - 8 = 62,62 - 25 = 37,37 - 6 = 31,31 + 5 = 36,36 / 16 = 2.25,2.25 * 28 = 63.0,63.0 - 7 = 56.0] [16 * 6 = 96,96 - 8 = 88,88 + 7 = 95,95 + 5 = 100,100 + 14 = 114,114 - 25 = 89,89 - 5 = 84,84 - 28 = 56] [25 + 28 = 53,53 + 5 = 58,58 + 16 = 74,74 + 5 = 79,79 - 8 = 71,71 + 6 = 77,77 - 14 = 63,63 - 7 = 56] [25 + 28 = 53,53 + 6 = 59,59 + 14 = 73,73 - 5 = 68,68 - 16 = 52,52 - 8 = 44,44 + 7 = 51,51 + 5 = 56] [25 / 5 = 5.0,5.0 + 6 = 11.0,11.0 * 8 = 88.0,88.0 + 5 = 93.0,93.0 - 28 = 65.0,65.0 + 14 = 79.0,79.0 - 16 = 63.0,63.0 - 7 = 56.0] [28 - 14 = 14,14 * 6 = 84,84 * 5 = 420,420 + 8 = 428,428 + 5 = 433,433 - 25 = 408,408 - 16 = 392,392 / 7 = 56.0] [28 / 8 = 3.5,3.5 * 16 = 56.0,56.0 + 5 = 61.0,61.0 + 14 = 75.0,75.0 + 5 = 80.0,80.0 - 6 = 74.0,74.0 - 25 = 49.0,49.0 + 7 = 56.0] [5 * 28 = 140,140 / 5 = 28.0,28.0 - 8 = 20.0,20.0 + 25 = 45.0,45.0 + 6 = 51.0,51.0 + 7 = 58.0,58.0 + 14 = 72.0,72.0 - 16 = 56.0] [5 - 28 = -23,-23 + 7 = -16,-16 / 16 = -1.0,-1.0 + 6 = 5.0,5.0 * 5 = 25.0,25.0 - 8 = 17.0,17.0 + 25 = 42.0,42.0 + 14 = 56.0] [5 - 5 = 0,0 + 14 = 14,14 + 7 = 21,21 + 28 = 49,49 - 8 = 41,41 + 6 = 47,47 - 16 = 31,31 + 25 = 56] [5 - 6 = -1,-1 - 7 = -8,-8 / 16 = -0.5,-0.5 * 8 = -4.0,-4.0 + 14 = 10.0,10.0 * 5 = 50.0,50.0 / 25 = 2.0,2.0 * 28 = 56.0] [5 - 7 = -2,-2 + 8 = 6,6 + 5 = 11,11 - 6 = 5,5 + 14 = 19,19 + 28 = 47,47 + 25 = 72,72 - 16 = 56] [5 - 7 = -2,-2 - 25 = -27,-27 + 28 = 1,1 - 8 = -7,-7 + 5 = -2,-2 + 14 = 12,12 * 6 = 72,72 - 16 = 56] [5 / 5 = 1.0,1.0 * 7 = 7.0,7.0 * 6 = 42.0,42.0 / 14 = 3.0,3.0 + 16 = 19.0,19.0 + 8 = 27.0,27.0 - 25 = 2.0,2.0 * 28 = 56.0] [6 * 5 = 30,30 - 14 = 16,16 * 7 = 112,112 + 28 = 140,140 * 16 = 2240,2240 / 8 = 280.0,280.0 / 25 = 11.199999999999999,11.199999999999999 * 5 = 56.0] [6 + 8 = 14,14 + 25 = 39,39 + 7 = 46,46 - 14 = 32,32 * 5 = 160,160 * 28 = 4480,4480 / 16 = 280.0,280.0 / 5 = 56.0] [6 - 25 = -19,-19 - 16 = -35,-35 * 8 = -280,-280 / 14 = -20.0,-20.0 + 28 = 8.0,8.0 - 5 = 3.0,3.0 + 5 = 8.0,8.0 * 7 = 56.0] [7 + 28 = 35,35 + 25 = 60,60 - 8 = 52,52 + 5 = 57,57 - 5 = 52,52 - 16 = 36,36 + 6 = 42,42 + 14 = 56] [8 - 6 = 2,2 + 28 = 30,30 - 25 = 5,5 / 5 = 1.0,1.0 + 16 = 17.0,17.0 + 5 = 22.0,22.0 - 14 = 8.0,8.0 * 7 = 56.0] num_solutions = 20 */ go3 ?=> _ = random2(), N = random_integer1(10), Numbers = random_integer1_n(30,N), Target = random_integer(100), println([numbers=Numbers,target=Target,n=N]), reset_store, run_model(10_000,$model(Numbers,Target),[ presentation=[], min_accepted_samples=20,show_accepted_samples=true ]), Store = get_store(), C = 0, foreach(V in Store.get("res").remove_dups.sort) println(V.map(first)), C := C + 1, end, println(num_solutions=C), fail, nl, nl. go3 => true.