# Question
Title: I reverse the source code, you negate the output!
Your task, if you wish to accept it, is to write a program that outputs a non-zero number(can be integer or float). The tricky part is that if I reverse your source code, the output must be the original integer negated.

# Rules

* You must build a **full program**. That is, your output has to be printed to STDOUT.
* Both the numbers must be in base 10 (outputting them in any other base or with scientific notation is forbidden).
* Outputting the numbers with trailing / leading spaces is allowed.
* This is code-golf, so the shortest (original) code in each language wins!
* Default Loopholes apply.

## Example

Let's say your source code is `ABC` and its corresponding output is `4`. If I write `CBA` instead and run it, the output must be `-4`.

# Answer
# 05AB1E, 2 bytes

```
(1

```

Try it online!

!enilno ti yrT

```
(       # negate nothing
 1      # push 1 (and implictly output it)

```

```
1       # push 1
 (      # negate it (and implictly output it)

```
> 53 votes

# Answer
# PowerShell,  ~~4~~  3 bytes

```
1-0

```

Try it online! or !enilno ti yrT

*Golfed a byte by using arithmetic instead of the number-comment-number format.*

---

This is apparently also the same as jshell (per Sam), and jq (per manatwork -- `1-0` and `0-1`).
> 31 votes

# Answer
# JavaScript (V8), 19 bytes

```
print(1)//)1-(tnirp

```

Try it online!

---

almost identical to...

# C# (Visual C# Interactive Compiler), 19 bytes

```
Print(1)//)1-(tnirP

```

Try it online!

*(thanks to @someone for pointing it out)*

---

still pretty much the same in...

# Lua, 19 bytes

```
print(1)--)1-(tnirp

```

Try it online!

---

but shorter in...

# Python 2, 15 bytes

```
print 1#1-tnirp

```

Try it online!

---

Even shorter in PHP, because it has this magic printing tool: `<?=` ...

# PHP, 12 bytes

```
<?=1;#;1-=?<

```

Try it online!

---

Even shorterer in Ruby, because you can `inspect` rather than print

# Ruby, 8 bytes

```
p 1#1- p

```

Try it online!
> 30 votes

# Answer
# ///, 4 bytes

```
9/9-

```

Outputs `9`.

Try it online!

Reversed:

```
-9/9

```

Outputs `-9`.

Try it online!

Everything before the `/` is printed, while the rest is ignored (not really used slashes much so I don't know exactly what happens, but it doesn't output anything).
> 15 votes

# Answer
# Whitespace, 21 bytes

```
S S S T N
T   N
S T N
N
N
T   S N
T   N
T   T   S S

```

Letters `S` (space), `T` (tab), and `N` (new-line) added as highlighting only.

Outputs `1`/`-1`.

Try it online or try it online reversed (with raw spaces, tabs and new-lines only).

**Explanation:**

Utilizing the *Exit Program* builtin being a short palindrome `NNN`.
The regular program will:

```
SSSTN  # Push 1 to the stack
TNST   # Pop and print the top of the stack as number
NNN    # Exit the program, making everything after it no-ops

```

The reverse program will:

```
SSTTN  # Push -1 to the stack
TNST   # Pop and print the top of the stack as number
NNN    # Exit the program, making everything after it no-ops

```

Small additional explanation of pushing a number:

* First `S`: Enable Stack Manipulation
* Second `S`: Push a number to the stack
* `S` or `T`: Positive/negative respectively
* Some `S`/`T` followed by a trailing `N`: number in binary, where `S=0` and `T=1`

I.e. `SSTTSTSN` pushes `-10`.
> 11 votes

# Answer
# Google, 3 bytes

```
2-1

```

Try it online!
!enilno ti yrT
> 11 votes

# Answer
## Stack Cats `-mn`, 4 bytes

```
:-:_

```

Try it online! In the footer I've included all other 4-byte solutions. (Stack Cats ignores everything after the first linefeed.)

Try the reverse!

### Explanation

The `-n` flag turns on numeric output (and input, but we don't have any), and the `-m` flag is normally just a golfing convenience which lets you avoid the redundant part of the source code. This is because every Stack Cats program needs to have mirror symmetry. With the `-m` flag you only give it the first half (plus the central character). So the *actual* program here is:

```
:-:_:-:

```

As you can see in the first TIO link, there's a ton of 4-byte solutions, but I picked this one for its simplicity. Stack Cats is stack-based, and this program only uses the initial stack. Since we don't have any input, it contains a single `-1` (an EOF marker) on top of an infinite well of zeros. The three commands in the program have the following meaning:

```
:   Swap the top two stack elements.
-   Negate the top stack element (i.e. multiply by -1).
_   Pop a. Peek b. Push b-a.

```

So here is how the program modifies the stack (states and commands are staggered to indicate how each command changes the stack from one state to the next):

```
   :   -   :   _   :   -   :

-1   0   0  -1   1   0   0   1
 0  -1  -1   0   0   1   1   0
 0   0   0   0   0   0   0   0
 …   …   …   …   …   …   …   …

```

As it turns out, the only command that really does anything here is `_` which turns our EOF marker into a `1`. Output at the end of the program is implicit, and the EOF marker is optional, so this just prints out the `1` we get.

Now if we reverse the source code, due to the implicit mirroring, the actual program becomes:

```
_:-:-:_

```

This does something very different:

```
   _   :   -   :   -   :   _

-1   1   0   0   1  -1   0  -1
 0   0   1   1   0   0  -1  -1
 0   0   0   0   0   0   0   0
 …   …   …   …   …   …   …   …

```

This time the bottom of the stack *is* still a `-1` so it does act as the EOF marker and only the `-1` on top of it gets printed.

...

Now with all of that said, since Stack Cats has such a unique relationship with reversing code, I feel that using `-m` is a little cheating. It's normally only meant to save bytes by omitting the redundant part of the source code, but here it actually makes the challenge a lot easier and even the full program shorter. This is because reversing a full program will only change the program if it contains any of `<>[]`, which also means that the program ends up making use of multiple stacks (Stack Cats actually has a tape of stacks, where all but the initial one are only filled with zeros to begin with). Furthermore, reversing it then just swaps the `<>` and `[]` pairs, which still makes the execution symmetric. The only way to break that symmetry is to use `I` which does `-]` or `-[` or nothing depending on the sign of the top of the stack. So...

---

## Stack Cats `-n`, 11 bytes

```
*|]I*:*I[|*

```

Try it online! The footer again includes all other alternatives at the same byte count. Some of those output 1/-1 and some output 2/-2 as indicated after each program. I picked this one to explain kinda randomly as one of the ones that output 2.

Try the reverse!

### Explanation

As I said, this one's a bit longer. Even if we did use the `-m` notation for this, it would weigh in at 6 bytes instead of the above 4.

The commands in use this time:

```
*   Toggle the least significant bit of the top of the stack.
|   Reverse the longest non-zero of prefix on this stack.
[]  Move one stack to the left/right and take the top of the current stack with you.
I   If the top of the stack is positive, -], if it's negative, -[, otherwise do nothing.
:   Swap the top two stack elements.

```

The first program only uses two stacks. That's a bit messy to do in ASCII art, but I'll try my best. The square brackets indicate which stack the tape head is on, and I'll put the commands between each pair of stack states.

```
  [-1]
…   0   0   …
    0   0
    …   …

      *

  [-2]
…   0   0   …
    0   0
    …   …

      | (does nothing)
      ]

      [-2]
…   0   0   …
    0   0
    …   …

      I

   [2]
…   0   0   …
    0   0
    …   …

      *

   [3]
…   0   0   …
    0   0
    …   …

      :

   [0]
…   3   0   …
    0   0
    …   …

      *

   [1]
…   3   0   …
    0   0
    …   …

      I

      [-1]
…   3   0   …
    0   0
    …   …

      [

  [-1]
…   3   0   …
    0   0
    …   …

      |

  [ 3]
…  -1   0   …
    0   0
    …   …

      *

  [ 2]
…  -1   0   …
    0   0
    …   …

```

Now the `-1` acts as an EOF marker and the `2` gets printed.

The other program is the same until the `[`. It's still virtually the same all the way until the second `I`. We'll technically be on a different stack, but without values on them, they're all indistinguishable. But then the difference between `I[` and `I]` ends up mattering:

```
    *|[I*:*I

      [-1]
…   3   0   0   …
    0   0   0
    …   …   …

        ]

          [-1]
…   3   0   0   …
    0   0   0
    …   …   …

        | (does nothing)
        *

          [-2]
…   3   0   0   …
    0   0   0
    …   …   …

```

And this time, we don't have an EOF marker, but the program still outputs the `-2`.
> 11 votes

# Answer
# Klein 011, 5 bytes

```
1-
@/

```

Try it online!

# Reversed

```
/@
-1

```

Try it online!

These take advantage of Klein's unique topology, specifically the real projective plane. (Although individually each answer only needs a Klein bottle).
> 10 votes

# Answer
# Haskell without comments, 41 bytes

Forwards prints `1` \+ newline:

```
main=print$!1
niam=main
"1-"!$rtStup=niam

```

Try it online!

Reversed prints `-1` with no newline (which could be added at a cost of 2 bytes):

```
main=putStr$!"-1"
niam=main
1!$tnirp=niam

```

Try it online!

* The first line of each program prints the number.
    + For `-1` string output is used to avoid parentheses.
    + Using `$!` (strict application) instead of a space allows the reversed line to be a valid definition of the operator `!$` (just `$` wouldn't do since the redefinition would break the use).
* The middle line ensures that `niam` is defined for the last line.
* The last line is a definition of an operator `!$`, which is not used but needs to parse and typecheck correctly.
> 10 votes

# Answer
# PHP, ~~15~~ 13 bytes

A PHP version without comment abuse. `ohce` is an undefined constant, so it will be equal to string value of its name. As a result, this will try to print `+1-'ohce'` or `-1+'ohce'` when reversed. Since `'ohce'` is a non-numeric value, 0 will be used instead in the arithmetic operations and only `1` or `-1` will be printed.

```
;echo+1-ohce;

```

Try it online!

Try it online!
> 9 votes

# Answer
# Japt, 2 bytes

Any single digit integer `>0` can be used in place of the `2` as can `A-G`, `H`, `I`, `J` or `L` (`10-16`, `32`, `64`, `-1` & `100`, respectively).

```
n2

```

Test it | Reversed

The `n` method when applied to an integer, subtracts that integer from the argument passed to it, which defaults to `0`. When run forwards, the `n` method is being run on the implicit first input, which also defaults to `0`.

Alternatively, the `g` method could be used instead of `n`, which gives the sign of the result of subtracting its argument from the integer it's applied to.
> 7 votes

# Answer
# Cubix, ~~7~~ ~~6~~ 5 bytes

```
@)O(@

```

Try it here
Reversed

### Explanation

Cubified:

```
  @
) O ( @
  .

```

Unrolling the control flow, we execute `)O(@`, which increments, outputs, decrements, and exits.

Reversed and cubified:

```
  @
( O ) @
  .

```

Unrolling the control flow, we execute `(O)@`, which decrements, outputs, increments, and exits.

### Previous version

```
@O(.)O@

```

Try it here
Reversed

Not as short, but aesthetically pleasing.
> 7 votes

# Answer
# T-SQL, 16 bytes

```
--Forwards:
PRINT 4--4-TNIRP

--Backwards:
PRINT-4--4 TNIRP

```

Picked 4 because 1 is overused :)
> 6 votes

# Answer
# Jelly, 2 bytes

```
NC

```

Try it online!

`N`egative, results in `0`, then `C`omplement, results in `1-0` = `1`.

---

```
CN

```

Try it online! `C`omplement, results in `1-0` = `1`. `N`egative, results in `-1`.
> 6 votes

# Answer
# K (ngn/k), 3 bytes

```
2-1

```

Try it online!

am i missing something? seems obvious for REPL languages
> 6 votes

# Answer
# Hexagony, 5 bytes

```
1!@!(

```

Try it online!

Any valid program must:

* Have a termination command (`@` or `:`). The latter is only different for the former when there's a memory pointer movement command. Also this command must not be at the first or the last byte.
* Have an output command. (`!`, `;` is also possible but would probably take more bytes)
* Have a memory manipulation command.

Therefore a 2-byte program is obviously impossible. A 3-byte program is impossible because the second byte must be the termination command, and the first byte must not be a mirror/IP manipulation command, therefore only 1 byte can be executed.

I think a 4-byte program is not possible. Such a program must have the form `a@bc` with hexagonal grid

```
 Forward:       | Backward:
                |
  c b           |   a @
 @ a .          |  b c .
  . .           |   . .

```

Therefore `a` must be a IP redirection command. However it's impossible to generate both positive and negative number with only 1 memory manipulation command.
> 6 votes

# Answer
# Runic Enchantments, 4 bytes

```
1@Z1

```

Try it online! Try it Reversed!

I couldn't find a way to re-use the `1` command, even at the expense of a byte or two.

`1@ɩ` also works, but is the same number of bytes.
> 5 votes

# Answer
# APL (Dyalog Unicode),  ~~4~~  3 bytes

```
1-0

```

Try it online!

Trivial answer. Prints `1` when run and `¯1` when run reversed.
> 5 votes

# Answer
# Zsh, 12 bytes

```
<<<2 # 2-<<<

```

Try it online!

Basic forward, comment, reverse method.

---

If I/O is less restrictive, then a more interesting **11 byte** solution is possible thanks to Zsh supporting negative return codes:

```
return -127

```

Reversed, `721- nruter` exits with code `127` (command not found). `exit -127` cannot be used, it would be cast to a `u8`. Try it online!
> 5 votes

# Answer
# CJam, 3 bytes

```
W;1

```

Try it online!

### How they work

Normal version:

```
W    e# Push -1
;    e# Delete
1    e# Push 1
     e# Implicit display

```

Reverse version: you get the idea.
> 4 votes

# Answer
# Perl 5 (-p), 12 bytes

```
\$--{}}{++$\

```

Try it online!

!enilno ti yrT

The `}{` pseudo-operator really comes in handy.

---

## Perl 5 (-M5.010), 9 bytes

*Provided by Nahuel Fouilleul in a comment*

```
say+1-yas

```

Try it online!

!enilno ti yrT
> 4 votes

# Answer
# MATL, 3 bytes

```
Nqv

```

Try it online!

### How they work

Normal:

```
N   % Push number of elements in the stack: 0
q   % Subtract 1: gives -1
v   % Concatenate stack contents vertically: leaves -1 as is
    % Implicit display stack contents

```

Reversed:

```
v   % Concatenate stack contents vertically: gives the empty array, []
q   % Subtract 1: leaves [] as is
N   % Push number of elements in the stack: 1
    % Implicit display. [] is not displayed

```
> 4 votes

# Answer
# Wolfram Language (Mathematica), ~~21~~ 18 bytes

```
Print@1;tnirP//1-0

```

Try it online!

-3 thanks to Martin Ender
> 4 votes

# Answer
## Retina, 6 bytes

```
-`<
-

```

Prints `1`.

Try it online!

---

```

-
<`-

```

Prints `-1`.

Try it online!

### Explanation: `1`

```
-`<
-

```

This... does nothing. Due to the ```, this is a substitution from `<` to `-` (with configuration `-`, which does nothing), but the input is empty, so the output is empty as well.

```

```

And this second stage matches the empty regex against the empty input and counts the number of matches, which is exactly 1. Output is implicit.

### Explanation: `-1`

```

-

```

This time we replace the empty regex with `-`. This does indeed turn the empty input into a single `-`.

```
<`-

```

Here, the configuration actually does something: `<` prints the stage's input before executing the stage, so we print the `-`. Then `-` counts the hyphens in the stage's input which is again 1. Due to the implicit output, this prints a `1` after the `-`, giving us `-1` as required.
> 4 votes

# Answer
# brainfuck, 156 bytes

```
+++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++++++++++++++++++++++<+++++++++++++++++++++++++++++++++++++++++++++++++.++++++++++

```

Try it online! / Forward/backward verifier in Bash

Prints `-1` forward and `\n1` backwards.

Despite being almost trivial, I believe this is the optimal solution for this particular fixed output.

Proof:

* The program cannot have `[` or `]`.

Therefore the program must have the form `<A> . <B> . <C>`.
* Each `,` can be replaced with a sufficient number of `<` without increasing the number of `+` or `-`.
* Each `+` is only useful in either the forward or the backward program, never both.

Proof: `+` in part A is obviously only useful in the forward program, and `+` in part C is obviously only useful in the backward program.

Denote `shift(P)` = number of `<` in P - number of `>` in P. Consider program `<B> = <D> + <E>`, the `+` in the middle is useful in the forward program \\$\iff\\$ `shift(E) = 0`, similarly it's useful in the backward program \\$\iff\\$ `shift(D) = 0`. However if `shift(D) = shift(E) = 0` then the program `B` executed either forward or backward would add a fixed value to the current cell before printing the second time, which can't be the case because `ord('1') - ord('\n') != ord('1') - ord('-')`.

Therefore the program needs at least `ord('-')+ord('1')+ord('\n')+ord('1') = 153` `+`s, 2 `.`s, and at least a `<` `>` or `,` because `shift(B) != 0`.
> 4 votes

# Answer
# Google Sheets, 12

Fun problem!

Forward:

```
=1+N("(N+1-=

```

Backward:

```
=-1+N("(N+1=

```

Google sheets auto-closes quotes and parens. `N(string)` is always 0.
> 4 votes

# Answer
# Haskell, 28 bytes

```
main=print 1--)1-(tnirp=niam

```

Try it online!

Try it enilno!
> 3 votes

# Answer
# Triangular, 4 bytes

```
i%%d

```

Try it online!

Outputs 1.

Ungolfed:

```
   i
  % %
 d

```

**Reversed:**

```
d%%i

```

Try it online!

Outputs -1.
> 3 votes

# Answer
# Java 5 or 6, ~~127~~ 67 bytes

```
enum A{A;{System.out.print(9);}}//}};)9-(tnirp.tuo.metsyS{;A{A mune

```

Outputs `9`/`-9`.

No online compiler, because Java 5 or 6 isn't available anywhere.

You can however try this **127 bytes** Java 8 equivalent:
Try it online or try it online reversed.

**Explanation:**

```
enum A{                              // Create an enum
 A;                                  //  With a mandatory value
 {                                   //  And in a separate instance code-block:
  System.out.print(9);}}             //   Print 9 to STDOUT
//}};)9-(tnirp.tuo.metsyS{;A{A mune  // Comment and thus a no-op

```

Java 5 and 6 had a bug allowing you to create a code block inside an enum to do something, despite missing a program's mandatory main-method. This will result in an error:

> java.lang.NoSuchMethodError: main
> Exception in thread "main"

But will still output what we'd want to STDOUT first, so we can ignore that.
> 3 votes

# Answer
# JavaScript, 31 bytes

The obligatory comment abuse for JavaScript!

```
console.log(1)//)1-(gol.elosnoc

```

and reversed:

```
console.log(-1)//)1(gol.elosnoc

```
> 3 votes

# Answer
# Golang, 109 bytes

```
package main;import "fmt";func main(){fmt.Println(1)}//})1(nltnirP.tmf{)(niam cnuf;"tmf" tropmi;niam egakcap

```

And its reverse:

```
package main;import "fmt";func main(){fmt.Println(-1)}//})1(nltnirP.tmf{)(niam cnuf;"tmf" tropmi;niam egakcap

```

Try it online!
> 3 votes

# Answer
\\$\Large{\mathbf{\TeX} \left(\text{MathJax}\right)},~4\\,\text{bytes}\\$

```
1%1-

```

$$ \begin{array}{|r|c|c|} \hline & \textbf{Code} %& \begin{array}{c}\boxed{\textbf{Boxed}} \\ \textbf{Result} \end{array} & \textbf{Result} \\\hline \textbf{Forward:} & \texttt{1%1-} & %\boxed{ 1%1- %} \\\hline \textbf{Backward:} & \texttt{-1%1} & %\boxed{ -1%1 %} \\\hline \end{array} $$
> 3 votes

# Answer
# Poetic, 153 bytes

```
mood o-o level a
was i redder?o,rats
lived on,lager:a trap!no reviver
ah hah ha
god deified on?now i strap on
redder was i?redder i saw,o
sleep o-on time

```

Try it online!

Prints `1`.

### Reversed

```
emit no-o peels
o,was i redder?i saw redder
no parts i won?no deified dog
ah hah ha
reviver on!part a:regal,no devil
star,o?redder i saw
a level o-o doom

```

!enilno ti yrT

Prints `-1`.
> 3 votes

# Answer
# MarioLANG, 5 bytes

```
+
:
-

```

Try it online!

**Reversed:**

```
-
:
+

```

Try it online!
> 2 votes

# Answer
# Stax, 2 bytes

```
U1

```

Run and debug it at staxlang.xyz!

!zyx.gnalxats ta ti gubed dan nuR

Push -1. Push 1. Implicitly print the top of the stack.
> 2 votes

# Answer
# Turing Machine Language, 29 bytes

```
0 * - r 1
1 * 1 * 1
1 r _ * 0

```

And its reverse:

```
0 * _ r 1
1 * 1 * 1
1 r - * 0

```

Try it online!

Note: This will run in a continous loop both ways.

Explanation:

```
0 * - r 1     ; Prints a hyphen '-' then moves right along the tape.
1 * 1 * 1     ; Prints '1' and loops back in on itself.
1 r _ * 0     ; Never hits.

```

And its reverse:

```
0 * _ r 1     ; Prints a space then moves right along the tape.
1 * 1 * 1     ; Prints '1' and loops back in on itself.
1 r - * 0     ; Never hits.

```
> 2 votes

# Answer
# \>\<\>, 7 bytes

A solution using the stack length. The regular and reversed programs share most of the code.

```
2l-n;<3

```

Try it online!
!enilno ti yrT

---

# \>\<\>, 7 bytes

A more boring solution where the programs only share the `;`.

```
1n;n-10

```

Try it online!
!enilno ti yrT

---

If we were allowed to use the fact that stdin is empty, this 5-byte variation of the second solution would be legal. Alas, it is not.

```
1n;ni

```

Try it online!
!enilno ti yrT
> 2 votes

# Answer
# Forth (gforth), 10 8 bytes

```
1 . -1 0

```

Outputs: 1

**Reverse:**

```
0 1- . 1

```

Outputs: -1

Try it online!

### Code Explanation

```
1     \ Place 1 on the stack
.     \ Output top of stack
-1 0  \ Place -1 and 0 on the stack but don't output them

Reverse:
0 1-  \ Place 0 on the stack and subtract 1
.     \ Output top of stack
1     \ Place 1 on stack, but don't output it

```
> 2 votes

# Answer
# PHP, 10 bytes.

Not very special, but it's rare for PHP to be short :)

```
<?=1#1-=?<

```
> 2 votes

# Answer
# International Phonetic Esoteric Language, ~~8~~ 6 bytes (WIP language) (OLD)

No TIO interpreter yet, but is runnable by cloning the repository above, and calling `python main.py "code here"`.

Forward, prints `1`:

```
od12do

```

Backward, prints `-1`:

```
od21do

```

If instructions try to peek or pop at an empty stack, they are `nop`ed. In this case, instructions `o`, `ɲ`, and `d` turn into `nop`s when the code is run, depending on where they are.

Forward:

```
oɲd12dɲo
o      ; nop
 d     ; nop
  1    ; push 1
   2   ; push 2
    d  ; pop, pop, push [2 - 1]
     o ; pop, print

```

Backward:

```
oɲd21dɲo
o      ; nop
 d     ; nop
  2    ; push 2
   1   ; push 1
    d  ; pop, pop, push [1 - 2]
     o ; pop, print

```

-2 bytes for not swapping the stack.
> 2 votes

# Answer
# MAWP 0.1, 18 bytes

```
?.:M?%?00?;W590?.?

```

Displays 1. Try it!

```
?.?095W;?00?%?M:.?

```

Displays '-' and then 1, which shows -1. Try it!
> 2 votes

# Answer
# Arn, 3 bytes

Forward:

```
1-0

```

Backward:

```
0-1

```

Pretty simple, I'm looking for a more interesting answer now
> 2 votes

# Answer
# Vyxal, 2 bytes

```
-1

```

Try it Online!
> 2 votes

# Answer
# HBL, 1 byte

```
+<

```

Run forwards, outputs `4`:

```
+   Increment
 <  Three

```

Run backwards, outputs `-4`:

```
<   Negate
 +  Four

```

Found while exploring different answers to Am I being run backwards?, which is a superset of this question.
> 2 votes

# Answer
# Python 3, 18 bytes

```
print(1)#)1-(tnirp

```

Try it online!
> 1 votes

# Answer
# Ruby, ~~8~~ 7 bytes

```
p 1#0~p

```

Try it online!

Thanks Arnauld for chipping off 1 byte and making it less dull.
> 1 votes

# Answer
# Charcoal, 5 bytes

```
ωＰ¹1←

```

Try it online! Outputs `1`. Explanation:

```
ω   Print the empty string (does nothing)
Ｐ¹ Print a `-` without moving the cursor
1   Print a `1`
←   Move the cursor left (no effect on output)

```

Reversed:

```
←1¹Ｐω

```

Try it online! Outputs `-1`. Explanation:

```
←1  Print a `1` and move the cursor left
¹   Print a `-`
Ｐω  Print the empty string (does nothing)

```
> 1 votes

# Answer
# Brachylog, 4 bytes

```
wṅ1?

```

Try it online!

Prints the positive output with a leading zero. The leading zero is actually just a zero that gets printed separately, but...

```
w       Print the input variable.
 ṅ      Something negated
  1     is 1,
   ?    which is the input variable.

```

!enilno ti yrT

```
?       The input variable is the input variable,
 1      which is 1.
   w    Print it
  ṅ     negated.

```
> 1 votes

# Answer
## Stax, 5 bytes

```
1PsPU

```

Not going to win any awards, but this one is refreshingly straightforward. Depends on input being empty.
> 1 votes

# Answer
# Vim, 6 keystrokes/bytes

```
<C-x><C-x><esc>1i1

```

Outputs 1. Try it online!

```
1i1<esc><C-x><C-x>

```

Outputs -1. Try it online!
> 1 votes

# Answer
## Keg, 5 bytes

```
1#-10

```

Explanation:

```
1#    Push 1
 #-10 Comment

```

Reversed explanation:

```
01-#  Push -1
   #1 Comment

```
> 1 votes

# Answer
# Befunge-93 (FBBI), ~~7~~ 6 bytes

```
1-.@.1

```

*-1 byte thanks to @squid.*

Try it online!
> 1 votes

# Answer
## GolfScript, 4 bytes

Simply abusing comments to remove a number.

```
1#1-

```

TIO

Reversed:

```
-1#1

```

TIO
> 1 votes

# Answer
## Pip, ~~3~~ 2 bytes

```
vo

```

o is a variable denoting 1, v is -1.

`0-1` is another 3 byte solution, but since it was already made in Python, I decided to make this instead.

-1 byte from Dlosc.

Try it online!
> 1 votes

# Answer
# Vyxal, 2 bytes

```
u1

```

Try it Online!

!enilnO ti yrT

`1` pushes 1, `u` pushes -1. The last one pushed is automatically printed at the end of execution.
> 1 votes

# Answer
# Fueue, 9 bytes

```
(H)!45 54

```

Outputs `6`.

Try it online!

**Reversed**

```
45 54!)H(

```

Outputs `-6`.

!enilno ti yrT

## Explanation

Fueue is a queue-based language where the program is stored in a queue. (The program queue is also the only way to store data.) From Esolang:

> Evaluation proceeds as follows:
>
> * Look at the front element of the queue.
> * If it is a numeric value, convert it to a character and print.
> * If it is a function, and there are enough values of the appropriate type directly behind it in the queue, the function and those values are popped, and the result is pushed back to the end of the queue.
> * Otherwise, it is simply sent to the back of the queue.

(There is another bullet point on the Esolang page, but it is irrelevant for this answer.)

I take advantage of the fact that the decimal representation of the ASCII code for `6`, which is 54, is the reverse of the ASCII code for `-`, which is 45.

In my explanations, I will be listing out the steps to evaluate each program, skipping a few obvious steps. The explanation to the right of a queue is how to get from the previous queue to the current queue, not how to get from the current queue to the next queue.

### Normal

| QUEUE | EXPLANATION |
| --- | --- |
| `(`  `H`  `)`  `!`  `45`  `54` | Starting code. |
| `)`  `!`  `45`  `54`  `[H]` | Put `H` in a block. (Note that the results of an operation are put at the *end* of the queue.) |
| `!`  `45`  `54`  `[H]` `)` | Can’t be executed, so moved to end of queue. |
| `54`  `[H]` `)` | Pop `45`. |
| `[H]` `)` | Output "`6`". |
| `)`  `[H]` | Blocks can’t be executed normally. |
| `H` | Unblock `[H]`. |
|  | Halt. |

### Reversed

| QUEUE | EXPLANATION |
| --- | --- |
| `45`  `54`  `!`  `)`  `H`  `(` | Starting code. |
| `!`  `)`  `H`  `(` | Output "`-6`". |
| `H`  `(` | Pop `)`. |
|  | Halt. |
> 1 votes

# Answer
# convey, ~~8~~ 7 bytes

-1 byte if writting it horizontaly and not verticaly, (you save one line feed)

Prints -1 and 1

```
1-0
[}[

```

Try it online! (old version)

```
[}[
0-1

```

Try it online! (old version)

I wonder if there is someway to work whit the direction of the conveyor when you reverse the code, i have been trying to do something like that but it changes also the output position `}` and the code doesn't compile :(
> 1 votes

# Answer
# Knight, 4 bytes

```
O1~O

```

Try It Online!

Try It Online reversed!
> 1 votes

# Answer
# MathGolf, 3 bytes

```
d;3

```

Boring approach for now. Will see if a 2-byter is possible.

Outputs `3`/`-3`. `c;2` and `b;1` are two alternatives for `2`/`-2` and `1`/`-1` respectively.

Try it online or try it online reversed.

**Explanation:**

```
d    # Push builtin -3
 ;   # Discard the top of the stack
  3  # Push 3
     # (output the entire stack joined together implicitly)

```
> 0 votes

# Answer
# C (clang), 39 bytes

```
main(){puts("1");}//};)"1-"(stup{)(niam

```

Try it online!

Corrected as @AdamBorkBork error spotting.
> 0 votes

# Answer
# Bash, 16 bytes

```
echo -1 # 1 ohce

```

Try it online!
> 0 votes

# Answer
# Gaia, 4 bytes

```
2-”2

```

Try it online!

```
2-”	| push the string "2-"
   2	| push 2
	| implicit print TOS

```

```
2”	| push the string "2"
  -2	| push -2
	| implicit print TOS

```
> 0 votes

# Answer
# Python REPL, 4 bytes

```
1-0

```

Only works in the Python REPL environment.

Shaved one byte based on suggestion from Ilmari Karonen.
> 0 votes

# Answer
# Putt, 3 2 bytes

```
N1

```
1. `N`EGATE
2. PUSH `1`
3. Prints implicitly

## Reverse:

```
1N

```
1. PUSH `1`
2. `N`EGATE
3. Prints implicitly
> 0 votes

# Answer
# dc, 4 bytes

```
1p1_

```

prints 1

in reverse,

```
_1p1

```

prints -1
> 0 votes

# Answer
# ink, 6 bytes

```
1//1-\

```

Try it online!

### Reversed

```
\-1//1

```

Try it online!
> 0 votes

# Answer
# Pxem, filename: 6 bytes + content: 0 bytes = 6 bytes.

* Filename: `1.p.1-`
* Content: empty

Try it online!

`.p` is `until empty; do putchar pop; done`. `.1` is not a command; treated as a substring for literal.
> 0 votes

# Answer
# M4, 10 bytes, with warning

```
1dnl lnd1-

```

Try it online!

---

# M4, 16 bytes, clean output

```
1m4exit tixe4m1-

```

Try it online!
> 0 votes

# Answer
# Rattle, 5 bytes

```
+p;p-

```

Try it online!

This is pretty basic. Forwards, it will increment then print `1` (p- is an uncalled function). Reverse, it will decrement then print `-1` (p+ is an uncalled function).
> 0 votes

# Answer
# \<\>^v, 3 bytes

```
(;)

```

Prints -1.

Reversed:

```
);(

```

Prints 1.

### Explanation

In \<\>^v, the stack is initialized to `[0]` (only one element, the number 0) at the start of every program. `(` decrements the top of the stack, `;` prints the top of the stack and `)` increments the top of the stack. So `(;)` turns 0 into -1, then prints it, then turns it back into 0. Its reverse, `);(`, turns 0 into 1, prints it, then turns it back into 0.

Normal version (`(;)`)

Reversed (`);(`)
> 0 votes

---
Tags: code-golf, source-layout
---


title: Count the cells

text:
# Question
Title: Count the cells
Given a multi-line string as input containing characters `"|"`, `"_"` and `" "` (space), count the number of cells it contains.

A cell is the following structure of 3 characters by 2 lines:

```
 _
|_|

```

That is, an underscore on one line (the characters to its right and left don’t matter), and `"|_|"` right below it.

Two cells can share the same characters. For example, there are 3 cells here:

```
 _
|_|_
|_|_|

```

### Inputs and outputs

* You can assume that the input string will only contain the following characters: `"|"`, `"_"`, `" "`, and `"\n"`.
* You may take a list of strings as input, or a list of lists of chars, instead of a multi-line string.
* You may assume that there are at least 2 lines and 3 chars per line.
* You may pad each line with spaces so that all lines have the same length.

### Test cases

```
Input                               Output

 _
|_|                                 1

___
|_|                                 1

|_|                                 0

 _  _  __ __
|_|  _|  _|_||                      2

 _
|_|_
|_|_|                               3

 _
| |_
|_|_|                               1

 _
|_|_
|___|                               1

 _ _
|_|_|
|_|_|                               4

```

### Scoring

This is , so the shortest answer in bytes wins.

# Answer
> 10 votes
# 05AB1E, ~~18~~ ~~16~~ ~~14~~ 13 bytes

```
Ç°·üö7%J»232¢

```

Try it online!

# Explanation

```
Ç          convert each character to its ASCII code
°          map each number to 10**x
·          times two
üö         for each consecutive pair of rows, convert the number as a number in
           a base of the next number
7%         modulo 7
J          join each row into a string of numbers
»          join the rows together with a newline
232        push the string "232" (pushing it as a compressed number doesn't work due to a bug)
¢          and count how many times it appears in the string of digits

```

| Characters | ASCII codes | 2 * 10^first number converted from base-2\*10^second number, mod 7 |
| --- | --- | --- |
|  | 32, 32 | 4 |
| `_` | 32, 95 | 4 |
| `|` | 32, 124 | 2 |
| `_` | 95, 32 | 4 |
| `_` `_` | 95, 95 | 3 |
| `_` `|` | 95, 124 | 2 |
| `|` | 124, 32 | 1 |
| `|` `_` | 124, 95 | 1 |
| `|` `|` | 124, 124 | 2 |

# Answer
> 8 votes
# APL (Dyalog Unicode), 23 bytes

Anonymous tacit prefix function. Takes character matrix as argument.

```
≢∘⍸{'_||_'≡2↓,¯1⌽⍵}⌺2 3

```

Try it online!

`{``}⌺2 3` on each 2-by-3 submatrix:
`_`
`|_|`

`¯1⌽⍵` rotate the columns cyclically one step to the left
`_`
`||_`

`,` ravel (flatten)
`_||_`

`2↓` drop the first two elements
`_||_`

`'_||_'≡` does the string match?

`≢∘⍸` count the **i**ndices where true

# Answer
> 7 votes
# Python 3, 69 bytes

```
lambda a:sum(c+a[n+a.find('\n'):][:3]=='_|_|'for n,c in enumerate(a))

```

Try it online!

# Answer
> 4 votes
# Factor \+ `math.unicode`, 66 bytes

```
[| s | "_"s "|_|"s [ start-all* ] 2bi@ 10 s index v-n ∩ length ]

```

Attempt This Online!

Input is a multiline string padded with spaces so each line is the same length. This answer relies on there being a trailing newline in the input; if that is not allowed, let me know and I will change my answer.

It finds the starting indices of (possibly overlapping) subsequences `"_"` and `"|_|"`, subtracts the index of the first newline from the `"|_|"` indices, takes the intersection between the two sequences of indices, and returns the length of that.

# Answer
> 3 votes
# 05AB1E, ~~21~~ 20 bytes

```
€ü3øεü2ε€ÁJ„_|ºÅ¿]˜O

```

Input as a right-padded list of lines.

-1 byte using the rotate approach from *@Adám*'s APL (Dyalog Unicode) answer

Try it online or verify all test cases.

`€ÁJ„_|ºÅ¿]˜O` could alternatively be `ćÅs«]˜„|_2×¢` for the same byte-count:
Try it online or verify all test cases.

**Explanation:**

```
€                 # Map over each inner string of the (implicit) input-list:
 ü3               #  Create overlapping triplets
   ø              # Zip/transpose; swapping rows/columns
    ε             # Map over each inner list:
     ü2           #  Create overlapping pairs
       ε          #  Map over each pair of strings:
        €         #   Map over each string:
         Á        #    Rotate its characters once towards the right
          J       #   Join the two strings together
           „_|    #   Push string "_|"
              º   #   Mirror it to "_||_"
               Å¿ #   Check if the string ends with "_||_"
    ]             # Close the nested maps
     ˜            # Flatten the list of pairs
      O           # Sum
                  # (which is output implicitly as result)

```

```
        ć         #   Extract head ([a,b] to [b] and a with `a` on top)
         Ås       #   Pop this head, and leave just its middle character
           «      #   Append it to the string in the remainder-list
    ]             # Close the nested maps
     ˜            # Flatten the list of list of wrapped strings
      „|_         # Push string "|_"
         2×       # Double it to "|_|_"
           ¢      # Count how many "|_|_" are in the list
                  # (which is output implicitly as result)

```

# Answer
> 3 votes
# Retina 0.8.2, 37 bytes

```
&`(?<=(.)*)._.*¶(?<-1>.)*(?(1)^)\|_\|

```

Try it online! Link is to test suite that takes double-spaced test cases. Explanation: The lookbehind calculates the column that the left `|` should be in, then the arbitrary character above it is matched, then a `_`, then a .NET balancing group is used to advance the match to the corresponding column on the next line, then then `|_|` is matched. The `&` stage modifier is used to allow the matches to overlap.

# Answer
> 3 votes
# x86-64 machine code, 31 bytes

```
31 F6 6A FF 59 B0 0A F2 AE AE 8B 57 FD 8A 14 0F 81 FA 5F 7C 5F 7C 75 02 FF C6 AE 76 ED 96 C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the address of a null-terminated byte string in RDI, and returns the number of cells in EAX. This requires the lines to be padded to the same length.

In assembly:

```
f:  xor esi, esi        # Set ESI to 0. ESI will count the cells.
    push -1; pop rcx    # Set RCX to -1.
    mov al, '\n'        # Set AL to the ASCII code of the line feed.
    repne scasb         # Repeatedly compare AL with a byte from the string,
                        #  advancing the pointer each time, until they match.
                        #  Also count down RCX each time.  This consumes the first line
                        #  and makes RCX -(linelength+1), with linelength including \n.
    scasb               # Make one more comparison, advancing RDI once more.
