// For information about Teeko, visit // // http://en.wikipedia.org/wiki/Teeko // // This version starts with all 8 pieces on the board (not standard) // // To get enough memory, type: java -mx200m Teeko import java.io.*; // import java.util.*; class Move { int x1, y1, x2, y2, z1; Move prev = null; } public class Teeko { static int[][][] u; static int[][][][] s; static int[] v, p; static int[][] q, t, w, y; static byte[][] x; static char[] piece, letter; static String[] choice; static Move mv, mv2; public static String lesTekst() { String s = null; BufferedReader inn= new BufferedReader(new InputStreamReader (System.in)); try { s = inn.readLine(); } catch(IOException e){} return s;} public static int lesInt() { int tall = 0; String s = null; boolean done = false; do { s = lesTekst(); try { tall = Integer.parseInt(s); done = true; } catch(NumberFormatException e) { System.out.print("Illegal format! Enter an integer: "); System.out.flush();}} while(!done); return tall;} public static void main(String args[]) { int a, b, c, d, e, f, g, h, i, j, k, l, m, c1, f1, g1, h1, h2, h3, h4, b1; s = new int[25][25][25][25]; t = new int[12650][5]; u = new int[12650][5][5]; v = new int[12650]; w = new int[5][5]; x = new byte[12650][12650]; y = new int[34][6]; p = new int[34]; q = new int[25][8]; piece = new char[3]; letter = new char[5]; choice = new String[34]; String stripe = "\n +---+---+---+---+---+"; for (a = 0; a < 25; a++) { b = a % 5; c = a / 5; q[a][0] = a; q[a][1] = (4 - b) + 5 * c; q[a][2] = b + 5 * (4 - c); q[a][3] = (4 - b) + 5 * (4 - c); q[a][4] = c + 5 * b; q[a][5] = (4 - c) + 5 * b; q[a][6] = c + 5 * (4 - b); q[a][7] = (4 - c) + 5 * (4 - b); } System.out.println("\nTeeko oracle by J K Haugland"); System.out.println(""); do { System.out.print("Enter 0 for standard Teeko or 1 for Teeko-58: "); b1 = lesInt(); } while (b1 < 0 || b1 > 1); System.out.println("\nCounting positions..."); d = -1; for (a = 0; a < 22; a++) for (b = a + 1; b < 23; b++) for (c = b + 1; c < 24; c++) for (g = c + 1; g < 25; g++) { d++; for (e = 0; e < 5; e++) for (f = 0; f < 5; f++) u[d][e][f] = 0; u[d][a % 5][a / 5] = 1; u[d][b % 5][b / 5] = 1; u[d][c % 5][c / 5] = 1; u[d][g % 5][g / 5] = 1; v[d] = 0; if (a + 5 == b && b + 5 == c && c + 5 == g) v[d] = 1; if (a + 3 == g && a % 5 < 2) v[d] = 1; if (a == 0 || a == 1 || a == 5 || a == 6) if (a + 6 == b && b + 6 == c && c + 6 == g) v[d] = 1; if (a == 3 || a == 4 || a == 8 || a == 9) if (a + 4 == b && b + 4 == c && c + 4 == g) v[d] = 1; if (a / 5 == b / 5) { k = b - a; if (k == 1 || b1 == 1) if (a + 5 * k == c && b + 5 * k == g) v[d] = 1; } s[a][b][c][g] = d; s[a][b][g][c] = d; s[a][c][b][g] = d; s[a][c][g][b] = d; s[a][g][b][c] = d; s[a][g][c][b] = d; s[b][a][c][g] = d; s[b][a][g][c] = d; s[b][c][a][g] = d; s[b][c][g][a] = d; s[b][g][a][c] = d; s[b][g][c][a] = d; s[c][b][a][g] = d; s[c][b][g][a] = d; s[c][a][b][g] = d; s[c][a][g][b] = d; s[c][g][b][a] = d; s[c][g][a][b] = d; s[g][b][c][a] = d; s[g][b][a][c] = d; s[g][c][b][a] = d; s[g][c][a][b] = d; s[g][a][b][c] = d; s[g][a][c][b] = d; t[d][0] = a; t[d][1] = b; t[d][2] = c; t[d][3] = g; t[d][4] = 2; } for (a = 0; a < 12650; a++) for (b = 1; b < 8; b++) { if (t[a][4] == 1) t[a][4] = 2; c = 0; while (c < 25 && t[a][4] == 2) { if (u[a][c % 5][c / 5] != u[a][q[c][b] % 5][q[c][b] / 5]) { if (u[a][c % 5][c / 5] == 1) t[a][4] = 1; else t[a][4] = 0; } c++; } if (t[a][4] == 2) t[a][4] = 1; } j = 0; for (a = 0; a < 12650; a++) for (b = 0; b < 12650; b++) { x[a][b] = 100; // default value if (v[b] == 1) x[a][b] = 0; // finished game - 0 moves left if (v[a] == 1) x[a][b] = 110; // default value for illegal positions if (u[a][t[b][0] % 5][t[b][0] / 5] == 1 || u[a][t[b][1] % 5][t[b][1] / 5] == 1 || u[a][t[b][2] % 5][t[b][2] / 5] == 1 || u[a][t[b][3] % 5][t[b][3] / 5] == 1) x[a][b] = 110; if (x[a][b] == 0) { j++; if (j % 100000 == 0) System.out.print("-"); } } System.out.println("0 "+j); c = 1; do { j = 0; for (a = 0; a < 12650; a++) if (t[a][4] == 1) for (b = 0; b < 12650; b++) { if (x[a][b] == 100) // legal and not already assigned { stop : { for (k = 0; k < 4; k++) { d = t[a][k] % 5; e = t[a][k] / 5; for (f = -1; f <= 1; f++) for (g = -1; g <= 1; g++) if (f * f + g * g > 0) if (d + f >= 0 && d + f < 5 && e + g >= 0 && e + g < 5) if (u[a][d + f][e + g] == 0 && u[b][d + f][e + g] == 0) { f1 = f; g1 = g; for (h = 0; h < 4; h++) p[h] = t[a][h]; p[k] = d + f1 + 5 * (e + g1); h = s[p[0]][p[1]][p[2]][p[3]]; if (c % 2 == 1) { if (x[b][h] == c - 1) { x[a][b] = (byte)c; break stop; } } else { if (x[b][h] < c) x[a][b] = (byte)c; else { x[a][b] = 100; break stop; } } } } } if (x[a][b] == c) { j++; if (j % 100000 == 0) System.out.print("-"); for (d = 1; d < 8; d++) { e = s[q[t[a][0]][d]][q[t[a][1]][d]][q[t[a][2]][d]][q[t[a][3]][d]]; f = s[q[t[b][0]][d]][q[t[b][1]][d]][q[t[b][2]][d]][q[t[b][3]][d]]; if (x[e][f] != c) { x[e][f] = (byte)c; j++; if (j % 100000 == 0) System.out.print("-"); } } } } } System.out.println(c+" "+j); c++; } while (j > 0); for (a = 0; a < 12650; a++) for (b = 0; b < 12650; b++) if (x[a][b] == 100) j++; System.out.println("\nNumber of draws: "+j); piece[0] = 'o'; piece[1] = ' '; piece[2] = 'x'; letter[0] = 'A'; letter[1] = 'B'; letter[2] = 'C'; letter[3] = 'D'; letter[4] = 'E'; System.out.println("\nPositions leading to maximum length perfect play:"); for (a = 0; a < 12650; a++) if (t[a][4] == 1) for (b = 0; b < 12650; b++) if (x[a][b] == c - 2) { System.out.print("x -"); for (d = 0; d < 4; d++) System.out.print(" "+letter[t[a][d] % 5]+(1+t[a][d] / 5)); System.out.print(" o -"); for (d = 0; d < 4; d++) System.out.print(" "+letter[t[b][d] % 5]+(1+t[b][d] / 5)); System.out.println(""); } a = s[1][9][15][23]; b = s[3][5][19][21]; for (c = 0; c < 5; c++) for (d = 0; d < 5; d++) w[c][d] = u[a][c][d] - u[b][c][d]; mv = new Move(); while (x[a][b] > 0) { System.out.println(stripe); for (d = 4; d >= 0; d--) { System.out.print((d+1)+"|"); for (c = 0; c < 5; c++) System.out.print(" "+piece[1+w[c][d]]+" |"); System.out.println(stripe); } System.out.println(" A B C D E\n"); j = 0; if (x[a][b] == 110) System.out.println("Illegal position"); else for (k = 0; k < 4; k++) { d = t[a][k] % 5; e = t[a][k] / 5; for (f = -1; f <= 1; f++) for (g = -1; g <= 1; g++) if (f * f + g * g > 0) if (d + f >= 0 && d + f < 5 && e + g >= 0 && e + g < 5) if (w[d + f][e + g] == 0) { f1 = f; g1 = g; for (h = 0; h < 4; h++) p[h] = t[a][h]; p[k] = d + f1 + 5 * (e + g1); h = s[p[0]][p[1]][p[2]][p[3]]; j++; choice[j] = ". "+letter[d]+(e+1)+" -> "+ letter[d+f1]+(e+g1+1)+" : "; if (x[b][h] == 100) choice[j] += "Draw"; else { if (x[b][h] % 2 == 0) choice[j] += "Win"; else choice[j] += "Loss"; if (x[b][h] > 0) choice[j] += " in "+ (x[b][h]+1)+" moves"; } y[j][0] = d; y[j][1] = e; y[j][2] = d+f1; y[j][3] = e+g1; y[j][4] = h; y[j][5] = (int)x[b][h]; if (y[j][5] % 2 == 0) y[j][5] = y[j][5] - 100; else y[j][5] = 100 - y[j][5]; } } for (c = 1; c <= j; c++) p[c] = c; for (c = 1; c < j; c++) for (d = c + 1; d <= j; d++) if (y[p[c]][5] > y[p[d]][5]) { e = p[c]; p[c] = p[d]; p[d] = e; } for (c = 1; c <= j; c++) System.out.println(c+choice[p[c]]); if (mv.prev != null) System.out.println("77. Retract last move"); System.out.println("88. Back to start"); System.out.println("99. Enter new position"); do { System.out.print("Enter alternative: "); d = lesInt(); } while (d != 99 && d != 88 && (d < 1 || d > j) && (d != 77 || mv.prev == null)); if (d == 77) { b = a; a = mv.z1; for (c = 0; c < 5; c++) for (d = 0; d < 5; d++) w[c][d] = -w[c][d]; piece[1] = piece[0]; piece[0] = piece[2]; piece[2] = piece[1]; piece[1] = ' '; w[mv.x1][mv.y1] = 1; w[mv.x2][mv.y2] = 0; mv = mv.prev; } else if (d == 88) { a = s[1][9][15][23]; b = s[3][5][19][21]; for (c = 0; c < 5; c++) for (d = 0; d < 5; d++) w[c][d] = u[a][c][d] - u[b][c][d]; piece[0] = 'o'; piece[1] = ' '; piece[2] = 'x'; mv = new Move(); } else if (d == 99) { do { System.out.println("Enter one five-digit number for each row"); System.out.println("0 = blank; 1 = 'x' (plays first); 2 = 'o'"); for (e = 0; e < 5; e++) for (f = 0; f < 5; f++) w[e][f] = 0; for (e = 0; e < 5; e++) { f = lesInt(); w[0][4 - e] = f / 10000; w[1][4 - e] = (f / 1000) % 10; w[2][4 - e] = (f / 100) % 10; w[3][4 - e] = (f / 10) % 10; w[4][4 - e] = f % 10; for (f = 0; f < 5; f++) if (w[f][4 - e] == 2) w[f][4 - e] = -1; } h1 = 0; h2 = 0; h3 = 0; for (e = 0; e < 5; e++) for (f = 0; f < 5; f++) { if (w[e][f] == 0) h1++; if (w[e][f] == 1) h2++; if (w[e][f] == -1) h3++; } if (h1 != 17) System.out.println ("Error: "+h1+" blanks (should be 17)"); if (h2 != 4) System.out.println ("Error: "+h2+" x's (should be 4)"); if (h3 != 4) System.out.println ("Error: "+h3+" o's (should be 4)"); } while (h1 != 17 || h2 != 4 || h3 != 4); h1 = 0; while (w[h1 % 5][h1 / 5] <= 0) h1++; h2 = h1 + 1; while (w[h2 % 5][h2 / 5] <= 0) h2++; h3 = h2 + 1; while (w[h3 % 5][h3 / 5] <= 0) h3++; h4 = h3 + 1; while (w[h4 % 5][h4 / 5] <= 0) h4++; a = s[h1][h2][h3][h4]; h1 = 0; while (w[h1 % 5][h1 / 5] >= 0) h1++; h2 = h1 + 1; while (w[h2 % 5][h2 / 5] >= 0) h2++; h3 = h2 + 1; while (w[h3 % 5][h3 / 5] >= 0) h3++; h4 = h3 + 1; while (w[h4 % 5][h4 / 5] >= 0) h4++; b = s[h1][h2][h3][h4]; piece[0] = 'o'; piece[1] = ' '; piece[2] = 'x'; mv = new Move(); } else { c = p[d]; mv2 = new Move(); mv2 = mv; mv = new Move(); mv.prev = mv2; mv.x1 = y[c][0]; mv.y1 = y[c][1]; mv.x2 = y[c][2]; mv.y2 = y[c][3]; mv.z1 = a; a = b; b = y[c][4]; w[y[c][0]][y[c][1]] = 0; w[y[c][2]][y[c][3]] = 1; for (c = 0; c < 5; c++) for (d = 0; d < 5; d++) w[c][d] = -w[c][d]; piece[1] = piece[0]; piece[0] = piece[2]; piece[2] = piece[1]; piece[1] = ' '; } } System.out.println(stripe); for (d = 4; d >= 0; d--) { System.out.print((d+1)+"|"); for (c = 0; c < 5; c++) System.out.print(" "+piece[1+w[c][d]]+" |"); System.out.println(stripe); } System.out.println(" A B C D E\n\n G A M E O V E R\n"); } }