24点游戏解法

本文提供了 24 点游戏的解法，不只包括是否满足 24 点规则。

限首先官方给的案例是不全的，先上一段可以 100% 通过的 bug：

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] nums = Arrays.stream(in.nextLine().split(" ")).mapToInt(
                                 Integer::parseInt).toArray();

        System.out.println(solve24(nums, 24, 15));
    }

        // selected:二进制去重，15 即为 1111
    public static boolean solve24(int[] nums, double target, int selected) {
        if (selected == 0) {
            return target == 0.00d;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (!checkI(i, selected)) {
                continue;
            }
            int newSelected = setI(i, selected);
            int select = nums[i];
            boolean result = false;
            result |= solve24(nums, target + select, newSelected);
            result |= solve24(nums, target - select, newSelected);
            result |= solve24(nums, target * select, newSelected);
            result |= solve24(nums, target / select, newSelected);
            if (result) {
                return true;
            }
        }
        return false;
    }

        // 校验 i 为是否为1
    public static boolean checkI(int i, int selected) {
        return ((selected >> i) & 1) == 1;
    }

        // 第 i 为置为0
    public static int setI(int i, int selected) {
        int c = ~(1 << i);
        return selected & c;
    }

上述代码的核心思想为：

既然数字可以组合得到24点，那么用 24 做逆向运算，如果最终结果为0，则表示满足 24 点规则。

而问题出在：

忽略了括号相关的组合情况，例如：1 9 1 2，显然应该是 （9-1）*(1+2),此方案不能解答，而官网给的用例却全部通过了（手动狗头～～）

具体解法可以参照 leetcode 679 。

