Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Count Quoridor wall positions
import java.math.BigInteger;
import java.util.*;
public class QuoridorCounter {
public static void main(String[] args) {
List<String> rows = new ArrayList<String>();
char[] chs = new char[8];
for (int i = 0; i < 6561 /* 3^8 */; i++) {
int r = i;
for (int j = 0; j < 8; j++) {
chs[j] = "HV ".charAt(r % 3);
r /= 3;
}
String row = new String(chs);
if (row.indexOf("HH") == -1) rows.add(row);
}
// Initialise: first row
BigInteger[][] counts = new BigInteger[rows.size()][21];
for (int i = 0; i < counts.length; i++) {
for (int j = 0; j < counts[i].length; j++) {
counts[i][j] = BigInteger.ZERO;
}
int k = 0;
for (char ch : rows.get(i).toCharArray()) if (ch != ' ') k++;
counts[i][k] = BigInteger.ONE;
}
// Subsequent rows.
for (int step = 0; step < 7; step++) {
BigInteger[][] nc = new BigInteger[rows.size()][21];
for (int i = 0; i < nc.length; i++) {
for (int j = 0; j < nc[i].length; j++) {
nc[i][j] = BigInteger.ZERO;
}
}
for (int row1 = 0; row1 < rows.size(); row1++) {
for (int row2 = 0; row2 < rows.size(); row2++) {
boolean clash = false;
for (int i = 0; i < 8; i++) {
if (rows.get(row1).charAt(i) == 'V' && rows.get(row2).charAt(i) == 'V') clash = true;
}
if (clash) continue;
// row1 can be followed by row2.
int delta = 0;
for (char ch : rows.get(row2).toCharArray()) if (ch != ' ') delta++;
for (int wallCount = 0; wallCount + delta < 21; wallCount++) {
nc[row2][wallCount + delta] = nc[row2][wallCount + delta].add(counts[row1][wallCount]);
}
}
}
counts = nc;
}
// Final count
BigInteger total = BigInteger.ZERO;
for (BigInteger[] byRow : counts) {
for (BigInteger val : byRow) total = total.add(val);
}
System.out.println(total);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.