S2T2

Jim Randell 10:36 am on 8 October 2020 Permalink Reply
Tags: by: Victor Bryant ( 139 )   

• 

  Jim Randell 10:37 am on 8 October 2020 Permalink | Reply

  (See also: Teaser 2756, Enigma 1602).

  This Python program checks to see if each symbol can be assigned a value that is a multiple of 25p to make the required 10 words correct (and also checks that the remaining two words are wrong).

  Instead of treating the letters G, H, R, U separately, we treat them as GH, HR, UR, which reduces the number of symbols to consider by 1.

  The program runs in 413ms.

  Run: [ @repl.it ]

  from enigma import (irange, subsets, update, unpack, diff, join, map2str, printf)
  
  # <value> -> <symbol> mapping
  words = {
    100: ("O", "N", "E"),
    200: ("T", "W", "O"),
    300: ("T", "HR", "E", "E"),
    400: ("F", "O", "UR"),
    500: ("F", "I", "V", "E"),
    600: ("S", "I", "X"),
    700: ("S", "E", "V", "E", "N"),
    800: ("E", "I", "GH", "T"),
    900: ("N", "I", "N", "E"),
    1000: ("T", "E", "N"),
    1100: ("E", "L", "E", "V", "E" ,"N"),
    1200: ("T" ,"W", "E", "L", "V", "E"),
  }
  
  # decompose t into k numbers, in increments of step
  def decompose(t, k, step, ns=[]):
    if k == 1:
      yield ns + [t]
    elif k > 1:
      k_ = k - 1
      for n in irange(step, t - k_ * step, step=step):
        yield from decompose(t - n, k_, step, ns + [n])
  
  # find undefined symbols and remaining cost
  def remaining(v, d):
    (us, t) = (set(), v)
    for x in words[v]:
      try:
        t -= d[x]
      except KeyError:
        us.add(x)
    return (us, t)
  
  # find values for vs, with increments of step
  def solve(vs, step, d=dict()):
    # for each value find remaining cost and undefined symbols
    rs = list()
    for v in vs:
      (us, t) = remaining(v, d)
      if t < 0 or bool(us) == (t == 0): return
      if t > 0: rs.append((us, t, v))
    # are we done?
    if not rs:
      yield d
    else:
      # find the value with the fewest remaining symbols (and lowest remaining value)
      (us, t, v) = min(rs, key=unpack(lambda us, t, v: (len(us), t)))
      # the remaining values
      vs = list(x for (_, _, x) in rs if x != v)
      # allocate the unused symbols
      us = list(us)
      for ns in decompose(t, len(us), step):
        # solve for the remaining values
        yield from solve(vs, step, update(d, us, ns))
  
  # choose the 2 equations that are wrong
  for xs in subsets(sorted(words.keys()), size=2):
    # can't include FOUR
    if 400 in xs: continue
    # find an allocation of values
    for d in solve(diff(words.keys(), xs), 25):
      xvs = list(sum(d[s] for s in words[x]) for x in xs)
      if all(x != v for (x, v) in zip(xs, xvs)):
        # output solution
        wxs = list(join(words[x]) for x in xs)
        printf("wrong = {wxs}", wxs=join(wxs, sep=", ", enc="[]"))
        printf("-> {d}", d=map2str(d, sep=" ", enc=""))
        for (x, xv) in zip(wxs, xvs):
          printf("  {x} = {xv}p")
        printf()
        break
  

  Solution: NINE and TEN do not cost an amount equal to their number.

  One way to allocate the letters, so that ONE … EIGHT, ELEVEN, TWELVE work is:

  25p = F, H, N, O, T
  50p = E, X
  150p = W, R
  200p = I, U
  225p = V
  350p = S
  500p = G
  700p = L

  (In this scheme: NINE costs £3 and TEN costs £1).

  But there are many other possible assignments.

  You can specify smaller divisions of £1 for the values of the individual symbols, but the program takes longer to run.

  It makes sense that NINE and TEN don’t cost their value, as they are short words composed entirely of letters that are available in words that cost a lot less.

  ---

  Here’s a manual solution:

  We note that ONE + TWELVE use the same letters as TWO + ELEVEN, so if any three of them are correct so is the fourth. So there must be 0 or 2 of the incorrect numbers among these four.

  Now, if ONE and TEN are both correct, then any number with value 9 or less with a T in it must be wrong. i.e. TWO, THREE, EIGHT. Otherwise we could make TEN for £10 or less, and have some letters left over. And this is not possible.

  If ONE is incorrect, then the other incorrect number must be one of TWO, ELEVEN, TWELVE, and all the remaining numbers must be correct. So we could buy THREE and SEVEN for £10, and have the letters to make TEN, with EEEHRSV left over. This is not possible.

  So ONE must be correct, and TEN must be one of the incorrect numbers.

  Now, if NINE is correct, then any number with value 7 or less with an I in it must be incorrect. Which would mean FIVE and SIX are incorrect. This is not possible.

  Hence, the incorrect numbers must be NINE and TEN.

  All that remains is to demonstrate one possible assignment of letters to values where NINE and TEN are incorrect and the rest are correct. And the one found by the program above will do.

  LikeLike

