27
\$\begingroup\$

Background

Conway chained arrow notation is a notation to express very large numbers. It consists of zero or more positive integers separated by right arrows, e.g. \$2 \to 3 \to 4 \to 5 \to 6 \$.

Assuming \$p, q, a_1, \dots, a_n\$ are positive integers and \$X\$ is an abbreviation for a nonempty chain \$a_1 \to a_2 \to \dots \to a_n\$, the rules for evaluating such a notation are as follows:

$$ \begin{align} (\text{empty chain}) &= 1 \\ (p) &= p \\ p \to q &= p^q \\ X \to 1 &= X \\ X \to 1 \to p &= X \\ X \to (p+1)\to (q+1) &= X \to (X \to p\to (q+1))\to q \end{align} $$

A length-3 chain has an equivalent up-arrow notation: \$ p \to q \to r = p \uparrow^r q\$.

Note that the arrow notation cannot be treated as some kind of binary operator:

$$ \begin{align} 2 \to 3 \to 2 &= 16 \\ 2 \to (3 \to 2) &= 512 \\ (2 \to 3) \to 2 &= 64 \end{align} $$

More examples can be found on the Wikipedia page linked above.

Task

Given a (possibly empty) list of positive integers, interpret it as Conway chained arrow notation and evaluate it into a single number.

It is OK if your program gives wrong answers for large values due to the limits (bounds and/or precision) of your language's number type, as long as the underlying algorithm is correct.

Standard rules apply. The shortest code in bytes wins.

Test cases

Input => Output
[] => 1
[1] => 1
[99999999] => 99999999
[5, 5] => 3125
[4, 8] => 65536
[1, 2, 4] => 1
[2, 2, 4] => 4
[2, 3, 2] => 16
[2, 4, 2] => 65536
[4, 3, 2] => 4^256 = 1.34e154
[2, 2, 3, 2] => 4
\$\endgroup\$
  • 1
    \$\begingroup\$ Can we take the input list in reversed order? \$\endgroup\$ – Leo Apr 29 at 2:33
  • \$\begingroup\$ @Leo Yes, no problem, as long as you state so in your answer. \$\endgroup\$ – Bubbler Apr 29 at 2:59
  • 2
    \$\begingroup\$ Interesting, but even after coding the algorithm, I feel I don't have any real insight into it. Did you read the original source? Does it have background on the intuition and motivation that led Conway to this definition? \$\endgroup\$ – Jonah Apr 29 at 4:18
  • 2
    \$\begingroup\$ @Jonah There's a little motivation here. \$\endgroup\$ – Mitchell Spector Apr 29 at 7:05
  • 1
    \$\begingroup\$ @MitchellSpector I looked it up in The Book of Numbers and the explanation there is pretty good: fundamentally, it looks like a generalization and more compact version of up arrow notation. Although all these things grow so fast they defy anything we have intuition about \$\endgroup\$ – Jonah Apr 29 at 11:36

15 Answers 15

14
\$\begingroup\$

Haskell, 75 68 63 bytes

f(q:p:x)|p^q>p,x>[]=f$q-1:f(q:p-1:x):x|1<2=f$p^q:x
f[x]=x
f _=1

Try it online!

Takes input as a list in reversed order, since in Haskell it's easier to deal with the beginning of a list than with the end of it.

Now shorter and uglier!

Rules 3,4,5,6 are combined in the first line. The most important trick is realizing that p^q==p iff p==1||q==1 (where ^ is exponentiation and we're dealing with strictly positive numbers). We check the conditions to apply rule 6 (p and q greater than 1, at least three elements in the input) and if they are valid we do so recursively. If these conditions fail we know that either there is a 1 in the first two elements or there are just two elements in total: for both of this cases f(p^q:x) can solve the task.

The last two lines deal with inputs with less than two elements. They could be rewritten as a single line f x=last$1:x but the score would not change.


Below the original solution, no golfing tricks, just beautiful Haskell code:

f[]=1
f[p]=p
f[q,p]=p^q
f(1:x)=f x
f(_:1:x)=f x
f(q:p:x)=f$q-1:f(q:p-1:x):x

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Haskell is just beautiful. Amazing that this syntax easily beats the dc and c "golfed" implementations. \$\endgroup\$ – 6005 May 1 at 14:07
  • 2
    \$\begingroup\$ and aside of absence of whitespaces, it's actually not golfed at all. \$\endgroup\$ – Xwtek May 2 at 5:08
  • \$\begingroup\$ That's right, compared to "real" code this is just missing a type declaration and a more meaningful name for the function, so we could say my golfing was just removing comments and whitespace :D I'm a bit disappointed that I couldn't find a way to really golf this more, but I'm always happy to show how beautiful Haskell can be. \$\endgroup\$ – Leo May 2 at 7:23
  • 1
    \$\begingroup\$ Ok, sorry to ruin all of this, I found a way to golf it and made everything ugly :/ \$\endgroup\$ – Leo May 2 at 8:08
7
\$\begingroup\$

dc, 112 107 bytes

?[dz0r^+q]sZ[rd3Rd_3R^q]sE[ilfx1rq]sA[iSplfx1rLprq]sB[z2>Zz2=Ed1=Ard1=B1-rlfx3RSpr1-lfx_3Rri1+Lp1+r3R]dsfxp

Try it online!

Or verify all the test cases.

The input is on stdin (a line with space-separated numbers), and the output is on stdout.


How it works:

dc is a stack-based language. The recursive macro f does the Conway chained-arrow calculation, but the stack is treated differently from what you usually see:

  1. The input to f is the entire stack when the call is made. (So f essentially takes a variable number of arguments.)

  2. If the stack at the time of call is

$$a_1 \; a_2 \; \dots \; a_n$$

(with the top of the stack on the right), f will compute the value of

$$a_1 \to a_2 \to \dots \to a_n$$

and push it on top of the stack, but it leaves the arguments on the stack also.

So f turns the stack

$$a_1 \; a_2 \; \dots \; a_n$$

into

$$a_1 \; a_2 \; \dots \; a_n \; [\text{ArrowValue}(a_1 \; a_2 \; \dots \; a_n)]$$

where I've written \$\;[\text{ArrowValue}(a_1 \; a_2 \; \dots \; a_n)]\;\$ for the value of \$\;a_1 \to a_2 \to \dots \to a_n.\$

There are several auxiliary macros as well. All the usual complex control structures other languages have (loops, conditionals, functions) are implemented in dc using macros.


Note that dc produces a few error messages or warnings due to the golfing tricks used, but they don't interrupt program execution, and the messages are just written to stderr. Examples of these: duplicating when there's nothing on the stack, adding when there's only one item on the stack, or setting the input base to an illegal value.

The code also makes use of the fact that we can distinguish positive numbers from \$0\$ by whether the power \$0^x\$ is \$0\$ or \$1.\$


Here's a detailed summary of the program's operation, updated for the revised, shorter answer.

?  Read a line of space-separated numbers, written in the usual
   Conway chained-arrow order, pushing them onto the stack in turn.
   (The chained arrow sequence will start at the bottom of the stack,
   since that's pushed first, and will end at the top of the stack, since
   that's pushed last.)


        MACRO Z
Macro Z will only be called when the stack either is empty or
has just one item p on it.  We'll analyze both possibilities.
[   Start macro.
         Stack: Empty   or   p
 d    Duplicate.
         Stack: Empty   or   p p
 z    Push the size of the stack.
         Stack: 0       or   p p 2
 0    Push 0.
         Stack: 0 0     or   p p 2 0
 r
      Swap.
         Stack: 0 0     or   p p 0 2
 ^    Exponentiate.
         Stack: 1       or   p p 0
 +    Add top 2 items if they exist.
         Stack: 1       or   p p
 q    Exit this macro and the macro which called it.
]sZ End macro and name it Z.

Summary of Z:
      Turn: Empty stack
      Into: 1
and
      Turn: p
      into: p p


        MACRO E
[       Start a macro.  Assume the stack is: ... p q (top on right).
 r        Swap.                         Stack: ... q p
 d        Duplicate.                    Stack: ... q p p
 3R       Rotate left the top 3 items.  Stack: ... p p q
 d        Duplicate.                    Stack: ... p p q q
 _3R      Rotate right the top 3 items. Stack: ... p q p q
 ^        Exponentiate.                 Stack: ... p  q p**q
 q        Exit this macro and the macro which called it.
]sE     End the macro and name it E.
Summary of E:
  Turn: ... p q
  into: ... p q p**q


        MACRO A
[       Start a macro.  Assume the stack is:   ... p (top on right).
 i        Discard the top of stack.  (Actually make it the new input radix just because dc wants a place to put it.)
                                        Stack: ...
 lfx      Call f recursively.           Stack: ... ArrowValue(...)
 1        Push 1.                       Stack: ... ArrowValue(...) 1
 r        Swap.                         Stack: ... 1 ArrowValue(...)
 q        Exit this macro and the macro which called it.
]sA     End the macro and name it A.
Summary of A:
  Turn: ... p
  into: ... 1 ArrowValue(...)


        MACRO B
[       Start a macro.  Assume the stack is:    ... p q (top on right).
 i        Discard top of stack (by storing it as the input radix).
                                         Stack: ... p 
 Sp       Pop p off the stack and
          push it onto stack p.          Stack: ...
 lfx      Call f recursively.            Stack: ... ArrowValue(...)
 1        Push 1.                        Stack: ... ArrowValue(...) 1
 r        Swap.                         Stack: ... 1 ArrowValue(...)
 Lp       Pop the old value of p from stack p.
                                        Stack: ... 1 ArrowValue(...) p
 r        Swap                          Stack: ... 1 p ArrowValue(...)
 q        Exit this macro and the macro which called it.
]sB     End the macro and name it B.
Summary of B:
  Turn: ... p q
  into: ... 1 p ArrowValue(...)



        MACRO f
[       Start a macro.
 z      Push the stack size.
 2>     If the stack size was 0 or 1,
 O        then call macro Z and return from f.
          In this case, we've turned ...
                                into ... 1

                     or we've turned ... p 
                                into ... p p

 z2=E   If the stack size was 2,
          then call macro E and return from f.
          In this case, we've turned ... p q
                                into ... p q p**q

        If we get here, the stack size is at least 3.

 d1=A   If the item at the top of the stack == 1,
          then call macro A and return from f.
          In this case, we've turned ... 1
                                into ... 1 ArrowValue(...)

        If we get here, the stack size is at least 3 and the item at the top of the stack isn't 1.
                              Stack: ... p q r
          where r != 1.
 r      Swap.                 Stack: ... p r q      
 d1=B   If the item at the top of the stack == 1,
          then call macro B and return from f.
        In this case, we've turned   ... p 1 r
                              into   ... p 1 r ArrowValue(... p)

        If we get here, the stack size is at least 3, neither of the items at the top of the stack is 1,
        and we've already gone from
                              Stack: ... p q r
                           to Stack: ... p r q               
 1-     Subtract 1.           Stack: ... p r q-1
 r      Swap.                 Stack: ... p q-1 r
 lfx    Call f recursively.   Stack: ... p q-1 r [ArrowValue(... p q-1 r)]
 3R     Rotate left the top 3 items on the stack.
                              Stack: ... p r [ArrowValue(... p q-1 r)] q-1
 Sp     Pop q-1 off the stack and push it onto stack p.
                              Stack: ... p r [ArrowValue(... p q-1 r)] 
 r      Swap.                 Stack: ... p [ArrowValue(... p q-1 r)] r
 1-     Subtract 1.           Stack: ... p [ArrowValue(... p q-1 r)] r-1
 lfx    Call f recursively.   Stack: ... p  [ArrowValue(... p q-1 r)]  r-1  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]
 _3R    Rotate right the top 3 items on the stack.
                              Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  [ArrowValue(... p q-1 r)]  r-1
 r      Swap:                 Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r-1  [ArrowValue(... p q-1 r)]
 i      Discard the top item. Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r-1
 1+     Add 1                 Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r
 Lp     Load the old value of q-1 from stack p.
                              Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r  q-1
 1+     Add 1.                Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  r  q
 r      Swap.                 Stack: ... p  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]  q  r
 3R     Rotate left the top 3 items on the stack.
                              Stack: ... p  q  r  [ArrowValue(... p ArrowValue(... p q-1 r) r-1)]
]       End the macro,
dsf       save it on the stack, and name it f.
Summary of f:
  Turn: ...
  into: ... ArrowValue(...)

x       Execute f.
p       Print the desired value, which is now at the top of the stack.
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

C (gcc) -m32 -lm, 159 150 137 136 bytes

f(a,b,u,t)int*a,*b;{t=a-b?b-a-1?*a-1?b-a-2?a[1]-1?t=a[1]--,a[1]=f(a,b),--*a,u=f(a,b),++*a,a[1]=t,u:f(a+2,b):pow(a[1],*a):f(a+1,b):*a:1;}

Try the test cases online! (except for [4, 3, 2], which overflows).

9 bytes off thanks to ceilingcat!

And saved 1 more byte thanks to ceilingcat too.


Input is taken as an array of ints in reverse order, and is passed as a pointer to the beginning and a pointer to (the location immediately after) the end.


The following applies to the previous version of the program. The current version uses exponentiation from the C math library. The compilation flag -m32 is now used so that the usual #include <math.h> line can be omitted.

C doesn't have exponentiation built in, so the previous version handled that by changing the 3rd and 4th rules of the recursive definition from

$$ \begin{align} p \to q &= p^q \\ X \to 1 &= X \\ \end{align} $$

to

$$ \begin{align} \quad\quad\quad\quad\quad X \to 1 &= X \\ p \to q &= (p \to q-1)*p \\ \end{align} $$

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @ovs Thanks for fixing my mangled edit. \$\endgroup\$ – Mitchell Spector Apr 30 at 18:43
3
\$\begingroup\$

J, 90 79 75 bytes

(1:`]`(^~/)`(2&}.$:@,~<:@{.,[:$:]-2=#\)@.(3<.#))`($:@}.~1+i.&1)@.(1 e.2&{.)

Try it online!

Takes input in reverse order.

I suspect there's room for more golfing yet. I may return to it tomorrow.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES7),  78  77 bytes

Takes the list in reverse order.

f=([q,p,...a])=>a+a?f(--q?--p?[q,f([++q,p,...a]),...a]:a:[p,...a]):p**q||q||1

Try it online!

With BigInt support (78 bytes)

This version accepts either a list of Numbers or a list of BigInts and returns a value of the same type.

f=([q,p,...a])=>a+a?f(--q?--p?[q,f([++q,p,...a]),...a]:a:[p,...a]):p?p**q:q||1

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Is that supposed to be a[0]? By my reading, that should be ...a... \$\endgroup\$ – Neil Apr 29 at 10:00
  • \$\begingroup\$ @Neil You're right: \$X\$ is ...a. Thank you! \$\endgroup\$ – Arnauld Apr 29 at 10:11
2
\$\begingroup\$

Python 2, 117 112 111 bytes

f=lambda x:(len(x)<3)*reduce(lambda a,b:b**a,x,1)or f((1in x[:2])*x[1:]or[x[0]-1,f([x[0],x[1]-1]+x[2:])]+x[2:])

Try it online!

Takes input in reverse order.

A recursive function that takes in a list of positive integers and returns a single number.

In order to save bytes, we combine the 3 base cases into one expression:

(len(x)<3)*reduce(lambda a,b:b**a,x,1)

which returns either \$1\$, \$p\$, or \$p^q\$.


The recursive cases are also mashed together via:

f((1in x[:2])*x[1:]or[x[0]-1,f([x[0],x[1]-1]+x[2:])]+x[2:])

which becomes f(x[1:]) when x[0] is \$1\$ or x[1] is \$1\$, and becomes f([x[0]-1,f([x[0],x[1]-1]+x[2:])]+x[2:]) otherwise.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Erlang (escript), 111 bytes

Port of the Haskell answer. The last case seems to time out.

f([])->1;f([P])->P;f([1|X])->f(X);f([Q,P])->math:pow(P,Q);f([_,1|X])->f(X);f([Q,P|X])->f([Q-1,f([Q,P-1|X])|X]).

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 57 49 bytes

Saved 8 bytes thanks to @Bubbler!

{3>≢⍵:*/⌽⍵⋄1=⊃⍵:∇1↓⍵⋄(∇(⊃⍵-1),,∘v)⍣(2⊃⍵-1)∇v←2↓⍵}

Try it online!

A monadic function that must be given the input in reverse.

This is how Conway described his chained arrow notation:

Our own "chained arrow" notation names some even larger numbers. In this, a^^...^^b (with c arrows) is called a->b->c.

a->b-> ... ->x->y-> 1 is another name for a->b-> ... ->x->y

and a ... x->y->(z+1) is defined to be

a ... x if y = 1,

a ... x->(a...x)->z if y = 2,

a ... x->(a...x->(a...x)->z)->z if y = 3

and so on.

We can replace the first rule from here with the first three rules from the question, which can be collapsed to just folding over the chain with exponentiation (3>≢⍵: */⌽⍵). 1=⊃⍵: ∇1↓⍵ handles the \$X \to 1\$ case, which both definitions share. The \$ X \to 1 \to p\$ case is taken care of by Conway's last rule, which is just \$y-1\$ applications of {∇z,⍵,x}.


Original answer, 70 62 59 55 bytes

Saved 4 bytes here too thanks to Bubbler

f←{3>≢⍵:*/⌽⍵⋄3>⍵⍳1:∇⍵↓⍨⍵⍳1⋄∇(⊃⍵-1)(∇(⊃⍵)(2⊃⍵-1),2↓⍵),2↓⍵}

Try it online!

{3>≢⍵:*/⌽1 1,⍵ ⍝ If ⍵ has 0, 1, or 2 elements, prepend two 1's and reverse it so 
                 ⍝ it's `1 1`, `p 1 1`, or `p q 1 1`, and then reduce with exponentiation
⋄3>⍵⍳1:∇(⍵⍳1)↓⍵                    ⍝ If 1 is at index 1 or 2 in ⍵, drop to that index
⋄∇(⊃⍵-1)(∇(⊃⍵)(2⊃⍵-1),2↓⍵),2↓⍵} ⍝ Otherwise, return f q (f (q+1) p X) X
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The second one doesn't work on TIO because you're using as Atop (f⍤g) which was added in 18.0, while TIO is still at 17.1. You can convert that part into a train (eliminating the need of Atop). Also, 1 1, in */⌽1 1,⍵ can be entirely removed (*/⍬ is 1). Finally, using a variable for 2↓⍵ gives 49 bytes. \$\endgroup\$ – Bubbler Nov 25 at 4:37
  • \$\begingroup\$ @Bubbler That's amazing, thanks! I didn't know that there was an identity for folding with exponentiation, that's really useful. \$\endgroup\$ – user Nov 25 at 15:55
1
\$\begingroup\$

Rust, 161 bytes

fn f(s:&[u32])->u32{match
s{[]=>1,[x]=>*x,[p,q]=>p.pow(*q),[x@..,1]=>f(x),[x@..,1,_]=>f(x),[x@..,p,q]=>f(&[x,&[f(&[x,&[p-1],&[*q]].concat())],&[q-1]].concat())}}

Uses Rusts pattern matching. The last case is a little verbose, because there's no spread operator.

Try it on the rust playground.

Readable version

fn f(s: &[u32]) -> u32 {
    match s {
        []=>1,
        [x]=>*x,
        [p,q]=>p.pow(*q),
        [x@..,1]=>f(x),
        [x@..,1,_]=>f(x),
        [x@..,p,q]=>f(&[x, &[f(&[x,&[p-1,*q]].concat())], &[q-1]].concat())
    }
}
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 68 66 bytes

"D©g2‹iPë`i)Y.Vëi)Y.Vë)\®`®g<imëX®šUs<s)Y.VXćsUDgÍsŠǝRć<šRY.V"DV.V

This was pretty hard in a stack-based language..

Try it online or verify all test cases.

Explanation:

"                          "# Start a string we can execute as 05AB1E code
                            # to mimic recursive calls:
 D                          # Duplicate the list at the top of the stack
                            # (which will be the (implicit) input at the start)
  ©                         # Store it in variable `®` (without popping)
   g2‹i                     # Pop one, and if its length is smaller than 2:
       P                    #  Take the product
                            #  ([] → 1; [p] → p)
   ë                        # Else (the length is >= 2):
    `                       #  Dump the contents of the list onto the stack
     i                      #  Pop the top value, and if it's a 1:
      )                     #   Wrap the remaining values into a list
       Y.V                  #   And do a recursive call
                            #   (p=1 for [...,q,p] → recursive call to [...,q])
     ë                      #  Else:
      i                     #   Pop the second top value, and if it's a 1:
       )                    #    Wrap the remaining values into a list
        Y.V                 #    And do a recursive call
                            #    (q=1 for [...,q,p] → recursive call to [...])
      ë                     #   Else:
       )\                   #    Discard everything on the stack
         ®`                 #    Dump the contents of `®` onto the stack again
           ®g<i             #    If the length of `®` is 2:
               m            #     Take the power of the two values
                            #     ([p,q] → p^q)
              ë             #    Else (the length is >= 3):
               X®šU         #     Prepend `®` to list `X`
                            #     (`X` is 1 by default, but that doesn't matter;
                            #      it'll become [[...,p,q],1] and the 1 is ignored)
               s<s)         #     Decrease the second value from the top by 1
                   Y.V      #     And do a recursive call
                            #     ([...,p,q] → recursive call to [...,p-1,q],
                            #      let's call its result `R` for the moment)
               Xć           #     Extract the first list from variable `X` again,
                 sU         #     and pop and store the remaining values as new `X`
                 DgÍ        #     Take its length - 2 (without popping by duplicating first)
                            #     (let's call this length-2 `I` for the moment)
                    sŠ      #     Swap & triple-swap ([...,R,[...,p,q],I] → [...,[...,p,q],R,I])
                      ǝ     #     Insert value `R` into the list at (0-based) index `I`
                            #     ([...,[...,p,q]] → [...,[...,R,q]])
                 Rć<šR      #     And decrease the last value in the top list by 1
                            #     ([...,[...,R,q]] → [...,[...,R,q-1]])
                       Y.V  #     And do a recursive call again
"                          "# End the string of 05AB1E code
 DV                         # Store a copy of this string in variable `Y`
   .V                       # Execute it as 05AB1E code (`Y.V` is how we can do recursive calls)
                            # (after which the result is output implicitly)
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Pyth, 40 38 bytes

L?tJtby?}1<b2J+,thby+,hbthJtJttb|^F_b1

Try it online!

Takes input in reverse order.

L defines a recursive function named y that takes in a list b of positive integers and returns a single number.

Similarly to my Python answer, the base cases are combined into one expression:

|^F_b1

in which ^F_b folds the exponentiation function ^ over b in reverse. If b has 2 elements \$(q,p)\$ this will return \$p^q\$, if b has 1 element \$(p)\$ it will return \$p\$, and if b is empty it will return 0 (| .. 1 turns the 0 into 1, as needed)


The recursive cases are handled by:

y?}1<b2J+,thby+,hbthJtJttb

This part is a pretty straightforward translation of the recursive rules. If either of the first two elements of b are 1 it calls y on tb (equivalent to b[1:] in Python)*. Otherwise, the formula \$X \to (X \to p\to (q+1))\to q\$ is passed recusively to y.

*The rule \$X \to 1 \to p = X\$ thus takes two steps instead of one, but doing it this way saves a few bytes.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Scala, 156 bytes

val f:Seq[Int]=>Int={case Nil=>1
case p::Nil=>p
case q::p::Nil=>math.pow(p,q)toInt
case 1::x=>f(x)
case p::1::x=>f(x)
case q::p::x=>f(q-1::f(q::p-1::x)::x)}

Try it in Scastie

Note: Input must be a reversed List. If it's not reversed, the algorithm won't work correctly, and if it's not a List, there'll be a MatchError.

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 67 66 bytes

f[x__,1,_:0]=f@x
f[x___,p_:1,q_:1]=If[x<1,p^q,f[x,f[x,p-1,q],q-1]]

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Java, 282 chars

interface c{int n[]=new int[99];static void main(String[]a){int i=0,j=a.length;for(;i<j;)n[i]=new Integer(a[i++]);System.out.print(j<1?1:j<2?n[0]:c(j));}static int c(int j){j-=n[j-2]<2?2:n[j-1]<2?1:0;if(j<3)return(int)Math.pow(n[0],n[1]);n[j-2]--;n[j-2]=c(j);n[j-1]--;return c(j);}}

Readable version:

interface c{
    int n[]=new int[99];
    static void main(String[]a){
        int i=0,j=a.length;for(;i<j;)n[i]=new Integer(a[i++]);
        System.out.print(j<1?1:j<2?n[0]:c(j));
    }
    static int c(int j){
        j-=n[j-2]<2?2:n[j-1]<2?1:0;
        if(j<3)return(int)Math.pow(n[0],n[1]);
        n[j-2]--;
        n[j-2]=c(j);
        n[j-1]--;
        return c(j);
    }
}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Clojure, 117 bytes

(defn f([]1)([q]q)([q p](Math/pow p q))([q p & x](if(== p(f q p))(apply f p x)(apply f(dec q)(apply f q(dec p)x)x))))

Try it online!

Handles all test cases, takes input arguments in reverse order.

| improve this answer | |
\$\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.