Find the minimum number of lane changes necessary to cross the entire track without running into any obstacles
A track is represented by a 5xN board (with 5 lanes and N squares in each lane). Some of the squares are blocked and the runner cannot pass through them (red blocks in the image above). The runner may only move forward or laterally (i.e. advancing or switching lanes), and cannot run into or jump over any obstacles. Diagonal or backward moves through the board are also not allowed. The runner may start and finish in any arbitrary lane of his choosing. Your job is to determine, given the track, the minimum number of lane changes necessary to finish the race.
The input matrix will be a 5xN matrix with 1's representing blocked squares and 0's representing available/free squares. The output of your function should be a number indicating the minimum number of lane changes necessary to finish the race. For example, the track shown in the picture above would be represented as:
x = [0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0];
and your function
n = fivelanes(x);
should return n=2, since there are multiple paths available (e.g. yellow line in the picture above) that would allow the runner to reach the end of the track with only 2 lane changes, but none that would allow the runner to complete the track with only one or less lane changes.
Good luck!
Small print: You may assume that there will always be a direct path between the start and finish requiring only forward- and lateral- movements. The testsuite does not include cases where there are no possible paths of this form. Lane changes are counted identically irrespective of whether they involve adjacent or non-adjacent lanes (i.e. switching from lane 1 to lane 4 counts as one lane-change, just the same as switching from lane 1 to lane 2). When switching lanes the runner may not run over obstacles (i.e. switching from lane 1 to lane 3 is not possible if there is an obstacle in lane 2 at that point in the track). Below a few examples of tracks and possible minimal-lane-changes paths (note: optimal paths are not unique; in all of these examples the optimal number of lane-changes is, coincidentally, 5)
why can't I use bwlabel from the imaging toolbox?
this one took a while to solve lol
Very proud of my solution.
Great problem!
@Daniel, this cheat does not work because user directories are effectively random (hint: you may simply use relative paths instead). In any way, this form of cheats/hacks are not welcome in this particular Cody problem. There are, nevertheless, plenty of hacking problems in Cody (e.g. https://www.mathworks.com/matlabcentral/cody/problems?term=tag%3Ahack) that welcome and even encourage this sort of explorations, so please use those venues instead if you are interested.
Somehow, this test suite has changed and now I cannot pass Test 62, even though I did not use a lookup table solution. Please advise.
The solution is timing out (it is just taking too long). I would recommend to change your code to use a single call to dijkstra_lanes instead of one separate call for each StartLane-to-EndLane combination. You may do so, for example, by adding two nodes to your graph, one "start" node that is connected (with distance 0) to every non-blocked lane in the first row, and one "end" node that is connected (with distance 0) to every non-blocked lane in the last row. Then you will only need to call dijkstra_lane once to compute the optimal path distance of this extended graph, instead of calling your function N1*N2 times (for each of the N1/N2 first/last -row non-blocked positions)
Thank you for the recommendation.
added a few more test cases to discourage look-up table solutions (by I liked your bin2dec idea to encode the board, I copied that in my testsuite now :)
added a few test cases to discourage this sort of solutions
sorry, Cody web interface has some issues with very long solution files (solutions cannot be viewed, html parsing is misinterpreted so other solutions listed below this one cannot be displayed, etc.), could you please resubmit a shorter file? I will then simply rescore this solution to force it to be cropped (which will also fix the formatting issues)
2405 Solvers
195 Solvers
424 Solvers
Find last zero for each column
135 Solvers
1249 Solvers