http://www.perlmonks.org?node_id=547026


in reply to Challenge: Egg Timer Puzzles

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).

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.

blokhead