Author |
Topic: The ASYLUM (Read 3712 times) |
|
mattian
Senior Riddler
 
Gender: 
Posts: 404
|
 |
Re: The ASYLUM
« Reply #25 on: Jul 30th, 2004, 5:51pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: The ASYLUM
« Reply #26 on: Jul 31st, 2004, 12:35am » |
Quote Modify
|
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 3826 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.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #27 on: Jul 31st, 2004, 9:37am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: The ASYLUM
« Reply #28 on: Aug 1st, 2004, 3:03pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #29 on: Aug 5th, 2004, 1:43pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #30 on: Aug 5th, 2004, 1:47pm » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: The ASYLUM
« Reply #31 on: Aug 6th, 2004, 5:17am » |
Quote Modify
|
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))
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #32 on: Aug 6th, 2004, 6:47am » |
Quote Modify
|
Right! You are correct - still more resolution though, than the Asylum.
|
|
IP Logged |
|
|
|
asterix
Guest
|
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).
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #34 on: Aug 6th, 2004, 8:36am » |
Quote Modify
|
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.
|
| « Last Edit: Aug 6th, 2004, 8:37am by mattian » |
IP Logged |
|
|
|
asterix
Guest
|
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.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #36 on: Aug 6th, 2004, 10:45am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
asterix
Guest
|
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?
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #39 on: Aug 6th, 2004, 4:05pm » |
Quote Modify
|
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.
|
| « Last Edit: Aug 6th, 2004, 4:07pm by mattian » |
IP Logged |
|
|
|
asterix
Guest
|
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).
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #41 on: Aug 6th, 2004, 5:37pm » |
Quote Modify
|
Hey Asterix, you should register with the forum so that we can track your contributions throughout the site.
|
|
IP Logged |
|
|
|
mattian
Senior Riddler
Gender:
Posts: 404
|
|
Re: The ASYLUM
« Reply #42 on: Aug 6th, 2004, 5:40pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove
