View Question
 Question
 Subject: Logical problem to solve Category: Computers > Algorithms Asked by: lucavilla-ga List Price: \$10.00 Posted: 15 Nov 2006 04:59 PST Expires: 15 Dec 2006 04:59 PST Question ID: 782909
 ```NOTE: what I ask here is NOT a software. I only ask the algorithm, *described in english language*, that solves the logical problem described below. _____ I want to create a website that automatically find the cheapest shipping method from a list where the dimension limits varies, asking to the user the less possible input and precision while keeping the exactness of the calculator. For example, given these shipping methods (with dimensions accepted, name, price): A) 0 to 10x10x10 inches - Letter Post Airmail USPS - \$10 B) 0 to 20x20x20 inches - Parcel Post Airmail USPS - \$40 C) 0 to 40x40x80 inches - Letter Post Airmail FedEx - \$30 D) 0 to 70x100x100 inches - Parcel Post Airmail FedEx - \$50 I would only ask to the user to select *the first* dimension that contains the object to be shipped, *from the four following*: 1) 10x10x10 2) 20x20x20 3) 40x40x80 4) 70x100x100 So that: - in case the user selects the option 1), the calculator will only search for the cheapest between A, B, C and D shipping methods - in case the user selects the option 2), the calculator will only search for the cheapest between B, C and D shipping methods - in case the user selects the option 3), the calculator will only search for the cheapest between C and D shipping methods - in case the user selects the option 4), the calculator will only search for the cheapest between D (only D) shipping method Now the problem is this: how can I manage the case in which the shipping methods dimensions cross each other? example: A) 0 to 10x20x50 inches - Letter Post Airmail DHL - \$10 B) 0 to 15x15x80 inches - Parcel Post Airmail DHL - \$40 C) 0 to 30x40x45 inches - Letter Post Airmail UPS - \$30 D) 0 to 30x35x38 inches - Parcel Post Airmail UPS - \$50 I can't simply offer to the user the following four options: 1) 10x20x50 2) 15x15x80 3) 30x35x60 4) 30x40x50 because if, for example, the object were 27x30x55 inches, the user (with the rule to select *the first* dimension that contains the object to be shipped) would select the option 3) but the calculator would not know if to consider it included in the following (30x40x50) or not. In fact in this case it's not included because the object longest side, 55, is greater than 50! In conclusion it would miss this information... I think that the solution to this problem would be to add one or two fictitious dimension options to the 4 proposed to the user, so creating 5 or 6 proposed options... (I don't know...). What I ask to you is to solve this problem (i.e. to indicate to me how to DEDUCE the fictitious dimension options to be added) with an algorithm described in english language, that works no matter of the number of the shipping methods (in reality they would be about 50...) and the complexity of them (there could be multiple crossing in the dimensions...). I will report this algorithm to the coder who is working on this project. Thank you in advance``` Clarification of Question by lucavilla-ga on 16 Nov 2006 14:34 PST ```Hi! I made an test and I found that the algorithm is not correct :( Consider these shipping methods: 1) 10x20x50 2) 15x15x80 3) 30x35x60 4) 30x40x50 You algorithm would propose to the user these dimensions: 10x15x50 good for 1) + 2) + 3) + 4) 10x20x50 good for 1) + 3) + 4) 15x15x50 good for 2) + 3) + 4) 15x15x60 good for 2) + 3) 15x15x80 good for 2) 30x35x50 good for 3) + 4) 30x35x60 good for 3) 30x40x50 good for 4) In case the user estimates his object to be 30x33x45, under the rule of selecting "*the first* dimension that contains the object to be shipped" he will select the dimension 30x35x60, that erroneously limits the prices search to the shipping method number 3) when in reality it should search through the shipping methods number 3) AND 4)``` Clarification of Question by lucavilla-ga on 16 Nov 2006 14:37 PST ```Hi! I made an test and I found that the algorithm is not correct :( Consider these shipping methods: 1) 10x20x50 2) 15x15x80 3) 30x35x60 4) 30x40x50 You algorithm would propose to the user these dimensions: 10x15x50 good for 1) + 2) + 3) + 4) 10x20x50 good for 1) + 3) + 4) 15x15x50 good for 2) + 3) + 4) 15x15x60 good for 2) + 3) 15x15x80 good for 2) 30x35x50 good for 3) + 4) 30x35x60 good for 3) 30x40x50 good for 4) In case the user estimates his object to be 30x33x45, under the rule of selecting "*the first* dimension that contains the object to be shipped" he will select the dimension 30x35x60, that erroneously limits the prices search to the shipping method number 3) when in reality it should search through the shipping methods number 3) AND 4) ?``` Clarification of Question by lucavilla-ga on 16 Nov 2006 14:40 PST ```Ooops please ignore the above clarifications! I erroneously posted them as "clarifications" instead of "comments" to be added at the bottom of the thread as answers to manuka```
 There is no answer at this time.

 Subject: Re: Logical problem to solve From: manuka-ga on 15 Nov 2006 22:45 PST
 ```You'er seriously underestimating the number of additional dimensions that would be required. If there are really about 50 base dimensions, I think doing it this way will cause you problems. You actually give two different sets of dimensions in your second example. Let's look at the simpler set: 1) 10x20x50 2) 15x15x80 3) 30x35x60 4) 30x40x50 One general algorithm would go as follows: Consider all possible combinations of 1), 2), 3), 4). For each combination, take the minimum of each dimension among all items used. Then eliminate duplicates and sort. Note that if there are n items there are 2^n - 1 combinations - this will be impossible to handle with 50 items. More on that later. 1 --> 10x20x50 1 + 2 --> 10x15x50 1 + 3 --> 10x20x50, duplicate 1 + 4 --> 10x20x50, duplicate 1 + 2 + 3 --> 10x15x50, duplicate 1 + 2 + 4 --> 10x15x50, duplicate 1 + 3 + 4 --> 10x15x50, duplicate 1 + 2 + 3 + 4 --> 10x15x50, duplicate 2 --> 15x15x80 2 + 3 --> 15x15x60 2 + 4 --> 15x15x50 2 + 3 + 4 --> 15x15x50, duplicate 3 --> 30x35x60 3 + 4 --> 30x35x50 4 --> 30x40x50 So even for this simple set you have gone from 4 options to 8. Consider the nastier set you also suggested: A) 10x20x50 B) 15x15x80 C) 30x40x45 D) 30x35x38 The combinations here are: A --> 10x20x50 AB --> 10x15x50 A C --> 10x20x45 A D --> 10x20x38 ABC --> 10x15x45 AB D --> 10x15x38 A CD --> 10x20x38, duplicate ABCD --> 10x15x38, duplicate B --> 15x15x80 BC --> 15x15x45 B D --> 15x15x38 BCD --> 15x15x38, duplicate C --> 30x40x45 CD --> 30x35x38 D --> 30x35x38, duplicate so now we have gone from 4 to 11 choices. With 50 base dimensions I would expect that you would have several hundred choices in the final list at best (if there's a fair degree of overlap in the individual sizes), and quite possibly thousands (if there's not). Now, as mentioned earlier you'll need a better algorithm for handling as many as 50 sets of dimensions. Here's one: From your dimensions, make three lists containing the distinct X, Y and Z values for each dimension. In each list, also store the maximum values for the other dimensions associated with each entry. For example, the X list for the last example would read: 10 (20) (50) 15 (15) (80) 30 (40) (45) Take each value in the X, Y and Z lists in turn (requiring X <= Y <= Z). Discard any combinations where the value of one component is greater than the maximum for that component corresponding to the selected values fo the other components. For example, the combination 15x40x50 is rejected because for X=15, the maximum value of Y is 15.(Also, for Y=40, the maximum value of Z is 45.) This way you have, instead of 2^n - 1, only n^3 or less combinations. (In most cases you will have substantially less because some component values will be repeated.) For n=50, this reduces the number of combinations to be assessed from around 1 quadrillion to 125,000 at most (and most likely much less). This is a practical number for a computer to do. For small n this is less efficient than the combinations method (the equivalence point is at n=8), and for the same example we now have 37 combinations to look at (excluding cases where X>Y or Y>Z), so I won't give you all the details, but we wind up with the same 11 combinations we found earlier. Note that this method may produce some results that don't correspond to a valid combination of options. At least, I suspect it will and I can't see a proof that it won't, but I don't have an actual example handy. They're most likely to arise when you have significant overlap in sizes used. Unfortunately I don't have a clear handle on the expected number of these; in the case where there is significant overlap of sizes used it would also be computationally tricky to check that a given result does correspond to a given combination of base dimensions. So I'll leave it at that for now.```
 Subject: Re: Logical problem to solve From: lucavilla-ga on 16 Nov 2006 14:14 PST
 ```Very very very thanks manuka for your answer! You wrote: > You actually give two different sets of dimensions in your > second example I'm really stupid! I didn't noticed it.. Obviously it's an error. And luckily you was smart enough to understand it. Sorry! You wrote: > You'er seriously underestimating the number of additional > dimensions that would be required Well... in facts they are about 50 but with just a few (no more than 5) overlaps in them... In conclusion... I find your solution very useful and I'm now evaluating if it's correct and exhaustive.```
 Subject: Re: Logical problem to solve From: lucavilla-ga on 16 Nov 2006 14:38 PST
 ```Hi! I made an test and I found that the algorithm is not correct :( Consider these shipping methods: 1) 10x20x50 2) 15x15x80 3) 30x35x60 4) 30x40x50 You algorithm would propose to the user these dimensions: 10x15x50 good for 1) + 2) + 3) + 4) 10x20x50 good for 1) + 3) + 4) 15x15x50 good for 2) + 3) + 4) 15x15x60 good for 2) + 3) 15x15x80 good for 2) 30x35x50 good for 3) + 4) 30x35x60 good for 3) 30x40x50 good for 4) In case the user estimates his object to be 30x33x45, under the rule of selecting "*the first* dimension that contains the object to be shipped" he will select the dimension 30x35x60, that erroneously limits the prices search to the shipping method number 3) when in reality it should search through the shipping methods number 3) AND 4) ?```
 Subject: Re: Logical problem to solve From: lucavilla-ga on 22 Nov 2006 16:38 PST
 ```I made an error again: in my example the user would select the dimension 30x35x50, that limits the prices search to the shipping methods number 3) AND 4) and this would be EXACT! I need to evaluate your algorithm again because it could be exact :) Tomorrow I'll perform other tries on it and will tell you if I understimated your genial algorithm! :D```
 Subject: Is this possible ... From: fedebaeza-ga on 29 Nov 2006 13:55 PST
 ```Hi, all ... If you try calculating the volume of the package in order to discard the smaller ones. You can compare uni-dimensionally, i mean. Let:a) 10x20x50 10E b) 15x15x80 30E c) 30x35x60 20E d) 30x40x50 40E Set a,b,c,b = false Set aprice, bprice, cprice, dprice = 99999999 If user-lengh < d-lengh If user-width < d-width if user-high < d-high Set d = true Set dprice=d-real-price End-If End-If End-If If user-lengh < c-lengh If user-width < c-width if user-high < c-high Set c = true Set cprice=c-real-price End-If End-If End-If If user-lengh < b-lengh If user-width < b-width if user-high < b-high Set b = true Set bprice=b-real-price End-If End-If End-If If user-lengh < a-lengh If user-width < a-width if user-high < a-high Set a = true Set aprice=a-real-price End-If End-If End-If If a,b,c,d=F It does not fit anyone. Else search-min (aprice,bprice,cprice,dprice) End-If```