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
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
It appears the testing set might not be stringent enough. There doesn't seem to be any tests that have a non-unique solution. I had commented out the part of my code meant to deal with this to help me get the dimensions correct for concatenating, but turns out it solved the problem!
Thanks to Alfonso for mentioning the graph function! That made solving this problem possible for me.
and this?