Problem 44378. Five-dimensional maze
Description
The traditional maze is 2-dimensional: the navigator can move in the positive or negative directions along two axes x and y. Now imagine, if you will, a 5-dimensional maze. As in the 2-dimensional case, the navigator may only move along one of these directions at any time, and some of the directions are blocked by walls. Your task is to find and give the shortest path through the given maze.
This problem is a generalization of Problem 283. If you haven't solved that yet, I would recommend solving it first.
Encoding
- The maze will be represented by an [ M x N x O x P x Q ] matrix.
- Each element of the matrix represents a valid location in the maze and the value of each element is a binary-coded representation of the walls, positive directions in which you can not move. If a value reads 0, it means the navigator is permitted to move along any of the five dimensions in the positive direction.
- Walls are bi-directional: if a wall exists between two locations, you cannot traverse it in either direction. A skilled navigator must check the destination location's walls if she wishes to move in the negative direction along any dimension.
- The start position is at the origin: subscript (1,1,1,1,1).
- The end position is at the furthest extent: subscript (M,N,O,P,Q).
- The output should be a matrix of the same size as the input matrix that lists the steps you need to go through to traverse the maze with the remaining squares being 0. Refer to Problem 283 for a 2-D example.
- You are NOT guaranteed that there will be only one shortest path for the test cases. If there exist multiple shortest paths, you must represent them all. It can easily be shown that the superposition of two shortest paths will never lead to a multi-valued element in the output matrix.
Solution Stats
Problem Comments
-
16 Comments
Can you please further explain the coding of the walls? I have already solved the 2D problem, but I still don't get the wall encoding in 5D. The end position is always encoded as 31, but wouldn't 31 mean the end position has walls in all dimensions, thus making inaccessible?.
for a given location on the square the bits encode only the walls in the *positive* direction of each axis. For example, for a 2d maze the bits encode the presence of a wall wall in the "down" and "right" directions, respectively (but the ability to move "up" or "left" is determined by the presence of walls in the corresponding neighboring squares). In the 5d maze, a value of 31 means that you cannot move in the positive direction further in any dimension (i.e. this is a corner, but you may of course move in the negative direction in some dimensions, depending on the values of the neighboring squares)
Thank you for answering, Alfonso.
For i.e. test case 5, maze(10) = 01111 and should be a bottom wall of the first page of the maze. If its a bottom wall, shouldn't that mean that the first digit should be 1 instead of zero, since I shouldn't be able to step outside the maze? In the 2d Cody problem of yours, this is implicit, is that not the case here or am I botching the binary encoding.
@Peter the first binary digit refers to the least significant one, so all "bottom" squares (last along the first dimension) would have odd numbers in an enclosed board
@Alfonso. Thanks for the hint, that got me toward a working solution. This one was a lot easier in non-Cody environment with py.networkx library running in MATLAB.
@Peter. the new 'graph' class (since 2016a I believe) is also quite handy (see solution 1293329 and 'help graph' for more details)
@Bryant perhaps isequal(solve_maze5([0 2;1 3]),[1 2;2 3]) (no big deal, but I believe currently there is no non-unique shortest-path test case)
@Bryant, on second thought perhaps it would be nicer of us to wait until after the Cody5 deadline to implement the change to the testsuite suggested in my previous comment, if at all? (there is a relevant ongoing discussion in the 'Tautology' problem 44374 regarding the pros and cons of modifications to the testsuite, particularly for problems in the Cody5 groups; it is unclear whether some consensus will be reached but I thought I'd mention in case you were not aware of that)
I still don't quite understand the coding of the walls. In the first test case, you can only move in the fifth dimension. However, the binary coding of all the positions except the last was 15 ('01111'), which, to my understanding, forbids movement in all directions except for the first dimension. Therefore you will always be trapped in the initial position, because the only dimension (i.e. the fifth) is forbidden. Please tell me where I got wrong, thanks!!!
@Alfonso Nieto-Castanon
@Ziheng, you are interpreting the order of the dimensions in reverse. In general, if the wall encoding is x, then bitget(x,n) will be 1 if there is a wall along the n-th dimension/direction. The x=15 (#01111) encoding means that the fifth dimension is open (bitget(15,5)==0), while the first to fourth dimensions are closed (bitget(15,1:4)==[1 1 1 1]) , so you are allowed to travel along the length of this tube.
@Alfonso Nieto-Castanon Thanks for the explanation! That makes sense to me.
can you add an anti-cheater test case, eg the currently leading solution is a non-solution: https://www.mathworks.com/matlabcentral/cody/problems/44378-five-dimensional-maze/solutions/1391295
Dijkstra is our friend.
Pretty confusing the fact that in the 'easy' version of this problem the walls associated to horizontal and vertical dimension are swapped.
"01" -> wall placed in dimension-1 is drawn as vertical wall, which allows to step up and down: (dimension 1), whereas it should be an horizontal wall, no?)
Luckily on this problem the '1' placed in the Nth place blocks the way on that dimension accordingly.
Solution Comments
Show commentsProblem Recent Solvers44
Suggested Problems
-
5677 Solvers
-
Back to basics 8 - Matrix Diagonals
925 Solvers
-
485 Solvers
-
Right Triangle Side Lengths (Inspired by Project Euler Problem 39)
1830 Solvers
-
Calculate the Number of Sign Changes in a Row Vector (No Element Is Zero)
731 Solvers
More from this Author56
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!