wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> The ASYLUM
        
(Message started by: mattian on Jul 24^th, 2004, 8:25pm)

Title: The ASYLUM
Post by mattian on Jul 24^th, 2004, 8:25pm

ASYLUM
======

You are the only patient in a mental asylum with eight wards labeled A through H. Each ward has four doors - three white and one red. The white doors are marked, "1", "2" and "3". Although these markings are not very helpful, you do know that each door leads to one of three places - the previous ward, the next ward or the ward in which you're already standing.

The terms "previous" and "next" in this case refer to those wards with ward letters alphabetically before and after the current ward letter. For example: If door 1 in ward C leads to the next ward, then it leads to ward D. If door 2 leads to the previous ward it leads to B. If door 3 of ward H leads to the next ward, then it leads to ward A, and vice versa. In other words, the ward-connections wrap around.

When you walk through a white door, you enter the destination ward through the red door of the that ward. The red door locks behind you.

Your objective is to escape the asylum and you know that you can do that by turning around going back through the red door that locked behind you.

* Unfortunately the red doors are all locked.
* Fortunately during your journey from ward to ward, in one of the wards you find a key.
* Unfortunately if you use the key, you will set off the alarm and be caught, restrained and returned to your room.
* Fortunately you know that the alarm in ward E has been disabled.
* Unfortuantely you never know which ward you're in - except in the very beginning: Ward A.

Objective: Escape the asylum in the fewest transitions possible. Remember you may only use the key once - so make sure you know you're in Ward E when you do it.

Some things to think about:
Is it possible to guarantee an escape?
Is it possible to guarantee that the patient will find the key - given a particular strategy?

Some rules:
1. The only way to see what's behind a door is to walk through it, and close the door behind you.
2. All wards look identical
3. A transition is counted each time a white door is opened.

I have written a little simulator which lets you be the patient in this puzzle. Please visit http://www.monahansen.com/asylum/

Note: Currently only IE support has been written for this simulator. Other browsers might work - but I wouldn't count on it. ENJOY!

Title: Re: The ASYLUM
Post by Grimbal on Jul 25^th, 2004, 6:37am

Opera doesn't work, for instance.

::[hide]It is not possible to guarantee an escape. You can if you find the key in ward A. If not, you first move might loose information about where you were. If A and C lead to B via door 1, and your first move is 1, you will never know which of A and C was your starting position.
If you have the key in ward A, leave it there until you have figured how to go to the next room and back. Then you move the key one room and restart. When you have moved 4 times, you are in room E, whatever direction you took.
[/hide]::

Title: Re: The ASYLUM
Post by Grimbal on Jul 25^th, 2004, 6:40am

PS: nice simulation, by the way. It reminds an old game where at some place you are in a twisty maze of passages, all alike.

Title: Re: The ASYLUM
Post by mattian on Jul 25^th, 2004, 9:09am

Quote:

nice simulation, by the way.

I will create a GUI for all the riddles I post from now on. Makes it more fun. So let me know if there are any riddle scenarios in this forum (or otherwise) that you want me to simulate.

Title: Re: The ASYLUM
Post by Three Hands on Jul 26^th, 2004, 11:17am

It does look like you need a certain amount of luck to get out of the asylum...

[hide] Given that the key is the only "signpost" you get, and you can't tell which door you cam through when you move into another ward (clearly a good reason for you to be locked up in the first place - with that kind of short term memory :P). Therefore, probably you're best plan is to keep track of the route you took to find the key, and then effectively use the key to help map the entire asylum. This would probably take quite a lot of time, however. Having then worked out a map of the asylum, you can then, I would imagine, work out which room the key originated in, and so what route to take to get to Ward E - and thus freedom.[/hide]

I imagine that counts as a bare bones for a solution, and just needs someone to crunch numbers to work out how long you would be expected to take. Or come up with a better solution, as I expect you'd be in there for quite a long time...

Title: Re: The ASYLUM
Post by mattian on Jul 26^th, 2004, 11:38am

Grimbal, Three hands:

Actually - as both of you have pointed out - there was an omission in the original puzzle which makes it ...

::
... impossible to guarantee success for the patient - unless the key is found in ward A. This was not my intention when it was constructed. It was an oversight on my side before publishing it. One option is to add a constraint that says, "The key is in ward A."
::

Title: Re: The ASYLUM
Post by mattian on Jul 26^th, 2004, 11:44am

Three Hands:

I don't think it takes all that long (not all that short either - don't get me wrong), but barring the issue described by you and Grimbal, the solution is fairly simple - assuming the patient has a really good memory.

Title: Re: The ASYLUM
Post by Three Hands on Jul 27^th, 2004, 7:39am

