|
Limbic~Region has asked for the wisdom of the Perl Monks concerning the following question:
All,
Some egg timers look like a scaled down version of an hour glass. There are a number of puzzles for cooking eggs a specified amount of time where the solution isn't obvious. It requires realizing that by turning over two egg timers at the same time when the smaller has finished you can stop the larger and have 2 new amounts to work with.
For instance, given 7-min & 4-min egg timers, you can split the 7-min into 4/3. You can split the 4-min into 1/3 by turning it over twice in the time the 7-min runs once. Continuing that further you can split the 7-min into 1/6 by letting the 1 minute side of the 4 run.
You get the picture.
The challenge is to create a program that - given a target amount and a variable amount of egg timers, will generate solution(s) for the puzzle. All solutions are welcome but non-straight forward approaches will get creativity bonus points. For those following along at home, adding an explanation in spoiler tags will get you tutelage bonus points.
Update: There are 2 aspects of this puzzle so far that have been interpreted differently. The first is the number of timers. I intended this to be a specific number and not an infinite amount. The second is if timers have to run continously or can be set aside (by turning them on their side). My intention was to allow timers to be stopped for later use. Feel free to intepret the problem any way you want, but these were my intentions.
Update 2: Given an infinite amount of time it may be possible to arrive at any value running timers end to end as it would be by "saving off intermediate values". I don't have proof either way but I suspect some values would only be possible by stopping timers. To force the issue, a nice variation would be to impose an overall time limit for cooking the egg (IOW minimize the overall time). Your choice.
|
Re: Challenge: Egg Timer Puzzles
by GrandFather (Saint) on May 02, 2006 at 23:42 UTC
|
Nice challenge, but a number of sample problems would be good as test cases and to indicate a unified way of providing the problem data.
I guess something like: <target time> <, timer time>+ would be appropriate. So your sample problem could be specified as:
3, 7, 4
with the answer provided as:
begin 7, begin 4
ends 4, begin cooking
ends 7, end cooking (time = 3)
DWIM is Perl's answer to Gödel
| [reply]
[d/l]
[select] |
|
|
| [reply] |
Re: Challenge: Egg Timer Puzzles
by blokhead (Monsignor) on May 03, 2006 at 01:04 UTC
|
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:
- Start two 4-minute timers, one after the next
- 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.
| [reply]
[d/l] |
|
|
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
DWIM is Perl's answer to Gödel
| [reply]
[d/l] |
|
|
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:
| [reply]
[d/l] |
|
|
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.
| [reply] |
|
|
|
|
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 | [reply]
[d/l] |
|
|
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.
| [reply] |
Re: Challenge: Egg Timer Puzzles
by ikegami (Patriarch) on May 03, 2006 at 05:27 UTC
|
Here's a very straightforward version that implements
"given a 7-min timer & a 4-min egg timer"
rather than
"given unlimited 7-min timers & unlimited 4-min egg timers
It's unclear what the OP intended.
use List::Util qw( min );
use List::MoreUtils qw( any );
my $target = 5;
my @max = (7, 4);
my $time = 0;
my @status = (0) x @max;
my %seen;
for (;;) {
die("Unable to solve the problem\n")
if $seen{join('|', @status)}++;
foreach (0..$#status) {
next if $status[$_];
$status[$_] = $max[$_];
print("$time: begin $max[$_]\n");
}
last if any { $_ == $target } @status;
my $elapsed_time = min(@status);
$status[$_] = $status[$_] - $elapsed_time
foreach 0..$#status;
$time += $elapsed_time;
}
print("$time: begin cooking\n");
$time += $target;
print("$time: end cooking\n");
outputs
0: begin 7
0: begin 4
4: begin 4
7: begin 7
8: begin 4
12: begin 4
14: begin 7
16: begin 4
16: begin cooking
21: end cooking
I don't support putting the timer's on hold, but that's just laziness on my end :)
.oO( Why aren't Scalar::Util, List::Util and List::MoreUtils core modules? I wouldn't mind if the function in those modules were core functions! )
| [reply]
[d/l]
[select] |
|
|
ikegami,
It's unclear what the OP intended.
Indeed. I updated the root thread to reflect my intentions though I still want people to be able to intepret the puzzle any way they want. These are fun distractions that I like to post and aren't intended to be right or wrong.
Thanks for your contribution. Compare your solution to my by hand solution for a 20 minute target with 3/5/13/19 egg timers.
3 5 13 19
Step1. 3 & 5 together (elapsed time 3 minutes)
3 2/3 13 19
Step2. 3 & 13 together (elapsed time 6 minutes)
3 2/3 3/10 19
Step3. 10 & 19 together (elapsed time 16 minutes)
3 2/3 13 9/10
Step4. 2 & 9 together (elapsed time 18 minutes)
3 5 13 7/12
Step5. Begin cooking & start 13 (elapsed time 31 minutes)
3 5 13 7/12
Step6. start 7 (elapsed time 38 minutes)
3 5 13 19
Step7. Finish cooking 38 - 18 = 20
Also see where yours fails for 21.
3 5 13 19
Step1 A. Begin cooking & start 19 (elapsed time 19 minutes)
Step1 B. Simultaneously start 3 & 5 (no change to elapsed time)
3 2/3 13 19
Step2. Start 2 (elapsed time 21 minutes)
Step3. Finish cooking
Of course, you could run this end to end where the 3/5 is done first to get to the 2 minutes and then start the 19 but that would exceed 21 minutes. I think a nice variation on this puzzle would be to limit the overall amount of time you have to cook the egg. This might force the "setting aside" intermediate timers while longer timers are running.
| [reply]
[d/l]
[select] |
|
|
Oops, I forgot to mention it was only mean to work for times smaller than the maximum egg timer time (or is it smaller than the minimum eff timer time?) It was just an initial try.
| [reply] |
|
|
