S2T2

Jim Randell 8:28 am on 26 August 2025 Permalink Reply
Tags: by: Angela Newing ( 36 )   

• 

  Jim Randell 8:29 am on 26 August 2025 Permalink | Reply

  This Python program uses the [[ SubstitutedExpression() ]] solver from the enigma.py library to solve the puzzle.

  We assign numeric values from 0 to 4 to the floors (this makes it easier to code the condition that D is one floor below C), and then assign each of the floor values to the remaining groups of attributes: name, colour, make.

  The program runs in 71ms. (Internal runtime is 8.4ms).

  from enigma import (SubstitutedExpression, sprintf, printf)
  
  # we assign floor values (0 .. 4 = basement .. 3rd) to each of the groups:
  #   name (A, B, C, D, E)
  #   make
  #   colour
  
  # floors (basement, ground, 1st, 2nd, 3rd)
  floor = (FB, FG, F1, F2, F3) = (0, 1, 2, 3, 4)
  
  # symbols and labels for the groups
  name = (A, B, C, D, E) = "ABCDE"
  make = (MM, MA, MF, MV, MT) = "KLMNP"  # MG, Audi, Ford, Vauxhall, Toyota
  colour = (CS, CB, CK, CW, CR) = "QRSTU"  # silver, blue, black, white, red
  
  # construct the expressions
  exprs = list(sprintf(x) for x in [
    # "A does not live in the basement"
    "{FB} != {A}",
    # "basement owns the MG"
    "{FB} == {MM}",
    # "A's car is not the silver Audi" => "the Audi is silver"
    "{MA} == {CS}", "{MA} != {A}", "{CS} != {A}",
    # "A's car is not blue"
    "{CB} != {A}",
    # "the blue car belongs to the second floor"
    "{CB} == {F2}",
    # "the Ford is not black" (!)
    "{MF} != {CK}",
    # "the Ford belongs to the first floor"
    "{MF} == {F1}",
    # "the ground floor car is white"
    "{FG} == {CW}",
    # "E's car is not black"
    "{CK} != {E}",
    # "the Vauxhall belongs to A, B, or C"
    "{MV} in {{ {A}, {B}, {C} }}",
    # "D lives one floor below C"
    "{D} + 1 == {C}",
    # "D owns the Toyota"
    "{MT} == {D}",
  ])
  
  # construct the solver
  p = SubstitutedExpression(exprs, base=5, distinct=[name, make, colour])
  
  # labels for output
  floors = ["basement", "ground floor", "1st floor", "2nd floor", "3rd floor"]
  names = ["Anne", "Beth", "Carol", "Dave", "Eric"]
  colours = ["silver", "blue", "black", "white", "red"]
  makes = ["MG", "Audi", "Ford", "Vauxhall", "Toyota"]
  output = lambda f, n, c, m: printf("{f}: {n}, {c} {m}")
  
  # solve the puzzle
  for s in p.solve(verbose=0):
    # collect attributes by floor
    ss = list([f] for f in floors)
    for (xs, ts) in [(name, names), (colour, colours), (make, makes)]:
      for (x, t) in zip(xs, ts):
        ss[s[x]].append(t)
    # output solution
    for vs in ss: output(*vs)
    printf()
  

  Solution: Eric’s car is red; Anne’s car is white; Dave’s car is blue.

  The complete description is:

  basement: Beth, black, MG
  ground floor: Anne, white, Vauxhall
  1st floor: Eric, red, Ford
  2nd floor: Dave, blue, Toyota
  3rd floor: Carol, silver, Audi

  LikeLike

