title: Count the crossing words

text:
# Question
Title: Count the crossing words
Consider the following standard 15×15 crossword puzzle grid.

We can represent this in ASCII art by using `#` for blocks and  (space) for white squares.

```
     #    #
     #    #
          #
   #   #
###     ##   ##

     ##   #
   #       #
    #   ##

##   ##     ###
       #   #
    #
    #    #
    #    #

```

Given a crossword grid in the ASCII art format above, determine how many words it holds. (The above grid has 78 words. It happens to be last Monday's *New York Times* puzzle.)

A word is a group of two or more consecutive spaces running vertically or horizontally. A word starts and ends with either a block or the edge of the grid and always runs top to bottom or left to right, never diagonally or backwards. Note that words can span the whole width of the puzzle, as in the sixth row of the puzzle above. A word does not have to be connected to another word.

## Details

* Input will always be a rectangle containing the characters `#` or  (space), with rows separated by a newline (`\n`). You can assume the grid is made of any 2 distinct printable ASCII characters instead of `#` and .
* You may assume there is an optional trailing newline. Trailing space characters DO count, as they affect the number of words.
* The grid will not always be symmetrical, and it may be all spaces or all blocks.
* Your program should theoretically be able to work on a grid of any size, but for this challenge it will never be larger than 21×21.
* You may take the grid itself as input or the name of a file containing the grid.
* Take input from stdin or command line arguments and output to stdout.
* If you prefer, you may use a named function instead of a program, taking the grid as a string argument and outputting an integer or string via stdout or function return.

## Test cases

1. Input:

```
    #
    #
    #

```

Output: `7` (There are four spaces before each `#`. The result would be the same if each number sign were removed, but Markdown strips spaces from otherwise empty lines.)
2. Input:

```
##
 #
##

```

Output: `0` (One-letter words don't count.)
3. Input:

```
######
#    #
  ####
# ## #
# ## #
#### #

```

Output: `4`
4. Input: (May 10's Sunday *NY Times* puzzle)

```
   #    ##   #
   #    #    #
   #         #
       #     ###   ##
    #       #
##   #   #
        #       ##
      #   ##
   #        ##      #
         #   ###   ##
#   ##         ##   #
##   ###   #
#      ##        #
         ##   #
   ##       #
           #   #   ##
        #       #
##   ###     #
       #         #
       #    #    #
       #   ##    #

```

Output: `140`

## Scoring

Shortest code in bytes wins. Tiebreaker is oldest post.

# Answer
> 8 votes
# CJam, ~~18~~ ~~17~~ ~~13~~ 11 bytes

*2 bytes saved by Dennis.*

Uses spaces for filled cells and `1` for empty cells:

```
qN/_z+:~1-,

```

Test it here.

## Explanation

```
q    e# Read the entire input.
N/   e# Split into lines.
_z   e# Make a copy and transpose it.
+    e# Add the lines of the two grids together.
:~   e# Evaluate each line which will push a rep-digit number for each empty-cell chunk.
1-   e# Remove all the 1s as these correspond to individual empty cells.
,    e# Get the length of the array.

```

# Answer
> 9 votes
# Slip, 18 + 3 = 21 bytes

```
>? ( +(X|$^)<<){2}

```

Run with the flags `no` (hence the +3), and uses space/`X` instead of space/`#`. Annoyingly this is longer than CJam/Pyth, but I guess Slip wasn't designed to be particular golfy...

Try it online. Note that the first example is missing spaces on a few lines.

## Explanation

```
>?           Optionally turn right, hence matching either horizontally or vertically
[space]      Match a space
(    ){2}    Group, twice:
[space]+       Match 1+ spaces
(X|$^)         Either an X or the boundary of the grid
<<             Reverse the match pointer by turning left twice

```

The `n` flag makes output print the number of matches, and the `o` flag enables overlapping matches starting from the same square. The reason for the back-and-forth is because Slip tries matches starting from every square, and we want to make sure we only match a full row rather than a partial one. Slip only returns unique matches, even if they started from different positions.

Note: Originally I had `>?( +(X|$^)<<){2}`, with the first space on the inside. This would miss some cases with 2 space long words at the edge, since the pointer would go like this:

```
XXX       XXX       XXX       XXX
X>        X >       X<        <
XXX       XXX       XXX       XXX

[sp]    [sp]+$^    <<[sp]    [sp]+   (uh oh match fails)

```

# Answer
> 4 votes
# Haskell, 81 bytes

```
import Data.List
m x=sum[1|(_:_:_)<-words x]
f x=m x+m(unlines$transpose$lines x)

```

Uses spaces  as block characters and any other (non whitespace) character as an empty cell.

How it works: split input into list of words at spaces. Take a `1` for every word with at lease 2 characters and sum those `1`s. Apply the same procedure to the transposition (split at `\n`) of the input. Add both results.

# Answer
> 4 votes
# Pyth, ~~15~~ ~~14~~ 13 bytes

```
lftTcjd+.zC.z

```

I'm using  as seperator and `#` as fill characters instead of their opposite meaning from the OP. Try it online: Demonstration

Instead of `#` as fill character this accepts also letters. So you could actually take the solved crossword puzzle, and it would print the number of words. And if you remove the `l` command, it even prints all words. Test it here: May 10's Sunday NY Times puzzle

### Explanation

```
        .z      all input rows
          C.z   all input columns (C transposes)
       +        add them (all rows and columns)
     jd         join by spaces
    c           split by spaces
 f              filter for pieces T, which satisfy:
  tT              len(T) > 1
l               length, implicitly printed

```

# Answer
> 4 votes
# JavaScript (*ES6*) 87 ~~121 147~~

Build the transposition of input string and append it to input, then count the strings of 2 or more spaces.

Run the snippet in Firefox to test.

Credits @IsmaelMiguel, a solution for ES5 (122 bytes):

```
function F(z){for(r=z.split(/\n/),i=0;i<r[j=0][L='length'];i++)for(z+='#';j<r[L];)z+=r[j++][i];return~-z.split(/  +/)[L]};

```

```
F=z=>
(
  r=z.split(/\n/),
  [r.map(r=>z+=r[i],z+='#')for(i in r[0])],
  ~-z.split(/  +/).length
)

// TEST
out=x=>O.innerHTML += x + '\n';

[
'     #    #    \n     #    #    \n          #    \n   #   #       \n###     ##   ##\n               \n     ##   #    \n   #       #   \n    #   ##     \n               \n##   ##     ###\n       #   #   \n    #          \n    #    #     \n    #    #     ', '##\n #\n##', '    #\n    #\n    #',
 '######\n#    #\n  ####\n# ## #\n# ## #\n#### #',
 '   #    ##   #       \n   #    #    #       \n   #         #       \n       #     ###   ##\n    #       #        \n##   #   #           \n        #       ##   \n      #   ##         \n   #        ##      #\n         #   ###   ##\n#   ##         ##   #\n##   ###   #         \n#      ##        #   \n         ##   #      \n   ##       #        \n           #   #   ##\n        #       #    \n##   ###     #       \n       #         #   \n       #    #    #   \n       #   ##    #   '
].forEach(x=>out(x.replace(/ /g,'.')+'\n'+F(x)+'\n'))
```

```
<pre id=O></pre>
```

# Answer
> 0 votes
# , 38 bytes

```
1#.1<[:#;._1 1:,@,.[:(,!.1|:)'#'&=;._2

```

Try it online!

---
Tags: code-golf, grid, counting, crossword
---


title: Score a Game of Boggle

text:
# Question
Title: Score a Game of Boggle
# Background

In Boggle, a round is scored by adding up the points for each *unique* word a player has found (i.e. any word that more than one player has found is worth 0 points). The points are calculated based on the number of letters in each word, as follows:

3 letters: 1 point

4 letters: 1 point

5 letters: 2 points

6 letters: 3 points

7 letters: 5 points

8 or more letters: 11 points

# Challenge

In this challenge, write a program or function that takes in a list of lists of strings representing each player's words and outputs a list of the players' scores. You can assume that there will be at least 2 players and all words will be 3 or more letters and will all be lowercase (or all uppercase if you would prefer). You may also assume that each player will only use each word once; that is, no player's list will contain duplicates. This is code golf, so shortest answer in bytes wins.

# Rules

Input can be taken in any reasonable format. Examples include a list of lists of strings, a list of comma-separated strings, a comma separated string on each line of input, etc. Output can be in the form of a list of integers (or your language's equivalent) or you can print the values to stdout using a separator of your choice (such as a newline).

# Test Cases

Input =\> Output

```
[["cat","dog","bird","elephant"],
 ["bird","dog","coyote"],
 ["dog","mouse"]]                 => [12,3,2]

[["abc","def","ghi"],
 ["ghi","def","abc"]]             => [0,0]

[["programming","puzzles"],
 ["code","golf"],
 []]                              => [16,2,0]

```

# Answer
> 7 votes
# Husk, ~~21~~ ~~20~~ 19 bytes

-2 bytes thanks to Zgarb

Idea taken from A055228

```
ṠṀöṁ(⌈√Π-3▼8L)fε`#Σ

```

Try it online!

### Explanation (Of older version)

```
            ṠṀ-oṠ-uΣ   Remove duplicated words
                   Σ   Concatenate
                  u    Remove duplicates
               oṠ-     Remove those unique elements from the list (give list of elements that appear more than once)
            ṠṀ-        Remove those words from each list in the input
m                      For each list
 ṁ(                    Map then sum
          L)           Length
        ▼8             Min(8,x)
      -3               Minus 3
     Π                 Factorial
    √                  Square root
   ⌈                   Ceiling

```

# Answer
> 3 votes
# , ~~142~~ ~~126~~ ~~121~~ 117 bytes

```
function(L)sapply(lapply(L,setdiff,(l=unlist(L))[duplicated(l)]),function(x)sum(c(1,1,2,3,5,11)[pmin(6,nchar(x)-2)]))

```

Try it online!

Takes `L` as a list of vectors of strings; returns the values.

First, it `unlist`s the words, finds the duplicates, then removes them from the players' word lists. Then it takes these unique word lists and computes the scores of each, using `pmin` to ensure that words longer than 8 get scored as 11.

# Answer
> 3 votes
# JavaScript (ES6), ~~106~~ 93 bytes

*\[Saved 13(!) bytes, thanks to Arnauld, Shaggy, and JollyJoker.\]*

```
a=>a.map(b=>b.map(c=>x+=(a+'').split`,`.filter(d=>d==c)[1]?0:+'11235'[c.length-3]||11,x=0)|x)

```

**Test cases:**

```
let f=

a=>a.map(b=>b.map(c=>x+=(a+'').split`,`.filter(d=>d==c)[1]?0:+'11235'[c.length-3]||11,x=0)|x)

console.log(f([["cat","dog","bird","elephant"],
               ["bird","dog","coyote"],
               ["dog","mouse"]
              ])
           )  // [12,3,2]

console.log(f([["abc","def","ghi"],
               ["ghi","def","abc"]
              ])
           ) // [0,0]

console.log(f([["programming","puzzles"],
               ["code","golf"],
               []
              ])
            ) // [16,2,0]
```

# Answer
> 3 votes
# JavaScript (ES6), 92 bytes

```
a=>a.map(b=>b.reduce((s,v)=>s+(a.filter(b=>b.includes(v))[1]?0:+"11235"[v.length-3]||11),0))

```

Somewhat similar to Rick Hitchcock's answer but created mostly independently; I used a different method of summing (`reduce`) and different method for checking for repeated terms (`filter` \+ `includes`). Credit to him for the idea of checking for item `[1]` instead of checking `.length>1`, though.

## Test Cases

```
let f=
a=>a.map(b=>b.reduce((s,v)=>s+(a.filter(b=>b.includes(v))[1]?0:+"11235"[v.length-3]||11),0))

;[[["cat","dog","bird","elephant"],["bird","dog","coyote"],["dog","mouse"]],[["abc","def","ghi"],["ghi","def","abc"]],[["programming","puzzles"],["code","golf"],[]]]
.forEach(test=>O.innerHTML+=JSON.stringify(test)+" -> "+JSON.stringify(f(test))+"\n")
```

```
<pre id=O></pre>
```

# Answer
> 2 votes
# Pyth, 26 bytes

Uses H.PWiz's formula.

```
m+Fm.E@.!a3hS,8lk2fq1/sQTd

```

**Verify all the test cases.**

The initial version, **33 bytes**:

```
m+Fm*h+++*6>lk7y>lk6>lk5glk3q1/sQ

```

**Verify all the test cases.**

# Explanation

```
m+Fm*h+++*6>lk7y>lk6>lk5>glk3q1/sQ   Full program.

m                                    Map over the input.
   m                                 Map over each sublist.
                        >lk3         Is the length higher than 2? 1 if True and 0 if False.
      +             >lk5             Plus "is length higher than 5?".
       +       y>lk6                 Plus "is length higher than 6?", doubled.
        +*6>lk7                      Plus "is length higher than 7?", times 6.
     h                               Increment.
                            q1/sQ    Count the occurrences of the element in the flattened
                                     input, and check if it equals 1. 0 if False, 1 if True.
    *                                Multiplication.
 +F                                  Sum each sublist.

```

# Answer
> 2 votes
# Python 2, ~~106~~ ~~105~~ ~~88~~ 84 bytes

-1 byte thanks to Jonathan Frech
-1 (17) bytes thanks to reffu

```
lambda x:[sum(sum([1,0,1,1,2,6][:len(s)-2])*(`x`.count(`s`)<2)for s in l)for l in x]

```

Try it online!

# Answer
> 2 votes
# Perl 6, 64 bytes

```
{@^a.map:{sum .map:{@a.Bag{$_}>1??0!!(1,1,2,3,5)[.comb-3]||11}}}

```

Try it online!

# Answer
> 2 votes
# Japt, ~~29~~ ~~25~~ ~~24~~ ~~23~~ ~~21~~ 20 bytes

```
Ëx@èøX ¥1©3nXÊm8)Ê¬c

```

Try it

---

## Explanation

Implicit input of array `U`.

```
Ëx@

```

Map over the array (`Ë`) and reduce each sub-array by addition (`x`) after passing its elements through the following function, where `X` is the current word.

```
èøX

```

Count (`è`) the elements in `U` that contain (`ø`) `X`.

```
¥1

```

Check if that is equal to 1.

```
©

```

Logical AND (`&&`).

```
3nXÊm8)

```

Subtract (`n`) 3 from the minimum of (`m`) 8 and the length (`Ê`) of `X`.

```
Ê¬c

```

Factorial, square root and round up, respectively.

# Answer
> 2 votes
# Haskell, ~~76~~ 75 bytes

```
f l=[sum[fst.last$zip[0,0,1,1,2,3,5,11]w|w<-p,[w]==(filter(==w)=<<l)]|p<-l]

```

Try it online!

# Answer
> 1 votes
# Jelly, 26 bytes

```
ðċ@Ị¥ÐfL€«8ị“¡[żÇ’ḃ11¤Sµ€Ẏ

```

Try it online!

# Answer
> 1 votes
# Java 10, ~~202~~ ~~200~~ ~~198~~ ~~197~~ 194 bytes

```
a->{int q=a.length,r[]=new int[q],i=0,j,f;for(;i<q;i++)for(var s:a[i]){for(f=j=0;j<q;)f|=a[j].contains(s)&!a[i].equals(a[j++])?1:0;r[i]+=f<1?(j=s.length())<5?1:j<6?2:j<7?3:j<8?5:11:0;}return r;}

```

-1 byte thanks to *@ceilingcat*.

**Explanation:**

Try it here.

```
a->{                       // Method with ArrayList<String>[] parameter & int[] return-type
  int q=a.length,          //  Length of the input-array
      r[]=new int[q],      //  Result integer-array the size of the input-array,
                           //  initially filled with 0s by default
      i=0,j,               //  Index integers
      f;                   //  Flag integer (used as boolean)
  for(;i<q;i++)            //  Loop `i` in the range [0, `q`):
    for(var s:a[i]){       //   Inner loop over the Strings of the `i`'th List
      for(f=j=0;           //    Reset the flag `f` and index `j` both to 0
          j<q;)            //    Inner loop `j` in the range [0, `q`) again:
        f|=a[j].contains(s)//     If the `j`'th list contains the current String
           &!a[i].equals(a[j++])?
                           //     and the `i`'th and `j`'th list aren't the same:
            1              //      Bitwise-OR the flag with 1 (0->1; 1->1)
           :               //     Else:
            0;             //      Bitwise-OR the flag with 0 (0->0; 1->1)
                           //    End of inner loop (3) (implicit / single-line body)
      r[i]+=               //    Increase the `i`'th item in the result integer-array by:
            f<1?           //     If the flag is still 0 (so the current String is unique):
             (j=s.length())<5?
                           //      If the length of the String is below 5:
              1            //       Increase by 1
             :j<6?         //      Else-if the length is 5 instead:
              2            //       Increase by 2
             :j<7?         //      Else-if the length is 6 instead:
              3            //       Increase by 3
             :j<8?         //      Else-if the length is 7 instead:
              5            //       Increase by 5
             :             //      Else (the length is above 7):
              11           //       Increase by 11
            :              //     Else (the flag is 1 - thus the String is not unique):
             0;            //      Leave it the same by increasing with 0
  return r;}               //  Return the resulting integer-array

```

# Answer
> 1 votes
# R, 117 bytes

A completely different approach from the other R answer:

```
function(L)sapply(L,function(x)sum(c(0:3,5,11)[cut(nchar(x[x%in%names(which(table(unlist(L))<2))]),c(0,2,4:7,Inf))]))

```

Test cases:

```
> f=function(L)sapply(L,function(x)sum(c(0:3,5,11)[cut(nchar(x[x%in%names(which(table(unlist(L))<2))]),c(0,2,4:7,Inf))]))
> L=list(c("cat","dog","bird","elephant"),c("bird","dog","coyote"),c("dog","mouse"))
> f(L)
[1] 12  3  2
> L=list(c("abc","def","ghi"),c("ghi","def","abc"))
> f(L)
[1] 0 0
> L=list(c("programming","puzzles"),c("code","golf"),c())
> f(L)
[1] 16  2  0

```

Takes the names occurring only once in the list, convert their length to a factor based on the given cut-off points and translates that into scores that is then summed.

# Answer
> 1 votes
# K (ngn/k), 34 bytes

```
{+/'(&7\5782020)'#''x^\:&1<#'=,/x}

```

Try it online!

* `&1<#'=,/x` get non-unique words (i.e. words that more than one player identified)
* `x^\:` remove the non-unique words from each player's submission
* `#''` get the number of characters in each players' words
* `(&7\5782020)` a compressed version of `0 3 5 6 7 7 8 8 8 8 8 8`
* `(...)'` do a binary search, returning the index of the first value in the left-side list not larger than each item in the right-side list (this translates word lengths to their scores)
* `+/'` get each player's point total (by summing the score of their individual words)

# Answer
> 0 votes
# Perl 5, 104 + 2 (-na) = 106 bytes

```
push@a,[@F];map$k{$_}++,@F}{map{$s=0;map$s+=(($l=y///c)<8?$l<7?$l<5?1:$l-3:5:11)*($k{$_}<2),@$_;say$s}@a

```

Try it online!

# Answer
> 0 votes
## Clojure, 102 bytes

```
#(for[p %](apply +(for[w p](if(next(filter #{w}(flatten %)))0(get{3 1 4 1 5 2 6 3 7 5}(count w)11)))))

```

`next` returns `nil` if there is only one word `w` :)

# Answer
> 0 votes
# PHP, 226 bytes

```
function x($a){foreach($a as$p){$q=call_user_func_array('array_diff',$a);array_push($a,array_shift($a));$x=0;array_map(function($b)use(&$x){$b=strlen($b);$x+=($b<5?1:($b==5?2:($b==6?3:($b==7?5:11))));},$q);$o[]=$x;}return $o;}

```

I think this could still be trimmed down quite a bit.

Ungolfed:

```
function x($a) {
    foreach ($a as $p) {
        $q = call_user_func_array('array_diff', $a);
        array_push($a, array_shift($a));
        $x = 0;
        array_map(function($b) use (&$x){
            $b = strlen($b);
            $x += ($b < 5 ? 1 : ($b == 5 ? 2 : ($b == 6 ? 3 : ($b == 7 ? 5 : 11))));
        }, $q);
        $o[] = $x;
    }
    return $o;
}

```

Try it online!

# Answer
> 0 votes
# Scala, 242 bytes

The function takes, as a parameter `a`, a `Seq[Set[String]]` and returns an `Array[Int]`. I use an Array for it to be mutable (4-char loss).

```
var s=Seq("")
a.foreach(x=>x.foreach(y=>s:+=y))
var u:Array[Int]=Array()
var i= -1
a.foreach(t=>{i+=1
u:+=0
t.map(x=>{val l=x.length
if(s.count(_==x)<2){if(l>7)u(i)+=11
if(l==7)u(i)+=5
if(l==6)u(i)+=3
if(l==5)u(i)+=2
if(l>2&l<5)u(i)+=1}})})
u

```

Try it online!

Might be optimizable, since I did not even work on the

```
if(l>7)u(i)+=11
if(l==7)u(i)+=5
if(l==6)u(i)+=3
if(l==5)u(i)+=2
if(l>2&l<5)u(i)+=1

```

part. Thanks for this challenge!

# Answer
> 0 votes
# Swift 4, 164 bytes\*

```
{$0.map{Set($0).subtracting(Dictionary(grouping:$0.flatMap{$0},by:{$0}).flatMap{$1.count != 1 ?$0:nil}).map{[0,1,1,2,3,5,11][min(max($0.count-2,0),6)]}.reduce(0,+)}}

```

The above expression is technically correct, pure Swift. However, the expression is so complex that, due to exponential blowup in the type inference system, can't be processed before the compiler gives up after some arbitrary timeout (like 15s or something).

To make this expression compilable with the current compiler, it can be broken down like this:

```
{
let n = Dictionary(grouping:$0.flatMap{$0},by:{$0}).flatMap{$1.count != 1 ?$0:nil}
return $0.map{Set($0).subtracting(n).map{[0,1,1,2,3,5,11][min(max($0.count-2,0),6)]}.reduce(0,+)}
}

```

Test cases:

```
let f: (_ input: [[String]]) -> [Int] = {
    let n = Dictionary(grouping:$0.flatMap{$0},by:{$0}).flatMap{$1.count != 1 ?$0:nil}
    return $0.map{Set($0).subtracting(n).map{[0,1,1,2,3,5,11][min(max($0.count-2,0),6)]}.reduce(0,+)}
}

let testcases: [(input: [[String]], expected: [Int])] = [
    (input: [
            ["cat","dog","bird","elephant"],
            ["bird","dog","coyote"],
            ["dog","mouse"]
        ],
        expected: [12,3,2]
    ),
    (input: [
            ["abc","def","ghi"],
            ["ghi","def","abc"]
        ],
        expected: [0,0]
    ),
    (input: [
            ["programming","puzzles"],
            ["code","golf"],
            []
        ],
        expected: [16,2,0]
    ),
]

for (caseNumber, testcase) in testcases.enumerated() {
    let actual = f(testcase.input)
    assert(actual == testcase.expected,
        "Testcase #\(caseNumber) \(testcase.input) failed. Got \(actual), but expected \(testcase.expected)!")
    print("Testcase #\(caseNumber) passed!")
}

```

Broken down:

```
let verboseF: (_ input: [[String]]) -> [Int] = { playerHands in
    let allWords = playerHands.flatMap{$0}
    // demo data for first test case:
    // allWords: ["cat", "dog", "bird", "elephant", "bird", "dog", "coyote" "dog", "mouse"]

    let allWordsGroupedByThemselves = Dictionary(grouping: allWords, by: {$0})
    /* allWordsGroupedByThemselves:
    [
        "cat": ["cat"],
        "dog": ["dog", "dog", "dog"],
        "bird": ["bird", "bird"],
        "elephant": ["elephant"],
        "coyote": ["coyote"], "mouse": ["mouse"]
    ]*/

    let allWordsUsedMoreThanOnce = allWordsGroupedByThemselves.flatMap{$1.count != 1 ?$0:nil}
    // allWordsUsedMoreThanOnce: ["dog", "bird"]

    return playerHands.map{ hand in
        // demo data for first hand of first test case:
        // hand: ["cat","dog","bird","elephant"]

        let uniqueWordsInHand = Set(hand)
        // uniqueWordsInHand: ["cat","dog","bird","elephant"]

        let uniqueWordsInHandNotUsedByOthers = uniqueWordsInHand.subtracting(allWordsUsedMoreThanOnce)
        // uniqueWordsInHandNotUsedByOthers: ["cat", "elephant"]

        let wordLengths = uniqueWordsInHandNotUsedByOthers.map{$0.count}
        // wordLengths: [3, 8]

        let scores = wordLengths.map{ wordLength in
            return [0,1,1,2,3,5,11][min(max(wordLength-2, 0), 6)] //A look up table that maps word length to word score
        }
        //scores: [1, 11]

        let playerScore = scores.reduce(0,+)
        // playerScore: 12

        return playerScore
    }
}

```

# Answer
> 0 votes
# ASP \+ Python, 137 bytes

```
u(P,W):-1{p(_,W)}1;p(P,W).s(P,S):-S=#sum{@v(W):u(P,W)};p(P,_).#script(python)
def v(w):return[1,1,2,3,5,11][min(len(w.string),8)-3]#end.

```

Expects data formatted as:

```
p(1,("cat";"dog";"bird";"elephant")).
p(2,("bird";"dog";"coyote")).
p(3,("dog";"mouse")).

```

Needs clingo 5.2.1 with python support.

Ungolfed:

```
unique(P,W):- 1 { player(_,W) } 1 ; player(P,W).
score(P,S):- S = #sum{@value(W): unique(P,W)} ; player(P,_).
#script (python)
def value(word):
    return [1,1,2,3,5,11][min(len(word.string),8)-3]
#end.

```

The python function is heavily inspired from the python answer.

---
Tags: code-golf, string, array, boggle
---


title: Evaluate Conway chained arrow notation

text:
# Question
Title: Evaluate Conway chained arrow notation
## 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

```

# Answer
> 16 votes
# 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!

# Answer
> 7 votes
# 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.

```

# Answer
> 6 votes
# 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} $$

# Answer
> 5 votes
# APL (Dyalog Unicode), ~~57~~ ~~49~~ ~~48~~ 46 bytes

*Saved 8 bytes thanks to @Bubbler!*

```
{3>≢w←⍵↓⍨⊃⍸1≠⍵:*/⌽w⋄(∇(⊃w-1),,∘(2↓w))⍣(1⊃w)⊢1}

```

Try it online!

A monadic function that must be given the input in reverse. Now also requires zero-indexing. This is slightly different from Conway's definition, but I *think* it's equivalent. If anyone can find a more math-y proof, that'd be great.

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.

No one likes ones (and \\$X\to 1\\$ evaluates to \\$X\\$), so we first remove leading ones using `⍵↓⍨⊃⍸1≠⍵`. `⊃⍸1≠⍵` is the first () index where () there isn't a 1 (`1≠⍵`), and we drop () until that index. The result of that is assigned to `w` to reuse.

We can replace the first rule from here with the first three rules from the question. So if `w` has 0, 1, or 2 elements (`3>≢w`), we can fold over it with exponentiation (`*/⌽w`), because according to APL's rules, `*/x` is `x` and `*/⍬` ( is an empty set) is 1. We do have to reverse () `w` again, though, because it was reversed in the first place.

The second part of the function takes care of cases when `w` is in the form \\$X \to y \to (z+1)\\$. It's essentially \\$y\\$ applications of the function \\$\lambda a. X \to a \to z\\$, starting, with 1.

If \\$y\\$ and \\$z\\$ are both 1, then this becomes \\$X \to 1 \to 1\\$. Next iteration, `w` will be just \\$X\\$. If only \\$y\\$ is 1, then it becomes \\$X \to 1 \to z\\$. After that, it becomes \\$X \to 1 \to (z-1)\\$, then \\$X \to 1 \to (z-2)\\$, and so on until it reaches \\$X \to 1 \to 1\\$, which gives us \\$X\\$. So this satisfies the fifth rule in the question (\\$X \to 1 \to p = X\\$).

If \\$y\\$ is greater than 1, this becomes $$ X \to (X \to (... (X \to (X \to (1) \to z) \to z) ...) \to z) \to z\\ = X \to (X \to (... (X \to (X) \to z) ...) \to z) \text{ (by question's 5th rule)} $$ The second is Conway's definition (there are \\$y\\$ copies of \\$X\\$ and \\$y-1\\$ copies of \\$z\\$). In the first, there are \\$y\\$ copies of both \\$X\\$ and \\$z\\$.

# Answer
> 3 votes
# , 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.

# Answer
> 3 votes
# 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())
    }
}

```

# Answer
> 2 votes
# 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.

# Answer
> 2 votes
# 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!

# Answer
> 2 votes
# 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!

# Answer
> 2 votes
# Factor, 144 bytes

```
:: g ( x -- y )
x llength 3 < [ x 1 [ swap ^ ] foldl ]
[ x car 1 = [ x cdr g ]
[ 1 x cadr [ x cdr cdr cons x car 1 - swons g ] times ] if
] if ;

```

Try it online!

Takes a linked list in reverse order. Uses the algorithm described in user's APL answer.

Using linked lists is shorter than using arrays when the code involves a lot of dissection at the start (and you don't need sophisticated sequence operations):

```
first (5)              > car (3)
rest (4)               > cdr (3)
second (6) > 1 nth (5) > cadr (4)
prefix (6)             > cons (4)
swap prefix (11)       > swons (5)
unclip (6)             = uncons (6)
unclip swap (11)       > unswons (7)

```

### How it works

```
:: g ( x -- y )         ! Takes a list `x` and returns a number
  x llength 3 < [         ! If x has 2 or fewer numbers...
    x 1 [ swap ^ ] foldl    ! Reduce by ^ on reversed arguments
  ] [                     ! Otherwise `x` is in the form of `X->y->z`
    x car 1 = [           ! If z is 1...
      x cdr g               ! Remove z(=1) and recurse
    ] [                   ! Otherwise...
      1                     ! Setup the initial value of 1
      x cadr                ! Setup the loop count of y
      [ x cdr cdr cons      ! Build y':X
        x car 1 - swons g ] ! Build z-1:y':X
      times                 ! Iterate the above function y times to 1
    ] if
  ] if

```

# Answer
> 1 votes
# 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)

```

# Answer
> 1 votes
# 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.

# Answer
> 1 votes
# 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);
    }
}

```

# Answer
> 1 votes
# 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.

# Answer
> 1 votes
# Scala, ~~156~~ 141 bytes

```
val f:Seq[Int]=>Int={case x if x.size<3=>(x:\1.0)(math.pow(_,_))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.

I hate that `math.pow(_,_)` works but just `math.pow` would need the first argument to be a `Double`.

# Answer
> 1 votes
# 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!

---
Tags: code-golf, number
---