Maximize the score in a game where boxes are removed according to the sum of two dice; see https://math.stackexchange.com/questions/4629747.

Question4629747.java

package info.joriki.math.stackexchange;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import info.joriki.math.algebra.BigRational;

public class Question4629747 {
    static Map<Integer,BigRational> sums = new HashMap<>();
    static Map<Integer,List<Integer>> options = new HashMap<>();
    static Map<Integer,BigRational> values = new HashMap<>();
    
    static BigRational getValue (int bits) {
        BigRational value = values.get(bits);
        if (value == null) {
            BigRational bitSum = sums.get(bits);
            value = BigRational.ZERO;
            for (int i = 1;i <= 6;i++)
                for (int j = 1;j <= 6;j++) {
                    int sum = i + j;
                    BigRational best = bitSum;
                    for (Integer option : options.get(sum))
                        if ((bits & option) == option) {
                            BigRational candidate = getValue(bits & ~option);
                            if (candidate.compareTo(best) < 0)
                                best = candidate;
                        }
                    value = BigRational.sum(value,best);
                }
            value = BigRational.product(value,new BigRational(1,36));
            values.put(bits,value);
        }
        return value;
    }
    
    static class Result implements Comparable<Result> {
        int bits;
        BigRational value;
        
        public Result (int bits,BigRational value) {
            this.bits = bits;
            this.value = value;
        }

        public int compareTo(Result r) {
            return value.compareTo (r.value);
        }

        public String toString () {
            return new StringBuilder(String.format("%9s",Integer.toBinaryString(bits)).replace(' ','0').replace('0','_').replace('1','☐')).reverse() + " : " + BigRational.sum(new BigRational (45), value.negate());
        }
    }
    
    public static void main(String [] args) {
        for (int bits = 0;bits < 1 << 9;bits++) {
            int sum = 0;
            for (int bit = 0;bit < 9;bit++)
                if ((bits & (1 << bit)) != 0)
                    sum += bit + 1;
            List<Integer> list = options.get(sum);
            if (list == null) {
                list = new ArrayList<>();
                options.put(sum,list);
            }
            list.add(bits);
            sums.put(bits,new BigRational (sum));
        }
        
        for (int sum = 0;sum <= 45;sum++) {
            List<Result> results = new ArrayList<>();
            for (int bits : options.get(sum))
                results.add(new Result(bits,getValue(bits)));
            results.sort(null);
            System.out.println(sum + " :");
            for (Result result : results)
                System.out.println("  " + result);
        }
        
        for (int bits = 0;bits < 1 << 9;bits++)
            getValue(bits);
    }
}