1
\$\begingroup\$

Not sure if this is the correct community to post this is. But as I see this problem as an interesting puzzle to solve, I'd thought to give it a shot...

Problem Statement:

Let`s say we have:

  • N collections of parts: A, B,C,D,...etc
  • Each collection consists of n parts: 1,2,3,4,5 ...
  • All these parts are randomly present in an input buffer:

B1, C5, D2,A4,A2, etc

The aim now is to sort all parts into their collections, and make sure that in each collection the parts are ordered correctly.

A desired output would be: A1,A2,A3,A4,A5 B1,B2,B3,B4,B5, ..etc

This will be a physical process in which the parts are sheets of material. This gives some real world constraints:

  1. A sorting and output buffer of Nb locations is available.
  2. On each of the buffer locations multiple sheets can be stacked.
  3. To retrieve one particular sheet, all sheets that are placed on top of it need to be moved (and temporarily stored in another location). This takes physical effort + time and should therefor be minimized.
  4. It is not possible to move a correctly ordered subset of a collection at once. This would involve picking up each sheet individually from it's stack.
  5. Once a collection is completely sorted and ordered, it can be removed from the buffer.

The question: I am getting to grips with the logic of this sorting and ordering problem. Some initial questions I have asked myself, and you might find interesting to think about/test/simulate.

  • For a given input (N, n) what is an efficient number of buffer locations (Nb)?
  • What should be the sorting logic in this problem? Which rules would work when N scales to max. 30 and n to max. 150
  • Does anyone have sources (papers, articles, algorithms, etc) on this type of problem?
  • What aspect of the system should be changed to make the sorting more efficient? For instance what would be the benefit of being able to physically move a subset of a collection at once, while maintaining it's ordering.

I was struggling with clearly writing down the specifics of this sorting and ordering problem, if something is unclear, let me know so I can provide more info.

Thanks!!

\$\endgroup\$

closed as off-topic by xnor, caird coinheringaahing, user202729, Angs, JungHwan Min Apr 11 '18 at 7:34

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – caird coinheringaahing, user202729, JungHwan Min
If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ I think this is too open-ended as a puzzle or challenge for here. Maybe you could post in on CS theory? I'd suggesting focusing down to a narrower question scope. \$\endgroup\$ – xnor Apr 11 '18 at 6:52
  • \$\begingroup\$ "what is an efficient number of buffer locations": For Max N=30 and max n=150, Nb of 30*150 = 4500 will result in "fastest" sorting (Count-sort). Are buffer locations Nb expensive? \$\endgroup\$ – GPS Apr 11 '18 at 6:55
  • 3
    \$\begingroup\$ Welcome to PPCG! This is indeed interesting (makes me think of pancake sorting). One thing to note is that this would require a winning criteria here (looks like some kind of minimisation of the measure of physical effort and/or time which you mention but do not quantify). On another note, should (4) read "It is not possible to move an incorrectly ordered subset"? \$\endgroup\$ – Jonathan Allan Apr 11 '18 at 6:57
  • 2
    \$\begingroup\$ Welcome to PPCG, I hope you stick around. Just to let you know, this site has a sandbox that can help you refine your challenges before you post them \$\endgroup\$ – Nathaniel Apr 11 '18 at 7:45

Browse other questions tagged or ask your own question.