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.