• 

  Frits 7:43 pm on 27 August 2025 Permalink | Reply

  Reusing code from Tantalizer 66.

  deepcopy = lambda s: [x.copy() for x in s]
  n_elements = lambda s: sum(len(y) for x in s for y in x)
  
  # update values in positions <ps> for column <col>
  def update(ps, vals):
    col = colno[vals[0]] # column for the values in <vals>
    for i in range(5):
      if i in ps:
        lst[i][col] = vals
      else:
        # remove values from other positions
        remove(i, [x for x in lst[i][col] if x in vals]) 
  
  # remove values <vals> from lst[pos][col]      
  def remove(pos, vals):
    if not vals: return
    col = colno[vals[0]] # column for the values in <vals>
    ln = len(lst[pos][col])
    lst[pos][col] = [x for x in lst[pos][col] if x not in vals]  
    if not lst[pos][col]:
      error = True   # no value remained
    if ln > 1 and len(lst[pos][col]) == 1:
      update([pos], lst[pos][col])
  
  # propagate uniqueness of value <v>
  def unique(col, v):
    # check for uniqueness
    if len(s := [i for i in range(5) if v in lst[i][col]]) == 1:
      update(s, [v])     
  
  # values <v1> and <v2> belong together
  def linked(v1, v2):
    c1 = colno[v1] 
    c2 = colno[v2] 
    # if v1 and v2 don't both exist for a position remove all of them
    for i in range(5):
      if not(v1 in lst[i][c1] and v2 in lst[i][c2]):
        remove(i, [v1])
        remove(i, [v2])
  
    unique(c1, v1)
    unique(c2, v2)  
  
  # values <v1> and <v2> don't belong together
  def not_linked(v1, v2):
    c1 = colno[v1] 
    c2 = colno[v2] 
    # remove other value if a position has a set value for <v1> or <v2> 
    for i in range(5):
      if lst[i][c1] == [v1]:
        remove(i, [v2])
      if lst[i][c2] == [v2]:
        remove(i, [v1])
  
  # try all options for person <p> and list <s>
  def solve(k, p, s, ss=[]):
    global lst
    if (n := n_elements(lst)) == 15:
      yield lst
    elif k == 0:
      # we have to try options for another person
      p = ss[1]
      s = deepcopy(lst[p])
      yield from solve(3, p, s, ss[1:])
    else:
      if len(s[k - 1]) == 1:  # one value
        yield from solve(k - 1, p, s, ss)
      else:
        save = deepcopy(lst)
        # try all values
        for v in s[k - 1]:
          update([p], [v])
          # check/update relations until <lst> is no longer updated
          n = check()   
          if not error:
            yield from solve(k - 1, p, s, ss)
          # back track all updates
          lst = deepcopy(save)          
  
  # check/update relations until <lst> is no longer updated
  def check():
    global error
    error = False
    n, prev = 75, 76
    
    while n < prev and not error:
      linked("basement", "MG")        # "basement owns the MG"
      linked("Audi", "silver")        # "A's car is not the silver Audi"
      linked("blue", "second-floor")  # "the blue car belongs to the second floor"
      not_linked("Ford", "black")     # "the Ford is not black"
      linked("Ford", "first-floor")   # "the Ford belongs to the first floor"
      linked("ground-floor", "white") # "the ground floor car is white"
      # "D lives one floor below C"
      for fl in lst[D][0]:
        if floor[floor.index(fl) + 1] not in lst[C][0]:
          remove(D, [fl])
      for fl in lst[C][0]:
        if floor[floor.index(fl) - 1] not in lst[D][0]:
          remove(C, [fl])    
  
      # calculate number of elements in flattened list
      prev, n = n, n_elements(lst)
      if n < 15:
        error = True
    return n
  
  floor  = "basement ground-floor first-floor second-floor third-floor".split()
  make   = "MG Audi Ford Vauxhall Toyota".split()
  colour = "silver blue black white red".split()
  names  = "Anne Beth Carol Dave Eric".split()
  A, B, C, D, E = range(5)
  
  # dictionary column number per item
  colno = {x: 0 if x in floor else 1 if x in colour else 2 
             for x in floor + make + colour}
  
  # make an initial list per person with all possibilities
  lst = [[floor, colour, make] for _ in range(5)]
  error = False
  
  # initial constraints
  remove(A, ["basement"])         # "A does not live in the basement"
  remove(A, ["Audi"])             # "A's car is not the silver Audi"
  remove(A, ["silver", "blue"])   # "A's car is not blue"
  remove(E, ["black"])            # "E's car is not black"
  # "the Vauxhall belongs to A, B, or C"
  remove(D, ["Vauxhall"])
  remove(E, ["Vauxhall"])
  # "D lives one floor below C"
  remove(D, ["third-floor"])
  remove(C, ["basement"])
  update([D], ["Toyota"])         # "D owns the Toyota"
  
  # check/update relations until <lst> is no longer updated
  n = check()    
  if error: 
    print("no solution")
  elif n == 15:
    for name, vals in zip(names, lst):
      print(f"{name}:", ", ".join(x[0] for x in vals))
  elif n > 15:
    # start with person for which the most is known
    ns = sorted([(sum(len(y) for y in x), i) for i, x in enumerate(lst)])
    ns = [i for x, i in ns if x > 3]
    # try all options 
    for s in solve(3, ns[0], deepcopy(lst[ns[0]]), ns):
      for name, vals in zip(names, lst):
        print(f"{name}:", ", ".join(x[0] for x in vals))
      print("answer:", [[name for name, vals in zip(names, lst) 
            if col in vals[1]][0] for col in ["red", "white", "blue"]])
  

  LikeLike