title: Molecules to Atoms

text:
# Question
Title: Molecules to Atoms
# The Challenge

Write a program that can break down an input chemical formula (see below), and output its respective atoms in the form `element: atom-count`.

---

# Input

Sample input:

```
H2O

```

Your input will always contain at least one element, but no more than ten. Your program should accept inputs that contain parentheses, which may be nested.

Elements in the strings will always match `[A-Z][a-z]*`, meaning they will always start with an uppercase letter. Numbers will always be single digits.

---

# Output

Sample output (for the above input):

```
H: 2
O: 1

```

Your output can be optionally followed by a newline.

---

# Breaking Down Molecules

Numbers to the right of a set of parentheses are distributed to each element inside:

```
Mg(OH)2

```

Should output:

```
Mg: 1
O: 2
H: 2

```

---

The same principle applies to individual atoms:

```
O2

```

Should output:

```
O: 2

```

---

And also chaining:

```
Ba(NO2)2

```

Should output:

```
Ba: 1
N: 2
O: 4

```

---

# Testcases

```
Ba(PO3)2
->
Ba: 1
P: 2
O: 6

C13H18O2
->
C: 13
H: 18
O: 2

K4(ON(SO3)2)2
->
K: 4
O: 14
N: 2
S: 4

(CH3)3COOC(CH3)3
->
C: 8
H: 18
O: 2

(C2H5)2NH
->
C: 4
H: 11
N: 1

Co3(Fe(CN)6)2
->
Co: 3
Fe: 2
C: 12
N: 12

```

# Scoreboard

For your score to appear on the board, it should be in this format:

```
# Language, Score

```

Or if you earned a bonus:

```
# Language, Score (Bytes - Bonus%)

```

```
function getURL(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:getURL(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),useData(answers)}})}function getOwnerName(e){return e.owner.display_name}function useData(e){var s=[];e.forEach(function(e){var a=e.body.replace(/<s>.*<\/s>/,"").replace(/<strike>.*<\/strike>/,"");console.log(a),VALID_HEAD.test(a)&&s.push({user:getOwnerName(e),language:a.match(VALID_HEAD)[1],score:+a.match(VALID_HEAD)[2],link:e.share_link})}),s.sort(function(e,s){var a=e.score,r=s.score;return a-r}),s.forEach(function(e,s){var a=$("#score-template").html();a=a.replace("{{RANK}}",s+1+"").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SCORE}}",e.score),a=$(a),$("#scores").append(a)})}var QUESTION_ID=58469,ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],answer_ids,answers_hash,answer_page=1;getAnswers();var VALID_HEAD=/<h\d>([^\n,]*)[, ]*(\d+).*<\/h\d>/;
```

```
body{text-align:left!important}table thead{font-weight:700}table td{padding:10px 0 0 30px}#scores-cont{padding:10px;width:600px}#scores tr td:first-of-type{padding-left:0}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="scores-cont"><h2>Scores</h2><table class="score-table"><thead> <tr><td></td><td>User</td><td>Language</td><td>Score</td></tr></thead> <tbody id="scores"></tbody></table></div><table style="display: none"> <tbody id="score-template"><tr><td>{{RANK}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SCORE}}</td></tr></tbody></table>
```

**Edit:** Square brackets are no longer a part of the question. Any answers posted before 3AM UTC time, September 23, are safe and will not be affected by this change.

# Answer
> 11 votes
# CJam, ~~59~~ 57 bytes

```
q{:Ci32/")("C#-"[ ] aC~* Ca C+"S/=~}%`La`-S%$e`{~": "@N}/

```

Try it online in the CJam interpreter.

### How it works

```
q             e# Read all input from STDIN.
{             e# For each character:
  :Ci         e#   Save it in C and cast to integer.
  32/         e#   Divide the code point by 32. This pushes
              e#   2 for uppercase, 3 for lowercase and 1 for non-letters.
  ")("C#      e#   Find the index of C in that string. (-1 if not found.)
  -           e#   Subtract. This pushes 0 for (, 1 for ), 2 for digits,
              e#   3 for uppercase letters and 4 for lowercase letters.

 "[ ] aC~* Ca C+"

 S/           e#   Split it at spaces into ["[" "]" "aC~*" "Ca" "C+"].
 =~           e#   Select and evaluate the corresponding chunk.
              e#     (   : [    : Begin an array.
              e#     )   : ]    : End an array.
              e#     0-9 : aC~* : Wrap the top of the stack into an array
              e#                  and repeat that array eval(C) times.
              e#     A-Z : Ca   : Push "C".
              e#     a-z : C+   : Append C to the string on top of the stack.
}%            e#
`             e# Push a string representation of the resulting array.
              e# For input (Au(CH)2)2, this pushes the string
              e# [[["Au" [["C" "H"] ["C" "H"]]] ["Au" [["C" "H"].["C" "H"]]]]]
La`           e# Push the string [""].
-             e# Remove square brackets and double quotes from the first string.
S%            e# Split the result at runs of spaces.
$e`           e# Sort and perform run-length encoding.
{             e# For each pair [run-length string]:
  ~           e#   Dump both on the stack.
  ": "        e#   Push that string.
  @N          e#   Rotate the run-length on top and push a linefeed.
}/            e#

```

# Answer
> 11 votes
# Python 3, 157 154 bytes

```
import re
s=re.sub
f=s("[()',]",'',str(eval(s(',?(\d+)',r'*\1,',s('([A-Z][a-z]*)',r'("\1",),',input()))))).split()
for c in set(f):print(c+":",f.count(c))

```

Try it online!

Only supports input using regular brackets.

Before creating the golfed solution using `eval` above I created this reference solution, which I found very elegant:

```
import re, collections

parts = filter(bool, re.split('([A-Z][a-z]*|\(|\))', input()))
stack = [[]]
for part in parts:
    if part == '(':
        stack.append([])
    elif part == ')':
        stack[-2].append(stack.pop())
    elif part.isdigit():
        stack[-1].append(int(part) * stack[-1].pop())
    else:
        stack[-1].append([part])

count = collections.Counter()
while stack:
    if isinstance(stack[-1], list):
        stack.extend(stack.pop())
    else:
        count[stack.pop()] += 1

for e, i in count.items():
    print("{}: {}".format(e, i))

```

# Answer
> 10 votes
# Pyth, 66 65 bytes

```
VrSc-`v::z"([A-Z][a-z]*)""('\\1',),"",?(\d+)""*\\1,"`(k))8j": "_N

```

Try it online!

Port of my Python answer. Only supports input using regular brackets.

# Answer
> 6 votes
# Python 3, 414 bytes

I hope that the order of the result doesn't count.

```
import re
t=input().replace("[", '(').replace("]", ')')
d={}
p,q="(\([^\(\)]*\))(\d*)","([A-Z][a-z]*)(\d*)"
for i in re.findall(q,t):t = t.replace(i[0]+i[1],i[0]*(1if i[1]==''else int(i[1])))
r=re.findall(p,t)
while len(r)>0:t=t.replace(r[0][0]+r[0][1],r[0][0][1:-1]*(1if r[0][1]==''else int(r[0][1])));r=re.findall(p,t)
for i in re.findall(q[:-5], t):d[i]=d[i]+1if i in d else 1
for i in d:print(i+': '+str(d[i]))

```

Try it online!

# Answer
> 6 votes
# JavaScript ES6, 366 bytes

```
function f(i){function g(a,b,c){b=b.replace(/[[(]([^[(\])]+?)[\])](\d*)/g,g).replace(/([A-Z][a-z]?)(\d*)/g,function(x,y,z){return y+((z||1)*(c||1))});return(b.search(/[[(]/)<0)?b:g(0,b)}return JSON.stringify(g(0,i).split(/(\d+)/).reduce(function(q,r,s,t){(s%2)&&(q[t[s-1]]=+r+(q[t[s-1]]||0));return q},{})).replace(/["{}]/g,'').replace(/:/g,': ').replace(/,/g,'\n')}

```

JS Fiddle: https://jsfiddle.net/32tunzkr/1/

I'm pretty sure this can be shortened, but I need to get back to work. ;-)

# Answer
> 6 votes
# SageMath, ~~156~~ 148 bytes

```
import re
i=input()
g=re.sub
var(re.findall("[A-Z][a-z]?",i))
print g("(\d+).(\S+)\D*",r"\2: \1\n",`eval(g("(\d+)",r"*\1",g("([A-Z(])",r"+\1",i)))`)

```

Try it online here (hopefully link will work, might need an online account)

Note: If trying online, you will need to replace `input()` with the string (e.g. `"(CH3)3COOC(CH3)3"`)

### Explanation

Sage allows you to simplify algebraic expressions, providing they are in the right format (see 'symbolic manipulation' of this link). The regexes inside the eval() basically serve to get the input string into the right format, for example something like:

```
+(+C+H*3)*3+C+O+O+C+(+C+H*3)*3

```

`eval()` will then simplify this to: `8*C + 18*H + 2*O`, and then it's just a matter of formatting the output with another regex substitution.

# Answer
> 5 votes
# Javascript (ES6), ~~286~~ 284

Not that much shorter than the other ES6 one but I gave it my best. Note: this will error out if you give it an empty string or most invalid inputs. Also expects all groups to have a count of more than 1 (ie, no `CO[OH]`). If this breaks any challenge rules, let me know.

```
a=>(b=[],c={},a.replace(/([A-Z][a-z]*)(?![0-9a-z])/g, "$11").match(/[A-Z][a-z]*|[0-9]+|[\[\(]/g).reverse().map(d=>(d*1==d&&b.push(d*1),d.match(/\(|\[/)&&b.pop(),d.match(/[A-Z]/)&&eval('e=b.reduce((f,g)=>f*g,1),c[d]=c[d]?c[d]+e:e,b.pop()'))),eval('g="";for(x in c)g+=x+`: ${c[x]}\n`'))

```

Uses a stack-based approach. First, it preprocesses the string to add `1` to any element without a number, ie `Co3(Fe(CN)6)2` becomes `Co3(Fe1(C1N1)6)2`. Then it loops through in reverse order and accumulates element counts.

```
a=>(
  // b: stack, c: accumulator
  b=[], c={},

  // adds the 1 to every element that doesn't have a count
  a.replace(/([A-Z][a-z]*)(?![0-9a-z])/g, "$11")

    // gathers a list of all the elements, counts, and grouping chars
    .match(/[A-Z][a-z]*|[0-9]+|[\[\(]/g)

    // loops in reverse order
    .reverse().map(d=>(

       // d*1 is shorthand here for parseInt(d)
       // d*1==d: true only if d is a number
       // if it's a number, add it to the stack
       d * 1 == d && b.push(d * 1),

       // if there's an opening grouping character, pop the last item
       // the item being popped is that group's count which isn't needed anymore
       d.match(/\(|\[/) && b.pop(),

       // if it's an element, update the accumulator
       d.match(/[A-Z]/) && eval('

         // multiplies out the current stack
         e = b.reduce((f, g)=> f * g, 1),

         // if the element exists, add to it, otherwise create an index for it
         c[d] = c[d] ? c[d] + e : e,

         // pops this element's count to get ready for the next element
         b.pop()
       ')
  )),

  // turns the accumulator into an output string and returns the string
  eval('
    g="";

    // loops through each item of the accumulator and adds it to the string
    // for loops in eval always return the last statement in the for loop
    // which in this case evaluates to g
    for(x in c)
      g+=x+`: ${c[x]}\n`
  ')
)

```

Fiddle

# Answer
> 5 votes
# Perl, ~~177~~ 172 bytes

171 bytes code + 1 byte command line parameter

Ok, so I may have got a *little* carried away with regex on this one...

```
s/(?>[A-Z][a-z]?)(?!\d)/$&1/g;while(s/\(([A-Z][a-z]?)(\d+)(?=\w*\W(\d+))/$2.($3*$4).$1/e||s/([A-Z][a-z]?)(\d*)(\w*)\1(\d*)/$1.($2+$4).$3/e||s/\(\)\d+//g){};s/\d+/: $&\n/g

```

Usage example:

```
echo "(CH3)3COOC(CH3)3" | perl -p entry.pl

```

# Answer
> 2 votes
## Mathematica, 152 bytes

```
f=TableForm@Cases[PowerExpand@Log@ToExpression@StringReplace[#,{a:(_?UpperCaseQ~~___?LowerCaseQ):>"\""<>a<>"\"",b__?DigitQ:>"^"<>b}],a_. Log[b_]:>{b,a}]&

```

The above defines a function `f` which takes a string as input. The function takes the string and wraps each element name into quotes and adds an infix exponentiation operator before each number, then interprets the string as an expression:

```
"YBa2Cu3O7" -> ""Y""Ba"^2"Cu"^3"O"^7" -> "Y" "Ba"^2 "Cu"^3 "O"^7

```

Then it takes the logarithm of that and expands it out (mathematica doesn't care, what to take the logarithm of :)):

```
Log["Y" "Ba"^2 "Cu"^3 "O"^7] -> Log["Y"] + 2 Log["Ba"] + 3 Log["Cu"] + 7 Log["O"]

```

and then it finds all occurrences of multiplication of a `Log` by a number and parses it into the form of `{log-argument, number}` and outputs those in a table. Some examples:

```
f@"K4(ON(SO3)2)2"
K   4
N   2
O   14
S   4

f@"(CH3)3COOC(CH3)3"
C   8
H   18
O   2

f@"Co3(Fe(CN)6)2"
C   12
Co  3
Fe  2
N   12

```

# Answer
> 1 votes
# Java, 827 bytes

```
import java.util.*;class C{String[]x=new String[10];public static void main(String[]a){new C(a[0]);}C(String c){I p=new I();int[]d=d(c,p);for(int i=0;i<10;i++)if(x[i]!=null)System.out.println(x[i]+": "+d[i]);}int[]d(String c,I p){int[]f;int i,j;Vector<int[]>s=new Vector();while(p.v<c.length()){char q=c.charAt(p.v);if(q=='(')s.add(d(c,p.i()));if(q==')')break;if(q>='A'&&q<='Z'){f=new int[10];char[]d=new char[]{c.charAt(p.v),0};i=1;if(c.length()-1>p.v){d[1]=c.charAt(p.v+1);if(d[1]>='a'&&d[1]<='z'){i++;p.i();}}String h=new String(d,0,i);i=0;for(String k:x){if(k==null){x[i]=h;break;}if(k.equals(h))break;i++;}f[i]++;s.add(f);}if(q>='0'&&q<='9'){j=c.charAt(p.v)-'0';f=s.get(s.size()-1);for(i=0;i<10;)f[i++]*=j;}p.i();}f=new int[10];for(int[]w:s){j=0;for(int k:w)f[j++]+=k;}return f;}class I{int v=0;I i(){v++;return this;}}}

```

Git repository w/ ungolfed source (not perfect parity, ungolfed supports multi-character numbers).

Been a while, figured I'd give Java some representation. Definitely not going to win any awards :).

# Answer
> 1 votes
## ES6, 198 bytes

```
f=s=>(t=s.replace(/(([A-Z][a-z]?)|\(([A-Za-z]+)\))(\d+)/,(a,b,x,y,z)=>(x||y).repeat(z)))!=s?f(t):(m=new Map,s.match(/[A-Z][a-z]?/g).map(x=>m.set(x,-~m.get(x))),[...m].map(([x,y])=>x+": "+y).join`\n`)

```

Where `\n` is a literal newline character.

Ungolfed:

```
function f(str) {
    // replace all multiple elements with individual copies
    // then replace all groups with copies working outwards
    while (/([A-Z][a-z]?)(\d+)/.test(str) || /\(([A-Za-z]+)\)(\d+)/.test(str)) {
        str = RegExp.leftContext + RegExp.$1.repeat(RegExp.$2) + RegExp.rightContext;
    }
    // count the number of each element in the expansion
    map = new Map;
    str.match(/[A-Z][a-z]?/g).forEach(function(x) {
        if (!map.has(x)) map.set(x, 1);
        else map.set(x, map.get(x) + 1);
    }
    // convert to string
    res = "";
    map.forEach(function(value, key) {
        res += key + ": " + value + "\n";
    }
    return res;
}

```

# Answer
> 1 votes
# Pip `-l`, ~~85~~ ~~77~~ 62 bytes

Takes the formula as a command-line argument, and uses the `-l` flag for proper output formatting.

```
_.": ".(_N Y(VaRl:XU+KXL`"&"`RXI`X&`R`[\d"][("]`{aJ'.}l))MUQy

```

Try it online!

The main trick is to transform the formula via regex replacements into a Pip expression. This, when eval'd, will do the repetition and resolve parentheses for us. We then post-process a bit to get the atom counts and format everything correctly.

Ungolfed, with comments:

```
                        a is command-line arg (implicit)
l:`[A-Z][a-z]*`         Regex matching element symbols
aR: l `"&"`             Replace each symbol in a with symbol wrapped in quotes
aR: XI `X&`             Add X before each number (XI is a regex matching integers)
aR: `[\d"][("]` {aJ'.}  Insert . between a digit or " and a ( or "
Y (Va)@l                Eval result, findall matches of l, and yank that list into y
_.": ".(_Ny) M UQy      Map function to y uniquified:
                        Each element, concatenated with ": ", concatenated with
                        the count of that element in y
                        Print that list, one element per line (implicit, -l flag)

```

Here's how the input `Co3(Fe(CN)6)2` is transformed:

```
Co3(Fe(CN)6)2
"Co"3("Fe"("C""N")6)2
"Co"X3("Fe"("C""N")X6)X2
"Co"X3.("Fe".("C"."N")X6)X2
CoCoCoFeCNCNCNCNCNCNFeCNCNCNCNCNCN

```

Then:

```
["Co" "Co" "Co" "Fe" "C" "N" "C" "N" "C" "N" "C" "N" "C" "N" "C" "N" "Fe" "C" "N" "C" "N" "C" "N" "C" "N" "C" "N" "C" "N"]
["Co" "Fe" "C" "N"]
[3 2 12 12]
["Co: 3" "Fe: 2" "C: 12" "N: 12"]

```

# Answer
> 1 votes
# Perl 5 `-MList::Util=pairmap -n`, 94 bytes

```
s/\(([^()]+?)\)(\d)/$1x$2/e&&redo;s/([A-Z][a-z]*)(\d?)/$k{$1}+=$2||1/ge;pairmap{say"$a: $b"}%k

```

Try it online!

# Answer
> 0 votes
# JavaScript (Node.js), 133 bytes

```
x=>x.replace(/[A-Z][a-z]*|\d+|./g,c=>d=[c<'/'?c<')'?'}':'{':+c?`for(_ in"${Array(-~c)}")`:`o.${c}=-~o.${c};`]+d,d='',o={})+eval(d)&&o

```

Try it online!

Would remain shorter than the existing ones using same old ECMAscript

---
Tags: code-golf, string, counting, chemistry
---


# Question
Title: Implement hyperexponentiation/tetration without the use of '^'
## The Challenge

Implement tetration (aka Power Tower or Hyperexponentiation) with the least amount of characters.

## The Conditions

* Don't use the 'power' operator or its equivalents (such as `pow(x,y)`, `x^y`, `x**y`, etc.)
* Input given as: `x y` (separated by a space)
* `x` is exponentiated by itself `y` times.
* Your method must be able to compute at least `4 3` (4 exponentiated by itself 3 times)

## The Scoring

* **Lowest score wins:** (# of characters)
* Bonus deduction if you do not use the multiplication operator (-5 points).
* No Speed/Memory requirements. Take as long as you want.

## Examples

```
x, 0 -> 1

2, 2 -> 2^2 = 4

2, 4 -> 2^(2^(2^2)) = 65536

4, 3 -> 4^(4^4) = 4^256 = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096

```

Open to suggestions/alterations/questions

# Answer
# J, score is 7 (12 chars - 5 points for avoiding multiplication)

`+/@$/@$~/@$~`

usage:

```
   4 +/@$/@$~/@$~ 3
1.34078e154
t=.+/@$/@$~/@$~  NB. define a function
   4 t 3
1.34078e154
   2 t 2
4

```

Just few nested folds:

* Using multiplication it would be `*/@$~/@$~`
* Using power it would be `^/@$~` where `$~` creates array, `/` is a fold function.
> 17 votes

# Answer
## Haskell, ~~87~~ 85 - 5 == 80 ~~82~~

```
import Data.List
t x=genericLength.(iterate(sequence.map(const$replicate x[]))[[]]!!)

```

Uses neither of exponentiation, multiplication or addition (!), just list operations. Demonstration:

```
Prelude> :m +Data.List
Prelude Data.List> let t x=genericLength.(iterate(sequence.map(const$replicate x[]))[[]]!!)
Prelude Data.List> t 2 2
4
Prelude Data.List> t 2 4
65536
Prelude Data.List> t 4 3

```

...
ahm... you didn't say anything about performance or memory, did you? But given enough billions of years and some petabytes of RAM, this would still yield the correct result (genericLength can use a bigInt to count the length of the list).
> 16 votes

# Answer
## GolfScript, ~~15~~ 18 chars

```
~])*1\+{[]+*{*}*}*

```

Yes, one of the `*`s is a multiplication operator (exercise: which one?) so I don't qualify for the 5 char bonus. Still, it's just barely shorter than Peter's solution.

This earlier 15-char version is otherwise the same, but produces no output when the second argument is 0. Thanks to r.e.s. for spotting the bug.

```
~])*{[]+*{*}*}*

```
> 13 votes

# Answer
## J, 16 19 12 characters

```
*/@$~/1,~$~/

```

or as a verb (17 characters):

```
h=:[:*/@$~/1,~$~/

```

usage:

```
   h 2 4
65536

```

or taking input from keyboard (24 27 20 characters):

```
*/@$~/1,~$~/".1!:1]1

```

with thanks to FUZxxl for pointing out my stupidity. :-)

**Explanation:**

J is read from right to left, so using `2 4`:

`/` is used to insert the verb `$~` between each pair of items in the list. `$~` takes the left item and shapes it `$` using the right item (the `~` reverses the arguments) - so this would be equivalent to `4 $ 2` which gives you a list of `2`s which is four items long `2 2 2 2`.

Now we append 1 to the list `1,~` and then do the same thing again; `/` insert a verb `*/@$~` between each pair of items in the list. This verb starts in the same way `$~` but this time it `/` inserts a `*` between each item of the newly generated list. The `@` just makes sure that the `*/@$~` works as one verb instead of two. This gives `2` multiplied by itself enough times to be equivalent to `2^4`.

J's vocabulary page \- I find solving problems with J fun just because of the different way it sometimes does things.

Adding one further iteration to remove the `*` operator has 2 problems

* It comes out at 17 characters (`+/@$~/,@$~/1,~$~/`) which, even with the -5 bonus, is too long
* It runs out of memory if the number gets too large so doesn't meet the requirement of being able to calculate `4 3`
> 10 votes

# Answer
## GolfScript (24 chars - 5 = 19 points)

```
~\1{1{0{+}?}?}{@\+@*}:?~

```

is insanely slow.

## (or 20 chars)

```
~\1{1{*}?}{@\+@*}:?~

```

is much faster.
> 8 votes

# Answer
## Python, 70

This uses nested `eval` calls, eventually producing a string `"a*a*a*a...*a"` which gets evaluated. Almost half of the score is wasted on getting the arguments... though I've noticed that a few other solutions don't bother with that.

```
a,b=map(int,raw_input().split())
exec"eval('*'.join('a'*"*b+'1'+'))'*b

```
> 6 votes

# Answer
# Br\**nfuck, 128-5=123 bytes

```
+<<+<<,<,[>[>+>>+<<<-]>[<+>-]>[>[>>+>+<<<-]>>>[<<<+>>>-]<<[>[>+>+<<-]>>[<<+>>-]<<<-]>[-]>[<<+>>-]<<<<-]>>[<<+>>-]+<[-]<<<<-]>>>.

```

Input is in the form of characters with code points of the numbers desired as inputs. Output is the same.

An explanation is ~~coming when I have the time~~ below. Do I get bonus points for not using exponentiation, multiplication, OR even addition?

```
Cell 3 (0-indexed) is the running total x.
This calculates the nth tetration of a.

+<<+<<,<,                                       Initialize tape with [n, a, 0, 1, 0, 1]
[                                               While n:
  >[>+>>+<<<-]>[<+>-]                             Copy a 3 cells to right: [n, a, 0, x, a, 1]
  >[                                              While x:
    >[>>+>+<<<-]>>>[<<<+>>>-]                       Copy a 2 cells to right: [n, a, 0, x, a, 1, a, 0]
    <<[>[>+>+<<-]>>[<<+>>-]<<<-]                    Cell 7 = prod(cell 5, cell 6)
    >[-]>[<<+>>-]<<<<-]                             Move this value to cell 5. End while.
  >>[<<+>>-]+<[-]<<<<-]                           Update x to result of exponentiation. End while.
>>>.                                            Print the result!

```

This works (tested) for `x 0`, `0 x`, `x 1`, `1 x`, `x 2`, `2 3`, and `2 4`. I tried `3 3`, but it ran for several hours without finishing (in my Java implementation—probably not optimal) (EDIT: in @Timwi's EsotericIDE \[It's great! Y'all should try it\] as well. No luck.). In theory, this works up to the cell size of the specific implementation.
> 6 votes

# Answer
### Scala:110

```
type B=BigInt
def r(a:B,b:B,f:(B,B)=>B):B=if(b>1)f(a,r(a,b-1,f))else a
def h(a:B,b:B)=r(a,b,r(_,_,r(_,_,(_+_))))

```

ungolfed:

```
type B=BigInt
def recursive (a:B, b:B, f:(B,B)=>B): B =
  if (b>1) f (a, recursive (a, b-1, f))
  else a
recursive (2, 3, recursive (_, _, recursive (_, _, (_ + _))))

```

explanation:

```
type B=BigInt
def p (a:B, b:B):B = a+b
def m (a:B, b:B):B = if (b>1) p (a, m (a, b-1)) else a
def h (a:B, b:B):B = if (b>1) m (a, h (a, b-1)) else a
def t (a:B, b:B):B = if (b>1) h (a, t (a, b-1)) else a

```

plus, mul, high(:=pow), tetration all work in the same manner. The common pattern can be extracted as recursive method, which takes two BigInts and a basic function:

```
def r (a:B, b:B, f:(B,B)=>B):B =
  if (b>1) f(a, r(a, b-1, f)) else a
r (4, 3, r (_,_, r(_,_, (_+_))))

```

The underlines are placeholder for something which gets called in this sequence, for example the addition plus(a,b)=(a+b); therefore (*+*) is a function which takes two arguments and adds them (a+b).

unfortunately, I get issues with the stack size. It works for small values for 4 (for example: 2) or if I reduce the depth for one step:

```
def h(a:B,b:B)=r(a,b,r(_,_,(_*_))) // size -7, penalty + 5
def h(a:B,b:B)=r(a,b,r(_,_,r(_,_,(_+_))))

```

The original code is 112 characters and would score, if valid, 107. Maybe I find out how to increase the stack.

The expanded algorithm can be transformed to tailrecursive calls:

```
type B=BigInt
def p(a:B,b:B):B=a+b
import annotation._
@tailrec
def m(a:B,b:B,c:B=0):B=if(b>0)m(a,b-1,p(a,c))else c
@tailrec
def h(a:B,b:B,c:B=1):B=if(b>0)h(a,b-1,m(a,c))else c
@tailrec
def t(a:B,b:B,c:B=1):B=if(b>0)t(a,b-1,h(a,c))else c

```

The tailrecursive call is longer than the original method, but didn't raise a stackoverflow in the long version - however it doesn't yield a result in reasonable time. t(2,4) is fine, but t(3,3) already was stopped by me after 5 min. However, it is very elegant, isn't it?

```
// 124 = 119-5 bonus
type B=BigInt
def r(a:B,b:B,c:B,f:(B,B)=>B):B=if(b>0)r(a,b-1,f(a,c),f)else c
def t(a:B,b:B)=r(a,b,1,r(_,_,1,r(_,_,0,(_+_))))

```

And now the same as above: use stinky multiplication (we even profit while rejecting the bonus of 5, because we save 7 characters: win=4 chars:)

```
// 115 without bonus
type B=BigInt
def r(a:B,b:B,c:B,f:(B,B)=>B):B=if(b>0)r(a,b-1,f(a,c),f)else c
def t(a:B,b:B)=r(a,b,1,r(_,_,1,(_*_)))

```

invocation:

```
timed ("t(4,3)")(t(4,3))
t(4,3): 1
scala> t(4,3)
res89: B = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096

```

runtime: 1ms.
> 5 votes

# Answer
## Ruby ~~66~~ 59 characters

```
def e(x,y)
r=1
(1..y).each{t=x
(2..r).each{t*=x}
r=t}
r
end

```
> 3 votes

# Answer
## Python, 161 - 5 (no * operator) = 156

```
r=xrange
def m(x,y):
 i=0
 for n in r(y):i+=x
 return i
def e(x,y):
 i=1
 for n in r(1,y+1):i=m(i,x)
 return i
def t(x,y):
 i=1
 for n in r(y):i=e(x,i)
 return i

```

invoke:

```
t(2, 4)

```
> 3 votes

# Answer
## Perl, 61 chars

here's a bizarre one

```
sub t
{
  ($x,$y,$z)=@_;
  $y>1&&t($x,$y-1,eval$x."*$x"x($z-1||1))||$z
}

```

usage:

```
print t(2,4,1)

```
> 3 votes

# Answer
## *Mathematica*, ~~40~~ 33

This doesn't quite conform to the rules but it is not in contention for the shortest code anyway, and I hope that it will be of interest to someone.

```
m@f_:=Fold[f,1,#2~Table~{#}]&;

m[m@Sum]

```

This builds a "tetration" function when it is run, but the arguments must be given in reverse order. Example:

```
m[m@Sum][3, 4]

```

> 1340780792994259709957402499820584612747936582059239337772356144372176 4030073546976801874298166903427690031858186486050853753882811946569946 433649006084096
> 3 votes

# Answer
## Haskell:  ~~58~~  51 chars, with or without multiplication.

```
i f x 1=x;i f x n=f$i f x$n-1
t=i(\o n->i(o n)n)(+)4

```

Ungolfed:

```
bump op n a = iterate (op n) n !! (fromIntegral $ a-1)
tetrate = iterate bump (+) !! 3

```

Shorter definition comes from inlining “bump”, and defining a custom version of “iterate”. Unfortunately the result is impossibly inefficient, but starting with (\*) instead of (+) gives decent speed. In `ghci`:

```
Prelude> let i f x 1=x;i f x n=f$i f x$n-1
(0.00 secs, 1564024 bytes)
Prelude> let t=i(\o n->i(o n)n)(*)3
(0.00 secs, 1076200 bytes)
Prelude> t 4 3
13407807929942597099574024998205846127479365820592393377723561443721764030073546
976801874298166903427690031858186486050853753882811946569946433649006084096
(0.01 secs, 1081720 bytes)

```
> 3 votes

# Answer
## Rockstar, 233 bytes

Rockstar is a quite new computer programming language, designed for creating programs that are also song lyrics. Rockstar is heavily influenced by the lyrical conventions of 1980s hard rock and power ballads.

The solution takes two inputs, one per each line (string manipulation is very limited). It uses multiplication operator, so no bonus to apply for :/

```
P takes A,B
N is 1
C is 1
While C is as low as B
Let N be N of A
Build C up

Give back N

T takes E,F
If F is empty
Give back 1
Else
Knock F down
Let G be T taking E,F
Give back P taking E,G

Listen to X
Listen to Y
Say T taking X,Y

```

Ungolfed, here's a more lyric version (comments are in parentheses, which are standard comments in Rockstar). Variable names may take up more words, and all words count ('my power' is different from 'the power' and from 'Power')

```
Power takes the force and the cross          (function def, two parameters: 'the force', 'the cross')
  Build my arm up                            ('my arm' := 1) (literally: 'my arm'++, but my arm was initialized with 0)
  Build my faith up                          ('my faith' := 1)
  While my faith is as weak as the cross     (While loop, condition: 'my faith' <= 'the cross')
    Let my arm be the force of my arm        ('my arm' := 'the force' * 'my arm' )
    Build my faith up                        ('my faith' ++ )
                                             (empty line to terminate While block)
  Give back my arm                           (return 'my arm')
                                             (empty line to terminate function block)
Tower takes the force and the enemy          (function def, two parameters: 'the force', 'the enemy')
  If the enemy is nowhere                    (If, condition: 'the enemy' == 0) (literally: 'the enemy' == NULL, but NULL is considered 0 in arithmetics)
    Build Victory up                         (Victory := 1, this is a bit diffeerent from the golfed version)
    Give back Victory                        (return Victory)
  Else                                       (else)
    Knock the enemy down                     ('the enemy' -- )
    Let the defense be Tower taking the force and the enemy ('the defense' := Tower ('the force', 'the enemy'))
    Give back Power taking the force and the defense        (return Power ('the force', 'the defense'))
                                             (empty line to terminate If block)
                                             (empty line to terminate Function block)
Listen to us                                 (input: 'us')
Listen to your enemy                         (input: 'your enemy')
Scream Tower taking us and your enemy        (output: Tower('us', 'your enemy'))

```
> 3 votes

# Answer
# JavaScript (Node.js), 41 bytes

*Have some BigInts*

```
a=>g=b=>b--?(P=n=>n--?a*P(n):1n)(g(b)):1n

```

Try it online!
> 3 votes

# Answer
# Jelly, 9 bytes - 5 (no multiplication) = 4

```
xxxS¥/¥@/

```

Try it online!

# Jelly, 6 bytes - 5 (no multiplication, but cheats by using the list product atom) = 1

```
xxP¥@/

```

Try it online!
> 3 votes

# Answer
## Python, 112 chars

The numbers should be the 1st and 2nd argument: `python this.py 4 3`
`**` operator not used.
`*` used. It's quite trivial to implement, exactly like `**`, but costs more than 5 chars.

```
import sys
p=lambda y:y and x*p(y-1)or 1
t=lambda y:y>1 and p(t(y-1))or x
x,y=map(long,sys.argv[1:])
print t(y)

```
> 2 votes

# Answer
## C, 117 105 99 chars

EDIT: Merged the two functions `p` and `r` into one, saving some chars.
Of 99 chars, 52 do the actual calculation (including variable definitions). The other 47 are for handling input and output.
BUG: Badly handles powers of 0 (e.g. `0 2`). Should find a minimum cost fix. This isn't a bug, I forgot that `0 2` is undefined.

Successfully handles `4 3`, and even gives an exact result. However, can be inaccurate for some smaller numbers.
Prints the number with a trailing `.000000`.

```
x,y,z;
double R(){return--y?!z?y=R(),R(z=1):x*R():x;}
main(){
    scanf("%d%d",&x,&y);
    printf("%f\n",R());
}

```
> 2 votes

# Answer
# VBA, 90 Chars

\*Perhaps the no multiplication bonus is not good enough. I think the no multiplication answer is much more interesting, but this is code golf, so it's not the best. Here's an answer without `*`, and a better (shorter, and better scoring) answer with it:

## 90 chars, no power operators, uses multiplication = 90

```
Sub c(x,y)
f=IIf(y,x,1):For l=2 To y:b=x:For j=2 To f:b=b*x:Next:f=b:Next:MsgBox f
End Sub

```

## 116 chars, no power operators, no multiplication bonus (-5) = 111

```
Sub c(x,y)
f=IIf(y,x,1):For l=2 To y:b=x:For j=2 To f:For i=1 To x:a=a+b:Next:b=a:a=0:Next:f=b:Next:MsgBox f
End Sub

```

**NOTE:** VBA has issues printing the number when the result is very large (i.e. `4, 3`), but it does calculate correctly, so if, for example, you wanted to USE that number, you would be good to go. Also, even BIGGER numbers overflow (i.e. `3, 4`).
> 2 votes

# Answer
## Factor, 187 characters

```
USING: eval io kernel locals math prettyprint sequences ;
IN: g
:: c ( y x o! -- v )
o 0 = [ x y * ] [ o 1 - o!
y x <repetition> 1 [ o c ] reduce ] if ;
contents eval( -- x y ) swap 2 c .

```

Before golf:

```
USING: eval io kernel locals math prettyprint sequences ;
IN: script

! Calculate by opcode:
!   0 => x * y, multiplication
!   1 => x ^ y, exponentiation
!   2 => x ^^ y, tetration
:: calculate ( y x opcode! -- value )
    opcode 0 = [
        x y *
    ] [
        ! Decrement the opcode. Tetration is repeated exponentiation,
        ! and exponentiation is repeated multiplication.
        opcode 1 - opcode!

        ! Do right-associative reduction. The pattern is
        !   seq reverse 1 [ swap ^ ] reduce
        ! but a repetition equals its own reverse, and 'calculate'
        ! already swaps its inputs.
        y x <repetition> 1 [ opcode calculate ] reduce
    ] if ;

contents eval( -- x y )         ! Read input.
swap 2 calculate .              ! Calculate tetration. Print result.

```

I did not remove the multiplication operator `*`. If I did so, then I would need to add some logic expressing that the sum of an empty sequence is 0, not 1. This extra logic would cost more than the -5 bonus.

---

*Rule breaker, 124 + 10 = 134 characters*

```
USING: eval kernel math.functions prettyprint sequences ;
contents eval( -- x y ) swap <repetition> 1 [ swap ^ ] reduce .

```

This program has a lower score, but the exponentiation operator `^` breaks the rules. The rules say "(# of characters) + (10 * (# of 'power' operators))", so I applied the +10 penalty. However, the rules also say "Don't use the 'power' operator", so any program taking this penalty does break the rules. Therefore, this program of 134 characters is not a correct answer, and I must present my longer program of 187 characters as my answer.
> 2 votes

# Answer
# Ruby, 47 46 45

`t=->x,n{r=x;2.upto(n){r=([x]*r).inject :*};r}`
> 2 votes

# Answer
## Haskell 110 - 5 = 105

Tetration Peano Style. This is the most insanely slow solution possible, just a warning, but also avoids even addition.

```
data N=Z|S N
a&+Z=a
a&+S b=S$a&+b
_&*Z=Z
a&*S b=a&+(a&*b)
_&^Z=S Z
a&^S b=a&*(a&^b)
_&>Z=S Z
a&>S b=a&^(a&>b)

```

This relies on you having the patience to type out Peano numbers (and won't show the answer, If you actually want to run it, add these few lines (90 chars):

```
f 0=Z
f a=S$f$a-1
t Z=0
t(S a)=1+t a
main=interact$show.f.(\[x,y]->x&>y).map(f.read).words

```
> 2 votes

# Answer
## Lua: 133 chars, multiplication-less

```
a,b=io.read():match"(%d+) (%d+)"a,b,ba=a+0,b+0,a for i=1,b-1 do o=1 for i=1,a do o=o+o for i=1,ba-b do o=o+o end end a=o end print(o)

```

I was originally going to use string repetition hacks to do fake multiplication, but it likes to fail on large values. I could possibly use dynamic compilation and loadstring to make it smaller, but it's getting late here... I need sleep.

Entering "4 3" into stdin outputs:

```
1.3407807929943e+154

```
> 2 votes

# Answer
# Perl 6, 32 bytes

```
->\a,\b{(1,{[*] a xx$_}...*)[b]}

```

Try it online!

`(1, { [*] a xx $_ } ... *)` is a lazy sequence that generates the power tower, each element being the a list which consists of the first input parameter `a` replicated (`xx`) a number of times equal to the previous element (`$_`), that list then being reduced with multiplication (`[*]`). From that sequence we simply pluck out the `b`-th element.
> 2 votes

# Answer
# Lambda calculus, 10-5

(using Church encoding and De Bruijn indeces)
`λλ(1λ13)λ1`

## Explanation

Without De Bruijn indeces: `λa,b.(b λc.ca)λc.c`:

```
λa,b.                                                 define the anonymous function f(a,b)=
     (b                                                apply the following function b times
        λc.                                                    the anonymous function g(c)=
           ca)                 apply c to a because of church encoding this is equal to a^c
              λc.c                              the identity function, 1 in church encoding

```

If you define `exp_a(x)=a^x` this program defines `a↑↑b=exp_a^b(1)` where `^b` denotes function itteration.

I'm not sure if this is allowed because `ca` is technically equivalent to `a^c` how ever it is not a real built-in and only a side effect of the way integers are encoded in lambda calculus.
> 2 votes

# Answer
**Python - 151 bytes**

```
Python 3.0:
r=range
def exp(a,b):
 if b=0:
  a=1
else:
 r1=a
 for i in r(1,b):
  s=s*a

def tet(a,b):
 r1=0
  if b=0:
   a=1
else:
 r1=a
 for i in range(1,b):
 r1=exp(a, result)

```

Here's how the new *new* version works.

1: Exponentiation is initialized (multiplies a by a b times), as well as tetration (in terms of our exp function).

2: a is stored in result of the tetration function.

3: Then we exponentiate a to result (as tetration does), and store that in result

4: Repeat step 3 b times.

Feel free to tell me I suck. (With *huge* credits to the commenters and Googology Wiki)
> 2 votes

# Answer
# Wolfram Language (Mathematica), 29 bytes

(27 characters)

```
aNest[Nest[a#&,1,#]&,1,#]&

```

Try it online!

Input curried as `f[x][y]`.

---

Without `*`: **35 bytes** (33 characters)

```
aa+#&~n~0~n~1~n~1
n=Nest~Curry~3

```

Try it online!
> 2 votes

# Answer
**Javascript: 116 chars**

```
function t(i){y=i.split(' ');a=y[0];b=y[1];return+b&&p(a,t(a+' '+(b-1)))||1}function p(a,b){return+b&&a*p(a,b-1)||1}

```

t('4 3') Outputs:

```
1.3407807929942597e+154

```
> 1 votes

# Answer
### Python ~~(111)~~ (113) no *

```
r=lambda x,y:(x for _ in range(y));t=lambda x,y:reduce(lambda y,x:reduce(lambda x,y:sum(r(x,y)),r(x,y)),r(x,y),1)

```

6\***3 \- 36k digits))

Upd: Have to add initial value, to fit t(X,0)=1
> 1 votes

# Answer
# Common Lisp, 85 chars

```
(lambda(b c)(let((r b)u)(dotimes(c c r)(setf u 1 r(dotimes(c b u)(setf u(* u r)))))))

```

I tried doing the multiplications through repeated addition, but it was way more than 5 characters. Same thing with macrolets, the declarations were not worth the gains.

Another solution, inspired by boothby's python solution. It's 1 character less than the above solution.

```
(lambda(a b)(eval`(*,@(loop for x below b nconc(loop for x below a nconc`(,a,a))))))

```
> 1 votes

# Answer
# Python 3 – 68

(including the 10-point penalty for the power operator)

```
a,b=input().split()
r=1
exec("r=%s**r;"%a*int(b))
print(r)

```
> 1 votes

# Answer
## Haskell: 88-5 chars without multiplication, 59 chars with multiplication

Without multiplication:

```
h x y=foldr(\x y->foldl(\x y->foldl(+)0(replicate x y))1(replicate y x))1(replicate y x)

```

There are probably ways that I could golf that down a little.

With multiplication:

```
h x y=foldr(\x y->foldl(*)1(replicate y x))1(replicate y x)

```

And finally, the ungolfed program:

```
mult x y = foldl (+) 0 (replicate x y)
expo x y = foldl (mult) 1 (replicate y x)
h x y = foldr (expo) 1 (replicate y x)

```

This is probably the simplest way to do this problem, which is defining multiplication as repeated addition, exponentiation as repeated multiplication, and tetration as repeated exponentiation.
> 1 votes

# Answer
# Racket 58 (no \*)

```
(define(t x y)(if(= y 0)1(for/product([i(t x(- y 1))])x)))

```
> 1 votes

# Answer
# Ruby, ~~43~~ 39 points

```
->a,b{c=1;eval"c=eval('a*'*~-c+?a);"*b}

```

Try it online

# Ruby, also ~~43~~ 39 points

```
t=->a,b{b<1?1:eval("a*"*~-t[a,b-1]+?a)}

```

Try it online

---

The following are no longer valid(?)

# Ruby, 26 + (1 power operation)\*10 points

```
t=->a,b{b<1?1:a**t[a,b-1]}

```

Try it online

# Ruby, 28 + (1 power operation)\*10 points

```
->a,b{c=1;b.times{c=a**c};c}

```

Try it online
> 1 votes

# Answer
# Yabasic, 71 bytes

A function that takes input `a` and `b` as a space delimited string.

```
Input""a,b
d=a^(b>0)
For i=2To b
c=a
For j=2To d
c=c*a
Next
d=c
Next
?d

```

Try it online!
> 1 votes

# Answer
# , 71 - 5 = 66 bytes

```
function(x,y,b=x){for(i in 2:y)b=cumprod(z<-rep(x,b))[sum(z|1)];cat(b)}

```

Try it online!

-5 for avoiding \*, which was harder than I expected. It explodes really fast and won't work (unless it had more memory) but it satisfies all necessary criteria.
> 1 votes

# Answer
# PHP, ~~139~~ 125 bytes

```
function f($x,$y){return gmp_strval($y?(function($x,$y){for($a=1;$i<$y;$i++)$a=gmp_mul($x,$a);return$a;})($x,f($x,$y-1)):1);}

```

Uses GMP library for the arbitrary-length math. It does compute the result instantly and able to solve 2\***5 as well.

The longer (198 bytes - 5 = 193) version that does not multiply:

```
function f($x,$y){return gmp_strval($y?(function($x,$y,$a=1){for(;$i<$y;$i++)$a=(function($x,$y){$a=0;for(;$i<gmp_intval($y);$i++)$a=gmp_add($x,$a);return$a;})($x,$a);return$a;})($x,f($x,$y-1)):1);}

```

Output Tests:

```
2, 0 -> 1
Exec time 0.00009513 seconds
2, 2 -> 4
Exec time 0.00006819 seconds
2, 4 -> 65536
Exec time 0.00002694 seconds
4, 3 -> 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
Exec time 0.00011992 seconds

```

If you were curious the result of 2\***5, here it is:

```
2, 5 -> [encoded data, 19729 characters]
Exec time 0.11125493 seconds

```
> 1 votes

# Answer
# APL(NARS), chars 46, bytes 92

```
{⍺ ⍺{(a b)←⍺⋄⍵≤1:{⍵:b⋄1}⍵⋄(a,a{×/⍵⍴⍺}b)∇⍵-1}⍵}

```

test:

```
  h←{⍺ ⍺{(a b)←⍺⋄⍵≤1:{⍵:b⋄1}⍵⋄(a,a{×/⍵⍴⍺}b)∇⍵-1}⍵}
  3 h 0
1
  2 h 2
4
  2 h 4
65536
  4 h 3
1.340780793E154

```

without the use of pow=`*` in APL where `⍵>0`; but i use multiplication `×`...
> 1 votes

# Answer
# APL (Dyalog Classic), 23 bytes

```
f←{⍵=0:1⋄⊃⌽{×/⍵⍴⍺}\⍵⍴⍺}

```

Try it online!
> 1 votes

# Answer
# JavaScript, 85 bytes

```
function(s){for(s=s.split(" "),a=b=s[0],i=0;++i<s[1];)for(j=a,a=b;--j;)a*=b;return a}

```

# JavaScript (ES6), 83 bytes

```
r=f=>(i,n,j=i)=>--n?j:r(f)(i,n,f(i,j));s=>r(r((a,b)=>a*b),(s=s.split(" "))[0],s[1])

```
> 1 votes

# Answer
# APL (Dyalog Unicode), ~~14~~ 12 bytes (SBCS)

```
f←(×/⍴⍨)/1,⍨⍴⍨

```

Try it online!

### Without multiplication, ~~19~~ 17 - 5 = 12

```
f←((+/⍴⍨)/⍴⍨)/1,⍨⍴⍨

```

Try it online!

This is practically the same thing as above, but much, much slower. This time, since we can't have multiplication either, there's `(+/⍴⍨)`.

### With exponentiation operator (`*`), 4 bytes

```
*/⍴⍨

```

Try it online!
> 1 votes

# Answer
# Whispers v3, \\$39 - 5 = 34\\$ bytes

```
> Input
> Input
>> 1↑↑2
>> Output 3

```

This uses the tetration builtin
> 1 votes

# Answer
# Perl 5 `-Mbigint -pa`, ~~51~~ 46 bytes

```
for$i(0..<>){$_=1;for$b(1..$e){$_*="@F"}$e=$_}

```

Try it online!
> 1 votes

# Answer
# \[Wolfram Language (Mathematica)\], 114 bytes

Obviously nowhere near shortest, but points for supporting all hyperoperations, and no `*`?

```
h[n_,a_,b_]:=Which[n==0,b+1,b!=0,h[n-1,a,h[n,a,b-1]],n==1,a,n==2,0,True,1]
h[4,##&@@FromDigits/@StringSplit@#]&@"3 2"

```

(yields 3^3 = 27).
> 1 votes

# Answer
# Javascript (ES6), 24 + 10 bytes:

`h=(a,n)=>n?a**h(a,--n):1`

# Without \**, 50 bytes:

`e=(n,p)=>p?e(n,--p)*n:1;h=(a,n)=>n?e(a,h(a,--n)):1`

# Without \*, 77 - 5 bytes:

`m=(n,p)=>p?n+m(n,--p):0;e=(n,p)=>p?m(e(n,--p),n):1;h=(a,n)=>n?e(a,h(a,--n)):1`

There's got to be a better way to do this than create recursive helpers, but until then...

h is the main function, the others are recursive helpers.
> 0 votes

# Answer
In Python 3:

```
pow = 1
for i in range(n):
   pow=pow**a

```

where a is the base and n is the height
> 0 votes

# Answer
# TI-Basic, 27 - 5 = 22 bytes

```
Prompt X,Y
1
For(I,1,Y
prod(seq(X,J,1,Ans
End
Ans

```

There's no multiplication operator, but there is `prod(`. Takes two separate inputs. Output is stored in `Ans` and is displayed.
> 0 votes

---
Tags: code-golf, math, restricted-source
---


title: Don't output the file

text:
# Question
Title: Don't output the file
This `rar` file, when decompressed, gives a 65024-byte `exe` file. Requiring you to output the contents of that file would be absolutely no fun.

But you aren't required to do that. Actually, you're to do something opposite: Output a binary of the same length (65024 bytes), such that no byte equals the byte at same position in the source `exe` file.

This is code-golf, shortest code wins.

# Answer
# BQN, 81 bytesSBCS

```
•Out 65024↑1042/"#?ZY>Rg*778c0?74h3g)G?mm5963!1[!1OC+VUb)7]#Z-%&N/D^sUrJaVwc}%! "

```

Try it online! This is written for CBQN, I removed the `•Out`  to run it online.

If you split the binary into chunks of 1042, in each chunk at least one printable different from `"` is missing. Search program:

```
pa ← @-˜'"'⊸≠⊸/' '+↕95
b ← @-˜•FBytes "fr08v101.exe"
m ← ⊑⌽1000+/{⊑∧´¬∧˝pa∊⌜<˘↑‿⥊b}¨ 1000+↕1000
•Show m
•Show @+⊑⟜pa¨ ⊑∘/˘⍉¬pa∊⌜<˘↑‿m⥊b

```
> 6 votes

# Answer
# Pyth, ~~55~~ 51 bytes

```
<3s*L1586"iýy±å7Ë±â7a£Õ§³mh79B!OÈwc7wÝ%'÷î3awo÷c#

```

Try it online!

```
         "iýy±å7Ë±â7a£Õ§³mh79B!OÈwc7wÝ%'÷î3awo÷c#    41-character string literal
   *L1586                                            repeat each character 1586 times
  s                                                  concatenate
<3                                                   remove the last 3 characters
                                                     output with a trailing newline

```

(Use the `PYTHONIOENCODING=latin1` environment variable for correct binary output.)
> 4 votes

# Answer
# Charcoal, 339 bytes

```
ＵＴＩ⪪”}⊞➙×Ｔμ[j…｜U◨{Ｕ⁸→º4Ｄ›⮌⪫ιaＹh⎇E"6ºρ⌊mＭＯk…÷›ＧF⭆B↨⬤U↙⊕✳…Ｈd¶5‖Ｏ$¬÷Ｇ≕6ＴχSυ⟧⌈◨~a3j'▷↘3⊖À⁷0r]e⎇⁻≔s＆g>▶r↔⊗⁰ηχκη↔S1hLΦ⍘⦄⪪⊕«⪪⊙M»nＰＯgbＯ\XＫÀ›'◨‽⬤κ➙›\p；▶⸿⁴P÷χ>Ie…Ｅσ/Ｎ⟲Ｂ÷«～υ⟧χ9✂‽G⁶⦄⁷τＨ¿Þ₂⊘ΦＷ4rO＆v×σIB⍘↔_﹪ηA⸿/?⊙/Ｊ¡lβ“K▷¬✂6τＢ﹪G▶﹪⁺%zÀτ(&7\`g⁷Ｃ↙¤⦄ïＧ↖0⪫ςj]nＱ#Ｗ¶ＪeM)⬤χ9c←@⁷S5w⌊#Ｕ；Ｎ⌕·NＳＮ1?Σ@s↖$Ｔ(⁵xd«Fαh▶º⌊0l⮌d⮌oＨ"=d=▷À⁰j¤q⊙⦃Oε↥∧ψ�¬&≧↷cy/⊞⁴GE»¦≔✳κ¦'⁶↘S⎚ü]₂Ｑ”¶

```

Try it online! Link is to verbose version of code. Explanation: Charcoal is very good at printing lots of `-` signs. The compressed strings represents all the runs of non-`-`-signs in the file. Each run of `-`s is separated by a newline, thus ensuring that no character of the output matches a character in the file.

```
ＵＴ

```

Turn off Charcoal's default rectangular output, since we don't want space padding.

```
Ｉ⪪...¶

```

Split the compressed string `1041\n97...104\n2031` on newlines (they are the golfiest separators), and cast the numbers to integer, which causes Charcoal to output them as that number of `-` signs.

A "port" of @ovs's answer is only 90 bytes:

```
⭆“"jＶXＷ⬤tＯ#^S0➙↷⊟Li§Ｋ″1·β℅±d74%;{ESＭ»ΠⅈρξDςΦcＳEenÞ⁻.⁷¡ê；q¬⟧l﹪Π0№Σ″≔Ｘ⁼·⁶d´Z»～⪪Ｖ⎚+⪪ÀkＯ”×ι⁵¹²

```

Try it online! Link is to verbose version of code. Explanation: Simply repeats each character in the compressed string 512 times (I used this instead of @ovs' 1042 because it's a factor of 65024 and larger factors end up covering all of printable ASCII). Conveniently all the characters needed are in Charcoal's "symbols" area which allows the string to be compressed from 127 to 84 bytes. (It's not possible to do this with all letters (either upper or lower case) or all digits.)
> 3 votes

# Answer
# JavaScript (ES10), 131 bytes

Returns an array of bytes.

```
_=>[..."hx53ptn9mgv1xij4xcw506nhi1cxi7w116o3kntsesafc5xwy4w15u6bo7ulphwt"].flatMap(v=>Array(1016).fill(n-=parseInt(v,36)-17),n=187)

```

Try it online!

### How?

This encodes 64 bytes \\$b\_0\\$ to \\$b\_{63}\\$ that are repeated 1016 times each and do not appear in the corresponding chunk of the original file:

```
187,171,183,197,189,177,171,179,174,175,161,177,161,160,158,171,
155,160,145,157,174,185,179,179,178,194,199,183,182,192,177,193,
209,220,213,227,224,218,206,195,198,187,194,196,201,213,197,182,
165,178,163,179,191,178,189,195,188,198,185,181,173,173,158,146

```

The values were chosen in such a way that \\$|b\_k-b\_{k-1}|\<18\\$ for each \\$k\>0\\$, which allows to store the delta values in base 36.
> 2 votes

# Answer
# 05AB1E, ~~260~~ ~~70~~ 69 bytes

*-1 thanks to Kevin Cruijssen.*

```
•Ý=£ë—ÛāR5Bf·½"¨ß¡˜v`₆BÌÝΩ\∞?ΓтJ&тƒFćO#'œ|Ć‹RÞ¼Á,нìçD|•Ƶ?вŽ4´δи˜Ž3ć(£

```

Try it online! Outputs as a list of byte values. Alternative link for text output.

# Explanation

Similarly to other answers here, this answer uses equal-sized chunks (except the last chunk), each consisting of the same byte throughout the entire chunk (but different bytes throughout the entire output). To get an optimal score, maximizing the chunk size is important – or rather, minimizing the number of chunks.

To do this, I iterated through chunk sizes, starting from \\$1{,}000\\$ and going up. With each iteration, I checked if every byte value was present at least once in at least one chunk.

This happened at \\$1{,}200\\$ bytes per chunk. This meant that each chunk but the last can be up to \\$1{,}199\\$ bytes, with the last chunk being \\$278\\$ bytes. This means there are \\$54\\$ full chunks plus the small chunk at the end, making a total of \\$55\\$ chunks.

Let's verify this: \\$54×1{,}199+278=65{,}024\\$.

Finally, for each chunk, we find the smallest byte that doesn't exist there and repeat it for the length of that chunk, and we're done!
> 1 votes

# Answer
# JavaScript (Node.js), 74 bytes SBCS

```
_=>"[-!^7q7hŒƒŽÏ³á»±™{3Ž³îg}GÅc¬ïn·×O~v#¹›½+:[¦w".repeat(1414).slice(20)

```

Try it online!

I'm not sure if this happen for random enough file, or why you use `aaaabbbbccccdddd` rather than `abcdabcdabcdabcd` even for languages with better support for the latter solution
> 1 votes

# Answer
PHP (276 chars)

```
for($d=[-17,-532,-95,-515,-79,463,95,-392,-27,148,$i=-1,808,53,61,15,-665,-5,419,-29,211,46,399,95,569,11,-2,101,-588,11,418,-43,-70,-48,-1887,105,918,-63,-1655,-97,-317,-104,-116,-74,513,53,885,-97,605,150,593,20,-295];++$i<52;)echo str_repeat(chr(150-$d[$i]),2500-$d[++$i]);

```

Try it Online *(using an URL shortener to store the **.exe** file)*

If GMP is available it's **206 chars** long :

```
for($d=str_split(($i=0).gmp_init('1FmB6eDs41MlblmT1hchbcMok3RFjcIJ7OHt8hphdLMPDPgigsPrqHXfc3QEFotYuvL9zfZ3y7ZYkD7nnoSCgAzgJhHEVnl9R6mB5cshIudtpnunsccV',62),4);$i<52;)echo str_repeat(chr($d[$i++]),$d[$i++]);

```

**How is generated this sequence of str\_repeat ?**

Just by the output of strcspn.

```
<?php
$data = file_get_contents('raw_file');
$file_length = strlen($data);
$ptr = 0;
while ($ptr < $file_length) {
    $max_dist = $max_ord = 0;
    for ($i = 0; $i < 256; ++$i) {
        $char = chr($i);
        $dist = strcspn($data, $char, $ptr);
        if ($dist > $max_dist) {
            $max_dist = $dist;
            $max_ord = $i;
        }
    }
    $ptr += $max_dist;
    echo ".str_repeat(chr($max_ord), $max_dist)";
}

```
> 0 votes

---
Tags: code-golf, kolmogorov-complexity, open-ended-function
---


title: Generate all groupings

text:
# Question
Title: Generate all groupings
Let's define a **grouping** as a flat list, which is either:

* just `0`
* 2 groupings followed by the literal integer `2`
* 3 groupings followed by `3`
* 4 groupings followed by `4`
* etc. (for all integers \\$ \ge 2 \\$)

Note that `1` is not included in this definition, because otherwise groupings could be infinite.

For example, these are valid groupings:

* `0`
* `0 0 2`
* `0 0 0 3`
* `0 0 0 2 2`
* `0 0 0 0 0 2 3 0 0 0 4 2 0 2`

If it helps, here is a more visual representation of the last two groupings above, using parentheses to show how they're constructed:

```
(0 ((0 0) 2) 2)
((0 ((0 0 (0 0 2) 3) 0 0 0 4) 2) 0 2)

```

## Task

Given a positive integer `n`, output all possible **groupings** which contain exactly `n` `0`s.

For example, for `n = 3`, there are 3 possible groupings:

* `0 0 0 3`
* `0 0 0 2 2`
* `0 0 2 0 2`

## Rules

## Test cases

```
input -> outputs
1 -> [0]
2 -> [0 0 2]
3 -> [0 0 0 2 2], [0 0 0 3], [0 0 2 0 2]
4 -> [0 0 0 0 2 2 2], [0 0 0 0 2 3], [0 0 0 0 3 2], [0 0 0 0 4], [0 0 0 2 0 2 2], [0 0 0 2 0 3], [0 0 0 2 2 0 2], [0 0 0 3 0 2], [0 0 2 0 0 2 2], [0 0 2 0 0 3], [0 0 2 0 2 0 2]
5 -> [0 0 0 0 0 2 2 2 2], [0 0 0 0 0 2 2 3], [0 0 0 0 0 2 3 2], [0 0 0 0 0 2 4], [0 0 0 0 0 3 2 2], [0 0 0 0 0 3 3], [0 0 0 0 0 4 2], [0 0 0 0 0 5], [0 0 0 0 2 0 2 2 2], [0 0 0 0 2 0 2 3], [0 0 0 0 2 0 3 2], [0 0 0 0 2 0 4], [0 0 0 0 2 2 0 2 2], [0 0 0 0 2 2 0 3], [0 0 0 0 2 2 2 0 2], [0 0 0 0 2 3 0 2], [0 0 0 0 3 0 2 2], [0 0 0 0 3 0 3], [0 0 0 0 3 2 0 2], [0 0 0 0 4 0 2], [0 0 0 2 0 0 2 2 2], [0 0 0 2 0 0 2 3], [0 0 0 2 0 0 3 2], [0 0 0 2 0 0 4], [0 0 0 2 0 2 0 2 2], [0 0 0 2 0 2 0 3], [0 0 0 2 0 2 2 0 2], [0 0 0 2 0 3 0 2], [0 0 0 2 2 0 0 2 2], [0 0 0 2 2 0 0 3], [0 0 0 2 2 0 2 0 2], [0 0 0 3 0 0 2 2], [0 0 0 3 0 0 3], [0 0 0 3 0 2 0 2], [0 0 2 0 0 0 2 2 2], [0 0 2 0 0 0 2 3], [0 0 2 0 0 0 3 2], [0 0 2 0 0 0 4], [0 0 2 0 0 2 0 2 2], [0 0 2 0 0 2 0 3], [0 0 2 0 0 2 2 0 2], [0 0 2 0 0 3 0 2], [0 0 2 0 2 0 0 2 2], [0 0 2 0 2 0 0 3], [0 0 2 0 2 0 2 0 2]
6 -> [0 0 0 0 0 0 2 2 2 2 2], [0 0 0 0 0 0 2 2 2 3], [0 0 0 0 0 0 2 2 3 2], [0 0 0 0 0 0 2 2 4], [0 0 0 0 0 0 2 3 2 2], [0 0 0 0 0 0 2 3 3], [0 0 0 0 0 0 2 4 2], [0 0 0 0 0 0 2 5], [0 0 0 0 0 0 3 2 2 2], [0 0 0 0 0 0 3 2 3], [0 0 0 0 0 0 3 3 2], [0 0 0 0 0 0 3 4], [0 0 0 0 0 0 4 2 2], [0 0 0 0 0 0 4 3], [0 0 0 0 0 0 5 2], [0 0 0 0 0 0 6], [0 0 0 0 0 2 0 2 2 2 2], [0 0 0 0 0 2 0 2 2 3], [0 0 0 0 0 2 0 2 3 2], [0 0 0 0 0 2 0 2 4], [0 0 0 0 0 2 0 3 2 2], [0 0 0 0 0 2 0 3 3], [0 0 0 0 0 2 0 4 2], [0 0 0 0 0 2 0 5], [0 0 0 0 0 2 2 0 2 2 2], [0 0 0 0 0 2 2 0 2 3], [0 0 0 0 0 2 2 0 3 2], [0 0 0 0 0 2 2 0 4], [0 0 0 0 0 2 2 2 0 2 2], [0 0 0 0 0 2 2 2 0 3], [0 0 0 0 0 2 2 2 2 0 2], [0 0 0 0 0 2 2 3 0 2], [0 0 0 0 0 2 3 0 2 2], [0 0 0 0 0 2 3 0 3], [0 0 0 0 0 2 3 2 0 2], [0 0 0 0 0 2 4 0 2], [0 0 0 0 0 3 0 2 2 2], [0 0 0 0 0 3 0 2 3], [0 0 0 0 0 3 0 3 2], [0 0 0 0 0 3 0 4], [0 0 0 0 0 3 2 0 2 2], [0 0 0 0 0 3 2 0 3], [0 0 0 0 0 3 2 2 0 2], [0 0 0 0 0 3 3 0 2], [0 0 0 0 0 4 0 2 2], [0 0 0 0 0 4 0 3], [0 0 0 0 0 4 2 0 2], [0 0 0 0 0 5 0 2], [0 0 0 0 2 0 0 2 2 2 2], [0 0 0 0 2 0 0 2 2 3], [0 0 0 0 2 0 0 2 3 2], [0 0 0 0 2 0 0 2 4], [0 0 0 0 2 0 0 3 2 2], [0 0 0 0 2 0 0 3 3], [0 0 0 0 2 0 0 4 2], [0 0 0 0 2 0 0 5], [0 0 0 0 2 0 2 0 2 2 2], [0 0 0 0 2 0 2 0 2 3], [0 0 0 0 2 0 2 0 3 2], [0 0 0 0 2 0 2 0 4], [0 0 0 0 2 0 2 2 0 2 2], [0 0 0 0 2 0 2 2 0 3], [0 0 0 0 2 0 2 2 2 0 2], [0 0 0 0 2 0 2 3 0 2], [0 0 0 0 2 0 3 0 2 2], [0 0 0 0 2 0 3 0 3], [0 0 0 0 2 0 3 2 0 2], [0 0 0 0 2 0 4 0 2], [0 0 0 0 2 2 0 0 2 2 2], [0 0 0 0 2 2 0 0 2 3], [0 0 0 0 2 2 0 0 3 2], [0 0 0 0 2 2 0 0 4], [0 0 0 0 2 2 0 2 0 2 2], [0 0 0 0 2 2 0 2 0 3], [0 0 0 0 2 2 0 2 2 0 2], [0 0 0 0 2 2 0 3 0 2], [0 0 0 0 2 2 2 0 0 2 2], [0 0 0 0 2 2 2 0 0 3], [0 0 0 0 2 2 2 0 2 0 2], [0 0 0 0 2 3 0 0 2 2], [0 0 0 0 2 3 0 0 3], [0 0 0 0 2 3 0 2 0 2], [0 0 0 0 3 0 0 2 2 2], [0 0 0 0 3 0 0 2 3], [0 0 0 0 3 0 0 3 2], [0 0 0 0 3 0 0 4], [0 0 0 0 3 0 2 0 2 2], [0 0 0 0 3 0 2 0 3], [0 0 0 0 3 0 2 2 0 2], [0 0 0 0 3 0 3 0 2], [0 0 0 0 3 2 0 0 2 2], [0 0 0 0 3 2 0 0 3], [0 0 0 0 3 2 0 2 0 2], [0 0 0 0 4 0 0 2 2], [0 0 0 0 4 0 0 3], [0 0 0 0 4 0 2 0 2], [0 0 0 2 0 0 0 2 2 2 2], [0 0 0 2 0 0 0 2 2 3], [0 0 0 2 0 0 0 2 3 2], [0 0 0 2 0 0 0 2 4], [0 0 0 2 0 0 0 3 2 2], [0 0 0 2 0 0 0 3 3], [0 0 0 2 0 0 0 4 2], [0 0 0 2 0 0 0 5], [0 0 0 2 0 0 2 0 2 2 2], [0 0 0 2 0 0 2 0 2 3], [0 0 0 2 0 0 2 0 3 2], [0 0 0 2 0 0 2 0 4], [0 0 0 2 0 0 2 2 0 2 2], [0 0 0 2 0 0 2 2 0 3], [0 0 0 2 0 0 2 2 2 0 2], [0 0 0 2 0 0 2 3 0 2], [0 0 0 2 0 0 3 0 2 2], [0 0 0 2 0 0 3 0 3], [0 0 0 2 0 0 3 2 0 2], [0 0 0 2 0 0 4 0 2], [0 0 0 2 0 2 0 0 2 2 2], [0 0 0 2 0 2 0 0 2 3], [0 0 0 2 0 2 0 0 3 2], [0 0 0 2 0 2 0 0 4], [0 0 0 2 0 2 0 2 0 2 2], [0 0 0 2 0 2 0 2 0 3], [0 0 0 2 0 2 0 2 2 0 2], [0 0 0 2 0 2 0 3 0 2], [0 0 0 2 0 2 2 0 0 2 2], [0 0 0 2 0 2 2 0 0 3], [0 0 0 2 0 2 2 0 2 0 2], [0 0 0 2 0 3 0 0 2 2], [0 0 0 2 0 3 0 0 3], [0 0 0 2 0 3 0 2 0 2], [0 0 0 2 2 0 0 0 2 2 2], [0 0 0 2 2 0 0 0 2 3], [0 0 0 2 2 0 0 0 3 2], [0 0 0 2 2 0 0 0 4], [0 0 0 2 2 0 0 2 0 2 2], [0 0 0 2 2 0 0 2 0 3], [0 0 0 2 2 0 0 2 2 0 2], [0 0 0 2 2 0 0 3 0 2], [0 0 0 2 2 0 2 0 0 2 2], [0 0 0 2 2 0 2 0 0 3], [0 0 0 2 2 0 2 0 2 0 2], [0 0 0 3 0 0 0 2 2 2], [0 0 0 3 0 0 0 2 3], [0 0 0 3 0 0 0 3 2], [0 0 0 3 0 0 0 4], [0 0 0 3 0 0 2 0 2 2], [0 0 0 3 0 0 2 0 3], [0 0 0 3 0 0 2 2 0 2], [0 0 0 3 0 0 3 0 2], [0 0 0 3 0 2 0 0 2 2], [0 0 0 3 0 2 0 0 3], [0 0 0 3 0 2 0 2 0 2], [0 0 2 0 0 0 0 2 2 2 2], [0 0 2 0 0 0 0 2 2 3], [0 0 2 0 0 0 0 2 3 2], [0 0 2 0 0 0 0 2 4], [0 0 2 0 0 0 0 3 2 2], [0 0 2 0 0 0 0 3 3], [0 0 2 0 0 0 0 4 2], [0 0 2 0 0 0 0 5], [0 0 2 0 0 0 2 0 2 2 2], [0 0 2 0 0 0 2 0 2 3], [0 0 2 0 0 0 2 0 3 2], [0 0 2 0 0 0 2 0 4], [0 0 2 0 0 0 2 2 0 2 2], [0 0 2 0 0 0 2 2 0 3], [0 0 2 0 0 0 2 2 2 0 2], [0 0 2 0 0 0 2 3 0 2], [0 0 2 0 0 0 3 0 2 2], [0 0 2 0 0 0 3 0 3], [0 0 2 0 0 0 3 2 0 2], [0 0 2 0 0 0 4 0 2], [0 0 2 0 0 2 0 0 2 2 2], [0 0 2 0 0 2 0 0 2 3], [0 0 2 0 0 2 0 0 3 2], [0 0 2 0 0 2 0 0 4], [0 0 2 0 0 2 0 2 0 2 2], [0 0 2 0 0 2 0 2 0 3], [0 0 2 0 0 2 0 2 2 0 2], [0 0 2 0 0 2 0 3 0 2], [0 0 2 0 0 2 2 0 0 2 2], [0 0 2 0 0 2 2 0 0 3], [0 0 2 0 0 2 2 0 2 0 2], [0 0 2 0 0 3 0 0 2 2], [0 0 2 0 0 3 0 0 3], [0 0 2 0 0 3 0 2 0 2], [0 0 2 0 2 0 0 0 2 2 2], [0 0 2 0 2 0 0 0 2 3], [0 0 2 0 2 0 0 0 3 2], [0 0 2 0 2 0 0 0 4], [0 0 2 0 2 0 0 2 0 2 2], [0 0 2 0 2 0 0 2 0 3], [0 0 2 0 2 0 0 2 2 0 2], [0 0 2 0 2 0 0 3 0 2], [0 0 2 0 2 0 2 0 0 2 2], [0 0 2 0 2 0 2 0 0 3], [0 0 2 0 2 0 2 0 2 0 2]

```

# Answer
# Haskell, 59 bytes

Returns a list of groupings in lexicographic order.

```
(!0)
0!1=[[]]
n!s=[k:g|k<-[0^n..s],k/=1,g<-(n-0^k)!(s+1-k)]

```

Try it online!

The possible groupings can be constructed from left to right if you keep track of two values: the remaining number of `0`s to place, and the number of currently open groupings. When all `0`s are placed and there is a single open grouping, we have constructed a valid output.

This is implemented by the function `(!)` which takes the number of `0`s as a left argument `n` and the open groupings as `s`. At each step we can insert a `0` if `n>0` and any integer in `[2..s]` to close multiple open groupings.

```
-- main function: (!) with 0 open groupings
(!0)
-- base case: no more 0s to place, a single grouping left
0!1=[[]]
-- k is the number to insert
-- 0^n == if n==0 then 1 else 0
n!s=[k:g|k<-[0^n..s],k/=1,g<-(n-0^k)!(s+1-k)]

```
> 8 votes

# Answer
# Wolfram Language (Mathematica), version 12.3.1, 44 bytes

```
Groupings[#,2~Range~#,Length/@#~Level~All&]&

```

Try it online!

Yes, Mathematica has a built-in for groupings.

But the version on TIO (Mathematica 12.0.1) gives the wrong result for input `1`. The version I'm using (Mathematica 12.3.1) works correctly.
> 7 votes

# Answer
# JavaScript (V8),  ~~77~~  76 bytes

Prints all groupings as comma-separated strings.

```
f=(n,s=0,g=0,h=k=>k|n>1?f(k?h(k-1)|n:n+--k,s+[,k+1],g-k):!g&&print(s))=>h(g)

```

Try it online!

### Commented

```
f = (                  // f is a recursive function taking:
  n,                   //   n = input
  s = 0,               //   s = output 'string' (initially the number 0)
  g = 0,               //   g = number of groupings - 1
  h = k =>             //   h = helper recursive function taking a counter k
    k | n > 1 ?        //     if k is not equal to 0 or n is greater than 1:
      f(               //       recursive call to f:
        k ?            //         if k is not equal to 0:
          h(k - 1)     //           do a recursive call to h with k - 1
          | n          //           and pass n unchanged (*)
        :              //         else:
          n + --k,     //           set k = -1 and decrement n
        s + [, k + 1], //         append a comma followed by k + 1 to s
        g - k          //         subtract k from g
                       //         (this actually increments g if k = -1)
      )                //       end of recursive call
    :                  //     else:
      !g && print(s)   //       print s if g = 0
) => h(g)              // initial call to h with k = g

```

*(\*) This relies on the fact that `h()` will always eventually return a zero'ish value. And that's why we use `!g && print(s)` rather than `g || print(s)`.*
> 5 votes

# Answer
# Charcoal, 47 bytes

```
Ｎθ⊞υ⟦⁰⟧ＦυＦ⁺…⁰‹№ι⁰θ…·²⁻ＬιΣι⊞υ⁺ι⟦κ⟧ＩΦυ⁼⁼№ι⁰θ⁻ＬιΣι

```

Try it online! Link is to verbose version of code. Explanation: A simplification of @ovs's method, where the number of `0`s to place is simply the desired number of `0`s minus the current number of `0`s, and the number of open groupings is the length minus the sum.

```
Ｎθ

```

Input the desired number of `0`s.

```
⊞υ⟦⁰⟧Ｆυ

```

Start a breadth first search with a single `0`. (I can't use an empty list because `Sum([])` isn't `0` in Charcoal.)

```
Ｆ⁺…⁰‹№ι⁰θ…·²⁻ＬιΣι

```

Loop over the concatenation of two ranges, one from `0` to whether more `0`s are needed (so either an empty range or a range containing just `0`), one from `2` to the difference between the length and the sum inclusive.

```
⊞υ⁺ι⟦κ⟧

```

Append the value to the grouping and push it to the search list.

```
ＩΦυ⁼⁼№ι⁰θ⁻ＬιΣι

```

Output those groupings with one grouping and the correct number of `0`s.
> 4 votes

# Answer
# Core Maude, 209 + 15 = 224 bytes

```
mod G is inc LIST{Nat}*(op size to{_]). ops({_})([_]): Nat ~> Nat . var A B
N :[Nat]. eq{N}=[N]N . eq 0 1 = 0 . eq[0]= nil . eq[s N]= 0[N]. crl A B N =>
A{A]B s sd(N,{A])if{A]> 1 /\{A]< N /\ A B =[{A B]]. endm

```

To get the list of groupings for \\$n\\$, run the following Maude command with the \\$G\\$ module loaded.

```
search{}=>* A .

```

The groupings will be the listed assignments to \\$A\\$. So, for example, for \\$n = 3\\$ run

```
search{3}=>* A .

```

(The bytes of this command — minus the bytes to specify \\$n\\$ — have been included in the total.)

### Example Session

```
Maude> search{1}=>* A .
search in G : {1} =>* A .

Solution 1 (state 0)
states: 1  rewrites: 4 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0

No more solutions.
states: 1  rewrites: 15 in 0ms cpu (0ms real) (~ rewrites/second)
Maude> search{2}=>* A .
search in G : {2} =>* A .

Solution 1 (state 0)
states: 1  rewrites: 4 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 2

No more solutions.
states: 1  rewrites: 128 in 0ms cpu (0ms real) (~ rewrites/second)
Maude> search{3}=>* A .
search in G : {3} =>* A .

Solution 1 (state 0)
states: 1  rewrites: 5 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 0 3

Solution 2 (state 1)
states: 2  rewrites: 181 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 2 0 2

Solution 3 (state 2)
states: 3  rewrites: 218 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 0 2 2

No more solutions.
states: 3  rewrites: 1467 in 1ms cpu (1ms real) (1467000 rewrites/second)
Maude> search{4}=>* A .
search in G : {4} =>* A .

Solution 1 (state 0)
states: 1  rewrites: 6 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 0 0 4

-- SNIP --

Solution 11 (state 10)
states: 11  rewrites: 4520 in 3ms cpu (3ms real) (1506666 rewrites/second)
A --> 0 0 0 0 2 2 2

No more solutions.
states: 11  rewrites: 15508 in 12ms cpu (12ms real) (1292333 rewrites/second)
Maude> search{5}=>* A .
search in G : {5} =>* A .

Solution 1 (state 0)
states: 1  rewrites: 7 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 0 0 0 5

-- SNIP --

Solution 45 (state 44)
states: 45  rewrites: 72386 in 42ms cpu (41ms real) (1723476 rewrites/second)
A --> 0 0 0 0 0 2 2 2 2

No more solutions.
states: 45  rewrites: 149258 in 59ms cpu (58ms real) (2529796 rewrites/second)
Maude> search{6}=>* A .
search in G : {6} =>* A .

Solution 1 (state 0)
states: 1  rewrites: 8 in 0ms cpu (0ms real) (~ rewrites/second)
A --> 0 0 0 0 0 0 6

-- SNIP --

Solution 197 (state 196)
states: 197  rewrites: 853311 in 216ms cpu (215ms real) (3950513 rewrites/second)
A --> 0 0 0 0 0 0 2 2 2 2 2

No more solutions.
states: 197  rewrites: 1340298 in 329ms cpu (328ms real) (4073854 rewrites/second)

```

### Ungolfed

```
mod G is
    inc LIST{Nat} * (op size to {_]) .

    ops ({_}) ([_]) : Nat ~> Nat .

    var A B N : [Nat] .

    eq {N} = [N] N .
    eq 0 1 = 0 .

    eq [0] = nil .
    eq [s N] = 0 [N] .

    crl A B N => A {A] B s sd(N, {A]) if {A] > 1 /\ {A] < N /\ A B = [{A B]] .
endm

```

This solution uses Maude's rewriting feature, where Maude will search using a rewrite system to find all solutions to an problem of the form \\$t\_1 \to\_R^\* t\_2\\$, or in this case, \\$\\{n\\} \to\_G^\* A\\$, where \\$\to\_G^\*\\$ means zero or more applications of rules in \\$G\\$, and \\$A\\$ is a variable (so essentially *any* term). The single rule picks a run of zeros and groups them, so Maude will explore every way of grouping starting from \\$\\{n\\} \approx\_G 0 \\; 0 \\, \cdots \\, 0 \\; n\\$.

We use odd function names (`{_}`, `[_]`, and `{_]`) to take advantage of Maude's odd tokenization rules. `{_}` creates the initial grouping; `[_]` produces a list of zeroes; `{_]` is the renamed `size` function for lists.
> 4 votes

# Answer
# Python, 100 bytes

```
f=lambda n:[k+j+R for i in range(1,n)for*j,J in f(i)for k in f(n-i)for R in[[J,2],[J+1]][:i]]or[[0]]
```

Attempt This Online!

### How?

One big recursive list comprehension. Conceptually: Cut off the tree's lefttmost branch (from the root node) and do recursion on both bits. Technicality: The right bit is the original tree with the left bit removed, while the left bit discards the root branch so as not to violate the no nonbranching nodes requirement. IOW, the left bit hangs one level lower than the right bit. Except when the original tree had only two root branches. Then both hang low.
> 3 votes

# Answer
# Curry (PAKCS), 63 bytes

```
(!0)
0!1=[]
n!s=anyOf[k:n!(s+1-k)|k<-[2..s]]?n>0&>0:(n-1)!(s+1)

```

Try it online!

Based on ovs's Haskell answer. There are two differences:

* The `^` operator is not supported by the Curry version on TIO.
* An expression in Curry can be **non-deterministic**, i.e. having multiple values at the same time. Here I define a non-deterministic function `f`, whose return values are all the possible groupings.

---

# Curry (PAKCS), 68 bytes

```
(([]:iterate g[0])!!)
g a=a++[0,2]
g(a++[b])|b>1=g a++[b]?a++[0,b+1]

```

Try it online!

Another non-deterministic function that returns all the possible groupings at the same time.
> 3 votes

# Answer
# JavaScript (Node.js), ~~86~~ 84 bytes

```
f=(n,x=[0],i=0)=>n?x.flatMap((_,j)=>j>i?[]:f(n-!j,[...u=x,j+=!!j],i-j+1)):i-1?[]:[u]

```

Try it online!
> 2 votes

# Answer
# Python3, 205 bytes:

```
f=lambda x:''.join(f(i)if list==type(i)else'0'for i in x)+str(l:=len(x))*(l>1)
def s(n,c=[]):
 if n:
  for i in[c+[0],*[[],[[0,c]]][j:=len(c)>1],*[[],[[c,0]]][j]]:
   yield from s(n-1,i)
 else:yield f(c)

```

Try it online!
> 2 votes

---
Tags: code-golf, array, combinatorics
---


title: Tron Light-Cycle KotH

text:
# Question
Title: Tron Light-Cycle KotH
Basically the tron light-cycle game as a king of the hill competition!

## Leaderboard

**Updated as of 2022-04-05**

```
#1) Player Avoid by Agent Biscutt

#2) Dodge West by Imanton1

#3) Space Finder by Spitemaster

#4) Blind Bot by TheSilican

```

Judge/Leaderboard Website

## The Game

Players will write bots that compete in a light-cycle tournament. A round of light-cycle starts with bots evenly spaced out along the edge of a rectangular play area:

```
+--------------------+
|    @          @    |
|                    |
|                    |
|                    |
|                    |
|                    |
|                    |
|    @          @    |
+--------------------+

```

Each turn, each bot simultaneously must choose one of 4 directions to step (N, E, S, or W). The "head" of the bot steps in that direction, and the space that was once occupied by the head becomes part of the "body".

```
+--------------------+
|    #         @#    |
|    @               |
|                    |
|                    |
|                    |
|                    |
|               @    |
|   @#          #    |
+--------------------+

```

The round ends as soon as one or more bots crash into a wall, or into the head or body of another bot (including its own body).

```
         *CRASH*
+-----------@--------+
|    #      #####    |
|    ###             |
|      #             |
|   @  @             |
|   #                |
|   #            @#  |
|   #           ###  |
|   ##          #    |
+--------------------+

```

The bot(s) that crashed into the wall will be eliminated, and a new round will start with new starting positions. Bots are eliminated each round, until only 1 bot remains.

**The leaderboard rankings are based on the order that the bots are eliminated.**

## Code / API

For ease of judging and creating the judge website, *submissions will be restricted to javascript*.

A bot is a javascript function with the following API:

```
(state) => {
  // state is an object with access to information about the game
  // bots can use the state to make decisions
  // bots return one of "N", "E", "S", "W"
  // e.g.:
  return "N";
}

```

The `state` parameter contains the following API calls:

* `state.getDim()`: Returns a `[w, h]` tuple of the width and height of the arena. e.g. `[20, 10]`
* `state.getSelf()`: Returns a `[x, y]` tuple of the current bot's head. e.g. `[3, 7]`
* `state.get(x, y)`: Given integers `x` and `y`, returns a string corresponding to what is currently on the map at (x, y)
    + `"#"` \- body of a bot, or out-of bounds of the map ("wall")
    + `"@"` \- head of a bot
    + `" "` \- empty cell
* `state.getBoard()`: Returns a 2d array of the entire map. `state.getBoard()[x][y]` is equivalent to `state.get(x, y)`

Coordinates: (0, 0) is the bottom-left corner of the playfield with x increasing to the right and y upwards.

## Code Submission

~~To make a bot submission, add your bot code to this GitHub repository with a pull request, in addition to posting an answer.~~

Edit: Opening a PR in GitHub is no longer necessary, simply post your submission here.

Each user may only make one submission, however you may freely edit your submission after posting.

# Answer
> 4 votes
# Space Finder

```
(state) => {
  const [x, y] = state.getSelf();
  let starts = [[x, y + 1, "N"], [x + 1, y, "E"], [x, y - 1, "S"], [x - 1, y, "W"]];
  let toSearch = starts.slice();
  toSearch = toSearch.filter(d => state.get(d[0], d[1]) == " ");
  let searched = [];
  let adjacent = [[0, 1], [1, 0], [0, -1], [-1, 0]];
  let dirs = {
    N: toSearch.find(s => s[2] == "N") ? 1 : 0,
    E: toSearch.find(s => s[2] == "E") ? 1 : 0,
    S: toSearch.find(s => s[2] == "S") ? 1 : 0,
    W: toSearch.find(s => s[2] == "W") ? 1 : 0
  };
  let active = {...dirs};
  // Determine the size of the spaces adjacent to each of the possible moves
  while (toSearch.length){
    active[toSearch[0][2]]--;
    adjacent.forEach(a => {
      if (!toSearch[0]) return;
      let loc = [toSearch[0][0] + a[0], toSearch[0][1] + a[1], toSearch[0][2]];
      let tile = state.get(loc[0], loc[1]);
      if (tile == " "){
        let prev = searched.find(s => s[0] == loc[0] && s[1] == loc[1]);
        if (prev){
          if (prev[2] == toSearch[0][2]){
            return;
          }
          dirs[toSearch[0][2]] = prev[2];
          searched.forEach(s => s[2] = s[2] == toSearch[0][2] ? prev[2] : s[2]);
          toSearch = toSearch.filter(d => d[2] != toSearch[0][2]);
          if (Object.values(dirs).filter(v => !isNaN(+v)).length == 2){
            toSearch = [null];
            return;
          }
          return;
        }
        searched.push(loc);
        toSearch.push(loc);
        dirs[loc[2]]++;
        active[loc[2]]++;
      } else if (tile == "@"){
        dirs[loc[2]] /= 2;
      }
    });
    toSearch.shift();
    if ((active.N == 0) + (active.E == 0) + (active.S == 0) + (active.W == 0) == 3){
      let key = Object.keys(active).find(k => active[k]);
      if (dirs[key] > Math.max(...Object.entries(dirs).filter(v => v[0] != key && !isNaN(+v[1])).map(v => v[1]))) break;
    }
  }
  // Pick the move with the largest space
  for (let key of Object.keys(dirs)){
    if (isNaN(+dirs[key])) dirs[key] = dirs[dirs[key]];
    if (isNaN(+dirs[key])) dirs[key] = dirs[dirs[key]];
  }
  let best = Math.max(...Object.values(dirs));
  let possible = Object.keys(dirs).filter(d => dirs[d] == best);
  // Pick the move with the fewest things adjacent to it
  if (possible.length > 1){
    let scores = {" ": 0, "#": 0, "@": 1};
    possible = possible.map(p => {
      let dir = starts.find(s => s[2] == p);
      return [p, adjacent.reduce((a, c) => a + scores[state.get(c[0] + dir[0], c[1] + dir[1])], 0)];
    });
    possible = possible.filter(p => p[1] == Math.min(...possible.map(p => p[1]))).map(p => p[0]);
  }
  return possible[0];
}

```

Space Finder checks each adjacent space to determine which is attached to the largest empty area. If it has multiple choices, it avoids other heads.

# Answer
> 3 votes
# Dodge West

```
(state) => {
        const [x, y] = state.getSelf();

        if (state.get(x - 1, y) === " " && !(state.get(x - 2, y + 0) === "@" || state.get(x - 1, y + 1) === "@" || state.get(x - 1, y - 1) === "@"))
            return "W";
        if (state.get(x, y + 1) === " " && !(state.get(x + 0, y + 2) === "@" || state.get(x + 1, y + 1) === "@" || state.get(x - 1, y + 1) === "@"))
            return "N";
        if (state.get(x, y - 1) === " " && !(state.get(x + 0, y - 2) === "@" || state.get(x + 1, y - 1) === "@" || state.get(x - 1, y - 1) === "@"))
            return "S";
        if (state.get(x + 1, y) === " " && !(state.get(x + 2, y + 0) === "@" || state.get(x + 1, y + 1) === "@" || state.get(x + 1, y - 1) === "@"))
            return "E";

        if (state.get(x - 1, y) === " ")
            return "W";
        if (state.get(x, y + 1) === " ")
            return "N";
        if (state.get(x, y - 1) === " ")
            return "S";
        if (state.get(x + 1, y) === " ")
            return "E";

        return "N";
    }

```

Much like 'Blind Bot', but tries to avoid head-on collisions by turning if another bot could collide with it. Tries to go West and hold on that side of the screen.

# Answer
> 1 votes
# Blind Bot

Bot that simply checks each of the 4 adjacent directions, and goes in the first direction that is empty. Just to get the ball rolling for now, I may or may not edit this submission in the future.

```
(state) => {
    const [x, y] = state.getSelf();
    if (state.get(x, y + 1) === " ") {
      return "N";
    } else if (state.get(x + 1, y) === " ") {
      return "E";
    } else if (state.get(x, y - 1) === " ") {
      return "S";
    } else if (state.get(x - 1, y) === " ") {
      return "W";
    }
    return "N";
  }

```

# Answer
> 0 votes
# Player Avoid

This bott simply tries to avoid collision with other bots. Also, runs east instead of north as default, just to spice things up.

```
(state) => {
    const [x, y] = state.getSelf();
    if (state.get(x + 1, y) === " " &&
  (state.get(x + 1, y+1) ===" " || state.get(x + 1, y-1) ===" ")
  && (state.get(x+1, y + 1) != "@" && state.get(x+1, y-1)!=  "@")
  && ((state.get(x-1, y + 1) != "@" && state.get(x-1, y-1)!=  "@") || state.get(x+2, y)=="#")
  && ((state.get(x+2, y + 2) != "@" && state.get(x+2, y-2)!=  "@"))
  && ((state.get(x-2, y + 2) != "@" && state.get(x-2, y-2)!=  "@"))
  && ((state.get(x+2, y + 2) != "@" && state.get(x+2, y-1)!=  "@"))
  && ((state.get(x-2, y + 2) != "@" && state.get(x-2, y-1)!=  "@"))
        && state.get(x+2, y)!="@"
       ) {
      return "E";
    } else if (state.get(x - 1, y) === " "
  && (state.get(x - 1, y+1) ===" " || state.get(x - 1, y-1) ===" ")
  && (state.get(x-1, y + 1) != "@" && state.get(x-1, y-1)!=  "@")
  && ((state.get(x+1, y + 1) != "@" && state.get(x+1, y-1)!=  "@") || state.get(x+2, y)=="#")
  && ((state.get(x+2, y + 2) != "@" && state.get(x+2, y-2)!=  "@"))
  && ((state.get(x-2, y + 2) != "@" && state.get(x-2, y-2)!=  "@"))
  && ((state.get(x+2, y + 2) != "@" && state.get(x+2, y-1)!=  "@"))
  && ((state.get(x-2, y + 2) != "@" && state.get(x-2, y-1)!=  "@"))

               && state.get(x-2, y)!="@"
              ) {
      return "W";
    }else if (state.get(x, y + 1) === " "
  && (state.get(x+1, y + 1) != "@" && state.get(x-1, y + 1)!=  "@")
  && state.get(x, y+2)!="@"
             ) {

                return "N";
    } else  if (state.get(x, y - 1) === " "
  && (state.get(x+1, y - 1) != "@" && state.get(x-1, y - 1)!=  "@")
  && state.get(x, y+2)!="@"
               ) {
               return "S";
    }

    if (state.get(x, y + 1) === " " && state.get(x, y + 2)!="@") {
      return "N";
    } else if (state.get(x + 1, y) === " " && state.get(x+2, y)!="@") {
      return "E";
    } else if (state.get(x, y - 1) === " " && state.get(x, y - 2)!="@") {
      return "S";
    } else if (state.get(x - 1, y) === " " && state.get(x-2, y)!="@") {
      return "W";
    }
    if (state.get(x, y + 1) === " ") {
      return "N";
    } else if (state.get(x + 1, y) === " ") {
      return "E";
    } else if (state.get(x, y - 1) === " ") {
      return "S";
    } else if (state.get(x - 1, y) === " ") {
      return "W";
    }
    return "S";
  }

```

---
Tags: king-of-the-hill, javascript
---


title: Simulate the ripple effect

text:
# Question
Title: Simulate the ripple effect
Imagine throwing a rock into a pond. You get to see perfect circles of ripples spreading out over the pond, bouncing off of each other. Of course, nothing can be as serene as that in coding, but, we can try!

Given a point on a 2D array `(x, y)` and the dimensions of a 2D array/pond `(w, h)`, and a "frame" count, `f`, return a array of 2D arrays length f that shows a ripple animation starting at `(x, y)`. An ON value (choose between int, bool, or any val for that matter that has two values) should spread out one point in a diamond shape, as the examples show.

Example 1

> ```
> Input: (0, 0, 3, 3, 7)
> Output = a[]
> a[0] =
> 1 0 0
> 0 0 0
> 0 0 0
>
> a[1] =
> 0 1 0
> 1 0 0
> 0 0 0
>
> a[2] =
> 0 0 1
> 0 1 0
> 1 0 0
>
> a[3] =
> 0 0 0
> 0 0 1
> 0 1 0
>
> a[4] =
> 0 0 0
> 0 0 0
> 0 0 1
>
> a[5]+ =
> 0 0 0
> 0 0 0
> 0 0 0
>
>
> ```

Example 2

> ```
> Input: (2, 2, 5, 5, 5)
> Output: b
> b[0] =
> 0 0 0 0 0
> 0 0 0 0 0
> 0 0 1 0 0
> 0 0 0 0 0
> 0 0 0 0 0
>
> b[1] =
> 0 0 0 0 0
> 0 0 1 0 0
> 0 1 0 1 0
> 0 0 1 0 0
> 0 0 0 0 0
>
> b[2] =
> 0 0 1 0 0
> 0 1 0 1 0
> 1 0 0 0 1
> 0 1 0 1 0
> 0 0 1 0 0
>
> b[3] =
> 0 1 0 1 0
> 1 0 0 0 1
> 0 0 0 0 0
> 1 0 0 0 1
> 0 1 0 1 0
>
> b[4] =
> 1 0 0 0 1
> 0 0 0 0 0
> 0 0 0 0 0
> 0 0 0 0 0
> 1 0 0 0 1
>
> b[5]+ =
> 0 0 0 0 0
> 0 0 0 0 0
> 0 0 0 0 0
> 0 0 0 0 0
> 0 0 0 0 0
>
> ```

Requirements

* Output should be an array of an array of an array, or a format that well represents the desired output shown above (comments appreciated on this part)
* Must be a method
* Must not use libraries that do everything for you
* values in the arrays of output must only use 2 unique values
    + this means you can't just return the plain manhattan distance, you must make it a ripple
* Standard loopholes apply

Information

* Parameters are (`int x`, `int y`, `int w`, `int h`, `int f`)
* \\$0 \le x \< w \le 10\\$
* \\$0 \le y \< h \le 10\\$
* \\$0 \< f \le 10\\$
* `w` and `h` are equal
* if your language does not support functions, just print to stdout

Test cases:

* The two examples
* `(3, 2, 5, 5, 3)`
* `(0, 0, 1, 1, 1)`
* `(1, 2, 3, 3, 4)`
* `(4, 4, 10, 10, 10)`

Please try to make it testable online, would be appreciated
This is code golf, so shortest code for each language wins!

# Answer
> 9 votes
# , 30 27 26 bytes

```
1 :'i.@u=/1#.(|@-"1]#:i.)'

```

Try it online!

Using `(2 2) 5 f (5 5)` as the example:

* `]#:i.` Creates the w,h coordinate system (showing it boxed here for clarity):

```
┌───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│0 4│
├───┼───┼───┼───┼───┤
│1 0│1 1│1 2│1 3│1 4│
├───┼───┼───┼───┼───┤
│2 0│2 1│2 2│2 3│2 4│
├───┼───┼───┼───┼───┤
│3 0│3 1│3 2│3 3│3 4│
├───┼───┼───┼───┼───┤
│4 0│4 1│4 2│4 3│4 4│
└───┴───┴───┴───┴───┘

```
* `|@-"1` subtract from x,y and take absolute value:

```
┌───┬───┬───┬───┬───┐
│2 2│2 1│2 0│2 1│2 2│
├───┼───┼───┼───┼───┤
│1 2│1 1│1 0│1 1│1 2│
├───┼───┼───┼───┼───┤
│0 2│0 1│0 0│0 1│0 2│
├───┼───┼───┼───┼───┤
│1 2│1 1│1 0│1 1│1 2│
├───┼───┼───┼───┼───┤
│2 2│2 1│2 0│2 1│2 2│
└───┴───┴───┴───┴───┘

```
* `1#.` Sum each cell for the Manhattan distance:

```
4 3 2 3 4
3 2 1 2 3
2 1 0 1 2
3 2 1 2 3
4 3 2 3 4

```
* `i.@u=/` Equality "table" (3d table) with 0, 1, 2, 3, 4:

```
0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

0 0 0 0 0
0 0 1 0 0
0 1 0 1 0
0 0 1 0 0
0 0 0 0 0

0 0 1 0 0
0 1 0 1 0
1 0 0 0 1
0 1 0 1 0
0 0 1 0 0

0 1 0 1 0
1 0 0 0 1
0 0 0 0 0
1 0 0 0 1
0 1 0 1 0

1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 0 0 0 1

```

# Answer
> 7 votes
# Julia 1.0, ~~55~~ 52 bytes

*-3 bytes thanks to @MarcMush*

`x` and `y` are 1-indexed. Outputs an `Array{BitArray{2},1}`.

```
x*y*w*h*f=0:~-f.|>d->@.abs((1:w)-x)+abs((1:h)-y)'==d

```

Try it online!

It simply generates a 2D matrix consisting of the manhattan distances from the point `(x,y)`.

# Answer
> 5 votes
# Wolfram Language (Mathematica), 53 bytes

```
Table[Abs[#1-i]+Abs[#2-j]==k,{k,0,#5},{i,#3},{j,#4}]&

```

Try it online!

Defines a pure function that takes the inputs `x, y, w, h, f` (in that order). Constructs a `h`-by-`w`matrix using `Table`, where each matrix element is either `True` or `False` depending on whether the Manhattan distance from `(x, y)` equals `k`, an iteration variable corresponding to the kth element in the output array. `x` and `y` are 1-indexed. In the TIO I have wrapped the output in `Boole` so that the output has `0` for `False`and `1` for `True`.

# Answer
> 4 votes
# , 62 bytes

```
\(x,y,d,f,`[`=outer)abs(1:d-x-1)[abs(1:d-y-1),"+"][1:f-1,"=="]
```

Attempt This Online!

Returns a 3-d `logical` `array`--`+` is prepended to the function call to make the output more readable.

Computes the manhattan distances of each cell with the starting cell, then computes the equality with each frame number.

# Answer
> 3 votes
# PARI/GP, 63 bytes

A port of dingledooper's Julia answer. `x` and `y` are 1-indexed. Outputs a vector of matrices.

```
(x,y,w,h,f)->[matrix(w,h,i,j,abs(i-x)+abs(j-y)==d)|d<-[0..f-1]]
```

Attempt This Online!

# Answer
> 3 votes
# Factor \+ `math.matrices math.unicode pair-rocket`, 80 bytes

```
[ <iota> [ '[ 2array _ => _ v- vabs Σ _ = ] <matrix-by-indices> ] 4 nwith map ]

```

Takes input as `h w y x f` and gives output as a sequence of matrices.

I'm using a modern build of Factor for this, so have a picture:

There are two reasons for that:

* `make-matrix-with-indices` is now called `<matrix-by-indices>`.
* Values can be fried directly into literals now, so I can say `_ => _` instead of `_ _ 2array`.

See here for a version that runs on TIO at a cost of 7 bytes.

# Answer
> 3 votes
# 05AB1E, 12 (or 17) bytes

```
F²Lã€αO²ôNQ,

```

Three inputs in the order: \\$f\\$, \\$d\\$, \\$\[x,y\]\\$, where \\$d\\$ is both \\$w\\$ and \\$h\\$ since it's guaranteed that \\$w==h\\$ anyway, and \\$\[x,y\]\\$ are 1-based indices. Outputs each matrix on a separated line to STDOUT.

Try it online.

For a more strict I/O as described in the challenge description, it would be 17 bytes instead:

```
L<²L`âε³>αO}²нôδQ

```

Try it online.

**Explanation:**

```
F            # Loop `N` in the range [0, first (implicit) input `f`):
 ²L          #  Push a list in the range [1, second input `d`]
   ã         #  Create all coordinate-pairs by taking the cartesian product of
             #  itself
    €        #  Map over each coordinate-pair:
     α       #   Calculate the absolute difference with the (implicit) third
             #   input [x,y]
      O      #  Sum each inner pair to get the Manhattan distance
       ²ô    #  Split this list into parts of size `d` to turn it into a matrix
         NQ  #  Check for each value if it equals `N`
           , #  Pop and output this matrix with trailing newline

```

```
L            # Push a list in the range [1, first (implicit) input `f`]
 <           # Decrease it by 1 to range [0, f)
  ²          # Push the second input-pair [w,h]
   L         # Transform both to a list in the range [[1,w],[1,h]]
    `        # Pop and push both lists separated to the stack
     â       # Create pairs of both lists with the cartesian power
      ε      # Map over each pair:
       ³     #  Push the third input [x,y]
        >    #  Increase it from a 0-based to 1-based index
         α   #  Take the absolute difference with the current pair
          O  #  Sum to get the Manhattan distance
      }²н    # After the map: push the first value of the second input: w
         ô   # Split the list into parts of that size
          δ  # Apply on the two lists double-vectorized:
           Q #  Check which values in the matrix are equal to the value of the
             #  [0,f) list
             # (after which the list of matrices is output implicitly as result)

```

# Answer
> 3 votes
# Ruby, 81 bytes

```
->x,y,w,h,f{(0...f).map{|c|(-y...h-y).map{|m|(-x...w-x).map{|n|m.abs+n.abs==c}}}}

```

Try it online!

# Answer
> 2 votes
# Java 10, ~~140~~ 134 bytes

```
(x,y,w,h,f)->{var r=new int[f][h][w];for(;f-->0;)for(int d=h*w;d-->0;)r[f][d%h][d/h]=Math.abs(d%h-x)+Math.abs(d/h-y)==f?1:0;return r;}

```

Could technically be 132 bytes since `w==h`, but this also works for non-square matrices.

Try it online.

**Explanation:**

```
(x,y,w,h,f)->{           // Method with the 5 parameters & int[][][] return-type
  var r=new int[f][h][w];//  Result array of `f` amount of `h` by `w` sized
                         //  matrices, filled with 0s by default
  for(;f-->0;)           //  Loop `f` in the range (f,0]:
    for(int d=h*w;d-->0;)//   Inner loop over all cells of a matrix:
      r[f]               //    Modify the matrix at index `f`
          [d%h][d/h]=    //    at the current cell, to:
        Math.abs(d%h-x)  //     Calculate the absolute difference of the current
                         //     cell's x-coordinate and `x`
        +Math.abs(d/h-y) //     Add the same for `y`
        ==f?             //     If this Manhattan distance is equal to `f`:
            1            //      Fill the current cell with a 1
           :0;           //     Else: keep the 0
  return r;}             //  Return the result

```

# Answer
> 1 votes
# Python 3.8 (pre-release), 90 bytes

```
lambda a,b,c,d,e,R=range:[[[i==abs(k-a)+abs(j-b)for k in R(c)]for j in R(d)]for i in R(e)]

```

Try it online!

Returns a 2d list of booleans indicating whether or not the Manhattan distance from the original point is equal to the iteration number, for each iteration number from 0 to `e` (frame count).

# Answer
> 1 votes
# Charcoal, 25 bytes

```
ＮθＮηＮζＮεＥＮＥε⭆ζ⁼ι⁺↔⁻ηλ↔⁻θν

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ                          First input as a number
  Ｎη                        Second input as a number
    Ｎζ                      Third input as a number
      Ｎε                    Fourth input as a number
         Ｎ                  Fifth input as a number
        Ｅ                   Map over implicit range
           ε                Fourth input
          Ｅ                 Map over implicit range
             ζ              Third input
            ⭆               Map over implicit range and join
               ι            Current frame
              ⁼             Equal to
                   η        Second input
                 ↔⁻         Absolute difference with
                    λ       Current row
                ⁺           Plus
                       θ    First input
                     ↔⁻     Absolute difference with
                        ν   Current column

```

# Answer
> 1 votes
# Jelly, 10 bytes

Uses Jonah's method of precalculating the Manhattan distance matrix and then filtering for equality with the step number.

```
;ạ⁵SƲþ/‘=Ɱ

```

A full-program that accepts `[w, h] f [x, y]` and prints a list of frames which are each lists of lists of integers `1` (ripple) and `0` (calm). The coordinates, `w h x y` are all 1-indexed (top-left = `[1,1]`).

**Try it online!** (Footer formats the result for ease on the eyes.)

### How?

```
;ạ⁵SƲþ/‘=Ɱ - Main Link: [w, h]; f
      /    - reduce [w, h] by:
     þ     -   table between i in [1..w] and j in [1..h] of:
    Ʋ      -     last four links as a monad - f(i, j):
;          -       concatenate -> [i, j]
  ⁵        -       third program argument = [x, y]
 ạ         -       absolute difference (vectorises) -> [abs(i-x), abs(j-y)]
   S       -       sum -> Manhattan distance of [i, j] from [x, y]
       ‘   - increment (vectorises)
         Ɱ - map across (implicit range) [1..f] with:
        =  -   equals? (vectorises)
           - implicit print

```

---
Tags: code-golf, matrix, physics
---


title: What's the Missing Code? (Robbers)

text:
# Question
Title: What's the Missing Code? (Robbers)
# Robbers' Challenge

Read the cops' challenge first.

In this challenge, you (the robbers) must find the correct string of characters, which, when added into the cop's code, will make it produce the correct (case-sensitive) output (except that there may also be an extra trailing newline at the end).

The number of characters you add in must be less than or equal to the number of characters removed from the original code, and your answer is still valid even if it was not intended.

The characters can be added anywhere in the code, but they must all be consecutive in the same place (i.e. not random characters dotted around the code).

Make sure to link the cop's post that you have cracked in your answer, and once you have posted your answer here, comment under the cop's post linking your answer if you have enough reputation.

## Example

Say a cop posted the following submission:

> # Python, score of 14
>
> Code: `print(5*"a")`
> Number of characters removed: 1
> Target output: `5 a` (currently outputs `aaaaa`)

This is the answer a robber would post to crack it:

> # Cracks ...'s Python answer (link)
>
> Character to add: `,` before the `*`
> Resulting code: `print(5,*"a")`
> Resulting output: `5 a`

## Scoring

The following scoring criterion will be used in order (if #1 is a tie, then #2 is used to tiebreak, etc.):

1. The robber who has cracked the most cops' answers (that were uncracked at the time of posting) after 1 week wins!
2. Out of the tied robbers, the one whose most-upvoted answer has the most upvotes wins
3. Out of the tied robbers, the one whose most-upvoted answer was posted first wins

Good luck!

# Answer
> 7 votes
# , cracks pajonk's answer

```
el(names(swiss),6)

```

Try it online!

Characters to add = `names(swiss),`

# Answer
> 24 votes
# Python 3, cracks Sisyphus' answer

```
print(dⅳmod(99,15))

```

Try it online!

Inserts `dⅳmod` where the  is U+2173 (Small Roman Numeral Four), a one-character multibyte ligature that normalizes to `iv`, letting us squeeze the built-in into 5 characters. I learned of this ligature trick for Python 3 in doing this crack.

# Answer
> 9 votes
# JavaScript (Node.js), cracks l4m2's answer

```
console.log((99n**77n).toString(34))

```

Try it online!

### Cracking script

```
let s = "39iw027a2hnuqi2c1os255jmjsidafs3nx6496n8vl8dak0qc3r15xwheq4vxpb136up7rsmbm8v5slowjwf7mvj0s751b03gxif5";

// there's no 'y' and no 'z', so this could be an integer in base 36, 35 or 34
[36, 35, 34].forEach(base => {
  let n = [...s].reduce((p, c) => p * BigInt(base) + BigInt(parseInt(c, base)), 0n);

  console.log(`Base ${base} -> ${n}`);

  // look for divisors of reasonable size
  for(let d = 2n; d < 1000n; d++) {
    let k = 0, N = n;
    while(!(N % d)) { N /= d; k++; }
    k && console.log(`${d}**${k}\t${N == 1n ? "success!" : "failed"}`);
  }
  console.log();
});

```

Try it online!

# Answer
> 6 votes
# Java, cracks *David Conrad*'s answer

`Character.` is added before the `getName(x)` within the `toString()` method.

Try it online.

This took longer than expected..

**Explanation:**

The `Character#getName(int)` method returns the Unicode name for the given character codepoint.

The characters names of the given codepoints `130, 14, 8613, 8784, 150, 151` are in order:

```
BREAK PERMITTED HERE
SHIFT OUT
UPWARDS ARROW FROM BAR
APPROACHES THE LIMIT
START OF GUARDED AREA
END OF GUARDED AREA

```

Which then gets split by spaces and the correct word is extracted based on the modulo operators used.

# Answer
> 5 votes
# , cracks Robin Ryder's answer

```
print("R",,F)

```

Try it online!

The original answer indicated that 8 characters had been removed; this crack uses only 3 characters: `,,F`, so presumably it isn't the intended solution...

# Answer
> 4 votes
# Cracks emanresu A's Vyxal "kay" submission

```
kaøBy

```

**Try it online!**

All we need to do is wrap the alphabetic characters we get from `ka` in square brackets before we uninterleave with `y`, and that's a two-byte built-in, `øB`.

---

The "bonus" output is achieved with a reversal (`Ǔ`) instead: `kaǓy` Try it.

# Answer
> 4 votes
# PHP, cracks Michel's answer

```
<?php for($i=7;$i-->2;)print$i<<print$i;

```

Try it online!

The main observation is that the expected output (`612510483624`) can be split in such a way that an obvious pattern emerges: `6 12 5 10 4 8 3 6 2 4`. It follows a consistent pattern of `$i*2 $i ...`.

The tricky bit is figuring out how to print it, but it turns out to be as simple as inserting a `print` before the second `$i`. The rightmost `print` is evaluated first, printing `$i`, and then `$i<<1` is printed, since the other `print` returns a `1`.

# Answer
> 4 votes
# Python, cracks pxeger's answer

```
"print("")"
print(__doc__)
""
```

Attempt This Online!

TIL you can store a string inside `__doc__` by adding it on the first line.

# Answer
> 3 votes
# Python 3, Cracks des54321's answer

```
print(str(quit)[14:18])

```

OR

```
print(str(exit)[14:18])

```

I brute-forced this by running:

```
import gc
for x in gc.get_objects():
    if str(x)[14:18] == "Ctrl":
        print(x)

```

# Answer
> 3 votes
# Python 3, cracks thegreatemu's answer

```
import random as r
r.seed(258117)
print(r.random())

```

Try it online!

I just brute-forced six-digit seeds, which took 8 seconds to run on TIO.

# Answer
> 3 votes
# MATL, cracks Luis Mendo's answer

```
'Hey My'YbtvZc

```

Try it online!

Adds the string `YbtvZc` to the end.

# Answer
> 2 votes
# Cracks des54321's Python answer

Adding `^63` after `chr(i` results in:

```
print("".join(chr(i^63)for i in b'wZSSP\x1fhPMS[\x1e'))

```

...which outputs `Hello World!`

Try it online!

# Answer
> 2 votes
### Crack for bigyihsuan's Lexurgy SC answer

```
a:
*=>w
b:
w=>zwq

```

Obviously not the intended solution, but seems to work fine.

# Answer
> 2 votes
# Python 3, cracks EphraimRuttenberg's answer:

```
print(str(...)[1:3]*50)

```

Try it online!

Added code: `...` inside the `str()`.

# Answer
> 2 votes
# , cracks Robin Ryder's second answer

```
`?`=noquote#print
?"R"

```

Try it online!

The 8 characters to add are `noquote#`. This exchanges the asssignment of `?` to the `print` function into an assignment to the `noquote` function, and comments-out the now-useless `print`.

# Answer
> 2 votes
# , cracks Robin Ryder's third answer

```
{assign("?",print.noquote)}
?"R"

```

Try it online!

The 8 characters to add are `.noquote`, changing the `print` function into the rather-obscure `print.noquote` function.
This series of challenges was an uphill battle for poor Robin Ryder; I think neither of us was fully aware of the variety of `noquote`-like options and functions that lurk in base-, and Robin patiently added more-and-more convoluted re-assignments and curly-braces to counteract each new `noquote` variant as it popped up in unintended cracks...

# Answer
> 2 votes
# Behavior, cracks Lince Assassino's answer

```
@(type:type)-0-3

```

Try it online! (you will have to input the program yourself)

Adds `-3` to the end. Removing the `-0` originally gives a result of `cfunc`, so I assumed `-0` meant "remove the character at index `0`." Using the same logic, we add `-3` to remove the character at index `3` in `func` to get `fun`.

# Answer
> 1 votes
# Python, 124 bytes, cracks jezza\_99's answer

```
import sys
S=sys.stdout
sys.stdout=type('',(),{'write':lambda x,y:'','flush':lambda z:1})()
import this
S.write(this.s[:98])
```

All of the re-added characters are at the end of the program.

Attempt This Online!

# Answer
> 1 votes
# PHP, cracks Michel's answer

```
<?php echo hexdec(M_E),'';

```

Try it online!

My first thought was, "maybe the number is large enough that printing it as a hex literal is shorter somehow...". When converting it to hex, I immediately notice that the hex digits are the first few digits of \\$ e \\$ (`0x2718281828459`). The rest is trivial.

---
Tags: string, cops-and-robbers
---