|
from me: Please leave some comments as they mean a lot <3.
Last day's puzzle was first solved by Konfustikator, while Pseudo_Utopia might be easier to understand.
+ Show Spoiler [solution] +
Total color is 6, consider row_y which looks like
row_y = {(0,y), (1,y), (2,y), ... (6,y)}
clearly, row_y is a row with y axis value of y, and its x values ranges from 0 to 6.
Since each row has 7 elements, then 2 of them must be the same color.
Now consider this area formed by
{row_0, row_1, row_2, ... row_6^7}
This is a huge tall rectangle with height 6^7+1 and width 7. Since with 6 colors, all rows of 7 elements have 6^7 kinds of coloring scheme, then with a height of 6^7+1 two rows, say row_i, row_j must have identical coloring scheme.
Then since both row_i and row_j has 1 color that's repeated, that color will form the rectangle, whos verticies are identical color.
Considering draw out a picture if this is not intuitive enough, but this is a very clean solution.
Today's puzzle is a bit into the computer science side, but still fairly math oriented. It is as follows.
You have a maze, here is how it's constructed:
the maze is made within a rectangular grid of size mxn, where m and n are arbitarily chosen natural numbers.
Of any grid, it can either be part a path or a wall.
From any point inside the maze, provided that it's not a wall, will have a way out.
Then clearly, to walk outside of a maze, you'll have to go up, down, left, right in some way.
You also have a robot, here's the property of the robot:
You can code the robot to move in a certain way. For instance, coding it with the sequence:
left, left, up, up will make the robot attempt to move left twice, and up twice.
If the robot is blocked on the left, executing the move "left" multiple times will not move the robot.
The robot has no sense of perception, that is to say:
-It cannot know if it hits a wall
-It cannot know where it is inside the maze
-It does not know how far it has walked
Your Job:
Code the robot in such a way that for ANY valid maze [that is to say, for any m, n maze size and for any valid maze construction of that size] the robot will eventually be able to get out.
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.
Some example pictures:
Here is an example of a valid maze, with the maze area being black and white, and the outside area colored green. where the robot starts at the red point, and executing the instruction:
up-up-down-down-right-right-left-left
then ends up at point blue.
Again, post anything that comes across your mind, and if you're confident that you have the answer, put it in a spoiler. GL!
Again, leave a comment, it'll be much appreciated and kept me doing these blogs.
Edit:
No "random move" algorithms please.
|
Hmm. Left, down, right, up(times infinity) would ensure that our robot friend could always make progress, but if he gets caught in four open squares it wouldn't work. This is an interesting one, but I don't think I know enough to solve it. T_T
|
Far worse than that, even in the example with the red dot, LDRU repeated endlessly just results in it moving back and forth between the dot and the square below it.
My first thought on reading the question was "yay implement BFS ezpz" and then I got to the part where the robot can't sense anything. ;; Trying to think of some kind of psuedo-BFS (or more likely DFS in this case) I could implement without feedback.
|
I just noted that doing the Zig-Zag route up-right m*n times puts the robot in some "accumulation points" at corners. Im thinking about up-right m*n times then twisting the direction so the up-right becomes left-up. I think the brute force solution is some sort of up-right, left-up, down-left, right-down (each one m*n times) and then if you do the same again the robot ends up at the same square so you can do repeat but this time in other direction. Damn its hard to explain.
|
Spoilering in case I'm getting close to the answer, but I don't think I'm there yet.
+ Show Spoiler +Thinking about it more, psuedo-BFS may be the way to go after all. Because of the maze definition, there is some sequence of moves that will get the robot out. You could have it essentially attempt all possible combinations in a logical order (i.e. U; R; D; L; UU; UR; UD; UL; RU... etc.) that's easily written through loops, and do the inverse after each attempt (i.e. say it tries the sequence UDLRUDUDRR, the inverse would be LLUDUDLRUD) to attempt to return to the starting point, then start the next sequence. The problem with that is that since you have no feedback, performing the inverse sequence of moves is unlikely to return you to the starting position.
|
On June 08 2009 12:50 Macavenger wrote:Spoilering in case I'm getting close to the answer, but I don't think I'm there yet. + Show Spoiler +Thinking about it more, psuedo-BFS may be the way to go after all. Because of the maze definition, there is some sequence of moves that will get the robot out. You could have it essentially attempt all possible combinations in a logical order (i.e. U; R; D; L; UU; UR; UD; UL; RU... etc.) that's easily written through loops, and do the inverse after each attempt (i.e. say it tries the sequence UDLRUDUDRR, the inverse would be LLUDUDLRUD) to attempt to return to the starting point, then start the next sequence. The problem with that is that since you have no feedback, performing the inverse sequence of moves is unlikely to return you to the starting position.
You can't do inverse.
For instance, say your robot has a wall on the immediate left.
The sequence LLL will be inversed to RRR, yet LLLRRR will certainly NOT make you go back to the original point.
|
For Malongo:
+ Show Spoiler +I looked at a couple of approaches very similar to that, and I don't think it quite works. Running some test cases on the example provided, the collection points can end up not being anywhere near the exit, and having no direct path between any collection point and the exit. If you got lucky and tried R-D followed by L-D immediately from the start, you'd get it, but you can't assume that kind of luck, and the starting position shown is not actually a collection point itself, so you can't really get back to it. Unless there's some way of juggling the order of attempts I haven't thought of, I don't think what you have is going to reliably produce a solution.
|
On June 08 2009 12:54 evanthebouncy! wrote:Show nested quote +On June 08 2009 12:50 Macavenger wrote:Spoilering in case I'm getting close to the answer, but I don't think I'm there yet. + Show Spoiler +Thinking about it more, psuedo-BFS may be the way to go after all. Because of the maze definition, there is some sequence of moves that will get the robot out. You could have it essentially attempt all possible combinations in a logical order (i.e. U; R; D; L; UU; UR; UD; UL; RU... etc.) that's easily written through loops, and do the inverse after each attempt (i.e. say it tries the sequence UDLRUDUDRR, the inverse would be LLUDUDLRUD) to attempt to return to the starting point, then start the next sequence. The problem with that is that since you have no feedback, performing the inverse sequence of moves is unlikely to return you to the starting position. You can't do inverse. For instance, say your robot has a wall on the immediate left. The sequence LLL will be inversed to RRR, yet LLLRRR will certainly NOT make you go back to the original point.
I said that in my explanation  It's why I said I didn't think I had it yet.
|
randomly choose the direction. even if it takes ages, at some point you will get out :o
|
On June 08 2009 12:56 Macavenger wrote:Show nested quote +On June 08 2009 12:54 evanthebouncy! wrote:On June 08 2009 12:50 Macavenger wrote:Spoilering in case I'm getting close to the answer, but I don't think I'm there yet. + Show Spoiler +Thinking about it more, psuedo-BFS may be the way to go after all. Because of the maze definition, there is some sequence of moves that will get the robot out. You could have it essentially attempt all possible combinations in a logical order (i.e. U; R; D; L; UU; UR; UD; UL; RU... etc.) that's easily written through loops, and do the inverse after each attempt (i.e. say it tries the sequence UDLRUDUDRR, the inverse would be LLUDUDLRUD) to attempt to return to the starting point, then start the next sequence. The problem with that is that since you have no feedback, performing the inverse sequence of moves is unlikely to return you to the starting position. You can't do inverse. For instance, say your robot has a wall on the immediate left. The sequence LLL will be inversed to RRR, yet LLLRRR will certainly NOT make you go back to the original point. I said that in my explanation It's why I said I didn't think I had it yet.
HAHHA i read everything but your last sentence. >_<
|
+ Show Spoiler +Also, you might want to revise the question a wee bit, since I think technically if you just tell the robot to choose a random direction at each move, statistically it will get out eventually... but I don't think that's really in the spirit of the problem.
|
+ Show Spoiler +loop LU * i, RU * i, RD * i, LD * i with i increasing every cycle from 1 to max(m,n) and reset i to 1 when if it reaches the upper boundary.
I guess you can trap this as well but I'm too tired to think properly :o
|
On June 08 2009 13:14 ven_ wrote:+ Show Spoiler +loop LU * i, RU * i, RD * i, LD * i with i increasing every cycle from 1 to max(m,n) and reset i to 1 when if it reaches the upper boundary.
I guess you can trap this as well but I'm too tired to think properly :o
It does not know what is a boundry.
|
On June 08 2009 13:04 Macavenger wrote:
Also, you might want to revise the question a wee bit, since I think technically if you just tell the robot to choose a random direction at each move, statistically it will get out eventually... but I don't think that's really in the spirit of the problem.
done
|
On June 08 2009 13:16 evanthebouncy! wrote:Show nested quote +On June 08 2009 13:14 ven_ wrote:+ Show Spoiler +loop LU * i, RU * i, RD * i, LD * i with i increasing every cycle from 1 to max(m,n) and reset i to 1 when if it reaches the upper boundary.
I guess you can trap this as well but I'm too tired to think properly :o It does not know what is a boundry.
Well, the algorithm does. I'm referring to i reaching max(m,n).
|
On June 08 2009 13:20 ven_ wrote:Show nested quote +On June 08 2009 13:16 evanthebouncy! wrote:On June 08 2009 13:14 ven_ wrote:+ Show Spoiler +loop LU * i, RU * i, RD * i, LD * i with i increasing every cycle from 1 to max(m,n) and reset i to 1 when if it reaches the upper boundary.
I guess you can trap this as well but I'm too tired to think properly :o It does not know what is a boundry. Well, the algorithm does. I'm referring to i reaching max(m,n).
Ah I should probably fix it...
By "Arbitary" I mean the algorithm provider does not know the size of m and n... I'll go fix it now. Thx.
|
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.
|
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.
You don't know where the walls are.
|
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.
|
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.
+ 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.
|
|
|
|
|
|
EPT![[image loading]](http://img26.imageshack.us/my.php?image=85936727.jpg)
