Seed Drill Robot
MediumOnline Assessment
Simulate a seeding robot that sweeps a field row by row, and report how many seeds it plants, how many times it refills, and how far it drives.
The field is a grid of rows. Each cell is . (normal soil, takes 1 seed), ~ (loose sand, takes 2 seeds) or # (a rock: nothing can be planted, but the robot can drive over it). The robot starts at the top-left cell (0, 0) facing east with its hopper full (capacity seeds), and the depot is at (0, 0).
It visits every cell exactly once in a snake path: row 0 left to right, then it steps down into the last cell of row 1 and goes right to left, then steps down into the first cell of row 2, and so on. Each step to the next cell in this path, including the step down at the end of a row, is 1 unit of distance.
At each cell in the path, in order, the robot:
- does nothing if the cell is one of the cells being skipped (see step 3) or if it is a rock;
- otherwise plants the cell: it needs 1 seed (
.) or 2 seeds (~). If the hopper holds fewer seeds than needed, it first drives straight to the depot and back to this cell, which costs2 * (row + column)distance, and fills the hopper tocapacity, then plants. It never refills unless it needs a seed it does not have; - after planting, the robot skips the next
gapcells of the path (not planting there, whether they are soil or rock), then resumes.
After the last cell, the robot drives from where it stopped back to the depot, which costs row + column of that last cell.
Input: field (a list of strings), gap and capacity.
Output: [seeds, refills, distance]: the total seeds planted, the number of refill trips, and the total distance driven (sweep steps, refill trips, and the final return).
Example 1
- Input:
- [["..~.","#..~"],1,3]
- Output:
- [6,1,16]
- Explanation
- Path: (0,0)
.plants 1 seed (hopper 2) and skips (0,1); (0,2)~needs 2 and the hopper has exactly 2, so it plants (hopper 0) and skips (0,3). Next is (1,3)~: the hopper is empty, so the robot drives to the depot and back, 2 * (1 + 3) = 8, refills to 3 and plants 2 (hopper 1), skipping (1,2). (1,1).plants 1 seed (hopper 0) and skips (1,0). Seeds 1 + 2 + 2 + 1 = 6, 1 refill. Distance: 7 steps + 8 + 1 for the return from (1,0) = 16.
Example 2
- Input:
- [["~~.","..#","~.."],0,3]
- Output:
- [11,4,30]
- Explanation
- With
gap = 0the robot plants every non-rock cell. The hopper (3) runs short at (0,1) (needs 2, has 1): refill, cost 2 * 1 = 2. Further refills happen at (1,1) (cost 4), at (2,0) where it has 1 seed but needs 2 (cost 4), and at (2,2) (cost 8). The rock at (1,2) takes no seed. Seeds: 2+2+1+1+1+2+1+1 = 11, 4 refills. Distance: 8 steps + 18 for the refills + 4 for the return from (2,2) = 30.
Example 3
- Input:
- [["#.#.~","~..#."],2,3]
- Output:
- [4,1,16]
- Explanation
- The rock at (0,0) is skipped and does not start a cooldown. (0,1) plants 1 seed, then (0,2) and (0,3) are skipped. (0,4)
~plants 2 seeds (hopper 0), and the 2 skipped cells run across the row turn: (1,4) and (1,3). At (1,2) the hopper is empty, so it refills at a cost of 2 * (1 + 2) = 6 and plants 1 seed. (1,1) and (1,0) are skipped. Seeds 4, 1 refill, distance 9 + 6 + 1 = 16.
Constraints
- 1 ≤ field.length ≤ 20; all rows have the same length, 1 to 20; cells are
.,~or# - 0 ≤ gap ≤ 10; 2 ≤ capacity ≤ 30