• 

  GeoffR 6:36 pm on 8 October 2020 Permalink | Reply

  I used a wide range of upper .. lower bound values for letter variables.

  The programme would not run satisfactorily under the Geocode Solver, but produced a reasonable run time under the Chuffed Solver. It confirmed the incorrect numbers were NINE and TEN.

  % A Solution in MiniZinc
  include "globals.mzn";
   
  var 10..900:O; var 10..900:N; var 10..900:E; var 10..900:T;
  var 10..900:W; var 10..900:H; var 10..900:R; var 10..900:F;
  var 10..900:U; var 10..900:V; var 10..900:I; var 10..900:L;
  var 10..900:G; var 10..900:S; var 10..900:X;
  
  constraint sum([
  O+N+E == 100, T+W+O == 200, T+H+R+E+E == 300, F+O+U+R == 400,
  F+I+V+E == 500, S+I+X == 600, S+E+V+E+N == 700,
  E+I+G+H+T == 800, N+I+N+E == 900, T+E+N == 1000,
  E+L+E+V+E+N == 1100, T+W+E+L+V+E == 1200]) == 10;
  
  solve satisfy;
  
  output [" ONE = " ++ show (O + N + E) ++
  "\n TWO = " ++ show (T + W + O ) ++
  "\n THREE = " ++ show (T + H + R + E + E) ++
  "\n FOUR = " ++ show (F + O + U + R) ++
  "\n FIVE = " ++ show (F + I + V + E) ++
  "\n SIX = " ++ show (S + I + X) ++
  "\n SEVEN = " ++  show (S + E + V + E + N) ++
  "\n EIGHT = " ++ show (E + I + G + H + T) ++
  "\n NINE = " ++ show (N + I + N + E) ++
  "\n TEN = " ++ show (T + E + N) ++
  "\n ELEVEN = " ++ show (E + L + E + V + E + N) ++
  "\n TWELVE = " ++ show (T + W + E + L + V + E) ++
  "\n\n [O N E T W H R F U V I L G S X = ]" ++ 
  show([O, N, E, T, W, H, R, F, U, V, I, L, G, S, X]) ];
  
  %  ONE = 100
  %  TWO = 200
  %  THREE = 300
  %  FOUR = 400
  %  FIVE = 500
  %  SIX = 600
  %  SEVEN = 700
  %  EIGHT = 800
  %  NINE = 171   << INCORRECT
  %  TEN = 101    << INCORRECT
  %  ELEVEN = 1100
  %  TWELVE = 1200
  %  Letter Values (One of many solutions)
  %  [O    N   E   T   W    H   R    F   U    V    I   L    G    S    X = ]
  %  [10, 71, 19, 11, 179, 13, 238, 10, 142, 461, 10, 511, 747, 130, 460]
  %  time elapsed: 0.04 s
  % ----------
  
  
  
  

  LikeLike

  • 

    Frits 7:47 pm on 11 October 2020 Permalink | Reply

    @GeoffR, As Jim pointed out to me (thanks) that FOUR can not be an incorrect number your MiniZinc program can be adapted accordingly. Now both run modes have similar performance.

    LikeLike

