制作24游戏解说员

Question

第24场比赛是一种纸牌游戏。每张卡片上都有四个插卡号。对于一个玩家来说，目标是使用加法，减法，乘法和除法最终得到24。

这个代码的目标高尔夫/拼图是写一个程序，为四个中间，将说明一个或多个解决方案可能使用这些数字。

进一步说明：

• 应用于输入任意四个内部数字(低于24，高于0)。如果没有解决方案，则将0 solutions显示为输出。
• 应该输出这组四个数字的解决方案总数以及所使用的公式。
  • 可以使用方括号() (而且通常很重要)来获得一个或多个解决方案。

• 应该只显示不同的解决方案。例如，当给定{1，1，4，4}时，它不应该显示交换1和4的情况。此外，如果有一个解决方案(a*b)*(c*d)，您也不应该输出(c*d)*(a*b)，例如。

例如:对于{9，6，3，2}，程序应该输出：

   (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

如果你能做一个遵循上述规则的工作程序，那就太好了。

如果你用尽可能少的代码来做这件事的话，你会得到更多的赞誉。

快乐密码拼图/高尔夫！

Answer 1

通宵通宵，大量的代码(C#不是最简洁的语言)和8，这是正确的8个计算解决方案。我可能会改变很多事情.这可能是错的，但我想我现在应该把它弄进去。

+-* 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.Add(i);
            });

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

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

    }
}

Answer 2

Java

它很长--我应该用Python或Haskell重写它--但我认为它是正确的。

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) {
      expressions.add(new ConstantExpression(numbers.iterator().next()));
      return expressions;
    }

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

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

    Set<Expression> result = new HashSet<Expression>();
    for (Collection<Expression> expressions : getCombinations(groupExpressionOptions)) {
      boolean containsAdditive = false, containsMultiplicative = false;
      for (Expression exp : expressions) {
        containsAdditive |= exp instanceof AdditiveExpression;
        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 (!containsAdditive)
          result.add(new AdditiveExpression(firstExpression, a, b));
        if (!containsMultiplicative)
          try {
            result.add(new MultiplicativeExpression(firstExpression, a, b));
          } 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))
        result.add(Util.concat(restCombination, first));
    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()) {
      result.add(new ArrayList<Collection<T>>());
      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)) {
        result.add(Util.concat(restGrouping, firstGroup));
      }
    }
    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)) {
      result.add(subcollection);
      result.add(Util.concat(subcollection, first));
    }
    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 {}

class AdditiveExpression extends AggregateExpression {
  final Expression firstOperand;
  final Collection<Expression> addOperands;
  final Collection<Expression> subOperands;

  AdditiveExpression(Expression firstOperand, Collection<Expression> addOperands,
                     Collection<Expression> subOperands) {
    this.firstOperand = firstOperand;
    this.addOperands = addOperands;
    this.subOperands = subOperands;
  }

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

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

  @Override
  public String toString() {
    StringBuilder sb = new StringBuilder(firstOperand.toString());
    for (Expression exp : addOperands)
      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() {
    StringBuilder sb = new StringBuilder(maybeAddParens(firstOperand));
    for (Expression exp : mulOperands)
      sb.append('*').append(maybeAddParens(exp));
    for (Expression exp : divOperands)
      sb.append('/').append(maybeAddParens(exp));
    return sb.toString();
  }

  static String maybeAddParens(Expression exp) {
    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);
    result.add(x);
    return result;
  }
}

与大卫的代码一样，我的代码为{9, 6, 3, 2}提供了9种解决方案：

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

我还没有彻底阅读24theory.com页面，但是将(3-9)*(2-6)和(9-3)*(6-2)区分开来似乎是合理的，不是吗？

Answer 3

R

我肯定有一个更短的方法来写这个，加上我硬编码了可能的括号，但它是有效的！

# 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]