Re^10: Challenge: Number of unique ways to reach target sum

[Limbic~Region]

fergal,
As far as I can tell my Perl is faster than your C. So (for a sanity check) if you run blokhead's memoized counting code on your machine (the machine that takes 72 mins for the C) how long does it take?

Ok - I will assume I am just being dense here. When you say that you suspect your Perl is faster than my C, I presume you are talking about this code. I modified it slightly as to not penalize it for IO. IOW, I made it go through the solutions without actually printing them. It has been running for 4 1/2 hours on the same machine that my C code takes 72 minutes to complete on and is still not finished.

When you ask me to run blokhead's memoized counting code on the same machine as the one that completes the C code in 72 minutes, I am not sure why you would want me to do this. I presume it will finish in 10 seconds or less since it isn't actually going through the solutions.

I am not trying to be unhelpful here but I just don't get at what you are trying to get me to test. Any code that I have tested that actually goes through the solutions (without printing them) takes so long I give up on including your code I linked to. What am I missing?

[fergal]

Nope, that code is only memoized for generation, the output stage is unmemoized and hence very slow.

The semi-memoized output code is in my followup. Here's the whole thing joined up and ready to run.

use List::Util 'min';
use POSIX 'ceil';
use strict;
use warnings;

sub make_ways {
    my ($N, $S, $T) = @_;

    # one coin left can we do it?
    if ($S == 1) {
        if ($T <= $N) {
            return ["$T"];
        } else {
            return 0;
        }
    }

    my $min = (2*$T-$S+$S**2)/(2*$S); ## more correctly, ceil() of thi
+s
    my $max = min( $T-(($S-1)*$S/2), $N );

    my @all_ways;
    for my $K ($min .. $max) {
        my $ways = make_ways( $K-1, $S-1, $T-$K );
        if ($ways) {
            push(@all_ways, ["$K", $ways]);
        }
    }
    if (@all_ways) {
        return \@all_ways;
    } else {
        return 0
    }
}

use Memoize;
memoize 'make_ways';

my $ways = make_ways(100, 10, 667);
my $printed = 0;
nasty_print_ways($ways, "", 6);
print "$printed\n";

# do my own memoizing as I couldn't get Memoize to work, for this func
+tion
# possibly to do with the arguments being array refs
my %strings;
sub string_ways {
  my $ways = $_[0];

  if (my $strings = $strings{$ways})
  {
    #die "already $strings";
    return $strings
  }
  my @strings;
  for my $way (@$ways) {
    if (ref $way) {
      my ($coin, $more_ways) = @$way;
      push(@strings, map {"$_+$coin"} (@{string_ways($more_ways)}));
    } else {
      push(@strings, $way);
    }
  }

  return $strings{$ways} = \@strings;
}

sub nasty_print_ways {
  my ($ways, $base, $depth) = @_;

  if ($depth == 0) {
      my $strings = string_ways($ways);
      for my $string (@$strings) {
          $printed++;
          #print STDERR "$printed\n" unless ($printed % 10000000);
          #print "$string+$base\n";
        }
  }
  else {
    $depth--;
    for my $way (@$ways) {
      if (ref $way) {
        my ($coin, $more_ways) = @$way;
        my $new_base = length($base) ? "$coin+$base" : $coin;
        nasty_print_ways($more_ways, $new_base, $depth);
      } else {
        # print "$base+$way\n";
      }
    }
  }
}

The reason I wanted you to run blokheads quick code was to be able to get a quick comparison of my machine and your machine. It's not important.

I ran your C and it took 2 or 3 hours. I'm running it again with your optimisations, although that fomit-pointer (or whatever it was) make my gcc complain.

By the way, your code printed out -114xxx. That's because j is a double (a kind of float) and you format is "%d" but %d is for int. I've changed j to unsigned long long int and printf("%lld", j). I'm waiting for it to complete.

[Limbic~Region]

fergal,
I had a copy/paste error which was the source of a whole lot of problems originally. I left j as type double and updated the printf() format as ".0f" but your way works too. I also had a missing hyphen from -fomit-frame-pointer which I corrected.

I have run this code on my machine and it finished in 53.5 minutes. I am not really shocked by this but I am impressed. The only optimizations the C code attempts to make is by limiting the number of the 17 trillion different sets it visits. Adding in a cache and some other neat doo-dads could probably blow this 53.5 minutes out of the water - but why bother. That is one of the beauties of Perl. The amount of time it would take to devise a C program to beat the Perl is more than time than it takes the Perl to run. Good Job.

[fergal]

Yeah, I thought about rewriting in C, maybe using glib to get nice hashes and strings. Memory usage would be way smaller and it would be way faster but it wouldn't be much fun to write :)

I just got

fergal@anacreon:~$ time ./lr
14479062751

real    76m17.183s
user    75m32.075s
sys     0m0.764s

fergal@anacreon:~$ time perl make_ways.pl
14479062752

real    37m46.569s
user    37m26.124s
sys     0m1.416s

That's without -march=... and -fomit-doodads.