• 

  Frits 4:56 pm on 11 October 2020 Permalink | Reply

  Pretty slow (especially for high maximum prizes).

  I combined multiple “for loops” into one loop with the itertools product function so it runs both under Python and PyPy.

  @ Jim, your code has some unexplained “# can’t include FOUR” code (line 62, 63).
  It is not needed for performance.

   
  from enigma import SubstitutedExpression
  from itertools import product
  
  mi = 25      # minimum prize
  step = 25    # prizes differ at least <step> pennies 
  ma = 551     # maximum prize + 1
  bits = set() # x1...x12 are bits, 10 of them must be 1, two them must be 0
  
  # return numbers in range and bit value 
  # (not more than 2 bits in (<li> plus new bit) may be 0)
  rng = lambda m, li: product(range(mi, m, step), 
                             (z for z in {0, 1} if sum(li + [z]) > len(li) - 2))
  
  def report():
    print(f"ONE TWO THREE FOUR FIVE SIX "
    f"SEVEN EIGHT NINE TEN ELEVEN TWELVE"
    f"\n{O+N+E} {T+W+O}   {T+HR+E+E}  {F+O+UR}  {F+I+V+E} {S+I+X} "
    f"  {S+E+V+E+N}   {E+I+GH+T}  {N+I+N+E} {T+E+N}   {E+L+E+V+E+N}"
    f"   {T+W+E+L+V+E}"
    f"\n   O   N   E   T   W   L  HR   F  UR   I   V   S   X  GH"
    f"\n{O:>4}{N:>4}{E:>4}{T:>4}{L:>4}{W:>4}{HR:>4}{F:>4}{UR:>4}"
    f"{I:>4}{V:>4}{S:>4}{X:>4}{GH:>4}")
  
  for (O, N, E) in product(range(mi, ma, step), repeat=3):
    for x1 in {0, 1}:
      if x1 != 0 and O+N+E != 100: continue
      li1 = [x1]
      for (T, x10) in rng(ma, li1):
        if x10 != 0 and T+E+N != 1000: continue
        li2 = li1 + [x10]
        maxW = 201 - 2*mi if sum(li2) == 0 else ma
        for (W, x2) in rng(maxW, li2):
          if x2 != 0 and T+W+O != 200: continue
          li3 = li2 + [x2]
          for (I, x9) in rng(ma, li3):
            if x9 != 0 and N+I+N+E != 900: continue
            li4 = li3 + [x9]
            for L in range(mi, ma, step):
              for (V, x12) in rng(ma, li4):
                if x12 != 0 and T+W+E+L+V+E != 1200: continue
                li5 = li4 + [x12]
                for x11 in {0, 1}:
                  li6 = li5 + [x11]
                  if sum(li6) < 4 : continue
                  if x11 != 0 and E+L+E+V+E+N != 1100: continue
                  maxF = 501 - 3*mi if sum(li6) == 4 else ma
                  for (F, x5) in rng(maxF, li6):
                    if x5 != 0 and F+I+V+E != 500: continue
                    li7 = li6 + [x5]
                    maxSX = 601 - 2*mi if sum(li7) == 5 else ma
                    for (S, x7) in rng(maxSX, li7):
                      if x7 != 0 and S+E+V+E+N != 700: continue
                      li8 = li7 + [x7]
                      for (X, x6) in rng(maxSX, li8):
                        if x6 != 0 and S+I+X != 600: continue
                        li9 = li8 + [x6]
                        maxGH = 801 - 3*mi if sum(li9) == 7 else ma
                        for (GH, x8) in rng(maxGH, li9):
                          if x8 != 0 and E+I+GH+T != 800: continue
                          li10 = li9 + [x8]
                          maxHR = 301 - 4*mi if sum(li10) == 8 else ma
                          for (HR, x3) in rng(maxHR, li10):
                            if x3 != 0 and T+HR+E+E != 300: continue
                            li11 = li10 + [x3]
                            maxUR = 401 - 3*mi if sum(li11) == 9 else ma
                            for (UR, x4) in rng(maxUR, li11):
                              if x4 != 0 and F+O+UR != 400: continue
  
                              r = tuple(li11 + [x4])
                              if sum(r) != 10: continue  
                              # only report unique bits
                              if r not in bits:
                                report()
                                bits.add(r)
                                
  # ONE TWO THREE FOUR FIVE SIX SEVEN EIGHT NINE TEN ELEVEN TWELVE
  # 100 200   300  400  500 600   700   800  125 100   1100   1200
  #    O   N   E   T   W   L  HR   F  UR   I   V   S   X  GH
  #   25  25  50  25 550 150 175  50 325  25 375 200 375 700 
  

  LikeLike

  • 

    Jim Randell 5:17 pm on 11 October 2020 Permalink | Reply

    @Frits: The fact that FOUR cannot be one of the incorrect numbers is one of the conditions mentioned in the puzzle text.

    LikeLike

• 

  GeoffR 8:56 am on 12 October 2020 Permalink | Reply

  @Frits: I never used the fact that FOUR cannot be one of the incorrect numbers.
  I only spelt out a condition in the teaser as part of the programme ie F+O+U+R = 400.
  I do not think my programme needs adapting – is OK as the original posting.

  LikeLike