EPT[Math Puzzle] Day13 - Page 3
| Blogs > evanthebouncy! |
|
Cambium
United States16368 Posts
| ||
|
DeathSpank
United States1029 Posts
On June 08 2009 18:57 Cambium wrote: To those of you who gave generic CS solutions (be it greedy, breadth-depth search, etc.), it doesn't work because you don't know the "exit condition" because the robot doesn't know when it has hit a wall and could not move further. Your program will most likely result in an infinite loop. well then its going to do that anyways. I'm sure I could do the math to figure out the limit I need for my solution but I really am to lazy. Programmers are lazy dudes. No one would ever program anything without an exit condition. Even if you found a correct solution you would never know when you hit the exit. So you would keep going and going. The robot can't know where it is. I therefor assume that the robot will exit automatically when I have reached my destination. | ||
|
Ivs
Australia139 Posts
I'll have a go at this. Result 1: Given any two start position in a fixed maze and two robots on one each, there exists a finite instruction such that, when executed simultaneously by the two robots (and no collision between the robots, so they are like probes on mining mode), they will eventually stack. Assume the contrary. Find two starting positions with the minimal shortest path (ie, for each pair calculate the shorest path, then find the pair with the minimal value) such that the above fails. Call the two squares A and B and put robots there. Say the Euclidean (ie, measure with ruler distance) distance between them currently be say, d. Now let the robot at A move towards B using the shortest path and let the other robot replicate the moves. The shortest path between robots does not increase during this whole time since one robot is reducing it. The shortest path also does not decrease by our minimal assumption. When the first robot gets up to position B, let the other be at position C. Now the path looks just like the original, because as one robot was "erasing" the path, the other one was "tracing" an identical one. Hence the Vector BC = Vector AB. And C is now 2d distance away from A. We can continue this process and yield points D, E, F etc which gets further away from A by d each time. This is a contradiction since our maze is finite. Result 2: Given a fixed maze and a robot on each square of the maze, there exists a finite instruction such that, when executed simultaneously by all robots, they will all stack. This follows directly from Result 1. We just pick out any two separated robots, use Result 1 to stack them. Since once stacked they don't unstack, we can just pretend they are one robot. Repeat until all robots are stacked. For a particular maze, define the sequence of moves found in Result 2 the "imba sequence" Now after performing the "imba sequence", say the stacked robots are on a square S (which only depends on the "imba sequence" and not the start points). For any other square T, we can just now 1a2a3a our stacked robots there. Call this sequence of moves "attack-T sequence". Final Result: Define our algorithm as follows: List out all possible strings made up of U,D,L,R of length k, for all k. Concatenate them all together (so list all the possible strings of length 1, then 2, then 3 etc). It's clear that this big string has countable length. We'll prove that this algorithm satisfies the problem. For any square T on the maze, combine our "imba sequence" with our "attack-T sequence", call it "bisu sequence" or something. Clearly the sequence is finite, so it appears in our algorithm somewhere. Consider performing the algorithm up to the start of "bisu sequence". Now no matter where the robot is, the "bisu sequence" will bring it to square T. And since this works for any T, no matter where the end of the maze is, as long as it's finite, the robot will get there in finite number of moves. Hopefully it is correct :-). Edit: Just read Muirhead's, It's much shorter/nicer :-). At least this is different and has a few additional results. | ||
|
ven
Germany332 Posts
Start with a length of 1. Follow every possible sequence with that length. Increase length by 1. Repeat. Example: U, R, D, L, (length+1), UU UR UD UL, (length+1), UUU, UUR, UUD, UUL, URU, URR, URD, URL, UDU, UDR, UDD, UDL, ULU, ULR, ULD, ULL, (length+1), etc.. This way we'll create every possible path through the maze. It doesn't matter that we change positions between the tries because for every position there is a solution and as soon as our path is long enough we will eventually find the exit path that matches our current position. This would be easier if we had knowledge about the maze size because we could just always use the longest possible path for our length but since we don't have that we increase our path length until we reach the one that we need. | ||
|
WhenHellfreezes
United States81 Posts
On June 08 2009 23:49 ven_ wrote: Start with a length of 1. Follow every possible sequence with that length. Increase length by 1. Repeat. Example: U, R, D, L, (length+1), UU UR UD UL, (length+1), UUU, UUR, UUD, UUL, URU, URR, URD, URL, UDU, UDR, UDD, UDL, ULU, ULR, ULD, ULL, (length+1), etc.. This way we'll create every possible path through the maze. It doesn't matter that we change positions between the tries because for every position there is a solution and as soon as our path is long enough we will eventually find the exit path that matches our current position. This would be easier if we had knowledge about the maze size because we could just always use the longest possible path for our length but since we don't have that we increase our path length until we reach the one that we need. There is a problem with your assumptions. That it doesn't matter that we change positions is incorrect for example consider the length of three. It is possible that after doing UUU, UUR, UUD, that you moved to a spot such that UUU is the correct way to exit but you won't do that sequence again since you already did it in your rotation. The way to fix that would be to have every permutation of sequences for each length. Thus for every length i you would have (4^i)! sequences of lengths i. The total sum of moves in this sequence passes 1 mil within just like 5-6 lengths. Therefore a random algorithm would be loads better. I seriously don't understand why you are disallowing that. | ||
|
ven
Germany332 Posts
| ||
|
WhenHellfreezes
United States81 Posts
You have every possible sequence of moves of length 3 as per what you said. But what I'm saying is that there are 4^3 such sequences and that you need to have every such possible arrangment of those sequences in order to fix the problem of not knowing where you are. You need to write every permutation of these 4^3 sequences or (4^3)! sequences of length 3. I'm saying that you stop at 4^3 and you need (4^3)!. | ||
|
ven
Germany332 Posts
| ||
|
WhenHellfreezes
United States81 Posts
| ||
|
moriya
United States54 Posts
I thought the original question is to ask a gernal solution for every possible box. For example, in 1D case the solution is UDDUUUDDDDUUUUU...How to prove that there is no such a sequence for 2D case? | ||
|
Muirhead
United States557 Posts
I provide a single sequence which solves every possible maze. All solutions posted are either like mine and Ivs's, grossly inefficient but nicely deterministic, or they are based on randomness. The random solutions are in many senses nicer but are "only" guaranteed to succeed with probability 1. Which you prefer depends on whether you want to be a practical computer scientists or an AWESOME MATHEMATICIAN ^^. Though to be honest, I don't know enough (any) comp sci. Could someone summarize how fast my algorithm runs compared to a random algorithm? | ||
|
ven
Germany332 Posts
But even then, any algorithm to solve a maze of this kind would be so horribly inefficient and slow that it doesn't make sense to compare their runtime. | ||
|
Muirhead
United States557 Posts
 | ||
