The Nightstar Zoo

Nightstar IRC Network - irc.nightstar.net
It is currently Sun Dec 17, 2017 7:01 am

All times are UTC - 6 hours [ DST ]




Post new topic Reply to topic  [ 14 posts ] 
Author Message
 Post subject: The maze
PostPosted: Thu Mar 13, 2003 7:43 pm 
Fred and George have a long standing rivalry between them. They both love mazes, and are always writing them for eachother. Fred, however, is much better than George at solving them, and has never been stumped yet.

Today, George is fed up. "Fred, I'm going to stump you this time. I'm gonna make the hardest maze you've ever seen. You'll have to go through trapdoors and secret passages, teleporters, and visit every room. I'll make you lost at every corner and want to quit before you pass the third branch, I will. And I won't give you any restarts either."

Fred thinks for a moment. "George, you go ahead and make that maze, and if everything you say about it is true, then I will have it done in the time that it takes to trace with the pencil."

What makes Fred so sure?


Top
  
 
 Post subject:
PostPosted: Thu Mar 13, 2003 10:02 pm 
If he has to visit every room, then any room in the maze is on a correct path to the goal.


Top
  
 
 Post subject:
PostPosted: Thu Mar 13, 2003 10:33 pm 
Offline
Energizer Bunny
User avatar

Joined: Wed May 22, 2002 12:24 am
Posts: 1634
But that's not necessarily true... I can create a lot of mazes where one of the rules is that you have to visit every room and that you can't retrace your steps... and so entering a particular room at the wrong time can trap you.

Vorn


Top
 Profile  
 
 Post subject:
PostPosted: Thu Mar 13, 2003 11:56 pm 
Vorn the Unspeakable wrote:
But that's not necessarily true... I can create a lot of mazes where one of the rules is that you have to visit every room and that you can't retrace your steps... and so entering a particular room at the wrong time can trap you.

Vorn


Depends on your definition of "retracing".


Top
  
 
 Post subject:
