Linear equation with 3 variables in C

Question

I am given my C class homework, which is:

A hyperloop track is built of individual pipe segments of certain length. The track starts and ends with a bulkhead, and there is a bulkhead in-between each two pipe segments. The segments are produced by two different manufacturers(s1 and s2). Lengths of the segments(s1,s2), bulkheads(b), and of the desired track(l) are given. The task is to develop a function that will, based on these 4 parameters, decide whether there are valid combinations of segments and bulkheads that will result in the exact length of the desired track, and, if there are, output the number of these combinations.

Note: two different segments may be equal in their lengths, the length of a bulkhead may also be equal to zero.

My opinion is that I should solve a linear equation with 3 variables:

(m)*s1 + (n)*s2 + (m+n+1)*b = l

But I have no idea which method I should use to write an efficient code.

Answer 1

Equation provides criteria for finding combinations. When writing c code for this, it will only require iterating for m and n and checking if it meets l length. Below is pseudo code that can provide combinations

for m = 0 to l/s1
for n = 0 to l/s2
bnum = m + n - 1
if (m*s1 + n*s2 + bnum*b) == l)
print m, n, bnum

Answer 2

First of all, look at your construction project differently:

• You must start with a bulkhead.
• Thereafter, each pipe must have a bulkhead after it.

Thus, you need to build a track of length l-b with pipes of length m+b and n+b.

Redistribute the factors, and you'll find that you have an equation in two variables, not 3:

(m+b)*s1 + (n+b)*s2 = l-b

Without loss of generality, assume s2 > s1. Your track will need at least (lower bound) this many pipe segments, enough of the longer one to reach at least the required track length.

ceil( (l-b) / (n+b) )

and no more (upper bound) than

floor( (l-b) / (m+b) )

You can brute-force an iterative solution:

• solve the equation for s2
• iterate s1 across the above range
• for each value of s1, see whether s2 is an integer. If so, record the solution.

This is simple, but inelegant. In actuality, you'll want to use appropriate work on linear Diophantine equations to parameterize all solutions with s1, s2 >= 0.