Golf your finger-strokes in Flow Free: Warps

Question

Background

Flow Free is a series of puzzle games whose objective is to connect all the same-colored pairs of dots on the grid. Flow Free: Warps introduces the "warping" mechanic: a line connecting two dots can go through the border of the grid, which makes it re-enter through the opposite side of the grid (torus topology).

The following is an in-game screenshot of an initial grid and its complete solution, so that the readers can get some feel of the game.

Due to the warping nature, many of the lines should be drawn in multiple finger strokes. As in the screenshots, the game shows one-cell-wide extra border around the main grid whose cells act as "shadow" of the actual cells on the opposite side. The player can make any kind of moves on the shadow cells just like on the cells on the main grid.

The following shows the relationships between the shadow cells and their corresponding main cells on a 5x5 grid. Note that the shadow corner cells are also functional.

E5 | E1 E2 E3 E4 E5 | E1
---+----------------+---
A5 | A1 A2 A3 A4 A5 | A1
B5 | B1 B2 B3    B5 | B1
C5 | C1          C5 | C1
D5 | D1          D5 | D1
E5 | E1 E2 E3 E4 E5 | E1
---+----------------+---
A5 | A1 A2 A3 A4 A5 | A1

For example, the path B1 B2 B3 A3 E3 E4 E5 E1 can be drawn in one finger stroke by starting at main B1 and going >>^^>>>, finishing at the top right corner shadow E1.

Additionally, the game has a convenience feature: if you drop your finger at the cell (orthogonally) adjacent to the destination cell, the line is auto-connected with it. For example, if the destination of the above path is D1 instead, drawing the line through B1 to E1 is enough to complete the line, so the path still takes one finger stroke. But this feature only works between two cells adjacent when only the main cells are considered, e.g. dropping your finger at B5 (either main or shadow) won't auto-connect to B1.

Under these mechanisms, every single line shown in the above screenshot takes just one finger stroke. Note that you can start at either side of the line, and you can start or extend the line at any equivalent cell (out of the main and shadow cells).

To be precise, the player can do one of the following actions in one finger stroke:

• First stroke: Start drawing a line from one of the two dots, and draw it as far as possible, and release.
• Second and subsequent strokes: start drawing at the cell (or any of its shadows) where the last stroke stopped, and extend the line as far as possible, and release.

Challenge

Given the description of a line on a grid of Flow Free: Warps, determine how many finger strokes will be needed to complete the line.

The line can be taken as input in a suitable, clear format. If the input is B4 - B1 - B2 - A2 - D2 on a 4x4 grid, the following (and the respective equivalents according to Default I/O) are allowed:

• An ordered list of coordinates: [(2, 4), (2, 1), (2, 2), (1, 2), (4, 2)]
• A 2D grid where the path is marked with successive integers: [[0, 4, 0, 0], [2, 3, 0, 1], [0, 0, 0, 0], [0, 5, 0, 0]]

If you want to use a different input format, please ask in comments.

The line will always be valid in the following sense:

• It has a well-defined start cell and an end cell.
• Each adjacent pair of cells within the path are orthogonally adjacent on the grid, potentially through the border.

You can further assume the grid is rectangular and has at least 4 rows and 4 columns. The grid may be non-square.

You are not allowed to assume that the path does not touch itself. Many levels in the game contain some thin walls, which make some paths touch themselves by going through both sides of such walls.

Standard code-golf rules apply. The shortest code in bytes wins.

Test cases

Since a line on a grid can be represented in multiple different ways, the test cases are presented in a visually clear style.

Input:
[[ 1, 2, 3, 4 ],
 [ 8, 7, 6, 5 ],
 [ 0, 0, 0, 0 ],
 [ 0, 0, 0, 0 ]]
Output: 1

Input:
[[ 1, 2, 0, 0 ],
 [ 0, 0, 0, 0 ],
 [ 7, 8, 5, 6 ],
 [ 0, 3, 4, 0 ]]
Output: 1 (start at bottom shadow of 1 and release finger at shadow 7)

Input:
[[ 0, 0, 0, 0 ],
 [ 3, 4, 1, 2 ],
 [ 6, 5, 8, 7 ],
 [ 0, 0, 0, 0 ]]
Output: 2

Input:
[[ 0, 0, 0, 0 ],
 [ 3, 4, 1, 2 ],
 [ 6, 5, 0, 7 ],
 [ 0, 0, 0, 0 ]]
Output: 1 (start at shadow 7 and release finger at shadow 2)

Input:
[[ 7, 8, 9, 0, 0, 0 ],
 [ 0, 0, 0, 1, 2, 3 ],
 [ 5, 0, 0, 0, 0, 4 ],
 [ 6, 0, 0, 0, 0, 0 ]]
Output: 2 (first stroke can only go to 1..7 or 9..3)

Input:
[[ 0, 0, 4, 5,  0,  9 ],
 [ 0, 0, 0, 6,  7,  8 ],
 [ 0, 1, 0, 0,  0,  0 ],
 [ 0, 2, 3, 0, 11, 10 ]]
Output: 1 (start at shadow 11 and release at shadow 2)

Input:
[[ 0, 0, 5, 0, 9, 0,15, 0,19 ],
 [24,25, 6, 7, 8, 0,16,17,18 ],
 [23, 1, 0, 0, 0, 0, 0, 0, 0 ],
 [22, 2, 3, 0,11,12,13, 0,21 ],
 [ 0, 0, 4, 0,10, 0,14, 0,20 ]]
Output: 5

Answer 1

JavaScript (ES7), 194 bytes

Expects (list, width, height), where list is an ordered list of 0-indexed coordinates.

(p,w,h)=>(m=g=([c,...p],N,X=-3,Y=X)=>1/X/Y?c?[0,1,2,3].map(k=>g(p,(X-([x,y]=c,P=k&1?x?~x+w?g:-1:w:x))**2<2&(Y-(Q=k&2?y?~y+h?g:-1:h:y))**2<2|!(p+p||k)?N:-~N,P,Q)):N>m?0:m=N:0)(p)|g(p.reverse())|m

Try it online!

How?

As illustrated below, there are up to 4 distinct ways of selecting some cells in the grid: the original position P and 3 shadow positions S.

 . | . . . | .
---+-------+---
 . | P . . | S
 . | . . . | .
 . | . . . | .
---+-------+---
 . | S . . | S

The loop [0,1,2,3].map(k=>...) attempts to do one recursive call per possibility. However, if a given shadow is invalid, at least one of the coordinates will be set to a non-numeric value, causing the search to be aborted early thanks to the test 1/X/Y.

We keep track of the current number of strokes in N and the minimum number of strokes in m.

If the last position used is not a shadow, the corresponding stroke is never counted, even if it's not adjacent to the penultimate position. The test is |!(p+p||k).

Two searches are executed: from first to last point and from last to first point.