Once in a while, my wife sends me to a REAL supermarket, with a shopping list (she writes me an a piece of paper, or texts me a message).
I was wondering is there a fast way to for-fill the list, without iterating the whole super a dozens of times, till I believe I've got everything.
(I found this question very helpful in life: pair-socks-from-a-pile-efficiently, and hoped I can use the community's help in my own situation)
I don't know/remember where each item is located in the supermarket, and the list I'm given is never sorted (for example, vegetables are listed all over the list, and not one after the other). Also, usually I get continuously text messages with more and more items to buy, while I'm still in the super.
My approach is planning a path that would assure me I iterate the whole supermarket, and pick items from the list while walking that path.
(n)I pass: check if I have such item in my list (m), will give me an
O(n*m)complicity, which not so efficient.
(p): standing on the beginning of each row I can read the sign or see which sort of items I should find there, than iterate my list, trying to remember all items in list I should find in that row. than walk that row and add those items to my cart, should give me
O(p*m)complicity. but this never really happens: I can't remember more than three of four items from my list I'm expecting to find in that row, and even if I do, I often forget an item and have to use this algorithm again (lets say
qtimes), which comes to:
A couple of comments I'd like to add:
(v). Sure I can't remember all those veggies, and rather not stop next to each vegetable in the market (or should I?), to check if I've got it in my list.
If you can get the shopping list ordered corresponding to the store's layout, that's a massive help (I'm talking real-life here, not necessarily algorithmically)
kaveman. sure it will be helpful, but supers usually change their layout in order to get us wonder all around the shop.
As long as you don't forget what to get in each aisle once for each item in that aisle, then your O(qpm) is still better than O(nm). Also provided there are at least one aisle with nothing you need, p (aisles you visit) will be less then P (aisles that exist), possibly negating q entirely. IF you go down one row and forget something ten times, it will still be more efficient than walking down ten rows, checking n/p items, to confirm you don't need any of it.
+1 just for mentioning the pair-socks-from-a-pile-efficiently. First time I came across it, made my day.
Real life answer: Shop online (like walmart.com/cp/food/976759 for the USA). Otherwise constraints like having items added while you go, memory limitations of three items at a time, etc. really make this difficult. I am saying this because I have the same issue...