Skip to content

Instantly share code, notes, and snippets.

@miku
Created September 5, 2010 22:36
Show Gist options
  • Save miku/566395 to your computer and use it in GitHub Desktop.
Save miku/566395 to your computer and use it in GitHub Desktop.
#!/usr/bin/env python
# Four men want to cross a bridge. The bridge is of a width such that a
# maximum of 2 people may cross at a time.
#
# One man takes 10 minutes to cross, another takes 5 minutes to cross,
# another takes 2 minutes to cross, and the last takes 1 minute to
# cross.
# I will call these men A, B, C, and D, respectively.
#
# Here is the catch. If two people cross the bridge together, they must
# walk at the pace of the slower one. So if A and B cross, they take 10
# minutes. Also, it is night. Each trip requires a flashlight. There
# is only one flashlight. The men are not allowed to toss the light over
# the river.
#
# How fast can you get all 4 men over the bridge?
import random
class Point(object):
def __init__(self, name=None, init=None):
self.name = name
self.people = init
def send(self, people, to=None):
for p in people:
self.people.remove(p)
to.people += people
print people, "from", self.name, "to", to.name
return max(people)
def __str__(self):
return self.name
if __name__ == '__main__':
acc, counter = 10000, 0
while acc > 17:
acc = 0
a = Point(name='A', init=[1, 2, 5, 10])
b = Point(name='B', init=[])
while True:
chosen = random.sample(a.people, 2)
acc += a.send(chosen, to=b)
if not a.people:
break
chosen = random.sample(b.people, 1)
acc += b.send(chosen, to=a)
print acc
counter += 1
print "Sol'n found after", counter, "iterations."
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment