/* CountDown problem in Picat. From Ruby Quiz #7 http://www.rubyquiz.com/quiz7.html """ One of the longest-running quiz shows on UK TV is called Countdown, and has a "numbers round". There are some cards laid face down in front of the host - the top row contains 'large' numbers (from the set 25, 50, 75, 100), and the rest are 'small' (1 to 10). Six cards are picked and displayed: the choice is made by one of the contestants, who typically will ask for one large number and five small ones. Next, a machine called "Cecil" picks a target number between 100 and 999 at random. The contestants then have 30 seconds to find a way of combining the source numbers using the normal arithmetic operators (+, -, *, /) to make the target number, or to get as close as possible. Each source card can be used no more than once. The same applies to any intermediate results, although of course you don't have to explicitly show the intermediate results. Example: source 100 5 5 2 6 8, target 522 100 * 5 = 500 5 + 6 = 11 11 * 2 = 22 500 + 22 = 522 or more succinctly, (5*100)+((5+6)*2) = 522 Another solution is (100+6)*5-8 = 522 Normal arithmetic rules apply, and in particular you are not allowed to use integer rounding. That is, 7 divided by 3 is 2 1/3, not 2. The quiz is to write a program which will accept one target number and a list of source numbers, and generate a solution which calculates the target or a number as close to the target as possible. """ Note: This model is more restricted in how the operators works: It only solve solutions of this form: Numbers = [3,5,9,9,10,100] Target = 564 Solution: (((((100/5)*10)-9)*3)-9) = 564 100/5 = 20 20*10 = 200 200-9 = 191 191*3 = 573 573-9 = 564 Also, if there are some duplicates it will show duplicated solutions, since two permutations give the same result. This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp. main => time2(go). go ?=> % Target=564, Target = 464, % Numbers = [3,5,9,9,10,100], Numbers = [4, 50, 10, 100, 8, 2], countdown(Numbers,Target), nl, fail, nl. go => true. go2 => Numbers = [4,4,4,4], foreach(Target in 1..4**4) All=findall(_, countdown(Numbers,Target)), printf("\tTarget=%4d: %4d solutions\n", Target,All.length) end, nl. % Target: 24 % N #sols % ------- % 1 0 % 2 4 % 3 125 % 4 4446 % 5 148822 % % OEIS: 0,4,125,4446,148822 go3 => N = 4, Target = 24, All=findall(_, countdown2(N,Target)), printf("\tTarget=%4d: %4d solutions\n", Target,All.length), nl. % % check(Target, Print, S) % Target: the target number to be constructed % Print : true -> print the solution string, else -> don't % S : the solution string % countdown(Numbers,Target) => println([target=Target,numbers=Numbers]), N = Numbers.length, % Picat's integer operator is "//" and is used for the check below OpsString = ["+","-","*","//"], OpsString2 = ["+","-","*","/"], % "/" instead of "//" for nicer presentation % decision variables % The result, the numbers in correct positions X = new_list(N), X :: Numbers.remove_dups(), % permutations of Numbers Perms = new_list(N), Perms :: 1..N, % array of the consecutive results (S[N] = Target) S = new_list(N), S :: 1..10000, % Operators % 1: + % 2: - % 3: * % 4: // (integer division) Ops = new_list(N-1), Ops :: 1..OpsString.length, % % constraints % all_different(Perms), foreach(I in 1..N) % x[i] = numbers[perm[i]] element(Perms[I],Numbers,X[I]) % nth(Perms[I],Numbers,X[I]) end, make_ops(X,Ops,Target,S), % search Vars = X ++ Ops ++ Perms ++ S ++ [Target], solve([ff,split], Vars), % % solution % % println(numbers=Numbers), % println(target=Target), println(x=X), % println(s=S), % println(perms=Perms), % println(ops=Ops), % The solution as a string Str = ['(' : _ in 1..N-1] ++ X[1].to_string(), Str2 = Str, foreach(I in 1..N-1) Str := Str ++ " " ++ OpsString[Ops[I]] ++ " " ++ X[I+1].to_string() ++ ")", Str2 := Str2 ++ " " ++ OpsString2[Ops[I]] ++ " " ++ X[I+1].to_string() ++ ")" end, % check it S2 = apply(Str.parse_term()), if S2 = Target then println(str=Str2), foreach(I in 1..N-1) printf("%d %w %d = %d\n", S[I],OpsString2[Ops[I]],X[I+1],S[I+1]) end, nl else println([not_correct_parsed,target=Target,s2=S2]), halt end. % % Here the input is a length of a list and % then we check what solutions there are for = Target % countdown2(N,Target) => println([target=Target,n=N]), % Picat's integer operator is "//" and is used for the check below OpsString = ["+","-","*","//"], OpsString2 = ["+","-","*","/"], % "/" instead of "//" for nicer presentation % decision variables % The result, the numbers in correct positions X = new_list(N), X :: 1..9, % permutations of Numbers Perms = new_list(N), Perms :: 1..N, % array of the consecutive results (S[N] = Target) S = new_list(N), S :: 1..10000, % Operators % 1: + % 2: - % 3: * % 4: // (integer division) Ops = new_list(N-1), Ops :: 1..OpsString.length, % % constraints % all_different(Perms), foreach(I in 1..N) % x[i] = numbers[perm[i]] element(Perms[I],X,X[I]) % nth(Perms[I],Numbers,X[I]) end, make_ops(X,Ops,Target,S), % search Vars = X ++ Ops ++ Perms ++ S ++ [Target], solve([ff,split], Vars), % % solution % % println(numbers=Numbers), % println(target=Target), println(x=X), % println(s=S), % println(perms=Perms), % println(ops=Ops), % The solution as a string Str = ['(' : _ in 1..N-1] ++ X[1].to_string(), Str2 = Str, foreach(I in 1..N-1) Str := Str ++ " " ++ OpsString[Ops[I]] ++ " " ++ X[I+1].to_string() ++ ")", Str2 := Str2 ++ " " ++ OpsString2[Ops[I]] ++ " " ++ X[I+1].to_string() ++ ")" end, % check it S2 = apply(Str.parse_term()), if S2 = Target then println(str=Str2), foreach(I in 1..N-1) printf("%d %w %d = %d\n", S[I],OpsString2[Ops[I]],X[I+1],S[I+1]) end, nl else println([not_correct_parsed,target=Target,s2=S2]), halt end. % The (basic) operations make_op(A,B, Op,Res) => (Op #= 1) #<=> (Res #= A + B), (Op #= 2) #<=> (Res #= A - B), (Op #= 3) #<=> (Res #= A * B), (Op #= 4) #<=> (A #= Res * B). % division % (Op #= 4) #<=> (Res #= A // B). % division make_ops(Y, Ops, Res, S) => N = Y.length, S[1] #= Y[1], foreach(I in 1..N-1) make_op(S[I], Y[I+1], Ops[I], S[I+1]) end, Res #= S[N].