Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Challenge: Egg Timer Puzzles

by Limbic~Region (Chancellor)
on May 02, 2006 at 23:13 UTC ( #547013=perlquestion: print w/ replies, xml ) Need Help??
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.

Cheers - L~R

Comment on Challenge: Egg Timer Puzzles
Re: Challenge: Egg Timer Puzzles
by GrandFather (Cardinal) 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
      GrandFather,
      Good point - thanks. In this particular case I don't see much harm in letting contributors interpret things as they want to as it is just a fun exercise in learning but some uniformity is always a good thing.

      Let this serve as a guideline for anyone seeking one.

      Cheers - L~R

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

    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

      You can't "set aside" a timer and you have only one of each timer specified. So for the chosen problem (5, 7, 4) a solution is:

      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
        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:

        1. Run the 4-minute timer, 10 times in a row
        2. At the same time, run the 7-minute timer, 5 times in a row
        3. 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).
        4. 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:

        blokhead

        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.

        Cheers - L~R

        Another solution

        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

      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.

      Cheers - L~R

Re: Challenge: Egg Timer Puzzles
by ikegami (Pope) 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! )

      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.

      Cheers - L~R

        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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://547013]
Approved by kvale
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others examining the Monastery: (13)
As of 2014-09-30 15:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (375 votes), past polls