May’s Ponder This challenge by IBM was considered quite difficult, it was only solved after five days1 and only sixteen people had solved it after a month.
And indeed finding an efficient algorithm to build an optimal solution seems quite difficult and I haven’t been able to do it yet2.
However to solve the challenge we don’t need our algorithm to be efficient or optimal as I will show you.
I’ve found the description of the problem a bit hard to understand, here is a version that I hope is simpler:
We have eight people and a boat, each of which can be on either banks of a river (That’s 512 possible configurations).
We can move from one configuration to another if it involves moving the boat across the river and one or two people with it.
With these rules the minimum number of trips to move everyone from one side to the other is 13.
Our goal is to find forbidden sets of people such that the minimum number of trips to move everyone without ever having a forbidden set on one bank becomes at least 73.
There are 256 possible sets of people however if a set is forbidden, its complement is forbidden too as it would correspond to the set of people on the other bank.
Hence we only need to decide which of the 128 sets containing the eighth person to forbid.
The first step in solving the challenge is to be able to compute the minimum number of trips given a set of forbidden sets.
This can be done with a simple BFS on the graph of configurations:
Armed with this we can try to forbid random sets and see what numbers we get:
After waiting for more than a minute, the best score I get is 15, not very promising.
Let’s try again using a different random distribution that emphasizes more extreme solutions (with lots of forbidden sets or very few):
This time, after a minute I reach a score of 31 which is much better but still far from our 73 target.
Instead of starting from scratch and generating a new random set of forbidden sets every time we should maybe try to improve our current set of forbidden sets.
Let’s start by allowing every set and then forbidding sets randomly.
If adding a new forbidden set makes it impossible to move everyone across the river then we revert back to the best known solution.
And if we get stuck and don’t make progress, we forget everything and restart from scratch:
Now I get a score of 37 after a minute.
Better but still not enough.
The problem is that when adding random forbidden sets, sometimes we add useful sets that increase the score of the solution and sometimes we add bad ones that prevent us from finding a better solution later.
To solve this problem we can try to find minimum sets of forbidden sets, sets where every element is useful.
For this we can go over every element of the set, see if removing it reduces the score and keep only the elements that would decrease the score if removed.
Now every time we find a new best solution we minimize it before trying to improve it:
This change yields a huge improvement and we now get scores above 73 in a few minutes.
Here is the final code:
I was the first one to solve it which I didn’t expect at all as the challenge is usually solved less than a day after it is posted online. ↩
And I am no longer actively searching so I will probably never find the optimal solution. ↩
You can send your comments to stuff at thomash dot fr.