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).
<Reveal this spoiler or all in this thread>
In code, it looks like this:
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.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)); }
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
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^2: Challenge: Egg Timer Puzzles
by GrandFather (Saint) on May 03, 2006 at 01:20 UTC | |
by blokhead (Monsignor) on May 03, 2006 at 01:29 UTC | |
by Limbic~Region (Chancellor) on May 03, 2006 at 12:46 UTC | |
by GrandFather (Saint) on May 03, 2006 at 18:43 UTC | |
by tweetiepooh (Hermit) on May 03, 2006 at 13:49 UTC | |
Re^2: Challenge: Egg Timer Puzzles
by Limbic~Region (Chancellor) on May 03, 2006 at 12:33 UTC |
In Section
Seekers of Perl Wisdom