|
On June 08 2009 13:32 evanthebouncy! wrote:Show nested quote +On June 08 2009 13:27 illu wrote:Pretty easy. + Show Spoiler +
Since at any point there is one way out, we can create a non-deterministic Turing Machine as follows:
1. At each position, move to any of the other possible positions that are not walls.
Then this Turing Machine will always accept, by construction of the maze. We know that non-determinism gives no extra computation powers so we can come up with an algorithm by a Turing Machine to create this path, which executes on finite time.
The actual algorithm is extremely simple so I won't get too detailed in this. (wiki if you like). Just go with a breadth-first search and you will get a path that allows you to exit. As shown before this algorithm will complete on finite time which is what we want.
Too technical, i have no clue what you just said. just reading your (1) though: you cannot garentee that you "moved" in a sense that the robot does not know if its attempted move is not blocked by the wall.
You said it's more or less computer science. This is really standard stuffs. In fact I am not even a computer scientist and I know it.
EDIT:
just reading your (1) though: you cannot garentee that you "moved" in a sense that the robot does not know if its attempted move is not blocked by the wall.
That is irrevalent. So long as there is one possible path for an exit in finite time non-deterministic turing machine will give a pass. Try wiki on turing machines first.
|
Alright... I don't have anything yet, but a few observations are:
The sequence has to include up, right, left, and down, otherwise you can be trapped.
There has to be net motion in one direction in the case of a 1000x1000 maze with no walls or something.
Up, right, left, down does not work. In other words, you need multiple moves to up, right, left, down in some sequence?
If this is something I had no chance of getting in the first place, I would be pretty sad. It's midnight, so I'm going to try again tomorrow.
|
On June 08 2009 13:37 illu wrote:Show nested quote +On June 08 2009 13:32 evanthebouncy! wrote:On June 08 2009 13:27 illu wrote:Pretty easy. + Show Spoiler +
Since at any point there is one way out, we can create a non-deterministic Turing Machine as follows:
1. At each position, move to any of the other possible positions that are not walls.
Then this Turing Machine will always accept, by construction of the maze. We know that non-determinism gives no extra computation powers so we can come up with an algorithm by a Turing Machine to create this path, which executes on finite time.
The actual algorithm is extremely simple so I won't get too detailed in this. (wiki if you like). Just go with a breadth-first search and you will get a path that allows you to exit. As shown before this algorithm will complete on finite time which is what we want.
Too technical, i have no clue what you just said. just reading your (1) though: you cannot garentee that you "moved" in a sense that the robot does not know if its attempted move is not blocked by the wall. You said it's more or less computer science. This is really standard stuffs. In fact I am not even a computer scientist and I know it.
I c, lemme do some search on it.
|
On June 08 2009 13:37 Macavenger wrote:Show nested quote +On June 08 2009 13:32 evanthebouncy! wrote:On June 08 2009 13:27 illu wrote:Pretty easy. + Show Spoiler +
Since at any point there is one way out, we can create a non-deterministic Turing Machine as follows:
1. At each position, move to any of the other possible positions that are not walls.
Then this Turing Machine will always accept, by construction of the maze. We know that non-determinism gives no extra computation powers so we can come up with an algorithm by a Turing Machine to create this path, which executes on finite time.
The actual algorithm is extremely simple so I won't get too detailed in this. (wiki if you like). Just go with a breadth-first search and you will get a path that allows you to exit. As shown before this algorithm will complete on finite time which is what we want.
Too technical, i have no clue what you just said. just reading your (1) though: you cannot garentee that you "moved" in a sense that the robot does not know if its attempted move is not blocked by the wall. + Show Spoiler +It's been a couple years since I worked with Turning machines and non-determinism, so I'm a bit rusty, but reading his solution, I'm quite certain it correctly proves the existence of an algorithm. Non-deterministic Turing Machines can do some pretty interesting things, and can easily have paths that lead nowhere, which would be the equivalent of attempting to move into a wall.
His approach doesn't work. He can't move into a direction that isn't a wall because he doesn't know where they are. Even if he knew where the walls were it wouldn't be much different from a NDTM that moved into any direction at all and it would accept. This is nothing else than using a random direction every step.
|
On June 08 2009 13:46 ven_ wrote:Show nested quote +On June 08 2009 13:37 Macavenger wrote:On June 08 2009 13:32 evanthebouncy! wrote:On June 08 2009 13:27 illu wrote:Pretty easy. + Show Spoiler +
Since at any point there is one way out, we can create a non-deterministic Turing Machine as follows:
1. At each position, move to any of the other possible positions that are not walls.
Then this Turing Machine will always accept, by construction of the maze. We know that non-determinism gives no extra computation powers so we can come up with an algorithm by a Turing Machine to create this path, which executes on finite time.
The actual algorithm is extremely simple so I won't get too detailed in this. (wiki if you like). Just go with a breadth-first search and you will get a path that allows you to exit. As shown before this algorithm will complete on finite time which is what we want.
Too technical, i have no clue what you just said. just reading your (1) though: you cannot garentee that you "moved" in a sense that the robot does not know if its attempted move is not blocked by the wall. + Show Spoiler +It's been a couple years since I worked with Turning machines and non-determinism, so I'm a bit rusty, but reading his solution, I'm quite certain it correctly proves the existence of an algorithm. Non-deterministic Turing Machines can do some pretty interesting things, and can easily have paths that lead nowhere, which would be the equivalent of attempting to move into a wall. His approach doesn't work. He can't move into a direction that isn't a wall because he doesn't know where they are. Even if he knew where the walls were it wouldn't be much different from a NDTM that moves into any direction at all and it would accept. This is nothing else than using a random direction every step.
But there is always one way to exit, so when we expand our tree diagram we will have one accepting state somewhere. So I think my NDTM will accept any solvable mazes.
|
ven brings up a good point that it might be equivalent to a random solution, though.
Need to be less rusty, argh D:
|
That's not the issue. Your turing machine would work with information that it doesn't have (where the walls are). Also as far as I understand the question we have to provide a deterministic algorithm to solve the maze which your non-deterministic TM doesn't do. :o
|
Alright. This came to me while I was lying awake. I haven't thought too deeply about it, and I haven't even bothered to check it, but something like this:
+ Show Spoiler +Okay. This is a bit hard to put in words. First: move along the "x-axis" the maximum number of times that you can + 1. Second, move along the "y-axis" the maximum number of times that you can in the maze + 1. Then use the same process reversing the directions along both axes.
(For instance, in a 100x100 maze, you would move right 101 times first, and then move down 101 times, or move left 101 times and then down 101 times, or whatever. Thus, you can exit the maze if it's "blank")
Now, this should allow you to end up going directly to the furthest possible space "To the left" or "upwards". Now the problem that I saw was that you can end up in a shape where the robot can move 50 times left, 0 times upward, 50 times right, 0 times downward- if he gets stuck in two shapes like [ and ].
To counter that, inject a random single move in any direction between every two long moves.
Even if this isn't it, hopefully I'm at least on to something.
|
On June 08 2009 14:10 Zozma wrote:Alright. This came to me while I was lying awake. I haven't thought too deeply about it, and I haven't even bothered to check it, but something like this: + Show Spoiler +Okay. This is a bit hard to put in words. First: move along the "x-axis" the maximum number of times that you can + 1. Second, move along the "y-axis" the maximum number of times that you can in the maze + 1. Then use the same process reversing the directions along both axes. Now, this should allow you to end up going directly to the furthest possible space "To the left" or "upwards". Now the problem that I saw was that you can end up in a shape like
[ r ]
R is the robot. He moves left 50 times or something, moves up forty times, and then moves right 50 times: an infinite loop.
To counter that, inject a random single move in any direction between every two long moves. Even if this isn't it, hopefully I'm at least on to something.
You don't know the maximum number. I had a similar idea but without knowing how many times you can move you wouldn't know when to stop.
|
+ Show Spoiler +Yeah you do... Because the grid is only MxN, you can just use those numbers, right? If he runs into a wall, it's all good, he'll just stop there and continue going eventually in the next direction.
|
On June 08 2009 12:05 evanthebouncy! wrote:
The fine print:
By ANY valid maze it means that regardless of size of m, n, and regardless of maze design, the robot will be able to move outside the maze eventually. That is to say, while you are coding, you cannot assume a certain m, n, or design.
|
Yeah, not knowing m and n for the given maze really makes this more challenging. The only direction I can think to go with it at this point is some kind of spiraling thing, where you loop from 1 to k steps in each direction, then from k to 1, then increment k and repeat. Then you have to come up with some kind of crazy reordering of directions you're trying to avoid the collection points trap we were discussing early, I would think.
|
Yeah, I had the same idea of spiraling movement in my mind. Those pesky walls totally disrupting it of course :p
|
+ Show Spoiler +Suppose we are given the maze but not the starting position. Then we can solve the puzzle by looking at each possible starting position in turn. In short, we pick some box and assume the robot started there, giving it commands to solve the puzzle. Then, we pick a second box to assume the robot started in, see where the robot would be after our commands based on the first assumption, and give it commands to exit the maze. Etc.
Since the set of possible mazes is countable, we can adjoin the solutions for every given maze end to end and be done.
|
Now I doubt that within finite steps the solution can be achieved...
The spiral path may be promising solution, if there exsits a solution.
|
On June 08 2009 14:13 ven_ wrote:Show nested quote +On June 08 2009 14:10 Zozma wrote:Alright. This came to me while I was lying awake. I haven't thought too deeply about it, and I haven't even bothered to check it, but something like this: + Show Spoiler +Okay. This is a bit hard to put in words. First: move along the "x-axis" the maximum number of times that you can + 1. Second, move along the "y-axis" the maximum number of times that you can in the maze + 1. Then use the same process reversing the directions along both axes. Now, this should allow you to end up going directly to the furthest possible space "To the left" or "upwards". Now the problem that I saw was that you can end up in a shape like
[ r ]
R is the robot. He moves left 50 times or something, moves up forty times, and then moves right 50 times: an infinite loop.
To counter that, inject a random single move in any direction between every two long moves. Even if this isn't it, hopefully I'm at least on to something. You don't know the maximum number. I had a similar idea but without knowing how many times you can move you wouldn't know when to stop.
You don't have to know the maximum number. If you could guarantee that you had an algorithm capable of solving it for a given width/height you could run some loops varying the width height, increasing the maximum number the width and height can take each run through and then running the algorithm for those values. You would have to cover all of the possible width height combinations until you actually get to the real width/height.
|
On June 08 2009 15:06 moriya wrote:
Now I doubt that within finite steps the solution can be achieved...
The spiral path may be promising solution, if there exsits a solution.
Muirhead solved it.
|
sure hope the op has an answer not just a trick question that has no answer to it 
|
On June 08 2009 16:18 omG.[RaYnE] wrote:sure hope the op has an answer not just a trick question that has no answer to it
evan's questions are always legit. Most of them are difficult(to me at least), but all of them have "real" answers.
|
+ Show Spoiler +easy. bruteforce this shit. put your instructions in a dynamic array. Go through all the possibilities of instructions for the current size of the the array. ++the size of the array and you'll have it... eventually.
|
|
|
|
|
|
EPT