True - if you find the key in Ward A,[hide]you only need to find out the way forward and back around half the wards. Given that in each room one does nothing, one goes forwards and one goes backwards, the method that seems to work best is to leave the key initially in Ward A, and go through a door. If you see a key on the floor, you can remember that door as the "same room". If you enter an empty ward, then you can assume you have gone forwards (Since direction does not matter particularly, as you only need to get 4 steps round). From this room, you then attempt to find a way back to room A by guessing a door. One door will cause you to stay put, one door will cause you to move away from A, but in either case, you can't tell. Therefore, there is a 1/3 (or 6/18 ) chance of guessing the way back immediately. If you switch doors after having chosen a door that leads you to a blank ward, you have a (1/3*1/2) = 1/6 (or 3/18 ) chance of finding your way back (Same room - back a room), ((1/3*1/2)+(1/3*1/3) = 5/18 chance of being two steps away (Same room - forward a room, Forward a room, same room), (1/3*1/3) = 1/9 (or 2/18 ) of being 1 step away (Forward a room, back a room), and 1/9 (or 2/18 ) of being 3 steps away (Forward - forward). However, by using that strategy, half the time you will findthe key again, and so know how to get from A to B, and B to A. So you then move the key to B and repeat. If you do not find your way back, then I imagine selecting doors at random until you find your way back to A is recommended, and if you manage to do this in less than 7 steps, you can guarantee that the last room you were in was B (since it takes 7 steps to get from B to A the long way round as a minimum, and you could not be certain that you did not manage to do that) and so know how to go A-B-A, so can continue. Otherwise, go back to room B and try a different door from the one you tried the previous time, with the odds slightly more in your favour this time. Having moved the key from A to B, know A-B-A, you can then repeat the same process of working out B-C-B, and then move to C, then D, and finally E, using the same principles. Previous results may be able to alter probabilities in rooms, but I'm not mathematical enough to know how to do that.

I'm not convinced, however, that it is entirely impossible to work out where you pick the key up if it is not in ward A to begin with. If you keep track o the route you took to get to the key, knowing that you started in A, then you have a route for how to get from A to ward 1 (the ward where you found the key). You can then work out the connections for the Asylum doors, using the mapping technique outlined above, only labelling your point of origin 1 instead of A. Then, knowing all the connections, you may be able to re-create the original journey you took, and so find out which ward for "your map" (1,2,3,4,5,6,7,8 ) corresponds to the "Asylum map" (A,B,C,D,E,F,G,H) Ward A, hence finding out the fastest route from your current ward to ward E, and escape. This process, however, I imagine would be expected to take a lot longer. For the initial part to work, however, I expect that a non-repeating pattern of doors being taken would need to be used, so as to avoid potential problems with not knowing when you started going through the "same" door for a ward, since that number door was also a door from an adjacent ward that took you into that ward - at least for the first couple of steps...[/hide]

So, a possible method for success, but I'm not much good at crunching numbers...

[e] Sorry for adding more to what is already a long post...

[hide]After some time trying the method I suggested above for the original version in mattian's simulation (thank you for providing such a useful test-tool, btw ;) ) I've encountered a few occasions where I've been left with a 50:50 chance of guessing which ward is ward A (and hence ward E). This, I suspect, is mostly due to no finding an appropriate combination of doors to use while finding the key to avoid the situation where two wards could be your point of origin, if such a combination exists. I suppose now the challenge is two-fold: Find an optimal combination to use while moving from Ward A to the key, and then, having found the key, perfect the mapping of the ward doors in order to, as quickly as possible, determine which ward is ward A, and then move as quickly as possible to ward E.

For this latter challenge, I would guess that testing new doors as a possible "backtrack" of the combination you used to get from ward A to the key would be the optimal strategy in trying to do this as swiftly as possible. I would also add that I don't think I've used more than 100 steps to escape, although some attempts can get close to this, so my guess about taking a long time appears to be unfounded, when compared with those 100 prisoners in the complex across the street...[/hide] [/e]

Title: Re: The ASYLUM
Post by mattian on Jul 27^th, 2004, 9:23am

Quote:

If you do not find your way back, then I imagine selecting doors at random until you find your way back to A is recommended, and if you manage to do this in less than 7 steps, you can guarantee that the last room you were in was B

Not true. It is possible your transition was A-B-C-D-D-C-B-A, for example. There are many other such examples which take you from A to A in seven steps.

Your probabilities approach is interesting, however, there is a more precise way to resolve the edges of the maze - which is also more efficient. Again - assuming you find the key in A.

Quote:

I'm not convinced, however, that it is entirely impossible to work out where you pick the key up if it is not in ward A to begin with. If you keep track o the route you took to get to the key, knowing that you started in A, then you have a route for how to get from A to ward 1 (the ward where you found the key).

Finding the key from ward A a second time is easy - the trick is in finding ward A after you find the key. Consider the following example:

A1 - H (notation here is <current_ward><door> - <destination_ward>)
A2 - A
A3 - B

