note
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).
<p>
<spoiler>
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.
<p>
More generally, if X1 .. XN are the different kinds of timers you have, the egg-timer numbers you can generate from these are exactly <i>the linear combinations of X1 .. XN</i>. From number theory, we know that this set of numbers is the same as <i>the multiples of GCD(X1 ... XN)</i>.
<p>
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).
<p>
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
<blockquote>
GCD(X1 .. XN) = b1 * X1 + b2 * X2 + ... + bN * XN
</blockquote>
(called Bezout coefficients). Now we're getting closer!
<p>
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
<blockquote>
GCD(4,7) = 1 = 2*4 - 1*7
</blockquote>
So to get 1 minute of time inside a timer, we do the following two steps <i>in parallel</i>:
<ol>
<li>Start two 4-minute timers, one after the next
<li>Start one 7-minute timer
</ol>
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!
<p>
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!
</spoiler>
<p>
In code, it looks like this:
<code>
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 aside.\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));
}
</code>
OK, so this finds <i>terrible</i> 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.
<p>
<b>Update:</b> see [id://547029] for how you can extend this technique and get rid of the infinite # of timers assumption.
<p>
<!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-137386">
<p>
blokhead
</div></div>
547013
547013