r:  mov edx, [rdi-3]    # Load bytes from addresses RDI-3 to RDI into EDX.
    mov dl, [rdi+rcx]   # Replace the first of those bytes with one at address RDI+RCX,
                        #  the position in the previous line above the third byte.
    cmp edx, '_' | '|'<<8 | '_'<<16 | '|'<<24   # Compare EDX with the cell's bytes.
    jne s               # Jump to skip if they are not equal.
    inc esi             # (If equal) Add 1 to ESI.
s:  scasb               # Compare AL with a byte from the string; advance the pointer.
    jbe r               # Jump back, to repeat, if AL ≤ that byte (false only for 0).
    xchg esi, eax       # Switch the total from ESI into EAX.
    ret                 # Return.

```

# Answer
> 3 votes
# Vyxal, ~~19~~ 17 bytes

```
C6+¨pe11%ṅ⁋3l⁺↔SO

```

Try it online or verify test cases.

-2 bytes thanks to Command Master

# Answer
> 2 votes
# , 30 bytes

```
[:+/@,2 3('._.\|_\|'rxE,);._3]
```

Attempt This Online!

*+1 thanks to Neil for spotting a subtle bug*

* `2 3...;._3]` Looks at all 2 x 3 squares
* `('._.\|_\|'rxE,)` Checks if the flatten regex matches the required pattern
* `[:+/@,` Sums the matches

# Answer
> 2 votes
# Ruby, 78 bytes

```
->l{a,*l=l;g=0;l.sum{|b|w=a.chars.count{"#{b[g,3]}#{a[g+=1]}"=="|_|_"};a=b;w}}

```

Try it online!

# Answer
> 2 votes
# lin, 54 bytes

```
2`xp"`,*3`xp \; `'"`', \+ `/
`,* `flat `_`"._.\|_\|"?t

```

Try it here! Takes a list of equal-sized space-padded strings.

For testing purposes, the code below auto-converts a space-padded multiline string:

```
\@..
 _  _  __ __
|_|  _|  _|_||
@ >ls ; outln
2`xp"`,*3`xp \; `'"`', \+ `/
`,* `flat `_`"._.\|_\|"?t

```

## Explanation

Prettified code:

```
2`xp ( `,* 3`xp \; `' ) `', \+ `/
`,* `flat `_` "._.\|_\|"?t

```
* `2`xp (...) `',` pairwise flatmap...
    + ``,* 3`xp \; `'` zip and triplet-wise map...
        - ``,* `flat `_`` zip, flatten, convert to string
        - `"._.\|_\|"?t` check if matches regex `/._.\|_\|/`
* `\+ `/` sum

# Answer
> 2 votes
# MATL, ~~21~~ 20 bytes

```
Ji6\^[aJa;0J0]_Z+4=z

```

Input is a 2-dimensional char array (rows should be righty-padded with spaces so that they have the same length).

Try it online! Or verify all test cases (this displays each input together with output, for convenience).

### How it works

Modulo 6 is applied to (the ASCII code of) the chars in the input, which gives `5` for `_`, `4` for `|` and `2` for . Element-wise exponentiation with the imaginary unit `j` respectively gives `j`, `1` and `-1`.

Two-dimensional convolution is then used to detect the desired pattern, using the matrix `[-1, j, -1; 0, j, 0]` as kernel (note that convolution flips the kernel in both directions). The pattern is detected whenever the convolution gives exactly `4`. Thus the final result is the number of times that `4` appears in the convolution output.

# Answer
> 1 votes
# Charcoal, 28 bytes

```
ＷＳ⊞υιＩΣＥυ∧κＬΦ⌕Ａι|_|⁼_§§υ⊖κ⊕λ

```

Try it online! Link is to verbose version of code. Assumes input is a rectangular list of newline-terminated strings. Explanation:

```
ＷＳ⊞υι

```

Input the strings into an array.

```
   υ                      Array of strings
  Ｅ                       Map over strings
     κ                    Current index
    ∧                     Logical And
        ⌕Ａ                All overlapping matches of
           |_|            Literal string `|_|`
          ι               In current string
       Φ                  Filtered where
                  υ       Array of strings
                 §        Indexed by
                    κ     Outer index
                   ⊖      Decremented
                §         Indexed by
                      λ   Current match position
                     ⊕    Incremented
              ⁼           Is equal to
               _          Literal string `_`
      Ｌ                   Take the length
 Σ                        Take the sum
Ｉ                         Cast to string
                          Implicitly print

```

# Answer
> 0 votes
# Dyalog APL, 23 bytes

```
≢∘⍸1↓'|_|'∘⍷∧¯1⊖1⌽'_'∘=

```

Attempt This Online!

This is an alternative to Adám’s ⌺-based solution that is exactly as long but quite a bit faster:

```
      f←≢∘⍸{'_||_'≡2↓,¯1⌽⍵}⌺2 3
      g←≢∘⍸1↓'|_|'∘⍷∧¯1⊖1⌽'_'∘=
      m←(,⍨1e3)⍴' _|'[?1e6⍴3]
      'cmpx'⎕CY'dfns'
      cmpx'f m' 'g m'
  f m → 2.1E0  |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  g m → 4.0E¯3 | -100%

```

The basic idea is to find where the top parts (`_`) and the bottom parts (`|_|`) of the squares are, align them, and count how many times they overlap.

We’ll use a modified version of the fifth test case as an example:

```
      ⎕←m←3 5⍴'__|_||_|_ |_|_|'
__|_|
|_|_
|_|_|

```

First we find where the `|_|`s are:

```
      ('|_|'∘⍷)m
0 0 1 0 0
1 0 0 0 0
1 0 1 0 0

```

The 1s indicate where the `|_|`s begin. This means that the rightmost two columns will always consist of 0s.

Then we find where the `_`s are:

```
      ('_'∘=)m
1 1 0 1 0
0 1 0 1 0
0 1 0 1 0

```

We need to move the 1s one step to the left and one step downwards to align them with the 1s in the `|_|` matrix, then AND the two matrices.

We can move the 1s one step to the left by rotating once along the last axis:

```
      (1⌽'_'∘=)m
1 0 1 0 1
1 0 1 0 0
1 0 1 0 0

```

The leftmost column wraps around to the right, creating an extra 1 in the rightmost column. Fortunately, this doesn’t matter because the corresponding column in the `|_|` matrix must consist of 0s, so this column will get masked out anyway.

Next we move the 1s one step downwards by doing a -1 rotate along the first axis:

```
      (¯1⊖1⌽'_'∘=)m
1 0 1 0 0
1 0 1 0 1
1 0 1 0 0

```

Now the 1s are aligned, but the bottommost row wraps around to the top, creating extra 1s in the topmost row. This is a problem because the corresponding row in the `|_|` matrix can contain 1s. We can fix this by dropping the topmost row after ANDing the two matrices:

```
      ('|_|'∘⍷∧¯1⊖1⌽'_'∘=)m
0 0 1 0 0
1 0 0 0 0
1 0 1 0 0
      (1↓'|_|'∘⍷∧¯1⊖1⌽'_'∘=)m
1 0 0 0 0
1 0 1 0 0

```

Finally, we count the number of 1s:

```
      (≢∘⍸1↓'|_|'∘⍷∧¯1⊖1⌽'_'∘=)m
3

```

---
Tags: code-golf, ascii-art
---


title: Chicken McNugget Numbers

text:
# Question
Title: Chicken McNugget Numbers
### Description

Chicken McNugget numbers are numbers that can be expressed as a sum of \\$6\\$, \\$9\\$ or \\$20\\$ \- the initial sizes of the famous Chicken McNuggets boxes sold by McDonald's. In that sum, a number may occur more than once, so \\$6 + 6 = 12\\$ is such a number too, and the number must "contain" at least one of the mentioned sizes. The first Chicken McNugget numbers are:

\begin{align\*}&6\\ &9\\ &6 + 6 = 12\\ &6 + 9 = 15\\ &9 + 9 = 6 + 6 + 6 = 18\\ &20\\ &6 + 6 + 9 = 21\\ &\dots \end{align\*}

### Challenge

Your task is to write a program or function, that, given a positive integer, determines whether this number can be expressed in the described way, therefore is such a Chicken McNugget number. It should then output a truthy or falsy value based on its decision.

### Test cases

```
6 -> true
7 -> false
12 -> true
15 -> true
21 -> true
40 -> true
42 -> true

```

This is , so the shortest answer in bytes wins and the standard loopholes apply!

# Answer
# Python, 27 bytes

```
lambda n:0x82492cb6dbf>>n&1

```

Try it online!
> 38 votes

# Answer
# Python 3, 24 bytes

```
lambda n:0<=n--n%3*20!=3

```

Try it online!

## Explanation

With `6` and `9` alone, one can make all integers divisible by `3` which are greater than `3`, as is stated in ovs's comment to the challenge. It is assumed that one can also make `0`. In conclusion, one can make `0,6,9,12,15,...`.

With one instance of `20`, one can make: `20,26,29,32,35,...`.

With two instances of `20`, one can make: `40,46,49,52,55,...`.

Three instances is never necessary, for `3 x 20 = 10 x 6`.

---

Notice that the cases where no `20` is needed is also divisible by 3; the cases where one `20` is needed leaves a remainder of `2`; the cases where two `20` is needed leaves a remainder of `1`.

The number of `20` needed can hence be calculated by `(-n)%3`. Then, we do `n-(((-n)%3)*20)` to remove the number of `20` needed from the number. We then check that this number is non-negative, but is not `3`.
> 29 votes

# Answer
# Python 2, 28 bytes

```
lambda n:-n%3-n/20<(n%20!=3)

```

Try it online!
> 8 votes

# Answer
# Jelly, 11 bytes

```
ṗ3’æ.“©µÞ‘ċ

```

Try it online!

### How it works

```
ṗ3’æ.“©µÞ‘ċ  Main link. Argument: n

ṗ3           Cartesian power; yield all 3-tuples over [1, ..., n].
  ’          Decrement all coordinates.
     “©µÞ‘   Yield [6, 9, 20].
   æ.        Take the dot product of each 3-tuple and [6, 9, 20].
          ċ  Count the occurrences of n (Positive for Chicken McNuggets numbers).

```
> 7 votes

# Answer
# Haskell, 36 bytes

```
f n|n<1=n==0
f n=any(f.(n-))[6,9,20]

```

Try it online!

## Explanation

This solution is about as straightforward as it can get. The first line declares that for any number less than 1 it is a McNugget number if `n==0`. That is to say that `0` is a McNugget number and all negative numbers are not.

The second line declares that for all other numbers, `n` is a McNugget number if it minus any of the Nugget sizes is a McNugget number.

This is a pretty simple recursive search.
> 5 votes

# Answer
# Jelly, 11 bytes

```
_20$%3$¿o>3

```

Try it online!

Port of my Python answer, but slightly modified: subtract `20` until divisible by `3`, then check whether it belongs to `0,6,9,...` by mapping `0` to the input (by using `or`), and then check if it is greater than `3`.

The only three numbers that produce `0` upon completing the first step is `0`, `20`, or `40`, with the first one being out of the domain, and the rest being greater than `3`.
> 3 votes

# Answer
# Python 3, 48 46 42 bytes

```
lambda n:n+50in b'2345679:<=?@BCEHIKNQTW]'

```

Try it online!

Switches `True` and `False`.
> 3 votes

# Answer
# Mathematica, 53 bytes

```
!Flatten@Table[Tr/@Tuples[{6,9,20},i],{i,#}]~FreeQ~#&

```
> 3 votes

# Answer
# Mathematica, 30 bytes

```
{6,9,20}~FrobeniusSolve~#!={}&

```

Try it on Wolfram Sandbox.
> 3 votes

# Answer
# Mathematica, 20 bytes

```
0<=#-20Mod[-#,3]!=3&

```

Anonymous function. Takes a number as input and returns `True` or `False` as output. Logic copied from Leaky Nun's answer, with some added abuse of `Inequality`.
> 3 votes

# Answer
# x86-64 Machine Code, 22 bytes

```
48 B8 41 92 34 6D DB F7 FF FF 83 F9 40 7D 03 48 D3 E8 83 E0 01 C3

```

The above bytes define a function in 64-bit x86 machine code that determines whether the input value is a Chicken McNugget number. The single positive integer parameter is passed in the `ECX` register, following the Microsoft 64-bit calling convention used on Windows. The result is a Boolean value returned in the `EAX` register.

**Ungolfed assembly mnemonics:**

```
; bool IsMcNuggetNumber(int n)
; n is passed in ECX
    movabs  rax, 0xFFFFF7DB6D349241   ; load a 64-bit constant (the bit field)
    cmp     ecx, 64
    jge     TheEnd                    ; if input value >= 64, branch to end
    shr     rax, cl
TheEnd:
    and     eax, 1                    ; mask off all but LSB
    ret

```

Obviously, this plays heavily off of Anders Kaseorg's solution in Python, in that it is based around a bit-field representing the values that are Chicken McNugget numbers. Specifically, each bit in this field that corresponds to a valid Chicken McNugget number is set to 1; all other bits are set to 0. (This considers 0 to be a valid Chicken McNugget number, but if you don't like that, your preference is a single-bit modification away.)

We start off by simply loading this value into a register. It is a 64-bit value, which already takes 8 bytes to encode, plus we need a one-byte REX.W prefix, so we are really being quite spendthrift in terms of bytes, but this is the heart of the solution, so I guess it's worth it.

We then shift the field right by the input value.* Finally, we mask off all but the lowest-order bit, and that becomes our Boolean result.

However, since you cannot shift by more than the number of bits actually in the value, this works only for inputs from 0–63. To support higher input values, we insert a test at the top of the function that branches to the bottom of the input value is \>= 64. The only thing interesting about this is the we *preload* the bit-field constant in `RAX`, and then branch down to the instruction that masks off the lowest-order bit, thus ensuring that we always return 1.

**Try it online!**
(The C function call there is annotated with an attribute that causes GCC to call it using the Microsoft calling convention that my assembly code uses. If TIO had provided MSVC, this wouldn't be necessary.)

\__
* As an alternative to a shift, we could have used the x86 `BT` instruction, but that's 1 byte longer to encode, so no advantage. Unless we were *forced* to use a different calling convention that didn't conveniently pass the input value in the `ECX` register. This would be a problem because `SHR` *requires* that its source operand be `CL` for a dynamic shift count. Therefore, a different calling convention would require that we `MOV`ed the input value from whatever register it was passed in to `ECX`, which would cost us 2 bytes. The `BT` instruction can use *any* register as a source operand, at a cost of only 1 byte. So, in that situation, it would be preferable. `BT` puts the value of the corresponding bit into the carry flag (CF), so you would use a `SETC` instruction to get that value in an integer register like `AL` so it could be returned to the caller.

---

**Alternative implementation, 23 bytes**

Here is an alternative implementation that uses modulo and multiplication operations to determine whether the input value is a Chicken McNugget number.

It uses the System V AMD64 calling convention, which passes the input value in the `EDI` register. The result is still a Boolean, returned in `EAX`.

Note, though, that unlike the above code, this is an *inverse* Boolean (for implementation convenience). It returns `false` if the input value is a Chicken McNugget number, or `true` if the input value is *not* a Chicken McNugget number.

```
                    ; bool IsNotMcNuggetNumber(int n)
                    ; n is passed in EDI
8D 04 3F            lea    eax, [rdi+rdi*1]   ; multiply input by 2, and put result in EAX
83 FF 2B            cmp    edi, 43
7D 0E               jge    TheEnd             ; everything >= 43 is a McNugget number
99                  cdq                       ; zero EDX in only 1 byte
6A 03               push   3
59                  pop    rcx                ; short way to put 3 in ECX for DIV
F7 F1               div    ecx                ; divide input value by 3
6B D2 14            imul   edx, edx, 20       ; multiply remainder of division by 20
39 D7               cmp    edi, edx
0F 9C C0            setl   al                 ; AL = (original input) < (input % 3 * 20)
                 TheEnd:
C3                  ret

```

What's ugly about this is the need to explicitly handle input values \>= 43 by a compare-and-branch at the top. There are obviously other ways of doing this that don't require branching, like caird coinheringaahing's algorithm, but this would take a *lot* more bytes to encode, so isn't a reasonable solution. I figure I'm probably missing some bit-twiddling trick that would make this work out more elegantly and be fewer bytes than the bitfield-based solution above (since encoding the bitfield itself takes so many bytes), but I've studied this for a while and still can't see it.

Oh well, try it online anyway!
> 3 votes

# Answer
# 05AB1E, 17 16 bytes

```
ŽGç₂в©IED®âO«]I¢

```

Try it online!

Explanation

```
  ŽGç₂в                 The list [6, 9, 20]
       ©                Store this list in register_c
        IE              Loop <input> number of times
           ®â           Cartesian product stack contents with list in register_c
             O          Sum up the contents of each sub array
          D   «         List duplicated before taking Cartesian product, concat
               ]        End for loop
                I¢      Count occurences of input

```
> 3 votes

# Answer
# JavaScript (ES6), ~~69~~ 64 bytes

```
n=>'ABCDEFHIKLNOQRTWXZ]`cfl'.includes(String.fromCharCode(n+65))

```

```
f=
n=>'ABCDEFHIKLNOQRTWXZ]`cfl'.includes(String.fromCharCode(n+65))
```

```
<input onkeydown=a.innerHTML=f(this.value)>
<pre id=a>
```

Outputs `false` for Chicken McNugget numbers, `true` otherwise.
> 2 votes

# Answer
# Java, ~~21~~ ~~57~~ 24 bytes

**Try it online!**

Golfed:

```
n->(n-=n*2%3*20)>=0&n!=3

```

Ungolfed:

```
import java.util.*;

public class ChickenMcNuggetNumbers {

  private static final Set<Integer> FALSE_VALUES = new HashSet<>(Arrays.asList(
    new Integer[] { 0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23,
    25, 28, 31, 34, 37, 43 }));

  public static void main(String[] args) {
    for (int i = 0; i < 45; ++i) {
      System.out.println(i + " -> expected=" + !FALSE_VALUES.contains(i)
        + ", actual=" + f(n->(n-=n*2%3*20)>=0&n!=3, i));
    }
  }

  public static boolean f(java.util.function.Function<Integer, Boolean> f, int n) {
    return f.apply(n);
  }
}

```
> 2 votes

# Answer
# Add++, 35 bytes

```
D,f,@,A6$%0=@20$%0=A3$%0=A8<A43<s1<

```

Try it online!

Look ma, no while loops. Or strings. Or lists. Or really anything that helps save bytes. But mainly because Add++ doesn't know what any of those are.

3 months later, I realised that this was invalid, and fixed it. Somehow, that golfed it by 13 bytes. This is a function that takes one argument and tests whether that argument is a Chicken McNugget number or not.

## How it works

```
D,f,@,                        - Create a monadic (one argument) function called f (example argument: 3)
A                             - Push the argument again; STACK = [3 3]
 6                            - Push 6;                  STACK = [3 3 6]
  $                           - Swap the top two values; STACK = [3 6 3]
   %                          - Modulo;                  STACK = [3 3]
    0                         - Push 0;                  STACK = [3 3 0]
     =                        - Are they equal?          STACK = [3 0]
      @                       - Reverse the stack;       STACK = [0 3]
       20                     - Push 20;                 STACK = [0 3 20]
         $                    - Swap the top two values; STACK = [0 20 3]
          %                   - Modulo;                  STACK = [0 3]
           0                  - Push 0;                  STACK = [0 3 0]
            =                 - Are they equal?          STACK = [0 0]
             A                - Push the argument;       STACK = [0 0 3]
              3               - Push 3;                  STACK = [0 0 3 3]
               $              - Swap the top two values; STACK = [0 0 3 3]
                %             - Modulo;                  STACK = [0 0 0]
                 0            - Push 0;                  STACK = [0 0 0 0]
                  =           - Are they equal?          STACK = [0 0 1]
                   A          - Push the argument;       STACK = [0 0 1 3]
                    8         - Push 8;                  STACK = [0 0 1 3 8]
                     <        - Less than;               STACK = [0 0 1 0]
                      A       - Push the argument;       STACK = [0 0 1 0 3]
                       43     - Push 43;                 STACK = [0 0 1 0 3 43]
                         <    - Less than;               STACK = [0 0 1 0 0]
                          s   - Sum;                     STACK = [1]
                           1  - Push 1;                  STACK = [1 1]
                            < - Less than;               STACK = [0]

```
> 2 votes

# Answer
# Python 2, 51 bytes

*-1 byte thanks to @LeakyNun*

```
lambda n:max(n>43,25<n>n%3>1,5<n>n%3<1,n in[20,40])

```

Try it online! Footer prints all non McNugget numbers
> 1 votes

# Answer
# Pyth, 15 bytes

```
fg.{CM"     "{T./

```

Try it online!

The string contains the characters corresponding to codepoints 6, 9, and 20.
> 1 votes

# Answer
# Javascript, ~~92~~ ~~78~~ 72 bytes

\*saved 14 bytes thanks to @Jonasw

```
a=>!(a in[0,1,2,3,4,5,7,8,10,11,13,14,16,17,19,22,23,25,28,31,34,37,43])

```

Uses the fact that "All integers are McNugget numbers except 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, and 43." from @LeakyNun's comment
> 1 votes

# Answer
# Haskell, ~~64~~ 56 bytes

I didn't do any bit trickery, but looking at the other answers it might actually be shorter to import the `Bits` module and use those methods. This approach checks much more directly.

```
f x=(\l->elem x[i*6+j*9+k*20|i<-l,j<-l,k<-l,x/=0])[0..x]

```
> 1 votes

# Answer
# Excel, 87 bytes

```
=AND(OR(MOD(A1,3)*MOD(A1,20)*IF(A1>43,MOD(A1-40,3),1)*IF(A1>23,MOD(A1-20,3),1)=0),A1>5)

```

Alternatively, 92 bytes:

```
=CHOOSE(MOD(A1,3)+1,A1>3,IF(A1>43,MOD(A1-40,3)=0,A1=40),IF(A1>23,MOD(ABS(A1-20),3)=0,A1=20))

```
> 1 votes

# Answer
# APL (Dyalog), 19 bytes

```
⊢∊6 9 20+.×⍨∘↑∘⍳3⍴⊢

```

with `⎕IO←0`

Same algorithm with Dennis's answer

Try it online!
> 1 votes

# Answer
# Retina, 26 bytes

```
.+
$*
^(1{6}|1{9}|1{20})+$

```

Try it online!
> 1 votes

# Answer
# PHP, 69+1 bytes

```
for($n=$argn;$n>0;$n-=20)if($n%3<1)for($k=$n;$k>0;$k-=9)$k%6||die(1);

```

exits with `1` for a Chicken McNugget Number, `0` else.

Run as pipe with `-n` or try it online.
> 1 votes

# Answer
# Jelly, 10 bytes

```
Œṗḟ€“©µÞ‘Ạ

```

Try it online!

Outputs in the opposite direction; returning `false` indicates that the input is a Chicken McNugget number. The TIO footer swaps this for you.

## How it works

```
Œṗḟ€“©µÞ‘Ạ - Main link. Takes an integer n on the left
Œṗ         - Integer partitions of n; all ways to sum integers to n
    “©µÞ‘  - Yield [6, 9, 20]
   €       - Over each partition P:
  ḟ        -   Remove all 6s, 9s and 20s
         Ạ - Are all resulting lists non-empty?

```
> 1 votes

# Answer
# Python 2, 61 bytes

```
lambda n:n in[int(c,36)for c in'1234578ABDEGHJMNPSV']+[37,43]

```

Try it online!
> 0 votes

# Answer
# Mathematica, 59 bytes

```
!Select[IntegerPartitions@#,{6,9,20}~SubsetQ~#&]=={}&&#!=0&

```
> 0 votes

# Answer
# Pari/GP, 44 bytes

```
n->n&&#(1/(1-x^6)/(1-x^9)/(1-x^20)%x^n++)==n

```

Try it online!
> 0 votes

# Answer
# Javascript 37 bytes

Takes a positive integer `n` and outputs `true` for Chicken McNugget numbers and `false` for others.

```
F=n=>!(n<0||(n%6&&!F(n-9)&&!F(n-20)))

```

## Explanation

```
F=n=>!(            // negate the internal test for non-Chicken McNugget numbers
    n<0 || (       // if n < 0, or
        n%6 &&     // if n % 6 is truthy,
        !F(n-9) && // and n-9 is not a Chicken McNugget number
        !F(n-20)   // and n-20 is not a Chicken McNugget number
                   // then n is not a Chicken McNugget number
    )
)

```

The recursion on this function is heinous, and for any sufficiently large `n`, you will exceed call stack limits. Here's a version that avoids those limits by checking if `n` is larger than the largest non-Chicken McNugget number (43 bytes \[bonus points for being the largest non-Chicken McNugget number?\]):

```
F=n=>n>43||!(n<0||(n%6&&!F(n-9)&&!F(n-20)))

```

```
F=n=>n>43||!(n<0||(n%6&&!F(n-9)&&!F(n-20)))

$('#input').on('keyup', () => $('#output').text(F(parseInt($('#input').val(), 10))))
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<input type="text" id="input" />
<span id="output"></span>
```
> 0 votes

# Answer
# JavaScript ES5, 46 bytes

```
n=>n>5&&(!(n%20)||(n<24?!(n%3):n<44?n%3-1:1));

```

**Explicit boolean answer, 50 bytes:**

```
n=>!!(n>5&&(!(n%20)||(n<24?!(n%3):n<44?n%3-1:1)));

```

Clumsy, but it gets the job done. Returns `false` or `0` for every value that isn't 0, 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, or 43, and `true`, `-1`, or `1` for everything else.

Explicit solution returns `true` or `false` only.

```
n=>!!(                                          ); forces Boolean type (optional)
      n>5                                          false for 0, 1, 2, 3, 4, 5 (and negative inputs)
            !(n%20)                                explicit true for 20, 40
                      n<24?!(n%3)                  false for 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23
                                  n<44?n%3-1       false for 25, 28, 31, 34, 37, 43

```
> 0 votes

# Answer
# Clojure 33 bytes

An on ok quick attempt: `#(-> %(rem 20)(rem 9)(rem 6)(= 0))`
> 0 votes

---
Tags: code-golf, number, decision-problem, integer-partitions
---


title: Build a Turing *incomplete* language

text:
# Question
Title: Build a Turing *incomplete* language
The world is full of Turing-complete programming languages. Just about every useful language (and most useless ones) are Turing-complete. Some even became Turing-complete by accident. Often this is great, since every Turing-complete language supports the same power of universal computation. But the power of Turing completeness also comes with a curse! The halting problem is undecidable for arbitrary programs in a Turing-complete language, and more generally, it’s impossible to analyze arbitrary programs in any non-trivial way. Sometimes we need less powerful languages.

It takes great care to design a useful language that falls short of Turing completeness. That’s the subject of this challenge!

## Requirements

Write an interpreter that will accept a **program** and some **input** for the program, and produce some **output**. The program, input, and output are given using simple data types of your choice.

* Examples of “simple” data types: booleans; numbers; strings (bytes or Unicode); arrays or mappings of simple data types; algebraic data types defined in your interpreter.
* Examples of data types *not* considered “simple”: function expressions; a subset of strings representing valid programs in some language (unless the subset is validated by your interpreter); generalized algebraic data types. (This restriction is intended to disqualify trivial answers such as the identity function in Agda.)

Your **input format** must include some way to express arbitrarily sized **natural numbers**, in a reasonable representation of your choice (e.g. arrays or strings of unary, binary, or decimal digits, or directly as big integers if your host language has them). Your **output format** must include at least two values, distinguishable from each other, to represent **“true” and “false”**. Whether the formats can express anything else is up to you.

You may interpret programs in any target language, existing or new, under three conditions:

* Your interpreter must be observably **deterministic**: for a given program and input, you must always produce the same output.
* Your interpreter must **not be Turing-complete**. Explain why this is the case—for example, it might be Turing incomplete because the interpreter eventually halts on every program and input, or because its halting problem is otherwise decidable.
* As a minimum standard of usefulness, your target language must be able to express **every polynomial-time function** from natural numbers to booleans. Explain why this is the case. (To be clear, “polynomial-time” is defined over the length of the input in binary bits, even if your chosen representation of naturals is less efficient.)

Whether any other functions are expressible is up to you—for example, you might design your language around the primitive recursive functions, the elementary functions, or Gödel’s System T, each of which includes all polynomial-time functions.

Your interpreter may be written in any existing host language. You may assume it runs on an ideal machine with unlimited memory and pointers big enough to access it.

This is : make the shortest interpreter you can!

## Clarifications

I believe these points follow from the requirements, but they’re listed here in the hope of being helpful. Feel free to request additional clarifications in the comments.

* As per our default rules, your interpreter will be a program or function that follows our usual conventions for input and output. However, programs in your target language are not bound by these rules—for example, if you decide that programs in your target language will be snippets that perform I/O by accessing a predefined variable, that is fine, as long as your interpreter translates this convention by (say) automatically reading from STDIN to the variable at startup and writing the variable to STDOUT at exit. (This can be viewed as a natural consequence of our policy that languages are defined by their interpreters.)
* You may of course use any data types you want *within* your language, as long as the program, input, and output types are simple data types.
* Your interpreter must be prepared to accept *anything* in your chosen simple data type for programs as a program. Your interpreter may of course perform extra validity checks on the program and throw errors or fall back to some default behavior or do something else that respects the requirements—but you may not impose extra validity constraints on programs purely at the specification level. Writing “`eval` but you’re not allowed to pass in anything except deterministic programs that halt” does not solve this challenge.
* Because of the determinism requirement, an interpreter that works by executing arbitrary code with a timeout in seconds is unlikely to be valid. (Doubly so if it leaves programs enough wiggle room to disable or evade the timeout in some underhanded way.)
* Although I ~~am willing to be~~ may already have been proven wrong, my expectation is that solving this challenge will require doing some actual work to interpret a language. I’m not looking for solutions that put in 1% of this work to satisfy 80% of the requirements, whatever that means—that wouldn’t be fair to those who put in the effort to solve the full challenge as written.
* I updated the challenge with a requirement for the representation of natural number inputs to be “reasonable” after realizing there was a loophole using an unreasonable representation of naturals. Specifically: if we enumerate all polynomial-time functions as \\$p\_0, p\_1, p\_2, \dotsc\\$, the unreasonable representation of \\$n \in \mathbb N\\$ as \\$(p\_0(n), p\_1(n), \dotsc, p\_{n-1}(n))\\$ allows any polynomial-time function \\$p\_m\\$ to be “programmed” as \\$\\{0 \mapsto p\_m(0), 1 \mapsto p\_m(1), \dotsc, m \mapsto p\_m(m), n \mapsto n\_m\text{ for }n \> m\\}\\$, with every output hard-coded into either the program or the input! (I don’t think any of the existing answers have tried to exploit such an unreasonable representation.)

## Related challenges

(Deleted sandbox post)

# Answer
# Python 2, 38 bytes

```
lambda s,n:s.strip("()+*%n")or eval(s)

```

Try it online!

This evaluates a subset of Python 2 given by arithmetic expressions using only characters `()+*%n`, acting on natural-number input `n`. This computes the class ELEMENTARY, as the closure of the expressions in the basis

\\$\\{n+m, n^2, n\bmod m, 2^n\\}\\$

as noted in the Wikipedia article on ELEMENTARY and proven in Superpositions of elementary arithmetic functions. This moreover shows that Python operators can not only do primality testing, but any polynomial-time computable function.

The paper's argument seems to be based on constructions similar to Lopsy's prime-testing solution, encoding lists as digits in a large base and expressing bounded summation on those elements via arithmetic operations. The proof uses this expression for binomial coefficients as an intermediate step.

We check that our operators can express all operations in the basis. The `+`, `**`, and `%` operators do addition, exponent, and modulo. We can get the \\$2\\$ for \\$n^2\\$ and \\$2^n\\$ as \\$2=0^0+0^0\\$, where \\$0\\$ is `n**n%n**n`, avoiding the modulo-by-zero that simply `n%n` would give for `n=0`. Parentheses allow arbitrary composition of sub-expressions, and projection is trivial. We can interpret outputs as Booleans by associating `True=1, False=0`, as is standard in Python.

To ensure we that only this subset can be evaluated, we check that the input expression `s` is limited to the characters `()+*%n` by stripping them from `s` and returning what remains if non-empty. Note that an invalid string is never evaluated, rather than evaluated then discarded, preventing it from anything strange it could call or overwrite to allow its output to escape.

The really isn't anything extra that's non-trivial that can be done with the whitelisted characters that we might worry allows Turing completeness. The letter `n` alone can't spell any function or keyword. We can get multiplication with `*`, but this is of course elementary. We can't even get negative numbers or floats, though these would still be harmless. We can get the empty tuple `()`, but nothing interesting can be done with it.
> 21 votes

# Answer
# APL (Dyalog Unicode), <sup>~~15~~</sup> 14 bytes

```
(⍎⍞~'⎕⍎⍣⌶?{')⎕

```

Try it online!

A full program that takes two inputs (an array of numbers in APL syntax, and then a line of APL code) from STDIN and prints the result to STDOUT. The given APL code is sanitized by deleting characters that have a possibility to invoke an unbounded loop/recursion or access to the external system.

Since the input function is written in a single line, it must necessarily consist of built-in functions and operators, possibly including assignment. Using dfns is banned by the character `{`, and tradfns cannot appear because a tradfn requires at least two lines of code to be defined. Control structures and the Branch primitive are only meaningful inside trandfns, so they are automatically banned as a side effect.

The summary of banned characters with reasons:

* by itself is used merely as an I/O primitive, but it is used as the first character of all the system functions, which include shell and filesystem access.
* is called an I-beam, which grants access to experimental features. Some of the features include access to system.
* `{` is required to create a dfn/dop, and has no other uses.
* is power operator, which can act as a for-loop or a while-loop depending on how it is used.
* `?` is random number generator. It is excluded to satisfy the determinism requirement.
* is APL's eval. I can't think of a hole accessible via  when `⎕UCS`, `⎕AV` etc are banned, but it is included to be safe.

Any one line of APL code without the six characters is guaranteed to terminate, thus it is not Turing-complete.

Here is a more formal proof via structural induction. Here is the list of all language elements for reference. Let's define a **Q-function** to be a function that terminates by returning a deterministic array or erroring in finite time.

* All primitive functions except `⍎?` along with bracket indexing are Q-functions.
* All primitive operators except `⍣⌶` become Q-functions when given Q-functions and/or arrays as operands.
* Tacit functions made of Q-functions are Q-functions, because tacit functions cannot express recursive functions. Also, something like `g←⊢,g` does not create a self-reference; it is either illegal (if `g` is not defined beforehand) or creates a new function based on the previous value of `g`.
* Any variable created/modified via assignment can only result in a Q-function or an array.

The remaining functionality can be proven to be powerful enough to express elementary functions: Taking multiple arguments as a single array (e.g. subtraction function `f(x,y)` takes a length 2 array),

* Zero = `-⍨`, Successor = `1∘+`, and Subtraction = `0⌈-/`.
* Projection can be expressed as an indexing via .
* Composition can be written as `h g1,g2,g3,...`
* Bounded summation and product can be implemented as tacit functions: summation is `+/(0,⍳∘⊃)(g,)¨∘⊂1∘↓` and change `+/` to `×/` for product.
> 15 votes

# Answer
# APL (Dyalog Unicode), 42 bytes

```
{∇{×|≡⊃c i←⍺:⊃c⍺⍺⍣(i⊃⍵)⊂⍵⋄c(⊣+×)@i⊢⍵}/⍺,⍵}

```

Try it online!

I thought I'd give it a go at a more "proper" submission. This function interprets the programming language LOOP represented as a nested numeric array (which is used like an ADT), and the input to the LOOP program is represented as a simple numeric vector (enclosed once, for the sake of code golf).

### The concept

LOOP has four kinds of commands: (`x_i` are variables and `P` are sub-programs)

* `x_i := 0` (zero)
* `x_i := x_i + 1` (increment)
* `P_1; P_2` (sequence)
* `LOOP x_i DO P END` (bounded loop): Run `P` `x_i` times.

Here I represent a sequence of commands as an array `[P_k P_k-1 ... P_2 P_1]` instead of explicit concatenation, therefore eliminating a command. The order of command is reversed for the sake of code golf.

Each command in the program is encoded as a `(c i)` pair, where `i` is the variable index to refer to and `c` is the command to run on it. I use `c←0` for zero, `c←1` for increment, and `c←P` for the bounded loop.

For an illustration, the pseudocode

```
x_2 += x_1 * 2; x_1 = 0

```

can be written in LOOP as

```
LOOP x_1 DO
  x_2 := x_2 + 1
  x_2 := x_2 + 1
END;
x_1 := 0

```

and the representation for my submission is

```
(0 1)(((1 2)(1 2))1)
      ------------    Increment x_2 twice
     ---------------  Loop x_1 times
-----                 Assign zero to x_1

```

For the computational power, LOOP can precisely represent primitive recursive functions, thus satisfying the requirement of the challenge.

### The code

```
{∇{×|≡⊃c i←⍺:⊃c⍺⍺⍣(i⊃⍵)⊂⍵⋄c(⊣+×)@i⊢⍵}/⍺,⍵}  ⍝ ⍺←Program; ⍵←Input
{                                     ⍺,⍵}  ⍝ Append ⍵ to ⍺ for reduction
 ∇{                                 }/      ⍝ Reduce, exposing the self reference to inner dfn:
       c i←⍺               ⍝ Extract command type and index from the next command
   ×|≡⊃     :              ⍝ If the command type is not simple (a loop subprogram):
             ⊃c⍺⍺⍣(i⊃⍵)⊃⍵  ⍝ Run the subprogram c x_i times on the state ⍵
                         ⋄            ⍝ Otherwise
                          c(⊣+×)@i⊢⍵  ⍝ Multiply c and then add c to x_i, which is equivalent to
                                      ⍝ If c is 1, add 1 to x_i; if c is 0, set x_i to 0

```
> 11 votes

# Answer
# JavaScript (Babel Node), ~~59~~ ~~51~~ 47 bytes

```
n=>g=([a,b,c])=>c?g(a)+g(b)**g(c):b?g(a)%g(b):n

```

Try it online! (51 bytes thanks to @user202729)

This is using @xnor's basic approach, but without `eval`, and with a reduced basis.

The simple datatype D is a BigInt or an array of D. Given a program p (a D) and an input n (a BigInt), the expression `e(n)(p)` interprets the program with input n. Programs are interpreted as follows:

* \[a, b, c\] evaluates a, b, and c, returning a + b\**c
* \[a, b\] evaluates a and b, returning a modulo b
* \[0\] returns n

These three operations are enough to compute anything elementary recursive. No matter the value of n, the value of n+n\**n is positive, hence (n+n\**n)%(n+n\**n) gives 0, and 0 + 0\**0 gives 1. Hence, we have addition as a + b = a + b\**1 and exponentiation as a\**b = 0 + a\**b.

For example, this is a program that computes the constant 2:

```
[[[[[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], [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], [0]],
   [[0], [0], [0]]]]]

```

---

Corollary 2 of the following paper, which @xnor cited, is that this language gives all elementary recursive functions, using the usual tricks to encode a function \\$\mathbb{N}^n\to\mathbb{N}\\$ as a function \\$\mathbb{N}\to\mathbb{N}\\$.

Marchenkov, S. S. (2007). Superpositions of elementary arithmetic functions. Journal of Applied and Industrial Mathematics, 1(3), 351–360. doi:10.1134/s1990478907030106

They also point out in Corollary 3 that every recursively enumerable subset \\$S\\$ of \\$\mathbb{N}\\$ has an indicator function \\$f:\mathbb{N}\to \\{0,1\\}\\$ that is of the form \\$f(n)=\exists z\in\mathbb{N},n=p\_1(z)\wedge n=p\_2(z)\\$, where \\$p\_1(z)\\$ and \\$p\_2(z)\\$ are functions in the above language, such that \\$f(n)=1\\$ if and only if \\$n\in S\\$. The argument is that you take a Turing machine that describes \\$S\\$ (say, as a nondeterministic machine that halts with elements of \\$S\\$ on the tape) then use the language to make nearly identical functions \\$p\_1\\$ and \\$p\_2\\$ that take an execution trace \\$z\\$ and check whether it brings the machine into a halt state, and if so the result of each function is the tape contents, and otherwise they result in \\$p\_1(x)=0\\$ and \\$p\_2(x)=1\\$.
> 8 votes

# Answer
# JavaScript (Babel Node), ~~96~~ ~~86~~ ~~69~~ 62 bytes

```
x=>g=([a,b,c])=>c?((v=>{for(;v-->0;)g(b)})(g(a)),g(c)):x[a]+=b

```

Try it online!

This is implementing a variation on LOOP. A program is recursively defined to be an array of programs or a BigInt. A program `p` is run with input `x` (a list of BigInts) by passing `x` and `p` as curried arguments (`f(x)(p)` with `f` the above function). The program is interpreted as follows:

* \[i, n\] adds n to x\[i\], returning the sum.
* \[p, q, r\] with c = max(0, evaluate(p)), evaluates q c times then returns the result of evaluating r.

The interpreter expects that every x\[i\] used is initialized to some BigInt.

For example, the following is a program that returns the product of x\[2\] and x\[3\], assuming x\[0\] is set to 1 and x\[1\] starts with any non-negative number.

```
[[0, 0],      // loop x[0] times:
 [[0, 0],     //   loop x[0] times:
  [[1, 0],    //     loop x[1] times:
   [1, -1],   //       x[1] += -1
   [0, 0]],   //     x[0] += 0
  [[2, 0],    //   loop x[2] times:
   [[3, 0],   //     loop x[3] times:
    [1, 1],   //       x[1] += 1
    [0, 0]],  //     x[0] += 0
   [0, 0]]],  //   x[0] += 0
 [1, 0]]      // x[1] += 0

```

The last line returns the value of x\[1\].

Note that, while this version of LOOP allows variables to be negative, there is no way to clear such a value in a general way.
> 4 votes

# Answer
# VBS, 74 bytes

```
execute replace(replace(replace(lcase(inputbox(0)),"w",0),"e","ne"),"d",2)

```

Take program that looks like:

```
j=0:for i=0 to InputBox():j=j+i:ext:msgbox(j)

```

Disallow loops from `CreateObject`, `Do`, `(w)End`, `eval`, `execute`, `step`, `date`, `now`, `timer`

# JavaScript (Node.js), 35 bytes

(67 if no state allowed, 40 for no state strict, if you keep `=`; still 35 otherwise, still elementary but program is longer without `=`)

```
x=>n=>eval(x.replace(/[^!-=n]/g,0))
x=>n=>eval('for(i in this)delete this[i];'+x.replace(/[^!-=n]/g,0))
x=>n=>eval(x.replace(/[^!-=n]/g,'var '))

```

Try it online!

Even not reaching Bitwise operation is powerful

# JavaScript, 43 bytes

```
n=>g=([a,b,c])=>c?g(b)/g(c)-g(a)<<g(c):a||n

```

Why?

```
0   = 1 / 1 - 1 << 1
-x  = (x / 1 - 0 << 1) / -1 - 0 << -1
x+y = (-x / 1 - y << 1) / -1 - 0 << -1
x/y = -(0 / -y - (x / y - 0 << y) << -y) // If y>0
2^x = 2 / 1 - 1 << x
x>=0 = (1<<x)<<-x
[Convert To Positive]: 2^x + 2^x + 2^x + 2^(-1-x) + 1

```
> 1 votes

# Answer
# Bash, 33 bytes

```
dc -e"?sl`sed "s/[^l+%^]//g;q"`p"

```

Try it online!

Effectively the same scheme as @xnor's solution, except implemented in sed & dc, and using a subset of dc for user programs. All characters except \[+^%l\] are filtered out, and those that remain are evaluated by dc. Those characters are sufficient to perform the operations of addition, modulo, exponentiation(with 0^0 == 1) and to read from a variable 'l', which is written to with the user input before the inputted program is run. Numbers may be constructed using a combination of 0 = (n^n)%(n^n), 1 = 0^0, and the successor function, +0^0. Translated to dc, these would be:

```
0 = llll^llll^%
1 = llll^llll^%llll^llll^%^
S = llll^llll^%llll^llll^%^+

```

where S increments the value at the top of the stack. Operations may be arbitrarily nested. The set of characters is sufficient to encode the operations listed above. However, it is incapable of producing looping / recursion (which, in dc, would require executing a macro, which would require one of \[x=\<\>\], as well as either a or \[\] to define it). Similarly to @xnor's solution, the allowable programs are a superset of the class ELEMENTARY, adding the ability to do make arbitrary exponents, rather than just 2^ and ^2.
> 0 votes

---
Tags: code-golf, interpreter, language-design
---