2
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,dup 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.
l4m2
Posted 2018-06-04T14:39:14.810
Reputation: 5 985
12[tag:code-golf] and [tag:fastest-algorithm] are conflicting with each other. – Erik the Outgolfer – 2018-06-04T14:46:00.190
3@EriktheOutgolfer
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.– l4m2 – 2018-06-04T15:04:56.3403Do any of these rules prevent a lookup table from being used? – user2699 – 2018-06-04T15:53:52.073
@user2699
and your algorithm should handle all legal input,if k bit computing can be done in O(1)(time, space & code) – l4m2 – 2018-06-04T16:18:12.233Can you clarify how complexity is measured? Your comment mentions time and space, while Big-O notation measures approximate running time, but the description also seems to include individual floating point operations. – user2699 – 2018-06-04T17:40:38.867
6@l4m2 I think [tag:code-challenge] is more applicable than two separate tags here, since those two tags each mean that the criterion they describe is absolutely the only one, and, if I search for [tag:code-golf] challenges, I won't expect to find a challenge with a winning criterion like this one's. – Erik the Outgolfer – 2018-06-04T17:44:20.993
Tetration is actually defined with
a if b=0as the base case, not b=1 as in the challenge. Is this intentional? – hakr14 – 2018-06-04T19:05:42.427@hakr14 The definition in wiki is
1 if b=0, but I don't require handle of zero, so it'sa if b=1– l4m2 – 2018-06-04T22:33:35.653@EriktheOutgolfer I see some posts put all layers of winning criticia as tag and some put only the first, but code-challenge mean the combination of bother affect the rank together, rather than one first and another as tie-breaking – l4m2 – 2018-06-04T22:42:12.447
2Usually a primary win-condition tag is used (
[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. – Kevin Cruijssen – 2018-06-05T07:26:59.943@KevinCruijssen Once an efficient algorithm is found, others might copy it, and it will turn into a [tag:restricted-complexity] [tag:code-golf] – l4m2 – 2018-06-05T07:42:42.160
@l4m2 Tie breakers are in the criterion too, AFAIK. – Erik the Outgolfer – 2018-06-05T10:21:12.770