B1 - B
B2 - A
B3 - C

C contains the key

D1 - E
D2 - D
D3 - C

E1 - E
E2 - F
E3 - D

etc.

Now, consider the door sequence starting in A: (2, 3). Certainly, if you were given the opportunity to be transported back to A, you would be able to find the room with the key again. But finding A will need to be confirmed by the route used to arrive at C - in this case door 2 and then door 3. If you should stumble on ward E and use the sequence (2, 3), you would also end up at C, and draw the conclusion that E was A. Thus you would not be able to accurately differentiate between A and E.

Quote:

however, I expect that a non-repeating pattern of doors being taken would need to be used, so as to avoid potential problems with not knowing when you started going through the "same" door for a ward, since that number door was also a door from an adjacent ward that took you into that ward - at least for the first couple of steps...

Absolutely - repeating sequences are definitely out - not only in the beginning - well spotted.

Quote:

I suppose now the challenge is two-fold: Find an optimal combination to use while moving from Ward A to the key, and then, having found the key, perfect the mapping of the ward doors in order to, as quickly as possible, determine which ward is ward A, and then move as quickly as possible to ward E.

This is indeed a challenge - and will probably remain the solution to strive for. Whether an optimal sequence can be found - or even exists - will remain the subject of this thread, I think.

Quote:

I would also add that I don't think I've used more than 100 steps to escape, although some attempts can get close to this, so my guess about taking a long time appears to be unfounded, when compared with those 100 prisoners in the complex across the street...

Yep - not too long.

Three Hands - are you still using your "probabilities" approach? If so, I still maintain that there is a more elegant mapping method - however, I do think probability can be put to good use in helping to decide which door to try at any given node, although only in cases where this information is not already available inherently within the mapping method.

Title: Re: The ASYLUM
Post by Three Hands on Jul 27^th, 2004, 10:15am

on 07/27/04 at 09:23:02, mattian wrote:

Not true. It is possible your transition was A-B-C-D-D-C-B-A, for example. There are many other such examples which take you from A to A in seven steps.

For this, it was along the lines of "if you get back to A within 7 steps, then you know you cannot have got back to A via H, if you started A-B". This is just an observation so that you can map the connection from A to B with certainty as the last door you passed through, since from B it would be 7 steps to go the long way round to A (B-C-D-E-F-G-H-A). However, without further information, if you took 7 steps from B to get to A, you could not be certain whether you went B-C-D-E-D-C-B-A or B-C-D-E-F-G-H-A, or some other version. However, if you only take 6 steps, you know that the last step must have been B-A.

on 07/27/04 at 09:23:02, mattian wrote:

Indeed - This is where a lot of the difficulties in mapping back the trail from key to A come in - another variant on this would be:

A1: H
A2: A
A3: B

H1: H
H2: A
H3: G

With the starting combination (1,2), you would not be able to tell later if you started in A or H - a potential problem for complete solutions, so I think this puzzle will be more a case of maximising probability of escape ::)

on 07/27/04 at 09:23:02, mattian wrote:

Absolutely - repeating sequences are definitely out - not only in the beginning - well spotted.

;D

on 07/27/04 at 09:23:02, mattian wrote:

This is indeed a challenge - and will probably remain the solution to strive for. Whether an optimal sequence can be found - or even exists - will remain the subject of this thread, I think.

Indeed - but as I stated above, I reckon it will come down to more of a problem of "maximising probability", rather than guaranteeing

on 07/27/04 at 09:23:02, mattian wrote:

Three Hands - are you still using your "probabilities" approach? If so, I still maintain that there is a more elegant mapping method - however, I do think probability can be put to good use in helping to decide which door to try at any given node, although only in cases where this information is not already available inherently within the mapping method.

I've been approaching the puzzle with using a chart to map the Asylum having found the key based in the initial location of the key. Essentially, the probabilities are more looking at time expected for a successful map, as each time you move away from the key, you can only keep track of which doors you're going through, and also how many steps it takes you to get back to the key. If you get back immediately, then the connection between rooms is simple. If it takes two steps to get back, then you must have gone Same-Back, and so you get a full map of the room you were just in. If it takes 3 steps, then you must have gone Forward-Back-Back (assuming you do not go through the same door for the first two steps, otherwise it could be Same-Same-Back), so you get even more information (including the full map of the first room you went to from the key), but beyond that, it becomes impossible to tell (I think). However, using what information I can from this chart, it becomes simpler to navigate - the tricky part being retracing steps for Ward A. So it could potentially take quite a long time to do all of this (at least with my level of detail while mapping), but, as I said, I think I'd be out of the Asylum before those 100 prisoners with one lightbulb get away...

Just out of interest, what method have you been using for mapping the Asylum, mattian?

Title: Re: The ASYLUM
Post by mattian on Jul 27^th, 2004, 11:04am

