EN
by Tim Varelmann
Anyone who has read the book "Harry Potter and the Philosopher's Stone" knows that after the chess game enchanted by Professor McGonagall, further challenges await Harry and Hermione before they can get to the Philosopher's Stone and bring Ron, who has been knocked out by the white chess queen, to the hospital wing: After a fortunately already unconscious troll, the two have to solve a potions riddle from Professor Snape: they are standing in front of a table with 7 different bottles, when suddenly a black fire in front of them blocks the path to the Philosopher's Stone and a purple fire blocks the way back to Ron. Next to the bottles is a parchment with the following riddle:
Danger lies before you, while safety lies behind,
Two of us will help you, whichever you would find,
One among us seven will let you move ahead,
Another will transport the drinker back instead,
Two among our number hold only nettle wine,
Three of us are killers, waiting hidden in line.
Choose, unless you wish to stay here for evermore,
To help you in your choice, we give you these clues four:
First, however slyly the poison tries to hide
You will always find some on nettle wine's left side;
Second, different are those who stand at either end,
But if you would move onwards neither is your friend;
Third, as you see clearly, all are different size,
Neither dwarf nor giant holds death in their insides;
Fourth, the second left and the second on the right
Are twins once you taste them, though different at first sight.
J. K. Rowling, Harry Potter and the Philosopher's Stone
In the book, Hermione solves this puzzle with her magical brilliance. For Muggles like me, who have still been waiting for their invitation to Hogwarts since their 11th birthday, the only option is to get help from the computer. Genius, these muggles!
The first task in formulating an optimization problem - in both the real and the magical world - is to clear up misunderstandings through clear communication. The "if you would move onwards" part in the second clue sounds to some - including myself - like it refers to the neighbors of the previously mentioned bottles. However, when I had read all four clues, I noticed that not a single clue helps to distinguish the potion that leads safely through the black fire from the potion that leads safely through the purple fire. In the book, on the other hand, Hermione confidently chooses which potion leads through which fire. So, I must have misunderstood the problem somewhere and did what any good programmer does when he gets stuck. I googled for Snape's riddle. It turns out that the clue really means that neither of the two bottles at the end contains the potion to move onwards, i.e. the potion leading through the black fire.
Now, we can finally translate the magic riddle into the language of computers. To do this, we specify a whole set of decisions that the computer should make and give it a bunch of conditions that it has to fulfill: We have 4 different contents: 3x poison, 2x nettle wine, 1x purple fire potion and 1x black fire potion and want to find out at which of the 7 positions we find which bottle content. We therefore give the computer four decisions for each position, which it has to answer with 'Yes' or 'No'. Is there poison in this position? Is there nettle wine in this position? Is there purple fire potion in this position? Is there black fire potion in this position?
Since a computer understands math better than text, we program the computer to create so-called binary variables. These are variables to which it can assign either the value 1 or the value 0. The 1 corresponds to the answer 'Yes', the 0 corresponds to the answer 'No'. We number the positions p, from 1 (leftmost bottle) to 7 (rightmost bottle), and abbreviate the contents i, with the letters D for death (poison), N for nettle wine, P for purple fire potion, and B for black fire potion. To allow the computer to make a decision, we introduce binary variables V for the bottle decisions. We use the small letters p and c to indicate the position and content of the decision.
Thus, the variable V1,D represents the decision "Is there poison at position 1?".
Since we now let the computer make 28 decisions (4x 'Yes'/'No' at 7 positions), we also have to give it special conditions on how these decisions are to be made. And before we can translate the clues from Snape's puzzle into math, we must first prevent the computer from making gross nonsense with its 28 decisions. It would be gross nonsense, for example, if a position contained poison and nettle wine at the same time. On the other hand, the computer could answer all decisions in another position with 'No', which also falls into the category of gross nonsense. We therefore ask the computer to adhere to the following conditions:
For each position, we now answer exactly one of our 4 questions with 'Yes'. This is better, but still allows some nonsense, for example answering the question about the nettle wine with 'Yes' in every position. We therefore add further conditions:
Now the computer must answer 'Yes' to the question about the poison in exactly 3 positions, must answer 'Yes' to the question about the nettle wine in exactly 2 positions, and so on...
We can now model the individual clues of the puzzle:
We translate this clue into two parts: the leftmost bottle and all the others. For the leftmost bottle, we simply demand: it cannot contain any nettle wine because there is no room for poison to the left of it.
If there is nettle wine in another position, there must be poison to the left of it. Since the value for the poison decision can only be 0 or 1, the greater-than-equal condition forces a 1 for poison if the right neighbor has a 1 for nettle wine. However, there does not have to be a nettle wine to the right of every poison (after all, there are only two). The latter would also be required if we were to use an equal sign in the condition.
Here, too, we divide the clue into two parts, as the two parts of the sentence each contain a clue. In the first part, we require for each content that only one of bottles 1 and 7 may be answered with 'Yes' for this content. This prohibits bottles 1 and 7 from having the same content, because then, the decision for this same content would have to be 'Yes' (=1) in both positions, and the sum of both decisions would become 2.
The second part completely prohibits the black fire potion for bottles 1 and 7. Here, it pays off that we use 0 and 1 to calculate instead of 'Yes' and 'No'. We can add up the binary variables and demand that the sum must be zero. This one requirement can only be fulfilled if both values are 0, i.e. the question about the black fire potion is answered with 'No' at both positions. So, although we had one requirement for position 1 and another requirement for position 7, it is sufficient to formulate only one condition.
It would also have been possible to split this condition into 2 conditions in order to answer the respective decision "Is black fire potion in position 1?" and "Is black fire potion in position 7?" individually with 'No' or to set the respective variable to 0. However, the computational effort for the computer is generally lower if it has to fulfill fewer conditions, which is why the sum formulation is very elegant.
On closer inspection, it is also noticeable that the first part of clue 2 had already placed a condition on the sum of the decisions "Is black fire potion in position 1?" and "Is black fire potion in position 7?", namely that the sum must be less than or equal to 1. However, as soon as the second condition, that this sum must be 0, is fulfilled, the previous condition is of course also always fulfilled. Because we only want to set a few conditions for the computer, we only require the first condition of clue 2 for the contents poison, nettle wine, and purple fire potion, but not black fire potion:
While Hermione can see the bottles on the table in front of her, we can only speculate where the largest and the smallest bottle are. We therefore use placeholders G for the giant and d for the dwarf to formulate the conditions for the computer now and come back to the problem of where the giant and dwarf are later:
Again, we have formed a sum to define two decisions with only one condition, namely that the decision for poison must be 'No' for both the giant and the dwarf.
For each content, the decision at positions 2 and 6 must therefore be the same - either both decisions are 'No', or both decisions are 'Yes'.
Don't forget: We have already demanded that the decision for exactly one content must be answered with 'Yes' at each position, so it cannot happen that we have poison and nettle wine on positions 2 and 6 at the same time. A human also has the intuition that neither the black fire potion nor the purple fire potion can be placed in position 2 or 6, because both only exist once and therefore cannot have twins. Is the computer also aware of this? It is, because the computer also knows the condition that the sum of black fire potion variables across all 7 positions must be exactly 1 and that the sum of purple fire potion variables across all 7 positions must be exactly 1. The only possibility to satisfy all conditions, is that some bottle in positions different from 2 and 6 contain the black fire potion and the purple fire potion.
We have now completely modeled the problem. With the right software that can solve the problem, the computer can now find out which bottles have which contents at which positions. To do this, however, we still need to specify where the giant and dwarf are located. It is crucial to note that the riddle is unambiguously solvable for Hermione in the book, because she can see where giant and dwarf are located. We do not have this information. Thus, we attempt to solve a bigger problem: We are not only interested what the solution to Snape's riddle is, but we also want to see what Harry and Hermione see at the table in front of them. To find this out, we have 2 options, which are also frequently used for optimization problems in the muggle world: Brute computational force and clever looking around.
The brute force method means trying out all the possibilities. The giant can be in one of 7 positions. If the giant is fixed, there are still 6 other positions where the dwarf could stand, as each bottle is different in size. This means that we would have to solve 7*6=42 single optimization problems. This would be possible for our small optimization problem.
On closer inspection, however, this would be too much effort: What the dwarf and what the giant is, is unimportant for the optimization problem. The decisive factor is that there can be no poison in either position. For example, if we were to solve the optimization problem with the giant at position 1 and the dwarf at position 2, there can be no poison at positions 1 and 2. However, if we were to place the dwarf in position 1 and the giant in position 2, there can also be no poison in positions 1 and 2. Mathematicians speak of symmetry in such a situation: the problem is symmetrical with regard to the positions of giant and dwarf. If you pay attention to symmetry, you can take advantage of this property to save yourself computational work: Here, we only work out the solution if the giant is to the left of the dwarf. Then, all the different possibilities are unique, and we know that we could swap the position of the giant and dwarf each time without changing the solution once it has been calculated. This means that we have to solve fewer problems, as the following table illustrates:
This leaves 21 scenarios for which we solve the puzzle through optimization. Some of the scenarios may not have a solution at all.
As an example, lets consider the case where we place giant and dwarf in positions 1 and 2: then, according to clue 3, there can be no poison in position 1 and in position 2. According to clue 4, the bottles in positions 2 and 6 are twins. In our example, the twins have to be nettle wines, because poison cannot be in position 2 (giant/dwarf rule), and both black fire potion and purple fire potion can not have twins. However, clue 1 requires that poison must be to the left of nettle wine. Since we placed the two nettle wines is in positions 2 and 6, then poison would have to be in position 1 and 5 to satisfy clue 1. However, position 1 is the giant or the dwarf, thus must not contain poison due to clue 3.
This shows that when dwarf and giant are in positions 1 and 2, we would not be able to fulfill clues 1, 3 and 4 at the same time. This means that the position of giant and dwarf can not be 1 and 2, because Hermione solved the riddle. Such a situation is shown in the solution table with dashes. On the other hand, there are also scenarios where several solutions can fulfill all conditions. In this case, I have shown one solution in the table and placed one asterisk after the specification of giant and dwarf for each possible alternative solution:
With optimization problems in the Muggle world, it is quite normal for some information to be missing, unclear, or contradictory. Then, it helps to talk to lots of different people, show and explain small prototypes and listen carefully to what employees, customers and managers say if possible. And even in the magical world, we can find a few more small clues by carefully reading what is happening around the puzzle:
When Hermione had solved the riddle, she said to Harry, "I've got it. The smallest bottle will take us through the black fire." Harry then asks which one leads back through the purple flames, and Hermione "pointed to a bulbous bottle at one end of the row".
We could now incorporate this information into our model. For example, we could reformulate the condition that exactly one purple fire potion exists, and instead of summing over all positions, only sum positions 1 and 7 and allow no purple fire potion at all for positions 2-6.
On the other hand, the new clues do not clearly indicate where the giant and dwarf are placed. On the contrary: the information that the Black Fire Potion is in the smallest bottle is only helpful if we have already determined the position of the dwarf. Therefore, we have to use a bit of brute force anyway to find out exactly how Harry and Hermione had to guess. Furthermore, this condition breaks the symmetry because there is now more information in the dwarf than in the giant, whose contents we only know are not poison.
Instead of the asymmetrical calculation, we can go back through the solutions from the previous section and delete all those in which the purple fire potion is neither in position 1 nor in position 7 as unPOTTERable. Also, the black fire potion must be the dwarf. If the black fire potion is the giant, we can swap the positions of the giant and dwarf from the table of symmetrical solutions in order to still find a POTTERable solution. Finally, we can assume that the solution is unambiguous because Hermione can confidently assign which potion is where. Therefore, we can also delete all scenarios that had one or more stars, i.e. possible alternative solutions. This leaves us with the following solutions:
So for the next Potter fan party, this puzzle still gives you several scenarios to choose from that match the description in the book. However, the giant must always be one of the twins, and the only difference in the contents of the bottles depends on whether the dwarf is in position 3 or 4.
We have seen that magic and non-magic optimization problems use mathematics to translate complicated decisions in a way that the computer can understand. It is crucial to recognize and eliminate communication difficulties. Sometimes, clever use of mathematical properties makes it possible to represent several conditions in the real world as one mathematical condition - this saves computational effort, as does recognizing and exploiting symmetry in the problem. After all, despite all due care, it can happen that not all information or data is available. With a properly formulated optimization problem, we can still find ways and means to arrive at one or more satisfactory solutions.
If you want to experiment further, you can find my implemented models in the public repositories for GAMS and Pyomo.
And if you would like more digital and intelligent support from your computer for your decisions, let me know.
Thanks to Maren Varelmann for proofreading this article and giving valuable suggestions.
