Enigmatic Code

Programming Enigma Puzzles

Enigma 295: The max-multiple game

From New Scientist #1443, 14th February 1985 [link]

This is a game between you and the Angel. It starts with the natural numbers from 1 to N, written in a row. You and the Angel play alternately, you first. The rules are:

(a) You take any number you choose (subject to D below) from those remaining in the row, and delete it from the row.
(b) The Angel deletes from the numbers remaining in the row all these which are multiples of the number you just took.
(c) Go to (a).
(d) You can never take a number which has no multiple remaining in the row; that is, your take must permit the Angel in his turn to delete at least one number.

The games stops when you can legally take no more numbers, and you want the sum S of all the numbers you have take to be as large as possible.

Enigma 295

The picture records a game with N=9 and S=8. You could have done better. Now try with N=35. How large can you make S?

Also, today is (Spoiler Alert!) Cheryl’s Birthday!

[enigma295]

Advertisements

4 responses to “Enigma 295: The max-multiple game

  1. Jim Randell 16 July 2015 at 9:19 am

    This isn’t the fastest program, but it is short and it does find the maximum score. It plays the game recursively, eliminating choices that cannot beat the current maximum. For N=35 it takes 6m14s to run to completion (although it does find the maximum score after a few seconds). It should be possible to write a more sophisticated program that has shorter run times.

    from enigma import irange, diff, Accumulator, printf
    
    import sys
    N = (35 if len(sys.argv) < 2 else int(sys.argv[1]))
    
    # ns - numbers remaining
    # ss - numbers taken
    # s - sum(ss)
    # m - accumulator for max score
    def play(ns, ss, s, m):
    
      # are we done?
      if not ns:
        m.accumulate_data(s, ss)
        if s == m.value: printf("[{s} @ {ss}]")
        return
    
      # record multiples
      ms = dict((n, list(x for x in ns if x % n == 0)) for n in ns)
      # keys with more than one multiple
      ks = list(k for (k, v) in ms.items() if len(v) > 1)
      # can we beat the current value?
      if s + sum(ks) > m.value:
        # try each key
        for k in ks:
          play(diff(ns, ms[k]), ss + [k], s + k, m)
        
    
    # numbers that can be played
    ns = list(irange(N, 1, step=-1))
    
    m = Accumulator(fn=max, value=1)
    play(ns, [], 0, m)
    printf("[N={N}] max score = {m.value} @ {m.data}")
    

    Solution: The maximum score for N=35 is 145.

    One possible sequence is (17, 16, 15, 14, 13, 12, 10, 6, 9, 4, 2, 11, 3, 7, 5, 1).

    Overall there are 75,600 different sequences that produce a maximum score.

  2. Jim Randell 16 July 2015 at 10:31 am

    This program is much faster. For the N=35 case it runs in 40ms.

    It works by looking for a sequence that allows it to play all the numbers available. Clearly 1 must be played last, and we can’t play any number greater than N/2, so the only possible numbers that can be played before 1 are those from 2 to N/2. This program considers subsets of these numbers, in order of decreasing sum until it finds a playable sequence. And this is the maximum achievable total.

    from enigma import irange, printf
    
    # can we find a way to play all the numbers in <ms>?
    # ms - map numbers to remaining multiples
    # t - count of remaining numbers in the game
    # s - sequence played so far
    def play(ms, t, s):
    
      # are we done?
      if not ms:
        return (s if t > 0 else None)
    
      # look at how many remaining multiples each number has
      (n1s, ns) = ([], [])
      for (k, v) in ms.items():
        n = len(v)
        if n == 0:
          # numbers with no remaining multiples can never be played
          return None
        elif n == 1:
          n1s.append(k)
        else:
          ns.append(k)
      if n1s:
        # numbers with only 1 remaining multiple can be played immediately
        ns = n1s[0:1]
    
      # play one of the remaining numbers
      for n in ns:
        ds = ms[n].union([n])
        ms2 = dict()
        for (k, v) in ms.items():
          if k in ds: continue
          ms2[k] = v.difference(ds)
        # if this works return the sequence
        r = play(ms2, t - len(ds), s + [n])
        if r:
          return r
      else:
        return None
    
    # decompose <t> into a sequence of increasing numbers from <ns>
    def decompose(t, ns, m=0):
      if t == 0:
        yield []
      elif not(m > t):
        for n in ns:
          if m < n:
            for r in decompose(t - n, ns, n):
              yield [n] + r
    
    # find sequences which give the best score
    def solve(N):
      # 1 must be played last, so we don't consider it
    
      # map numbers from 2 to N/2 to higher multiples
      ns = list(irange(2, N // 2))
      ms0 = dict((n, set(irange(2 * n, N, step=n))) for n in ns)
      t0 = sum(ns)
    
      # consider increasing totals of deleted numbers
      for t in irange(0, t0):
        for ds in decompose(t, ns):
          printf("[considering t={t} ds={ds}]")
    
          # remove the deleted numbers
          ms = dict((k, v) for (k, v) in ms0.items() if k not in ds)
    
          # try to play all the remaining numbers
          r = play(ms, N - 1, [])
          if r:
            # and then play 1
            yield (t0 - t + 1, r + [1])
    
    
    import sys
    N = (35 if len(sys.argv) < 2 else int(sys.argv[1]))
    
    for (t, s) in solve(N):
      printf("[N={N}] max score = {t} {s}")
      break
    
  3. Brian Gladman 17 July 2015 at 12:56 pm

    This one was very interesting and I wonder if Stephen Ainley was being kind to puzzlers since 35 is the largest value for which a simple startegy of minimising the sum of the values removed by the Angel in each step works.

    from sys import argv
    from collections import defaultdict
    
    def play(moves, vals, N):
      # have we finished?
      if not vals:
        # if so yield our moves
        yield moves
      else:
        mx = max(vals)
        # save the maximum value I can remove for which the
        # Angel only removes one value
        max_ci, max_cv = None, None
        # consider my value, the Angel's values and the sum of
        # the Angel's values - map each Angel's sum to my 
        # values and the Angel's values
        d_sm = defaultdict(list)
        # for each value I can remove
        for i in (x for x in vals if x <= N // 2):
          # collect the Angel's values
          v = [x for x in range(2 * i, mx + 1, i) if x in vals]
          if v:
            # find the maximum value to remove for which the Angel
            # only removes one value
            if len(v) == 1:
              if max_ci is None or i > max_ci:
                max_ci, max_cv = i, [i] + v
            # keep values indexed on whether the Angel removes values
            # that I can remove and on the sum of the Angel's values
            d_sm[(min(v) <= N // 2), sum(v)] += [(i, [i] + v)]
        # first remove values for which the Angel only removes one value 
        if max_ci:
          t = [x for x in vals if x not in max_cv]
          yield from play(moves + [max_ci], t, N)  
        else:
          # consider other values sorted to minimise the removal of values that
          # that I could remove and then minimise the sum of the Angel's values
          for sm, l_iv in sorted(d_sm.items()):
            for i, v in l_iv:
              yield from play(moves + [i], [x for x in vals if x not in v], N)
    
    N = (35 if len(argv) < 2 else int(argv[1]))
    max_sm = None
    # look for solutions with a maximum sum
    for vals in play([], list(range(1, N + 1)), N):
      sm = sum(vals)
      if max_sm is None or sm > max_sm:
        max_sm = sm
        fs = 'N = {}, S = {} (of max {}) {}'
        print(fs.format(N, sm, sum(range(1, N // 2 + 1)), vals))
    
  4. arthurvause 21 July 2015 at 4:21 pm

    Brute force recursion plus memoization:

    def memoize(fn):
      stored_results = {}
    
      def memoized(*args):
        try:
          return stored_results[args]
        except KeyError:
          result = stored_results[args] = fn(*args)
          return result
     
      return memoized
    
    def play(remaining):
      if len(remaining)<2:
        return 0
      best=0
      largest = max(remaining)
      for x in remaining:
        if x <= largest/2:
          nextrem = set(remaining)-set(m*x for m in xrange(1,largest/x+1))
          if len(nextrem) < len(remaining) - 1:
            res = x + play(tuple(sorted(nextrem)))
            if res>best:
              best=res
      return best
    
    play = memoize(play)
    
    for N in xrange(6,40):
      print "N =",N, "S = ", play(tuple(range(1,N+1)))
    
    

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: