CODEWITHSUNDEEP
algorithmdynamic-programminggraph-algorithm
Suniti Jain
Suniti Jain

Reputation: 341

optimised cost to travel and collect units form factories

Problem statement there are 'n' factories, situated at arr[i]. The entry is at '0' and the exit id at 'exit-pos' . The moving time form one place to another is the distance between the two.

Each factory takes 'processing' time (same for all) to process. You have to start from '0' , exit from 'exit-pos' .

Also you have to produce 'n' units, each factory can produce 1 unit only. Along the path you need to visit each factory and give the order to produce. Then it will take ' processing' time to produce it. you can wait that time for the unit to produce and move ahead. Or you can visit other factories to give them order. latter you need to visit the factory again to pick the order.

Time taken to travel is the distance between the two places.

Question: You need to tell the minimum time taken to produce 'n' units and collect them also. Your journey starts at '0' and ends at a 'end-pos'.

Input:

number of units required to produce = number of factories = n
the location of factories in a array = arr
the exit position =  ext-pos
the processing time at each unit (it is same for each factory) = processing-time.

my approach I had this question during a test. Test is submitted but unfortunately no answers were given. During the test, I tried to used a recursive approach. It considered the 'items-collected', 'time', 'factory - position'. It failed. It got into a time loop.

Any suggestion/ question is there regarding question's clarity feel free to comment. Thanks

update: 0 < arrr[i] (factory time) < exiPos

Upvotes: 2

Views: 59

Answers (1)

Josef Wittmann
Josef Wittmann

Reputation: 1349

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:

Screenshot of the app

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.

  1. You can move left, only when there is a unfinished factory left of you.
  2. You can wait, only if you are at the leftmost unfinished factory.
  3. You can move right, only if you're moving into untouched territory or everything not right of you is finished.
  4. If you moved left last turn, continue moving only left as long as you can.
  5. If you moved left last turn and cannot move left anymore, you have to only wait.

Why does this work (references above list)?

  1. Moving left does not make any sense otherwise. Just don't.
  2. 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.
  3. 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.
  4. You chose to go back when turning around. Other options are explored by moving farther right before turning.
  5. 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

How to get to this solution

First I chose to visualize the solution and solve it by using Dijkstra's algorithm.

After inspecting the paths for various inputs, I noticed the pattern described in the "Strategy" solution: Going right, turning around and then completing this chunk of factories.

Possible Improvements

One could take the strategy and chunk the factories array.

Each chunk [a1, a2, ..., an] takes travelTime + waitTime = [3 * (an-a1)] + [min(0, processingTime - 2 * (an-a1))] time to finish.
And travelling between chunks [a1, ..., an] and [b1, ..., bm] takes b1 - an time.

Now one has to determine the chunks, which minimize the total time.

I had too much fun working this out.

And I can only recommend visualizing things.

One note to me: Think before you code. Just take a piece of paper and draw what you would do without a computer.

Upvotes: 1

Related Questions