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