############################################################################################################################
# bridge_flashlight_puzzle.py
#
# Bridge Flashlight Puzzle Python Solution
#
# There are 4 men who want to cross a bridge. They all begin on the same side.
# You have 17 minutes to get all of them across to the other side. It is night.
# There is one flashlight. A maximum of two people can cross at one time.
#
# Any party who crosses, either 1 or 2 people, must have the flashlight with them.
# The flashlight must be walked back and forth, it cannot be thrown etc.
#
# Each man walks at a different speed. A pair must walk together at a rate of the slower man's pace.
#
# Man 1: 1 minute to cross.
# Man 2: 2 minutes to cross.
# Man 3: 5 minutes to cross.
# Man 4: 10 minutes to cross.
#
# For example, if Man 1 and Man 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge.
# If Man 4 returns with the flashlight, a total of 20 minutes have passed, and you have failed the mission.
#
# Usage:
# $ python bridge_flashlight_puzzle.py
# (1, 2, 5, 10) ()
# (10, 5) (1, 2)
# (10, 5, 1) (2,)
# (1,) (2, 10, 5)
# (1, 2) (10, 5)
# () (10, 5, 1, 2)
#
#
# Author:
# Ramin Rakhamimov
# ramin32 AT gmail DOT com
# http://raminrakhamimov.com
############################################################################################################################
from itertools import combinations
from time import sleep
def find_bridge_path(a, b=tuple(), count=0, max_minutes=17, from_a=True, path=tuple()):
if count > max_minutes:
return
if not a and count <= max_minutes:
return path
if from_a:
for c in combinations(a, 2):
a1 = tuple(set(a) - set(c))
b1 = b + c
new_path = find_bridge_path(a1, b1, count + max(c), max_minutes, not from_a, path + ((a1, b1),))
if new_path:
return new_path
else:
for i in b:
a1 = a + (i,)
b1 = list(b)
b1.remove(i)
b1 = tuple(b1)
new_path = find_bridge_path(a1, b1, count + i, max_minutes, not from_a, path + ((a1, b1),))
if new_path:
return new_path
a = (1, 2, 5, 10)
path = find_bridge_path(a, max_minutes=17, path=(a,))
for traversal in path:
print traversal