Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Here is how I would solve this problem. I wanted to write code for this but I don't think I have time.</p> <p>You can find an optimal solution recursively. Make a data structure that represents the state of the parts store and the current request. Now, for each part you need, make a series of recursive calls that try the various ways to fill the order. The key is that by trying a way to fill the order, you are getting part of the work done, so the recursive call is now a slightly simpler version of the same problem.</p> <p>Here's a specific example, based on your example. We need to fill orders for product 3 (p3) which is made of components c1, c3, and c4. Our order is for 20 of p3, and we have 10 p3 in stock so we trivially fill the order for the first 10 of p3. Now our order is for 10 of p3, but we can look at it as an order for 10 of c1, 10 of c3, and 10 of c4. For the first recursive call we disassemble a p1, and fill an order for a single c1 and place an extra c2 in the store; so this recursive call is for 9 of c1, 10 of c3, and 10 of c4, with an updated availability in the store. For the second recursive call we disassemble a p2, and fill an order for a c1 and a c4, and put an extra c2 into the store; so this recursive call is for 9 of c1, 10 of c3, and 9 of c4, with an updated availability in the store.</p> <p>Since each call reduces the problem, the recursive series of calls will terminate. The recursive calls should return a cost metric, which either signals that the call failed to find a solution or else signals how much the found solution cost; the function chooses the best solution by choosing the solution with the lowest cost.</p> <p>I'm not sure, but you might be able to speed this up by memoizing the calls. Python has a really nifty builtin new in the 3.x series, <code>functools.lru_cache()</code>; since you tagged your question as "Python 3.2" this is available to you.</p> <p><a href="https://stackoverflow.com/questions/1988804/what-is-memoization-and-how-can-i-use-it-in-python">What is memoization and how can I use it in Python?</a></p> <p>The memoization works by recognizing that the function has already been called with the same arguments, and just returning the same solution as before. So it is a cache mapping arguments to answers. If the arguments include non-essential data (like how many of component c2 are in the store) then the memoization is less likely to work. But if we imagine we have products p1 and p9, and p9 contains components c1 and c9, then for our purposes disassembling one of p1 or one of p9 should be equivalent: they have the same disassembly cost, and they both produce a component we need (c1) and one we don't need (c2 or c9). So if we get the recursive call arguments right, the memoization could just return an instant answer when we get around to trying p9, and it could save a lot of time.</p> <p>Hmm, now that I think about it, we probably can't use <code>functools.lru_cache()</code> but we can just memoize on our own. We can make a cache of solutions: a dictionary mapping tuples to values, and build tuples that just have the arguments we want cached. Then in our function, the first thing we do is check the cache of solutions, and if this call is equivalent to a cached solution, just return it.</p> <p>EDIT: Here's the code I have written so far. I haven't finished debugging it so it probably doesn't produce the correct answer yet (I'm not certain because it takes a long time and I haven't let it finish running). This version is passing in dictionaries, which won't work well with my ideas about memoizing, but I wanted to get a simple version working and then worry about speeding it up.</p> <p>Also, this code takes apart products and adds them to the store as components, so the final solution will first say something like "Take apart 10 product A" and then it will say "Take 20 component alpha" or whatever. In other words, the component count could be considered high since it doesn't distinguish between components that were already in the store and components that were put there by disassembling products.</p> <p>I'm out of time for now and won't work on it for a while, sorry.</p> <pre><code>#!/usr/bin/python3 class Component: def __init__ (self, name): self.__name = name #def __repr__ (self): return 'Component {}'.format (self.__name) def __repr__ (self): return 'C_{}'.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) def __repr__ (self): return 'P_{}'.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 get_assembly_path (self, product, count): store = self.__items.copy() if product in store: take = min (count, store [product] ) s_trivial = ('Take {} of {}'.format (take, product) ) count -= take if not count: print(s_trivial) return dict_decr(store, product, take) product not in store order = {item:count for item in product.components} cost, solution = solver(order, store) if cost is None: print("No solution.") return print("Solution:") print(s_trivial) for item, count in solution.items(): if isinstance(item, Component): print ('Take {} of {}'.format (count, item) ) else: assert isinstance(item, Product) print ('Disassemble {} of {}'.format (count, item) ) 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) &amp; 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) ) def str_d(d): lst = list(d.items()) lst.sort(key=str) return "{" + ", ".join("{}:{}".format(k, v) for (k, v) in lst) + "}" def dict_incr(d, key, n): if key not in d: d[key] = n else: d[key] += n def dict_decr(d, key, n): assert d[key] &gt;= n d[key] -= n if d[key] == 0: del(d[key]) def solver(order, store): """ order is a dict mapping component:count store is a dict mapping item:count returns a tuple: (cost, solution) cost is a cost metric estimating the expense of the solution solution is a dict that maps item:count (how to fill the order) """ print("DEBUG: solver: {} {}".format(str_d(order), str_d(store))) if not order: solution = {} cost = 0 return (cost, solution) solutions = [] for item in store: if not isinstance(item, Component): continue print("...considering: {}".format(item)) if not item in order: continue else: o = order.copy() s = store.copy() dict_decr(o, item, 1) dict_decr(s, item, 1) if not o: # we have found a solution! Return it solution = {} solution[item] = 1 cost = 1 print("BASIS: solver: {} {} / {} {}".format(str_d(order), str_d(store), cost, str_d(solution))) return (cost, solution) else: cost, solution = solver(o, s) if cost is None: continue # this was a dead end dict_incr(solution, item, 1) cost += 1 solutions.append((cost, solution)) for item in store: if not isinstance(item, Product): continue print("...Product components: {} {}".format(item, item.components)) assert isinstance(item, Product) if any(c in order for c in item.components): print("...disassembling: {}".format(item)) o = order.copy() s = store.copy() dict_decr(s, item, 1) for c in item.components: dict_incr(s, c, 1) cost, solution = solver(o, s) if cost is None: continue # this was a dead end cost += 1 # cost of disassembly solutions.append((cost, solution)) else: print("DEBUG: ignoring {}".format(item)) if not solutions: print("DEBUG: *dead end*") return (None, None) print("DEBUG: finding min of: {}".format(solutions)) return min(solutions) 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) store.get_assembly_path(p3, 20) </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POOptimizing product assembly / disassembly
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USsteveha
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThank you very much. I will analyse your answer in more detail, but just now I am a bit busy. One problem I see with memoization is that it reduces significantly the recursion depth, which is always a bugger as python doesn't allow for LCO. But well, every recursive algorithm can be serialized.
      singulars
      1. PO
      1. USHyperboreus
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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