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 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 a single number representing the number of ways you can arrange the fence.


For input (in order listed above) 2 3 4 10, you can arrange the boards six ways:


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){
        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;


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.


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.

def f(l,u,c,s)

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:


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

APL (Dyalog Unicode), 55 bytes


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
| improve this answer | |

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.