6
\$\begingroup\$

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*count and <=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.

\$\endgroup\$
4
\$\begingroup\$

Ruby: 106 98 93 bytes

Update: Changed cache key type from strings to arrays. (-5)

Update: Storing the initial condition in the cache payed out quite well. (-8) However, it increases the runtime for the test case to roughly 2 seconds.

I simply use memoization. I guess it can be further golfed as my Ruby skills are far from perfect.

@m={[0,0]=>1}
def f(l,u,c,s)
  @m[[c,s]]||=s<0?0:(l..u).map{|x|f(l,u,c-1,s-x)}.reduce(:+)
end

Note that it runs for only one test case at a time, since I don't cache the min and max values (l and u, respectively). Here is my output for 1 10 100 700:

121130639107583774681451741625922964085713989291260198434849317132762403014516376282321342995

real    0m0.316s
user    0m0.312s
sys     0m0.004s
\$\endgroup\$
  • \$\begingroup\$ Yes, that's the correct output. \$\endgroup\$ – Geobits Sep 11 '14 at 17:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.