8
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.
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>>><
<<<<<
Starting from (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
<<<<<
Starting from (1, 1)
, a rather long path leads to (1, 3)
.
Replacing anything in the top row with ^
works too (thanks @Spitemaster).
Input
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.
Output
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.
Sample Cases
The sample cases are given as a character matrix and 1-indexed coordinates.
Case 1
Input
>>>>v
>>>><
<<<<<
1 1
1 3
Output
1
Explanation
See example.
Case 2
Input
<<<<<
v>v>v
>>>>>
1 1
5 3
Output
1
Explanation
You can either replace (1, 1)
with v
or (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.
Case 3
Input
^^^^^^
><<>>>
vvvvvv
2 2
5 2
Output
2
Explanation
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!
ex 2 will work changing any of the top row with either
^
orv
. – Jonathan Allan – 2019-06-15T19:40:15.173I suggest adding a test case or two requiring more than one change. – Jonathan Allan – 2019-06-15T19:42:47.140
3+1 to Jonathan's suggestion -- I think a problem like this deserves like 5-10 test cases, covering a variety of edge cases. – Jonah – 2019-06-15T19:43:46.697
what you have
><
does it ping pong back and forth (so that both positions are arrived at) or is it like there's a wall in between them? – Jonah – 2019-06-15T21:50:26.0801@Jonah It jumps between them (so yes, it hits both) – HyperNeutrino – 2019-06-15T23:51:49.703