Trail GPS stops
MediumOnline Assessment
Summarise a hiking tracker's GPS log: how far the hiker really moved, and when they stopped.
The log is a list of fixes [t, x, y]: a time in seconds and a position on a metre grid. Distance between two fixes is the grid distance |x1 - x2| + |y1 - y2|. Fixes are listed in recording order.
Step 1, drop glitches. The first fix is always accepted. Each later fix is compared with the last accepted fix: it is accepted only if t is strictly greater than that fix's t and distance <= max_speed * (t - last_t). Otherwise it is discarded and plays no further part.
Step 2, find stops. Walk the accepted fixes in order with an anchor fix. Take all following fixes whose distance from the anchor is at most radius, stopping at the first one that is farther. If at least one fix was taken and the last taken fix is at least min_stop seconds after the anchor, the anchor and the fixes taken form a stop, and the next anchor is the first fix after the stop. Otherwise the next anchor is simply the next fix after the current anchor. A fix belongs to at most one stop.
Step 3, measure. Moving distance is the sum of grid distances between consecutive accepted fixes, except for pairs where both fixes belong to the same stop.
Input: fixes, a list of [t, x, y]; and the integers radius, min_stop and max_speed.
Output: [moving_distance, stop_count, stopped_seconds], where stopped_seconds is the sum over stops of (last fix time minus anchor time). With no fixes, return [0, 0, 0].
Example 1
- Input:
- [[[0,0,0],[10,1,1],[20,0,2],[30,6,0],[40,306,0],[50,26,0],[60,30,0]],2,15,3]
- Output:
- [32,1,20]
- Explanation
- The fix at t=40 is 300 m from the previous one after 10 s, which needs 30 m/s against a limit of 3, so it is dropped. The accepted fixes are t=0, 10, 20, 30, 50, 60. The anchor at t=0 takes t=10 and t=20 (both within 2 m); t=30 is 6 m away and ends the run. The span is 20 s, at least min_stop, so that is a stop (stopped_seconds 20). Anchors at t=30 and t=50 find nothing close. Moving distance counts 20->30 (8), 30->50 (20) and 50->60 (4) but not the two pairs inside the stop: 32.
Example 2
- Input:
- [[[0,0,0],[10,1,0],[20,2,0],[30,2,1],[40,2,0],[50,2,1],[60,2,2],[70,40,40]],2,30,20]
- Output:
- [78,1,40]
- Explanation
- The anchor at t=0 takes t=10 and t=20 but t=30 is 3 m away; the span of 20 s is below min_stop 30, so there is no stop and the anchor simply moves to t=10. From t=10 the fixes at t=20, 30, 40, 50 are all within 2 m and t=60 is 3 m away, so the stop covers t=10 to t=50: 40 s. Moving distance is 0->10 (1), then 50->60 (1), then 60->70 (76), skipping the pairs inside the stop: 78.
Example 3
- Input:
- [[[100,0,0],[100,1,1],[105,8,0],[105,8,0],[110,9,0]],3,1000,2]
- Output:
- [9,0,0]
- Explanation
- The second fix at t=100 is 2 m away in 0 s, so it is dropped. The fix at t=105 is 8 m in 5 s, within the limit of 2 m/s, so it is accepted. The repeated t=105 fix is not strictly later than the last accepted fix, so it is dropped. The fix at t=110 is 1 m away and accepted. min_stop is 1000 s, so there are no stops and moving distance is 8 + 1 = 9.
Constraints
0 <= fixes.length <= 2000 <= t <= 10^6(not necessarily increasing in the log),-10^6 <= x, y <= 10^60 <= radius <= 100,1 <= min_stop <= 10^4,1 <= max_speed <= 100