public static boolean isInMapBounds(String[] map, Point p)
	{
		return Utilities.isInBounds(map, p.y, p.x) && map[p.y].charAt(p.x) != ' ';
	}

	public static class MapState
	{
		public static final int[] RIGHT_FACE = {2, 0, 3, 1};
		public static final int[] TURN_RIGHT = {3, 0, 1, 2};
		public static final int[] TURN_LEFT = {1, 2, 3, 0};

		public final int[] permutation;
		public final Point p;

		public MapState(int[] permutation, Point p)
		{
			this.permutation = permutation.clone();
			this.p = (Point) p.clone();
		}

		public MapState moveForward()
		{
			Point newPoint = new Point(p);
			int[] newPerm = permutation.clone();
			if (++newPoint.x == MAP_SIZE)
			{
				newPoint.x = 0;
				newPerm = compose(permutation, RIGHT_FACE);
			}
			return new MapState(newPerm, newPoint);
		}

		public MapState turnRight()
		{
			Point newPoint = new Point();
			newPoint.x = p.y;
			newPoint.y = MAP_SIZE - 1 - p.x;

			int[] newPerm = compose(permutation, TURN_RIGHT);

			return new MapState(newPerm, newPoint);
		}

		public MapState turnLeft()
		{
			Point newPoint = new Point();
			newPoint.x = MAP_SIZE - 1 - p.y;
			newPoint.y = p.x;

			int[] newPerm = compose(permutation, TURN_LEFT);

			return new MapState(newPerm, newPoint);
		}

		@Override
		public boolean equals(Object obj)
		{
			if (!(obj instanceof MapState))
				return false;
			MapState ms = (MapState) obj;
			return Arrays.equals(permutation, ms.permutation) && p.equals(ms.p);
		}

		public static int[] compose(int[]... perms)
		{
			int[] newPerm = new int[4];
			for (int i = 0; i < 4; i++)
			{
				int image = i;
				for (int j = perms.length - 1; j >= 0; j--)
					image = perms[j][image];
				newPerm[i] = image;
			}
			return newPerm;
		}
	}

	public static final int MAP_SIZE = 50;

	@Override
	public Object partTwo(InputStream input) throws IOException
	{
		String[] map;
		String instructions;
		try (Scanner in = new Scanner(input))
		{
			in.useDelimiter("\n\n");
			map = in.next().split("\n");
			instructions = in.next();
		}

		// Find start location
		Point start = new Point();
		while (map[0].charAt(start.x) == ' ')
			start.x++;

		// Find a representation of each side
		MapState[] sides = new MapState[6];
		sides[0] = new MapState(new int[] {0, 1, 2, 3}, start);
		int nextSide = 1;
		for (int i = 0; nextSide < 6; i++)
		{
			Point up = new Point(sides[i].p.x, sides[i].p.y - MAP_SIZE);
			if (isInMapBounds(map, up))
			{
				int[] newPerm = MapState.compose(sides[i].permutation, MapState.TURN_LEFT, MapState.RIGHT_FACE, MapState.TURN_RIGHT);
				MapState newState = new MapState(newPerm, up);
				if (!Arrays.stream(sides).anyMatch(newState::equals))
					sides[nextSide++] = newState;
			}

			Point down = new Point(sides[i].p.x, sides[i].p.y + MAP_SIZE);
			if (isInMapBounds(map, down))
			{
				int[] newPerm = MapState.compose(sides[i].permutation, MapState.TURN_RIGHT, MapState.RIGHT_FACE, MapState.TURN_LEFT);
				MapState newState = new MapState(newPerm, down);
				if (!Arrays.stream(sides).anyMatch(newState::equals))
					sides[nextSide++] = newState;
			}

			Point left = new Point(sides[i].p.x - MAP_SIZE, sides[i].p.y);
			if (isInMapBounds(map, left))
			{
				int[] newPerm = MapState.compose(sides[i].permutation, MapState.TURN_LEFT, MapState.TURN_LEFT,
						MapState.RIGHT_FACE, MapState.TURN_RIGHT, MapState.TURN_RIGHT);
				MapState newState = new MapState(newPerm, left);
				if (!Arrays.stream(sides).anyMatch(newState::equals))
					sides[nextSide++] = newState;
			}

			Point right = new Point(sides[i].p.x + MAP_SIZE, sides[i].p.y);
			if (isInMapBounds(map, right))
			{
				int[] newPerm = MapState.compose(sides[i].permutation, MapState.RIGHT_FACE);
				MapState newState = new MapState(newPerm, right);
				if (!Arrays.stream(sides).anyMatch(newState::equals))
					sides[nextSide++] = newState;
			}
		}

		// construct the map
		Map<String, boolean[][]> cube = new Hashtable<>();
		for (int i = 0; i < 6; i++)
		{
			boolean[][] thisFace = new boolean[MAP_SIZE][MAP_SIZE];
			for (int j = 0; j < MAP_SIZE; j++)
				for (int k = 0; k < MAP_SIZE; k++)
					thisFace[j][k] = map[j + sides[i].p.y].charAt(k + sides[i].p.x) == '#';
			int[] perm = sides[i].permutation;

			cube.put(Arrays.toString(perm), thisFace);
			for (int j = 0; j < 3; j++)
			{
				boolean[][] newFace = new boolean[MAP_SIZE][MAP_SIZE];
				for (int k = 0; k < MAP_SIZE; k++)
					for (int l = 0; l < MAP_SIZE; l++)
						newFace[k][l] = thisFace[l][MAP_SIZE - 1 - k];
				thisFace = newFace;
				perm = MapState.compose(perm, MapState.TURN_RIGHT);
				cube.put(Arrays.toString(perm), thisFace);
			}
		}

		// follow instructions
		Matcher m = Pattern.compile("(\\d+)([LR]|$)").matcher(instructions);
		MapState position = new MapState(new int[] {0, 1, 2, 3}, new Point());
		while (m.find())
		{
			int steps = Integer.parseInt(m.group(1));
			for (int i = 0; i < steps; i++)
			{
				MapState newPos = position.moveForward();
				if (cube.get(Arrays.toString(newPos.permutation))[newPos.p.y][newPos.p.x])
					break;
				position = newPos;
			}

			switch (m.group(2))
			{
			case "R":
				position = position.turnRight();
				break;
			case "L":
				position = position.turnLeft();
				break;
			}
		}

		// find the original rotation
		int i, dir = 0;
		w: while (true)
		{
			for (i = 0; i < 6; i++)
				if (Arrays.equals(sides[i].permutation, position.permutation))
					break w;

			position = position.turnLeft();
			dir++;
		}

		return (position.p.y + sides[i].p.y) * 1000 + (position.p.x + sides[i].p.x) * 4 + dir + 1004;
	}