Skip to content

Instantly share code, notes, and snippets.

@bivoje
Created March 8, 2019 04:29
Show Gist options
  • Save bivoje/19473fc453f6482665b89bb349f07298 to your computer and use it in GitHub Desktop.
Save bivoje/19473fc453f6482665b89bb349f07298 to your computer and use it in GitHub Desktop.
code for calculating solution for exercise no.38 of setion 1.2 from the book Discrete Mathematics and Its Applications 7th ed.
# 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("")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment