Boil eggs using hourglasses

Question

These are the classical puzzles:

You need to boil eggs for exactly 9 minutes, or else the visiting Duchess will complain, and you will lose your job as head chef.

But you have only 2 Hourglasses, one measures 7 minutes, and the other measures 4 minutes. How can you correctly measure 9 minutes?

(taken from here)

Let's write a program which will produce a solution for any such puzzle.

Input: 3 numbers a, b, x

Here a and b are the durations of the hourglasses, and x is the required time for boiling the eggs. Let's assume the following:

• 0 < a < b (without loss of generality)
• x is not divisible by a or b (to make the problem non-trivial)
• x > 0
• x is divisible by gcd(a, b) (to ensure a solution exists)

Output: a string which contains commands, such that after executing the commands, we get our eggs boiled for exactly x minutes.

The possible commands are:

• 'A' - turn hourglass A
• 'B' - turn hourglass B
• 'a' - wait until hourglass A runs out
• 'b' - wait until hourglass B runs out
• 's' - start boiling the eggs

You may use any single non-whitespace character to encode each command.

You may also use longer strings to encode commands, but then the string of commands must contain separators between each pair of commands.

You may also add a special command "stop boiling the eggs" if it makes implementation easier (naturally, you cannot restart the boiling - the "stop" command is for the case your algorithm cannot restrain itself from printing additional commands after it prints the solution).

You don't need to optimize your string of commands: it may use an inefficient algorithm or contain unnecessary commands, as long as the result is correct.

Test cases:

3, 5, 1 => ABaAbBsa
4, 7, 9 => ABaAbBsaAaAa
7, 11, 15 => ABaAsbBb
69, 105, 42 => ABaAbBaAaAbBaAbBaAaAbBaAsb
60, 256, 2020 => ABaAaAaAaAbBaAaAaAaAbBaAsaAaAaAbBaAaAaAaAaAbBaAaAaAaAbBaAaAaAaAbBaAaAaAaAbBaAaAaAaAaAbBaAaAaAaAbBb

Note: these solutions were generated by a script, so they contain completely unnecessary commands.

Answer 1

Python 2, 157 154 108 103 bytes

a,b,c=input()
t=c
while t%a:t+=b
print"".join("aA"[i%a*2:]+"bB"[i%b*2:]+"s"[i^t-c:]for i in range(t+1))

Try it online! or Check all test cases!

Input: from STDIN, 3 positive integers a,b,c representing the 2 hourglass times and the time needed for the egg to boil.
Output: print to STDOUT a string of commands following the specification.

Big idea

There exists positive integers \$x,y\$ such that: $$ax-by=c$$ (Proof in the last section)

Thus, if we continuously flip both hourglasses, the time between when the second hourglass finishes \$y\$ flips and when the first hourglass finishes \$x\$ flips is exactly equal to the time needed to boil the egg.

Code overview

t keeps track of \$by+c\$. We increment \$y\$ until \$\frac{by+c}{a}\$ is an integer. When a valid value of t is found, t will be the time needed to flip the first hourglass \$x\$ times, and also the time when the egg should be done. t-c is the time when the second hourglass finishes \$y\$ flips, and also the time when the egg should start to be boiled.

The command string is created by increasing the time i, and insert "aA" or "bB" every time \$a\$ or \$b\$ divides the current time. "s" is inserted when the time is t-c.

Proof of the existence of \$x\$ and \$y\$.

Since \$c\$ is a multiple of \$gcd(a,b)\$, Bézout's identity claims that there exists integers \$k_1, k_2\$ (which can be negative) such that: $$k_1a-k_2b=c$$ Since \$ba - ab = 0\$, we can increase \$k_1\$ and \$k_2\$ by \$b\$ and \$a\$ without changing the result: $$(k_1+b)a-(k_2+a)b=c$$ Thus, we can keep increasing \$k_1\$ and \$k_2\$ until they are both positive.

Answer 2

JavaScript (ES6), 93 bytes

Takes input as (a)(b)(x).

A=>(B,k=0)=>g=X=>(k+X)%A?"bB"+(h=n=>"aA".repeat(n+1))(-~~(~-k/A+1)+(k+=B)/A)+g(X):"bs"+h(X/A)

Try it online!

or Check the results online! with @SurculoseSputum's script

How?

The algorithm used requires to count the number of multiples of \$A\$ between \$k\$ (a multiple of \$B\$) and \$k+B\$ (included). This is done with the following formula:

$$\left\lfloor\frac{k+B}{A}\right\rfloor-\left\lceil\frac{k}{A}\right\rceil+1$$

which is translated as the following JS code:

(k + B) / A - ~~(~-k / A + 1) + 1

whose result is implicitly floored.

Commented

\$h\$ is a helper function that repeats "aA" \$n+1\$ times:

h = n => "aA".repeat(n + 1)

Main function:

A =>                     // A = duration of hourglass A
(B, k = 0) =>            // B = duration of hourglass B; k = counter
g = X =>                 // g is a recursive function taking the boiling time X
  (k + X) % A ?          // if k + X is not a multiple of A:
    "bB" +               //   append "bB"
    h(                   //   repeat "aA" as many times as there are ...
      -~~(~-k / A + 1) + //     ... multiples of A between k and k + B (included),
      (k += B) / A       //     using the formula described above
    ) +                  //     
    g(X)                 //   append the result of a recursive call
  :                      // else:
    "bs" +               //   append "bs"
    h(X / A)             //   repeat "aA" floor(X / A) + 1 times

Answer 3

05AB1E, 29 bytes

∞*.Δ³-²Ö}©ƒN¹Ö₃*N²Ö₂*®³-NQJ0K

Port of @SurculoseSputum's Python answer, so make sure to upvote him!!

Takes the inputs in the same order as the challenge description: a,b,x.
Outputs 95261 instead of aAbBs respectively.

Try it online or verify all test cases or verify the results with the Python script.

Explanation:

∞           # Push an infinite positive list: [1,2,3,...]
 *          # Multiply each by the (implicit) input `a`: [a,2a,3a,...]
  .Δ        # Get the first item in this list which is truthy for:
    ³-      #  Subtract the third input `x`
      ²Ö    #  And check if it's divisible by the second input `b`
  }©        # After we've found our value: store it in variable `®` (without popping)
    ƒ       # Loop `N` in the range [0, `®`]:
     N¹Ö    #  Check if `N` is divisible by the first input `a`
        ₃*  #  Multiply this by 95 (so 95 if truthy; 0 if falsey)
     N²Ö    #  Check if `N` is divisible by the second input `b`
        ₂*  #  Multiply this by 26 (so 26 if truthy; 0 if falsey)
     ®³-NQ  #  Check if `®` minus the third input `x` is equals to `N`
            #  (1 if truthy; 0 if falsey)
     J      #  Join all values on the stack together
      0K    #  And remove all 0s
            # (after the loop, the result is output implicitly)

Answer 4

Charcoal, 44 bytes

ＮθＮηＮζ⭆⊗×θη⁺⎇﹪ιθω⁺aA⎇﹪⁺ιζηωs⎇﹪ιηω⁺bB⎇﹪⁻ιζθωS

Try it online! Link is to verbose version of code. Uses S to stop boiling, so the actual boiling time is from the first s to the first S after the first s. Explanation:

ＮθＮηＮ

Input a, b and x.

ζ⭆⊗×θη⁺

Loop from 0 to 2ab.

⎇﹪ιθω⁺aA

If this is a multiple of a then stop and start the a hourglass.

⎇﹪⁺ιζηωs

In addition if this plus x is a multiple of b then start boiling.

⎇﹪ιηω⁺bB

If this is a multiple of b then stop and start the b hourglass.

⎇﹪⁻ιζθωS

In addition if this minus x was a multiple of a then stop boiling.

Answer 5

Python 3.7, 158 bytes

I'm very new to this, so if there's some convention on explanations/proofs that should be included please helpfully point me in the right direction.

My Solution:

1.) Not including 's', there is only one move that can be done without returning to a previous point. Wait for a timer to run out if both are running, or if a timer is empty flip that timer. Since timer 'a' is shorter than 'b', you start both, keep flipping 'a' until 'b' runs out, keep flipping 'b' until 'a' runs out (only once), and repeat this cycle indefinitely. It will of course return eventually to a previous position, but if a solution exists it will be found first.

2.) Keeping track of the time left on 'a' when 'b' runs out, you see that it is always some number 'd' less than or equal to 'a'. If a solution exists, eventually the time to cook the egg is a multiple 'n' of 'a' plus or minus 'd'.

3.) If the time to cook is 'n' x 'a' + 'd', start the egg, continue cycling 'a' until the egg is done. If the time to cook is 'n' x 'a' - 'd', start the egg, flip 'a' so it runs backwards 'd' minutes, and continue cycling 'a' until the egg is done.

My Code:

a,b,c=3,5,1
d,i,j,k=a,2,'AB','Aa'
while i:
 i+=1;d,j=((b-d)%a,j+k*((b-d)//a+1)) if i%2 else (a-d,j+'bB')
 if c%a==d:j+='s'+'A'*(i%2)+'a'+k*(c//a);i=0;print(j)

Try it online

Answer 6

Java 8, 115 bytes

(a,b,c)->{int t=c,i=0;for(;t%a>0;)t+=b;for(;i<=t;)System.out.print((i%a<1?"aA":"")+(i%b<1?89:"")+(i++==t-c?1:""));}

Port of @SurculoseSputum's Python answer, so make sure to upvote him!!

Outputs 891 instead of bBs respectively.

Try it online or verify the results with the Python script.