Solve it by using a strategy with A* search
I've uploaded the solution to a GitHub repo.
You can see a live demo here.
Here are the contents of the README with a screenshot:
Solution summary
Since 0 < arr[i] < exit-pos
, we always start at the first factory and finish at the last. It's trivial to add the remaining time.
The solution includes three different algorithms, which can be selected via a drop-down:
1. Dijkstra's algorithm (worst)
Explores all states and finds the minimum time to a final state:
- A state consists of the current position and the state of all factories (How long until product is done? Was it picked up?).
- From each state either wait until production is finished, move left (towards start) or right (towards exit).
- Obviously uses Dijkstra's algorithm.
2. A* search algorithm
The A* algorithm is basically the same as Dijkstra's algorithm, but uses a heuristic to favor more promising nodes.
The heuristic used calculates the minimum travel distance without waiting. It computes the time to the leftmost unfinished factory and from there to the exit.
The improvement is significant (even for small inputs).
3. Specialized A* (best)
This version uses the same search as the previous, but restricts new states being explored:
It follows the strategy to finish everything left of you once you turn from going right to going left. And waiting is only allowed at leftmost unfinished factory.
- You can move left, only when there is a unfinished factory left of you.
- You can wait, only if you are at the leftmost unfinished factory.
- You can move right, only if you're moving into untouched territory or everything not right of you is finished.
- If you moved left last turn, continue moving only left as long as you can.
- If you moved left last turn and cannot move left anymore, you have to only wait.
Why does this work (references above list)?
- Moving left does not make any sense otherwise. Just don't.
- You'll have to come back to the leftmost unfinshed factory anyways. On the way back right you'll cross all factories to the right. So we choose to wait only at the very left, because waiting elsewhere can be transformed to waiting here.
- Moving back right into touched territory won't be faster, since you have to come back to the very left (see 2.). Either go farther right initially, but only turn back right when you're done on your left.
- You chose to go back when turning around. Other options are explored by moving farther right before turning.
- Same as 4.
Performance
These are rough timings for this input:
n = 14
arr = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43]
processingTime = 15
Algorithm |
Time |
Dijkstra |
~ 3000 ms |
A* |
~ 100 ms |
Strategy |
~ 10 ms |
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…