Instantly share code, notes, and snippets.

# joriki/Question216503.java Created Oct 26, 2012

What would you like to do?
Check whether Bob can force a zero pattern against Alice in a game of determinants; see
 import java.util.List; import java.util.ArrayList; import java.util.Map; import java.util.HashMap; public class Question216503 { final static int n = 5; final static int [] weights = {0,1,n+1}; static class State { int ntypes [] = {n*n,0,0}; byte [] [] matrix = new byte [n] [n]; int [] [] order = new int [2] [n]; int [] [] sums = new int [2] [n]; { for (int i = 0;i < n;i++) order [0] [i] = order [1] [i] = i; } public boolean isValid () { int diff = ntypes [1] - ntypes [2]; return diff == 1 || diff == 0; } public long toCode () { long code = 0; for (int i = 0;i < n;i++) for (int j = 0;j < n;j++) { code <<= 2; code += matrix [order [0] [i]] [order [1] [j]]; } return code; } public long toCode (int [] rows,int [] cols) { long code = 0; for (int i = 0;i < n;i++) for (int j = 0;j < n;j++) { code <<= 2; code += matrix [order [0] [rows [i]]] [order [1] [cols [j]]]; } return code; } public void fromCode (long code) { for (int i = 0,shift = 2 * (n * n - 1);i < n;i++) for (int j = 0;j < n;j++,shift -= 2) set (i,j,(int) ((code >> shift) & 3)); } public byte get (int i,int j) { return matrix [i] [j]; } public void set (int i,int j,int value) { ntypes [matrix [i] [j]]--; ntypes [value]++; int change = weights [value] - weights [matrix [i] [j]]; matrix [i] [j] = (byte) value; sums [0] [i] += change; sums [1] [j] += change; if (reordering) fix (i,j); } private int rank (int i,int dir) { for (int j = 0;j < n;j++) if (order [dir] [j] == i) return j; throw new Error (); } private int [] r = new int [2]; final static boolean testing = false; final static boolean reordering = true; private void fix (int i,int j) { r [0] = rank (i,0); r [1] = rank (j,1); for (int k = 0;k < 2;k++) { while (r [k] != 0 && sums [k] [order [k] [r [k]]] > sums [k] [order [k] [r [k] - 1]]) { int tmp = order [k] [r [k]]; order [k] [r [k]] = order [k] [r [k] - 1]; order [k] [r [k] - 1] = tmp; r [k]--; } while (r [k] != n - 1 && sums [k] [order [k] [r [k]]] < sums [k] [order [k] [r [k] + 1]]) { int tmp = order [k] [r [k]]; order [k] [r [k]] = order [k] [r [k] + 1]; order [k] [r [k] + 1] = tmp; r [k]++; } } if (testing) check (); } private void check () { for (int k = 0;k < 2;k++) { boolean [] done = new boolean [n]; for (int l = 0;l < n;l++) { if (done [order [k] [l]]) throw new Error (); done [order [k] [l]] = true; if (l != 0 && sums [k] [order [k] [l]] > sums [k] [order [k] [l - 1]]) throw new Error (); if (l != n - 1 && sums [k] [order [k] [l]] < sums [k] [order [k] [l + 1]]) throw new Error (); } } } public String toString () { StringBuilder builder = new StringBuilder (); builder.append ('\n'); for (int i = 0;i < n;i++) { for (int j = 0;j < n;j++) { if (j != 0) builder.append (' '); builder.append (get (i,j)); } builder.append ('\n'); } return builder.toString (); } } static Map valueMap = new HashMap (); static List [] lists = {new ArrayList (),new ArrayList ()}; static int [] [] permutations = Permutations.getPermutations (n); static boolean put (State state,boolean result) { if (valueMap.put (state.toCode (),result) != null) return true; for (int k = 0;k < 2;k++) { List list = (List) lists [k]; list.clear (); outer: for (int [] permutation : permutations) { for (int i = 0;i < n;i++) if (state.sums [k] [state.order [k] [i]] != state.sums [k] [state.order [k] [permutation [i]]]) continue outer; list.add (permutation); } } for (int [] p0 : (List) lists [0]) for (int [] p1 : (List) lists [1]) valueMap.put (state.toCode (p0,p1),result); return false; } static void add (State state) { add (state,new int [2]); } static void add (State state,int [] index) { if (state.isValid () && put (state,false)) return; int type = state.ntypes [1] > state.ntypes [2] ? 2 : 1; int k = type - 1; int was = index [k]; for (;index [k] < n * n;index [k]++) { int i = index [k] % n; int j = index [k] / n; if (state.get (i,j) == 0) { state.set (i,j,type); add (state,index); state.set (i,j,0); } } index [k] = was; } static boolean play (State state,boolean first) { Boolean known = valueMap.get (state.toCode ()); if (known != null) return known; boolean result = compute (state,first); put (state,result); return result; } static boolean compute (State state,boolean first) { if (state.ntypes [0] == 0) return true; for (int i = 0;i < n;i++) for (int j = 0;j < n;j++) if (state.get (i,j) == 0) { state.set (i,j,first ? 1 : 2); boolean result = play (state,!first); state.set (i,j,0); if (result == first) return first; } return !first; } public static void main (String [] args) { for (int k = 1;k <= n;k++) { State state = new State (); for (int i = 0;i < k;i++) for (int j = 0;j < n + 1 - k;j++) state.set (i,j,2); add (state); } State state = new State (); state.set (0,0,1); System.out.println ("value : " + play (state,false)); } }