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

For symmetry reasons, you get the same result as if you calculate the number of ways you can generate 10 * 101 - 667 = 343 as the sum of 10 numbers in 1 .. 100.

This can speed the calculation to twice three times faster with a minimal change in the program, and eight four times faster if you
use this knowledge for every intermediate result.

Here's the resulting faster variant of my script: (Update: I've removed the redundant code from this snippet, as noted on Re: Challenge: Number of unique ways to reach target sum and updated the benchmarks accordingly) 

ruby -we '@a = (0 .. 10).map { (0 .. 667).map { (0 .. 101).map { (); }
+; }; }; def res c = 10, t = 667, m = 101; c * m - t < t and t = c * m
+ - t; if t < 0; 0; else @a[c][t][m] ||= if 0 == c && 0 == t; 1; elsif
+ 0 == c; 0; elsif 0 == t; 0; else (1 ... m).inject(0) {|r, x| r + res
+(c - 1, t - x, x); } end; end; end; (1 .. 10).each {|c| res c; warn "
+[c=#{c}]"; }; p res;'

[download]
 
ruby -we '@a = (0 .. 10).map { (0 .. 667).map { (0 .. 101).map { (); }
+; }; }; def res c = 10, t = 667, m = 101; c * m - t < t and t = c * m
+ - t; if t < 0; 0; else @a[c][t][m] ||= if 0 == c && 0 == t; 1; elsif
+ 0 == c; 0; elsif 0 == t; 0; else (1 ... m).inject(0) {|r, x| r + res
+(c - 1, t - x, x); } end; end; end; p res;'

[download]

This of course works only in those solutions which calculate the number of possibilities only, not for those that iterate on them all.

Update: blokhead's reply has another interesting optimization.

It uses the fact that if if t is too small or too large, there'll be no solutions. (Too small means t < c * (c + 1) / 2.) I'm not doing that, but at least I check for t being too small when I'm calculating a value. I don't have to check for it being too large explicitly, as that's taken care by the symmetry. This optimization gives a 20% 15% speed improvement. Some other optimizations (not that the big ifelse statement has disappeared completely) give some extra improvement,
so now my new code runs yet 30% 45% faster than the above.

Here's the result. 

ruby -we '@tri = (0 .. 10).map {|c| c * (c + 1) / 2; }; @a = [[Array.n
+ew(101, 1)] + [Array.new(101, 0)] * 400] + (1 .. 10).map { (0 .. 400)
+.map { Array.new(101); }; }; def res c = 10, t = 667, m = 101; (t2 = 
+c * m - t) < t and t = t2; if t < @tri[c]; 0; else @a[c][t][m] ||= (1
+ ... m).inject(0) {|r, x| r + res(c - 1, t - x, x); } end; end; puts 
+r = res; r == 14479062752 or fail;'

[download]

Update:

Constraing the sum to the correct range
like blokhead does makes it even more faster (with 40%). Here's the newer code. 
ruby -we '@tri = (0 .. 10).map {|c| c * (c + 1) / 2; }; @a = [[Array.n
+ew(101, 1)] + [Array.new(101, 0)] * 400] + (1 .. 10).map { (0 .. 400)
+.map { Array.new(101); }; }; def res c = 10, t = 667, m = 101; (t2 = 
+c * m - t) < t and t = t2; if t < @tri[c]; 0; else @a[c][t][m] ||= (g
+ = @tri[c - 1]; ((t + g)/c .. [m - 1, t - g].min)).inject(0) {|r, x| 
+r + res(c - 1, t - x, x); } end; end; puts r = res; r == 14479062752 
+or fail;'

[download]

Update: Improving this a tad bit more, we get 

ruby -we '@tri = (0 .. 10).map {|c| c * (c + 1) / 2; }; @a = (0 .. 10)
+.map { (0 .. 400).map { Array.new(101); }; }; def res c = 10, t = 667
+, m = 101; (t2 = c * m - t) < t and t = t2; if t <= 0; if t == 0 && c
+ == 0; 1 else 0 end; else @a[c][t][m] ||= (g = @tri[c - 1]; ((t + g)/
+c .. [m - 1, t - g].min)).inject(0) {|r, x| r + res(c - 1, t - x, x);
+ } end; end; puts r = res; r == 14479062752 or fail;'

[download]

In Section Seekers of Perl Wisdom