Created
November 15, 2014 15:15
-
-
Save anonymous/f87bda442b71975869dc to your computer and use it in GitHub Desktop.
Solve 4x4 mazes
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.HashSet; | |
import java.util.Iterator; | |
import java.util.List; | |
import java.util.Set; | |
public class Main { | |
public static void main(String[] args) { | |
// lookahead size | |
int k = 7; | |
Set<Maze> mazes = generateMazes(); | |
List<Direction[]> paths = createPaths(k); | |
int round = 0; | |
List<Direction> fullPath = new ArrayList<Direction>(); | |
while (mazes.size() > 0) { | |
System.out.println("Round " + round); | |
int bestScore = Integer.MAX_VALUE; | |
Direction[] bestPath = null; | |
for (Direction[] path : paths) { | |
int pathScore = mazes.stream().mapToInt(maze -> maze.tryMoves(path)).sum(); | |
if (pathScore < bestScore) { | |
bestScore = pathScore; | |
bestPath = path; | |
} | |
} | |
// we might not need all moves in the last batch | |
// just try to reduce k until we don't reach the end any more | |
while (bestScore == 0) { | |
paths = createPaths(k-1); | |
bestScore = Integer.MAX_VALUE; | |
Direction[] bestSubPath = null; | |
for (Direction[] path : paths) { | |
int pathScore = mazes.stream().mapToInt(maze -> maze.tryMoves(path)).sum(); | |
if (pathScore < bestScore) { | |
bestScore = pathScore; | |
bestSubPath = path; | |
} | |
} | |
if (bestScore == 0) { | |
bestPath = bestSubPath; | |
k--; | |
} | |
} | |
fullPath.addAll(Arrays.asList(bestPath)); | |
Iterator<Maze> it = mazes.iterator(); | |
while (it.hasNext()) { | |
Maze maze = it.next(); | |
for (Direction direction : bestPath) { | |
maze.move(direction); | |
} | |
if (maze.isFinished()) { | |
it.remove(); | |
} | |
} | |
round += k; | |
} | |
System.out.println("Found solution after " + round + " rounds."); | |
System.out.println("Best sequence: " + pathToString(fullPath)); | |
} | |
private static Set<Maze> generateMazes() { | |
Set<Maze> mazes = new HashSet<Maze>(); | |
// generate all different mazes from all 2^14 bitstrings | |
// a maze is valid when all non-wall cells can be reached from the start | |
for (int i = 0; i < 16384; i++) { | |
Maze maze = new Maze(i); | |
if (maze.isValid()) { | |
mazes.add(maze); | |
} | |
} | |
return mazes; | |
} | |
/** | |
* Create all possible paths (sequence of directions) of length k | |
* Sequences containing variants of RLR are ignored, because they never lead to an optimal solution | |
* (thanks to j_random_hacker) | |
*/ | |
private static List<Direction[]> createPaths(int k) { | |
List<Direction[]> paths = new ArrayList<Direction[]>(); | |
createPaths(paths, new Direction[k], 0); | |
return paths; | |
} | |
private static void createPaths(List<Direction[]> directions, Direction[] current, int i) { | |
if (i == current.length) { | |
directions.add(Arrays.copyOf(current, current.length)); | |
} else { | |
for (Direction direction : Direction.values()) { | |
// skip variants of RLR, because they never lead to an optimal solution | |
if (i > 2 && current[i-2] == direction && current[i-1] == Direction.opposite(direction)) { | |
continue; | |
} | |
current[i] = direction; | |
createPaths(directions, current, i+1); | |
} | |
} | |
} | |
private static String pathToString(List<Direction> path) { | |
StringBuilder builder = new StringBuilder(); | |
for (Direction direction : path) { | |
builder.append(direction.getName()); | |
} | |
return builder.toString(); | |
} | |
private static class Maze { | |
static final int SIZE = 4; | |
static final int UNVISITED = Integer.MAX_VALUE - 1; | |
static final int WALL = Integer.MAX_VALUE; | |
private int[][] maze; | |
private boolean valid; | |
private int x; | |
private int y; | |
private boolean finished; | |
public Maze(int representation) { | |
createMaze(representation); | |
calculateValidity(); | |
} | |
public boolean isValid() { | |
return valid; | |
} | |
public int getScore() { | |
return maze[x][y]; | |
} | |
public boolean isFinished() { | |
return finished; | |
} | |
public void move(Direction direction) { | |
int x = this.x + direction.getValue()[0]; | |
int y = this.y + direction.getValue()[1]; | |
// make a step if possible | |
if (x >= 0 && x < SIZE && y >= 0 && y < SIZE && maze[x][y] != WALL) { | |
this.x = x; | |
this.y = y; | |
if (x == SIZE - 1 && y == SIZE - 1) { | |
finished = true; | |
} | |
} | |
} | |
public int tryMoves(Direction[] directions) { | |
int currentX = this.x; | |
int currentY = this.y; | |
for (Direction direction : directions) { | |
int x = currentX + direction.getValue()[0]; | |
int y = currentY + direction.getValue()[1]; | |
// make a step if possible | |
if (x >= 0 && x < SIZE && y >= 0 && y < SIZE && maze[x][y] != WALL) { | |
currentX = x; | |
currentY = y; | |
} | |
if (currentX == SIZE - 1 && currentY == SIZE - 1) { | |
return 0; | |
} | |
} | |
return maze[currentX][currentY]; | |
} | |
private void createMaze(int id) { | |
// translate bitstring to maze (0 => empty cell, 1 => wall) | |
maze = new int[SIZE][SIZE]; | |
for (int i = 0; i < SIZE * SIZE - 2; i++) { | |
int x = (i + 1) % SIZE; | |
int y = (i + 1) / SIZE; | |
maze[x][y] = (id & (1 << i)) == 0 ? UNVISITED : WALL; | |
} | |
maze[0][0] = UNVISITED; | |
maze[SIZE-1][SIZE-1] = UNVISITED; | |
// find the shortest path from each non-wall to the end cell | |
shortestPath(SIZE-1, SIZE-1, 0); | |
} | |
private void shortestPath(int x, int y, int distance) { | |
if (x < 0 || x >= SIZE || y < 0 || y >= SIZE) { | |
return; | |
} | |
if (maze[x][y] != WALL && distance < maze[x][y]) { | |
maze[x][y] = distance; | |
shortestPath(x-1, y, distance+1); | |
shortestPath(x+1, y, distance+1); | |
shortestPath(x, y-1, distance+1); | |
shortestPath(x, y+1, distance+1); | |
} | |
} | |
private void calculateValidity() { | |
valid = true; | |
for (int x = 0; x < SIZE; x++) { | |
for (int y = 0; y < SIZE; y++) { | |
valid &= maze[x][y] != UNVISITED; | |
} | |
} | |
} | |
} | |
private enum Direction { | |
LEFT("L", new int[]{-1, 0}), | |
RIGHT("R", new int[]{1, 0}), | |
UP("U", new int[]{0, -1}), | |
DOWN("D", new int[]{0, 1}); | |
private String name; | |
private int[] value; | |
Direction(String name, int[] value) { | |
this.name = name; | |
this.value = value; | |
} | |
public String getName() { | |
return name; | |
} | |
public int[] getValue() { | |
return value; | |
} | |
public static Direction opposite(Direction d) { | |
switch (d) { | |
case LEFT: | |
return RIGHT; | |
case RIGHT: | |
return LEFT; | |
case UP: | |
return DOWN; | |
case DOWN: | |
return UP; | |
default: | |
return null; | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment