code for calculating solution for exercise no.38 of setion 1.2 from the book Discrete Mathematics and Its Applications 7th ed.

DMIA7_1.2_38_sol.py

# code for calculating solution for exercise no.38 of setion 1.2 from the book Discrete Mathematics and Its Applications 7th ed.
# no input, no configuring required. it just calculates & prints answer.
# it uses brute force approch. no sophisticated algorithm implemented with this code.
# further modification would enable argumented problem solving.

# Q: zebra
# Q: mineral
# The Englishman lives in the red house.
# The Spaniard owns a dog.
# The Japanese man is a painter.
# The Italian drinks tea.
# The Norwegian lives in the first house on the left.
# The green house is immediately to the right of the white one.
# The photographer breeds snails.
# The diplomat lives in the yellow house.
# Milk is drunk in the middle house.
# The owner of the green house drinks coffee.
# The Norwegian’s house is next to the blue one.
# The violinist drinks orange juice.
# The fox is in a house next to that of the physician.
# The horse is in a house next to that of the diplomat.

# returns all possible permutation sequance of (elem P n)
# elem : set, n : nat
def perm(elems, n):
  if n == 0:
    yield []
    return

  for x in elems:
    elems.remove(x)
    for p in perm(elems, n-1):
      yield [x] + p
    elems.add(x)

def gen(n):
  return perm(set(range(n)), n)

def comp_field(val):
  f1, f2 = val
  if f1 is None:
    return None
  return f1 == f2

def uniform(ls):
  if len(ls) < 2:
    return True

  x = ls[0]
  for a in ls:
    if a != x:
      return False
  else:
    return True

def check(houses, pattern):
  for i in range(len(houses)):
    if not uniform(list(
      filter(lambda x: x != None,
        map(comp_field,
          zip(pattern, list(houses)[i]))))):
      return False
  return True

def match(x, pattern):
  for f1, f2 in zip(x, pattern):
    if f2 is None:
      continue
    if f1 != f2:
      return False
  else:
    return True

def find(houses, pattern):
  for i in range(len(houses)):
    if match(houses[i], pattern):
      return houses[i]
  else:
    return None

def neighb(houses, pat1, pat2):
  h1 = find(houses, pat1)
  h2 = find(houses, pat2)
  assert h1 and h2 # last is index
  return abs(h1[-1] - h2[-1]) == 1

def nextTo(houses, pat1, pat2):
  h1 = find(houses, pat1)
  h2 = find(houses, pat2)
  assert h1 and h2
  return h1[-1]+1 == h2[-1]

def report(mapping, houses):
  for i in range(len(houses)):
    house = houses[i]
    for x in range(len(house)):
      print(mapping[x][house[x]], end="\t")
    print("")

mapping = [
  ["E",   "S",   "J",   "I",   "N"  ],
  ["pnt", "pho", "dip", "vio", "phy"],
  ["R",   "G",   "Y",   "B",   "W"  ],
  ["dog", "snl", "fox", "hrs", "zbr"],
  ["tea", "mlk", "cfe", "org", "mnr"],
  ["0",   "1",   "2",   "3",   "4"  ],
]

none   = [None] * 5
nation = [None] * 5
job    = [None] * 5
color  = [None] * 5
pet    = [None] * 5
drink  = [None] * 5

report_cnt = 0

# fix index. # 5
index = [0,1,2,3,4]

for drink in gen(5): # 4
  houses = list(zip(nation, job, color, pet, drink, index))
  if not check(houses, (None, None, None, None, 1, 2)): # Milk 2
    continue
  
  for pet in gen(5): # 3  
    houses = list(zip(nation, job, color, pet, drink, index))

    for color in gen(5): # 2
      houses = list(zip(nation, job, color, pet, drink, index))
      if not check(houses, (None, None, 1, None, 2, None)): # G coffee
        continue
      if not nextTo(houses, (None, None, 4, None, None, None), # W x
                            (None, None, 1, None, None, None)): # G x+1
        continue

      for job in gen(5): # 1
        houses = list(zip(nation, job, color, pet, drink, index))
        if not check(houses, (None, 3, None, None, 3, None)):
          continue
        if not check(houses, (None, 1, None, 1, None, None)):
          continue
        if not check(houses, (None, 2, 2, None, None, None)):
          continue
        if not neighb(houses, (None, None, None, 2, None, None),
                              (None, 4, None, None, None, None)):
          continue
        if not neighb(houses, (None, None, None, 3, None, None),
                              (None, 2, None, None, None, None)):
          continue

        for nation in gen(5): # 0
          houses = list(zip(nation, job, color, pet, drink, index))
          if not check(houses, (4, None, None, None, None, 0)):
            continue
          if not check(houses, (3, None, None, None, 0, None)):
            continue
          if not check(houses, (1, None, None, 0, None, None)):
            continue
          if not check(houses, (0, None, 0, None, None, None)):
            continue
          if not check(houses, (2, 0, None, None, None, None)):
            continue
          if not neighb(houses, (4, None, None, None, None, None),
                                (None, None, 3, None, None, None)):
            continue

          report_cnt += 1
          print("{}th case:".format(report_cnt))
          report(mapping, houses)
          print("")