// For information about Breakthrough, visit // // http://en.wikipedia.org/wiki/Breakthrough_%28board_game%29 // // To get enough memory, type: // // java -mx280m Breakth55 // import java.io.*; // import java.util.*; class Move { int x11, x21, x31, x41, x51, x12, x22, x32, x42, x52, x13, x23, x33, x43, x53, x14, x24, x34, x44, x54, x15, x25, x35, x45, x55; Move prev = null; } public class Breakth55 { static byte[] x; static int[][] y, z; static char[] p3, letter; static int [] p1, p2, p4, p5, p6; 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 a00, a01, a02, a03, a04, a05, a06, a07, a08, a09, a10, a11, a12, a13, a14, a15, a16, a17, a18, a19, a20, a21, a22, a23, a24, b, c, d, e, f, g, i, j, k, l, h00, h01, h02, h03, h04, h05, h06, h07, h08, h09, h10, h11, h12, h13, h14, h15, h16, h17, h18, h19, h20, h21, h22, h23, h24, m, n, r, s; char q; x = new byte[254803968]; y = new int[6][6]; z = new int[6][6]; letter = new char[6]; p1 = new int[200]; p2 = new int[200]; p3 = new char[200]; p4 = new int[200]; p5 = new int[200]; p6 = new int[200]; String stripe = "\n +---+---+---+---+---+"; System.out.println("\nBreakthrough 5x5 oracle by J K Haugland"); System.out.println("\nCounting positions..."); c = 0; d = 0; for (m = 0; m < 254803968; m++) { a00 = m / 127401984; a01 = (m / 63700992) % 2; a02 = (m / 31850496) % 2; a03 = (m / 15925248) % 2; a04 = (m / 7962624) % 2; a05 = (m / 3981312) % 2; a06 = (m / 1990656) % 2; a07 = (m / 995328) % 2; a08 = (m / 497664) % 2; a09 = (m / 248832) % 2; a10 = (m / 82944) % 3; a11 = (m / 27648) % 3; a12 = (m / 9216) % 3; a13 = (m / 3072) % 3; a14 = (m / 1024) % 3; a15 = (m / 512) % 2; a16 = (m / 256) % 2; a17 = (m / 128) % 2; a18 = (m / 64) % 2; a19 = (m / 32) % 2; a20 = (m / 16) % 2; a21 = (m / 8) % 2; a22 = (m / 4) % 2; a23 = (m / 2) % 2; a24 = m % 2; b = 0; if (a10 == 1 && a20 + a22 == 0) b = 3; if (a10 == 1 && a15 + a21 == 0) b = 3; if (a11 == 1 && a21 == 0) b = 3; if (a11 == 1 && a16 + a20 + a22 == 0) b = 3; if (a12 == 1 && a20 + a22 == 0) b = 3; if (a12 == 1 && a17 + a21 + a23 == 0) b = 3; if (a12 == 1 && a22 + a24 == 0) b = 3; if (a13 == 1 && a23 == 0) b = 3; if (a13 == 1 && a18 + a22 + a24 == 0) b = 3; if (a14 == 1 && a22 + a24 == 0) b = 3; if (a14 == 1 && a19 + a23 == 0) b = 3; if (a10 != 1 && a11 != 1 && a12 != 1 && a13 != 1 && a14 != 1 && a00 + a01 + a02 + a03 + a04 + a05 + a06 + a07 + a08 + a09 == 0) b = 2; x[m] = (byte)b; if (b == 2) c++; if (b == 3) { d++; if (d % 1000000 == 0) System.out.print("-"); } } // System.out.println ("2 "+c); System.out.println ("3 "+d); c = 4; do { j = 0; for (m = 0; m < 254803968; m++) if (x[m] == 0) // legal and not already assigned { a00 = m / 127401984; a01 = (m / 63700992) % 2; a02 = (m / 31850496) % 2; a03 = (m / 15925248) % 2; a04 = (m / 7962624) % 2; a05 = (m / 3981312) % 2; a06 = (m / 1990656) % 2; a07 = (m / 995328) % 2; a08 = (m / 497664) % 2; a09 = (m / 248832) % 2; a10 = (m / 82944) % 3; a11 = (m / 27648) % 3; a12 = (m / 9216) % 3; a13 = (m / 3072) % 3; a14 = (m / 1024) % 3; a15 = (m / 512) % 2; a16 = (m / 256) % 2; a17 = (m / 128) % 2; a18 = (m / 64) % 2; a19 = (m / 32) % 2; a20 = (m / 16) % 2; a21 = (m / 8) % 2; a22 = (m / 4) % 2; a23 = (m / 2) % 2; a24 = m % 2; stop : { y[1][1] = a00; y[2][1] = a01; y[3][1] = a02; y[4][1] = a03; y[5][1] = a04; y[1][2] = a05; y[2][2] = a06; y[3][2] = a07; y[4][2] = a08; y[5][2] = a09; y[1][3] = a10; y[2][3] = a11; y[3][3] = a12; y[4][3] = a13; y[5][3] = a14; y[1][4] = a15; y[2][4] = a16; y[3][4] = a17; y[4][4] = a18; y[5][4] = a19; y[1][5] = a20; y[2][5] = a21; y[3][5] = a22; y[4][5] = a23; y[5][5] = a24; for (d = 1; d < 6; d++) for (e = 1; e < 4; e++) if (y[d][e] == 1) for (f = 1; f < 6; f++) if (d - f < 2 && f - d < 2) if (y[f][e + 1] == 0 || (d != f && y[f][e + 1] == 4 - e)) { for (k = 1; k < 6; k++) for (l = 1; l < 6; l++) z[k][l] = y[k][l]; z[d][e] = 0; z[f][e + 1] = 1; if (e < 3) { h00 = z[5][5]; h01 = z[4][5]; h02 = z[3][5]; h03 = z[2][5]; h04 = z[1][5]; h05 = z[5][4]; h06 = z[4][4]; h07 = z[3][4]; h08 = z[2][4]; h09 = z[1][4]; h10 = 3 - z[5][3]; h11 = 3 - z[4][3]; h12 = 3 - z[3][3]; h13 = 3 - z[2][3]; h14 = 3 - z[1][3]; h15 = z[5][2]; h16 = z[4][2]; h17 = z[3][2]; h18 = z[2][2]; h19 = z[1][2]; h20 = z[5][1]; h21 = z[4][1]; h22 = z[3][1]; h23 = z[2][1]; h24 = z[1][1]; h10 = h10 % 3; h11 = h11 % 3; h12 = h12 % 3; h13 = h13 % 3; h14 = h14 % 3; n = h04 + 2 * (h03 + 2 * (h02 + 2 * (h01 + 2 * h00))); n = h09 + 2 * (h08 + 2 * (h07 + 2 * (h06 + 2 * (h05 + 2 * n)))); n = h14 + 3 * (h13 + 3 * (h12 + 3 * (h11 + 3 * (h10 + 3 * n)))); n = h19 + 2 * (h18 + 2 * (h17 + 2 * (h16 + 2 * (h15 + 2 * n)))); n = h24 + 2 * (h23 + 2 * (h22 + 2 * (h21 + 2 * (h20 + 2 * n)))); i = x[n]; if (c % 2 == 1) { if (i == c - 1) { x[m] = (byte)c; break stop; } } else { if (i < c && i > 0) x[m] = (byte)c; else { x[m] = 0; break stop; } } } else { k = 0; for (l = 1; l < 6; l++) if (z[l][5] == 1 && (l - f == 1 || f - l == 1)) { h00 = z[1][1]; h01 = z[2][1]; h02 = z[3][1]; h03 = z[4][1]; h04 = z[5][1]; h05 = z[1][2]; h06 = z[2][2]; h07 = z[3][2]; h08 = z[4][2]; h09 = z[5][2]; h10 = z[1][3]; h11 = z[2][3]; h12 = z[3][3]; h13 = z[4][3]; h14 = z[5][3]; h15 = z[1][4]; h16 = z[2][4]; h17 = z[3][4]; h18 = z[4][4]; h19 = z[5][4]; h20 = z[1][5]; h21 = z[2][5]; h22 = z[3][5]; h23 = z[4][5]; h24 = z[5][5]; if (l == 1) h20 = 0; if (l == 2) h21 = 0; if (l == 3) h22 = 0; if (l == 4) h23 = 0; if (l == 5) h24 = 0; n = h04 + 2 * (h03 + 2 * (h02 + 2 * (h01 + 2 * h00))); n = h09 + 2 * (h08 + 2 * (h07 + 2 * (h06 + 2 * (h05 + 2 * n)))); n = h14 + 3 * (h13 + 3 * (h12 + 3 * (h11 + 3 * (h10 + 3 * n)))); n = h19 + 2 * (h18 + 2 * (h17 + 2 * (h16 + 2 * (h15 + 2 * n)))); n = h24 + 2 * (h23 + 2 * (h22 + 2 * (h21 + 2 * (h20 + 2 * n)))); i = x[n]; if (c % 2 == 1) { if (i % 2 == 0 || i == c) k = 1; } else { if (i % 2 == 0 && i > 0 && i < c) k = 1; } } if (c % 2 == 1) { if (k == 0) { x[m] = (byte)c; break stop; } } else { if (k == 1) x[m] = (byte)c; else { x[m] = 0; break stop; } } } } } if (x[m] == c) { j++; if (j % 1000000 == 0) System.out.print("-"); n = a00 + 2 * (a01 + 2 * (a02 + 2 * (a03 + 2 * a04))); n = a05 + 2 * (a06 + 2 * (a07 + 2 * (a08 + 2 * (a09 + 2 * n)))); n = a10 + 3 * (a11 + 3 * (a12 + 3 * (a13 + 3 * (a14 + 3 * n)))); n = a15 + 2 * (a16 + 2 * (a17 + 2 * (a18 + 2 * (a19 + 2 * n)))); n = a20 + 2 * (a21 + 2 * (a22 + 2 * (a23 + 2 * (a24 + 2 * n)))); if (x[n] == 0) { x[n] = (byte)c; j++; if (j % 1000000 == 0) System.out.print("-"); } } } System.out.println(c+" "+j); c++; } while (j > 0); letter[1] = 'A'; letter[2] = 'B'; letter[3] = 'C'; letter[4] = 'D'; letter[5] = 'E'; System.out.println("\n\nDeepest positions:"); for (m = 0; m < 254803968; m++) if (x[m] > 28) { a00 = m / 127401984; a01 = (m / 63700992) % 2; a02 = (m / 31850496) % 2; a03 = (m / 15925248) % 2; a04 = (m / 7962624) % 2; a05 = (m / 3981312) % 2; a06 = (m / 1990656) % 2; a07 = (m / 995328) % 2; a08 = (m / 497664) % 2; a09 = (m / 248832) % 2; a10 = (m / 82944) % 3; a11 = (m / 27648) % 3; a12 = (m / 9216) % 3; a13 = (m / 3072) % 3; a14 = (m / 1024) % 3; a15 = (m / 512) % 2; a16 = (m / 256) % 2; a17 = (m / 128) % 2; a18 = (m / 64) % 2; a19 = (m / 32) % 2; a20 = (m / 16) % 2; a21 = (m / 8) % 2; a22 = (m / 4) % 2; a23 = (m / 2) % 2; a24 = m % 2; System.out.println(" "); System.out.println(2 * a20+" "+2 * a21+" "+2 * a22+" "+2 * a23+" "+2 * a24); System.out.println(2 * a15+" "+2 * a16+" "+2 * a17+" "+2 * a18+" "+2 * a19); System.out.println(a10+" "+a11+" "+a12+" "+a13+" "+a14); System.out.println(a05+" "+a06+" "+a07+" "+a08+" "+a09); System.out.println(a00+" "+a01+" "+a02+" "+a03+" "+a04); System.out.println("("+x[m]+")"); } j = 0; r = 77; s = 0; do { if (r == 77) { for (e = 1; e < 6; e++) { y[e][1] = 1; y[e][2] = 1; y[e][3] = 0; y[e][4] = 2; y[e][5] = 2; } s = 0; mv = new Move(); } else if (r == 88) { c = 1; do { c = 0; System.out.println("Enter one five-digit number for each row"); System.out.println("1 = your piece, 2 = opponent piece, 0 = empty space"); for (e = 1; e < 6; e++) for (f = 1; f < 6; f++) y[e][f] = 0; for (e = 1; e < 6; e++) { f = lesInt(); y[1][6 - e] = f / 10000; y[2][6 - e] = (f / 1000) % 10; y[3][6 - e] = (f / 100) % 10; y[4][6 - e] = (f / 10) % 10; y[5][6 - e] = f % 10; } for (e = 1; e < 6; e++) { if (y[e][5] != 0 && y[e][5] != 2) c = 1; if (y[e][4] != 0 && y[e][4] != 2) c = 1; if (y[e][3] < 0 || y[e][3] > 2) c = 1; if (y[e][2] < 0 || y[e][2] > 2) c = 1; if (y[e][1] < 0 || y[e][1] > 1) c = 1; } f = 0; for (e = 1; e < 6; e++) if (y[e][2] == 2) { f++; g = 0; for (i = 1; i < 6; i++) if (i - e == 1 || e - i == 1) if (y[i][1] == 1) g++; if (g == 0) c = 1; } if (f > 1) c = 1; k = 0; l = 0; for (e = 1; e < 6; e++) for (f = 1; f < 6; f++) { if (y[e][f] == 1) k++; if (y[e][f] == 2) l++; } if (k == 0 || l == 0) c = 1; if (c == 1) System.out.println("Invalid choice or too few moves left!"); } while (c == 1); s = 0; mv = new Move(); } c = 0; System.out.println(stripe); for (f = 5; f > 0; f--) { System.out.print(f+"|"); for (e = 1; e < 6; e++) { if (s == 0) g = y[e][f]; else g = y[6 - e][6 - f]; if (g == 0) System.out.print(" |"); else if (g + s == 2) System.out.print(" x |"); else System.out.print(" o |"); } System.out.println(stripe); } System.out.println(" A B C D E\n"); for (e = 1; e < 6; e++) for (f = 4; f < 6; f++) if (y[e][f] == 2) y[e][f] = 1; if (y[1][2] == 2 || y[2][2] == 2 || y[3][2] == 2 || y[4][2] == 2 || y[5][2] == 2) { for (e = 1; e < 6; e++) if (y[e][1] == 1) for (f = 1; f < 6; f++) if (y[f][2] == 2 && (e - f == 1 || f - e == 1)) { c++; p1[c] = e; p2[c] = 1; p3[c] = 'x'; p4[c] = f; p5[c] = 2; } } else { for (e = 1; e < 6; e++) for (f = 1; f < 4; f++) if (y[e][f] == 1) for (g = 1; g < 6; g++) if (e - g < 2 && g - e < 2) if (y[g][f + 1] == 0 || (e != g && y[g][f + 1] == 4 - f)) { c++; p1[c] = e; p2[c] = f; p4[c] = g; p5[c] = f + 1; if (y[g][f + 1] == 0) p3[c] = '-'; else p3[c] = 'x'; } } for (d = 1; d <= c; d++) { for (e = 1; e < 6; e++) for (f = 1; f < 6; f++) z[e][f] = y[e][f]; z[p1[d]][p2[d]] = 0; z[p4[d]][p5[d]] = 1; if (p2[d] < 3) { h00 = z[5][5]; h01 = z[4][5]; h02 = z[3][5]; h03 = z[2][5]; h04 = z[1][5]; h05 = z[5][4]; h06 = z[4][4]; h07 = z[3][4]; h08 = z[2][4]; h09 = z[1][4]; h10 = 3 - z[5][3]; h11 = 3 - z[4][3]; h12 = 3 - z[3][3]; h13 = 3 - z[2][3]; h14 = 3 - z[1][3]; h15 = z[5][2]; h16 = z[4][2]; h17 = z[3][2]; h18 = z[2][2]; h19 = z[1][2]; h20 = z[5][1]; h21 = z[4][1]; h22 = z[3][1]; h23 = z[2][1]; h24 = z[1][1]; h10 = h10 % 3; h11 = h11 % 3; h12 = h12 % 3; h13 = h13 % 3; h14 = h14 % 3; n = h04 + 2 * (h03 + 2 * (h02 + 2 * (h01 + 2 * h00))); n = h09 + 2 * (h08 + 2 * (h07 + 2 * (h06 + 2 * (h05 + 2 * n)))); n = h14 + 3 * (h13 + 3 * (h12 + 3 * (h11 + 3 * (h10 + 3 * n)))); n = h19 + 2 * (h18 + 2 * (h17 + 2 * (h16 + 2 * (h15 + 2 * n)))); n = h24 + 2 * (h23 + 2 * (h22 + 2 * (h21 + 2 * (h20 + 2 * n)))); p6[d] = 50 - (x[n] + 1); if (p6[d] % 2 == 0) p6[d] = -p6[d]; p6[d] = p6[d] + 50; } else { p6[d] = 100; e = p4[d]; for (f = 1; f < 6; f++) if (z[f][5] == 1 && (e - f == 1 || f - e == 1)) { h00 = z[1][1]; h01 = z[2][1]; h02 = z[3][1]; h03 = z[4][1]; h04 = z[5][1]; h05 = z[1][2]; h06 = z[2][2]; h07 = z[3][2]; h08 = z[4][2]; h09 = z[5][2]; h10 = z[1][3]; h11 = z[2][3]; h12 = z[3][3]; h13 = z[4][3]; h14 = z[5][3]; h15 = z[1][4]; h16 = z[2][4]; h17 = z[3][4]; h18 = z[4][4]; h19 = z[5][4]; h20 = z[1][5]; h21 = z[2][5]; h22 = z[3][5]; h23 = z[4][5]; h24 = z[5][5]; if (f == 1) h20 = 0; if (f == 2) h21 = 0; if (f == 3) h22 = 0; if (f == 4) h23 = 0; if (f == 5) h24 = 0; n = h04 + 2 * (h03 + 2 * (h02 + 2 * (h01 + 2 * h00))); n = h09 + 2 * (h08 + 2 * (h07 + 2 * (h06 + 2 * (h05 + 2 * n)))); n = h14 + 3 * (h13 + 3 * (h12 + 3 * (h11 + 3 * (h10 + 3 * n)))); n = h19 + 2 * (h18 + 2 * (h17 + 2 * (h16 + 2 * (h15 + 2 * n)))); n = h24 + 2 * (h23 + 2 * (h22 + 2 * (h21 + 2 * (h20 + 2 * n)))); g = 50 - (x[n] + 2); if (g % 2 == 0) g = -g; g = g + 50; if (g < p6[d]) p6[d] = g; } } } for (e = 1; e < c; e++) for (f = e + 1; f <= c; f++) if (p6[e] < p6[f]) { d = p1[e]; p1[e] = p1[f]; p1[f] = d; d = p2[e]; p2[e] = p2[f]; p2[f] = d; q = p3[e]; p3[e] = p3[f]; p3[f] = q; d = p4[e]; p4[e] = p4[f]; p4[f] = d; d = p5[e]; p5[e] = p5[f]; p5[f] = d; d = p6[e]; p6[e] = p6[f]; p6[f] = d; } for (e = 1; e < c; e++) for (f = e + 1; f <= c; f++) if (p6[e] == p6[f] && (p1[e] + 5 * p2[e] > p1[f] + 5 * p2[f] || (p1[e] + 5 * p2[e] == p1[f] + 5 * p2[f] && p4[e] + 5 * p5[e] > p4[f] + 5 * p5[f]))) { d = p1[e]; p1[e] = p1[f]; p1[f] = d; d = p2[e]; p2[e] = p2[f]; p2[f] = d; q = p3[e]; p3[e] = p3[f]; p3[f] = q; d = p4[e]; p4[e] = p4[f]; p4[f] = d; d = p5[e]; p5[e] = p5[f]; p5[f] = d; d = p6[e]; p6[e] = p6[f]; p6[f] = d; } for (d = 1; d <= c; d++) { if (s == 0) System.out.print(d+". "+letter[p1[d]]+p2[d]+p3[d]+letter[p4[d]]+p5[d]+": "); else System.out.print(d+". "+letter[6-p1[d]]+(6-p2[d])+p3[d]+letter[6-p4[d]]+(6-p5[d])+": "); if (p6[d] > 50) System.out.print("Win"); else System.out.print("Loss"); p6[d] = p6[d] - 50; if (p6[d] < 0) p6[d] = -p6[d]; p6[d] = 50 - p6[d]; System.out.println(" in "+p6[d]+" moves"); } if (p6[1] > 4) { if (mv.prev != null) System.out.println ("66. Retract last move"); System.out.println ("77. Back to start"); System.out.println ("88. Enter new position"); System.out.println ("99. Quit"); r = 0; do { System.out.print("Enter alternative: "); r = lesInt(); } while (r != 99 && r != 88 && r!= 77 && (r != 66 || mv.prev == null) && (r < 1 || r > c)); } else r = 77; if (r <= c) { for (e = 1; e < 6; e++) for (f = 4; f < 6; f++) y[e][f] = 2 * y[e][f]; mv2 = new Move(); mv2 = mv; mv = new Move(); mv.prev = mv2; mv.x11 = y[1][1]; mv.x21 = y[2][1]; mv.x31 = y[3][1]; mv.x41 = y[4][1]; mv.x51 = y[5][1]; mv.x12 = y[1][2]; mv.x22 = y[2][2]; mv.x32 = y[3][2]; mv.x42 = y[4][2]; mv.x52 = y[5][2]; mv.x13 = y[1][3]; mv.x23 = y[2][3]; mv.x33 = y[3][3]; mv.x43 = y[4][3]; mv.x53 = y[5][3]; mv.x14 = y[1][4]; mv.x24 = y[2][4]; mv.x34 = y[3][4]; mv.x44 = y[4][4]; mv.x54 = y[5][4]; mv.x15 = y[1][5]; mv.x25 = y[2][5]; mv.x35 = y[3][5]; mv.x45 = y[4][5]; mv.x55 = y[5][5]; y[p1[r]][p2[r]] = 0; y[p4[r]][p5[r]] = 1; for (e = 1; e < 6; e++) for (f = 1; f < 4; f++) if (f < 3 || e < 3) { g = y[6 - e][6 - f]; y[6 - e][6 - f] = y[e][f]; y[e][f] = g; } for (e = 1; e < 6; e++) for (f = 1; f < 6; f++) if (y[e][f] > 0) y[e][f] = 3 - y[e][f]; } if (r == 66) { y[1][1] = mv.x11; y[2][1] = mv.x21; y[3][1] = mv.x31; y[4][1] = mv.x41; y[5][1] = mv.x51; y[1][2] = mv.x12; y[2][2] = mv.x22; y[3][2] = mv.x32; y[4][2] = mv.x42; y[5][2] = mv.x52; y[1][3] = mv.x13; y[2][3] = mv.x23; y[3][3] = mv.x33; y[4][3] = mv.x43; y[5][3] = mv.x53; y[1][4] = mv.x14; y[2][4] = mv.x24; y[3][4] = mv.x34; y[4][4] = mv.x44; y[5][4] = mv.x54; y[1][5] = mv.x15; y[2][5] = mv.x25; y[3][5] = mv.x35; y[4][5] = mv.x45; y[5][5] = mv.x55; mv = mv.prev; } if (r == 99) j = 1; s = 1 - s; } while (j == 0); } }