# Make a 24 Game Solver

The 24 Game is a card game. On each cards are four interger numbers. For a player, the goal is to use Addition, Subtraction, Multiplication and Division to end up with 24.

The goal of this code golf/puzzle is to write a program that, for four intergers, will state the one or multiple solutions possible with those numbers.

Further notes:

• Should work for an input of any four interger numbers (below 24, above 0). If there is no solution, display 0 solutions as output.
• Should output the total number of solutions for this set of four numbers as well as the formulas used.
• Brackets () can be used (and are often important) to get one or multiple solutions.
• Should only display distinct solutions. For instance, when given {1, 1, 4, 4}, it should not display the cases where the ones and the fours are swapped. Also, if have a solution (a*b)*(c*d), you should not output (c*d)*(a*b) as well, for instance.

An example: For {9, 6, 3, 2}, the program should output:

   (9-3-2)×6
(6+2)×9/3
6×2+9+3
(9-3)×(6-2)
(3-2/6)×9
9×6/2-3
9×3-6/2
(9+6-3)×2
8 solutions


Kudos if you can make a working program that follows the rules outlined above.

Even more kudos if you do this in as little code as possible.

Happy Code Puzzling/Golfing!

• This seems more appropriate as a programming challenge rather than a code-golf. – DavidC Nov 10 '13 at 3:06
• "display a graceful error message" goes against the spirit of code golf. You should specify one or make it not count against the code length – John Dvorak Nov 10 '13 at 5:23
• @JanDvorak Hmm... you are right. I've changed it to outputting '0 solutions' if there are none – Qqwy Nov 10 '13 at 9:07
• @DavidCarraher: All right. I changed the 'victory condition' slightly. You are right, this is quite a difficult challenge so every working program should be treated as a winner. – Qqwy Nov 10 '13 at 10:27
• I am the owner of 24theory and I really appreciate your interest in the game and particularly the solver. When I wrote up the rules in this page, I had one thing in mind. That is to give "real" unique solutions in the most "concise" way. Now how to define "real" and "concise" is up to debate. But in my opinion, switching around orders a + b vs b + a, add "-" signs, like a * b vs (-a) * (-b) are obviously redundant. Applying that principal to {9, 6, 3, 2}: (3-9)*(2-6) and (9-3)*(6-2) are NOT distinctive as it's the same thing as a*b vs (-a)*(-b). But other than – user10660 Nov 19 '13 at 15:58

## Ruby, 253 243 (incomplete, many duplicates, no error message)

g=gets.split.map(&:to_i).permutation(4)
s=[0,2,4,6]
%w[+ - * /].repeated_permutation(3).map{|x|g.map{|y|s.map{|b|s.select{|e|e>b}.map{|a|y.zip(x).flatten[0..6].join.insert(a+1,?)).insert(b,?()}}}}.flatten.each{|x|puts x if 24==eval(x)rescue''}


I got this so far, but there are a lot of duplicates. Example run:

c:\a\ruby>24
9 6 3 2
(9+3)+6*2
(9+3+6*2)
9+(3+6*2)
9+3+(6*2)
(9+3)+2*6
(9+3+2*6)
9+(3+2*6)
9+3+(2*6)
(3+9)+6*2
(3+9+6*2)
3+(9+6*2)
3+9+(6*2)
(3+9)+2*6
(3+9+2*6)
3+(9+2*6)
3+9+(2*6)
(9+6-3)*2
(6+9-3)*2
(9+6*2)+3
(9+6*2+3)
9+(6*2)+3
9+(6*2+3)
(9+2*6)+3
(9+2*6+3)
9+(2*6)+3
9+(2*6+3)
(3+6*2)+9
(3+6*2+9)
3+(6*2)+9
3+(6*2+9)
(3+2*6)+9
(3+2*6+9)
3+(2*6)+9
3+(2*6+9)
(6+2)*9/3
(2+6)*9/3
(9-3+6)*2
(6-3+9)*2
(9-3-2)*6
(9-2-3)*6
(6*2)+9+3
(6*2+9)+3
(6*2+9+3)
6*2+(9+3)
(6*2)+3+9
(6*2+3)+9
(6*2+3+9)
6*2+(3+9)
(2*6)+9+3
(2*6+9)+3
(2*6+9+3)
2*6+(9+3)
(2*6)+3+9
(2*6+3)+9
(2*6+3+9)
2*6+(3+9)
2*(9+6-3)
2*(6+9-3)
9*(6+2)/3
9*(2+6)/3
2*(9-3+6)
2*(6-3+9)
6*(9-3-2)
6*(9-2-3)
(9*3)-6/2
(9*3-6/2)
9*3-(6/2)
(3*9)-6/2
(3*9-6/2)
3*9-(6/2)
(9*6)/2-3
(9*6/2)-3
(9*6/2-3)
9*(6/2)-3
(6*9)/2-3
(6*9/2)-3
(6*9/2-3)
9/3*(6+2)
9/3*(2+6)
(6/2)*9-3
(6/2*9)-3
(6/2*9-3)


It will probably prove very difficult to eliminate duplicates. I am working on it, but I am afraid it will triple my code size, so I'm posting here first. aaaaaaahhhhh my brain hurts now, so I will continue working on this later :P

• I am amazed at how much you achieved with so little code. – DavidC Nov 10 '13 at 13:57
• Why the begin..end block? puts x if 24==eval(x)rescue'' is 10 characters shorter. – manatwork Nov 10 '13 at 19:28
• @manatwork Didn't know you could do that, thanks! – Doorknob Nov 10 '13 at 20:00
• @DavidCarraher permutations is extremely strong – Cruncher Nov 11 '13 at 16:07

# Mathematica 449 479 470

This was based on Zhe Hu's approach but I kept native Mathematica expressions, with numbers stored as strings, throughout. This had two advantages: (1) easy detection of duplicates and (2) high-quality formatting in output.

Because the "deep structure" of the output is kept in a canonical, sorted form, duplicates are easily detected even if the components were initially generated in slightly different ways. Thus commutativity is recognized for addition and multiplication but not imputed to subtraction, division. Further, associativity is implicitly acknowledged.

p[{a_, b_, c_, d_}] := Module[{h, v, q},
q[x_, y_] := If[y == 0, Null, x/y];
h[m_, m_, num_] := {Part[num, m]};
h[s_, f_, num_] := h[s, f, num] = Flatten[Table[Outer[F, {Plus, Subtract, Times, q}, h[s, i, num],
h[i + 1, f, num]], {i, s, f - 1}]];
v[o_, n1_, n2_] := o[n1, n2];
t = (Map[# &, Select[Map[h[1, 4, #] &, Permutations[{a, b, c, d}]] // Flatten, (# /. F -> v) == 24 &]]) //. {q -> Divide, n_Integer :>  ToString[n]};
Append[u = Union[t //. {F[o_, j_, k_] :> o[j, k]}] //. {Times[a1_String, b1_String] :> Row[{"(", a1, "\[Times]", b1, ")"}]}, ToString[Length[u]] <> " solutions"] // Column]


The FullForm of the following solution,

is

Plus[Times[-1,"3"],Times[Power["2",-1],Row[List["(","6","\[Times]","9",")"]]]]


the structure of which is most clearly rendered in its TreeForm.

TreeForm[%]


The only reason for using a Row for multiplication was to explicitly show the multiplication operator for the product of two known numbers: e.g. (6 x 9) instead of (6 9).

## Examples

The code produced 9 solutions, not 8, for the suggested test case.

p[{2, 3, 6, 9}]


p[{1, 13, 5, 9}]


p[{24, 13, 5, 9}]


• Mathematica doesn't have a builtin for this? – MilkyWay90 Mar 2 '19 at 17:18

An all nighter, a ton of code (C# isn't the most terse of languages) and 8, that's right 8 computed solutions. There's a bunch of things I'd probably change about this... and it's probably wrong but I figured I'd get it in now.

+-* 9,6,3,2 | 15,12,24 //(9+6-3)×2
*/- 9,6,2,3 | 54,27,24  //9×6/2-3
-+* 9,3,6,2 | 6,12,24
--* 9,3,2,6 | 6,4,24  //(9-3-2)×6
--* 9,2,3,6 | 7,4,24
-+* 6,3,9,2 | 3,12,24
*++ 6,2,9,3 | 12,21,24 //6×2+9+3
+*/ 6,2,9,3 | 8,72,24 //(6+2)×9/3
8 Solutions

(9-3)×(6-2)???
(3-2/6)×9???
9×3-6/2???

using System;
using System.Linq;
using System.Collections.Generic;

namespace ConsoleApplication10
{
class Program
{
static void Main(string[] args)
{
var n = new List<double> { 9, 6, 3, 2 };
var r = new List<double[]>();
P(n, new List<double>(), r);
var F = new Dictionary<String, Func<double, double, double>> { { "*", (x, y) => x * y }, { "/", (x, y) => x / y }, { "+", (x, y) => x + y }, { "-", (x, y) => x - y } };
var fa = (from a in F
from b in F
from c in F
select new[] { a, b, c }).ToList();
var ir = new List<Tuple<string, double[], double[]>>();
foreach (var p in r)
foreach (var f in fa)
{
var t = new double[4];
t[0] = p[0];
for (int i = 1; i < 4; i++)
t[i] = f[i - 1].Value(t[i - 1], p[i]);
if (Math.Abs(t.Last() - 24) < 0.01)
ir.Add(Tuple.Create(string.Join("", f.Select(_ => _.Key)), t.Skip(1).ToArray(), p));
}

var fr = new List<Tuple<string, double[], double[]>>();
ir.ForEach(i =>
{
if (fr.Any(_ => _.Item1.OrderBy(c=>c).SequenceEqual( i.Item1.OrderBy(c=>c))) &&
fr.Any(_ => _.Item2.OrderBy(c=>c).SequenceEqual( i.Item2.OrderBy(c=>c)))) return;
if (fr.Any(_ => _.Item1.Take(2).Concat(i.Item1.Take(2)).All(k=> "/*".Contains(k)) && _.Item3.Last() == i.Item3.Last() ) ||
fr.Any(_ => _.Item1.Skip(1).Concat(i.Item1.Skip(1)).All(k=> "/*".Contains(k)) && _.Item2.First() == i.Item2.First() ))
return;
});

fr.ForEach(x => Console.WriteLine(x.Item1 + " " + string.Join(",", x.Item3) + " | " + string.Join(",", x.Item2)));
Console.WriteLine(fr.Count + " Solutions");
}

static void P<T>(List<T> s, List<T> c, List<T[]> r)
{
else
for (int i = 0; i < s.Count; i++)
{
var cc = c.ToList();
var ss = s.ToList();
ss.RemoveAt(i);
P(ss, cc, r);
}
}

}
}

• Very interesting approach. I did some quick skimming of your answers and found a few duplicates though (-+* 6,3,9,2) and (-+* 9,3,6,2) are effectively the same. It looks like your solution could use some bracket handling logic as well. It currently won't find solutions like (3-2/6)*9. It appears to only find solutions that fit the following pattern: (((a.b).c).d) (where . is any operator). – Jon Senchyna Nov 12 '13 at 15:36
• Thanks for those notes, I see what you mean :) Apparently my (((a.b).c).d) guess wasn't as good as I had hoped :P If I get some time I might tweak this... – NPSF3000 Nov 13 '13 at 4:22

## Java

It's quite long - I ought to rewrite it in Python or Haskell - but I think it's correct.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class TwentyFour {
public static void main(String[] _) {
for (Expression exp : getExpressions(Arrays.asList(9, 6, 3, 2)))
if (exp.evaluate() == 24)
System.out.println(exp);
}

static Set<Expression> getExpressions(Collection<Integer> numbers) {
Set<Expression> expressions = new HashSet<Expression>();
if (numbers.size() == 1) {
return expressions;
}

for (Collection<Collection<Integer>> grouping : getGroupings(numbers))
if (grouping.size() > 1)
return expressions;
}

static Set<Expression> getExpressionsForGrouping(Collection<Collection<Integer>> groupedNumbers) {
Collection<Set<Expression>> groupExpressionOptions = new ArrayList<Set<Expression>>();
for (Collection<Integer> group : groupedNumbers)

Set<Expression> result = new HashSet<Expression>();
for (Collection<Expression> expressions : getCombinations(groupExpressionOptions)) {
boolean containsAdditive = false, containsMultiplicative = false;
for (Expression exp : expressions) {
containsMultiplicative |= exp instanceof MultiplicativeExpression;
}

Expression firstExpression = expressions.iterator().next();
Collection<Expression> restExpressions = new ArrayList<Expression>(expressions);
restExpressions.remove(firstExpression);

for (int i = 0; i < 1 << restExpressions.size(); ++i) {
Iterator<Expression> restExpressionsIter = restExpressions.iterator();
Collection<Expression> a = new ArrayList<Expression>(), b = new ArrayList<Expression>();
for (int j = 0; j < restExpressions.size(); ++j)
Arrays.asList(a, b).get(i >> j & 1).add(restExpressionsIter.next());
if (!containsMultiplicative)
try {
} catch (ArithmeticException e) {}
}
}
return result;
}

// Sample input/output:
// [ {a,b} ]               -> { [a], [b] }
// [ {a,b}, {a} ]          -> { [a,b], [a,a] }
// [ {a,b,c}, {d}, {e,f} ] -> { [a,d,e], [a,d,f], [b,d,e], [b,d,f], [c,d, e], [c,d,f] }
static <T> Set<Collection<T>> getCombinations(Collection<Set<T>> collectionOfOptions) {
if (collectionOfOptions.isEmpty())
return new HashSet<Collection<T>>() {{ add(new ArrayList<T>()); }};

Set<T> firstOptions = collectionOfOptions.iterator().next();
Collection<Set<T>> restCollectionOfOptions = new ArrayList<Set<T>>(collectionOfOptions);
restCollectionOfOptions.remove(firstOptions);

Set<Collection<T>> result = new HashSet<Collection<T>>();
for (T first : firstOptions)
for (Collection<T> restCombination : getCombinations(restCollectionOfOptions))
return result;
}

static <T> Set<Collection<Collection<T>>> getGroupings(final Collection<T> values) {
Set<Collection<Collection<T>>> result = new HashSet<Collection<Collection<T>>>();
if (values.isEmpty()) {
return result;
}

for (Collection<T> firstGroup : getSubcollections(values)) {
if (firstGroup.size() == 0)
continue;

Collection<T> rest = new ArrayList<T>(values);
for (T value : firstGroup)
rest.remove(value);

for (Collection<Collection<T>> restGrouping : getGroupings(rest)) {
}
}
return result;
}

static <T> Set<Collection<T>> getSubcollections(final Collection<T> values) {
if (values.isEmpty())
return new HashSet<Collection<T>>() {{ add(values); }};

T first = values.iterator().next();
Collection<T> rest = new ArrayList<T>(values);
rest.remove(first);

Set<Collection<T>> result = new HashSet<Collection<T>>();
for (Collection<T> subcollection : getSubcollections(rest)) {
}
return result;
}
}

abstract class Expression {
abstract double evaluate();

@Override
public abstract boolean equals(Object o);

@Override
public int hashCode() {
return new Double(evaluate()).hashCode();
}

@Override
public abstract String toString();
}

abstract class AggregateExpression extends Expression {}

final Expression firstOperand;
final Collection<Expression> subOperands;

Collection<Expression> subOperands) {
this.firstOperand = firstOperand;
this.subOperands = subOperands;
}

@Override
double evaluate() {
double result = firstOperand.evaluate();
result += exp.evaluate();
for (Expression exp : subOperands)
result -= exp.evaluate();
return result;
}

@Override
public boolean equals(Object o) {
&& Util.equalsIgnoreOrder(this.subOperands, that.subOperands);
}
return false;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder(firstOperand.toString());
sb.append('+').append(exp);
for (Expression exp : subOperands)
sb.append('-').append(exp);
return sb.toString();
}
}

class MultiplicativeExpression extends AggregateExpression {
final Expression firstOperand;
final Collection<Expression> mulOperands;
final Collection<Expression> divOperands;

MultiplicativeExpression(Expression firstOperand, Collection<Expression> mulOperands,
Collection<Expression> divOperands) {
this.firstOperand = firstOperand;
this.mulOperands = mulOperands;
this.divOperands = divOperands;
for (Expression exp : divOperands)
if (exp.evaluate() == 0.0)
throw new ArithmeticException();
}

@Override
double evaluate() {
double result = firstOperand.evaluate();
for (Expression exp : mulOperands)
result *= exp.evaluate();
for (Expression exp : divOperands)
result /= exp.evaluate();
return result;
}

@Override
public boolean equals(Object o) {
if (o instanceof MultiplicativeExpression) {
MultiplicativeExpression that = (MultiplicativeExpression) o;
return Util.equalsIgnoreOrder(Util.concat(this.mulOperands, this.firstOperand),
Util.concat(that.mulOperands, that.firstOperand))
&& Util.equalsIgnoreOrder(this.divOperands, that.divOperands);
}
return false;
}

@Override
public String toString() {
for (Expression exp : mulOperands)
for (Expression exp : divOperands)
return sb.toString();
}

return String.format(exp instanceof AdditiveExpression ? "(%s)" : "%s", exp);
}
}

class ConstantExpression extends Expression {
final int value;

ConstantExpression(int value) {
this.value = value;
}

@Override
double evaluate() {
return value;
}

@Override
public boolean equals(Object o) {
return o instanceof ConstantExpression && value == ((ConstantExpression) o).value;
}

@Override
public String toString() {
return Integer.toString(value);
}
}

class Util {
static <T> boolean equalsIgnoreOrder(Collection<T> a, Collection<T> b) {
Map<T, Integer> aCounts = new HashMap<T, Integer>(), bCounts = new HashMap<T, Integer>();
for (T value : a) aCounts.put(value, (aCounts.containsKey(value) ? aCounts.get(value) : 0) + 1);
for (T value : b) bCounts.put(value, (bCounts.containsKey(value) ? bCounts.get(value) : 0) + 1);
return aCounts.equals(bCounts);
}

static <T> Collection<T> concat(Collection<T> xs, final T x) {
List<T> result = new ArrayList<T>(xs);
return result;
}
}


Like David's, my code gives 9 solutions for {9, 6, 3, 2}:

3*9-6/2
(3-9)*(2-6)
(9-3)*(6-2)
9*6/2-3
(3-2/6)*9
3+6*2+9
6*(9-3-2)
(6+2)*9/3
(9+6-3)*2


I haven't read the 24theory.com page thoroughly, but it seems reasonable to call (3-9)*(2-6) and (9-3)*(6-2) distinct, doesn't it?

# R

I'm sure there's a shorter way to write this, plus I hard-coded the possible parenthesis, but it works!

# set up
library(combinat)
library(iterpc)
library(data.table)
numbers = c(9,6,3,2)
operators = c('+','-','*','/')

# set up formulas without parens
numbers_permu = do.call('rbind', permn(numbers))
operators_permu = getall(iterpc(table(operators), 3, replace=TRUE, order=TRUE))

for(i in seq(nrow(numbers_permu))) {
for(j in seq(nrow(operators_permu))) {
tmp = c(rbind(numbers_permu[i,], operators_permu[j,]))
if (i==1 & j==1) formulas = data.table(t(tmp))
if (i>1 | j>1) formulas = rbind(formulas, data.table(t(tmp)))
}
}
formulas\$V8 = NULL # undo recycling

# add parens, repeating once for each possible parenthesis combo
setnames(formulas, names(formulas), c('V3', 'V4', 'V7', 'V8', 'V11', 'V12', 'V15'))
p1 =c(" ", " ", " ", " ", "(",  "(",  " ", " ", " ", " ", ")",  " ", " ", " ", " ", ")")
p2 =c(" ", " ", " ", " ", "(",  " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", ")")
p3 =c("(",  " ", " ", " ", "(",  " ", " ", " ", " ", " ", ")",  ")",  " ", " ", " ", " ")
p4 =c("(",  "(",  " ", " ", " ", " ", ")",  " ", " ", " ", ")",  " ", " ", " ", " ", " ")
p5 =c(" ", " ", " ", " ", " ", " ", " ", " ", " ", "(",  " ", " ", " ", " ", " ", ")")
p6 =c("(",  " ", " ", " ", " ", " ", ")",  " ", " ", " ", " ", " ", " ", " ", " ", " ")
p7 =c("(",  " ", " ", " ", " ", " ", " ", " ", " ", " ", ")",  " ", " ", " ", " ", " ")
p8 =c("(",  " ", " ", " ", " ", " ", ")",  " ", "(",  " ", " ", " ", " ", " ", ")",  " ")
p9 =c(" ", " ", " ", " ", "(",  " ", " ", " ", "(",  " ", " ", " ", " ", " ", ")",  ")")
p10=c(" ", " ", " ", " ", " ", "(",  " ", " ", " ", " ", ")",  " ", " ", " ", " ", " ")
p11=c(" ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ", " ")
parens_permu = t(data.table(p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11))

for(i in seq(nrow(formulas))) {
for(j in seq(nrow(parens_permu))) {
f = paste0(formulas[i,])
p = paste0(parens_permu[j,])
tmp = c(p[1] ,p[2] ,f[1], p[3] ,p[4], f[2],
p[5] ,p[6] ,f[3], p[7] ,p[8], f[4],
p[9] ,p[10],f[5], p[11],p[12],f[6],
p[13],p[14],f[7], p[15],p[16])
if (i==1 & j==1) full_formulas = data.table(t(tmp))
if (i>1 | j>1) full_formulas = rbind(full_formulas, data.table(t(tmp)))
}
}

# evaluate
for(i in seq(nrow(full_formulas))) {
equation = paste(full_formulas[i], collapse='')
solution = tryCatch(eval(parse(text=equation)), error = function(e) NA)
if (i==1) solutions = data.table(equation, solution)
if (i>1) solutions = rbind(solutions, data.table(equation, solution))
}
solutions[solution==24]