StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POOptimizing product assembly / disassembly
text
Body
copied!<p>I have a store that contains items. Each item is either a component (which is atomal) or a product which consists of various components (but never of 2 or more of the same components).</p> <p>Now, when I want to get a product out of the store, there are various scenarios:</p> <ul> <li>The store contains the necessary number of the product.</li> <li>The store contains components of which I can assemble the product.</li> <li>The store contains products that share components with the required product. I can disassemble those and assemble the required item.</li> <li>Any combination of the above.</li> </ul> <p>Below you can see my code so far (<code>getAssemblyPath</code>). It does find a way to assemble the required item if it is possible, but it does not optimize the assembly path.</p> <p>I want to optimize the path in two ways:</p> <ul> <li>First, choose the path which takes the least number of assembly/disassembly actions.</li> <li>Second, if there are various such paths, choose the path which leave the least amount of disassembled components in the store.</li> </ul> <p>Now, here I am at a complete loss of how to get this optimization done (I am not even sure if this is a question for SO or for Maths).</p> <p><strong>How can I alter <code>getAssemblyPath</code> so that it meets my optimization requirements?</strong></p> <p>My code so far:</p> <pre><code>#! /usr/bin/python class Component: def __init__ (self, name): self.__name = name def __repr__ (self): return 'Component {}'.format (self.__name) class Product: def __init__ (self, name, components): self.__name = name self.__components = components @property def components (self): return self.__components def __repr__ (self): return 'Product {}'.format (self.__name) class Store: def __init__ (self): self.__items = {} def __iadd__ (self, item): item, count = item if not item in self.__items: self.__items [item] = 0 self.__items [item] += count return self @property def items (self): return (item for item in self.__items.items () ) @property def products (self): return ( (item, count) for item, count in self.__items.items () if isinstance (item, Product) ) @property def components (self): return ( (item, count) for item, count in self.__items.items () if isinstance (item, Component) ) def getAssemblyPath (self, product, count): if product in self.__items: take = min (count, self.__items [product] ) print ('Take {} of {}'.format (take, product) ) count -= take if not count: return components = dict ( (comp, count) for comp in product.components) for comp, count in self.components: if comp not in components: continue take = min (count, components [comp] ) print ('Take {} of {}'.format (take, comp) ) components [comp] -= take if not components [comp]: del components [comp] if not components: return for prod, count in self.products: if prod == product: continue shared = set (prod.components) & set (components.keys () ) dis = min (max (components [comp] for comp in shared), count) print ('Disassemble {} of {}.'.format (dis, prod) ) for comp in shared: print ('Take {} of {}.'.format (dis, comp) ) components [comp] -= take if not components [comp]: del components [comp] if not components: return print ('Missing components:') for comp, count in components.items (): print ('{} of {}.'.format (count, comp) ) c1 = Component ('alpha') c2 = Component ('bravo') c3 = Component ('charlie') c4 = Component ('delta') p1 = Product ('A', [c1, c2] ) p2 = Product ('B', [c1, c2, c3] ) p3 = Product ('C', [c1, c3, c4] ) store = Store () store += (c2, 100) store += (c4, 100) store += (p1, 100) store += (p2, 100) store += (p3, 10) store.getAssemblyPath (p3, 20) </code></pre> <p>This outputs:</p> <pre><code>Take 10 of Product C Take 10 of Component delta Disassemble 10 of Product A. Take 10 of Component alpha. Disassemble 10 of Product B. Take 10 of Component charlie. </code></pre> <p>Which works, but it does unnecessarily disassemble product A, as product B contains both of the required components alpha and charlie.</p> <p>--</p> <p>EDIT:</p> <p>Answering the very sensible questions of Blckknght:</p> <blockquote> <p>When you say you want "the least number of assembly/disassembly actions", do you mean the smallest number of items, or the smallest number of different products?</p> </blockquote> <p>An "asm/disasm action" is the action of assembling or disassembling one product, no matter how many components are involved. I am looking for least number of touched items, no matter whether they be distinct or not.</p> <blockquote> <p>That is, is is better to dissassemble 20 of Product A than to dissassemble 10 of Product A and an additional 5 of Product B?</p> </blockquote> <p>The latter is closer to optimum.</p> <blockquote> <p>Further, you say you want to avoid leaving many components behind, but in your current code all disassembled components that are not used by the requested Product are lost. Is that deliberate (that is, do you want to be throwing away the other components), or is it a bug?</p> </blockquote> <p>The method <code>getAssemblyPath</code> only determines the path of how to get the items. It does not touch the actual store. At no moment it assigns to <code>self.__items</code>. Think of it as a function that issues an order to the store keep of what he must do in the (inmediate) future, in order to get the required amount of the required item out of his store.</p> <p>--</p> <p>EDIT 2:</p> <p>The first obvious (or at least obvious to me) way to tackle this issue, is to search first those products, that share the maximum amount of components with the required product, as you get more required components out of each disassembly. But unfortunately this doesn't necessary yield the optimum path. Take for instance:</p> <p>Product A consisting of components α, β, γ, δ, ε and ζ.</p> <p>Product B consisting of components α, β, η, δ, ε and θ.</p> <p>Product C consisting of components α, β, γ, ι, κ and λ.</p> <p>Product D consisting of components μ, ν, ξ, δ, ε and ζ.</p> <p>We have in store 0 of A, 100 of B, 100 of C and 100 of D. We require 10 of A. Now if we look first for the products that shares most components with A, we will find B. We disassemble 10 of B getting 10 each of α, β, δ and ε. But then we need to disassemble 10 of C (to get γ) and 10 of D (to get ζ). These would be 40 actions (30 disassembling and 10 assembling). But the optimum way would be to disassemble 10 of C and 10 of D (30 actions, 20 disassembling and 10 assembling).</p> <p>--</p> <p>EDIT 3:</p> <p><strong>You don't need to post python code to win the bounty. Just explain the algorithm to me and show that it does indeed yield the optimum path, or one of the optima if several exist.</strong></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload