In [ ]:
# SAMPLE INPUT:
#
# 3
# Buttercup must be milked beside Bella
# Blue must be milked beside Bella
# Sue must be milked beside Beatrice
In [2]:
import itertools
fin = open ('lineup.in', 'r')
fout = open ('lineup.out', 'w')
N = int(fin.readline().strip())
inputruleset = set()
for i in range(N):
inlist = [s for s in fin.readline().split()]
# make a tuple out of the sorted pair so that you have a hashable rule to add to the ruleset
if inlist[0]<inlist[5]:
inrule = (inlist[0],inlist[5])
else:
inrule = (inlist[5],inlist[0])
inputruleset.add(inrule)
print("inputruleset",inputruleset)
In [3]:
list1 = ["Bessie", "Buttercup", "Belinda", "Beatrice", "Bella", "Blue", "Betsy","Sue"]
list1.sort()
print(list1)
In [4]:
def all_rules_satisfied(lu):
rules = set()
for i in range(len(lu)-1):
if lu[i]<lu[i+1]:
rule = (lu[i],lu[i+1])
else:
rule = (lu[i+1],lu[i])
rules.add(rule)
return(rules)
In [5]:
# The rules that need to be satisfied are stored as sorted tuples in inputruleset
# Itertools.permutations produces all possible lineups
# These lineups will come out in alphabetic order because list1 is in alphabetic order
# All rules that are satisfied by the lineup are stored in ruleset
# Iterate through inputruleset and check if they are in ruleset for the current lineup
# The first valid lineup found will be the first of the alphabetically sorted valid lineups
for lineup in itertools.permutations(list1):
ruleset = all_rules_satisfied(lineup)
good_lineup = True
for rule in inputruleset:
if rule not in ruleset:
good_lineup = False
break
if good_lineup:
print(lineup)
for cow in lineup:
fout.write(cow+"\n")
fout.close()
break # done!
