Programming Enigma Puzzles
From New Scientist #2220, 8th January 2000 [link]
You play this game by first drawing 20 boxes in a continuous row. You then draw a star in each box in turn, in any order. Each time you draw a star you earn a score equal to the number of stars in the unbroken row [of stars] that includes the one you have just drawn.
Imagine that you have already drawn eleven stars as shown below, and you are deciding where to place the twelfth.
Drawing the next star in box 1 would score only 1 point, in box 11 it would score 2 points. A star in box 2, 5 or 6 would score 3 points, and in box 9, 12 or 19 it would score 4 points. Drawing the star in box 16 would score 6 points.
Your objective is to amass the lowest possible total for the 20 scores earned by drawing the 20 stars.
What is that minimum total?
This puzzle completes the archive of Enigma puzzles from 2000. There are now 1169 Enigma puzzles available on the site. There is a complete archive from the beginning of 2000 until the end of Enigma in December 2013 (14 years), and also from the start of Enigma in February 1979 up to January 1988 (10 years), making 24 years worth of puzzles in total. There are 623 Enigma puzzles remaining to post (from February 1988 to December 1999 – just under 11 years worth), so I’m about 62% of the way through the entire collection.
[enigma1064]
 | Frits on Enigma 764: Increasing de… |
| Frits on Enigma 764: Increasing de… |
 | Jim Randell on Enigma 764: Increasing de… |
 | GeoffR on BrainTwister #22: Even ro… |
| Jim Randell on BrainTwister #22: Even ro… |
| GeoffR on BrainTwister #22: Even ro… |
| Frits on BrainTwister #22: Even ro… |
| GeoffR on BrainTwister #22: Even ro… |
Enigmatic Code 
If we think about putting the final star in, then wherever we put it we are going to score 20 points in the final round, and if we are placing it in box i, then the will be a sequence of (i − 1) stars on the left of it, and (20 − i) stars on the right of it, and we want to choose i to minimise the total score involved in constructing these two sequences of stars.
This gives us a direct way to implement the function S(n), the minimum total score for a sequence of n boxes:
The following Python program gives us the required answer in 76ms.
Run: [ @repl.it ]
from enigma import irange, arg, cached, printf # calculate the minimal score for n boxes @cached def S(n): if n < 2: return n return n + min(S(i - 1) + S(n - i) for i in irange(1, n)) n = arg(20, 0, int) v = S(n) printf("S({n}) = {v}")Solution: The minimum total score for 20 boxes is 74.
We can also use the same technique to construct a sequence of moves that give the minimum score:
# find a minimal sequence of moves for boxes in sequence s def solve(s): n = len(s) # 0 or 1 boxes if n < 2: return s # find the best split point k = min(irange(1, n), key=lambda i: S(i - 1) + S(n - i)) - 1 # solve for left and right and add the split point return solve(s[:k]) + solve(s[k + 1:]) + [s[k]] s = solve(list(irange(1, n))) printf("sequence = {s}")The sequence found is presented below:
(I’ve used dashes instead of stars, and I’ve split out the left and right sides of the initial split point (08)).
The sequence S(n) appears in OEIS as A001855, where it is noted that:
which gives us an easy way to generate terms of S(n):
from itertools import count from enigma import first # generate sequence S(n) def generate(): t = 0 for i in count(1): yield t t += i.bit_length() s = first(generate(), n + 1) printf("S[0..{n}] = {s}")And we can get the answer to the problem using a single Python expression:
I hope this web site recognizes the HTML commands for superscript and subscript; if not, the following will be a mess:
If m = int{log2(n + 1)} + 1 then Sn = m(n + 1) − 2^m + 1.
If you are familiar with using LaTeX for typesetting equations, you can use that on WordPress by surrounding the LaTeX expressions with [[
$latex <LaTeX code here> $]] (see [ https://en.support.wordpress.com/latex/ ].So we would get:
If:
then:
(Although it’s easy for me, because I can edit comments – a facility that is sadly not available to normal commenters in WordPress).
Thanks for tidying it up, Jim. I did once take a look at LaTeX — in the 1980s, I think.
These days MS Word’s equation editor serves me well enough. I could export the result as a GIF or PNG image, but don’t know whether I could build that into a comment here.