PostPosted: Fri Mar 14, 2003 1:23 am 
The tradional way of navigating a maze is to always turn in the same direction whenever you have a chance to (usually right, I'm not going to get into the reasons for that now). However this doesn't always work with multi-level mazes.

Still it's a good tip if you're ever trapped in a maze by some supervilian.


Top
  
 
 Post subject:
PostPosted: Fri Mar 14, 2003 1:49 am 
The quickest way to get to the end of any maze is to go straight through the walls. In this case, just stop through all the rooms on the way out.


Top
  
 
 Post subject:
PostPosted: Fri Mar 14, 2003 11:24 am 
Dark_Tiger wrote:
The tradional way of navigating a maze is to always turn in the same direction whenever you have a chance to (usually right, I'm not going to get into the reasons for that now). However this doesn't always work with multi-level mazes.


Yes, that's good, but IIRC it doesn't work if the maze has some walls which aren't connected to the outside wall.


Top
  
 
 Post subject:
PostPosted: Sat Mar 15, 2003 2:04 pm 
Darth Paradox wrote:
If he has to visit every room, then any room in the maze is on a correct path to the goal.

Darth has the right idea, but this isn't really the solution, just a key point. Fred is completely confident that he will make the correct choice on the first try every time he reaches a branch in the maze. Why is this?

And can you prove it?


Last edited by Pi on Sat Mar 15, 2003 2:12 pm, edited 1 time in total.

Top
  
 
 Post subject:
PostPosted: Sat Mar 15, 2003 2:10 pm 
GrassyNoel wrote:
Dark_Tiger wrote:
The tradional way of navigating a maze is to always turn in the same direction whenever you have a chance to (usually right, I'm not going to get into the reasons for that now). However this doesn't always work with multi-level mazes.


Yes, that's good, but IIRC it doesn't work if the maze has some walls which aren't connected to the outside wall.


It does work on any finite planar maze in which both the entrance and exit are on the outside wall, regardless of whether there are 'floating' walls.

Where it breaks down is A) When the exit is not on the outside of the maze (ie: in the center), and B) When the maze is nonplanar (ie: trapdoors, teleporters, or secret passages that allow two paths to cross without intersecting). In either of these cases, a loop in the maze can defeat this algorithm.


Top
  
 
 Post subject:
PostPosted: Tue Aug 26, 2003 9:08 pm 
Pi wrote:
Darth Paradox wrote:
If he has to visit every room, then any room in the maze is on a correct path to the goal.

Darth has the right idea, but this isn't really the solution, just a key point. Fred is completely confident that he will make the correct choice on the first try every time he reaches a branch in the maze. Why is this?

And can you prove it?


Because there are no wrong choices. There is nothing in the stated rules that say that Fred can't retrace his steps, and if he has to visit every room *and* there are branches he *must* be allowed to revisit rooms.

In short Fred probably won't choose the quickest path, but there is no way he can fail to solve it on the first try given the stated conditons.

Of course if certain rooms can be declared to be non-revisitable then it would be possible to trap Fred if a wrong choice is made.


Top
  
 
 Post subject:
PostPosted: Tue Aug 26, 2003 10:54 pm 
Isn't this just one of those "Keep your left hand on the wall at all times" things? Just take the first left (or right if you prefer) at every turn. Upon hitting a dead end turn around and continue.

To defeat any loop, just take the next exit to the right from the left that lead to the trapdoor, teleporter, etc. IE, you're travelling down a previously travelled corridor. You know a teleporter is the next left, so instead of going left, take the second from the left.

In other words, where you would normally loop, don't take the first available left. ;)


Top
  
 
 Post subject: Re: The maze
PostPosted: Tue Aug 26, 2003 11:36 pm 
Pi wrote:
Fred and George have a long standing rivalry between them. They both love mazes, and are always writing them for eachother. Fred, however, is much better than George at solving them, and has never been stumped yet.

What makes Fred so sure?



Note, <b>They both love mazes, and are always writing them for eachother</b>

If they write/draw them, then of course he'llhave it solved with the trace of a pencil...as it's with a pencil that he makes his way thru!


Top
  
 
 Post subject:
PostPosted: Wed Aug 27, 2003 12:13 am 
The original solution to this one had been mostly answered by Darth. The idea was this:

First of all, no hint was made in the boasting that there was any state to the maze besides what room you're in. This allows us to be sure that if you visit the same room twice, your potential options for the rest of the maze are identical both times. It can be assumed that the maze can be represented by a nonplanar directed graph. (I can't think of a reason this wouldn't be true, but if so, please ignore it. Fred and George did)

Most of George's boasting was extraneous information, but the key point to pick out was that George said Fred would have to visit every room. This allows us to make two more assumptions about the maze. The first assumption is that, from any vertex on the graph, there exists a path to the exit. The second assumption is that every correct path in the maze goes through every room, and that, in particular, the optimal (shortest) path goes through every room.

Given these assumptions, it can be proven that, at each vertex in the graph, there is exactly one edge leading to a vertex that has not been visited yet. (Proving so is left as an exercise to the reader... :evil: ) Fred's algorithm is to start tracing at the beginning, and at each room, simply move to the next room that doesn't have a pencil line already in it. He will trace the optimal solution to the maze.



Vorn the Unspeakable wrote:
But that's not necessarily true... I can create a lot of mazes where one of the rules is that you have to visit every room and that you can't retrace your steps... and so entering a particular room at the wrong time can trap you.


Actually, Vorn, I don't believe that such a maze is possible without either keeping state data other than location, or by redefining "room" to include more than one vertex of the graph. (such as a single "room" with a partition and paths on both sides of the partition)


Top
  
 
 Post subject:
PostPosted: Wed Aug 27, 2003 12:18 am 
I like my answer...it just screams "Occam's Razor"


Top
  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 14 posts ] 

All times are UTC - 6 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group