Enigmatic Code

Programming Enigma Puzzles

Enigma 1729: Xmas gifts

From New Scientist #2896, 22nd December 2012 [link]

I have given each letter of the alphabet a different whole-number value from 1 to 26. Therefore I can now work out the value of any word by adding up the values of its letters. For example, XMAS and GIFTS both make 34. It turns out that all the following words have the same value as each other: WE THREE KINGS OF ORIENT ARE.

What are the values of A, N, S, W, E and R?

This puzzle was published a day earlier than I was expecting. And I’d sort of been expecting something to do with taxi cabs for Enigma 1729.

[enigma1729]

Advertisements

17 responses to “Enigma 1729: Xmas gifts

  1. Jim Randell 18 December 2012 at 8:17 pm

    The following Python program is not particularly pretty, but it gets the answer (and the two possible methods of arriving at it) in 3.1s.

    from itertools import permutations
    from enigma import irange, printf
    
    # the common sum s is the sum of two letters (min 3, max 51)
    # but also the sum of 6 letters (min 21, max 141)
    # so it must be between 21 and 51
    
    ns = set(irange(1, 26))
    
    # W + E = s
    for (W, E) in permutations(ns, 2):
      s = W + E
      if s < 21: continue
      ns1 = ns.difference((W, E))
      
      # A + R + E = s = W + E, hence A + R = W
      for A in ns1:
        R = W - A
        ns2 = ns1.difference((A, R))
        if len(ns2) != 22: continue
    
        # T + H + R + E + E = s = A + R + E, hence T + H + E = A
        for T in ns2:
          H = A - (T + E)
          ns3 = ns2.difference((T, H))
          if len(ns3) != 20: continue
    
          # O + F = s
          for O in ns3:
            F = s - O
            ns4 = ns3.difference((O, F))
            if len(ns4) != 18: continue
    
            # O + R + I + E + N + T = s
            for I in ns4:
              N = s - (O + R + I + E + T)
              ns5 = ns4.difference((I, N))
              if len(ns5) != 16: continue
    
              # G + I + F + T + S = 34
              for G in ns5:
                S = 34 - (G + I + F + T)
                # K + I + N + G + S = s
                K = s - (I + N + G + S)
                ns6 = ns5.difference((G, S, K))
                if len(ns6) != 13: continue
    
                # X + M + A + S = 34
                for X in ns6:
                  M = 34 - (X + A + S)
                  if M == X or M not in ns6: continue
    
                  printf("A={A} N={N} S={S} W={W} E={E} R={R} [T={T} H={H} O={O} I={I} F={F} G={G} K={K} X={X} M={M}]")
    

    Solution: A=17 N=4 S=3 W=26 E=5 R=9.

    • Jim Randell 19 December 2012 at 11:03 am

      Here’s a slightly different approach, that works by constructing the possible sets of numbers of a certain length that sum to a certain number. It’s a bit more satisfying, and runs in 995ms, and I may be able to get it faster by tweaking the order the sums are considered in.

      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
      
      # generate permutations of the choices
      def permute(n, t, s):
        for x in choose(n, t, s):
          for y in permutations(x):
            yield y
      
      # remove elements from a that are in b (but maintain the order of a)
      def difference(a, b):
        return tuple(x for x in a if not x in b)
      
      ns = tuple(irange(1, 26))
      
      # the common sum is between 21 and 49, as 21 is the smallest sum with
      # 6 letters (ORIENT) and 49 is the largest sum from 2 letters two
      # different ways (OF and WE)
      
      for s in irange(21, 49):
        # WE = s, E < W
        for (E, W) in choose(2, s, ns):
          ns1 = difference(ns, (W, E))
          # ARE = s = WE, hence AR = W
          for (A, R) in permute(2, W, ns1):
            ns2 = difference(ns1, (A, R))
            # THREE = s
            for (T, H) in permute(2, s - (R + E + E), ns2):
              ns3 = difference(ns2, (T, H))
              # ORIENT = s
              for (O, I, N) in permute(3, s - (R + E + T), ns3):
                # OF = s
                F = s - O
                ns4 = difference(ns3, (O, I, N, F))
                if len(ns4) != 16: continue
                # GIFTS = 34
                for (G, S) in permute(2, 34 - (I + F + T), ns4):
                  # KINGS = s
                  K = s - (I + N + G + S)
                  ns5 = difference(ns4, (G, S, K))
                  if len(ns5) != 13: continue
                  # XMAS = 34
                  # X and M only appear in one sum, so can't be distinguished
                  for XM in choose(2, 34 - (A + S), ns5):
      
                    printf("[s={s}] A={A} N={N} S={S} W={W} E={E} R={R} [T={T} H={H} O={O} I={I} F={F} G={G} K={K} XM={XM}]")
      
      • Jim Randell 21 December 2012 at 12:42 pm

        As Peter Hayes points out on the New Enigma site, you can simplify the requirements to two equations that contain enough information to solve the puzzle. This adaptation of the above Python program runs in 696ms.

        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
        
        # generate permutations of the choices
        def permute(n, t, s):
          for x in choose(n, t, s):
            for y in permutations(x):
              yield y
        
        # remove elements from a that are in b (but maintain the order of a)
        def difference(a, b):
          return tuple(x for x in a if not x in b)
        
        ns = tuple(irange(1, 26))
        
        # ARE = ORIENT, subtracting RE: A = OINT
        # XMAS = 34, substituting for A: XMOINTS = 34
        
        # OF = ORIENT, subtracting O: F = RIENT
        # GIFTS = 34, substituting for F: GIRIENTTS = 34, GRE = 34 - IINTTS
        
        for (X, M, O, I, N, T, S) in permute(7, 34, ns):
          A = O + I + N + T
          ns1 = difference(ns, (X, M, O, I, N, T, S, A))
          if len(ns1) != 18: continue
          for (G, R, E) in permute(3, 34 - (I + I + N + T + T + S), ns1):
            s = A + R + E
            W = s - E
            H = s - (T + R + E + E)
            K = s - (I + N + G + S)
            F = s - O
            ns2 = difference(ns1, (G, R, E, W, F, K, H))
            if len(ns2) != 11: continue
        
            printf("[s={s}] A={A} N={N} S={S} W={W} E={E} R={R} [T={T} H={H} O={O} I={I} F={F} G={G} K={K} X={X} M={M}]")
        
        • geoffrounce 9 March 2016 at 10:23 am

          MiniZinc produced a simple, fast solution.
          It found 18 whole alphabet solutions in 149 msec.
          All the solutions for A,N,S,W,E,R were as found previously, with the variations in values occurring in the letters B,C,D and J

          % A MiniZinc solution
          include "globals.mzn";
          solve satisfy;
           
          var 1..26:A; var 1..26:B; var 1..26:C; var 1..26:D; var 1..26:E; 
          var 1..26:F; var 1..26:G; var 1..26:H; var 1..26:I; var 1..26:J; 
          var 1..26:K; var 1..26:L; var 1..26:M; var 1..26:N; var 1..26:O; 
          var 1..26:P; var 1..26:Q; var 1..26:R; var 1..26:S; var 1..26:T; 
          var 1..26:U; var 1..26:V; var 1..26:W; var 1..26:X; var 1..26:Y; 
          var 1..26:Z; 
          
          array[1..26] of var int : ALPHA = [A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,
          P,Q,R,S,T,U,V,W,X,Y,Z];
          
          constraint alldifferent (ALPHA);
          
          %  XMAS and GIFTS both make 34
          constraint X + M + A + S == 34 /\ G + I + F + T + S == 34;
          
          % WE, THREE, KINGS, OF, ORIENT, and ARE have the same value
          constraint W + E == T + H + R + E + E /\
          W + E == K + I + N + G + S /\ W + E == O + F /\
          W + E == O + R + I + E + N + T /\ W + E == A + R + E;
          
          output[show(ALPHA)];
          % For all outputs below:  (A,N,S,W,E,R) = (17,4,3,26,5,9)
          % GIFTS = 7+2+21+1+3 = 34,   XMAS = 6+8+17+3 = 34,  WE = 26+5 = 31, 
          % THREE = 1+11+9+5+5= 31    KINGS = 15+2+4+7+3 = 31,  
          % ORIENT = 10+9+2+5+4+1 = 31,  ARE = 17+9+5 = 31  
          % 18 whole alphabet solutions
          %   [ A   B   C   D  E   F  G   H  I   J   K  L   M  N   O   P   Q  R  S  T   U  V   W   X   Y  Z ]
          %1. [17, 25, 24, 23, 5, 21, 7, 11, 2, 22, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %2. [17, 24, 25, 23, 5, 21, 7, 11, 2, 22, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %3. [17, 25, 23, 24, 5, 21, 7, 11, 2, 22, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %4. [17, 23, 25, 24, 5, 21, 7, 11, 2, 22, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %5. [17, 24, 23, 25, 5, 21, 7, 11, 2, 22, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %6. [17, 23, 24, 25, 5, 21, 7, 11, 2, 22, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %7. [17, 25, 24, 22, 5, 21, 7, 11, 2, 23, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %8. [17, 24, 25, 22, 5, 21, 7, 11, 2, 23, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %9. [17, 25, 22, 24, 5, 21, 7, 11, 2, 23, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %10.[17, 22, 25, 24, 5, 21, 7, 11, 2, 23, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %11.[17, 24, 22, 25, 5, 21, 7, 11, 2, 23, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %12.[17, 22, 24, 25, 5, 21, 7, 11, 2, 23, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %13.[17, 25, 23, 22, 5, 21, 7, 11, 2, 24, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %14.[17, 23, 25, 22, 5, 21, 7, 11, 2, 24, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %15.[17, 25, 22, 23, 5, 21, 7, 11, 2, 24, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %16 [17, 22, 25, 23, 5, 21, 7, 11, 2, 24, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %17 [17, 23, 22, 25, 5, 21, 7, 11, 2, 24, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %18 [17, 22, 23, 25, 5, 21, 7, 11, 2, 24, 15, 20, 8, 4, 10, 19, 18, 9, 3, 1, 16, 14, 26, 6, 13, 12]
          %   [ A   B   C   D  E   F  G   H  I   J   K  L   M  N   O   P   Q  R  S  T   U  V   W   X   Y  Z ]
          % Finished in 149msec
          %
          
          
  2. Naim Uygun 19 December 2012 at 12:30 am
    import random
    value=list(range(1,27))
    while (True):
      random.shuffle(value)
      a=value[0]
      b=value[1]
      c=value[2]
      d=value[3]
      e=value[4]
      f=value[5]
      g=value[6]
      h=value[7]
      i=value[8]
      j=value[9]
      k=value[10]
      l=value[11]
      m=value[12]
      n=value[13]
      o=value[14]
      p=value[15]
      q=value[16]
      r=value[17]
      s=value[18]
      t=value[19]
      u=value[20]
      v=value[21]
      w=value[22]
      x=value[23]
      y=value[24]
      z=value[25]
      we=w+e
      if we <21 : continue
      
      three=t+h+r+e+e
      kings=k+i+n+g+s
      of=o+f
      orient=o+r+i+e+n+t
      are=a+r+e
      if three != kings or three != of or three != orient or three != are: continue
      if kings != of or kings != orient or kings != are: continue
      if of != orient or of !=are or orient != are : continue
      print(a,n,s,w,e,r)
      break
    input("The End")
    
    • Jim Randell 19 December 2012 at 11:07 am

      @Naim: Did you get this to run in a reasonable time? I think considering the possible permutations of the 15 letters we’re interested in would be a lot faster that just randomly shuffling the entire alphabet. But even that doesn’t seem like would be an approach that would find the answer in a reasonable time.

  3. Brian Gladman 19 December 2012 at 10:03 am

    Yes, a bit messy this week.

    from itertools import permutations
    
    # since A = O + I + N + T and O, I, N and T are different, A >= 10 
    for A in range(10, 27):
      # since W= A + R, W > A
      for W in range(A + 1, 27):
        R = W - A
        if R in (A, W):
          continue
        # since A = O + I + N + T, O, I and N are each <= A - 6 
        rest1 = set(range(1, A - 5)) - set((R, W))
        for O, I, N in permutations(rest1, 3):
          T = A - (O + I + N)
          rest2 = set(range(1, 27)) - set((A, W, R, O, I, N, T))
          if len(rest2) != 19:
            continue
          for E in rest2:
            # O + F = W + E and A = T + H + E
            F, H = W + E - O, A - T - E
            rest3 = rest2 - set((E, F, H))
            if len(rest3) != 16:
              continue
            # T + H + R+ E + E, O + F and A + R + E are equal
            three, of, are = T + H + R + 2 * E, O + F, A + R + E
            if not (three == of == are):
              continue
            for S in rest3:
              # G + I + F + T + S = 34
              G = 34 - (F + I + T + S)
              # O + F = K + I + N + G + S
              K = of - (I + N + G + S)
              rest4 = rest3 - set((S, G, K))
              if len(rest4) != 13:
                continue
              for M in rest4:
                # X + M + A + S = 34
                X = 34 - (M + A + S)
                if len(rest4 - set((K, M, X))) != 11:
                  continue
                # O + R + I + E + N + T = O + F
                if O + R + I + E + N + T == of:
                  print(A, N, S, W, E, R, '(', F, G, H, I, K, O, T, M, X, ')')
    
  4. arthurvause 19 December 2012 at 12:30 pm

    Not a particularly fast program:

    from itertools import permutations as perm
    
    perms=0
    for (o,r,i,e,n,t) in perm( range(1,27),6):
      perms+=1
      if perms%10000000==0:
        print "{:,}".format(perms), "perms"
      if o+r+i+n+t <= 26:
        orient = o+r+i+e+n+t
        orientset=set( (o,r,i,e,n,t) )
        w = orient - e
        h = orient - (t+r+e+e)
        f = orient - o
        a = orient - (r+e)
        if 1<=a<=26 and 1<=w<=26 and 1<=h<=26 and 1<=f<=26:
          if len(set((a,w,h,f,o,r,i,e,n,t)))== 10:
            for (g,s) in perm( set(range(1,27))- set( (o,r,i,e,n,t,a,w,f,h)),2):
              if g+i+f+t+s ==34:
                k = orient-(i+n+g+s)
                if 1<=k<=26 and k not in (o,r,i,e,n,t,a,w,f,h,g,s):
                  for (x,m) in perm( set(range(1,27))- set( (o,r,i,e,n,t,a,w,f,h,g,s,k)),2):
                    if x+m+a+s==34:
                      print (a,n,s,w,e,r), (a,e,f,g,h,i,k,m,n,o,r,s,t,w,x)
    
    • arthurvause 19 December 2012 at 4:10 pm

      Amazing what you can do with a bit of profiling:

      from itertools import permutations as perm
      
      alphabet = range(1,27)
      alphaset = set(alphabet)
      for (o,i,n,t) in perm(alphabet ,4):
        if (o+i+n+t)< 26:
          for (r,e) in perm( set(range(1,27-(o+i+n+t)))- set((o,i,n,t)),2):
            orient = o+r+i+e+n+t
            w = orient - e
            a = orient - (r+e)
            h = a - (t+e)
            f = orient - o
            if 1<=h<=26:
              if len(set((a,w,h,f,o,r,i,e,n,t)))== 10:
                for g in  range(1,min(27,34-(i+f+t))):
                  if g not in (o,r,i,e,n,t,a,w,f,h):
                    s=34-(g+i+f+t)
                    if s in alphaset and s not in (o,r,i,e,n,t,a,w,f,h,g):
                      k = orient-(i+n+g+s)
                      if 1<=k<=26 and k not in (o,r,i,e,n,t,a,w,f,h,g,s):
                        for x in range(1,min(27,34-(a+s))):
                          if x not in (o,r,i,e,n,t,a,w,f,h,g,s,k):
                            m=34-(x+a+s)
                            if m not in (o,r,i,e,n,t,a,w,f,h,g,s,k,x):
                                print (a,n,s,w,e,r), (a,e,f,g,h,i,k,m,n,o,r,s,t,w,x)
          
      
      • Brian Gladman 21 December 2012 at 8:18 pm

        Hi Arthur, How do you justify the maximum for r and e on line 7, i.e. 27 – (o+i+n+t)?

        • arthurvause 22 December 2012 at 9:52 am

          I got a few letters mixed up. The code should have been

          from itertools import permutations as perm
          
          alphabet = range(1,27)
          alphaset = set(alphabet)
          for (r,i,n,t) in perm(range(1,19) ,4):
            if (r+i+n+t)< 25:
              for (o,e) in perm( set(range(1,27-(r+i+n+t)))- set((r,i,n,t)),2):
                orient = o+r+i+e+n+t
                w = orient - e
                a = orient - (r+e)
                h = a - (t+e)
                f = orient - o
                if 1<=h and 1<=a:
                  awfhorient_set=set((a,w,h,f,o,r,i,e,n,t)) 
                  if len(awfhorient_set)== 10:
                    for g in  range(1,min(27,34-(i+f+t))):
                      if g not in awfhorient_set:
                        s=34-(g+i+f+t)
                        if s in alphaset and s not in (o,r,i,e,n,t,a,w,f,h,g):
                          k = orient-(i+n+g+s)
                          if 1<=k<=26 and k not in (o,r,i,e,n,t,a,w,f,h,g,s):
                            for x in range(1,min(27,34-(a+s))):
                              if x not in (o,r,i,e,n,t,a,w,f,h,g,s,k):
                                m=34-(x+a+s)
                                if m not in (o,r,i,e,n,t,a,w,f,h,g,s,k,x):
                                    print (a,n,s,w,e,r), (a,e,f,g,h,i,k,m,n,o,r,s,t,w,x)
          

          we=orient ⇒w=orint<=26
          ⇒ rint≤26 ⇒ no letter
          in rint >18

          w=orint<=26 ⇒o≤26-rint

          f=rint+e≤26 ⇒ e≤26-rint

          h=orient-tree=orint-tre, orint≤26 ⇒orint-tre=h≤26

          a=orient-re=oint. orint<=26 ⇒a=oint≤26

  5. Caroline 19 December 2012 at 3:03 pm

    What do you mean no taxis?

    We three kings of orient are
    One in a taxi, one in a car
    One on a scooter beeping his hooter

    🙂

  6. ahmet saracoğlu 19 December 2012 at 7:08 pm
      
    private int getIndex(char chr)
            {
                return chr - 'a';
            }
      private bool ConvertTo(int[] word,int []alphabet)
            {
                int i, sum = 0, index = 0, gifts = 34, xmas = gifts, ift = 0, gs = 0, kgs = 0,
                    g = 0, s = 0, x = 0, m = 0, xm = 0;
                int[] counter = new int[27];
                char [] orient={'o','r','i','e','n','t'};
    
    
                for (i = 0; i < 6; i++)
                    alphabet[orient[i] - 'a'] = word[i];
    
                for (i = 0; i = gifts)
                    return false;
                else gs = gifts - ift;
    
                kgs = sum - alphabet['i' - 'a'] - alphabet['n' - 'a'];
    
                index = getIndex('k');
    
    
                if (kgs > gs)
                    alphabet[index] = kgs - gs;
                else return false;
    
               
                if (gs < 3)
                    return false;
    
                bool goon=true;
                
                g = 1;
                while ((g < gs)&&(goon))
                {
                    s = gs - g;
                    if (counter[s] == 0)
                        goon = false;
                    else g++;
                }
    
                if (g == gs)
                    return false;
    
                goon=true;
                alphabet['s' - 'a'] = s;
                xm = xmas - alphabet['a' - 'a'] - alphabet['s' - 'a'];
    
                for (i = 0; i  0) && (alphabet[i] < 27))
                        counter[alphabet[i]]++;
    
                
                for (x = 1; x < 26 && x < xm&&goon; x++)
                {
                    m = xm - x;
                    if ((counter[m] == 0) && (counter[x] == 0))
                    {
                        goon = false;
                        alphabet['m' - 'a'] = m;
                        alphabet['x' - 'a'] = x;
                    }
                }
    
                if (goon)
                    return false;
    
               
                
                for (i = 0; i  1)
                        return false;
                
                return true;
    
            }
    
    int[] alph = new int[26];
                int [] orient = {1,2,3,4,5,6};
                
    
                while (!ConvertTo(orient, alph))
                {
                    ClearAlphabet(alph);
                    Increase(orient);
                   
                }
    
    • ahmet saracoğlu 19 December 2012 at 7:12 pm

      The algorithm is based upon “orient” word, and the word’s permutations are checked, and then some candidates are eliminated in order to satisfy the condition given in the problem.

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: