I need help with understanding the following problem:

In a factory, machines are making cars (1-n) along the production line. One machine is making one part on the existing construction (part 1 is made by machine 1,...). Installation order of some parts is not important, but some parts have to be installed before others. Engineers have put together a dependence list for car parts as a table:

enter image description here

where the first column represents parts (1-8), and the second column represents preconditions for installment of each part. That is the list of parts (second column) whose installment must be done before the installment of current part (first column).

For each given list (second column), find the order of machines along the production line such that the manufacturing process of a car is done without interruptions, if such order exists. Also, find lists from the given table that give orders with interruptions.

Design an algorithm for this problem. Show the final order of machines along the production line, if it exists.

For each part (1-8, first column) we have to find a hash function without collisions that satisfies the second column in the table (if possible).

This is obviously the reversed process from generating hash table from given hash function.

I have found that the only possible order of machines along with production line, such that there is no interruption in the process is:


Question: How can we generate hash function from hash table?

  • $\begingroup$ Are you sure you need to solve it by generating a hash table? I don't understand your reasoning on this point. Plus, you can find a solution with oriented graphs instead. $\endgroup$ – Mariuslp Jan 15 '17 at 15:18
  • $\begingroup$ @Mariuslp, Could you show your idea with oriented graphs? $\endgroup$ – user300047 Jan 15 '17 at 15:27

The problem can be solved with oriented graphs, instead of hash functions.

For each part 1-8, create a node. Then, as part 1 relies on part 2, draw a oriented edge from 2 to 1. In your example, you obtain the following graph (edited following comment remarks):


Now, we want to know when, for a given list of preconditions, we can actually satisfy all of them. How does that translate in terms of oriented graphs?

Actually, it is easier to answer the following question: when is it impossible to meet the dependencies requirements? Again, how does it translate in terms of oriented graphs?

  • $\begingroup$ I think your answer would be easier to understand if you wrote the arrows the other way. $\endgroup$ – Ethan Bolker Jan 15 '17 at 16:27
  • $\begingroup$ Then, as @Ethan Bolker suggested, it would give a walk $4,2,1,3,8,7,6,5$ which is unique. Am I right? $\endgroup$ – user300047 Jan 15 '17 at 16:33
  • $\begingroup$ @Mariuslp Also, your graph doesn't have relations $3-7,3-8,1-8$. $\endgroup$ – user300047 Jan 15 '17 at 16:40
  • $\begingroup$ My bad, fixed the graph. I changed the directions, as suggested by @EthanBolker (but tbh I'm not sure it's easier to understand) $\endgroup$ – Mariuslp Jan 15 '17 at 16:49
  • $\begingroup$ @displayname: the solution does not relies on walks. Imagine you have an other part 9, depending on nothing, but on which 6 relies: there are no walks, but there is a solution to this new problem (for instance $4,2,1,3,8,7,9,6,5$). You should consider a trivial example in which there is no solution (1 relies on 2; 2 relies on 1), and look at the difference with the example graph. $\endgroup$ – Mariuslp Jan 15 '17 at 16:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.