3
\$\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
  • 12
    \$\begingroup\$ code-golf and fastest-algorithm are conflicting with each other. \$\endgroup\$ 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\$ 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\$ 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\$
3
  • \$\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\$ Jun 5 '18 at 15:51
  • \$\begingroup\$ 159 bytes \$\endgroup\$
    – ceilingcat
    Apr 16 '20 at 3:55
2
+200
\$\begingroup\$

APL (Dyalog Unicode), 30 19 bytesSBCS

{f←*/⍴⍨⋄×(f/⍺)-f/⍵}

Try it online! Thanks to @ngn for saving 11 bytes by defining tetration in a much clever and shorter way:

f ← */⍴⍨   ⍝ Define f to be the tetration function
       ⍨   ⍝ Taking a on the right and b on the left, 
      ⍴    ⍝   creating an array of b occurrences of the number a
    */     ⍝ and then building the tower of exponentials.

Now if I have a vector with two integers, f/ applies the function to those two integers, e.g. f/ 2 4 gives 65536 and f/ 4 2 gives 256. We need this in our main function:

{f←*/⍴⍨⋄×(f/⍺)-f/⍵}  ⍝ Dyadic function (g) expecting two vectors of 2 integers, e.g. 4 2 g 2 4
{f←*/⍴⍨            }  ⍝ Define the auxiliar function as above
{      ⋄           }  ⍝ and then:
{              f/⍵}   ⍝ Apply aux function to the right vector of integers
{        (f/⍺)     }  ⍝ Apply aux function to the left vector of integers
{             -    }  ⍝ Subtract the two values and finally
{       ×          }  ⍝ get the sign of that difference.

This means my function returns 1 if the left integers give a larger value, 0 if they are the same or ¯1 if the left integers give a smaller value.

My original submission had a recursive definition of tetration:

{f←{⍵=1:⍺⋄⍺*⍺∇⍵-1}⋄×(f/⍺)-f/⍵}

with tetration as:

{               }  ⍝ Dyadic function expecting 2 integers
{⍵=1:⍺         }  ⍝ If the right argument is 1, return the left argument;
{      ⋄        }  ⍝ otherwise (separate previous statement from the next one)
{       ⍺*      }  ⍝ Take the left argument to the power of
{         ⍺∇⍵-1}  ⍝ the recursive call of this function with same left argument and decremented right argument.
\$\endgroup\$
12
  • \$\begingroup\$ "Your code should handle a,b,c,d up to 100" \$\endgroup\$
    – ngn
    May 2 '20 at 0:41
  • 1
    \$\begingroup\$ assuming arbitrary precision, tetration can be */⍴⍨ \$\endgroup\$
    – ngn
    May 2 '20 at 1:40
  • 1
    \$\begingroup\$ I thought the challenge was to figure out how to compare \$f(a,b)\$ with \$f(c,d)\$ for input values up to \$100\$, without actually computing those values (since doing the actual computations isn't feasible). I think that's an interesting challenge! (If we were allowed to pretend that we could compute \$f(a,b)\$ and \$f(c,d)\$ so we could then just compare them with an if statement, it wouldn't be very interesting.) \$\endgroup\$ May 2 '20 at 4:06
  • 1
    \$\begingroup\$ @RGS I don't think anybody misinterpreted it -- the challenge was just underspecified. And, actually, Olivier Grégoire's Java solution presumably wins in any case (since this challenge is fastest-algorithm with tie-breakers). \$\endgroup\$ May 2 '20 at 16:06
  • 1
    \$\begingroup\$ In 18.0: ×-⍥(*/¨⍴⍨/) \$\endgroup\$
    – Adám
    May 2 '20 at 23:52
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.