On ordering appetizers

July 9, 2007 at 10:31 am · Filed under Open source (english), Syre

Some random perl code I threw together:


use Data::Dumper;
use List::Util (reduce);

@p = (580, 420, 355, 335, 275, 215);
$target = 1505;
$A[0] = [0, [], 0];
foreach $i (1 .. $target) {
    my @tmp;
    foreach $a (@A) {
	next unless defined($a);
        push @tmp, [$a->[0], $a->[1], $i];
        push @tmp, [$a->[0] + $_, [@{$a->[1]}, $_], $i] foreach (@p);
    }
    @tmp = grep({$_->[0] == $i;} @tmp);

    # ok, prefer the shortes solution for no other reason
    # than 7 times mixed fruit is so boring.
    $A[$i] = reduce { if ($a->[0] == $b->[0]) {
                          @{$a->[1]} < @{$b->[1]} ? $a : $b
                      } else {
                          $a->[0] > $b->[0] ? $a : $b
                      }
                    } @tmp;
}
print Dumper($A[$target]);

Mixed fruit? You probally have to read this xkcd strip

Update: Changing the grep statement from testing for less than or equal to strict equality seems to be about 30 times faster with the same result.

3 Comments »

  1. Matthias Urlichs said,

    July 10, 2007 @ 7:59 pm

    Well, here’s a Python version. It happens to be a whole lot faster than yours.
    Using appropriate data structures helps, I would say. ;-)

    It prefers the shortest solution because the pqueue module is a FIFO for equal amounts (aka priority values).

    #!/usr/bin/python
    import pqueue

    p = (580, 420, 355, 335, 275, 215)
    target = 1505

    q = pqueue.PQueue()
    q.insert(0,(0,)*len(p))

    current = -1
    while True:
    val,data = q.pop()
    if val == target:
    print [a for a in zip(data,p) if a[0]]
    break
    if current == val: continue
    current = val
    data = list(data)
    for f in range(len(p)):
    val += p[f]
    data[f] += 1
    q.insert(val,tuple(data))
    data[f] -= 1
    val -= p[f]

  2. Matthias Urlichs said,

    July 10, 2007 @ 8:01 pm

    Sorry about the indent lossage.

    indent everything below while: once, everything below for: twice, and the print+break twice.

  3. Peter Makholm said,

    July 11, 2007 @ 9:06 am

    Not just a Python version but a quite different solution. I don’t think it’is you data structure but an much better algorithm that makes the difference. Reimplementing it in perl with a dumb list gives a comparable speed:

    
#!/usr/bin/perl

$, = " ";

@p = (580, 420, 355, 335, 275, 215);
$target = 1505;

my @solution = ([0]);
while (($val,@data) = @{ shift @solution }) {
        next if $val > $target;
        do { print @data; last } if $val == $target;

        push @solution, [$val + $_, @data, $_] for @p;
}

    For harder problems and for a general solution which is to be run again and again speed will be an issue. But for solving a specific problem I couldn’t care less if it takes a minute or two to run - it’s all about getting things done.

    But my original code is crude, brute and ignorant and probally didn’t deserved to be made public.

RSS feed for comments on this post · TrackBack URI

Leave a Comment