Define f(a,b) := a if b=1; a^f(a,b-1) if b>1
(Tetration, where ^
means power) for positive integers a
and b
, given four positive integers a,b,c,d
, compare f(a,b)
and f(c,d)
.
Your program should output three constant values to mean "greater", "less" and "equal".
Samples:
a b c d f(a,b) output f(c,d)
3 2 2 3 27 > 16
4 2 2 4 256 < 65536
4 1 2 2 4 = 4
Lowest time complexity to max{a,b,c,d}
win, with tie-breaker code length(the shorter the better) and then answer time(the earlier the better).
Complexity assumption
- Your code should handle
a,b,c,d
up to 100, and your algorithm should handle all legal input - You can assume integer calculations (that your language directly support) in
O((a+b+c+d)^k)
costO(1)
time if can be done in O(1) for 2k bit numbers if k bit computing can be done in O(1) - For example, both plus(
+
) and multiply(*
) can be done in O(1) for 2k bit numbers if k bit computing for both can be done in O(1), so both satisy the requirement. It's fine if multiply can't be done without plus, or even if both can't be done without each other. - Float calculations in
O(log(a+b+c+d))
bit precision in±2^O((a+b+c+d)^k)
, takesO(1)
, with same requirements like integer calculations.
Fastest-algorithm challenges often result in ties, because the number of different complexities if often rather limited for certain problems, and once an optimal solution has been found there is a good chance others will be posted. For these cases, a tie-breaker should always be specified. Common choices are earliest answer, shortest code-length of the given implementation or shortest actual runtime on a given problem set.
\$\endgroup\$[fastest-algorithm]
in this case), and the challenge itself states what to do on tie-breakers without an additional tag. I definitely understand why you've added the[code-golf]
tag as tie-breaker. Once an efficient algorithm is found, others might copy it, or the amount of algorithms to be used is limited from the beginning maybe. But as mentioned by @EriktheOutgolfer, when I search for code-golf challenges, I wouldn't expect these kind of challenges to pop up. \$\endgroup\$