Arranging Fenceposts

Question

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.

Answer 1

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

Answer 2

APL (Dyalog Unicode), 55 bytes

⎕CY'dfns'
{0::0⋄⍺⊃⍵{+big⌿↑(⍳1+¯1⊥⍺)⌽¨⊂0,⍣(⊢/⍺)⊢⍵}⍣⍺⍺⊢1}

Try it online! (without big, so fast but inaccurate)

The time complexity of the algorithm is \$O(m(m-n)c^2)\$, where \$m\$ and \$n\$ are max and min, and \$c\$ is the count, ignoring the cost of bigint addition (which is not a language built-in, and therefore horribly inefficient). It is nowhere close to the fastest, but it's still much faster than brute-force, as it returns the correct result for 1 10 100 700 in 3 minutes on my PC.

To use, assign the inline operator to f and call it in the form of length (count f) min max.

⎕CY'dfns'  ⍝ Load dfns library, so we can use `+big`

{0::0⋄...}  ⍝ If any error occurs, return 0
⍺⊃⍵{...}⍣⍺⍺⊢1  ⍝ Build the vector of all possible combinations by
               ⍝ taking the polynomial represented by ⍵ raised to the power of ⍺⍺,
               ⍝ then fetch the ⍺-th coefficient (might error if ⍺ is out of range)
0,⍣(⊢/⍺)⊢⍵    ⍝ Prepend "max" copies of 0s to the current polynomial
(⍳1+¯1⊥⍺)⌽¨⊂  ⍝ Generate the list of ^ rotated 0..(max-min) times
+big⌿↑        ⍝ Promote to matrix and sum the numbers vertically