Jane Street's Puzzles October 2024: Knights Moves 6

You can find the problem statement to October’s puzzle here.

I initially wondered if there might be an interesting symmetry I could exploit to simplify the solution. However, after exploring a few ideas, I decided that a brute-force approach would be the most straightforward way to tackle it. As I progressed, though, it became clear that brute force alone wouldn’t be enough. I needed to optimize this approach to make it viable — and once I did, that’s what ultimately led me to a solution.

Rough Strategy

Looking at the puzzle, my first instinct was to break down the problem into several parts:

Path Generation: Find all the possible paths from a1 to f6, and a6 to f1 using an search algorithm like BFS or DFS.
Mirrored Paths: If we calculate the paths from a1 to f6, then to find the paths from a6 to f1 all we’d need to do is rotate those paths 90° clockwise you’d then have paths for a6 to f1.
Finding a solution: Each path would yield a score function. There’s two sets of score functions for each trip. For every combination of score functions, you’d test out values of $A$ , $B$ and $C$ and check if both score function equal 2024. If they do you have a valid solution.

Initial Approach

I began by implementing a straightforward, brute-force approach:

BFS Path Generation: Using BFS, I generated all possible paths from a1 to f6. For the second trip, I mirrored these paths, effectively creating routes for a6 to f1 by flipping the grid vertically - this is equivalent to the rotation, but much easier to calculate.
Scoring Each Path: After generating the paths, I calculated the score for each one making use of sympy a symbolic maths library. This made it very simple to handle to the algebra of generating the scoring functions.
Optimizing for Minimum $A + B + C$ : By iterating over all possible values for $A$ , $B$ , and $C$ , I looked for combinations that satisfied both paths and achieved the lowest sum.

While this method produced a valid solution, it was far from efficient. The main issues were:

Memory Constraints: BFS stored every single path as a list of lists, quickly consuming massive amounts of memory. In one run, memory usage reached over 32 GB, crashing my system.
Redundant Path Storage: I was storing multiple variations of paths that, despite their different sequences, yielded the same score function, resulting in excessive redundancy.
Nested Optimization Loops: Iterating over all combinations of score functions and then looping over possible values of $A$ , $B$ , and $C$ took substantial processing time.

In the end, while I did find a solution, it was clear this brute-force approach wouldn’t be practical for finding an optimal solution with the minimum $A + B + C$ . Optimization was necessary.

Optimized Approach

After reviewing the bottlenecks, I redesigned my approach to be significantly more efficient. Here’s how I tackled each problem area:

Switching to Depth-First Search (DFS): Rather than storing all paths at once with BFS, I implemented a depth-first search (DFS). This allowed me to calculate each path’s score function as soon as it was found. Paths were saved only if their score functions were unique, significantly reducing memory usage.
Generating Mirrored Paths Dynamically: Instead of storing separate paths for the second trip, I generated mirrored paths dynamically. By flipping the grid vertically, I could immediately derive the corresponding second path without doubling the stored path data.
Filtering Duplicate Score Functions: To eliminate redundant computations, I kept only the first instance of any score function. Since paths of the same length yield identical score functions, storing just one version per score saved on memory and processing.
Revised Value Combination Search: To streamline optimization, I changed the way I searched for $A$ , $B$ , and $C$ values:
- For each unique score function in the first set of paths from a1 to f6, I checked possible values of $A$ , $B$ , and $C$ to see which combinations equaled 2024.
- I repeated this for paths from a6 to f1.
- By taking the intersection of the valid $(A, B, C)$ combinations from both paths, I filtered out mismatches, leaving only those that met the criteria for both trips.

Results and Performance

With these optimizations, I reran the solution search, this time with a maximum path length of 15. The program completed in 11 minutes — a vast improvement over the initial run time. I achieved an optimal solution, with the minimum sum for $A + B + C$ that met the puzzle’s conditions.

Conclusion

Solving this puzzle highlighted the importance of both memory management and algorithmic efficiency. By switching from BFS to DFS, dynamically generating mirrored paths, and optimizing the combination search, I was able to find a precise and efficient solution. The experience underscored how small shifts in approach can yield substantial improvements in performance.

This challenge was a deep dive into the power of smart optimization for handling large search spaces, and I hope my approach provides insights for tackling similar algorithmic puzzles.