Given a grid of directions and a start and end position, determine the minimum number of substitutions in the direction grid that needs to be made to complete the path between the two points. The grid is doubly-cylindrical. This is clearer given an example.
Let's take the following grid as an example:
>>>>v >>>>< <<<<<
Let's start at
(1, 1) and end at
(1, 3) (where the coordinates are
(x, y) or
(col, row), with the top row and left column being
1). Then, one possible solution is to replace the
(1, 1) and
(1, 2) with
v, so that the final grid looks like this:
v>>>v v>>>< <<<<<
(1, 1), the path would lead us to
(1, 3). However, a shorter solution exists, which is to replace
(5, 2) with
v, so the final grid is this:
>>>>v >>>>v <<<<<
(1, 1), a rather long path leads to
Replacing anything in the top row with
^ works too (thanks @Spitemaster).
The input will consist of a rectangular grid of 4 possible values, as well as two coordinates. You can take the grid in any reasonable format; for example, character or integer matrix, string list, etc. You can also request the dimensions of the grid. You can take the coordinates in any reasonable format; for example, integer pair, complex number, etc. You can choose 0- or 1-indexing.
The output should be a single integer, the minimal number of grid replacements necessary to close the path from the start to the end.
Rules and Specifications
- Standard Loopholes Apply
- the grid is doubly cylindrical, meaning that moving up from the top goes to the bottom, left from the left goes to the right, etc.
The sample cases are given as a character matrix and 1-indexed coordinates.
>>>>v >>>>< <<<<< 1 1 1 3
<<<<< v>v>v >>>>> 1 1 5 3
You can either replace
(1, 1) with
(2, 1) with
v. In the first case, starting from
(1, 1), the path goes straight down and then to the right to the destination. In the second case, the path loops off the left to the right, reaches
(2, 1), goes down, right, down, and then right until it hits the destination.
^^^^^^ ><<>>> vvvvvv 2 2 5 2
The best change is to make the center row wrap around the left to the point; that is, make the first and last items in the center row
<. Alternatively, make
2 2 and
3 2 both
This is a code-golf challenge, so the shortest code wins!