Forum: Ruby #65: Splitting the Loot

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
E208b6a1d15b63fec4eeaaa43f2d5b9a?d=identicon&s=25 Luke Blanshard (Guest)
on 2006-02-05 17:05
(Received via mailing list)
My submission is attached.  The key insight: if you start with the
largest values you can divide the loot one gang member at a time without
fear of getting wrongly stuck.  For an example of being wrongly stuck,
consider:

% ruby loot.rb 3 1 1 1 2 2 2

The shares will all have to total 3, but if you start with the light end
you might end up with (1, 1, 1) for the first guy, and then the rest of
the loot can't be evenly split.  Starting with the heavy end, though,
gets you to the right place.

Technically, this is not so much an insight as an intuition.  It might
not be true in all cases.  But using it as a heuristic, we can cut the
solution down to O(n^3).

The "split" function takes a list of values and the number of gang
members and returns a list of sublists that all sum to the same amount,
or nil if no solution is possible.  It works by sorting the list of
values and calling "pick" once for each gang member to pick out that
member's share from the remaining list.  Using our insight, we never
backtrack in "split".  Once we've picked one member's share, we never go
back to try a different combination.

"Pick" works recursively, walking from the high end of the list to the
low end, until it finds a sublist that sums to the target amount or it
runs off the end of the list.  This function waits to delete elements
from the list until it finds a sublist that sums to the target amount.
In this way, "pick" doesn't have to create any intermediate lists.


Luke Blanshard
0d298cda3121e5cacaa2465437769025?d=identicon&s=25 Levin Alexander (Guest)
on 2006-02-05 19:36
(Received via mailing list)
My solution is attached.  It solves via recursion with a few
optimizations (it is still really slow, though)

 * it checks, if the sum of all pieces is divisable by the number of
persons,
   if not, then there is no solution.
 * it avoids giving every piece to the first person at the beginning

Two interesting methods I used:

  module Enumerable
    def all_equal?
      self.inject { |a,b| break false unless a == b; b } != false }
    end
  end
  [3,3,3,3].all_equal? #=> true

  class Object
    def if_false; self ? self : yield; end;
  end

This works nicely for Enumerable#find:

  [1,2,3,4,5].find {|x| x > 10}.if_false { warn "nothing found"; -1 }
#=> -1

-Levin
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2006-02-05 23:29
(Received via mailing list)
On 2/5/06, Luke Blanshard <luke@blanshard.us> wrote:
> My submission is attached.  The key insight: if you start with the
> largest values you can divide the loot one gang member at a time without
> fear of getting wrongly stuck.
...
> Technically, this is not so much an insight as an intuition.  It might
> not be true in all cases.  But using it as a heuristic, we can cut the
> solution down to O(n^3).
>

I thought I had a similar speedy solution, but then I found a few
places it fails:
Try splitting [4, 6, 8, 9, 18, 26, 34, 36, 39, 40, 43, 50, 55, 66, 67,
76, 82, 83, 86, 91, 96] into 5 parts.

The top-down approach fails to find an even division, but it is
possible:
0: 82 66 55
1: 86 67 50
2: 91 76 36
3: 96 83 18 6
4: 43 40 39 34 26 9 8 4

I used the following to generate a bunch of test cases (not all of
which are solvable):
  r = []
  n=rand(8)+2
  20.times{|e| r<< rand(100); }
  r << n-r.sum%n i #make sure it's divisible
  p n,r


-Adam
E208b6a1d15b63fec4eeaaa43f2d5b9a?d=identicon&s=25 Luke Blanshard (Guest)
on 2006-02-05 23:41
(Received via mailing list)
Adam Shelly wrote:
>> solution down to O(n^3).
>>
>>
>
> I thought I had a similar speedy solution, but then I found a few
> places it fails:...
>

Rats, you're right.  I came upon an example too.  Oh well.

Luke
12271b6df73fe29930d65586be5a4a70?d=identicon&s=25 Dave Howell (Guest)
on 2006-02-06 00:50
(Received via mailing list)
On Feb 5, 2006, at 14:38, Luke Blanshard wrote:

>>> Technically, this is not so much an insight as an intuition.  It
>
> Rats, you're right.  I came upon an example too.  Oh well.
>

Can you share any of these special cases??
Ddbfebb47432f6599da361df6a135c7c?d=identicon&s=25 Adam Shelly (Guest)
on 2006-02-06 04:36
(Received via mailing list)
On 2/5/06, Dave Howell <groups@grandfenwick.net> wrote:
>
> Can you share any of these special cases??
>

Try splitting [4, 6, 8, 9, 18, 26, 34, 36, 39, 40, 43, 50, 55, 66, 67,
76, 82, 83, 86, 91, 96] into 5 parts.
E208b6a1d15b63fec4eeaaa43f2d5b9a?d=identicon&s=25 Luke Blanshard (Guest)
on 2006-02-06 10:59
(Received via mailing list)
I wrote:
> ...
> Technically, this is not so much an insight as an intuition.  It might
> not be true in all cases...
D'oh!  Here's my second solution, which does backtrack if necessary.  It
handles Adam's example, and a shorter example I found:


$ ruby loot.rb 3   3 3 2 2 2 2 2 2 2 1
This loot can't be evenly split 3 ways

$ ruby loot2.rb 3   3 3 2 2 2 2 2 2 2 1
1: 2 2 3
2: 2 2 3
3: 1 2 2 2


$ ruby loot.rb 5   4 6 8 9 18 26 34 36 39 40 43 50 55 66 67 76 82 83 86
91 96
This loot can't be evenly split 5 ways

$ ruby loot2.rb 5   4 6 8 9 18 26 34 36 39 40 43 50 55 66 67 76 82 83 86
91 96
1: 4 8 9 86 96
2: 6 39 67 91
3: 18 26 76 83
4: 55 66 82
5: 34 36 40 43 50


This one uses recursive yielding to manage the search space.  It should
be close to the first solution in speed for cases where the heuristic
applies, except for the array duping.

Luke Blanshard
0d298cda3121e5cacaa2465437769025?d=identicon&s=25 Levin Alexander (Guest)
on 2006-02-06 11:14
(Received via mailing list)
On 2/5/06, Levin Alexander <levin@grundeis.net> wrote:
> My solution is attached.  It solves via recursion with a few
> optimizations (it is still really slow, though)

Here is an updated version that stops recursing, if someone gets
assigned more than his share.  (I can not *believe* that I did not
think of this earlier)  This speeds everything up quite a lot.

-Levin
4299e35bacef054df40583da2d51edea?d=identicon&s=25 James Gray (bbazzarrakk)
on 2006-02-06 15:59
(Received via mailing list)
On Feb 6, 2006, at 3:57 AM, Luke Blanshard wrote:

> $ ruby loot2.rb 5   4 6 8 9 18 26 34 36 39 40 43 50 55 66 67 76 82
> 83 86 91 96
> 1: 4 8 9 86 96
> 2: 6 39 67 91
> 3: 18 26 76 83
> 4: 55 66 82
> 5: 34 36 40 43 50

Looks like there are multiple correct splits for this one:

$ ruby loot.rb 5 4 6 8 9 18 26 34 36 39 40 43 50 55 66 67 76 82 83 86
91 96
1: 4 6 8 9 18 26 39 43 50
2: 34 83 86
3: 36 76 91
4: 40 67 96
5: 55 66 82

James Edward Gray II
64b06c594bfa93f0326ba39a8c5538b4?d=identicon&s=25 Patrick Deuster (Guest)
on 2006-02-06 16:17
(Received via mailing list)
James Edward Gray II wrote:
> Looks like there are multiple correct splits for this one:
>
>

My one produces a similar solution

ruby loot.rb 5 4 6 8 9 18 26 34 36 39 40 43 50 55 66 67 76 82 83 86 91
96

1: 26 86 91
2: 40 67 96
3: 55 66 82
4: 8 36 76 83
5: 4 6 9 18 34 39 43 50
This topic is locked and can not be replied to.