//import static Main.*;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static final int R = 1;
public static final int L = -1;
public static final int U = -4;
public static final int D = 4;
public static final int[] mov = new int[] {R,L,U,D};
public static ArrayList<Maze> mazes = new ArrayList<>();
public static void main
(String[] args
) { generateMazes("0");
String sequence
= "RRDRRDRLDRDLDLULLLDDRDDDURDRRDR"; // execSequence(sequence);
// int r = remaining(); // 0 if above sequence solves all mazes
boolean isSolution = isSolution(sequence); // true if sequence solves all mazes
System.
out.
println((isSolution
? "Sequence solves all " : "Sequence doesn't solve all ") + "mazes");
// manualGame();
}
public static boolean isSolution
(String s
) { return mazes.size() - numberSolved(s) == 0;
}
public static int numberSolved
(String s
) { int sum = numberSolvedHard(s);
for (Maze maze : mazes) {
maze.pos = 0;
maze.isAlive = true;
}
return sum;
}
public static int numberSolvedHard
(String s
) { int sum = 0;
for (char c : s.toCharArray()) {
for (Maze maze : mazes) {
if (!maze.isAlive) continue;
switch(c) {
case 'R': maze.move(R);
break;
case 'L': maze.move(L);
break;
case 'U': maze.move(U);
break;
case 'D': maze.move(D);
break;
}
if (!maze.isAlive) {
sum++;
}
}
}
return sum;
}
public static ArrayList<String> perms = new ArrayList<>();
public static ArrayList<String> invrs = new ArrayList<>();
public static void doPerms
(ArrayList
<String
> cont,
String seq,
String move
) { if (seq.length() >= 10)
return;
if (seq.length() >= 8)
cont.add(seq + move);
seq += move;
if (cont == perms) {
doPerms(cont, seq, "R");
doPerms(cont, seq, "D");
doPerms(cont, seq, "L");
doPerms(cont, seq, "U");
} else {
doPerms(cont, seq, "D");
doPerms(cont, seq, "R");
doPerms(cont, seq, "U");
doPerms(cont, seq, "L");
}
}
public static void execSequence
(String seq
) { for (char c : seq.toCharArray()) {
for (Maze maze : mazes) {
switch(c) {
case 'R': maze.move(R);
break;
case 'L': maze.move(L);
break;
case 'U': maze.move(U);
break;
case 'D': maze.move(D);
break;
}
}
}
}
public static int remainingNotAtGoal(int goal) {
int tot = remaining();
for (Maze maze : mazes) {
if (maze.isAlive) {
if (maze.pos == goal) tot--;
}
}
return tot;
}
public static int remaining() {
int tot = mazes.size();
for (Maze maze : mazes) {
if (!maze.isAlive) tot--;
}
return tot;
}
public static void manualGame() {
int r = remaining();
Scanner sc
= new Scanner
(System.
in); while (r > 0) {
System.
out.
println("Sequence: " + seq
+ " Length: " + seq.
length()); System.
out.
println("---------------------"); System.
out.
println("Removed: " + (mazes.
size() - r
)); System.
out.
println("Remaining: " + r
);
int _a = 0;
int[] a = new int[16];
int[] p = new int[16];
int[] d = new int[16];
for (Maze maze : mazes) {
if (!maze.isAlive) continue;
for (int i = 0; i < 16; i++) {
a[i] += maze.layout[i];
d[i] += maze.distances[i] == 255 ? 0 : maze.distances[i];
_a += a[i];
}
p[maze.pos]++;
}
System.
out.
printf("%-36s",
" | Obstacles"); System.
out.
printf(" | Current positions\n"); for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
System.
out.
printf("%4d", a
[i
*4 + j
]); }
for (int j = 0; j < 4; j++) {
System.
out.
printf("%4d", p
[i
*4 + j
]); }
for (int j = 0; j < 4; j++) {
System.
out.
printf("%4d", d
[i
*4 + j
]); }
}
System.
out.
print("Command: "); seq += cmd.toUpperCase();
for (Maze maze : mazes) {
if (!maze.isAlive) continue;
if (cmd.equals("d"))
maze.move(R);
if (cmd.equals("a"))
maze.move(L);
if (cmd.equals("w"))
maze.move(U);
if (cmd.equals("s"))
maze.move(D);
if (cmd.equals("p")) {
for (Maze m : mazes) {
if (m.isAlive)
m.printc();
}
}
}
r = remaining();
}
}
public static void generateMazes
(String layout
) { if (layout.length() == 16) {
if (layout.charAt(15) == '1') return;
int[] a = new int[16];
for (int i
= 0; i
< 16; i
++) a
[i
] = Character.
digit(layout.
charAt(i
),
10); if (solutionExists(a, 15)) mazes.add(new Maze(a));
return;
}
generateMazes(layout+'1');
generateMazes(layout+'0');
}
public static boolean solutionExists(int[] a, int k) {
if (a[0] == 2) return true;
if (a[k] == 2) return false;
for (int m : mov) {
if (canMove(a, k, m)) {
a[k] = 2;
boolean f = solutionExists(a, k+m);
a[k] = 0;
if (f) return true;
}
}
return false;
}
public static boolean canMove(int[] a, int pos, int dir) {
int npos = pos + dir;
if (npos < 0 || npos >= 16) return false;
if (a[npos] == 1) return false;
if (dir == 1 && pos % 4 == 3) return false;
if (dir == -1 && pos % 4 == 0) return false;
return Math.
abs((npos
- pos
) % 4) <= 1; }
public static int[] cpy(int[] arr) {
int[] a = new int[arr.length];
System.
arraycopy(arr,
0, a,
0, a.
length); return a;
}
}
class Maze {
public final int[] layout;
public int[] distances;
public int pos;
public boolean isAlive;
public boolean softIsAlive;
public Maze(int[] layout) {
this.layout = layout;
this.pos = 0;
this.isAlive = true;
}
public int getDistance() {
return distances[pos];
}
public int getDistance(int dir) {
if (!Main.canMove(layout, pos, dir)) return getDistance();
return distances[pos+dir];
}
public void move(int dir) {
int npos = pos + dir;
if (npos < 0 || npos >= 16) return;
if (layout[npos] == 1) return;
if (dir == 1 && pos % 4 == 3) return;
if (dir == -1 && pos % 4 == 0) return;
if (Math.
abs((npos
- pos
) % 4) > 1) return;
pos = npos;
if (pos == 15) this.isAlive = false;
}
public void print() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++)
System.
out.
printf("%-2s", i
*4 + j
== pos
? "x" : layout
[i
*4 + j
]); }
}
public void printd() {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++)
System.
out.
printf("%-2s", distances
[i
*4 + j
]); }
}
public void printc() {
for (int i = 0; i < 16; i++)
}
}