Skip to content

Instantly share code, notes, and snippets.

@joriki
Created February 1, 2023 03:05
Show Gist options
  • Save joriki/debb65dcad3a10ffd63111038acea601 to your computer and use it in GitHub Desktop.
Save joriki/debb65dcad3a10ffd63111038acea601 to your computer and use it in GitHub Desktop.
Maximize the score in a game where boxes are removed according to the sum of two dice; see https://math.stackexchange.com/questions/4629747.
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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment