/* BrainTwister #30: Digital Targets in Picat. https://enigmaticcode.wordpress.com/2024/07/26/braintwister-30-digital-targets/ """ BrainTwister #30: Digital targets From New Scientist #3501, 27th July 2024 [link] [link] You are playing a game in which you have to arrange 10 random single-digit numbers (which can include 0) to form five two-digit numbers, aiming for five targets: 10, 20, 30, 40 and 50. If you match a target exactly, you score that number. If you get within 5 of a target, you score half the value of the target. Otherwise you score zero for that target. For example, if you are given the numbers (1, 2, 2, 3, 3, 5, 5, 7, 8, 9), you can arrange them to get a total score of 60, as shown in the table below (although this isn’t the optimal score with these numbers). [ Target Digits Value Score ---------------------------- 10 1 7 17 0 20 2 8 28 0 30 3 5 35 15 40 3 9 39 20 50 5 2 52 25 --------------- Total 60 ] (a) Which 10 single-digit numbers would let you make the maximum possible score? (b) What’s the highest score you can make if you are given the numbers (0, 1, 1, 2, 3, 4, 5, 9, 9, 9)? (c) If you were given one of each digit 0-9, what is the highest score you could get? """ * go/0: CP/SAT approach: Total time: 0.444s * go2/0: Using permutation/2 and max_of/2: Total time 11.677s (excluding problem a). This program was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import util. import sat. main => go. /* CPU time 0.444 seconds (using SAT). problem = 0 nums = [1,2,2,3,3,5,5,7,8,9] x = [7,2,3,3,5,9,1,2,8,5] p = [8,2,4,5,7,10,1,3,9,6] scores = [0,10,16,19,27] z = 72 Target Number Score 10 79 0 20 21 10 30 32 16 40 38 19 50 55 27 CPU time 0.126 seconds. problem = a nums = [0,0,0,0,0,5,1,3,4,2] x = [1,2,3,4,5,0,0,0,0,0] p = [7,10,8,9,6,1,2,3,4,5] scores = [10,20,30,40,50] z = 150 Target Number Score 10 10 10 20 20 20 30 30 30 40 40 40 50 50 50 CPU time 0.062 seconds. problem = b nums = [0,1,1,2,3,4,5,9,9,9] x = [1,1,2,3,5,4,9,9,9,0] p = [3,2,4,5,7,6,8,9,10,1] scores = [7,9,14,19,50] z = 99 Target Number Score 10 14 7 20 19 9 30 29 14 40 39 19 50 50 50 CPU time 0.108 seconds. problem = c nums = [0,1,2,3,4,5,6,7,8,9] x = [7,1,2,4,5,6,9,8,3,0] p = [8,2,3,5,6,7,10,9,4,1] scores = [0,9,14,21,50] z = 94 Target Number Score 10 76 0 20 19 9 30 28 14 40 43 21 50 50 50 CPU time 0.148 seconds. */ go ?=> nolog, Tests = [ [0,[1,2,2,3,3,5,5,7,8,9]], % problem 0) (the example) [a,_], % problem a) [b,[0,1,1,2,3,4,5,9,9,9]], % problem b) [c, 0..9] % problem c) ], foreach([P,Nums] in Tests) println(problem=P), time(digital_targets(Nums)) end, nl. go => true. /* Non-CP: Using permutation/2 and max_of/2. Note: a) takes too long time, so it's skipped. Total time (excluding problem a): CPU time 11.677 seconds. problem = 0 CPU time 3.902 seconds. z = 72 x = [7,2,3,3,5,8,1,2,9,5] scores = [0,10,16,19,27] 10 78 0 20 21 10 30 32 16 40 39 19 50 55 27 problem = b CPU time 3.889 seconds. z = 99 x = [1,1,2,3,5,4,9,9,9,0] scores = [7,9,14,19,50] 10 14 7 20 19 9 30 29 14 40 39 19 50 50 50 problem = c CPU time 3.885 seconds. z = 94 x = [6,1,2,4,5,7,8,9,3,0] scores = [0,9,14,21,50] 10 67 0 20 18 9 30 29 14 40 43 21 50 50 50 */ go2 ?=> nolog, Tests = [ [0,[1,2,2,3,3,5,5,7,8,9]], % problem 0) (the example) % [a,_], % problem a) Too slow! [b,[0,1,1,2,3,4,5,9,9,9]], % problem b) [c, 0..9] % problem c) ], Targets = [10,20,30,40,50], foreach([P,Nums] in Tests) println(problem=P), time(maxof(digital_targets2(Nums,X,Scores,Z),Z)), println(z=Z), println(x=X), println(scores=Scores), N = 5, foreach(I in 1..N) printf("%6w %5w %4w\n",Targets[I],10*X[I]+X[I+N],Scores[I]) end, nl, nl end, nl. go2 => true. % % CP/SAT % digital_targets(Nums) => Targets = [10,20,30,40,50], N = 5, M = 2*N, if var(Nums) then % For problem a) Nums = new_list(M), Nums :: 0..9 end, X = new_list(M), X :: 0..9, % The permutation of Nums -> X P = new_list(M), P :: 1..M, all_different(P), permutation3(Nums,P,X), Scores = new_list(N), Scores :: 0..99, foreach(I in 1..N) T #= 10*X[I]+X[I+N], Scores[I] #= cond(Targets[I]#=T,T, cond(abs(Targets[I]-T) #<= 5,T div 2, 0)) end, Z #= sum(Scores), Vars = X ++ Scores ++ P ++ Nums, solve($[max(Z)],Vars), println(nums=Nums), println(x=X), println(p=P), println(scores=Scores), println(z=Z), println("Target Number Score"), foreach(I in 1..N) printf("%6w %5w %4w\n",Targets[I],10*X[I]+X[I+N],Scores[I]) end, nl, nl. % % Non-CP, using plain permutation % % Shorter but much slower. % % The "free" problem (problem a) takes very long time. % digital_targets2(Nums,X,Scores,Z) => Targets = [10,20,30,40,50], N = 5, M = 2*N, if var(Nums) then % For problem a) % Generate all possible permutations of [0..9,0..9,...0..9] X = new_list(M), foreach(I in 1..M) member(X[I],0..9) end else permutation(Nums,X) end, Scores = new_list(N), foreach(I in 1..N) T = 10*X[I]+X[I+N], Scores[I] = cond(Targets[I]==T,T, cond(abs(Targets[I]-T) <= 5,T div 2, 0)) end, Z = sum(Scores). % % The permutation from A <-> B using the permutation P % permutation3(A,P,B) => foreach(I in 1..A.length) % B[I] #= A[P[I]] PI #= P[I], BI #= B[I], element(PI, A, BI) end.