# 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

```
ＮθＮηＮζ⭆⊗×θη⁺⎇﹪ιθω⁺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.