Algorithm for rope burning

Question

Generalized from a technical interview question:

Original question: There are two ropes, each rope takes 1 hour to burn. But either rope has different densities at different points, so there’s no guarantee of consistency in the time it takes different sections within the rope to burn.

How do you use these two ropes to measure 45 minutes?

I have a generalized version:

There are n ropes, each rope takes x minutes to burn (for simplicity assume x is positive integer). But the ropes have different densities at different points, so there’s no guarantee of consistency in the time it takes different sections within the ropes to burn.

Using these n ropes, what time quantity can you measure?

For example, with n = 1 and x = 60, I can measure 60 minute period (burning one end of the rope), or 30 minute period (burning both ends of the rope at the same time)

Of course my aim would be finding an algorithm with minimal complexity. I imagine the solution to this would involve dynamic programming, but I am not quite sure. My brute force solution is as followed:

1. Start at minute 0, we have n ropes, each takes x minutes to burn. For a given rope, we have choices either to burn both ends, one end, or not burning the rope at all. Let number of ropes that will not be burnt at this stage be x, number of ropes that will be burnt one end be y, and number of ropes that will not be burnt at all be z. We have x + y + z = n and that x,y,z are positive integers and z != 0. Consider all possible cases for x, y and z and add those cases to a stack/queue.
2. For each item in the stack/queue, determine how many minutes have passed when there is a rope finishes burning. Output the time that has passed (calculated based on how long the finished rope has burnt, and which ends were burnt at what time). Now we have another scenarios with certain amount of ropes that are being burnt. Repeat the step 1 argument with x + y + z = n - 1 (with constraints imposed on x, y, and z since some ropes are still burning and we cannot set the fire off) and add all the newly generated cases to the stack/queue.
3. Repeat 2. until n = 0 (All ropes finished burning)

Edit: For n = 2 and x = 60, I've found that the following time period can be measured: 30, 60, 90, 120, 45 and 15.

As suggested, I posted the question on cs.stackexchange.com: https://cs.stackexchange.com/questions/32455/algorithm-for-rope-burning-problem

Answer 1

Well, here is my attempt to solve the problem with greater efficiency. I might have overlooked something, so be wary even if it seems to make sense.

We can start with a base state of 1 rope yields x minutes or x/2 minutes. Now, suppose it is possible to measure x_prev minutes with n ropes. Then, consider what happens if we add the n+1th rope. We can

1. Wait for the whole x_prev minutes to expire, then burn the next rope from 1 end. This means we can achieve x_prev + x minutes.
2. Wait for the whole x_prev minutes to expire, then burn the next rope from 2 ends. This means we can achieve x_prev + x/2 minutes.
3. Start burning the x_prev minutes as we burn the next rope from 1 end. This means we can achieve abs( x - x_prev ) minutes.
4. Start burning the x_prev minutes as we burn the next rope from 2 ends. This means we can achieve abs( x/2 - x_prev) minutes.

We do not care about a time t that was achieved with m with m<=n-1 ropes because we would have considered these four cases when we were adding the m+1-th rope.

These seem like the only four cases. So, in pseudocode, perhaps something like this

let solutions be a list of measurable times
def solve( n , x ):
    if n <= 0
         return, you cannot measure any times
    else
         #set up base case n=1
         append x/2 and x to solutions

         #we can be efficient by only checking the times achievable with n-1 ropes
         #we will store the index of the first time that was recorded with n-1 ropes
         #in start_idx
         let start_idx be an index in the solutions array

         #assume the array indices start at 0. then start_idx is the index
         #of the first recorded time measurable with 1 rope.
         start_idx = 0

         #then continuously add additional ropes until we have n ropes
         for i in 2..n

              let solutions_to_add be a list

              for j in start_idx..solutions.size() - 1
                   if solutions does not contain time+x
                        append time+x to solutions_to_add
                   if solutions does not contain time+x/2
                        append time+x/2 to solutions_to_add
                   if solutions does not contain abs( x-time )
                        append abs( x-time ) to solutions_to_add
                   if solutions does not contain abs( x/2-time )
                        append abs( x/2-time ) to solutions_to_add

              #update the start_idx to be the starting index of times achievable with
              #i ropes
              start_idx = solutions.size()

              #then add the achievable times with i ropes
              for each time in solutions_to_add
                   append time to solutions

You can probably get O(1) run time for solution contains by using a boolean array for lookup. The overall algorithm seems to be O(n^2).

Is it correct? I'm not really sure if my four cases cover everything. I am pretty sure the induction-like process is correct.