Quote:

... seven steps or less ...

I understand what you mean now - quite right - sorry.

Quote:

so I think this puzzle will be more a case of maximising probability of escape

Right - which is an interesting objective. But it will be a function of the position of the key and the number of transitions used to find it. The range will be anything from 100% likely (in cases where the key is found unambiguously) down to whatever maximum minimum we can find.

Quote:

Just out of interest, what method have you been using for mapping the Asylum, mattian?

Well it's hardly kosher for the author of a puzzle to relinquish his solution too early in the game, but I will post it here anyway - since Wu's site isn't seeing much traffic at the moment. Also - it looks as though it might be more interesting to investigate those probabilities as a team since I haven't solved that aspect of the puzzle myself - yet.

::
Let's consider the case in which the key is found in the first room - ward A.

STEP 1
======

Choose a door and write down the location and the door choice.

Example: A1

If you find the key again then you know the following edges:

A1:A
A2:B
A3:H

The choice of B and H in this initial case is completely arbitrary. So for convenience it is best to choose B according to the next door chosen.

Now consider the case in which you do not find the key; It means that you transitioned to ward B - again, it may be ward H, but it doesn't matter. In this initial step - it's arbitrary, as long as all decisions following this one conform to this chosen convention.

Okay... In this case, you know then the following edges:

A1:B
A2:A|H
A3:H|A

STEP 2
======

From ward B you now choose a door - Example: B2

Write down the possible transitions that have taken place:

a) A1:B2:A
b) A1:B2:B
c) A1:B2:C

The possible outcomes are: a) you find a key, or b) you don't find a key.

If you find a key then (a) is the only possible transition sequence and (b) and (c) are eliminated. And you have among your known edges the bi-directional edge: A1:B and B2:A - move the key to B.

If you don't find a key then (a) can be eliminated and BOTH (b) and (c) survive.

STEP 3
======

From ward B or C (you don't know which yet), choose a door - Example: [B|C]3

Possible transitions:

a) A1:B2:B3:A
b) A1:B2:B3:B
c) A1:B2:B3:C
d) A1:B2:C3:B
e) A1:B2:C3:C
f) A1:B2:C3:D

Two outcomes - key or no key.

key: Eliminate (b), (c), (d), (e), (f)
no key: Eliminate (a) and (b) - (b) is eliminated because it claims that B2 and B3 lead to B which is a contradiction.

STEP 4
======

Choose a door to establish the grounds for a contradiction to eliminate potential transition maps.

In this case door 1 is a good choice because it adds a second B entry to (d) which narrows the options down there - essentially we're challenging the paths we have to turn up the key - if it does, we learn something, if it doesn't, we also learn something.

So

a) A1:B2:B3:C1:B
b) A1:B2:B3:C1:C
c) A1:B2:B3:C1:D
d) A1:B2:C3:B1:A
e) A1:B2:C3:B1:B
f) A1:B2:C3:B1:C
g) A1:B2:C3:C1:B
h) A1:B2:C3:C1:C
i) A1:B2:C3:C1:D
j) A1:B2:C3:D1:C
k) A1:B2:C3:D1:D
l) A1:B2:C3:D1:E

key: Eliminate everything except (d).

no key: Eliminate (f) contradiction {B2:C, B1:C}, (h) contradiction, etc.

ETC.
===

This list will grow long and deep - but it's easy to maintain. When the key is found - the path (or potential set of paths) will remain after the others are all eliminated. The unique solution can be failure testing using the key as a marker which verifies or rejects potential solutions based on whether the key is found according to expectation. When the key is found after a long dry spell, many of the transitions will already be known - via the known set of paths that satisfy the sequence.

In the case where the key is not in the first room:

If the key is in the second room and found in the first move - it is essentially the same as finding it in the first room. If the key is in the third room and found after two transitions, then - again - the same solution can be used.

Simply put: If the key is found within the first two transitions, there is no issue.

If the key is not found within the first two transitions, then the same principle may be used, but it may easily result in multiple solutions. Suppose, for argument's sake that three of a potential four solutions indicate that a particular ward X is ward A while the fourth solution shows that ward Y is ward A - clearly there is a 75% chance that ward X is ward A.

::

Title: Re: The ASYLUM
Post by rmsgrey on Jul 28^th, 2004, 5:57am

It looks like, for a given key-finding strategy, it's always possible to design a set of links so that you can only narrow down your start point to one of seven rooms. Certainly it's possible to come up with scenarios where no search pattern can distinguish between three rooms you could have started in...

Title: Re: The ASYLUM
Post by mattian on Jul 28^th, 2004, 6:10am

Yes - if you were to apply an additional constraint, for example, which says:

If door d in ward x leads to ward y, then all other doors leading to ward y are NOT door d.

Then it would be possible to unambiguously find any ward by backtracking along the transition path.

