Re: Challenge: Egg Timer Puzzles

[blokhead]

My assumptions: We have an unlimited supply of timers in each available time amount. We can flip two timers simultaneously (don't need to be able to flip more simultaneously for the solutions this produces).

Generalizing from your examples, it doesn't take long to see that you can only make "new" egg-timer numbers by adding or subtracting existing egg-timer numbers. So the set of egg-timer numbers are all the numbers that can be written as a sum 7a+4b for integers a & b.

More generally, if X1 .. XN are the different kinds of timers you have, the egg-timer numbers you can generate from these are exactly the linear combinations of X1 .. XN. From number theory, we know that this set of numbers is the same as the multiples of GCD(X1 ... XN).

So once we know how to put exactly GCD minutes on a timer, we can time any valid egg-timer number by first generating a bunch of these GCD timers, and then running them successively many times in a row (the target number is just a multiple of this GCD).

Now all that's left is to figure out how to get GCD minutes on a timer. Fortunately, number theory can help us again! The standard algorithm for computing the GCD can also be augmented to give integers b1 .. bN such that

GCD(X1 .. XN) = b1 * X1 + b2 * X2 + ... + bN * XN

(called Bezout coefficients). Now we're getting closer!

How do we get from these coefficients back to the egg-timer problem at hand? Let's look at an example: For egg timers of 7 and 4 minutes, we have

GCD(4,7) = 1 = 2*4 - 1*7

So to get 1 minute of time inside a timer, we do the following two steps in parallel:

1. Start two 4-minute timers, one after the next
2. Start one 7-minute timer

Now, step #2 is going to finish sooner than step #1. If we stop the last timer in step #1 at the moment step #2 finishes, there will be 1 minute left over in the last timer. That's it!

More generally, we can split the X's up into those which have positive and negative Bezout coefficients. Start the appropriate number of timers for each group, one after the other (but the two groups in parallel). The negative-coefficient group will finish earlier, in fact, there will be exactly GCD minutes left on the last timer. Since the GCD is never bigger than any of the X's, these GCD minutes of time will always fit on the last timer, no matter which order we start them in. We set aside this last timer, and make as many GCD-timers as we want!

In code, it looks like this:

my @TIMERS = qw[ 4 7 ];
my $TARGET = shift || 5;

my ($gcd, @c) = bezout(@TIMERS);
die "$TARGET is not egg-timer-able!" if $TARGET % $gcd;

my $iter = $TARGET / $gcd;
my @pos = grep { $c[$_] > 0 } 0 .. $#c;
my @neg = grep { $c[$_] < 0 } 0 .. $#c;
@c = map abs, @c;

printf qq[
Perform steps 1 & 2 in parallel:

Step 1: One after the other, start the following timers:
%s

Step 2: One after the other, start the following timers:
%s

Step 2 will finish exactly $gcd minutes before step 2, so when it
finishes, set aside the remaining $gcd minutes on the last timer.
],
join("\n", map "  $c[$_] of the $TIMERS[$_]-minute timers", @pos),
join("\n", map "  $c[$_] of the $TIMERS[$_]-minute timers", @neg);

print "\nRepeat the whole thing $iter times to $TARGET minutes set asi
+de.\n"
   if $iter > 1;

sub bezout {
    if ( @_ > 2 ) {
        my ($g1, @c1) = bezout( @_[0,1] );
        my ($g2, @c2) = bezout( $g1, @_[2..$#_] );

        return ( $g2, (map { $c2[0]*$_ } @c1), @c2[1 .. $#c2] );
    }

    my ($x, $y) = @_;
    return ($y,0,1) if $x % $y == 0;

    my ($g, $s, $t) = bezout( $y, $x % $y );
    return ($g, $t, $s - $t * int($x/$y));
}

OK, so this finds terrible solutions for most numbers, if you'd actually have to do these things with the timers. But they are solutions nonetheless, and you didn't really say anything about optimality of solutions. Anyway, this method has its own intrinsic beauty from the application of number theory.

Update: see Re^3: Challenge: Egg Timer Puzzles for how you can extend this technique and get rid of the infinite # of timers assumption.

[GrandFather]

You can't "set aside" a timer and you have only one of each timer specified. So for the chosen problem (5, 7, 4) a solution is:

begin 7, begin 4
ends 4, begin 4
ends 7, begin 7
ends 4, begin 4
ends 4, begin 4
ends 7, begin 7
ends 4, begin cooking
ends 7, end cooking (time = 5)

Cooking time = 7 * 3 - 4 * 4

[blokhead]

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:

1. Run the 4-minute timer, 10 times in a row
2. At the same time, run the 7-minute timer, 5 times in a row
3. 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).
4. 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:

Read more... (6 kB)

[Limbic~Region]

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.

[GrandFather]

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.

[tweetiepooh]

Another solution

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

[Limbic~Region]

blokhead,
GrandFather is right on one account, you only have the specified number of timers in each amount. While you can re-use the same timer, you are restricted to whatever state it is in when you use it.

For instance, if you have the 7 minute timer in the root thread split at 6/1, you don't have another 7 minute timer available to use.

GrandFather's second argument is incorrect though. You do not need to run the timers continously once they have been started - they can be turned on their sides for later use. This doesn't matter at all when you only have 2 timers but it would make a difference with more timers.

This of course is just a fun puzzle so people can solve it either way. Your solution with an invalid assumption is fine too. That link you sent me last night is up again so I am checking it out as well as reading your solution.