24 game/Solve

24 game/Solve
You are encouraged to solve this task according to the task description, using any language you may know.

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

C.F: Arithmetic Evaluator

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

Translation of: Tcl

<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

1. 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># 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))}

}

1. Encoding the various permutations of digits

set permutations {

   {A a B b C c D d}
   {A a B b C d D c}
   {A a B c C b D d}
   {A a B c C d D b}
   {A a B d C c D b}
   {A a B d C b D c}
   {A b B a C c D d}
   {A b B a C d D c}
   {A b B c C a D d}
   {A b B c C d D a}
   {A b B d C c D a}
   {A b B d C a D c}
   {A c B b C a D d}
   {A c B b C d D a}
   {A c B a C b D d}
   {A c B a C d D b}
   {A c B d C a D b}
   {A c B d C b D a}
   {A d B b C c D a}
   {A d B b C a D c}
   {A d B c C b D a}
   {A d B c C a D b}
   {A d B a C c D b}
   {A d B a C b D c}

}

1. Given a list of four integers (precondition not checked!) return a list of
2. solutions to the 24 game using those four integers.

proc find24GameSolutions {values} {

   global 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 {+ - * /} { foreach y {+ - * /} { foreach z {+ - * /} { set e [string map [subst {x $x y $y z $z}] $p]

                       # Try to evaluate (div-zero is an issue!) and print if it is 24

catch { if {[expr $e] == 24.0} { lappend found [string map {.0 {}} $e] } } } } } }

   }
   return $found

}

1. Wrap the solution finder into a player

proc print24GameSolutionFor {values} {

   set found [find24GameSolutions $values]
   if {![llength $found]} {

puts "No solution possible"

   } else {

puts "Total [llength $found] solutions (may include duplicates)"

       puts "First solution: [lindex $found 0]"
   }

} print24GameSolutionFor $argv</lang> Demonstrating it in use:

bash$ tclsh8.4 24player.tcl 3 2 8 9
12 solutions total (may include duplicates)
First solution: ((9 - 3) * 8) / 2
bash$ tclsh8.4 24player.tcl 1 1 2 7
16 solutions total (may include duplicates)
First solution: (1 + 2) * (1 + 7)
bash$ tclsh8.4 24player.tcl 1 1 1 1
No solution possible