Introduction
This is the solution of the November’s Jane Street puzzle. It involves pentagons, patience and a lot of computation. Check out the original post on the Jane Street website.
The Puzzle
The scope of this puzzle is to find the minimum distance between two pentagons arranged in a polyform.
You have seventeen identical unit regular pentagonal tiles on a tabletop. You arrange them all into a single polyform, so each pentagon placed after the first shares a side with an already-placed pentagon, but no two pentagons overlap other than along their boundaries. What is the smallest nonzero distance you can create between two of the pentagons?
As an example, if you had to find this distance for four pentagons, the answer would be ~0.5877853, from the arrangement pictured above.
Solution
In order to solve this problem, I started to think about how to represent a sequence of pentagons. The way I went about it was to fix the first two pentagons and then starting to add the next on one of the four faces of the previous pentagon. In this way I could represent a sequence of pentagons as a sequence of integers from 2 to 5, where each integer represents the face of the previous pentagon that the next pentagon is added to. To represent the simple example with four pentagons, the sequence of integers would be [3, 2].
I also wanted to create visualizations of the polyforms that I would create. That would ensure I was on the right track and also help me to understand the problem better. I ended up choosing Python as the language to solve this problem.
Solving the problem with brute force would require cracking all possible sequences of integers from 2 to 5 with length 15 (remember that the first two pentagons are fixed). This would be equivalent to 4^15 = 1073741824 possible sequences (more tha 1 billion sequences!). There are however some things to keep in mind that would help reduce the number of sequences to consider:
- some sequences are equivalent to others in terms of minimum distance between pentagons, for example [3, 2] and [4, 5] are equivalent. This means that we can reduce the number of sequences to consider by half by considering only the sequences that start with 2 or 3.
- if we find that a pentagon is causing a collision (i.e. [2, 2, …]), we can stop considering the sequence that causes the collision and continue directly with the next one (in this case it would be [2, 3, …] and we would have skipped 4^13 ~ 67 million sequences)).
There are probably other ways to reduce the number of sequences to consider, but it is alway a trade between time spent coding and time spent running the code.
There are different sequences that lead to the same solution of 0.1387573, and this is one of them [2, 5, 2, 5, 2, 3, 4, 2, 5, 2, 3, 4, 2, 3, 5] which you can also see in the image below.
And this is the link to the solution from Jane Street Link
Final notes
This was a fun puzzle to solve. If I had to start from scratch, I would probably use C++ rather than Python, just to gain some speed in the computation and not having the laptop running for days…
You can also take a look at the code behind my solution on GitHub.
Do you want to take a look at more puzzles? Check out here