Boil eggs using hourglasses
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.
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
Charcoal, 44 bytes
NθNηNζ⭆⊗×θη⁺⎇﹪ιθω⁺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:
NθNηN
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.