Title: Re: The ASYLUM
Post by mattian on Jul 28^th, 2004, 6:14am

Oh! By designing a set of links, you mean as the patient solving the problem, and not the architect of the Asylum.

I can't see how such a strategy might be chosen; without some additional information.

Title: Re: The ASYLUM
Post by Three Hands on Jul 28^th, 2004, 9:43am

Mattian, I think the search pattern you described (having found the key) is more or less what I have been using (just less well explained) - although I'll confess not in the same level of detail, since I've been somewhat lazy about keeping notes... ::). However, I would propose that, if working on the premise that the key was not found in ward A, it may be simpler to label the wards while mapping from where you find the key with different terms - I think rmsgrey's suggestion (when we were discussing this offline) of labelling the ward where you find the key K, and the other wards L,M,N,O,P,Q and R - similar to the alphabetical labelling of the wards previously, is the most suitable I can think of.

One other interesting point from the probabilities - after finding the key, and so labelling the ward you find it in K, you also know which door that either L or R (depending on subsequent labelling) connects to K from. This then means that for the start of your maping, having left K, you have a 2/3 chance of returning to K through the door which you first went through to get to K. For instance, if, after some moderate searching, you go through door 1 in ward x (unknown ward), and find the key. After beginning your map with the room you just enter as K, after leaving K, trying door 1 has a 1/3 chance of success from one direction, but is guaranteed to be successful in the other - you just don't know which is which. Say that you actually came to K from L through door 1: The possibilities are therefore (after leaving K)

Go to R:
1 = K/R/Q
2 = K/R/Q
3 = K/R/Q - 1/3 chance for each

Go to L:
1 = K
2 = L/M
3 = L/M

So going through door 1 guarantees returning to K in one direction, and has a 1/3 chance of working in the other, and so has a 2/3 chance overall of returning you to K, while doors 2 and 3 have a 1/6 chance. This kind of probabalistic method could possibly be expanded for further optimising a mapping technique (possibly to justify more clearly what I say below), but I'll leave that for some other time, when I'm thinking more mathematically.

In terms of trying to ensure accurately back-tracking to A, and so being able to find ward E after finding the key, I also think that, when mapping from room L (arbitrary label for <room entered after K found>) and onwards, attempting the door you tried in the sequence prior to succeeding in finding the key. To expand on the example above, the sequence in finding the key finished (2,1). Knowing that the connection from L to K is through L1, trying L2 should tell you one of two things - either L2 leads to L - causing a repeat motion in your search, that L3 goes to M, and that either door 2 or whichever door preceded it in your search for K leads from M to L (assuming you're not unlucky enough to get a false trail through both L1 and R1 going to K) - or L2 leads to M - implying either M2 returns you to L, or you're going the wrong way round the asylum to back-track to A along the route you came. In either case, it seems to me to be a useful method for recreating your journey though the asylum from A to K

I hope this is clear enough - as you may have guessed, ideas I have do not always get translated clearly from brain to text...

Title: Re: The ASYLUM
Post by mattian on Jul 28^th, 2004, 10:31am

The reason I thought my solution differed from yours is because yours seemed to get more and more complex with each transition while mine became more volumous. In other words - your descriptions of probabilities at each ward became something like, for example: w * (x * (y * (z)))), where dependencies were described in terms of previous dependencies.

I saw this as an unnecessarily complex description of the solution. In my solution - when the key is found for the second time, all but two or three transition paths are eliminated (by contradiction) and only the very specific possibilities remain. It is not concerned with why things happened the way they did - only that they did happen the way they did. The interesting thing here is that finding the key (representing a single bit) after a long set of unfruitful transitions gives us a large amount of information all at once. I think of it in the same context as the red-eyed/brown-eyed monk riddle in the medium section of Wu's riddles - for n monks, there is no conclusive information for (n-1) days, and then all the information is confirmed on the nth day.

Essentially, I think your initial solution description was proposed as a relative interpretation of each transition while mine is absolute. As you say, they may very well boil down to the same thing, but I wonder how easily your approach can be maintained for large numbers of transitions.

Quote:

...it may be simpler to label the wards while mapping from where you find the key with different terms...

Right - I did the same thing.

Quote:

...having left K, you have a 2/3 chance of returning to K through the door which you first went through to get to K.

Nice. That's what I was suggesting earlier when I said that probabilities could help in deciding which door to choose in any given ward. And I agree - I think there is potential to take it further in the complete solution - principally in the final decision as to which ward is the true ward E.

Title: Re: The ASYLUM
Post by Leonid Broukhis on Jul 29^th, 2004, 9:09am

This puzzle reminded me of a problem concerning a sequence of ternary digits with no consecutive repetitions of any length Sloane's A085794 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A085794), It seems that this sequence guarantees the lowest average number of moves before finding the key because it escapes out of any loop.

