September 2025: Hooks 11

This was a classic Jane Street coding puzzle (well, coding at least seems necessary; if there’s a way to do this kind of puzzle without coding please let me know! Edit: thanks to Béla and Jette Rohloff for sharing their manual approach to solving this puzzle, which led to a solution in under three hours!) I was travelling when the puzzle was released, so I couldn’t be competitive on the leaderboard this month (and to be fair, I usually don’t place highly on this kind of puzzle anyway); instead, I decided to take my time and set myself the challenge of doing this month’s puzzle with no AI assistance. Usually, I determine how I want to approach this type of problem myself but then have ChatGPT do much of the heavy lifting when it comes to code writing, but this time I wanted to do things the old-fashioned way as an exercise in both coding and patience. Overall, this made a slightly boring (but still cool) puzzle a little more enjoyable, and I’m happy with what I was able to accomplish on my own.

Stats:

Difficulty: 6/10

Enjoyability: 5/10

Leaderboard Placing: 222/430

The approach:

The first thing to note is that it’s useful to think of hooks being placed from largest to smallest, from the outside of the board to the inside. At any given stage of placing hooks, one is faced with an \(n \times n\) subsquare of the original array, and one must place an \(n \times n\) hook in some corner of this subsquare as well as choose some number that will ultimately be placed in that hook. The first step in my solution was to write a backtracking algorithm to generate all valid choices of hook placements based on this principle (including the numbers associated with each hook). Accounting for the pre-placed numbers both within and on the border of the array, as well as the fact that not all hook-number associations are valid (e.g. the \(3 \times 3\) hook isn’t large enough to accommodate the number 6), the number of valid hook placements was on the order of 100.

From here, there were a couple of potential ways to proceed which stood out. One was to write another backtracking algorithm which, for each of the hook placements previously found, would decide on the locations of the filled squares within the hook, keeping those placements which didn’t violate conditions like the connectivity of the final collection of filled squares. Under this approach, the hope would be that there wouldn’t be too many valid choices, and one could attempt to realize a partition into pentominoes for each of the results either manually or somehow by some additional code. Some rough calculations showed that this approach, though easy to code, would likely be too computationally expensive. Feeling hopeful for an “easy” way out, I tried it anyway, but soon found that my suspicions were correct and it wouldn’t lead to anything useful in a reasonable amount of time.

The only option was then to fall back on the other approach which stood out, which was more computationally feasible but also significantly more painful to code. This approach was to recursively generate valid pentomino placements and superimpose them on the previously found hook placements to find a pair which satisfied all conditions. This was more computationally feasible since the pentomino information given on the border of the array significantly limits the pentomino placement possibilities, but was more painful since coding pentomino placements was tedious and required a lot of casework (among other issues). However, this approach ultimately worked without too much trouble, and led to the solution:

Note that in addition to the pentominoes necessitated by the border of the array, we’ve also used L, F, and T pentominoes (coloured lime green, navy, and purple respectively). We have several empty regions of area 1, one empty region of area 3, one empty region of area 4, one empty region of area 9, and one large empty region of area 15, giving the answer of \(3 \times 4 \times 9 \times 15 = 1620\).

As is usually true with this type of Jane Street puzzle, I don’t think I found anything close to the optimal way of reaching the solution. Regardless, this was a good coding exercise, and I had fun despite it taking much longer than I would have liked.