If you want to build a fence and have different length boards available, there are many different ways to set up your posts. So, given a minimum and maximum board length, a number of boards, and the total length, count how many ways you can arrange them.
Input
Input is four positive integers:
- min: The smallest board usable. Will be
>0. - max: The largest board available. Will be
>min. - count: Number of boards to use. Will be
>0. - length: Total length of the fence. For a valid fence, this should be
>=min*countand<=max*count
Individual boards can be any integer length between min and max (inclusive).
Output
Output a single number representing the number of ways you can arrange the fence.
Examples
For input (in order listed above) 2 3 4 10, you can arrange the boards six ways:
2233 2323 2332 3223 3232 3322 So the output is 6. If your input was 1 3 4 6, the output is 10, since there are ten ways to do it:
1113 1212 1131 1221 1311 2112 3111 2121 1122 2211 Input Output 5 10 6 45 4332 1 100 6 302 1204782674 27 53 8 315 4899086560 1 10 11 70 2570003777 1 6 15 47 20114111295 4 8 150 600 1 // all boards length 4 1 10 100 80 0 // invalid, you can't put 100 boards in 80 length Of course, there's a naive method to do this:
long f(int min, int max, int count, int length){ if(count==1) return 1; long num = 0; for(int i=min;i<=max;i++){ int goal = length - i; if(goal <= max*(count-1) && goal >= min*(count-1)){ num += f(min,max,count-1,goal); } } return num; } Rules
The algorithm given above works fine for small inputs, but it can easily overflow the long with larger inputs. Even with arbitrary-length numbers, it's incredibly inefficient. I believe it's O((max-min+1)^count).
To be considered valid for this challenge, you should be able to compute input 1 10 100 700 in under one hour on my i7. Given a more efficient algorithm than the one above, this should not be a problem. I will test any entries I believe may come close to the limit. If your algorithm takes more than a few minutes to run, you should use a freely available language (on linux) to facilitate testing.
Code may take the form of a complete program or function, with input/output as any of the standard methods. Shortest code in bytes wins.
