Introduction
In Jane Street’s latest puzzle, ‘Pent-Up’ Frustration 3 / Knight Moves 7, we’re given the following prompt
The board above has been tiled with the 12 pentominoes (plus a 2-by-2 tetromino) into 13 regions. Think of each of these 13 regions as constructed out of 1-by-1-by-1 cubes. We need to add a tower to each region. A tower is an additional size-1 cube placed on one of a region’s squares.
After adding these towers, place a knight at the bottom-left square. It then proceeds to make knight’s moves until it has visited all the towers. It never visits the same space twice. (A move on this board involves travelling 0 units in one dimension, 1 in another, and 2 in the third. The knight is allowed to “pass through” towers as it moves.)
But there’s a catch: As you can see, the knight starts with a score of 0. On its Nth move, its score increases by N if the move is to a location at the same altitude as the square it moved from. If, instead, it moves up, the score is multiplied by N. And finally, if it moves down, the score is divided by N. This last type of move is only allowed if the score is evenly divisible by N.
Every three moves, up until move #18, the knight wrote down its score upon arriving at a given square. From then on it only wrote down its score every K moves, for some larger value K. Using this information, can you reconstruct the knight’s path?
After filling all the remaining visited squares with the missing score values, find the unvisited squares. For each of these squares, compute the sum of the scores in any orthogonally adjacent squares that were part of the knight’s path. The answer to this puzzle is the sum of these “neighbor sums” from the unvisited squares.
As well as a visual depiction
Solution
\(33609\) is the final result, with the path and tower placement depicted in the animation below (a hand sketched version is shown in the next subsection)
Discovery
Brute force with problem specific optimization comes to mind for these types of problems.
Naively a naive brute force DFS would require checking
\[\begin{aligned} \text{# of moves} &= (\text{# of squares in a row} \times \text{# of squares in a column - 1}) ^{|\text{+ moves}| + |\text{* moves}\ + |\text{/ moves}|} \\ &= 63 ^{8 + 4 + 4} \\ &= 6.158129128\times10^{28} \end{aligned}\]Board positions to see which solved the problem.
Some simple observations bring that # down immensely
It then proceeds to make knight’s moves until it has visited all the towers, meaning the last move must end with the horse on a towerIt never visits the same space twice.andWe need to add a tower to each regionmeaning there can only be 13 moves at z-index of 1Every three moves, up until move #18, the knight wrote down its score upon arriving at a given square. From then on it only wrote down its score every K moves,meaning we can check to see if every \(\text{move} > 18 \text{ ? } (\text{move} - 18) \text{ % } k : \text{move % } 3\) lands on a clue tile- The only way to make the first three moves valid is by starting on a tower and moving to the 1 clue tile
In addition we can verify there is only a singular sequence of operations and \(K\) that land on all the clue tiles:
Ops: [+, +, /, +, +, +, *, /, +, +, +, *, +, +, /, +, +, +, +, +, *, +, +, /, +, +, +, +, +, *, /, +, *, /, +, +, +, +, +, +, +, +, +, +, +, +, +, +, +, +, +, +, +]
Scores: [0, 1, 3, 1, 5, 10, 16, 112, 14, 23, 33, 44, 528, 541, 555, 37, 53, 70, 88, 107, 127, 2667, 2689, 2712, 113, 138, 164, 191, 219, 248, 7440, 240, 272, 8976, 264, 299, 335, 372, 410, 449, 489, 530, 572, 615, 659, 704, 750, 797, 845, 894, 944, 995, 1047, 1100]
K: 7
You’ll notice that the sequence does not in fact end with z-index of 1, so we’ll have to brute force and try appending the following sequences to the end of the known operations to see which works
[*]
[+, *]
[+, +, *]
[+, +, +, *]
[+, +, +, *]
[+, +, +, +, *]
[+, +, +, +, +, *]
[+, +, +, +, +, +, *]
With that set the runtime of the brute force is lighting fast and yields the path depicted in the graphic above or more crudely as shown below.
Here’s the Java code that produced the final result of $33609$
package janestreet;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class pentupfrustration3_knightmoves7 {
static int[][] regions = new int[][]{
{ 1, 1, 1, 1, 1, 2, 2, 2 },
{ 3, 3, 3, 4, 4, 5, 5, 2 },
{ 3, 6, 3, 4, 4, 4, 5, 2 },
{ 7, 6, 6, 8, 8, 9, 5, 5 },
{ 7, 7, 6, 8, 8, 9, 9, 10 },
{ 7, 11, 6, 12, 9, 9, 13, 10 },
{ 7, 11, 12, 12, 12, 13, 13, 10 },
{ 11, 11, 11, 12, 13, 13, 10, 10 }
};
static List<int[]> hasTower = List.of(
new int[]{-1, -1},
new int[]{-1, -1},
new int[]{-1, -1},
new int[]{-1, -1},
new int[]{-1, -1},
new int[]{-1, -1},
new int[]{-1, -1},
new int[]{-1, -1},
new int[]{-1, -1},
new int[]{-1, -1},
new int[]{-1, -1},
new int[]{-1, -1},
new int[]{-1, -1},
new int[]{-1, -1}
);
static boolean[][] visited = new boolean[8][8];
static int[][] scores = new int[][]{
{-1,-1,-1,-1,-1,37,-1,1100},
{-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-1,-1,23,-1,138,-1,-1,},
{528,-1,-1,-1,-1,-1,-1,-1,},
{-1,449,-1,-1,16,-1,-1,-1},
{-1,750,-1,88,-1,272,1,-1},
{-1,-1,-1,-1,-1,-1,-1,-1},
{0,-1,-1,-1,-1,-1,-1,-1}
};
static int[][] addMoves = new int[][]{
{2,1,0},
{-2,1,0},
{-2,-1,0},
{2,-1,0},
{1,2,0},
{1,-2,0},
{-1,-2,0},
{-1,2,0}
};
static int[][] divideMoves = new int[][]{
{2,0,-1},
{-2,0,-1},
{0,2,-1},
{0,-2,-1}
};
static int[][] multiplyMoves = new int[][]{
{2,0,1},
{-2,0,1},
{0,2,1},
{0,-2,1}
};
static int maxDepth = 0;
static int maxTowers = 0;
public static int calculate_ops(Set<Integer> numbers, int z, int m, int score, int k, List<Integer> sol, List<Character> ops){
if(numbers.isEmpty()) return k;
boolean removed = false;
if(z < 0 || z > 1) return -1;
if((m > 19 && (m - 19) % k == 0) || (m <= 19 && (m - 1) % k == 0)){
if(!numbers.contains(score)){
return -1;
}
removed = true;
numbers.remove(score);
}
if(m == 19 && k == 3){
for(int i = 4; i < 10; i++){
int res = calculate_ops(numbers, z, m, score, i, sol, ops);
if(res != -1) return res;
}
return -1;
}
sol.add(score);
ops.add('+');
int staySame = calculate_ops(numbers, z, m + 1, score + m, k, sol, ops);
if(staySame != -1) return staySame;
ops.removeLast();
if(score % m == 0) {
ops.add('/');
int goDown = calculate_ops(numbers, z - 1, m + 1, score / m, k, sol, ops);
if(goDown != -1) return goDown;
ops.removeLast();
}
ops.add('*');
int goUp = calculate_ops(numbers, z + 1, m + 1, score * m, k , sol, ops);
if(goUp != -1) return goUp;
ops.removeLast();
sol.removeLast();
if(removed){
numbers.add(score);
}
return -1;
}
public static void placeMoves(int cellDestination, int move, List<List<Character>> ops, List<Character> currOps, int i, List<int[]> cells, int k, int r, int c, int z, int score, int towers){
if(i == currOps.size()){
recurse(cellDestination + 1, move, ops, cells, k, r, c, z, score, towers);
return;
}
boolean modulo = (move > 19 && (move - 18) % k == 0) || (move > 0 && move <= 19 && move % 3 == 0);
// go up
if(currOps.get(i) == '*'){
for(int[] dir: multiplyMoves){
int r1 = r + dir[0], c1 = c + dir[1], z1 = z + dir[2];
if(outOfBounds(r1, c1) || visited[r1][c1]) continue;
if(modulo && (r1 != cells.get(cellDestination + 1)[0] || c1 != cells.get(cellDestination + 1)[1])) continue;
int[] tower = hasTower.get(regions[r1][c1]);
int oldTower0 = tower[0];
int oldTower1 = tower[1];
if(!placeTower(r1, c1)) continue;
visited[r1][c1] = true;
int oldScore = scores[r1][c1];
scores[r1][c1] = score * move ;
placeMoves(cellDestination, move + 1, ops, currOps, i + 1, cells, k, r1, c1, z1, scores[r1][c1], towers + 1);
visited[r1][c1] = false;
scores[r1][c1] = oldScore;
tower[0] = oldTower0; tower[1] = oldTower1;
}
}
// go down
else if (currOps.get(i) == '/'){
for(int[] dir: divideMoves){
int r1 = r + dir[0], c1 = c + dir[1], z1 = z + dir[2];;
if(outOfBounds(r1, c1) || visited[r1][c1] || towerAt(r1, c1)) continue;
if(modulo && (r1 != cells.get(cellDestination + 1)[0] || c1 != cells.get(cellDestination + 1)[1])) continue;
visited[r1][c1] = true;
int oldScore = scores[r1][c1];
scores[r1][c1] = score / move;
placeMoves(cellDestination, move + 1, ops, currOps, i + 1, cells, k, r1, c1, z1, scores[r1][c1], towers);
visited[r1][c1] = false;
scores[r1][c1] = oldScore;
}
} else {
for(int[] dir: addMoves){
int r1 = r + dir[0], c1 = c + dir[1], z1 = z + dir[2];;
if(outOfBounds(r1, c1) || visited[r1][c1]) continue;
if(modulo && (r1 != cells.get(cellDestination + 1)[0] || c1 != cells.get(cellDestination + 1)[1])) continue;
int[] tower = hasTower.get(regions[r1][c1]);
int oldTower0 = tower[0];
int oldTower1 = tower[1];
if(z1 == 1 && !placeTower(r1, c1)) continue;
visited[r1][c1] = true;
int oldScore = scores[r1][c1];
scores[r1][c1] = score + move;
placeMoves(cellDestination, move + 1, ops, currOps, i + 1, cells, k, r1, c1, z1, scores[r1][c1], towers + (z1 == 1 ? 1 : 0));
visited[r1][c1] = false;
scores[r1][c1] = oldScore;
tower[0] = oldTower0; tower[1] = oldTower1;
}
}
}
public static void calculateAnswer(){
int total = 0;
for(int r = 0; r < scores.length; r++){
for(int c = 0; c < scores[r].length; c++){
if(scores[r][c] == -1){
int tmp = (outOfBounds(r - 1, c) || scores[r - 1][c] == -1 ? 0 : scores[r - 1][c]) +
(outOfBounds(r + 1, c) || scores[r + 1][c] == -1 ? 0 : scores[r + 1][c]) +
(outOfBounds(r, c + 1) || scores[r][c + 1] == -1 ? 0 : scores[r][c + 1]) +
(outOfBounds(r, c - 1) || scores[r][c - 1] == -1 ? 0 : scores[r][c - 1]);
total += tmp;
}
}
}
System.out.println("Final answer: " + total);
}
public static void recurse(int cellDestination, int move, List<List<Character>> ops, List<int[]> cells, int k, int r, int c, int z, int score, int towers){
if(move > maxDepth || towers > maxTowers){
System.out.println("move: " + cellDestination + " " + cells.size());
printBoard(r, c, 0, k, towers);
maxDepth = Math.max(move, maxDepth);
maxTowers = Math.max(towers, maxTowers);
}
if(cellDestination == cells.size() - 1) {
// has to end on a tower, original first 53 moves end up at z = 0
placeMoves(cellDestination, move, ops, List.of('*'), 0, cells, k, r, c, z, score, towers);
placeMoves(cellDestination, move, ops, List.of('+', '*'), 0, cells, k, r, c, z, score, towers);
placeMoves(cellDestination, move, ops, List.of('+', '+', '*'), 0, cells, k, r, c, z, score, towers);
placeMoves(cellDestination, move, ops, List.of('+', '+', '+', '*'), 0, cells, k, r, c, z, score, towers);
placeMoves(cellDestination, move, ops, List.of('+', '+', '+', '+', '*'), 0, cells, k, r, c, z, score, towers);
placeMoves(cellDestination, move, ops, List.of('+', '+', '+', '+', '+', '*'), 0, cells, k, r, c, z, score, towers);
return;
} else if (cellDestination >= cells.size()) {
printBoard(r, c, 0, k, towers);
calculateAnswer();
System.exit(0);
}
placeMoves(cellDestination, move, ops, ops.get(cellDestination), 0, cells, k, r, c, z, score, towers);
}
public static void main(String[] args){
Set<Integer> numbers = new HashSet<>();
numbers.add(37);
numbers.add(1100);
numbers.add(23);
numbers.add(138);
numbers.add(528);
numbers.add(449);
numbers.add(16);
numbers.add(750);
numbers.add(88);
numbers.add(272);
numbers.add(1);
numbers.add(0);
int m = 1;
List<Character> tmpOps = new ArrayList<>();
List<List<Character>> ops = new ArrayList<>();
List<Character> tmp = new ArrayList<>();
List<Integer> sol = new ArrayList<>();
int k = calculate_ops(numbers, 1, m, 0, 3, sol, tmpOps);
System.out.println("Ops: " + tmpOps);
System.out.println("Scores: " + sol);
System.out.println("K: " + k);
for(int i = 0; i < sol.size(); i++){
tmp.add(tmpOps.get(i));
if(i > 0 && i <= 18 && tmp.size() % 3 == 0){
ops.add(new ArrayList<>(tmp));
tmp.clear();
} else if(i > 18 && tmp.size() % k == 0){
ops.add(new ArrayList<>(tmp));
tmp.clear();
}
}
List<int[]> path = new ArrayList<>();
for(int i = 0; i <= 18; i++){
if(i % 3 == 0){
outer: for(int r = 0; r < scores.length; r++){
for(int c = 0; c < scores[r].length; c++){
if(scores[r][c] == sol.get(i)){
path.add(new int[]{r, c});
break outer;
}
}
}
}
}
for(int i = 19; i < sol.size(); i++){
if((i - 18) % k == 0){
outer: for(int r = 0; r < scores.length; r++){
for(int c = 0; c < scores[r].length; c++){
if(scores[r][c] == sol.get(i)){
path.add(new int[]{r, c});
break outer;
}
}
}
}
}
for(int[] i: path){
System.out.println(Arrays.toString(i));
}
visited[7][0] = true;
hasTower.get(11)[0] = 7;
hasTower.get(11)[1] = 0;
recurse(0, 1, ops, path, k, path.get(0)[0], path.get(0)[1], 1, 0, 1);
}
private static boolean outOfBounds(int r, int c){
return r < 0 || c < 0 || r >= 8 || c >= 8;
}
private static boolean towerAt(int r, int c){
int[] tower = hasTower.get(regions[r][c]);
return tower[0] == r && tower[1] == c;
}
private static boolean placeTower(int r, int c){
if(towerAt(r,c)) return true;
int[] tower = hasTower.get(regions[r][c]);
if(tower[0] != -1) return false;
tower[0] = r;
tower[1] = c;
return true;
}
private static void printBoard(int r, int c, int z, int k, int towers){
System.out.println("==================== " + (maxDepth - 1) + " ====================");
System.out.println(r + " " + c + " " + z + " k: " + k + " towers: " + towers);
for(int[] score: scores){
System.out.println(Arrays.toString(score));
}
for(boolean[] v: visited){
System.out.println(Arrays.toString(v));
}
for(int[] t: hasTower){
System.out.println(Arrays.toString(t));
}
}
}