Title: Re: The ASYLUM
Post by mattian on Jul 29^th, 2004, 10:46am

NICE! I was trying to find a good sequence on my own. I thought there might already exist such a sequence - but didn't know how to find it.

What is the guaranteed number of moves then to find the key? i.e. Worst case scenario?

Title: Re: The ASYLUM
Post by mattian on Jul 29^th, 2004, 11:13am

The portion of the sequence that Leonid posted, will not reach rooms D, E, F or G in the worst case: Here is a test sequence:

A0, A1, B0, A2, H0, A1, B2, B0, A2, H1, H0, A1, B2, B0, A1, B0, A2, H0, A1, B2, B0, A2, H1, H0, A2, H0, A1, B0, A2, H1, H0, A1, B2, B0, A1, B0, A2, H0, A1, B2, B0, A2, H1, H0, A1, B2, B0, A1, B0, A2, H1, H0, A1, B2, B0, A2, H1, H0, A2, H0, A1, B0, A2, H1, H0, A1, B2, B0, A1, B0, A2, H0, A1, B2, B0, A2, H1, H0, A1, B2, B1, C0, B2, B0, A1, B0, A2, H1, H0, A1, B2, B0, A1, B0, A2, H0, A1, B2, H0, A2, H1, H0, A2, H0, A1

That's 105 steps to cover four rooms in the worst case (in the worst case I could find, anyway).

Surely the best sequence will depend on the number of nodes in the network. In other words - is this sequence not constructed as a function of the number of nodes to which it relates?

For example: Take the case of two wards - a sequence to escape all loops would be something like: 0, 1

Three wards: 0, 1, 0, 1, 2, 1

I don't know what I'm getting at here, but it seems as though a temporally unique sequence has a pattern to it which specifically repeats with minor changes. The frequency of this very slightly varying pattern should have some relationship to the number of wards that need to be covered by the sequence.

P.S. If anyone knows what I'm talking about, please explain it to me.

Title: Re: The ASYLUM
Post by Three Hands on Jul 30^th, 2004, 7:46am

I think I understand the problem you're looking at, but I don't think I can provide any answers for it.

Basically, for the given path, you want to be able to guarantee that you enter all 8 wards at some point, but without using a repeating pattern to search with. This way, you're guaranteed to find the key at some stage during the search, and also have the best chance of being able to determine where Ward E is after finding the key.

In order to guarantee that you have gone in each direction, though, my first guess is that you need to be certain that for each ward, at some point on the pattern you would, assuming worst case, have passed through all three doors. Because of this, the more wards you have already been into, the harder it is to guarantee that for either of the wards at the edge of your search you will at a given point, have passed through all three doors. As you have shown, for one, to and three wards, it is fairly simple, but four wards looks to be more tricky (although guaranteed using the pattern suggested by Leonid), and five, six, seven and eight wards will probably become even more difficult to work out.

So finding an optimal pattern for the search for the key looks like it's going to be harder than I' originally suspected :-/

Title: Re: The ASYLUM
Post by mattian on Jul 30^th, 2004, 8:00am

I'm sure the sequence to which Leonid referred, will work, however, I don't know how to continue it. I did manage to spot some patterns within patterns within the partial-sequence, but nothing that would suggest how to continue it - unless we simply verify with each new sequence element - using brute force - that time-shift uniqueness remains in effect.

Also - I don't know at this point if we're even looking for the optimal sequence - I would be happy to find a sequence that simply guarantees a visit to all eight wards. I think I have an idea though - using the same method used in my posted solution, I could map out all possible outcomes and eliminate redundancy - ultimately, despite my efforts to keep the visited wards to a minimum, the sequence should force all outcomes into the all-wards-visited state. I'll give that a go.

... time passes ...

hmmm - I wonder if that will work.

Anyway, with a worst case for finding the key, I believe we could calculate the probabilty of finding the true Ward E in the worst case.

Title: Re: The ASYLUM
Post by Leonid Broukhis on Jul 30^th, 2004, 10:13am

For a simple square-free sequence generator, see

Sloane's A086713 (http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A086713).

Title: Re: The ASYLUM
Post by asterix on Jul 30^th, 2004, 1:09pm

That really doesn't seem to be the best sequence for what we're trying to do. The problem is that it tries so hard to avoid any pattern at all, when, in fact, sometimes you will want some pattern. Suppose three rooms in a row have the same door combinations. The sequence never lets you go through a door twice in a row (at least in the first hundred steps that are listed), so to pass through all three you would need a sequence like A1B0B1C0C1D. Will this sequence ever have a 10101 subsequence? Judging from the beginning of the sequence, it would seem that any subsequence of four steps always contains all 3 digits (0,1,2).

Title: Re: The ASYLUM
Post by asterix on Jul 30^th, 2004, 1:28pm

