Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

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

by Limbic~Region (Chancellor)
on Feb 15, 2006 at 15:37 UTC ( #530417=note: print w/replies, xml ) Need Help??


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

All,
As this thread has apparently lost interest, I am posting my code today instead of waiting until Friday. Note that you will have to uncomment one of the printf() to see the solutions.
#include <stdio.h> #include <stdlib.h> int sum (vals, end) int *vals, end; { int i, tot = 0; for (i = 0; i <= end; ++i) { tot += vals[i]; } return tot; } int sum1_n (n) int n; { return (n * n + n) / 2; } int Find_Eligible (list) int *list; { int i; for (i = 9; i ; --i) { if (list[i] - list[i - 1] > 1) return i - 1; } return -1; } void Reset_Dials (pos, i) int *pos, i; { for (; i <= pos[0] ; ++i) { pos[i] = 1; } } void Find_Range (target, prev, max_x, range) int target, prev, max_x, *range; { int guess; if (prev == 0) { range[0] = 0; range[1] = 0; return; } guess = (100 * max_x - target) * -1; if (guess >= prev) { range[0] = guess; if (range[0] == prev) ++range[0]; range[1] = 100 - max_x; return; } range[0] = prev + 1; range[1] = ((target - range[0]) / (max_x ? max_x : 1)) - max_x; if (range[0] > range[1] || ! max_x) { range[0] = 0; range[1] = 0; } } int Next_Loop (list) int *list; { static int d1[100], d2[100], d3[100], d4[100], d5[100], d6[100], d +7[100], d8[100], d9[100]; static int *dial[10] = {0, d1, d2, d3, d4, d5, d6, d7, d8, d9}; static int pos[10], base_sum, permuting, loops; int range[2], i, j, prev, max_x, target, tot = 0; if (! permuting) { int idx = Find_Eligible(list); if (idx == -1) return 0; loops = 9 - idx; pos[0] = loops; Reset_Dials(pos, 1); pos[loops] = 0; ++list[idx]; base_sum = sum(list, idx); for (i = 1; i <= loops; ++i) { max_x = loops - i; target = 667 - (base_sum - sum1_n(max_x - 1)); for (j = 1; j < i; ++j) { target -= dial[j][1]; } prev = i == 1 ? list[idx] : dial[i - 1][1]; Find_Range(target, prev, max_x, range); for (j = 1; range[0] <= range[1]; ++j) { dial[i][j] = range[0]++; } dial[i][0] = j - 1; } } if (++pos[loops] > dial[loops][0]) { i = loops; while (--i) { if (pos[i] == dial[i][0]) continue; ++pos[i]; Reset_Dials(pos, i + 1); break; } if (! i) { permuting = 0; return 1; } for (i = i + 1; i <= loops; ++i) { max_x = loops - i; target = 667 - (base_sum - sum1_n(max_x - 1)); for (j = 1; j < i; ++j) { target -= dial[j][pos[j]]; } prev = dial[i - 1][pos[i - 1]]; Find_Range(target, prev, max_x, range); for (j = 1; range[0] <= range[1]; ++j) { dial[i][j] = range[0]++; } dial[i][0] = j - 1; } } permuting = 1; int idx = 10 - loops; for (i = 1; i <= 10; ++i) { tot += i <= idx ? list[i - 1] : dial[i - idx][pos[i - idx]]; } if (tot != 667) return 1; for (i = 1; i <= loops; ++i) { list[i - 1 + idx] = dial[i][pos[i]]; } return -1; } int main () { int l[10] = {1, 2, 3, 76, 95, 96, 97, 98, 99, 100}; /*int l[10] = {47, 51, 52, 56, 58, 63, 74, 85, 89, 92};*/ short int i; double j = 0.0; while (1) { i = Next_Loop(l); if (i == -1) { ++j; /*printf("%d %d %d %d %d %d %d %d %d %d\n", l[0], l[1], l[ +2], l[3], l[4], l[5], l[6], l[7], l[8], l[9]);*/ } if (! i) break; } printf("%.0f\n", j); return 0; }

Cheers - L~R

Update: Fixed format of printf() that was causing type problems

Replies are listed 'Best First'.
Re^2: Challenge: Number of unique ways to reach target sum
by thor (Priest) on Feb 15, 2006 at 22:31 UTC
    As this thread has apparently lost interest, I am posting my code today instead of waiting until Friday.
    Patience, dear Limbic~Region. You had a solution already in the can when you posted this. Not everybody had that advantage. Just because nobody has posted in a while doesn't make it any less intersting...

    thor

    The only easy day was yesterday

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://530417]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (5)
As of 2020-07-10 23:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?