Enigmatic Code

Programming Enigma Puzzles

Enigma 1064: Low score draw

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]

4 responses to “Enigma 1064: Low score draw

  1. Jim Randell 30 April 2018 at 8:14 am

    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:

    S(0) = 0
    S(1) = 1
    S(n) = n + min(S(i – 1) + S(n – i) for i = 1..n)

    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:

                                                                   pts  tot
    (01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20)    0    0
    (-- 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20)    1    1
    (-- 02 -- 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20)    1    2
    (-- -- -- 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20)    3    5
    (-- -- -- 04 -- 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20)    1    6
    (-- -- -- 04 -- 06 -- 08 09 10 11 12 13 14 15 16 17 18 19 20)    1    7
    (-- -- -- 04 -- -- -- 08 09 10 11 12 13 14 15 16 17 18 19 20)    3   10
    (-- -- -- -- -- -- -- 08 09 10 11 12 13 14 15 16 17 18 19 20)    7   17
    
    (-- -- -- -- -- -- -- 08 -- 10 11 12 13 14 15 16 17 18 19 20)    1   18
    (-- -- -- -- -- -- -- 08 -- 10 11 -- 13 14 15 16 17 18 19 20)    1   19
    (-- -- -- -- -- -- -- 08 -- 10 -- -- 13 14 15 16 17 18 19 20)    2   21
    (-- -- -- -- -- -- -- 08 -- -- -- -- 13 14 15 16 17 18 19 20)    4   25
    (-- -- -- -- -- -- -- 08 -- -- -- -- 13 -- 15 16 17 18 19 20)    1   26
    (-- -- -- -- -- -- -- 08 -- -- -- -- 13 -- 15 -- 17 18 19 20)    1   27
    (-- -- -- -- -- -- -- 08 -- -- -- -- 13 -- -- -- 17 18 19 20)    3   30
    (-- -- -- -- -- -- -- 08 -- -- -- -- 13 -- -- -- 17 -- 19 20)    1   31
    (-- -- -- -- -- -- -- 08 -- -- -- -- 13 -- -- -- 17 -- 19 --)    1   32
    (-- -- -- -- -- -- -- 08 -- -- -- -- 13 -- -- -- 17 -- -- --)    3   35
    (-- -- -- -- -- -- -- 08 -- -- -- -- 13 -- -- -- -- -- -- --)    7   42
    (-- -- -- -- -- -- -- 08 -- -- -- -- -- -- -- -- -- -- -- --)   12   54
    
    (-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --)   20   74

    (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:

    S(n) = the number of digits in the binary representation of the numbers from 1 to (n – 1)

    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:

    >>> sum(int.bit_length(i) for i in irange(1, 20))
    74
    
  2. Hugh Casement 1 May 2018 at 11:58 am

    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.

    • Jim Randell 1 May 2018 at 12:48 pm

      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:

      m = int(log_2(n + 1)) + 1

      then:

      S_n = m(n + 1) - 2^m + 1

      (Although it’s easy for me, because I can edit comments – a facility that is sadly not available to normal commenters in WordPress).

  3. Hugh Casement 1 May 2018 at 2:37 pm

    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.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: