in reply to Re^3: Challenge: Number of unique ways to reach target sum
in thread Challenge: Number of unique ways to reach target sum

fergal,
No, it is C code and it will be posted on Friday as indicated in the root node. I added the tongue out smiley to indicate I was only teasing blokhead.

Oh, you state elsewhere that it requires greater than 400 GB to store all the answers. Since each value in the set of 10 is 100 or less then each set only requires 10 bytes. 10 * 14_479_062_752 = 144_790_627_520 which is less than a 150 GB but still far too much. Since the code I used (and have yet to show) generates the solutions in ascending order - an even smaller amount of storage is required. There is a little overhead in bookkeeping but if I use variable length records I only need to record the portion of 1 record that differs from the previous.

Cheers - L~R

  • Comment on Re^4: Challenge: Number of unique ways to reach target sum

Replies are listed 'Best First'.
Re^5: Challenge: Number of unique ways to reach target sum
by fergal (Chaplain) on Feb 15, 2006 at 15:54 UTC

    Your C takes 72 min on your machine, how long does blokhead's perl version take on the same machine?

[reply]
      fergal,
      I only ran the version that actually iterated (without Memoize) and gave up after about 3 hours.

      Cheers - L~R

[reply]

        Well, blokhead's memoize version take < 10s so that the easiest thing available as a benchmark and it's takes little effort to run it.

        I managed to generate all solutions just using Perl in 74 mins on one machine and 2 hours on another. I'd like to be able to compare these results to your 72 mins without having to chew 72 mins of CPU. I just tried it on that machine and killed it after 93 mins. It was compiled with -O2. Have you got a very very fast machine? If so then I think Perl with ugly-memoize beats the C, which is very surprising.

[reply]

In Section Seekers of Perl Wisdom