From: Luke Blanshard <luke@...>
Date: 2006-02-12T01:30:35+09:00
Subject: Re: [SUMMARY] Splitting the Loot (#65)

Wow, right you are.  I guess this 3AM coding thing has its down side.

Bill Dolinar wrote:
> Sorry.  Wrong example.  It won't split for things including 2 values 
> equalling the maximum split amount like:
>
> loot.rb 3  5 5 5
> loot.rb 3  4 1 5 5
> loot.rb 3  3 2 5 5
> loot.rb 3  3 1 1 5 5
> loot.rb 3  2 3 5 5
> loot.rb 3  2 2 1 5 5
> loot.rb 3  2 1 1 1 5 5
> loot.rb 3  1 1 1 1 1 5 5
> loot.rb 3  5 4 1 5
> loot.rb 3  5 3 2 5
> loot.rb 3  5 3 1 1 5
> loot.rb 3  5 2 3 5
> loot.rb 3  5 2 2 1 5
> loot.rb 3  5 2 1 1 1 5
> loot.rb 3  5 1 1 1 1 1 5
> loot.rb 3  5 5 4 1
> loot.rb 3  5 5 3 2
> loot.rb 3  5 5 3 1 1
> loot.rb 3  5 5 2 3
> loot.rb 3  5 5 2 2 1
> loot.rb 3  5 5 2 1 1 1
> loot.rb 3  5 5 1 1 1 1 1
>
> Bill
>
> On Feb 11, 2006, at 6:24 AM, Luke Blanshard wrote:
>
>> Aha.  You need to be using my *second* solution, cleverly named 
>> "loot2.rb".  Though actually, when I tested them with your example, 
>> they both worked.  Can you give more detail?
>>
>> Luke
>>
>> Bill Dolinar wrote:
>>> One group of combinations I found that Luke's solution didn't work 
>>> for was when the loot included a single value to be split to one 
>>> partner such as:
>>>
>>> ruby loot.rb 3 5 4 4 1 1
>>>
>>> It will work if you expand the line in the pick function reading:
>>>
>>> i += 1 while i < values.size && values[i] >= sum
>>>
>>> to:
>>>
>>> if values[lo] == sum
>>>     i += 1
>>> else
>>>     i += 1 while i < values.size && values[i] >= sum
>>> end
>>>
>>> I'm not sure how this changed the speed, but for all solvable 
>>> combinations of 3 partners with a sum of 9 Luke's ran in 80 seconds, 
>>> and Manuel's ran in 105 seconds.
>>>
>>> Bill
>>>
>>>
>>> On Feb 9, 2006, at 4:23 PM, Manuel Kasten wrote:
>>>
>>>> I want to mention Luke Blanchard's second solution. It is the fastest
>>>> solution of those I tested that worked without flaws. I never ever saw
>>>> it running longer than 0.2 seconds and I did test it a *lot* 
>>>> (because it
>>>> is around factor 10-20 faster than the next correct solution, and I
>>>> thought it must fail sometimes, but it never did). I couldn't believe
>>>> its speed. I studied his code for ca. 30 min just to understand what
>>>> it's doing (luckily it's got a lot of comments, I wouldn't have been
>>>> able to understand it otherwise). Then I could tell it is indeed
>>>> correct, but its speed is nevertheless amazing.
>>>
>>>
>>
>>
>
>
>
>
>