I thought we were allowed to freely interpret the problem. Anyway, I've added my assumptions to the top of my post to avoid confusion. Will try to look at a solution for your formulation later..
Update: After sleeping on it, I've realized that the same thing can still be done with just one timer of each size. In the example above, in steps 1 & 2, you only need one timer of each size. Since you are just setting off timers one after the next, if you need to run two of the same-sized timer, you can just flip the same timer after it's done. So you can always get GCD minutes into a timer, even if you have just one timer available in each size.
And extending that, here's how you can get K minutes into any single target timer T (as long as K minutes can fit in timer T and K is a multiple of the GCD). Take the Bezout equation above, multiply both sides by K/GCD to get:
K = b1 * X1 + ... + bN * XN
Then run the algorithm outlined above to get K minutes. But there's a difference -- this time when step 2 finishes, we'll have K minutes left over, but it may not fit inside the last timer in step 1 (that is, step 1 may have several pending timers left to run). There are two cases:
Case 1: Timer T is unused at the end (i.e, it is not one of the timers that still needs to finish in step 1 when step 2 finishes). In particular, this means that timer T is empty/full. Now, when step 2 finishes, there is possibly some timer in step 1 still running (paused) and possibly some other ones queued up in step 1. The total remaining amount is our desired number K. But since the timer T is freely available and empty/full (and K minutes can fit in this timer), we can just fill up timer T with the K minutes by letting the step 1 timers complete.
Case 2: Timer T still needs to finish in step 1 when step 2 finishes. But since we assumed that K minutes fits on timer T, then it must be the only timer not finished. So it must have K minutes left when step 1 ends, and we're done!
In our example with a 7- and 4-minute timer, here's how to get 5 on the big timer: My bezout equation is 1=2*4-7. I multiply it by 5 to get 5=10*4-5*7. This means I do the following:
- Run the 4-minute timer, 10 times in a row
- At the same time, run the 7-minute timer, 5 times in a row
- When the fifth 7-minute timer stops, there is 1 minute left on the currently running 4-minute timer (and we would have flipped it over again to get the 5 minutes).
- Transfer that 1 minute to the 7-minute timer. Then transfer 4 more minutes to it, using the (emptied) 4-minute timer.
In this way, we can realize any amount, in contiguous time! If we want 10 minutes for example, we use this method to get 3 minutes in the small timer. We can start it off, and then run the 7-minute timer when its finished to get 10 minutes total (the 7-minute timer is already in its empty/full state).
More generally, I claim that you will never need more than one partially-filled timer to realize an amount (why? because you can freely "shuffle around" time between timers in increments of GCD until all but one is full). So first, using all timers, fill some timer to the required partially-full amount (using the method above), set it off and when it finishes, all the timers will be in empty/full states and the remaining time can be realized from whole multiples of these empty/full timers.
Again, this is still possibly inefficient in terms of the number of steps needed (or total amount of "setup" time before starting to cook). Perhaps someone can improve on it. It's also a little complicated to express this in code (heck, it's complicated to write up), but I'll see if I can augment my code later today.
Update: (2006-10-25) added some proof-of-concept code by request:
| [reply]
[d/l] |
GrandFather,
You can't "set aside" a timer and you have only one of each timer specified.
Well, you are 1 for 2. You only have the specified number of timers at their respective times. I did say in the root thread that you can stop a timer with 2 new amounts. This could result by turning it on its side. It doesn't matter if you only have 2 timers but if you have more than it could come into play.
I don't mind that you ignored this though. It is just a fun puzzle that I left open to interpretation. I have not yet tackled it myself as I was interested to seeing approaches others took. I need to remember to post these things at the beginning of the day and not the end of the day though - more visibility.
| [reply] |
My appology. The formulation of the puzzle I am familiar with (as a brain teaser) is that you can flip the timers, but not stop them. I also suspect that the result is the same at the end of the (possibly long) day, but I'm not mathematician enough to prove it.
DWIM is Perl's answer to Gödel
| [reply] |
begin 7, begin 4
turn 4
end 7 start cooking = 0 min
turn 4 = 1 min
end 4 = 5 min
Cooking time = 4*3-7
Since 2*4-7 is 1 you should be able to get any timing | [reply]
[d/l] |
