Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# Rope Burning Riddler from fivethirtyeight.com
def explore(situation):
ropes = situation[0]
time = situation[1]
# Find unextinguished ropes and make a list of those
# with at least 1 unlit end.
allextinguished = True
ropestochoose = []
for r in range(N):
if ropes[r][1] == 0 or ropes[r][1] > time:
allextinguished = False
if not ropes[r][0] ==2:
ropestochoose.append(r)
if allextinguished:
# No descendent situations, so tally the intervals
for rope in ropes:
time = rope[1]
if not time in times:
times.append(time)
# Comment-out the following block to ignore
# periods between extinguishings
for rope1 in ropes:
for rope2 in ropes:
time = abs(rope1[1]-rope2[1])
if not time in times:
times.append(time)
return
# A choice is to (0) do nothing, (1) ignite a first
# end if unignited (2) ignite (both first and)
# second end if unignited. The choice for a particular
# rope R (0 to len(ropestochoose)-1) is (choices//3**R)%3
# (think of choices as a base-3 numeral).
for choices in range(1,3**len(ropestochoose)):
# We will modify a copy of ropes
newropes = list(ropes)
for r in range(len(ropestochoose)):
rope = newropes[ropestochoose[r]]
choice = (choices//3**r)%3
if rope[0] == 0:
# No ends lit
if choice == 1:
rope = [1,time+1]
elif choice == 2:
rope = [2,time+.5]
elif rope[0] == 1:
# One end already lit
if choice == 2:
rope = [2,time+.5*(rope[1]-time)]
newropes[ropestochoose[r]] = rope
# This will prevent redundantly exploring equivalent situations
newropes.sort(reverse=True)
# Find time of next extinguishing
nexttime = min([rope[1] for rope in newropes if rope[1] > time])
newsituation = [newropes,nexttime]
if (newropes == ropes or (newsituation in already_processed)):
continue
already_processed.append(newsituation)
explore(newsituation)
# Main program
# Numbers of ropes to do
MinRopes = 1
MaxRopes = 6
for N in range(MinRopes,MaxRopes+1):
# ropes is a list of pairs. each pair is: [ends-lit
# (0, 1, or 2), time (has been or will be) extinguished].
# We start with extinction time 0 as a dummy value.
ropes = [[0,0]]*N
time = 0
situation = [ropes,time]
# Keep track of the situations we have already processed
already_processed = [situation]
# This is our list of the durations we can measure
times = []
# Recursively explore the achievable situations
explore(situation)
# Done. Tidy up and finish.
if 0 in times:
# 0 is not a duration per problem statement.
times.remove(0)
times.sort()
print(N,"ropes measure",len(times), "intervals")
# print(times)
@hectorpefo

This comment has been minimized.

Copy link
Owner Author

@hectorpefo hectorpefo commented Feb 18, 2017

This is the problem statement: Suppose you have four ropes and a lighter. Each rope burns at a nonconstant rate but takes exactly one hour to burn completely from one end to the other. You can only light the ropes at either of their ends but can decide when to light each end as you see fit. If you’re strategic in how you burn the ropes, how many specific lengths of time can you measure? (For example, if you had one rope, you could measure two lengths of time: one hour, by simply burning the entire rope from one end, and half an hour, by burning the rope from both ends and marking when the flames meet.) https://fivethirtyeight.com/features/a-riddle-how-many-crooked-politicians-are-there/

@hectorpefo

This comment has been minimized.

Copy link
Owner Author

@hectorpefo hectorpefo commented Feb 25, 2017

Sped up the program by an order of magnitude by not defining choices for every rope, but only the ones needing decisions at the time.

@hectorpefo

This comment has been minimized.

Copy link
Owner Author

@hectorpefo hectorpefo commented Feb 25, 2017

Another order of magnitude (at least) speed-up. Now can do from 1 to 7 ropes in 4 minutes.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment