11
\$\begingroup\$

I do realise that this is a bit math-y, but - here goes.

In mathematics, the hyperoperation sequence is an infinite sequence of arithmetic operations (called hyperoperations) that starts with the unary operation of successor, then continues with the binary operations of addition, multiplication and exponentiation, after which the sequence proceeds with further binary operations extending beyond exponentiation, using right- associativity.

Your goal is to write a program that takes three integers x, y and n as input and outputs the result of the nth hyperoperation on x and y.

E.g.

1 1 1 outputs 2

2 4 4 outputs 65536

3 3 4 outputs 7625597484987

  • The program must be written in the shortest bit of code.
  • You may take input either from STDIN or from a file.
  • Library functions not allowed.
  • Input constraints: n will be ≥ 1.

http://en.wikipedia.org/wiki/Tetration has a good explanation in case you can't wrap your head around this.

\$\endgroup\$
  • \$\begingroup\$ What is n=1? If it's x+y or x+1, 1 1 1 should return 2 \$\endgroup\$ – John Dvorak Apr 27 '13 at 15:12
  • \$\begingroup\$ I knew I had made a mistake somewhere :) fixed, thx. \$\endgroup\$ – Soham Chowdhury Apr 27 '13 at 15:13
  • 1
    \$\begingroup\$ I've written me a pseudo-code, then I realised that it's actually a valid Ruby code (almost :-( ) \$\endgroup\$ – John Dvorak Apr 27 '13 at 15:25
  • 1
    \$\begingroup\$ No, n >= 1 only. \$\endgroup\$ – Soham Chowdhury Apr 27 '13 at 15:38
  • 1
    \$\begingroup\$ related Implement hyperexponentiation/tetration without the use of '^' \$\endgroup\$ – Howard Apr 27 '13 at 16:03
4
\$\begingroup\$

Ruby, slow, 86 84 83 characters

def f x,y,n
n>1?(c=x;2.upto(y){c=f(x,c,n-1)};c):x+y
end
p f *gets.split.map(&:to_i)

Ruby, fast, 96 94 93 characters

def f x,y,n
n>1?(n>2?(c=x;2.upto(y){c=f(x,c,n-1)};c):x*y):x+y
end
p f *gets.split.map(&:to_i)

The first version is way too slow with the last test case, so I added a version that uses multiplication as the base case instead of addition. The first version takes ages to calculate 3 3 4; the second one is instanteneous (in the native IRB console; the web version is a bit slower).

Several beauties of Ruby show up here:

Almost every statement is an expression in ruby. Thus, you can stuff semicolons inside the ternary operator, provided you've got enough parentheses lying around. Coffeescript borrowed that one. It also borrowed Ruby's "no parens needed" call syntax.

Implicit returns: this is a cool feature, and follows from the previous. Indeed, starting the last line of a function with return is considered lame, even when not golfing.

Numbers are objects in ruby (even null is an object). In ruby, integers have the method times, which executes the block passed to it several times. This is just one of Ruby's many iterator methods. Here, the upto method lets us save two more characters over what times lets us.

unary * is the splat operator here. It turns an array into an argument list. Just like Javascript's Function#apply, but it's shorter and better.

unary & turns a procedure into a block. While :to_i is a symbol, it converts into a procedure pretty well. Namely, it turns into a procedure that calls to_i on its argument and returns the result. More information on Stack Overflow.

It would be possible to get it even faster by using n=3 as the base case, but I'm afraid it is not needed. It would only cost 11 characters, though, thanks to another beauty of ruby: the exponentiation operator **. Python has this operator, but it's not the first one (as @aka.nice noted - thanks -, Fortran already had this operator).

online ruby interpreter available here: http://repl.it/Ikj/1

\$\endgroup\$
  • \$\begingroup\$ Nice, but I'm still waiting for an output from 3 3 4 :) it's very slow. \$\endgroup\$ – Soham Chowdhury Apr 27 '13 at 16:47
  • \$\begingroup\$ @SohamChowdhury the base case is addition. With a base case of multiplication, it would be very slow as well (and longer). I recommend testing with exponentiation instead ;-) \$\endgroup\$ – John Dvorak Apr 27 '13 at 16:49
  • \$\begingroup\$ It might save time to use memoization, but that would cost some bytes (quite a few) \$\endgroup\$ – John Dvorak Apr 27 '13 at 16:52
  • \$\begingroup\$ Add another version then :) \$\endgroup\$ – Soham Chowdhury Apr 27 '13 at 17:15
  • 1
    \$\begingroup\$ operator ** already existed in FORTRAN in the 50's and ALGOL would have 1 character less with up arrow \$\endgroup\$ – aka.nice Apr 29 '13 at 21:24
6
\$\begingroup\$

APL, 62

{1=3⌷⍵:2⌷+\⍵⋄0=2⌷⍵:(⍵[3]⌊3)⌷⍵[1],0,1⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1}⎕

{...}⎕: Takes evaluated input (space-separated numbers evaluates to a numerical array) and apply function to it.

1=3⌷⍵:: If n equals 1...
2⌷+\⍵: Return sum of first 2 elements (x+y)...
⋄0=2⌷⍵:: Else if y equals 0...
(⍵[3]⌊3)⌷⍵[1],0,1: Create numerical array [x,0,1] and return index min(n,3)...
⋄∇⍵[1],(∇⍵-0 1 0),3⌷⍵-1: Else return ∇(x,∇(x,y-1,n),n-1). (∇ is self-reference)


I have got a "hyper-raiser" operator, which takes a function and return next hyperoperation

{⍺⍺/⊃⍴/⌽⍵}

For example, +{⍺⍺/⊃⍴/⌽⍵} would be the multiplication function and +{⍺⍺/⊃⍴/⌽⍵}5 3 outputs 15.

But can't get it to recurse. Maybe someone else can do it.

\$\endgroup\$
  • \$\begingroup\$ Ah, APL. Beats Python for simplicity any day. </sarcasm> How do I run this? \$\endgroup\$ – Soham Chowdhury Apr 30 '13 at 11:29
2
\$\begingroup\$

Python, 83

(Based on flornquake's answer)

def h(x,y,n):r=n>2;exec"r=h(x,r,n-1);"*y*(n>1);return(x+y,r)[n>1]
print h(*input())

Very slow for large results.

For 2, 4, 4 the output is 65536.

\$\endgroup\$
  • \$\begingroup\$ "very slow" is the reason my 86-character solution was considered bad. \$\endgroup\$ – John Dvorak Apr 28 '13 at 10:54
  • 1
    \$\begingroup\$ @JanDvorak: Why do you think it was considered bad? Soham Chowdhury just said it is slow and that you should add another version, not that you replace your solution. (But maybe I misunderstood that.) \$\endgroup\$ – WolframH Apr 28 '13 at 14:19
  • \$\begingroup\$ You're right; restored the short version. Now I'm just a char longer than you. \$\endgroup\$ – John Dvorak Apr 28 '13 at 14:29
  • \$\begingroup\$ @WolframH exactly. Always nice to have versions. \$\endgroup\$ – Soham Chowdhury Apr 29 '13 at 2:02
2
\$\begingroup\$

Python, 96 92

def h(x,y,n):r=1;exec(n>2)*y*"r=h(x,r,n-1);";return(r,(x+y,x*y)[n>1])[n<3]
print h(*input())

Input: 3, 3, 4
Output: 7625597484987

Shortened using a couple of @WolframH's ideas.

\$\endgroup\$
2
\$\begingroup\$

Golfscript, slow, 39 characters

 ~{\(.{3${[4$\2$4$.~}4$(*}{;;+}if])\;}.~

(live link)

This is the standard recursive algorithm with a base case of n=1 (addition) (i.e. slow). The same I've used in my Ruby solution

Here's a version with my annotations (mostly stack-keeping). It doesn't include one optimisation I've added later:

~{            #read the input and do (x y n f)
 \(.{         #(x y f n-1); if(n-1)
  3${         #(x y f n-1 c)
   4$\2$4$.~  #(x y f n-1 x c n-1 f); call
  }3$(*       #y-1 times
  {\;}4*
 }{           #else
  ;;+         #return (x+y)
 }if
}.~           #once

~ is the eval operator. In case of strings, it treats the string as a GolfScript program. Luckily, a space-separated list of integers is a valid GolfScript program that pushes those integers on the stack. Compared to this, my previous version of the input routine (" "/{~}/, split by space and eval each) is pretty lame. In case of functions, it calls the function. When preceded by . (clone), it calls the function with itself as the first argument.

Golfscript doesn't seem to be exactly well suited for making recursive algorithms. If you want a recursive algorithm that isn't tail-call optimisable, you need to create and destroy stack frames to preserve your variables. In most languages, this is done automatically. In golfscript, you have to actually clone the variables (actually, stack entries), and destroy the stack entries you no longer need. Golfscript has no concept of stack frames. Have I said GolfScript is a stack-based language?

The first requirement is understandable. You have to specify the arguments somehow. It's only nice if they keep their original positions as well. The second requirement is unfortunate, especially since the return value is on the top of the stack, and golfscript lacks the ability to delete just any stack element. You can rotate the stack and discard the new top element, but that quickly builds up. \; is fine. \;\;\;\;\; isn't. You can do \; in a loop ({\;}9*; cost: 6 chars to discard up to 9 elements, or 7 chars to discard up to 99 elements), but we can do better:

Golfscript has first-class arrays. It also has the array literal syntax [1 2 3 4]. What's unexpected is that [ and ] are not actually a part of the syntax. They are merely two operators: [ marks the current position on the stack, and ] collects every element until it finds the start-of-array mark or runs out of stack, and discards the mark. You can even tear these two apart and see what happens. Well, quite an interesting thing:

Did I say golfscript has no concept of stack frames? I lied. This is a stack frame: [. You can discard it all at once: ];. But what if we want to keep the return value? You could close the stack frame on function entry (then we have a slightly mangled version of pass-by-array - not an interesting concept), or we can close the stack frame and take its last element instead of discarding it completely: ]-1= or we can uncons the last element instead, and then discard the frame: ])\;. They're the same length, but the latter is slightly cooler, so I'm using it.

So, instead of 6 or 7 characters to do a clean-up, we can do with 5. I still feel this could be golfed more, but hey, we've saved a character.

\$\endgroup\$
  • \$\begingroup\$ "calls the function with itself as the first argument" - interesting idea for recursion \$\endgroup\$ – aditsu May 1 '13 at 16:22
1
\$\begingroup\$

Smalltalk Squeak 4.x flavour many bytes!

I could implement one of the recursive form in Integer in 71 char

f:y n:n n=1or:[^(2to:y)inject:self into:[:x :i|self f:x n:n-1]].^self+y

Then reading from a file or FileStream stdin will cost me an arm... Squeak was obviously not designed as a scripting language. So I will spend many bytes to create my own general purpose utilities unrelated to the problem:

Implement this 21 char method in Stream (to skip seaparators)

s self skipSeparators

Implement this 20 char method in Behavior (to read an instance from a Stream)

<s^self readFrom:s s

Then 28 chars in String (to create a file handle)

f^FileDirectory default/self

Then 59 chars in FileDirectory (to create a readStream)

r^FileStream concreteStream readOnlyFileNamed:self fullName

Then 33 chars in BlockClosure (to evaluate it n times)

*n^(1to:n)collect:[:i|self value]

Then 63 chars in Array (evaluate the argument with receiver and arguments taken from the Array)

`s^self first perform:s asSymbol withArguments:self allButFirst

then solve the problem by evaluating this 31 char snippet anywhere to read from file named x

|s|s:='x'f r.[0class<s]*3`#f:n:

Even without counting the utilities, that's 71+31=102 chars already...

Now, since I'm sure to lose the codeGolf, I have a funnier implementation in Integer:

doesNotUnderstand:m
    (m selector allSatisfy:[:c|c=$+])or:[^super doesNotUnderstand:m].
    self class compile:
        m selector,'y y=0or:[^(2to:y)inject:self into:[:x :i|self'
        ,m selector allButLast,'x]].^'
        ,(Character digitValue:()asBit)
        ,(m selector size-2min:1)hex last.
    thisContext sender restart

This method will define (compile) a binary messages made of n + if it does not exist (is not understood by the receiver of the message m), and will restart execution at the beginning of sender context. I inserted additionnal carriage return and spaces for readability.

Note that (m selector size-2min:1)hex last is a shorted form of (m selector size>2)asBit printString.

If it was not to demonstrate Smalltalk evil superpowers, the last statement could be replaced by shorter and simpler

^m sendTo:self

Now implement 28 chars utility in Character (to repeat it n times in a String)

*n^String new:n withAll:self

Then evaluate this 43 chars expression:

|i s|i:=0class.s:='x'f r.[i<s]*2`($+*(i<s))

We can accelerate with 10 more chars by implementing in Integer:

++y^self*y

and in this case we also have shorter code because we can replace ^',(m selector size-2min:1)hex lastwith ^1'

For such a high price, the code work with second integer=0 :)

\$\endgroup\$
0
\$\begingroup\$

Groovy - 77

h={x,y,n->n<2?x+y:y<2?x:h(x,h(x,y-1,n),n-1)}
print h(args.collect{it as int})

Note: it requires obscene amounts of stack (and time) for non-tiny arguments.

\$\endgroup\$
0
\$\begingroup\$

AXIOM Computer Algebra System, bytes 69

p(x,y,n)==(n<=1=>y+x^n;n=2=>y*x;n=3=>x^y;y<=0=>1;p(x,p(x,y-1,n),n-1))

test:

(2) -> p(1,1,1)
   (2)  2
                                                 Type: Expression Integer
                                   Time: 0.05 (IN) + 0.03 (OT) = 0.08 sec
(3) -> p(2,4,4)
   (3)  65536
                                                 Type: Expression Integer
                                                              Time: 0 sec
(4) -> p(3,3,4)
   (4)  7625597484987
                                                 Type: Expression Integer
                                                              Time: 0 sec

This would eliminate some recursion...Possible I swap in x and y in some return... are there other test values?

\$\endgroup\$
0
\$\begingroup\$

APL(NARS), chars 61, bytes 122

{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}

test:

  h←{(x y n)←⍵⋄n≤1:y+x*n⋄n=2:x×y⋄n=3:x*y⋄y≤0:1⋄∇x,(∇x(y-1)n),n-1}
  h 1 1 1
2
  h 2 4 4
65536
  h 3 4 4
∞
  h 3 3 4
7625597484987
\$\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.