A circle of lavatories

[lionelhill]

In the city of Norwich, in the UK, there used to be many public lavatories, before we ran out of money and couldn't maintain them. At one corner of the ring-road, near City Station bridge (which is nowhere near the station, but that is another story), there was an ornamental octagonal public lavatory, which until recently carried a sign:
"These facilities are closed. Please use alternative conveniences at the bottom of Grapes Hill".
If you went to the bottom of Grapes Hill, there was another public toilet, also closed, with a sign directing you to a third. This third was also closed, with a sign directing you to the toilets in Tombland.

Few students on a pub crawl would have the bladder capacity to test this linked list to its end, but it always worried me that somewhere a toilet might direct you back to one you had already visited, and you would find yourself in an eternal ring of lavatories.

So the puzzle is this:
you are equipped with a small handful of assistants, and your mission is to establish whether the public lavatories of Norwich (starting at City Station bridge) do indeed contain a ring of toilets in which a tourist or student could become trapped, with only the booming bell of the town clock, tolling the passing of time, as they wander hopelessly from loo to loo. Your assistants cannot remember what an individual lavatory looks like (after a few, they all look the same). Nor can they mark the toilets in any way to show they've been visited (you can't damage public property). Nor can you photograph the lavatories (the UK has strict anti-terrorism rules about photographing things like fish-and-chip shops; a loo could be far more sensitive).

How can you find if there is a loop? The task must end in a finite time even if there is a loop. You cannot make any assumptions about the upper number of toilets in Norwich.

This puzzle has at least one solution; if my method of posing it creates undue questions and ambiguities, I will re-pose it as a straightforward computing puzzle, in a spoiler.

 

[IPGuru]

I wondered how long this group would take to descened into toilet humor

just to get the 1st question in
how many is a "small" number of assistants!
obviously with no uper limit on the number of Toilets Assistants < Toilets.

Spoiler

the obvious answer is with 1 assistant stay @ the 1st toilet & send the assistant arround the loop. if he gets back to the start without finig one there is a loop, but i suspect you are looking for a more efficent solution

 

[Olaf Doschke]

Taking "a small handful of assistants" literally, I assume we have <= 5 assistants.

Spoiler

Let an assitant stay at a toilet pointing to the next one, but not infinately. The problem may be, that a ring does not point back to the first toilet but a loop may and somewhere else, eg toilet #1 points to #2, #2 to #3, #3 to #4, #4 to #2, you will not arrave back at #1.

So with at least 2 assistants let one move on to the next toilet and the other wait for 10 minutes before going to the next toilet. Then the first one will meet the first one at some time, if there is a loop. Or both will meet at the last toilet in a row not pointing anywhere else. The assistent always moving on directly will know when the waiting assitant will arrive there, if both need about the same time for the walks, the second one will arrive at number of stations * 10 minutes.

If you have more assistants you can make the first one wat eg 16 minutes, the second 8 minutes, the third 4 minutes etc to optimize the time they need to find a loop.

Bye, Olaf.

 

[Olaf Doschke]

Spoiler

And if assistants don't have a clock the can "synchronize" via the town clock, eg with 2 assitants one moves on directly, the second waits for the next stroking of the clock (15 minutes), a third one would wait 2 times etc.

And of course only one of the remaining assitants, the one assigned to wait the longest time, will stay at each toilet, the rest moves on.

 

[lionelhill]

Yes, number of assistants << number of lavatories, and yes, the ring might start anywhere (so there may be a linear bit before a ring, if there is a ring, starts).

The task can be completed by two people without any ability to remember anything except to recognise one another, and to follow directions to the next lavatory.

For those who haven't got it, Olaf has correctly hit on the significance of Norwich's other buildings!

Spoiler

This is, of course, the algorithm for looking for a linked list that contains a circular section, using just two pointers and no recreation of the list. But the application is real! The lavatories really exist.

 

[CajunCenturion]

[hide]
For two people: Establish a time interval so that each person takes only one turn per time interval. The first person moves only the the next lavatory. The second person moves two lavatories ahead, or one if the first move takes him to the last station. If there is not a loop, the two will meet at the end station. If there is a loop, the two will meet at one station within the loop.

The only trick is to ensure that the timer interval is long enough to allow the second person to move two stations ahead.
[/hide]


--------------
Good Luck
To get the most from your Tek-Tips experience, please read
FAQ181-2886
As a circle of light increases so does the circumference of darkness around it. - Albert Einstein

 

[lionelhill]

CajunCenturion,
Good approach!

Spoiler

Norwich's city hall clock strikes every half hour, and Norwich is sufficiently small a city that anyone can make it from one loo to the next in under 15 minutes, even if they've been on a pub crawl.

 

[IPGuru]

As this is a group fro programmers I thought an example program would be a good idea.
this is a simple Python script with some example data what will perform the task

Spoiler

# each element in the list points to the next -1 signifys end of list
test1=[1,2,3,4,-1] #list with an end point
test2=[1,2,3,4,5,6,7,1,] #perfect circle
test3=[1,2,3,6,5,7,4,8,9,10,11,12,13,14,15,16,17,18,19,-1] #out of sequence list
test4=[1,2,3,6,5,7,4,8,9,10,11,12,13,14,15,16,17,18,19,8,-1] #pan handle!

srch=[test1,test2,test3,test4] #list of lists
def walk_list(list,ast1,ast2):
for step in range(2): #ast2 moves up to 2 toilets
ast2=list[ast2]
if ast2<0:
break #end reached no loop!
if ast2==ast1: # ast2 has met ast 1 must be a loop!
ast1=-1
break
if ast1 >=0 and ast2 >=0:
ast1=list[ast1]
ast1,ast2=walk_list(list,ast1,ast2)
return ast1,ast2

def main():
for test in srch: #perform test for each list in turn
ast1,ast2=0,0
print "searching list %s" % str(test)
ast1,ast2=walk_list(test,ast1,ast2)
if ast2 == -1:
print "no loop"
else:
print "loop found"
return 0

if __name__ == '__main__': main()

It was developed before cajuns suggestion but follows the same principle.

 

[hdingman]

Use GPS with "Track Route"
or "Save waypoint"