A hospital delivery robot gets its route from a planner as a list of grid cells (row, col), from the start to the goal. Each cell is a square cell metres wide, and the robot drives from the centre of one cell to the centre of the next. Consecutive cells in the list are always different and touch by a side or by a corner, so each step goes to one of the eight surrounding cells:
- a straight step (up, down, left or right) is
cellmetres long; - a diagonal step is \sqrt{2} times
cellmetres long.
Before accepting a route the nurses' station checks two things: how far the robot will drive, and how often it has to change direction (every change slows it down). A turn is a place where a step goes in a different direction from the step before it: from right to down-right counts as one turn, and so does doubling back.
Write path_corners(path, cell) that returns the tuple (length, turns): the length in metres and the number of turns. A path of a single cell has length 0.0 and no turns.
Examples
Input: path = [(2, 0), (2, 1), (2, 2), (1, 3), (0, 3)], cell = 0.5
Output: (2.2071067811865475, 2)
Explanation: right, right, up-right, up. Three straight steps of 0.5 m and one
diagonal of 0.7071 m; the direction changes at (2, 2) and at (1, 3).
Input: path = [(4, 4)], cell = 1.0
Output: (0.0, 0)
Input: path = [(1, 1), (1, 2), (1, 1)], cell = 0.25
Output: (0.5, 1)
Explanation: right, then back left: one turn.
Constraints
- floats are compared with a tolerance of
1e-6
Goals
- Measure a cell path in metres, with diagonal steps $\sqrt{2}$ cells long
- Count the places where a path changes direction