Reroute the Path

Question

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!

Answer 1

JavaScript (ES6),  140  135 bytes

Takes input as (a, width, height, x1, y1)(x0, y0) where a[] is a matrix of integers and all coordinates are 0-indexed.

Directions: \$-2\$ for left, \$-1\$ for up, \$0\$ for right and \$1\$ for down.

(a,w,h,X,Y)=>m=g=(x,y,n=0,r=a[y%=h],v=r[x%=w])=>x-X|y-Y?[-1,0,1,2].map(d=>r[v<2&&g(x+w+d%(r[x]=2),y+h+--d%2,n+(v!=d)),x]=v)|m:m=m<n?m:n

Try it online!

How?

We use a breadth-first search to try all possible paths from \$(x,y)\$ to \$(X,Y)\$ without visiting twice the same cell.

We keep track of the number of times \$n\$ where the direction that was chosen did not match the direction stored in the input matrix.

We eventually return \$m\$, which is defined as the minimum value of \$n\$.

Answer 2

Jelly, 73 72 bytes

W,0+Ɱ⁴PṬ€×Ɱ3¤Ẏ¤,€ɗ/€Ẏ$‘ƭ€ịØ.,N;U$¤;ɗ/0ị+æ.Ɱ⁴‘Ṫịʋ¥Ɗ%⁴ṭƲ⁴P¤¡ŒHṪe¥/Ʋ€Ẹ¬Ɗ/¿Ṫ

Try it online!

Example using case 3 that requires two changes (also has a footer to translate the ><v^ into numbers).

A full program that expects the following arguments:

• Left: a list of two lists; first the flattened direction grid encoded as 1=right, 2=left, 3=down, 4=up, followed by a list of the end position and start position as zero-indexes [row, column]. For first example, [1,1,1,1,3,1,1,1,1,4,2,2,2,2,2],[[2,0],[0,0]].

• Right: a list of the number of rows followed by columns. For first example [3,5]

Returns the number of changes required to get from start to end. Slow once this is more than one change. On TIO the third example case takes approx. 30 seconds to complete.

Full explanation below, but overview is:

1. Initialise a counter to zero.
2. Work out positions after each of \$\mathit{row} × \mathit{column}\$ moves.
3. Check if the end position is included:
   • If false, increment a counter and create \$3 × \mathit{row} × \mathit{column}\$ new versions of the grid, each with a single grid position changed to one of the three possible alternative moves. Then go back to step 2.
   • If true, terminate and output the counter

Full explanation:

W,0 | Wrap input in a list, and then pair with 0 (thus initialising the counter)


                                           Ɗ/¿ | While the following is true for the first item of the input pair (i.e. the list of all grids to be tested, paired with the end and start grid positions):
                                       Ʋ€      | - For each member of the list:
          ɗ/                                   |   - Reduce using the following as a dyad (so left argument is flattened grid and right is end/start positions)
ị       ¤                                      |     - Index into the following as a nilad
 Ø.                                            |       - [0, 1]
   ,N                                          |       - Pair with negative [[0, 1], [0, -1]]
     ;U$                                       |       - Concatenate to upended version of this [[0, 1], [0, -1], [1, 0], [-1, 0]]
         ;                                     |     - Concatenate (to end/start positions)
                            Ʋ⁴P¤¡              |   - Repeat the following links the number of times indicated by the product of the grid dimensions:
                        Ɗ                      |     - Following as a monad:
            0ị                                 |       - Last item (current grid position)
              +        ¥                       |       - Add to the following as a dyad:
               æ.Ɱ⁴                            |         - Dot product of current position with each of grid dimensions
                   ‘                           |         - Increase by 1
                    Ṫ                          |         - Tail (which is current position in flattened grid)
                     ị                         |         - index into flattened grid
                         %⁴                    |        - Mod grid dimensions
                           ṭ                   |        - Tack onto end of current grid/position list
                                 ŒH            |   - Split into halves (first half will be flattened grid and desired end position, second half will be all positions reached after moving through grid)
                                     ¥/        |   - Following as a dyad, with the first half from above step as left argument and the second half as right
                                   Ṫ           |     - Tail (i.e. the desired end position)
                                    e          |     - Exists within (the list of all positions reached)
                                         Ẹ¬    | - Not true for any of the input grids


                    ƭ€ | For each of the pair (list of grids, counter), do one of the following:
                  $    | - For the list of grids, do the following as a monad:
              ɗ/€      |   - Do the following as a dyad, with the flattened grid as the left argument and end/start positions as the right:
+Ɱ                     |     - Add to the flattened grid list each of:
           ¤           |       - The following as a nilad
         ¤             |         - The following as a nilad:
  ⁴P                   |           - The product of the grid dimensions
    Ṭ€                 |           - Convert each (using an implicit range from 1 to the grid dimension product) to a boolean list with a 1 at the relevant position (i.e. [[1], [0, 1], [0, 0, 1]...])
      ×Ɱ3              |           - Multiply by each of 1..3
          Ẏ            |        - Flatten to a single list of lists
            ,€         |    - Pair each with the end/start positions
                 Ẏ     |   - Tighten to a single list of grids paired with end/start positions
                   ‘   | - For the counter increment it


Ṫ | Finally, take the tail (which is the final value of the counter)