Boil eggs using hourglasses

Python 2, 157 154 108 103 bytes

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.

JavaScript (ES6), 93 bytes

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


Try it online!

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


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:


which is translated as the following JS code:

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

whose result is implicitly floored.


\$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

Charcoal, 44 bytes


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.


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


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


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


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