#!/usr/bin/python
# Solution to Einstein's Puzzle.

print("Starting...")

# First, build a list of all permutations of (0, 1, 2, 3, 4).
# There are 5! of them, or 120.
# Not efficient, but runs only once.
Factorials = []
for a in range(5):
  for b in range(5):
    if b != a:
      for c in range(5):
        if c != a and c != b:
          for d in range(5):
            if d != a and d != b and d != c:
              for e in range(5):
                if e != a and e != b and e != c and e != d:
                  Factorials.append([a, b, c, d, e])

Colours = ['Red', 'White', 'Yellow', 'Blue', 'Green']
Nations = ['Brit', 'Swede', 'Dane', 'Norwegian', 'German']
Drinks = ['Tea', 'Milk', 'Beer', 'Coffee', 'Water']
Smokes = ['Blends', 'Dunhill', 'Pall Mall', 'Blue Master', 'Prince']
Pets = ['Dogs', 'Birds', 'Cats', 'Horses', 'Fish']

# Next, churn through all permutations.
# There are 120^5 of them, or 24,883,200,000.
# Fortunately the rules wipe out whole sections of the tree.
for colour in Factorials:
  red = colour.index(Colours.index('Red'))
  white = colour.index(Colours.index('White'))
  yellow = colour.index(Colours.index('Yellow'))
  blue = colour.index(Colours.index('Blue'))
  green = colour.index(Colours.index('Green'))

  #4 The Green house is on the left of the White house.
  # We'll assume that this means directly left, not somewhere left.
  # But there's nothing to indicate which direction 'left' means. -- Bug caught by Eric Usherwood
  if (green+1 != white and green-1 != white):
    continue

  for nation in Factorials:
    brit = nation.index(Nations.index('Brit'))
    swede = nation.index(Nations.index('Swede'))
    dane = nation.index(Nations.index('Dane'))
    norwegian = nation.index(Nations.index('Norwegian'))
    german = nation.index(Nations.index('German'))

    #1 The Brit lives in a red house.
    if (red != brit):
      continue
    #9 The Norwegian lives in the first house.
    if (norwegian != 0):
      continue
    #14 The Norwegian lives next to the blue house.
    if (norwegian+1 != blue and norwegian-1 != blue):
      continue

    for drink in Factorials:
      tea = drink.index(Drinks.index('Tea'))
      milk = drink.index(Drinks.index('Milk'))
      beer = drink.index(Drinks.index('Beer'))
      coffee = drink.index(Drinks.index('Coffee'))
      water = drink.index(Drinks.index('Water'))

      #3 The Dane drinks tea.
      if (dane != tea):
        continue
      #5 The owner of the Green house drinks coffee.
      if (green != coffee):
        continue
      #8 The man living in the centre house drinks milk.
      if (milk != 2):
        continue

      for smoke in Factorials:
        blends = smoke.index(Smokes.index('Blends'))
        dunhill = smoke.index(Smokes.index('Dunhill'))
        pallmall = smoke.index(Smokes.index('Pall Mall'))
        bluemaster = smoke.index(Smokes.index('Blue Master'))
        prince = smoke.index(Smokes.index('Prince'))

        #7 The owner of the Yellow house smokes Dunhill.
        if (dunhill != yellow):
          continue
        #12 The man who smokes Blue Master drinks beer.
        if (bluemaster != beer):
          continue
        #13 The German smokes Prince.
        if (prince != german):
          continue
        #15 The man who smokes Blends has a neighbour who drinks water.
        # This rule is completely redundant.
        if (blends+1 != water and blends-1 != water):
          continue

        for pet in Factorials:
          dogs = pet.index(Pets.index('Dogs'))
          birds = pet.index(Pets.index('Birds'))
          cats = pet.index(Pets.index('Cats'))
          horses = pet.index(Pets.index('Horses'))
          fish = pet.index(Pets.index('Fish'))

          #2 The Swede keeps dogs as pets.
          if (swede != dogs):
            continue
          #6 The person who smokes Pall Mall rears birds.
          if (pallmall != birds):
            continue
          #10 The man who smokes Blends lives next to the one who keeps cats.
          if (blends+1 != cats and blends-1 != cats):
            continue
          #11 The man who keeps horses lives next to the man who smokes Dunhill.
          if (dunhill+1 != horses and dunhill-1 != horses):
            continue

          print("Answer Found!")
          print("Colours:\t%s\t%s\t%s\t%s\t%s" % (Colours[colour[0]], Colours[colour[1]], Colours[colour[2]], Colours[colour[3]], Colours[colour[4]]))
          print("Nations:\t%s\t%s\t%s\t%s\t%s" % (Nations[nation[0]], Nations[nation[1]], Nations[nation[2]], Nations[nation[3]], Nations[nation[4]]))
          print("Drinks: \t%s\t%s\t%s\t%s\t%s" % (Drinks[drink[0]], Drinks[drink[1]], Drinks[drink[2]], Drinks[drink[3]], Drinks[drink[4]]))
          print("Smokes: \t%s\t%s\t%s\t%s\t%s" % (Smokes[smoke[0]], Smokes[smoke[1]], Smokes[smoke[2]], Smokes[smoke[3]], Smokes[smoke[4]]))
          print("Pets:   \t%s\t%s\t%s\t%s\t%s" % (Pets[pet[0]], Pets[pet[1]], Pets[pet[2]], Pets[pet[3]], Pets[pet[4]]))

print("...Done.")