[Math Puzzle] Day13

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.