Posts Tagged ‘puzzle’
Sometime this week, I reread the first Harry Potter book (after at least 10 years… wow, has it been that long?), just for contrast after reading Rowling’s adult novel The Casual Vacancy (on which more later). Anyway, in the penultimate chapter there is a puzzle:
He pulled open the next door, both of them hardly daring to look at what came next — but there was nothing very frightening in here, just a table with seven differently shaped bottles standing on it in a line.
“Snape’s,” said Harry. “What do we have to do?”
They stepped over the threshold, and immediately a fire sprang up behind them in the doorway. It wasn’t ordinary fire either; it was purple. At the same instant, black flames shot up in the doorway leading onward. They were trapped.
“Look!” Hermione seized a roll of paper lying next to the bottles. Harry looked over her shoulder to read it:
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 forevermore,
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 onward, 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.
I became curious about whether this is just a ditty Rowling made up, or the puzzle actually makes sense and is consistent. It turns out she has constructed it well. Let’s take a look. This investigation can be carried out by hand, but we’ll be lazy and use a computer, specifically Python. The code examples below are all to be typed in an interactive Python shell, the one that you get by typing “python” in a terminal.
So what we have are seven bottles, of which one will take you forward (F), one will let you go back (B), two are just nettle wine (N), and three are poison (P).
>>> bottles = ['F', 'B', 'N', 'N', 'P', 'P', 'P']
The actual ordering of these 7 bottles is some ordering (permutation) of them. As 7 is a very small number, we can afford to be inefficient and resort to brute-force enumeration.
>>> import itertools >>> perms = [''.join(s) for s in set(itertools.permutations(bottles))] >>> len(perms) 420
set is needed to remove duplicates, because otherwise
itertools.permutations will print 7! “permutations”. So already the number of all possible orderings is rather small (it is ). We can look at a sample to check whether things look fine.
>>> perms[:10] ['PNFNPBP', 'NPPBNFP', 'FNNPBPP', 'PPPFNBN', 'NPPNBFP', 'PFNNBPP', 'NPBPPFN', 'NBNPPFP', 'NPPFBNP', 'BNPFNPP']
Now let us try to solve the puzzle. We can start with the first clue, which says that wherever a nettle-wine bottle occurs, on its left is always a poison bottle (and in particular therefore, a nettle-wine bottle cannot be in the leftmost position). So we must restrict the orderings to just those that satisfy this condition.
>>> def clue1(s): return all(i > 0 and s[i-1] == 'P' for i in range(len(s)) if s[i]=='N') ... >>> len([s for s in perms if clue1(s)]) 60
(In the code, the 7 positions are 0 to 6, as array indices in code generally start at 0.)
Then the second clue says that the bottles at the end are different, and neither contains the potion that lets you go forward.
>>> def clue2(s): return s != s and s != 'F' and s != 'F' ... >>> len([s for s in perms if clue1(s) and clue2(s)]) 30
The third clue says that the smallest and largest bottles don’t contain poison, and this would be of help to Harry and Hermione who can see the sizes of the bottles. But as we readers are not told the sizes of the bottles, this doesn’t seem of any help to us; let us return to this later.
The fourth clue says that the second-left and second-right bottles have the same contents.
>>> def clue4(s): return s == s ... >>> len([s for s in perms if clue1(s) and clue2(s) and clue4(s)]) 8
There are now just 8 possibilities, finally small enough to print them all.
>>> [s for s in perms if clue1(s) and clue2(s) and clue4(s)] ['PPNBFPN', 'BPNPFPN', 'BPFPNPN', 'BPPNFPN', 'PNPFPNB', 'BPNFPPN', 'PPNFBPN', 'PNFPPNB']
Alas, without knowing which the “dwarf” and “giant” bottles are, we cannot use the third clue, and this seems as far as we can go. We seem to have exhausted all the information available…
Almost. It is reasonable to assume that the puzzle is meant to have a solution. So even without knowing where exactly the “dwarf” and “giant” bottles are, we can say that they are in some pair of locations that ensure a unique solution.
>>> def clue3(d, g, s): return s[d]!='P' and s[g]!='P' ... >>> for d in range(7): ... for g in range(7): ... if d == g: continue ... poss = [s for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d,g,s)] ... if len(poss) == 1: ... print d, g, poss ... 1 2 PNFPPNB 1 3 PNPFPNB 2 1 PNFPPNB 2 5 PNFPPNB 3 1 PNPFPNB 3 5 PNPFPNB 5 2 PNFPPNB 5 3 PNPFPNB
Aha! If you look at the possible orderings closely, you will see that we are down to just two possibilities for the ordering of the bottles.
Actually there is some scope for quibbling in what we did above: perhaps we cannot say that there is a unique solution determining the entire configuration; perhaps all we can say is that the puzzle should let us uniquely determine the positions of just the two useful bottles. Fortunately, that gives exactly the same set of possibilities, so this distinction happens to be inconsequential.
>>> for d in range(7): ... for g in range(7): ... if d == g: continue ... poss = [(s.index('F'),s.index('B')) for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d,g,s)] ... if len(set(poss)) == 1: ... print d, g, [s for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d,g,s)] ... 1 2 PNFPPNB 1 3 PNPFPNB 2 1 PNFPPNB 2 5 PNFPPNB 3 1 PNPFPNB 3 5 PNPFPNB 5 2 PNFPPNB 5 3 PNPFPNB
Good. Note that there are only two configurations above. So with only the clues in the poem, and the assumption that the puzzle can be solved, we can narrow down the possibilities to two configurations, and be sure of the contents of all the bottles except the third and fourth. We know that the potion that lets us go forward is in either the third or the fourth bottle.
In particular we see that the last bottle lets us go back, and indeed this is confirmed by the story later:
“Which one will get you back through the purple flames?”
Hermione pointed at a rounded bottle at the right end of the line.
She took a long drink from the round bottle at the end, and shuddered.
But we don’t know which of the two it is, as we can’t reconstruct all the relevant details of the configuration. Perhaps we can reconstruct something with the remaining piece of information from the story?
“Got it,” she said. “The smallest bottle will get us through the black fire — toward the Stone.”
Harry looked at the tiny bottle.
Harry took a deep breath and picked up the smallest bottle.
So we know that the bottle that lets one move forward is in fact in the smallest one, the “dwarf”.
>>> for d in range(7): ... for g in range(7): ... poss = [s for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d,g,s)] ... if len(poss) == 1 and poss[d] == 'F': ... print d, g, poss ... 2 1 PNFPPNB 2 5 PNFPPNB 3 1 PNPFPNB 3 5 PNPFPNB
This narrows the possible positions of the smallest and largest bottles (note that it says the largest bottle is one that contains nettle wine), but still leaves the same two possibilities for the complete configuration. So we can stop here.
What we can conclude is the following: apart from the clues mentioned in the poem, the “dwarf” (the smallest bottle) was in either position 2 (third from the left) or 3 (fourth from the left). The biggest bottle was in either position 1 (second from the left) or 5 (sixth from the left). With this information about the location of the smallest bottle (and without necessarily assuming the puzzle has a unique solution!), Hermione could determine the contents of all the bottles. In particular she could determine the location of the two useful bottles: namely that the bottle that lets you go back was the last one, and that the one that lets you go forward was the smallest bottle.
>>> for (d,g) in [(2,1), (2,5), (3,1), (3,5)]: ... poss = [s for s in perms if clue1(s) and clue2(s) and clue4(s) and clue3(d, g, s)] ... assert len(poss) == 1 ... s = poss ... assert s.index('B') == 6 ... assert s.index('F') == d ... print (d,g), s ... (2, 1) PNFPPNB (2, 5) PNFPPNB (3, 1) PNPFPNB (3, 5) PNPFPNB
It is not clear why she went to the effort to create a meaningful puzzle, then withheld details that would let the reader solve it fully. Perhaps some details were removed during editing. As far as making up stuff for the sake of a story goes, though, this is nothing; consider for instance the language created for Avatar which viewers have learned.
See also http://www.zhasea.com/logic/snape.html which does it by hand, and has a perfectly clear exposition (it doesn’t try the trick of guessing that solution is unique before reaching for the additional information from the story).