实不相瞒，代码写完就去玩 24 点游戏了，有的题解不出来，很是头疼，索性写了个解法：

    private static final double TARGET=24;
    /**
     *
     * @param nums
     * @param formula   list 存储表达式子项，之所有选用 List<String> 是为了兼容数字大于9的情况
     * @param selected  记录选择标志位
     * @param nashorn
     * @return
     */
    public boolean dfs(int[] nums, List<String> formula, int selected, ScriptEngine nashorn) {
        if (selected == 0) {
            if (formula.size() < 7) {
                return false;
            }
            // todo test
//            System.out.println("complete formula: " + formula);
            String f = found24(formula, nashorn);
            boolean b = !f.isEmpty();
            if (b) {
                System.out.println(f);
            }
            return b;
        }
        boolean ret = false;
        for (int i = 0; i < nums.length; ++i) {
            int select = nums[i];
            int newSelect = setI(i, selected);
            if (selected == 15) {//1111
                formula.add(String.valueOf(select));
                if (!(ret |= dfs(nums, formula, newSelect, nashorn))) {
                    formula.remove(formula.size() - 1);
                    continue;
                }else{
                    return true;
                }
            }
            if (!checkI(i, selected)) {
                continue;
            }
            // addition
            formula.add("+");
            formula.add(String.valueOf(select));
            ret |= dfs(nums, formula, newSelect, nashorn);
            if (!ret) {
                formula.remove(formula.size() - 1);
                formula.remove(formula.size() - 1);
            } else {
                return true;
            }
            // subtraction
            formula.add("-");
            formula.add(String.valueOf(select));
            ret |= dfs(nums, formula, newSelect, nashorn);
            if (!ret) {
                formula.remove(formula.size() - 1);
                formula.remove(formula.size() - 1);
            } else {
                return true;
            }
            // multiplication
            formula.add("*");
            formula.add(String.valueOf(select));
            ret |= dfs(nums, formula, newSelect, nashorn);
            if (!ret) {
                formula.remove(formula.size() - 1);
                formula.remove(formula.size() - 1);
            } else {
                return true;
            }
            // division
            formula.add("/");
            formula.add(String.valueOf(select));
            ret |= dfs(nums, formula, newSelect, nashorn);
            if (!ret) {
                formula.remove(formula.size() - 1);
                formula.remove(formula.size() - 1);
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * 校验（从右到左）第 i 位是否为1
     * @param i
     * @param selected
     * @return
     */
    public boolean checkI(int i, int selected) {
        return ((selected >> i) & 1) == 1;
    }

    /**
     * 从右到左 第 i 位置为0
     * @param i
     * @param selected
     * @return
     */
    public int setI(int i, int selected) {
        int c = ~(1 << i);
        return selected & c;
    }

    /**
     * 枚举各种括号，找出带括号计算后可以得到 24 点的表达式
     * @param formula   包含表达式符号的集合
     * @param nashorn
     * @return          可得 24 点的表达式
     */
    public String found24(List<String> formula, ScriptEngine nashorn) {
        boolean ret = checkValue(calc(formula, nashorn) ,TARGET);
        if (ret) {
            return buildFormula(formula, null);
        }
        ArrayList<String> tempFormu = new ArrayList<>();
        // (AB)CD A(BC)D AB(CD)
        for (int i = 0; i < 3; ++i) {
            int end = 3 + i * 2;
            int start = end - 3;
            // 拼接表达式，一下类似，不重复注释
            tempFormu.addAll(formula.subList(0, start));
            tempFormu.add("("+String.valueOf(calc(formula.subList(start, end), nashorn)) + ")");
            tempFormu.addAll(formula.subList(end, 7));

            ret = checkValue(calc(tempFormu,nashorn),TARGET);
            if (ret) {
                return buildFormula(formula, Arrays.asList(Arrays.asList(start, end)));
            }
            tempFormu.clear();
        }
        // (AB)(CD)
        tempFormu.add("("+String.valueOf(calc(formula.subList(0, 3), nashorn)) + ")");
        tempFormu.addAll(formula.subList(3, 4));
        tempFormu.add("("+String.valueOf(calc(formula.subList(4, 7), nashorn))+")");
        ret = checkValue(calc(tempFormu,nashorn),TARGET);

        tempFormu.clear();
        if (ret) {
            return buildFormula(formula, Arrays.asList(Arrays.asList(0, 3), Arrays.asList(4, 7)));
        }
        // (ABC)D A(BCD)
        for (int i = 0; i < 2; ++i) {
            int end = 5 + i * 2;
            int start = end - 5;
            tempFormu.addAll(formula.subList(0, start));
            tempFormu.add("("+String.valueOf(calc(formula.subList(start, end), nashorn))+")");
            tempFormu.addAll(formula.subList(end, 7));
            ret = checkValue(calc(tempFormu,nashorn),TARGET);
            tempFormu.clear();
            if (ret) {
                return buildFormula(formula, Arrays.asList(Arrays.asList(start, end)));
            }
        }
        return "";
    }

    /**
     * 校验值 误差 < 1e-6
     * @param value
     * @param target
     * @return
     */
    public boolean checkValue(double value, double target){
        return Math.abs(target-value)<1e-6;
    }

    /**
     * 构建公式的字符串表达式（含有符号）
     * @param formulas
     * @param idxes     插入括号的下标（两层为了兼容双括号 (AB)(CD)）
     * @return
     */
    public String buildFormula(List<String> formulas, List<List<Integer>> idxes) {
        if (idxes == null) {
            return formulas.stream().collect(Collectors.joining());
        }
        StringBuilder formula = new StringBuilder();

        List<Integer> ids = idxes.get(0);
        if (idxes.size() == 1) {
            List<String> l1 = formulas.subList(0, ids.get(0));
            List<String> l2 = formulas.subList(ids.get(0), ids.get(1));
            List<String> l3 = formulas.subList(ids.get(1), 7);
            formula.append(l1.stream().collect(Collectors.joining()));
            formula.append("(" + l2.stream().collect(Collectors.joining()) + ")");
            formula.append(l3.stream().collect(Collectors.joining()));
        } else {//双括号只有一种可能
            List<String> l1 = formulas.subList(ids.get(0), ids.get(1));
            List<String> l2 = formulas.subList(idxes.get(1).get(0), idxes.get(1).get(1));
            formula.append("(" + l1.stream().collect(Collectors.joining()) + ")");
            formula.append(formulas.get(3));
            formula.append("(" + l2.stream().collect(Collectors.joining()) + ")");
        }
        return formula.toString();
    }

    public double calc(List<String> formula0, ScriptEngine nashorn) {
        try {
            String formula = formula0.stream().collect(Collectors.joining());
            // todo Test
//            System.out.println("calculating : " + formula);
            Object result = nashorn.eval(formula);
            if (result instanceof Integer) {
                return (Integer) result;
            }
            if (result instanceof Double) {
                double d = (Double) result;
                return d;
            }
            return 0;
        } catch (ScriptException e) {
            return 0;
        }
    }

靠着上述代码，总算通关了 24 游戏 160+32 个关卡，姑且一乐，需者自取

=======================补充==========================

关于24点游戏详细完整解法，可以参考这篇博客：https://blog.csdn.net/weixin_41346635/article/details/134467657