Let me amend that. It will get through eventually taking some backsteps along the way. But in mattian's worst case scenario where you've taken 105 steps and you're still in room A, an optimized set of steps would recognize that as soon as you've taken 7 steps and not found the key some door combinations are ruled out. Long before you get to 105, it should be possible, somehow, to realize you're just going back and forth, and by ruling out the all the combinations that would have carried you around the whole asylum, get you out of the loop a lot faster than the sequence will

Title: Re: The ASYLUM
Post by Leonid Broukhis on Jul 30^th, 2004, 4:25pm

on 07/30/04 at 13:09:38, asterix wrote:

Will this sequence ever have a 10101 subsequence? Judging from the beginning of the sequence, it would seem that any subsequence of four steps always contains all 3 digits (0,1,2).

By definition, no subsequence of any length appears twice in a row, therefore any 4 steps always contain all 3 digits.

Title: Re: The ASYLUM
Post by mattian on Jul 30^th, 2004, 5:51pm

What do you think of asterix's point though, Leonid. I think it sounds valid - the same thing was bothering me - it does seem as though the sequence, while guaranteed ultimately to visit all wards, is catering more to the worst case scenario than to the average combination of doors.

Unfortunately though, asterix, your idea will not work because there is no information in the room which can tell you you're back in ward A after 105 steps. For all you know you could be one transition away from finding the key - or you could be 500 away. I do agree that it would be nice to trim the fat of this guaranteed approach, but I don't see that it could be done without some risk of being caught in a loop somewhere.

The reason why I see asterix's point is because in all my test runs so far - I have found the key in under 100 transitions using an on-the-fly guess at a non-repeating sequence. I'm sure I've been lucky, but I'm also fairly confident that the average would not exceed 100. Leonid's suggestion offers security in exchange for transition-count.

Title: Re: The ASYLUM
Post by Leonid Broukhis on Jul 31^st, 2004, 12:35am

Right. I think that the sequence I've proposed could be an overkill - it will work in an arbitrary graph, and our graph is quite a special case. According to my calculations, there are 3⁸2⁶ different variants of connections; the key can be in any of 7 rooms (that is 21.5 bits). Each step from an empty room to an empty room brings a fraction of a bit of information about the connectivity (the first one brings approx 0.144 bits. Therefore, a rough estimate of the number of steps required to escape is 149 + N, where N <= 4.

Title: Re: The ASYLUM
Post by mattian on Jul 31^st, 2004, 9:37am

Nice! But how does that help us choose a sequence? Or doesn't it? Does it simply estimate the worst case for an on-the-fly guess at a non-repeating sequence? It would certainly tie in with the practical numbers I've encountered thus far.

Title: Re: The ASYLUM
Post by Leonid Broukhis on Aug 1^st, 2004, 3:03pm

One consequence of my observation is that each move must maximize the number of configurations that are rejected by discovering an empty room.

Pardon my wild associations, but this reminds me of the game of Mastermind, a.k.a. cows and bulls. The optimum strategy there is to pick a guess with the max of min of rejected combinations over all possible answers.

Title: Re: The ASYLUM
Post by mattian on Aug 5^th, 2004, 1:43pm

Right - that is what my solution tries to do. But I do it on the fly with no theory behind it. In other words, I keep track of all possible paths, and choose the next door in order to force an affirmation or contradiction based on my finding the key or not, respectively. It would be nice to analytically formalise this approach rather than manually examining the paths and looking for door selections that will force a result.

Title: Re: The ASYLUM
Post by mattian on Aug 5^th, 2004, 1:47pm

Re: Mastermind

Yes, but unlike Mastermind which provides you with one of 3^4 results for each guess, the Asylum provides you with one of only two.

i.e. Mastermind feedback can be: (0,0,0,0; 0,0,0,1; 0,0,0,2; 0,0,1,0; ...)

while the Asylum feedback can be: (0; 1)

Title: Re: The ASYLUM
Post by rmsgrey on Aug 6^th, 2004, 5:17am

Way off topic, but since Mastermind doesn't tell you to which position a given piece of feedback belongs, there are only 14 possible responses (0,0; 0,1; 0,2; 0,3; 0,4; 1,0; 1,1; 1,2; 2,0; 2,1; 2,2; 3,0; 3,1; 4,0 - 1,3 is impossible since if 3 are in the right place, the fourth is either also in the right place (0,4), or the wrong colour(0,3))

Title: Re: The ASYLUM
Post by mattian on Aug 6^th, 2004, 6:47am

Right! You are correct - still more resolution though, than the Asylum.

Title: Re: The ASYLUM
Post by asterix on Aug 6^th, 2004, 8:29am

