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

Is that Perl code to generate them all in 72 minutes? I can't see it posted anywhere.
  • Comment on Re^3: Challenge: Number of unique ways to reach target sum

Replies are listed 'Best First'.
Re^4: Challenge: Number of unique ways to reach target sum
by Limbic~Region (Chancellor) on Feb 15, 2006 at 13:19 UTC
    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

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

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

        Cheers - L~R