Enigmatic Code

Programming Enigma Puzzles

Enigma 1396: Magic planets

From New Scientist #2556, 17th June 2006

I have allocated distinct positive integers to the letters of the alphabet. By adding up the values of the letters in their names, I have obtained the following scores for some members of the solar system:

PLUTO 40,
URANUS 36,
NEPTUNE 29,
SATURN 33,
JUPITER 50,
MARS 32,
EARTH 31,
MOON 36,
VENUS 39,
MERCURY 33,
SUN 18.

Find the value of PLANETS.

[enigma1396]

Advertisements

2 responses to “Enigma 1396: Magic planets

  1. Jim Randell 1 September 2013 at 8:56 am

    I originally solved this when it was published in Perl, but using the choose() and permute() functions from Enigma 1729 the following Python code is a bit neater. It runs in 44ms.

    from itertools import permutations
    from enigma import irange, printf
    
    # choose n distinct numbers from s (ordered) that sum t
    def choose(n, t, s):
      # is it possible?
      if not(t > 0) or n > len(s): return
      # is there only one number?
      if n == 1:
        if t in s: yield (t,)
        return
      # choose a number from s and recurse
      for (i, a) in enumerate(s):
        if a + sum(s[i + 1:i + n - 1]) > t: break
        for x in choose(n - 1, t - a, s[i + 1:]):
          yield (a,) + x
    
    # permute the choices
    def permute(n, t, s):
      for x in choose(n, t, s):
        for y in permutations(x):
          yield y
    
    # allowable digits (MOON = 36)
    ds = set(irange(1, 32))
    
    # SUN = 18
    for (S, U, N) in permute(3, 18, list(irange(1, 15))):
      u1 = set((S, U, N))
      # URANUS = 36
      t = 36 - (U + N + U + S)
      for (R, A) in permute(2, t, list(n for n in irange(1, t - 1) if n not in u1)):
        # SATURN = 33
        T = 33 - (S + A + U + R + N)
        # MARS = 32
        M = 32 - (A + R + S)
        # MOON = 36
        (O, r) = divmod(36 - (M + N), 2)
        if r > 0: continue
        u2 = u1.union((R, A, T, M, O))
        if not(len(u2) == 8 and u2.issubset(ds)): continue
        # EARTH = 31
        t = 31 - (A + R + T)
        for (E, H) in permute(2, t, list(n for n in irange(1, t - 1) if n not in u2)):
          # VENUS = 39
          V = 39 - (E + N + U + S)
          # NEPTUNE = 29
          P = 29 - (N + E + T + U + N + E)
          # PLUTO = 40
          L = 40 - (P + U + T + O)
          u3 = u2.union((E, H, V, P, L))
          if not(len(u3) == 13 and u3.issubset(ds)): continue
          # MERCURY = 33
          t = 33 - (M + E + R + U + R)
          # C and Y can be interchanged, so just find a suitable pair
          for CY in choose(2, t, list(n for n in irange(1, t - 1) if n not in u3)):
            u4 = u3.union(CY)
            # JUPITER = 50
            t = 50 - (U + P + T + E + R)
            # I and J can be interchanged so just find a suitable pair
            for IJ in choose(2, t, list(n for n in irange(1, t - 1) if n not in u4)):
              # PLANETS = ?
              PLANETS = P + L + A + N + E + T + S
    
              printf("PLANETS={PLANETS} [S={S} U={U} N={N} R={R} A={A} T={T} M={M} O={O} E={E} H={H} V={V} P={P} L={L} CY={CY} IJ={IJ}]")
    

    Solution: PLANETS = 52.

    • Jim Randell 1 September 2013 at 10:04 am

      You can also solve this problem using a constraint based solver. Here I’ve used PyMathProg, (which links to GLPK to Python). It runs in 176ms.

      import pymprog
      from enigma import irange, printf
      
      # words and their totals
      words = (
        ('PLUTO', 40),
        ('URANUS', 36),
        ('NEPTUNE', 29),
        ('SATURN', 33),
        ('JUPITER', 50),
        ('MARS', 32),
        ('EARTH', 31),
        ('MOON', 36),
        ('VENUS', 39),
        ('MERCURY', 33),
        ('SUN', 18),
      )
      
      # indices for the grid
      numbers = list(irange(1, 32)) # max number is determined by MOON = 36
      letters = list('ACEHIJLMNOPRSTUVY')
      
      # create the model
      p = pymprog.model('enigma1396')
      
      # decision variable: x[l, n] = True if letter <l> is assigned number <n>
      x = p.var(pymprog.iprod(letters, numbers), 'x', bool)
      
      # constraints:
      
      # each letter is assigned to exactly one number
      p.st(sum(x[i, j] for j in numbers) == 1 for i in letters)
      # each number is assigned to at most one letter
      p.st(sum(x[i, j] for i in letters) <= 1 for j in numbers)
      # word constraints: sum of letters in the words match the totals 
      for (word, total) in words:
        p.st(sum(sum(j * x[l, j] for j in numbers) for l in word) == total)
      
      # solve the puzzle
      p.solve(int)
      
      # map letters to numbers
      l2n = dict((l, int(sum((j * x[l, j].primal) for j in numbers))) for l in letters)
      print('[' + ' '.join(k + '=' + str(l2n[k]) for k in sorted(l2n.keys())) + ']')
      
      # determine PLANETS
      PLANETS = sum(l2n[x] for x in 'PLANETS')
      printf("PLANETS={PLANETS}")
      

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: