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.
You are encouraged to solve this task according to the task description, using any language you may know.
Show examples of solutions generated by the function
C.F: Arithmetic Evaluator
Clojure
The code: <lang clojure>(use 'clojure.contrib.combinatorics) (defn mult [a b] (if (and (number? a) (number? b)) (* a b) "NaN")) (defn add [a b] (if (and (number? a) (number? b)) (+ a b) "NaN")) (defn sub [a b] (if (and (number? a) (number? b)) (- a b) "NaN")) (defn div [a b] (if (or (= b 0) (not (number? b)) (not (number? a))) "NaN" (/ (double a) (double b))))
(defn nested-replace [l m] ;apply map 'm' to each element of seq. 'l' all the way down. (cond (= l '()) '() (m (first l)) (concat (list (m (first l))) (nested-replace (rest l) m)) (seq? (first l)) (concat (list (nested-replace (first l) m)) (nested-replace (rest l) m)) true (concat (list (first l)) (nested-replace (rest l) m))))
(defn format-solution [sol] ;change expressions to infix, return arithmetic symbols to normal (let [rep-sym (fn [a] (cond (= a 'mult) '* (= a 'div) '/ (= a 'add) '+ (= a 'sub) '- true a))] (cond (number? sol) sol (seq? sol)
(list (format-solution (second sol)) (rep-sym (first sol)) (format-solution (nth sol 2))))))
(defn play24 [& digits] (count (map #(-> % format-solution println) (let [operator-map-list (map (fn [a] {:op1 (nth a 0) :op2 (nth a 1) :op3 (nth a 2)})
(selections '(mult add sub div) 3)) digits-map-list (map (fn [a] {:num1 (nth a 0) :num2 (nth a 1) :num3 (nth a 2) :num4 (nth a 3)}) (permutations digits)) patterns-list (list '(:op1 (:op2 :num1 :num2) (:op3 :num3 :num4)) '(:op1 :num1 (:op2 :num2 (:op3 :num3 :num4)))) ;Other patterns can be added here: (:op1 :num1 (:op2 (:op3 :num2 :num3) :num4)) op-subbed (reduce concat '() ;flatten the list by one level (map (fn [a] (map #(nested-replace a % ) operator-map-list)) patterns-list)) full-subbed (reduce concat '() (map (fn [a] (map #(nested-replace % a) op-subbed)) digits-map-list))] (filter #(= (eval %) 24) full-subbed)))))</lang>
The first four functions are a bit of a silly hack to protect us from division by 0 (and preserve remainders in our division) in an exception-free manner. Their impact on performance is small.
The function play24
works by substituting the given digits and the four operations into the two binary tree patterns (o (o n n) (o n n)) and (o n (o n (o n n))). The substitution is the 'hairy' part of the program: two pairs of nested maps (the function) are used to sub in first the operations and then the digits, which are matched into the tree patterns using maps (the datatype!)
Example use:
user=> (play24 '(5 6 7 8)) ((5 + 7) * (8 - 6)) (6 * (5 + (7 - 8))) (6 * (5 - (8 - 7))) (6 * (7 + (5 - 8))) (6 * (7 - (8 - 5))) ((6 * 8) / (7 - 5)) (6 * (8 / (7 - 5))) ((7 + 5) * (8 - 6)) ((8 - 6) * (5 + 7)) ((8 - 6) * (7 + 5)) ((8 * 6) / (7 - 5)) (8 * (6 / (7 - 5))) 12
Haskell
<lang haskell>import Data.List import Data.Ratio import Control.Monad import System.Environment (getArgs)
data Expr = Constant Rational |
Expr :+ Expr | Expr :- Expr | Expr :* Expr | Expr :/ Expr deriving (Eq)
ops = [(:+), (:-), (:*), (:/)]
instance Show Expr where
show (Constant x) = show $ numerator x -- In this program, we need only print integers. show (a :+ b) = strexp "+" a b show (a :- b) = strexp "-" a b show (a :* b) = strexp "*" a b show (a :/ b) = strexp "/" a b
strexp :: String -> Expr -> Expr -> String strexp op a b = "(" ++ show a ++ " " ++ op ++ " " ++ show b ++ ")"
templates :: [[Expr] -> Expr] templates = do
op1 <- ops op2 <- ops op3 <- ops [\[a, b, c, d] -> op1 a $ op2 b $ op3 c d, \[a, b, c, d] -> op1 (op2 a b) $ op3 c d, \[a, b, c, d] -> op1 a $ op2 (op3 b c) d, \[a, b, c, d] -> op1 (op2 a $ op3 b c) d, \[a, b, c, d] -> op1 (op2 (op3 a b) c) d]
eval :: Expr -> Maybe Rational eval (Constant c) = Just c eval (a :+ b) = liftM2 (+) (eval a) (eval b) eval (a :- b) = liftM2 (-) (eval a) (eval b) eval (a :* b) = liftM2 (*) (eval a) (eval b) eval (a :/ b) = do
denom <- eval b guard $ denom /= 0 liftM (/ denom) $ eval a
solve :: Rational -> [Rational] -> [Expr] solve target r4 = filter (maybe False (== target) . eval) $
liftM2 ($) templates $ nub $ permutations $ map Constant r4
main = getArgs >>= mapM_ print . solve 24 . map (toEnum . read)</lang>
Example use:
$ runghc 24Player.hs 2 3 8 9 (8 * (9 - (3 * 2))) (8 * (9 - (2 * 3))) ((9 - (2 * 3)) * 8) ((9 - (3 * 2)) * 8) ((9 - 3) * (8 / 2)) ((8 / 2) * (9 - 3)) (8 * ((9 - 3) / 2)) (((9 - 3) / 2) * 8) ((9 - 3) / (2 / 8)) ((8 * (9 - 3)) / 2) (((9 - 3) * 8) / 2) (8 / (2 / (9 - 3)))
Mathematica
The code: <lang Mathematica> treeR[n_] := Table[o[trees[a], trees[n - a]], {a, 1, n - 1}] treeR[1] := n tree[n_] :=
Flatten[treeR[n] //. {o[a_List, b_] :> (o[#, b] & /@ a), o[a_, b_List] :> (o[a, #] & /@ b)}]
game24play[val_List] :=
Union[StringReplace[StringTake[ToString[#, InputForm], {10, -2}], "-1*" ~~ n_ :> "-" <> n] & /@ (HoldForm /@ Select[Union@ Flatten[Outer[# /. {o[q_Integer] :> #2q, n[q_] :> #3q} &, Block[{O = 1, N = 1}, # /. {o :> o[O++], n :> n[N++]}] & /@ tree[4], Tuples[{Plus, Subtract, Times, Divide}, 3], Permutations[Array[v, 4]], 1]], Quiet[(# /. v[q_] :> valq) == 24] &] /. Table[v[q] -> valq, {q, 4}])]</lang>
The treeR
method recursively computes all possible operator trees for a certain number of inputs. It does this by tabling all combinations of distributions of inputs across the possible values. (For example, treeR[4]
is allotted 4 inputs, so it returns {o[treeR[3],treeR[1]],o[treeR[2],treeR[2]],o[treeR[1],treeR[3]]}
, where o
is the operator (generic at this point). The base case treeR[1]
returns n
(the input). The final output of tree[4]
(the 24 game has 4 random inputs) (tree
cleans up the output of treeR
) is:
<lang Mathematica>
{o[n, o[n, o[n, n]]],
o[n, o[o[n, n], n]], o[o[n, n], o[n, n]], o[o[n, o[n, n]], n], o[o[o[n, n], n], n]}</lang>
game24play
takes the four random numbers as input and does the following (the %
refers to code output from previous bullets):
Block[{O = 1, N = 1}, # /. {o :> o[O++], n :> n[N++]}] & /@ tree[4]
- Assign ascending numbers to the input and operator placeholders.
- Ex:
o[1][o[2][n[1], n[2]], o[3][n[3], n[4]]]
Tuples[{Plus, Subtract, Times, Divide}, 3]
- Find all combinations (
Tuples
allows repeats) of the four allowed operations. - Ex:
{{Plus, Plus, Plus}, {Plus, Plus, Subtract}, <<60>>, {Divide, Divide, Times}, {Divide, Divide, Divide}}
- Find all combinations (
Permutations[Array[v, 4]]
- Find all permutations (
Permutations
does not allow repeats) of the four given values. - Ex:
{{v[1],v[2],v[3],v[4]}, {v[1],v[2],v[4],v[3]}, <<20>>, {v[4],v[3],v[1],v[2]}, {v[4],v[3],v[2],v[1]}}
- Find all permutations (
Outer[# /. {o[q_Integer] :> #2[[q]], n[q_] :> #3[[q]]} &, %%%, %%, %, 1]
- Perform an outer join on the three above lists (every combination of each element) and with each combination put into the first (the operator tree) the second (the operation at each level) and the third (the value indexes, not actual values).
- Ex:
v[1] + v[2] - v[3] + v[4]
Union@Flatten[%]
- Get rid of any sublists caused by
Outer
and remove any duplicates (Union
).
- Get rid of any sublists caused by
Select[%, Quiet[(# /. v[q_] :> val[[q]]) == 24] &]
- Select the elements of the above list where substituting the real values returns 24 (and do it
Quiet
ly because of div-0 concerns).
- Select the elements of the above list where substituting the real values returns 24 (and do it
HoldForm /@ % /. Table[v[q] -> val[[q]], {q, 4}]
- Apply
HoldForm
so that substituting numbers will not cause evaluation (otherwise it would only ever return lists like{24, 24, 24}
!) and substitute the numbers in.
- Apply
Union[StringReplace[StringTake[ToString[#, InputForm], {10, -2}], "-1*" ~~ n_ :> "-" <> n] & /@ %]
- For each result, turn the expression into a string (for easy manipulation), strip the "
HoldForm
" wrapper, replace numbers like "-1*7" with "-7" (a idiosyncrasy of the conversion process), and remove any lingering duplicates. Some duplicates will still remain, notably constructs like "3 - 3" vs. "-3 + 3" and trivially similar expressions like "(8*3)*(6-5)" vs "(8*3)/(6-5)". Example run input and outputs:
- For each result, turn the expression into a string (for easy manipulation), strip the "
<lang Mathematica>RandomInteger[{1, 9}, 4] game24play[%]</lang>
<lang Mathematica>{7, 2, 9, 5} {-2 - 9 + 7*5}</lang>
<lang Mathematica>{7, 5, 6, 2} {6*(7 - 5 + 2), (7 - 5)*6*2, 7 + 5 + 6*2}</lang>
<lang Mathematica>{7, 6, 7, 7} {}</lang>
<lang Mathematica>{3, 7, 6, 1} {(-3 + 6)*(7 + 1), ((-3 + 7)*6)/1, (-3 + 7)*6*1,
6 - 3*(-7 + 1), 6*(-3 + 7*1), 6*(-3 + 7/1), 6 + 3*(7 - 1), 6*(7 - 3*1), 6*(7 - 3/1), 7 + 3*6 - 1}</lang>
Note that although this program is designed to be extensible to higher numbers of inputs, the largest working set in the program (the output of the Outer
function can get very large:
tree[n]
returns a list with the length being the (n-1)-th Catalan number.Tuples[{Plus, Subtract, Times, Divide}, 3]
has fixed length 64 (or p3 for p operations).Permutations[Array[v, n]]
returns permutations.
Therefore, the size of the working set is , where is the quadruple factorial. It goes without saying that this number increases very fast. For this game, the total is 7680 elements. For higher numbers of inputs, it is {7 680, 107 520, 1 935 360, 42 577 920, 1 107 025 920, ...}.
Perl
Will generate all possible solutions of any given four numbers according to the rules of the 24 game.
Note: the permute
function was taken from here
<lang Perl># Fischer-Krause ordered permutation generator
sub permute (&@) { my $code = shift; my @idx = 0..$#_; while ( $code->(@_[@idx]) ) { my $p = $#idx; --$p while $idx[$p-1] > $idx[$p]; my $q = $p or return; push @idx, reverse splice @idx, $p; ++$q while $idx[$p-1] > $idx[$q]; @idx[$p-1,$q]=@idx[$q,$p-1]; } }
@formats = ( '((%d %s %d) %s %d) %s %d', '(%d %s (%d %s %d)) %s %d', '(%d %s %d) %s (%d %s %d)', '%d %s ((%d %s %d) %s %d)', '%d %s (%d %s (%d %s %d))', );
- generate all possible combinations of operators
@op = qw( + - * / ); @operators = map{ $a=$_; map{ $b=$_; map{ "$a $b $_" }@op }@op }@op;
while(1) { print "Enter four integers or 'q' to exit: "; chomp($ent = <>); last if $ent eq 'q';
if($ent !~ /^[1-9] [1-9] [1-9] [1-9]$/){ print "invalid input\n"; next }
@n = split / /,$ent; permute { push @numbers,join ' ',@_ }@n;
for $format (@formats) { for(@numbers) { @n = split; for(@operators) { @o = split; $str = sprintf $format,$n[0],$o[0],$n[1],$o[1],$n[2],$o[2],$n[3]; $r = eval($str); print "$str\n" if $r == 24; } } } }</lang>
Python
The function is called solve, and is integrated into the game player. The docstring of the solve function shows examples of its use when isolated at the Python command line. <lang Python>
The 24 Game Player
Given any four digits in the range 1 to 9, which may have repetitions, Using just the +, -, *, and / operators; and the possible use of brackets, (), show how to make an answer of 24.
An answer of "q" will quit the game. An answer of "!" will generate a new set of four digits. An answer of "!!" will ask you for a new set of four digits. An answer of "?" will compute an expression for the current digits. Otherwise you are repeatedly asked for an expression until it evaluates to 24
Note: you cannot form multiple digit numbers from the supplied digits, so an answer of 12+12 when given 1, 2, 2, and 1 would not be allowed.
from __future__ import division, print_function from itertools import permutations, combinations, product, \
chain
from pprint import pprint as pp import random, ast, re import sys
if sys.version_info[0] < 3:
input = raw_input from itertools import izip_longest as zip_longest
else:
from itertools import zip_longest
def choose4():
'four random digits >0 as characters' return [str(random.randint(1,9)) for i in range(4)]
def ask4():
'get four random digits >0 from the plaayer' digits = while len(digits) != 4 or not all(d in '123456789' for d in digits): digits = input('Enter the digits to solve for: ') digits = .join(digits.strip().split()) return list(digits)
def welcome(digits):
print (__doc__) print ("Your four digits: " + ' '.join(digits))
def check(answer, digits):
allowed = set('() +-*/\t'+.join(digits)) ok = all(ch in allowed for ch in answer) and \ all(digits.count(dig) == answer.count(dig) for dig in set(digits)) \ and not re.search('\d\d', answer) if ok: try: ast.parse(answer) except: ok = False return ok
def solve(digits):
"""\ >>> for digits in '3246 4788 1111 123456 1127'.split(): solve(list(digits))
Solution found: 2 + 3 * 6 + 4 '2 + 3 * 6 + 4' Solution found: ( 4 + 7 - 8 ) * 8 '( 4 + 7 - 8 ) * 8' No solution found for: 1 1 1 1 '!' Solution found: 1 + 2 + 3 * ( 4 + 5 ) - 6 '1 + 2 + 3 * ( 4 + 5 ) - 6' Solution found: ( 1 + 2 ) * ( 1 + 7 ) '( 1 + 2 ) * ( 1 + 7 )' >>> """ digilen = len(digits) # length of an exp without brackets exprlen = 2 * digilen - 1 # permute all the digits digiperm = sorted(set(permutations(digits))) # All the possible operator combinations opcomb = list(product('+-*/', repeat=digilen-1)) # All the bracket insertion points: brackets = ( [()] + [(x,y) for x in range(0, exprlen, 2) for y in range(x+4, exprlen+2, 2) if (x,y) != (0,exprlen+1)] + [(0, 3+1, 4+2, 7+3)] ) # double brackets case for d in digiperm: for ops in opcomb: ex = list(chain.from_iterable(zip_longest(d, ops, fillvalue=))) for b in brackets: exp = ex[::] for insertpoint, bracket in zip(b, '()'*(len(b)//2)): exp.insert(insertpoint, bracket) txt = .join(exp) try: num = eval(txt) except ZeroDivisionError: continue if num == 24: ans = ' '.join(exp).rstrip() print ("Solution found:",ans) return ans print ("No solution found for:", ' '.join(digits)) return '!'
def main():
digits = choose4() welcome(digits) trial = 0 answer = chk = ans = False while not (chk and ans == 24): trial +=1 answer = input("Expression %i: " % trial) chk = check(answer, digits) if answer == '?': solve(digits) answer = '!' if answer.lower() == 'q': break if answer == '!': digits = choose4() trial = 0 print ("\nNew digits:", ' '.join(digits)) continue if answer == '!!': digits = ask4() trial = 0 print ("\nNew digits:", ' '.join(digits)) continue if not chk: print ("The input '%s' was wonky!" % answer) else: ans = eval(answer) print (" = ", ans) if ans == 24: print ("Thats right!") print ("Thank you and goodbye")
main()</lang>
Sample Output
The 24 Game Player Given any four digits in the range 1 to 9, which may have repetitions, Using just the +, -, *, and / operators; and the possible use of brackets, (), show how to make an answer of 24. An answer of "q" will quit the game. An answer of "!" will generate a new set of four digits. An answer of "?" will compute an expression for the current digits. Otherwise you are repeatedly asked for an expression until it evaluates to 24 Note: you cannot form multiple digit numbers from the supplied digits, so an answer of 12+12 when given 1, 2, 2, and 1 would not be allowed. Your four digits: 6 7 9 5 Expression 1: ? Solution found: 6 - ( 5 - 7 ) * 9 Thank you and goodbye
R
<lang r>solve24 <- function(values) {
ops <- c("+", "-", "*", "/") if(!require(gtools)) stop("The package gtools is needed") digiperm <- unique(permutations(4, 4, values, set=FALSE)) opcomb <- permutations(4, 3, ops, repeats.allowed=TRUE) brackets <- matrix(c( #Should really find a more general solution "((", "", ")", "", ")", "", "(", "(", "", "", "))", "", "(", "", ")", "(", "", ")", "", "((", "", "", ")", ")", "", "(", "", "(", "", "))"), byrow=TRUE, ncol=6) nd <- nrow(digiperm) no <- nrow(opcomb) nb <- nrow(brackets) score <- NA found_soln <- FALSE ans <- "" pos <- 1L for(i in 1:nd) #may be possible to vectorise { d <- digiperm[i,] for(j in 1:no) { o <- opcomb[j,] for(k in 1:nb) { b <- brackets[k,] expr <- paste(c(b[1], d[1], o[1], b[2], d[2], b[3], o[2], b[4], d[3], b[5], o[3], d[4], b[6]), collapse=" ") #again, this needs generalising score <- try(eval(parse(text=expr))) if(!is.nan(score) && score == 24) #if there was a divide by zero error then score is NaN { found_soln <- TRUE ans <- expr break } pos <- pos + 1L } if(found_soln) break } if(found_soln) break } if(found_soln) { cat("A solution is:", ans, "\n") } else { cat("No solution could be found\n") } invisible(ans)
}</lang>
<lang r>solve24(c(6, 7, 9, 5)) # A solution is: 6 + ( 7 - 5 ) * 9 solve24(c(9, 9, 9, 9)) # No solution could be found</lang>
Ruby
<lang ruby>class TwentyFourGamePlayer
PRINT_FORMATS = [ '((%d %s %d) %s %d) %s %d', '(%d %s (%d %s %d)) %s %d', '(%d %s %d) %s (%d %s %d)', '%d %s ((%d %s %d) %s %d)', '%d %s (%d %s (%d %s %d))', ] OPERATORS = [:+, :-, :*, :/] @@objective = 24.0
def initialize(digits) @digits = digits @solutions = [] solve end
attr_reader :digits, :solutions
def solve digits.permutation.to_a.uniq.each do |a,b,c,d| OPERATORS.each do |op1| OPERATORS.each do |op2| OPERATORS.each do |op3| PRINT_FORMATS.each do |expr| # change to floats so it does floating-point division test = expr.gsub('%d', '%f') % [a, op1, b, op2, c, op3, d] if eval(test) == @@objective @solutions << expr % [a, op1, b, op2, c, op3, d] end end end end end end end
end
- validate user input
digits = ARGV.map do |arg|
begin Integer(arg) rescue ArgumentError raise "error: not an integer: '#{arg}'" end
end digits.size == 4 or raise "error: need 4 digits, only have #{digits.size}"
player = TwentyFourGamePlayer.new(digits) if player.solutions.empty?
puts "no solutions"
else
puts "found #{player.solutions.size} solutions, including #{player.solutions.first}" puts player.solutions.sort.join("\n")
end</lang>
Sample output:
$ ruby 24game.player.rb 1 1 1 1 no solutions $ ruby 24game.player.rb 1 1 2 7 found 8 solutions, including (1 + 2) * (1 + 7) (1 + 2) * (1 + 7) (1 + 2) * (7 + 1) (1 + 7) * (1 + 2) (1 + 7) * (2 + 1) (2 + 1) * (1 + 7) (2 + 1) * (7 + 1) (7 + 1) * (1 + 2) (7 + 1) * (2 + 1) $ ruby 24game.player.rb 2 3 8 9 found 12 solutions, including (8 / 2) * (9 - 3) ((9 - 3) * 8) / 2 ((9 - 3) / 2) * 8 (8 * (9 - 3)) / 2 (8 / 2) * (9 - 3) (9 - (2 * 3)) * 8 (9 - (3 * 2)) * 8 (9 - 3) * (8 / 2) (9 - 3) / (2 / 8) 8 * ((9 - 3) / 2) 8 * (9 - (2 * 3)) 8 * (9 - (3 * 2)) 8 / (2 / (9 - 3))
Scala
A non-interactive player.
<lang scala>def permute(l: List[Double]): List[List[Double]] = l match {
case Nil => List(Nil) case x :: xs => for { ys <- permute(xs) position <- 0 to ys.length (left, right) = ys splitAt position } yield left ::: (x :: right)
}
def computeAllOperations(l: List[Double]): List[(Double,String)] = l match {
case Nil => Nil case x :: Nil => List((x, "%1.0f" format x)) case x :: xs => for { (y, ops) <- computeAllOperations(xs) (z, op) <- if (y == 0) List((x*y, "*"), (x+y, "+"), (x-y, "(-")) else List((x*y, "*"), (x/y, "/"), (x+y, "+"), (x-y, "-")) } yield (z, "(%1.0f%s%s)" format (x,op,ops))
}
def hasSolution(l: List[Double]) = permute(l) flatMap computeAllOperations filter (_._1 == 24) map (_._2)</lang>
Example:
val problemsIterator = ( Iterator continually List.fill(4)(scala.util.Random.nextInt(9) + 1 toDouble) filter (!hasSolution(_).isEmpty) ) val solutionIterator = problemsIterator map hasSolution scala> solutionIterator.next res8: List[String] = List((3*(5-(3-6))), (3*(5-(3-6))), (3*(5+(6-3))), (3+(6+(3*5))), (3*(6-(3-5))), (3+(6+(5*3))), (3*( 6+(5-3))), (3*(5+(6-3))), (3+(6+(5*3))), (3*(6+(5-3))), (6+(3+(5*3))), (6*(5-(3/3))), (6*(5-(3/3))), (3+(6+(3*5))), (3*( 6-(3-5))), (6+(3+(3*5))), (6+(3+(3*5))), (6+(3+(5*3)))) scala> solutionIterator.next res9: List[String] = List((4-(5*(5-9))), (4-(5*(5-9))), (4+(5*(9-5))), (4+(5*(9-5))), (9-(5-(4*5))), (9-(5-(5*4))), (9-( 5-(4*5))), (9-(5-(5*4)))) scala> solutionIterator.next res10: List[String] = List((2*(4+(3+5))), (2*(3+(4+5))), (2*(3+(5+4))), (4*(3-(2-5))), (4*(3+(5-2))), (2*(4+(5+3))), (2* (5+(4+3))), (2*(5+(3+4))), (4*(5-(2-3))), (4*(5+(3-2)))) scala> solutionIterator.next res11: List[String] = List((4*(5-(2-3))), (2*(4+(5+3))), (2*(5+(4+3))), (2*(5+(3+4))), (2*(4+(3+5))), (2*(3+(4+5))), (2* (3+(5+4))), (4*(5+(3-2))), (4*(3+(5-2))), (4*(3-(2-5))))
Tcl
This is a complete Tcl script, intended to be invoked from the command line.
<lang tcl>package require struct::list
- Encoding the various expression trees that are possible
set patterns {
{((A x B) y C) z D} {(A x (B y C)) z D} {(A x B) y (C z D)} {A x ((B y C) z D)} {A x (B y (C z D))}
}
- Encoding the various permutations of digits
set permutations [struct::list map [struct::list permutations {a b c d}] \
{apply {v {lassign $v a b c d; list A $a B $b C $c D $d}}}]
- The permitted operations
set operations {+ - * /}
- Given a list of four integers (precondition not checked!) return a list of
- solutions to the 24 game using those four integers.
proc find24GameSolutions {values} {
global operations patterns permutations set found {} # For each possible structure with numbers at the leaves... foreach pattern $patterns {
foreach permutation $permutations { set p [string map [subst { a [lindex $values 0].0 b [lindex $values 1].0 c [lindex $values 2].0 d [lindex $values 3].0 }] [string map $permutation $pattern]]
# For each possible structure with operators at the branches...
foreach x $operations { foreach y $operations { foreach z $operations { set e [string map [subst {x $x y $y z $z}] $p]
# Try to evaluate (div-zero is an issue!) and add it to # the result if it is 24 catch { if {[expr $e] == 24.0} { lappend found [string map {.0 {}} $e] } } } } } }
} return $found
}
- Wrap the solution finder into a player
proc print24GameSolutionFor {values} {
set found [lsort -unique [find24GameSolutions $values]] if {![llength $found]} {
puts "No solution possible"
} else {
puts "Total [llength $found] solutions (may include logical duplicates)"
puts "First solution: [lindex $found 0]" }
} print24GameSolutionFor $argv</lang> Demonstrating it in use:
bash$ tclsh8.4 24player.tcl 3 2 8 9 Total 12 solutions (may include logical duplicates) First solution: ((9 - 3) * 8) / 2 bash$ tclsh8.4 24player.tcl 1 1 2 7 Total 8 solutions (may include logical duplicates) First solution: (1 + 2) * (1 + 7) bash$ tclsh8.4 24player.tcl 1 1 1 1 No solution possible