in reply to
Re^2: Challenge: Egg Timer Puzzles
in thread Challenge: Egg Timer Puzzles
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:
#!/usr/bin/perl
use List::Util qw[ max min ];
use strict;
my ($TARGET, @TIMERS) = @ARGV ? @ARGV : (10, 4, 7);
print "Can you get $TARGET minutes using only {@TIMERS}-minute timers?
+\n";
my ($GCD, @c) = bezout(@TIMERS);
die "$TARGET is not egg-timer-able!" if $TARGET % $GCD;
my $max_timer = max @TIMERS;
my $remainder = $TARGET % $max_timer;
my $scale = $remainder / $GCD;
## start a queue of timer jobs to be run, by the left hand and right h
+and.
## a timer "job" is [a,b] where a is the capacity of the timer, and b
+will
## reduce as the timer is going to show how much time is left on that
+timer
my (@left, @right);
for my $t (0 .. $#TIMERS) {
if ($c[$t] > 0) {
push @left, [ $TIMERS[$t], $TIMERS[$t] ]
for 1 .. $scale * $c[$t];
} elsif ($c[$t] < 0) {
push @right, [ $TIMERS[$t], $TIMERS[$t] ]
for 1 .. $scale * abs $c[$t];
}
}
print ">> GOAL: get ${remainder}min onto the ${max_timer}min timer.\n"
+;
print ">> Then the rest of the time (@{[ $TARGET-$remainder ]}min) is
+a multiple of ${max_timer}min.\n";
my $T = 0;
if ($remainder) {
print "At time 0:\n";
print " - Start $left[0][0]min timer.\n";
print " - Start $right[0][0]min timer.\n";
}
while (@left and @right) {
my $tick = min( $left[0][1], $right[0][1] );
$T += $tick;
print "At time $T:\n";
for my $active (\@left, \@right) {
$active->[0][1] -= $tick;
if ($active->[0][1] == 0) {
print " - $active->[0][0]min timer expires.\n";
shift @$active;
print " - Start $active->[0][0]min timer.\n"
if @$active;
} else {
print " - $active->[0][0]min has $active->[0][1]min remain
+ing.\n";
}
}
}
## left hand will still have timers pending in the queue if we needed
## $remainder
if ($remainder and $left[0][0] != $max_timer) {
print ">> NOW READY TO LOAD UP ${max_timer}min TIMER WITH ${remain
+der}min.\n";
print " - Start ${max_timer}min timer.\n";
my $loaded = 0;
while (@left) {
$T += $left[0][1];
$loaded += $left[0][1];
print "At time $T:\n";
print " - $left[0][0]min timer expires.\n";
print " - ${max_timer}min timer has @{[ $max_timer-$loaded ]}m
+in remaining.\n";
shift @left;
print " - Start $left[0][0]min timer.\n"
if @left;
}
} else {
print ">> ${max_timer}min TIMER ALREADY LOADED UP WITH ${remainder
+}min.\n";
}
print ">> NOW START TIMING!\n";
print " - Flip ${max_timer}min timer: was @{[ $max_timer-$remainder ]}
+min remaining, now ${remainder}min remaining.\n"
if $remainder;
$T += $remainder;
print "At time $T:\n";
print " - ${max_timer}min timer expires.\n"
if $remainder;
for (1 .. int($TARGET/$max_timer)) {
print " - Start ${max_timer}min timer.\n";
$T += $max_timer;
print "At time $T:\n";
print " - ${max_timer}min timer expires.\n";
}
print ">> STOP TIMING!\n";
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));
}
And just a refresher... We want to get TARGET minutes out of @TIMERS
- We're going to use the largest timer (MAX_TIMER) to eat up as much of TARGET as we can, but before we rattle off MAX_TIMER a bunch of times in a row...
- Whatever time is left (REMAINDER = TARGET % MAX_TIMER) we need to get on the MAX_TIMER first.
- The remainder must be a multiple of the GCD, so we can multiply the Bezout equation from above by GCD/REMAINDER, group the positive and negative terms together to get:
REMAINDER = (some positive combination of timers) - (some positive combination of the other timers)
Call the first combination of timers the LEFT ones and the other ones the RIGHT ones. If we rattle off these two lists of timers in parallel, this says that the RIGHT ones will finish REMAINDER minutes before the LEFT. That's essentially how we get REMAINDER minutes onto MAX_TIMER.