2
\$\begingroup\$

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) cost O(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), takes O(1), with same requirements like integer calculations.
\$\endgroup\$
  • 12
    \$\begingroup\$ code-golf and fastest-algorithm are conflicting with each other. \$\endgroup\$ – Erik the Outgolfer Jun 4 '18 at 14:46
  • 3
    \$\begingroup\$ @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. \$\endgroup\$ – l4m2 Jun 4 '18 at 15:04
  • 3
    \$\begingroup\$ Do any of these rules prevent a lookup table from being used? \$\endgroup\$ – user2699 Jun 4 '18 at 15:53
  • 6
    \$\begingroup\$ @l4m2 I think 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 code-golf challenges, I won't expect to find a challenge with a winning criterion like this one's. \$\endgroup\$ – Erik the Outgolfer Jun 4 '18 at 17:44
  • 2
    \$\begingroup\$ Usually 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. \$\endgroup\$ – Kevin Cruijssen Jun 5 '18 at 7:26
2
\$\begingroup\$

Java (JDK 10), 295 bytes

int f(Long a,long b,long c,long d){return a>c?-f(c,d,a,b):a<c?b>d?d==1?(a==2&((b==2&c==4)|(b==3&c==16)))|(a==3&b==2&c==27)?0:1:b-d>1?1:f(t(a,b),1,c,d):-1:a<2?0:a.signum(b-d);}long t(long a,long b){long t=1;for(;b-->0;)t=p(a,t);return t;}long p(long a,long b){long p=1;for(;b-->0;)p*=a;return p;}

Try it online!

Codes:

  • 1 if a^^b > c^^d
  • -1 if a^^b < c^^d
  • 0 is a^^b == c^^d
\$\endgroup\$
  • \$\begingroup\$ fail on {1,4,2,2}? \$\endgroup\$ – l4m2 Jun 5 '18 at 15:49
  • \$\begingroup\$ I'll fix later today. I must have switched two conditions when golfing. \$\endgroup\$ – Olivier Grégoire Jun 5 '18 at 15:51
1
\$\begingroup\$

Haskell, 46 bytes

a#1=a
a#b=a^a#(b-1)
(a!b)c d=compare(a#b)(c#d)

Prints GT for >, LT for < and EQfor =.

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.