|
Ivs
Australia139 Posts
On June 08 2009 23:49 ven_ wrote: + Show Spoiler + This way we'll create every possible path through the maze. It doesn't matter that we change positions between the tries because for every position there is a solution and as soon as our path is long enough we will eventually find the exit path that matches our current position. Every possible path does occur, but you haven't shown that upon the positional change, the right path will follow. For example, considers two squares A and B, let the classes of sequences that finish the maze be c(A) and c(B). Each member c(A) and c(B) does occur infinitely often, but you could have say, each element of c(B) only follows position A and each of c(A) only follows position B. To complete it you would need to show that the sets c(A) and c(B) have common elements, which they in fact do. | ||
|
Daveed
United States236 Posts
I know that this problem doesn't specify it, but generally, robots should be constrained by processing ability and memory. Keeping an enumeration of 2^{m*n} possible mazes should be out of the question. As a math solution, this would work, but I don't think the quantifiers of the problem were set up as well as they could have been. That being said, I believe some variant of bugnav should do the trick. | ||
|
Muirhead
United States557 Posts
| ||
|
mmp
United States2130 Posts
On June 08 2009 14:44 Muirhead wrote: + 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. Interesting that you can try exhaustively on all mazes without worrying where the previous maze left your robit, since you are guessing from an unknown starting location. Counter intuitive, but cool once you think about it. Worst-case runtime: + Show Spoiler + Let B be the enumeration of possible mazes. This isn't exactly 2 ^ (m x n), since any open square must lead to an exit, but it is O(2 ^ (m x n)). To prove this, consider all mazes that do not have a solution path and are therefore invalid. Now make every other row entire open. All previously-invalid open squares are now adjacent to a solution row, while preserving (m x n) / 2 of the cells. For every board there are O(m x n) starting positions to try. Since you know which board you are currently trying, there exists a known solution path of length O(m x n). So we immediately know that it will require O(B x m^2 x n^2) moves. I'll work on non-deterministic runtime and expected runtime in a bit. | ||
|
King K. Rool
Canada4408 Posts
Solutions to this (assuming maze is given) seem inefficient like ven_ said. Assuming we follow an algorithm like muirhead's (can't really think of another solution, his is pretty cool) Worst case the last box you check would be the correct box. Obvious upper bound for boxes are O(m^2 * n^2). Number of boxes to check would be O(m^2 * n^2). Of course you likely could math it down to a better upper bound. Something similar to ... loop1 : i = 1.. m^2 * n^2 //ith box you check loop2: j = 1 .. i //follow 1..ith path m^2*n^2 instructions //follow the path Not sure if my math is right (not going to bother thinking too much, at work), but you get something like an arithmetic series 1+2+3+...+k, where k is m^2 * n^2. We know that the 1+2+...k is O(k^2), so you get O(m^4 n^4), but then this is assuming one instruction. We have at most m^2n^2 instructions so you get m^6n^6. O(m^6n^6) + finding paths for all boxes (which seems like it'll be easier to do). | ||
|
mmp
United States2130 Posts
On June 10 2009 02:32 Daveed wrote: @ Muirhead: I know that this problem doesn't specify it, but generally, robots should be constrained by processing ability and memory. Keeping an enumeration of 2^{m*n} possible mazes should be out of the question. As a math solution, this would work, but I don't think the quantifiers of the problem were set up as well as they could have been. That being said, I believe some variant of bugnav should do the trick. Most bug pathfinders are based on some limited information about the map. Our robit cannot detect collisions (or anything for that matter), so wall-crawling, tangent bug, etc. are simply out of the question. Because we have no information, the problem lends itself to non-heuristic approach. As for memory constraints, you require (m x n) bits to store any one maze. Generating another is simply a matter of incrementing bits until you have exhausted all permutations. For any given maze, I believe that you can construct a spanning tree of the adjacency matrix in O(m x n) time. You can search the tree for a solution (not necessarily the shortest) from any starting location in just as much time (linear). Computationally, 2 ^ (m x n) is bad, but you really cannot avoid this part of the problem. At best, you can do a depth-first approach and compute massively in parallel. | ||
|
Daveed
United States236 Posts
Although it needs to keep only one maze in its head at a time, it also needs to know which maze it's on, in order to generate the next maze in its enumeration (that IS what you are doing, correct?). @ mmp: I had overlooked the inability of the robot to detect where it was. Sure, point taken. | ||
| ||
