Enigmatic Code

Programming Enigma Puzzles

Enigma 316: The min-factor game

From New Scientist #1464, 11th July 1985 [link]

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

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

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

Enigma 316

The picture records a game with N=7 and S=6. You did very well. Now try with N=30.

How small can you make S?

[enigma316]

Advertisements

5 responses to “Enigma 316: The min-factor game

  1. Jim Randell 23 October 2015 at 9:52 am

    This is similar to Enigma 295.

    This program recursively chooses a number to delete, but prunes away branches that can’t beat the current minimum. It runs in 41.6s.

    from enigma import irange, diff, Accumulator, printf
    
    import sys
    N = (30 if len(sys.argv) < 2 else int(sys.argv[1]))
    
    # ns - numbers remaining
    # ss - numbers taken
    # m - accumulator for min score
    def play(ns, ss, m):
      # find remaining numbers with divisors
      fs = list()
      for (i, n) in enumerate(ns):
        f = list(x for x in ns[:i] if n % x == 0)
        if f:
          fs.append(f + [n])
      # if there are no further plays
      s = sum(ss)
      if not fs:
        m.accumulate_data(s, ss)
        if s == m.value:
          printf("[{s} @ {ss}]")
      else:
        for f in fs:
          if s + f[-1] < m.value:
            play(diff(ns, f), ss + [f[-1]], m)
    
    m = Accumulator(fn=min, value=N * N)
    play(list(irange(1, N)), [], m)
    printf("[N={N}] min score = {m.value} @ {m.data}")
    

    Solution: The minimum score for N=30 is 103.

    One possible sequence is (13, 9, 15, 10, 8, 12, 14, 22).

  2. Julian Gray 23 October 2015 at 4:47 pm

    Jim, I think that taking 13 is an illegal move because the Devil can’t respond. Instead 26 can removed any time after 10 and 2. That makes N = 116.

  3. Brian Gladman 23 October 2015 at 8:56 pm

    Essentially the same approach.

    from sys import argv
    
    N = (30 if len(argv) < 2 else int(argv[1]))
    # the numbers to be considered
    nbrs = set(range(1, N + 1))
    # for the current minimum sum of the numbers taken
    s_min = N * (N + 1) // 2
    # pre-compute the divisors of each of the numbers
    div = {n:set(x for x in range(1, n + 1) if n % x == 0) for n in nbrs}
    
    # play a round in the game with the numbers remaining in 'nbrs',
    # the numbers picked so far in 'taken' and a dictionary of the
    # divisors of all the numbers in 'div' 
    def round(nbrs, taken):
      global s_min, div
      # find numbers in 'nbrs' with more than one divisor in 'nbrs'
      p = [n for n in nbrs if len(div[n] & nbrs) > 1]  
      # the game finishes if there are none
      if not p:
        yield taken
      else:
        # only consider numbers that can give a minimum sum less 
        # than the lowest minimum so far found
        n_max = s_min - sum(taken)
        # select a number to take
        for n in p:
          if n < n_max:
            # continue to the next round
            yield from round(nbrs - div[n], taken + [n])
    
    # find solutions for the game
    for taken in round(nbrs, []):
      s = sum(taken)
      # do we have a new minimum?
      if s < s_min:
        # if so output the sum and the values taken
        s_min = s
        print(s, taken)
    

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: