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