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

blokhead,
This answer agrees with mine. The difference is that I actually iterate over the solutions which I am not sure your code could do in the 72 minutes it takes mine to run :P

Cheers - L~R

Update: This node was updated several times to address an implicit casting bug in my C code which truncated my answer.

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

Replies are listed 'Best First'.
Re^3: Challenge: Number of unique ways to reach target sum
by fergal (Chaplain) on Feb 15, 2006 at 01:51 UTC
    Is that Perl code to generate them all in 72 minutes? I can't see it posted anywhere.
[reply]
      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

[reply]

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

[reply]

In Section Seekers of Perl Wisdom