Solve 4x4 mazes

gistfile1.txt

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;
			}
		}
	}
}