Skip to content

@joriki /Question216503.java
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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<Long,Boolean> valueMap = new HashMap<Long,Boolean> ();
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<int []> list = (List<int []>) 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<int []>) lists [0])
for (int [] p1 : (List<int []>) 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));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.