Just out of curiosity, I put together a simulation. If I did it correctly (a big if), it took an average of 57 moves to visit all 8 rooms using the non-repeating sequence. But when I reached the end of the 105 moves listed for the sequence, I just quit and called it good. (The failure rate was a whopping 30%) If you use the same door twice in a row after every third move, you can get the average down to 45. And it seems the failure rate drops to 5%.
Maybe someone else would like to confirm my estimates (even I'm a little skeptical).

Title: Re: The ASYLUM
Post by mattian on Aug 6^th, 2004, 8:36am

The only issue I see with your simulation is that you assume success after 105 iterations, regardless of the outcome.

That will artificially lower your average.

Leonid did provide a link to method for establishing this sequence, so you should be able to continue beyond 105 to accurately extract an average for that sequence.

However, Leonid and I agree that this is not the optimal sequence - it's too heavy for the problem we're trying to solve. But it is still useful to use the number from this sequence as the benchmark for the success of other sequences - as long as there is no special handling at 105.

Title: Re: The ASYLUM
Post by asterix on Aug 6^th, 2004, 10:34am

Okay, I tried again. I took the sequence to 10,000 places.
What I found is that the sequence still failed in almost 30% of the cases. Only 70 out of 1000 trials did it find all the rooms somewhere between 100 and 10000 steps. The longest solution took 3113 steps.
The average of just the successes was about 44 steps.

Again, if I repeated a door choice after every three moves, the average was around 40-42 steps. But this process never failed to reach all the rooms. The longest it took was 287 steps.

Title: Re: The ASYLUM
Post by mattian on Aug 6^th, 2004, 10:45am

Interesting - I'l be interested to know how a perfectly random sequence performs. Can you throw a random generator in there and extract an average?

Title: Re: The ASYLUM
Post by asterix on Aug 6^th, 2004, 12:07pm

Random did about the same as my second pattern. I just realized two things. One is that the formula given to create the sequence is not the same non-repeating sequence as the first 105 digits suggested.
The other is a great big "Duh!!!" This generated sequence is actually loaded with repetitions. It is created entirely with the 3 sub-sequences: 01201, 020121, and 0212021. There will be times when these sequences, always starting out in the same 3 or 4 rooms will always end up in the same 3 or 4 rooms. (for example. From room A, you might end up in A, B, or C, depending on which of the three sequences you're using. If a start in B and C do the same thing, you never get anywhere else. What we really want is some sort of sequence that goes through every possible variety of some length of subsequences. How long a subsequence, I'm not sure. Maybe 4 digits; so you'd hit everything from 0000 through 2222, in as varied an order as possible. Anyone know how to formulate that sequence?

Title: Re: The ASYLUM
Post by william wu on Aug 6^th, 2004, 3:30pm

on 08/06/04 at 12:07:14, asterix wrote:

What we really want is some sort of sequence that goes through every possible variety of some length of subsequences. How long a subsequence, I'm not sure. Maybe 4 digits; so you'd hit everything from 0000 through 2222, in as varied an order as possible. Anyone know how to formulate that sequence?

Willywutang and the Number Stamp:
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1063089039

With apologies to De Bruijn.

Interesting problem mattian! Just reading it now. Looks like you put a lot of work into this :)

Title: Re: The ASYLUM
Post by mattian on Aug 6^th, 2004, 4:05pm

Kind words - thanks. Glad you like it. There'll be more. And let me know if you want me to model any other puzzles on your site - with a pretty GUI, I mean.

Check the What Am I section for my latest two puzzles:
Two Ancient Men, and
The year of Romans among Arabs is past.

Everyone seems to be afraid of them.

Title: Re: The ASYLUM
Post by asterix on Aug 6^th, 2004, 5:14pm

The other riddle isn't quite what I had in mind. The solutions there are too orderly, using up all the 0's right away, for instance. My idea, which may not be the best solution for the asylum, but could be a worthy puzzle anyway, would keep every smaller subsequence as far away as possible from its nearest copy. Here's an imperfect solution to give you an idea what I had in mind. Start with all possible 2 digit patterns, like 0012022110. The next 9 digits should do the same thing but in a different order, and then one more time, so that in the first 29 digits you have every 3 digit pattern. eg.
0012202110 221002011 121200102 (That actually skips a couple 3-patterns, but you get the idea.)
Find two more solutions to that problem to create every 4 digit pattern in the first 84 digits. And so on. This sequence will have as few repetitions of any length within it as possible, and most of them will be far enough apart to make it unlikely that you'll be in the same room at the start of each, so that the repetition does not matter. (some, short, repetition is not fatal, just not optimal).

Title: Re: The ASYLUM
Post by mattian on Aug 6^th, 2004, 5:37pm

Hey Asterix, you should register with the forum so that we can track your contributions throughout the site.

Title: Re: The ASYLUM
Post by mattian on Aug 6^th, 2004, 5:40pm

I haven't had much time to work on this problem this week. I will run my simulation and play with some sequences and let you know what I find. Perhaps I will have time this weekend.