title: Make a Brainfuck Interpreter

text:
# Question
Title: Make a Brainfuck Interpreter
There already is a Brainfuck interpreter question, but it is from 2011 and not up to date with current site standards and vague in places. I have proposed reposting this in chat, and it was well-received. Here goes.

## Objective

Given the Brainfuck code and the program's input as input, run the Brainfuck code. As there are various variants of Brainfuck, here is the one I will use for the challenge:

* There are least 128 cells.
* Cell values are positive integers, having a maximum value of at least 128.
* Going into negative cells in undefined.
* Going into negative numbers is undefined.
* Going above the maximum cell value is undefined.
* Going above the maximum cell is undefined.
* EOF is 0

You may assume that the code will conform to the above constraints and that brackets will be balanced. You may also assume that all input code will be nothing but `<>,.+-[]`.

# Testcases

```
"+[+[<<<+>>>>]+<-<-<<<+<++]<<.<++.<++..+++.<<++.<---.>>.>.+++.------.>-.>>--." -> "Hello, World!"

",[.,]", "abc" -> "abc"

```

# Scoring

As this is , shortest answer in bytes wins.

# Answer
> 2 votes
# simply, 425 bytes

This big boy defines an anonymous function which takes an input string and returns the output of the Brainfuck program.

This anonymous function has to be stored into a variable, and receives the code as the 1st argument (`$C`), and the input as the 2nd argument (`$T`).

This is a language being interpreted by JavaScript, which then interprets Brainfuck to generate JavaScript code.

```
fn($C$I){if run&empty($I)$I=''$T=&json_decode(<<<J
{".":"O+=String.fromCharCode(T[P]);",",":"T[P]=I[0]?I.shift().charCodeAt(0):0;","<":"P=P?P-1:255;",">":"P=(P+1)%256;","-":"T[P]=T[P]?T[P]-1:255;","+":"T[P]=T[P]?(T[P]+1)%256:1;","[":"while(T[P]){","]":"}"}
J)$N=''each$X in$C if$T[$X]$N=&str_concat($N$T[$X])$F=run$argv->map->constructor('X'run&str_concat("var I=Array.from(X+''),O='',T=[],P=0;"$N"return O"))send run$F($I);}

```

It is an absolute mess!

## Ungolfed - to plain English

```
Set $fn to the anonymous function($code, $input) {
    If call &empty($input) then {
        Set $input to "".
    }

    Set $tokens to the result of calling &json_decode(<<<JSON
{
    ".": "output += String.fromCharCode(tape[pointer]);",
    ",": "tape[pointer] = input.length ? input.shift().charCodeAt(0) : 0;",
    "<": "pointer = pointer ? pointer - 1 : 255;",
    ">": "pointer = (pointer + 1) % 256;",
    "-": "tape[pointer] = tape[pointer] ? tape[pointer] - 1 : 255;",
    "+": "tape[pointer] = tape[pointer] ? (tape[pointer] + 1) % 256 : 1;",
    "[": "while(tape[pointer]){",
    "]": "}"
}
JSON);

    Set $inner_code to "".
    Foreach $char in $code {
        If $tokens[$char] then {
            Set $inner_code to the result of calling &str_concat($inner_code, $tokens[$char], "\n").
        }
    }

    Set $js_code to the result of calling &str_concat(
        "input = Array.from(input + '');\nvar output = '';\nvar tape = [];\nvar pointer = 0;\n",
        $inner_code,
        "return output;"
    ).

    Set $fn to the result of calling $argv["map"]["constructor"]("input", $js_code).

    Return the result of calling $fn($input).
}

```

Now it is a lot more readable!

---

## How does it work?

This will simply read the input code, character by character, and replace the valid tokens into JavaScript code.

Using the `array["filter"]["constructor"](code)` (but using `"map"` to save bytes) trick in JSFuck, I can receive a JavaScript function which I can execute normally!

This is **FAAAAAAAAAAAAR** from the intended way of doing things, but ... it works!

---

## Example output

This is the *JavaScript* code generated for the test cases.

Hello world: `+[+[<<<+>>>>]+<-<-<<<+<++]<<.<++.<++..+++.<<++.<---.>>.>.+++.------.>-.>>--.`

```
var fn = function anonymous(X
) {
var I=Array.from(X+''),O='',T=[],P=0;T[P]=T[P]?(T[P]+1)%256:1;while(T[P]){T[P]=T[P]?(T[P]+1)%256:1;while(T[P]){P=P?P-1:255;P=P?P-1:255;P=P?P-1:255;T[P]=T[P]?(T[P]+1)%256:1;P=(P+1)%256;P=(P+1)%256;P=(P+1)%256;P=(P+1)%256;}T[P]=T[P]?(T[P]+1)%256:1;P=P?P-1:255;T[P]=T[P]?T[P]-1:255;P=P?P-1:255;T[P]=T[P]?T[P]-1:255;P=P?P-1:255;P=P?P-1:255;P=P?P-1:255;T[P]=T[P]?(T[P]+1)%256:1;P=P?P-1:255;T[P]=T[P]?(T[P]+1)%256:1;T[P]=T[P]?(T[P]+1)%256:1;}P=P?P-1:255;P=P?P-1:255;O+=String.fromCharCode(T[P]);P=P?P-1:255;T[P]=T[P]?(T[P]+1)%256:1;T[P]=T[P]?(T[P]+1)%256:1;O+=String.fromCharCode(T[P]);P=P?P-1:255;T[P]=T[P]?(T[P]+1)%256:1;T[P]=T[P]?(T[P]+1)%256:1;O+=String.fromCharCode(T[P]);O+=String.fromCharCode(T[P]);T[P]=T[P]?(T[P]+1)%256:1;T[P]=T[P]?(T[P]+1)%256:1;T[P]=T[P]?(T[P]+1)%256:1;O+=String.fromCharCode(T[P]);P=P?P-1:255;P=P?P-1:255;T[P]=T[P]?(T[P]+1)%256:1;T[P]=T[P]?(T[P]+1)%256:1;O+=String.fromCharCode(T[P]);P=P?P-1:255;T[P]=T[P]?T[P]-1:255;T[P]=T[P]?T[P]-1:255;T[P]=T[P]?T[P]-1:255;O+=String.fromCharCode(T[P]);P=(P+1)%256;P=(P+1)%256;O+=String.fromCharCode(T[P]);P=(P+1)%256;O+=String.fromCharCode(T[P]);T[P]=T[P]?(T[P]+1)%256:1;T[P]=T[P]?(T[P]+1)%256:1;T[P]=T[P]?(T[P]+1)%256:1;O+=String.fromCharCode(T[P]);T[P]=T[P]?T[P]-1:255;T[P]=T[P]?T[P]-1:255;T[P]=T[P]?T[P]-1:255;T[P]=T[P]?T[P]-1:255;T[P]=T[P]?T[P]-1:255;T[P]=T[P]?T[P]-1:255;O+=String.fromCharCode(T[P]);P=(P+1)%256;T[P]=T[P]?T[P]-1:255;O+=String.fromCharCode(T[P]);P=(P+1)%256;P=(P+1)%256;T[P]=T[P]?T[P]-1:255;T[P]=T[P]?T[P]-1:255;O+=String.fromCharCode(T[P]);return O
};

console.log(fn());
```

Cat program: `,[.,]`

```
var fn = function anonymous(X
) {
var I=Array.from(X+''),O='',T=[],P=0;T[P]=I[0]?I.shift().charCodeAt(0):0;while(T[P]){O+=String.fromCharCode(T[P]);T[P]=I[0]?I.shift().charCodeAt(0):0;}return O
};

console.log(fn(prompt("What does the cat say?", "")));
```

# Answer
> 2 votes
# Factor \+ `brainfuck`, 13 bytes

```
run-brainfuck

```

Try it online!

Try it online! (with input)

# Answer
> 1 votes
# Rust \+ `-C overflow-checks=off`, 370 bytes

```
|p:&[u8]|{let(mut o,mut c,mut t,mut k)=(0,0,[0;128],0);loop{match p[o]{62=>c+=1,60=>c-=1,43=>t[c]+=1,45=>t[c]-=1,46=>print!("{}",t[c]as char),44=>t[c]=stdin().bytes().next().unwrap_or(Ok(0)).unwrap(),91=>if t[c]<1{k=1;while k>0{o+=1;if p[o]==91{k+=1};if p[o]==93{k-=1}}},93=>if t[c]>0{k=1;while k>0{o-=1;if p[o]==91{k-=1}if p[o]==93{k+=1}}},_=>()}o+=1}};use std::io::*;

```

Attempt This Online! (Hello World)

Attempt This Online (Cat)

Will crash when it reaches the end of the program.

---
Tags: code-golf, interpreter, brainfuck
---


# Question
Title: The smallest number of steps for a chess piece to reach a position
I have previously posted a challenge, smallest number of steps for a knight in chess.

Now I would like to go a step further by adding the possibility to choose your piece.

If you place a piece on any square of a chessboard, what is the smallest number of steps to reach every possible position?

**Rules**

* It is an 8 by 8 board.
* The given input is a coordinate (x, y) and the chosen piece. Explain in the answer how to input the piece of choice.
* The piece starts at an arbitrary position, taken as input.
* The pawn can not start at the bottom row, and can not move 2 steps (like when in the start-position) and travels only to the top of the board not downwards.
* If a piece cannot reach a certain position, use a character of choice to indicate this.

**Example**

With input (1, 0) for a knight, we start by putting a 0 in that position:

```
. 0

```

From here on we continue to fill the entire 8x8 board.

For a knight the output will look as follows:

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

```

For a pawn with input (1, 7) the output will look like this:

```
. 6 . . . . . .
. 5 . . . . . .
. 4 . . . . . .
. 3 . . . . . .
. 2 . . . . . .
. 1 . . . . . .
. 0 . . . . . .
. . . . . . . .

```

In the examples, I start counting from zero but it does not matter if you start from zero or one.

**Challenge**

The pattern printed for a piece, as short as possible, in any reasonable format.

# Answer
> 7 votes
# APL (Dyalog APL), ~~133~~ ~~127~~ ~~108~~ ~~100~~ ~~91~~ ~~80~~ 70 bytes

```
{s⍴(⍉(⍺⌷9*(××(×,,,1⍺≠+)⍥|-×+),1 0≢,)/¨∘.-⍨,⍳s)(⊢⌊⌊.+)⍣≡9×⍵≢¨,⍳s←8 8}∘⊂

```

Attempt This Online!

**Update**: -19 bytes (127 → 108) by compressing the move matrices
**Update**: -8 bytes (108 → 100) by simplifying single move function
**Update**: -9 bytes (100 → 91) by changing the move matrix format
**Update**: -11 bytes (91 → 80)
**Update**: -10 bytes (80 → 70) by changing the move matrix format again

## I/O

This is a function that takes as arguments

* the starting square coordinates (Note that APL uses 1-based indexing by default and matrix indices are row number first. So the knight example in the OP has starting coordinates `1 2`); and
* an integer 1~6 for the piece choice, where they correspond to queen, rook, bishop, king, knight, and pawn respectively

The output is an 8×8 matrix, where the starting square is marked as `0` and unreachable squares are marked as `9`. This is unambiguous since no piece takes more than 7 moves to reach any reachable square on an 8×8 board.

## Explanation

### Algorithm Overview

This challenge boils down to a shortest paths problem on an unweighted directed graph, where squares are nodes and edges connect between squares that the chosen piece can move between. It's a directed graph solely because the pawn's move is not reversible.

But, to simplify the implementation, we treat the graph as a complete weighted directed graph, where the weight of an edge is 1 if it represents a move of the chosen piece and ∞ otherwise. As noted above, since 9 is not a possible shortest path length, we can just use 9 as "effectively infinite" and treat everything ≥9 as such.

This way, we can use an iterative algorithm that is similar to Dijkstra's Algorithm, but without tracking visited/unvisited nodes and without node prioritization. Each iteration just processes all edges simultaneously.

### Code Overview

The function first, based on the piece choice, generates a 64×64 "move matrix" which is just the adjacency matrix of the 64-node graph.

For example, this is the move matrix of the Queen:

```
┌→──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐
↓1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9│
│1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9│
│1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9│
│1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9│
│1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9│
│1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9│
│9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9│
│9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9│
│9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9│
│9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9│
│9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9│
│9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9│
│9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9│
│9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9│
│9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9│
│9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9│
│9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9│
│9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9│
│9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9│
│9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9│
│9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9│
│9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9│
│9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9│
│9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9│
│9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9│
│9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1 9 1 9 9 9 9 9 9│
│9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1 9 9 1 9 9 9 9 9│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1 9 9 9 1 9 9 9 9│
│9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1 9 9 9 9 1 9 9 9│
│9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1 9 9 9 9 9 1 9 9│
│9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1 9 9 9 9 9 9 1 9│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1 9 9 9 9 9 9 9 1│
│1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1│
│9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 1 1 1 1 1 1 1 1│
│9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 1 1 1 1 1 1 1 1│
│9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 1 1 1 1 1 1 1 1│
│9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 1 1 1 1 1 1 1 1│
│9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 1 1 1 1 1 1 1 1│
│9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 1 1 1 1 1 1 1 1│
│9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 9 9 9 9 9 9 9 1 1 1 1 1 1 1 1 1│
└~──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘

```

Then it creates the initial board state as an 64-element array of `9`s everywhere except `0` at the starting square.

Next, define a function that takes as arguments a "move matrix" and a current board state and "executes one move" by running one iteration of the shortest paths algorithm above.

With these, we can calculate the final output by looping the "single move" function until the output no longer changes (fixpoint).

Finally, we have to reshape that 64-element array as an 8×8 matix

```
{s⍴(⍉ ... ⍳s)( ... )⍣≡,9×⍵≢¨⍳s←8 8}∘⊂

{                                 }    ⍝ Defines a function that
                       9×⍵≢¨⍳s←8 8     ⍝   Generates the initial board state,
   (⍉ ... ⍳s)                          ⍝   Generates the the move matrix of the
                                       ⍝     chosen piece,
                    ⍣≡                 ⍝   Calculate the fixpoint of ...
             ( ... )                   ⍝     the "single move" function, and
 s⍴                                    ⍝   Reshape the final board state
                                       ⍝    to an 8×8 matrix
                                   ∘⊂  ⍝ Compose that function with a
                                       ⍝   preprocessing step of boxing its right
                                       ⍝   argument

```

### Move matrix generation

```
(⍉(⍺⌷9*(××(×,,,1⍺≠+)⍥|-×+),1 0≢,)/¨∘.-⍨,⍳s)

```

Note: The variable `s` is defined (as `8 8`) beforehand, during the initial board state generation explained later.

To generate the move matrix, we first generate a 64-element array of all the 64 coordinates (`,⍳s`). Then generate the 64×64 matrix of their relative positions by element-wise subtraction between each pair of them (`∘.-⍨`). For each of those, run a function with the (x,y) delta as right and left argument respectively (`(...)/¨`). Finally, transpose () that matrix to make the argument order easier to work with.

The inner function treats its two arguments as an (x,y) coordinate pair and returns `1` if the chosen piece can move to that square from (0,0) in a single move and `9` otherwise. It does this by generating the answer for all 6 pieces as a 6-element array, then indexing into that array using the piece choice (`⍺⌷`). The value for (0,0) does not matter as the "single move" function effectively ignores it.

For example, given (2,2) and piece choice `3` (bishop), the inner function generates `1 9 1 9 9 9` (because only the queen (1) and the bishop (3) can move to (2,2) from (0,0)), then chooses the 3rd element `1`.

To generate the 6 answers, we define a tacit function (`(××(×,,,1 5≠+)⍥|-×+),1 0≢,`) that returns a boolean (i.e. `0` or `1`) of whether the corresponding piece is *un*able to reach that square in one move, then exponentiate with `9` (`9*`) to get the desired result.

That tacit function, in turn, concatenates the results of 2 different tacit functions, one for the non-pawn pieces (`(××(×,,,1 5≠+)⍥|-×+)`), and one for the pawn (`1 0≢,`).

#### Pawn

```
1 0≢,

```

Simply returns whether (x,y) is *not* exactly () (1,0)

#### Other pieces

```
××(×,,,1⍺≠+)⍥|-×+

 ×                   ⍝ Calculate a = x × y
               -×+   ⍝ Calculate b = (x-y) × (x+y)
  (        )⍥|      ⍝ Apply a function with |a| and |b| as arguments
    , ,              ⍝ That function returns a 5-element array by concatenating:
   ×                 ⍝   1)   |a| × |b|              (queen)
     ,               ⍝   2,3) |a| and |b| themselves (rook and bishop)
       1 ≠+          ⍝   4)   whether |a| + |b| ≠ 1  (king)
        ⍺≠+          ⍝   5)   whether |a| + |b| ≠ 5  (knight)
×                     ⍝ Find the signum of those 5 results, because those
                      ⍝   results are 0 if the corresponding piece can move to
                      ⍝   (x,y) and positive otherwise

```

Notably, this takes advantage of the fact that the 5th entry only matters when the piece choice  is `5`.

### Initial board

```
9×⍵≢¨,⍳s←8 8

```

Generates a 64-element array where each entry is a 2-element array corresponding to the coordinates of a square on the board (`,⍳8 8`), then check each entry against the starting square coordinate (`⍵≢¨`). This results in an 8×8 boolean matrix which is `0` at the starting square and `1` everywhere else. Multiplying those by 9 () gives the initial board state.

This, as noted, also stores the array `8 8` in variable `s` along the way, which saves 2 bytes overall.

### Single move function

```
(⊢⌊⌊.+)

```

The single move function is defined as a tacit function that takes an existing board state and a move matrix and runs one iteration of the shortest paths algorithm. That is, for each edge with weight `w`, source node value `u` it generates a "candidate value" `u+w` for the destination node. The value of each node is then set to the smallest among its original value and all its "candidates".

Note that although the algorithm loops through all edges, it effectively ignores all not-yet-reached source nodes and all edges that does not correspond to the chosen piece's movement, since `u` is `9` ("effectively infinite") in the former case and `w` is `9` in the latter case.

---

To explain the code, let's follow as a reduced example the first iteration of the single move function when choosing rook and starting square (1,2) on a 3×3 board. The algorithm generalizes to any board size.

```
⍝ move matrix ⍺
┌→────────────────┐
↓1 1 1 1 9 9 1 9 9│
│1 1 1 9 1 9 9 1 9│
│1 1 1 9 9 1 9 9 1│
│1 9 9 1 1 1 1 9 9│
│9 1 9 1 1 1 9 1 9│
│9 9 1 1 1 1 9 9 1│
│1 9 9 1 9 9 1 1 1│
│9 1 9 9 1 9 1 1 1│
│9 9 1 9 9 1 1 1 1│
└~────────────────┘
⍝ Board state ⍵
┌→────────────────┐
│9 0 9 9 9 9 9 9 9│
└~────────────────┘

```

To calculate candidates, we need to add each entry in the board state to each entry in the corresponding column in the move matrix. Then, to find the best candidate, we need to find the min of each row.

```
min(1+9, 1+0, 1+9, 1+9, 9+9, 9+9, 1+9, 9+9, 9+9)
min(1+9, 1+0, 1+9, 9+9, 1+9, 9+9, 9+9, 1+9, 9+9)
min(1+9, 1+0, 1+9, 9+9, 9+9, 1+9, 9+9, 9+9, 1+9)
min(1+9, 9+0, 9+9, 1+9, 1+9, 1+9, 1+9, 9+9, 9+9)
min(9+9, 1+0, 9+9, 1+9, 1+9, 1+9, 9+9, 1+9, 9+9)
min(9+9, 9+0, 1+9, 1+9, 1+9, 1+9, 9+9, 9+9, 1+9)
min(1+9, 9+0, 9+9, 1+9, 9+9, 9+9, 1+9, 1+9, 1+9)
min(9+9, 1+0, 9+9, 9+9, 1+9, 9+9, 1+9, 1+9, 1+9)
min(9+9, 9+0, 1+9, 9+9, 9+9, 1+9, 1+9, 1+9, 1+9)

```

This operation may sound familiar -- it is actually matrix multiplication but with `min` and `+` instead of `+` and `×`.

Luckily, APL does have this "generalized matrix multiplication" operation built-in. So that whole "find best candidate for each square" is just `⌊.+`.

```
⍝ {⍺(⌊.+)⍵}
┌→────────────────┐
│1 1 1 9 1 9 9 1 9│
└~────────────────┘

```

Finally, we finish the iteration by dong element-wise min with the original board state.

```
⍝ {⍺(⊢⌊⌊.+)⍵}
┌→────────────────┐
│1 0 1 9 1 9 9 1 9│
└~────────────────┘

```

# Answer
> 11 votes
# JavaScript (ES7), 175 bytes

Expects `(P, X, Y)` where \\$X\\$ and \\$Y\\$ are 0-indexed and \\$P \in\\{3,4,5,6,7,10\\}\\$, as described in the *Piece encoding* paragraph below.

```
f=(P,X,Y,n=0,m=[...s='........'].map(_=>[...s]))=>m.map((r,y)=>r.map((V,x)=>V<=n||(h=(x-X)**2)==(v=(y-Y)**2)&P|h*v==(P&12)-4&&h+v<3|P&2&&y<Y|P-4&&f(P,x,y,n+1,m)),m[Y][X]=n)&&m

```

Try it online!

Or **171 bytes** if we can fill the 'background' with the pattern "Infinity", which I think is pretty nice since it would indeed take an infinity of moves to reach these squares. ;-)

Try it online!

### Piece encoding

Each bit in the piece code nibble encodes a specific property used by the move generator.

```
                    piece  |  P | as binary
                   --------+----+-----------
                    bishop |  3 |  0 0 1 1
                    pawn   |  4 |  0 1 0 0
                    king   |  5 |  0 1 0 1
                    rook   |  6 |  0 1 1 0
                    queen  |  7 |  0 1 1 1
                    knight | 10 |  1 0 1 0
                                   ^ ^ ^ ^
                                   | | | |
             moves like a knight --+ | | |
     moves along ranks and files ----+ | |
can move farther than one square ------+ |
           moves along diagonals --------+

```

For a pawn, the move generator applies an additional constraint which is not explicitly encoded in the bit mask: it may only move upwards.

### Move generator

A move between \\$(X,Y)\\$ and \\$(x,y)\\$ is valid if the following test succeeds:

```
(h = (x - X) ** 2)  // h = squared difference between x and X
==                  // is it equal to ...
(v = (y - Y) ** 2)  // v = squared difference between y and Y?
                    // if yes, this is a move along a diagonal
& P                 // which is valid if bit #0 is set in P
|                   //
h * v ==            // test whether h * v is equal to:
(P & 12) - 4        //   0 if bit #2 is set (move along ranks/files)
                    //   4 if bit #3 is set (knight move)
                    //  -4 otherwise (which always fails)
                    //
&&                  // additional conditions:
  h + v < 3 | P & 2 //   either h + v is less than 3 or bit #1 is set
&&                  //
  y < Y | P - 4     //   either y is less than Y or this is not a pawn

```

# Answer
> 4 votes
# Charcoal, 110 bytes

```
ＵＯ⁸ψＵＢ.Ｎθ⊞υ⟦⁰ＮＮ⟧Ｆυ«≔⊟ιζ≔⊟ιηＪζη¿¬℅ＫＫＦ⁸Ｆ⁸«ＰＩΣι≔⁺Ｘ⁻λζ²Ｘ⁻κη²ε≔⟦⁼↔⁻κη↔⁻λζ∨⁼κη⁼λζ⟧δ¿§⟦›³ε⌈δ⊟δ⊟δ⁼⁵ε∧⁼κ⊖η⁼λζ⟧θ⊞υ⟦⊕Σικλ

```

Try it online! Link is to verbose version of code. First input is an integer `0` King `1` Queen `2` Rook `3` Bishop `4` Knight `5` Pawn, second input is the column, third input is the row (`0`-indexed). Explanation:

```
ＵＯ⁸ψＵＢ.

```

Generate nice output by marking all unreachable squares with `.`. `ＵＯ⁸ψ` only would mark all unreachable squares with spaces. `ψ` only would trim trailing whitespace for pawn movements (removing it completely would trim leading whitespace too, which would be unhelpful).

```
Ｎθ

```

Input the piece number.

```
⊞υ⟦⁰ＮＮ⟧

```

Start a breadth-first search by placing a `0` at the input coordinates.

```
Ｆυ«

```

Loop over the squares as they are discovered.

```
≔⊟ιζ≔⊟ιηＪζη

```

Jump to the current square.

```
¿¬℅ＫＫ

```

Check that it hasn't already been visited from a different route.

```
Ｆ⁸Ｆ⁸«

```

Loop over the whole board.

```
ＰＩΣι

```

Set the source square to the current number of steps. (This is done inside the board loop to save a byte.)

```
≔⁺Ｘ⁻λζ²Ｘ⁻κη²ε

```

Get the Euclidean distance from the source square to the current square.

```
≔⟦⁼↔⁻κη↔⁻λζ∨⁼κη⁼λζ⟧δ

```

Determine whether the source and current squares are a bishop's or a rook's move away.

```
¿§⟦›³ε⌈δ⊟δ⊟δ⁼⁵ε∧⁼κ⊖η⁼λζ⟧θ

```

Create a list of six booleans depending on whether the source and current squares are a king's, queen's, rook's, bishop's, knight's or pawn's move away, and index using the input piece number to determine whether the piece can move to the current square.

```
⊞υ⟦⊕Σικλ

```

If it can then save this as being potentially one step further away.

---
Tags: code-golf, grid, graph-theory, chess
---


title: Goldbach partitions

text:
# Question
Title: Goldbach partitions
The Goldbach conjecture states that every even number greater than two can be expressed as the sum of two primes. For example,

```
4 = 2 + 2
6 = 3 + 3
8 = 5 + 3

```

However, once we get to 10 something interesting happens. Not only can 10 be written as

```
5 + 5

```

but it can also be written as

```
7 + 3

```

Since 10 can be expressed as the sum of two primes *two ways*, we say that the "Goldbach partition" of 10 is `2`. Or more generally,

> The Goldbach partition of a number is the total number of distinct ways of writing `n = p + q` where `p` and `q` are primes and `p >= q`

Your challenge is to write a program or function that finds the Goldbach partition of a number. Now, technically the term "Goldbach partition" is used only to refer to even numbers. However, since the odd integer **p + 2** can *also* be expressed as the sum of two primes if **p \> 2** is prime, we will extend this to all positive integers (A061358).

You may safely assume that your input will always be a positive integer, and you may take input and output in any of our default allowed methods, for example function arguments and return value, STDIN and STDOUT, reading and writing to a file, etc.

The Goldbach partitions of the positive integers up to 100 are:

```
0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 2, 1, 2, 1, 3, 0, 3, 1,
3, 0, 2, 0, 3, 1, 2, 1, 4, 0, 4, 0, 2, 1, 3, 0, 4, 1, 3, 1, 4, 0, 5, 1, 4,
0, 3, 0, 5, 1, 3, 0, 4, 0, 6, 1, 3, 1, 5, 0, 6, 0, 2, 1, 5, 0, 6, 1, 5, 1,
5, 0, 7, 0, 4, 1, 5, 0, 8, 1, 5, 0, 4, 0, 9, 1, 4, 0, 5, 0, 7, 0, 3, 1, 6

```

As usual, standard loopholes apply, and the shortest answer in bytes wins!

# Answer
> 7 votes
# Jelly, 8 bytes

```
_ÆRÆPSHĊ

```

Try it online! or verify all test cases.

### How it works

```
_ÆRÆPSHĊ  Main link. Argument: n (positive integer)

 ÆR       Prime range; yield [2, 3, 5, ..., n].
_         Subtract all primes in this range from n.
   ÆP     Compute the primality of the resulting differences.
          This returns 1 for each prime p such that n - p is also prime.
     S    Compute the sum of the resulting Booleans.
      H   Divide it by 2, since [p, n - p] and [n - p, p] have both been counted.
       Ċ  Ceil; round the resulting quotient up (needed if n = 2p).

```

# Answer
> 5 votes
# MATL, 8 bytes

```
tZq&+=Rz

```

**Try it online!**

### Explanation

Consider input `8` as an example

```
      % Take input implicitly
t     % Duplicate
      % STACK: 8, 8
Zq    % All primes up to that number
      % STACK: 8, [2 3 5 7]
&+    % Matrix with all pairwise additions
      % STACK: 8, [4  5  7  9
                   5  6  8 10
                   7  8 10 12
                   9 10 12 14]
=     % True for entries that equal the input
      % STACK: [0 0 0 0
                0 0 1 0
                0 1 0 0
                0 0 0 0]
R     % Extract upper triangular part (including diagonal).
      % This removes pairs that are equal up to order
      % STACK: [0 0 0 0
                0 0 1 0
                0 0 0 0
                0 0 0 0]
z     % Number of nonzero entries
      % STACK: 1
      % Display implicitly

```

---

It's interesting to observe the **graph of the sequence**, using a slightly modified version of the code:

```
:"@       % Input n implicitly. For each k from 1 to n, push k
tZq&+=Rz  % Same code as above. Pushes the result for each k
]v'.'&XG  % End. Concatenate all results into a vector. Plot as dots

```

For input `10000` the result is

You can try it at **MATL Online** (Refresh the page if the "Run" button doesn't change to "Kill" when pressed). It takes several about 25 seconds to produce the graph for input `3000`; inputs above a few thousands will time out.

# Answer
> 5 votes
## Python 2, 76 bytes

```
g=lambda n,k=2:n/k/2and all(x%i for x in[k,n-k]for i in range(2,x))+g(n,k+1)

```

Recursively crawls up from `k=2` to `n/2`, adding up values where both `k` and `n-k` are prime. It would be nice to count `n` down at the same time instead, but this has a problem that `k=0` and `k=1` are falsely called prime:

```
g=lambda n,k=0:n/k and all(x%i for x in[k,n]for i in range(2,x))+g(n-1,k+1)

```

The primality check is trial-division, shortened by checking both `k` and `n-k` together. I found this to be shorter than using a Wilson's Theorem generator (79 bytes):

```
f=lambda n,k=1,P=1,l=[]:n/k and P%k*(n-k in l+P%k*[k])+f(n,k+1,P*k*k,l+P%k*[k])

```

The idea for this one is to keep a list of all primes in the bottom half to be checked by the time we get to the top half, but for the midpoint `k=n/2`, we haven't had time to add `n-k` to out list when we get to `k`. An iterative version gets around this, but is 82 bytes:

```
n=input()
s=P=k=1;l=[]
while k<n:l+=P%k*[k];s+=P%k*(n-k in l);P*=k*k;k+=1
print~-s

```

# Answer
> 4 votes
# 05AB1E, 6 bytes

```
;ÅP-pO

```

Try it online!

Explanation:

```
                  # implicit input (example: 10)
;                 # divide input by 2 (5)
 ÅP               # primes up to that ([2, 3, 5])
   -              # subtract from the implict input ([8, 7, 5])
    p             # isPrime? ([0, 1, 1])
     O            # sum (2), implicit output

```

# Answer
> 4 votes
# Regex  (ECMAScriptRME / Perl / PCRE), ~~38~~ ~~33~~ 32 bytes

```
^(xx+)(?=\1(x*))(?!\2?(xx+)\3+$)

```

Try it on replit.com! \- ECMAScript (RegexMathEngine)
Try it online! \- Perl
Try it online! \- PCRE2

Takes its input in unary, as a string of `x` characters whose length represents the number. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method.)

```
^                     # tail = N = input number
(xx+)                 # \1 = conjectured first prime, automatically asserted
                      #      to be ≥ 2;
                      # tail = N-\1 == conjectured second prime
(?=
    \1                # tail -= \1; assert that second prime ≥ first prime;
                      # since the first prime is ≥ 2, this automatically
                      # asserts the second also to be so.
    (x*)              # \2 = tail == N-2*\1 == tool to make tail = \1
)
(?!                   # Assert there is no way to make the following match:
    \2?               # either leave tail unchanged, or tail = \1
    (xx+)\3+$         # Assert that tail is composite (which is only the same
                      # as being not prime for numbers ≥ 2)
)

```

# Regex  (ECMAScript 2018 or better), 36 bytes

```
(?<=(x+x))(?=\1(x*))(?!\2?(xx+)\3+$)

```

Returns its output as the number of matches.

Try it online! \- ECMAScript 2018
Try it online! \- Python (`import regex`)
Try it online! \- .NET

# Regex  (ECMAScript 2018 or better / Java), 37 bytes

```
(?<=^(xx+))(?=\1(x*))(?!\2?(xx+)\3+$)

```

Try it online! \- ECMAScript 2018
**Try it online! \- Java**
Try it online! \- Python (`import regex`)
Try it online! \- .NET

# Answer
> 3 votes
# JavaScript (ES6), ~~77~~ ~~73~~ 70 bytes

*Saved 3 bytes thanks to @Arnauld*

```
f=(n,x=n)=>--x<2||n%x&&f(n,x)
g=(a,b=a>>1)=>b>1?f(b)*f(a-b)+g(a,b-1):0

```

`f` is a primality-test function; the relevant function is `g`.

`f` works by recursively counting down from **n-1**; the control flow at each stage goes like this:

* `x<2||` If **x \< 2**, the number is prime; return **1**.
* `n%x&&` Otherwise if **n mod x = 0**, the number is not prime; return `n%x`.
* `f(n,x-1)` Otherwise, the number may or may not be prime; decrement **x** and try again.

`g` works in a similar fashion, though with not so much control flow. It works by multiplying **f(b)** by **f(a-b)** for each integer **b** in the range **\[2, floor(a/2)\]**, then summing the results. This gives us the number of pairs that sum to **a** where both numbers in the pair are prime, which is exactly what we want.

# Answer
> 3 votes
## GAP, 57 bytes

```
n->Number([2..QuoInt(n,2)],k->IsPrime(k)and IsPrime(n-k))

```

I don't think GAP has a shorter way than this obvious one. `Number` counts how many elements of a list satisfy a predicate.

Using it to compute the first 100 values:

```
gap> List([1..100],n->Number([2..QuoInt(n,2)],k->IsPrime(k)and IsPrime(n-k)));
[ 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 2, 1, 2, 1, 3, 0, 3, 1,
  3, 0, 2, 0, 3, 1, 2, 1, 4, 0, 4, 0, 2, 1, 3, 0, 4, 1, 3, 1, 4, 0, 5, 1, 4,
  0, 3, 0, 5, 1, 3, 0, 4, 0, 6, 1, 3, 1, 5, 0, 6, 0, 2, 1, 5, 0, 6, 1, 5, 1,
  5, 0, 7, 0, 4, 1, 5, 0, 8, 1, 5, 0, 4, 0, 9, 1, 4, 0, 5, 0, 7, 0, 3, 1, 6 ]

```

# Answer
> 3 votes
# Brachylog, 22 bytes

```
:{,A:B>=.:#pa+?,.=}fl

```

Try it online!

### Explanation

A straight up transcription of the problem.

```
:{                }f       Find all valid outputs of the predicate in brackets for the Input
                    l      Output is the number of valid outputs found

  ,A:B>=.                  Output = [A, B] with A >= B
         :#pa              Both A and B must be prime numbers
             +?,           The sum of A and B is the Input
                .=         Label A and B as integers that verify those constraints

```

# Answer
> 3 votes
# Mathematica, 52 bytes

```
Count[IntegerPartitions[#,{2}]//PrimeQ,{True,True}]&

```

The result is provided as an anonymous function. Try to plot a graph over it:

```
DiscretePlot[
 Count[IntegerPartitions[#, {2}] // PrimeQ, {True, True}] &[i], {i, 1,
   1000}]

```

By the way, the code has the same length with function version of demo code on OEIS.

# Answer
> 2 votes
# 05AB1E, ~~10~~ 8 bytes

Extremely inefficient.

```
D!f-pO;î

```

Try it online! or Try a less efficient way of generating primes

**Explanation**

`n = 10` used as example.

```
D          # duplicate
           # STACK: 10, 10
 !         # factorial
           # STACK: 10, 3628800
  f        # unique prime factors
           # STACK: 10, [2,3,5,7]
   -       # subtract
           # STACK: [8,7,5,3]
    p      # is prime
           # STACK: [0,1,1,1]
     O     # sum
           # STACK: 3
      ;    # divide by 2
           # STACK: 1.5
       î   # round up
           # STACK: 2
           # implicit output

```

# Answer
> 2 votes
# Vyxal, 6 bytes

```
½~æ-æ∑

```

Try it Online! Includes header and footer to produce first 100 results.

# Answer
> 1 votes
# Jelly, 12 bytes

```
HRð,_@ÆPð×/S

```

**TryItOnline**
**1-100**

### How?

```
HRð,_@ÆPð×/S - Main link: n    e.g. 22
H            - halve
 R           - range          [1,2,3,4,5,6,7,8,9,10,11] (note this will be 1 to n//2)
  ð          - dyadic chain separation
   ,         - pair with
    _@       - n -           [[1,2,3,4,5,6,7,8,9,10,11],[21,20,19,18,17,16,15,14,13,12,11]]
      ÆP     - is prime? (1 if prime 0 if not)
                            [[0,1,1,0,1,0,1,0,0,0,1],[0,0,1,0,1,0,0,0,1,0,1]]
        ð    - dyadic chain separation
         ×/  - reduce with multiplication
                             [0,0,1,0,1,0,0,0,0,0,1]
           S - sum           3

```

# Answer
> 1 votes
## Racket 219 bytes

```
(let*((pl(for/list((i n) #:when(prime? i))i))(ll(combinations(append pl pl)2))(ol'()))(for/list((i ll))(define tl(sort i >))
(when(and(= n(apply + i))(not(ormap(λ(x)(equal? x tl))ol)))(set! ol(cons tl ol))))(length ol))

```

Ungolfed:

```
(define(f n)
 (let* ((pl                                   ; create a list of primes till n
          (for/list ((i n) #:when (prime? i))
            i))
         (ll (combinations (append pl pl) 2)) ; get a list of combinations of 2 primes
         (ol '()))                            ; initialize output list
    (for/list ((i ll))                        ; test each combination
      (define tl (sort i >))
      (when (and (= n (apply + i))            ; sum is n
                 (not(ormap (lambda(x)(equal? x tl)) ol))) ; not already in list
        (set! ol (cons tl ol))))              ; if ok, add to list
    (println ol)                              ; print list
    (length ol)))                             ; print length of list

```

Testing:

```
(f 10)
(f 100)

```

Output:

```
'((5 5) (7 3))
2
'((97 3) (89 11) (83 17) (71 29) (59 41) (53 47))
6

```

# Answer
> 1 votes
# Actually, 11 bytes

```
;R`p`░@-♂bΣ

```

Try it online!

Explanation:

```
;R`p`░@-♂bΣ
 R`p`░       prime values in [1, n]
;     @-     subtract each value from n
        ♂b   convert each value to boolean
          Σ  sum

```

# Answer
> 1 votes
## Haskell, 73 bytes

```
f n|r<-[a|a<-[2..n],all((<2).gcd a)[2..a-1]]=sum[1|p<-r,q<-r,q<=p,p+q==n]

```

Usage example: `map f [1..25]` -\> `[0,0,0,1,1,1,1,1,1,2,0,1,1,2,1,2,0,2,1,2,1,3,0,3,1]`.

Direct implementation of the definition: first bind `r` to all primes up to the input number `n`, then take a `1` for all `p` and `q` from `r` where `q<=p` and `p+q==n` and sum them.

---
Tags: code-golf, math, sequence, number-theory, primes
---


title: Optimally pop all the bubbles

text:
# Question
Title: Optimally pop all the bubbles
In a given 2d grid of positive integers (representing different types of "bubbles"), there are one of two actions that you can do each "step". You can either:

1. Pop an island (a connected group of bubbles - two bubbles that are diagonally adjacent are not considered connected) of the same type of bubbles, given that the island consists of **at least 2 bubbles** AND at least one bubble in said island has **no bubbles above it**.

Or,

2. Drop a **single** bubble of any type into any column, given that the chosen column is **not filled** to the top of the grid.

After one of these two steps, all bubbles will **fall** towards the bottom of the grid, and the next step will start.

The grid can also include `0`'s, which represent empty space.

# Task

Your task is: Given a \\$m\times n\\$ 2d grid of positive integers representing a grid of bubbles and the optional \\$m\\$ and \\$n\\$ and input, determine the fewest amount of moves in which the entire grid can be cleared of bubbles. The input grid is guaranteed to be clearable.

# Worked example

```
22222
21212
22222
21212
22222

```

The first step will be to first pop the island of `2`'s. After all the bubbles have fallen, the grid will then look like this, where the `0`'s represent empty space:

```
00000
00000
00000
01010
01010

```

The second step will be to drop a `1` bubble in the middle column, so that the grid now looks like this:

```
00000
00000
00000
01010
01110

```

And the final step is to pop the island of `1`'s, clearing the entire grid.

# Test Cases

```
m, n
grid
-> output

5, 5
22222
21212
22222
21212
22222
-> 3

7, 7
1111111
2222222
1111111
2222222
1111111
2222222
1111111
-> 7

7, 6
000000
121212
212121
121212
212121
121212
212121
-> 22

2, 7
0000000
1000001
-> 4

8, 1
0
1
2
2
2
2
2
1
-> 5

8, 2
00
10
20
20
20
20
20
10
-> 4

```

If any of y'all need it, I also made a (pretty bad) tool that will take in a list of steps (more info in the TIO link) and output the board state after those steps have been taken: Try It Online!

---

This is , so the shortest solution in bytes for each language wins!

# Answer
# Python3, 901 bytes:

```
E=enumerate
def B(b):
 P,R,s=[(x,y)for x,j in E(b)for y,k in E(j)if k],[],[];p=P
 while p:
  x,y=p[0];q=[(x,y)];s+=p[0],
  while(o:=[X for x,y in q for X in[(x+1,y),(x,y+1),(x-1,y),(x,y-1)]if X in P and b[x][y]==b[X[0]][X[1]]and(X in s)^1]):q+=o;s+=o
  R+={*q},;p=[i for i in p if(i in s)^1]
 return R
F=lambda b:[*map(list,zip(*[[0]*i.count(0)+[j for j in i if j]for i in zip(*b)]))]
def f(b):
 q,S=[(b,0)],{}
 while q:
  b,c=q.pop(0)
  if sum(sum(b,[]))<1:return c
  I=B(b)
  for i in I:
   if len(i)>1and sum(all(b[x-t][y]==b[x][y]or 1>b[x-t][y]for t in range(x+1))for x,y in i):
    W=eval(str(b))
    for x,y in i:W[x][y]=0
    if(str(w:=F(W))in S)^1or-~c<S[str(w)]:q+=(w,c+1),;S[str(w)]=c+1
  for y,C in E(zip(*b)):
   if C[0]<1:
    for v in{j for k in b for j in k if j}:
     W=eval(str(b));W[0][y]=v
     if(len(B(e:=F(W)))<=len(I))&((str(e)in S)^1or-~c<S[str(e)]):q+=(e,c+1),;S[str(e)]=c+1

```

Try it online!
> 5 votes

---
Tags: code-golf, array, grid
---


title: Detect round trips on a dodecahedron

text:
# Question
Title: Detect round trips on a dodecahedron
An ant starts on an edge of a dodecahedron, facing parallel to it. At each step, it walks forward to the next vertex and turns either left or right to continue onto one of the other two edges that meet there. A sequence of left/right choices that returns the ant to its initial state (edge and direction) is called a *round trip*.

Write a function (or program) that takes a string of `L`s and `R`s and returns (or outputs) one of two values, indicating whether the input represents a round trip.

Examples:

```
LLLLL -> yes
LRLRLRLRLR -> yes
RRLRRLRRL -> yes
(empty sequence) -> yes
R -> no
LLLLLL -> no (starts with a round trip but leaves initial state)
RLLLLR -> no (returns to initial edge but opposite direction)

```

# Answer
# Python 2, 79 bytes

```
lambda s:all(n==reduce(lambda n,c:-~[n,n%3+n%4][c>'L']%5,s,n)for n in range(5))

```

Try it online!

This uses the group-theoretic approach from Ilmari Karonen's GolfScript answer to my 2014 challenge, in particular to the bonus question.

Instead of the ant crawling around the dodecahedron, we imagine it stays in place while the dodecahedron turns under its feet. We must determine whether the sequence of rotations returns the dodecahedron to the initial position.

There are 60 rotation of the dodecahedron -- 12 faces times 5 positions per face. These rotations can be expressed as permutations of 5 elements. Specifically, they permute 5 colored tetrahedra shown below that partition the 20 vertices of the dodecahedron.

We could take each rotation and write down which color tetrahedron moves onto which color's position to obtain a permutation of the five colors. Specifically, these are the even permutations, which are half of the 5!=120 permutations of five elements, or 60, forming the alternating group \\$A\_5\\$ on five elements. The other 60 odd permutations would involve reflecting the dodecahedron and well as rotating it, so they do not figure in this problem.

We want to choose two even permutations that represent the rotations from the ant turning left and right. As noted by Ilmari Karonen, the two permutations must have order 5, corresponding to five left or five right turns brining the ant back to the same place. Moreover, their product must have order 5 as well, and neither can be a power of the other.

There are many choices for the two permutations. If we think of them as permuting the values 0 to 4, the pair our code uses is `12340` and `13042`. The first one simply adds one modulo 5. From here, there's 5 choices for the other one: `13042, 14302, 24310, 32041, 32410`. The code uses `13042` because it happens to have a short expression in Python `1+(n%3+n%4)%5`, or just `n%3+n%4` if we "share" the `+1` and `%5` for the other case\`. I found this via some brute-forcing.

Now let's take another look at the code:

```
lambda s:all(n==reduce(lambda n,c:-~[n,n%3+n%4][c>'L']%5,s,n)for n in range(5))

```

Try it online!

To check that the sequence of permutations combines to the identity, we test each starting value `n` from `range(5)`, apply the sequence of permutations to it using `reduce`, and check that `all` of them end up at the initial value. The `-~` is a shortcut to add one.

---

**74 bytes**

```
lambda s:0in[n==reduce(lambda n,c:-~[n,48/~n][c>'L']%5,s,n)for n in 0,1,2]

```

Try it online!

Outputs True/False swapped.

I found `48/~n` as a shorter alternative for the second permutation when it is incremented and taken mod 5.

Also, instead of checking that the permutation maps each of `0,1,2,3,4` to themselves, this only checks `0,1,2`. This suffices because the map is bijective, so once `0,1,2` are fixed, `3` and `4` have to either map to themselves or swap, and because the permutation is even they can't swap.

**65 bytes**

```
S=s=`321.`
for c in input():s=(s+s[ord(c)%9:3]+s)[3:8]
print s==S

```

Try it online!

This uses a different mapping pair: `34012, 34120`. These are nice to implement as operations on lists, moving the last two elements to the front in both cases, and for the latter cycling the last 3. To start, we just need any sequence of 5 distinct elements, so we use ``321.`` which equals `'321.0'`.

**61 bytes**

```
n=27
for c in input():n=n%16*64|n/16*4**(c>'L')%63
print n<28

```

Try it online!

This uses bitwise shenanigans, much like my 2018 answer with cubes. It implements the permutations `34012, 34120`.

The number `n` encode 5 fields of bits 2 each, say `abcde`. Each step permutes these bits to either `deabc` or `debca` using bitwise operations. `n%16*64` moves `de` into the first two positions, while `n/16*4**(c>'L')%63` makes `abc` in the last 3 positions and then conditionally transforms it to `bca` if an `R` is read.

Initial, these five fields are `00123`, which translates into `n=27` in base 4. It's fine that the first 2 of them are the same, as no sequence of permutations can solely swap them because all the permutations are even. Because `n=27` is the smallest possible permutation of the fields, we can use `n<28` to check that the final state is the same as the initial one.

**60 bytes**

```
L=1;R=1j
for c in input():exec c+"=(L+R)%5%5j"
print L*1j==R

```

Try it online!

A new method based on alephalpha's finding that \\$A\_5 \cong PSL(2,5)\\$. A cute trick here is using `L` and `R` for variables so we can plug the character we read and `exec`.

We interpret the `L`'s and `R`'s as instructions to set either `L=L+R` or `R=L+R`. If this always results in either getting back the original values mod 5 or getting back their negations mod 5, then the instructions give a closed loop.

It suffices to test that this works for both the initial "basis vectors" `L=1, R=0` and `L=0, R=1`. Instead of testing twice, we run both tests in parallel using complex numbers, with one case in the real part and the other in the imaginary part, so `L=1, R=1j`. Python 2 has a wacky complex modulus that lets us `%5` to reduce the real part and `%5j` to reduce the imaginary part.

In the end, we can if we're in one of the success cases of the original `L=1,R=1j` or its negation mod 5 of `L=4,R=4j`. It turns out it suffices to check `L*1j==R` as shown by this code testing for false positives.

**59 bytes**

```
L=1;R=1j
exec"=(L+R)%5%5j;".join(input()+' ')
print L*1j==R

```

Try it online!

Saves one byte from above using `.join` to create the string to execute.
> 12 votes

# Answer
# PARI/GP, 51 bytes

```
s->t=x;[t=Mod(t+p=c>"O",5)/(t*!p+1)|c<-Vec(s)];t==x
```

Attempt This Online!

Using the isomorphism \\$A\_5 \cong PSL(2,5)\\$. See this question on Mathematics SE: https://math.stackexchange.com/q/93762/99103

In this isomorphism, the permutations represented by `L` and `R` are mapped to the rational functions \\$\frac{x}{x+1}\\$ and \\$x+1\\$ respectively.

---

## PARI/GP, 58 bytes

```
s->m=matid(2);[m=m*[1,p=c>"O";!p,1]%5|c<-Vec(s)];m==m[1,1]
```

Attempt This Online!

This uses the same isomorphism as above, but uses matrices (\\$\bigl(\begin{smallmatrix}1&0\\1&1\end{smallmatrix}\big)\\$ and \\$\bigl(\begin{smallmatrix}1&1\\0&1\end{smallmatrix}\big)\\$ for `L` and `R`) instead of rational functions to represent elements of \\$PSL(2,5)\\$.

---

## PARI/GP, 63 bytes

```
s->prod(n=0,4,m=n;[m=[m+1,33%m+=9][c%5]%5|c<-Vecsmall(s)];m==n)
```

Attempt This Online!

A port of @xnor's answer, but uses `33%(n+9)%5` instead of `(1+n%3+n%4)%5`.
> 7 votes

# Answer
# Jelly, ~~15~~ 13 bytes (thanks @Jonathan Allan!)

```
OH+53œ?@ƒ5FṢƑ

```

Try it online!

```
OH+53œ?@ƒ5FṢƑ
O                ord() the input list (vectorizes)
 H               Divide by 2 (vectorizes)
  +              Add...
   53            ...53 (all these steps vectorize)
        ƒ        Reduce the input list with:
       @             The preceding dyadic link, with its arguments swapped:
     œ?                  The nth permutation of the right argument
                 ...using the following as the starting value for the reduce:
         5           5 (which gets implicitly converted to [1,2,3,4,5] by œ?)
          F      Flatten (wraps 5 into [5] in case the input list is empty)
            Ƒ    Check if the output of the previous link is equal to its left argument:
           Ṣ         Sort the output list
(The last two bytes effectively check if the list is already in sorted order.)

```

Uses essentially the same logic as @xnor's answer. The two permutations I used were `45231` and `45123`, since their indices (94 and 91, respectively) can be easily computed from the `ord` values of 'R' and 'L' (82 and 76, respectively): divide by 2 and add 53. I wrote a Python script to check all valid pairs of permutations to find the optimal ones (in terms of how many bytes are needed to calculate their indices from 82 and 76), and no other permutations were better than these.
> 5 votes

# Answer
# Charcoal, ~~33~~ 32 bytes

```
≔Ｅ⁵ιθＦＳＵＭθ⎇›ιL﹪⁺³κ⁵÷↔⁻⁹×⁴κ²⬤θ⁼ικ

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for a round trip, nothing if not. Explanation: I too read the linked post with the dodecahedral bonus but I decided to pick `[4, 2, 0, 1, 3]` and `[3, 4, 0, 1, 2]` as my permutations for which the formulas are ~~`max(n*2,9-n*2)%5`~~ `abs(9-4*n)//2` and `(n+3)%5`. (Porting @xnor's formulas would probably be shorter but that would have been boring.)

```
≔Ｅ⁵ιθ

```

Start with a list `[0, 1, 2, 3, 4]`.

```
ＦＳ

```

Loop over the input string.

```
ＵＭθ

```

Update the list elements in-place.

```
﹪⎇›ιL⁺³κ⌈⟦⊗κ⁻⁹⊗κ⟧⁵

```

Apply one of the two permutations as appropriate.

```
⬤θ⁼ικ

```

Check that each list element is equal to its index.
> 4 votes

# Answer
# Python+, 49 bytes

```
n=27
£c:§()
 n=n%16*64|n/16*4**(c>'L')%63
$(n<28)

```

Basically just xnor's Python answer, converted to Python+
> 3 votes

---
Tags: code-golf, math, geometry, graph-theory
---


title: Carry-less sum given a base b

text:
# Question
Title: Carry-less sum given a base b
Given a list of positive integers \\$\mathcal I=I\_1,I\_2,I\_3,...,I\_n\\$ and a base \\$b\>1\\$ return their "carry-less sum", i.e. represent \\$\mathcal I\\$ in base \\$b\\$ and sum digit-by-digit discarding carry.

Worked example:

```
I = 13, 2, 9; b = 3

```

In base 3:

```
   111
 +   2
 + 100
 -----
 = 210

```

and back to base 10:

```
desired output: 21

```

More test cases:

```
I=[1000, 576, 23, 1, 141], b=12 => 1573

I=[1000, 576, 23, 1, 141], b=2 => 307

I=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], b=4 => 11

I=[1, 2, 3, 5, 8, 13, 21, 34, 55], b=5 => 77

I=[900, 100], b=10 => 0

```

This is code-golf shortest function or program per language wins.

Standard rules and loopholes apply.

# Answer
> 7 votes
# K (ngn/k), 11 bytes

```
{x/x!+/'x\}

```

Try it online!

First time writing a curried function in K...

Works exactly like coltim's answer, except for how the function is called. This one is a monadic function that takes the base and returns another monadic function that takes an array and returns the answer. You can call it like

```
(f 12) 1000 576 23 1 141
f[12][1000 576 23 1 141]

```

# Answer
> 5 votes
# Python 3, 56 bytes

```
f=lambda I,b:sum(I)and sum(I)%b+b*f([x//b for x in I],b)

```

Try it online!

# Answer
> 3 votes
# Pip, 18 bytes

```
R($+R*:SgTDa)%aFDa

```

Takes the base, followed by the integers, as command-line arguments. Try It Online!

### Explanation

> \[This challenge is\] a good example of why base-conversion builtins should be little-endian
> \- ais53

```
R($+R*:SgTDa)%aFDa
                    a is first command-line arg; g is list of args
       Sg           All but the first command-line argument
         TDa        Convert each to a list of integers representing base-a digits
    R*:             Reverse each list of digits
  $+                Add the lists of digits together itemwise
 (          )%a     Take each digit sum mod a
R                   Reverse again
               FDa  Convert from base-a digits to decimal

```

# Answer
> 3 votes
# , 42 bytes

```
`/`=\(I,b)`if`(s<-sum(I),I%/%b/b*b+s%%b,0)
```

Attempt This Online!

The same approach as other recursive answers.

Renaming the function to `/` makes `I%/%b/b*b` evaluate in the correct order (first `%/%`, then `/`, then `*`) and saves a byte compared to `f(I%/%b,b)*b`.

# Answer
> 2 votes
# Jelly, 6 bytes

```
bUS%Uḅ

```

Try it online!

```
b         Convert each to base b
 U        reversed,
  S       sum corresponding digits,
   %      mod b,
    U     reverse back to big-endian,
     ḅ    convert from base b.

```

> a good example of why base-conversion builtins should be little-endian

-- ais523

Incidentally, having to reverse twice only costs one byte due to dyadic chaining rules requiring something between `%` and  anyways, but in cases like this I'd have to agree that

> I like the monadic link rules, but not the dyadic link rules

-- ais523

# Answer
> 2 votes
# Charcoal, 19 bytes

```
ＷΣθ«⊞υι≧÷ηθ»Ｉ↨⮌﹪υηη

```

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

```
ＷΣθ«

```

Repeat until the (sum of the) input list is zero.

```
⊞υι

```

Push the sum to the predefined empty list.

```
≧÷ηθ

```

Vectorised integer divide the input list by the input base in place.

```
»Ｉ↨⮌﹪υηη

```

Vectorised modulo the list of sums by the input base, then interpret that as a number in the input base, and output the result. (The `Reverse` is there because base conversion isn't little-endian as it "should" be...)

# Answer
> 2 votes
# JavaScript (ES6),  ~~53~~  52 bytes

Expects `(base)(list)`.

```
b=>g=a=>(a=a.map(n=>(s+=n,n/b|0),s=0),s&&s%b+b*g(a))

```

Try it online!

Or **51 bytes** with BigInts:

```
b=>g=a=>(a=a.map(n=>(s+=n,n/b),s=0n),s&&s%b+b*g(a))

```

Try it online!

### Commented version

```
b =>            // outer function taking the base b
g = a =>        // inner recursive function taking the list a[]
( a =           // update a[] (and compute the sum at the same time):
  a.map(n =>    //   for each entry n in a[]:
    ( s += n,   //     add n to the sum s
      n / b | 0 //     compute floor(n / b)
    ),          //
    s = 0       //     start with s = 0
  ),            //   end of map()
  s &&          // if the sum is not 0:
    s % b +     //   compute the sum modulo the base
    b * g(a)    //   add the product of the base and the result
)               //   of a recursive call with the updated list

```

# Answer
> 2 votes
# Vyxal, 8 bytes

```
τR∑Ṙ$%¹β

```

Try it Online!

# Answer
> 2 votes
# , 14 bytes

```
[#.[|[:+/#.inv

```

Try it online!

* `#.inv` base digits
* `[:+/` sum elementwise
* `[|` mod by base
* `[#.` back to base 10

# Answer
> 2 votes
# K (ngn/k), 12 bytes

```
{y/y!+/'y\x}

```

Try it online!

* `y\x` convert list input `x` to base-`y`
* `+/'` sum each "row" of the above
* `y!` mod the sums by `y`
* `y/` convert back from base-`y` (to base-10)

# Answer
> 2 votes
# C (gcc), <sup>~~88~~</sup> 73 bytes

```
i;s;f(l,b,n)int*l;{for(s=i=0;i<n;l[i++]/=b)s+=l[i];s=s?s%b+b*f(l,b,n):0;}

```

Try it online!

Inputs a pointer to an array on integers, a base, and the length of the array (because pointer in C carry no length info).
Returns the carry-less sum.

# Answer
> 2 votes
# PARI/GP, 34 bytes

```
b->g(a)=if(a,g(a\b)*b+vecsum(a)%b)
```

Attempt This Online!

A curried function that takes input as `(base)(list)`.

# Answer
> 2 votes
# Desmos, 77 bytes

```
k=[0...floor(max(log_bl))]
f(l,b)=total([mod(floor(l/b^i).total,b)fori=k]b^k)

```

Function \\$f(l,b)\\$ takes in a list of positive integers \\$l\\$ and a base \\$b\\$.

Not too sure what little endian big endian is all about so I just did it my own way.

Try It Online!

Try It Online! - Prettified

# Answer
> 2 votes
# Haskell, ~~54~~ 51 bytes

```
b!l=sum[b^w*mod(sum$map(`div`b^w)l)b|w<-[0..sum l]]

```

Try it online!

# Answer
> 2 votes
# Wolfram Language (Mathematica), 52 bytes

```
Total@PadLeft@IntegerDigits@##~Mod~#2~FromDigits~#2&

```

Try it online!

Input `[I, b]`.

# Answer
> 2 votes
# Nibbles, ~~10~~ 9 bytes (18 nibbles)

*Edit: -2 nibbles thanks to bug-fix in nibbles compiler (thanks Darren Smith!) allowing  ``@` (convert from base) to work correctly on 2d lists*

```
`@@.\`'.$\`@_$%+$_

```

```
       .                # Map over
        $               # the elements of arg1
         \              # reversing
          `@ $          # the digits in base
            _           # arg2.
     `'                 # Now transpose this,
    \                   # reverse it,
   .                    # and map over each list
               +$       # sum
              %  _      # modulo arg2.
`@                      # Finally, convert from base
  @                     # arg2

```

# Answer
> 2 votes
# 05AB1E, 10 bytes

```
вí0ζOR¹%¹β

```

Inputs in the order \\$b,\mathcal I\\$.

Try it online or verify all test cases.

**Explanation:**

```
в          # Convert the values in the second (implicit) input-list to the base of the
           # first (implicit) input-integer as inner lists
 í         # Reverse each inner list
   ζ       # Zip/transpose; swapping rows/columns,
  0        # with 0 as trailing filler digit for unequal length lists
    O      # Sum each inner column-list
     R     # Reverse the list back
      ¹%   # Modulo each value by the first input-base
        ¹β # Convert this list from the first input-base to a base-10 integer
           # (which is output implicitly as result)

```

# Answer
> 2 votes
# Perl 5, 52 bytes

```
sub f{$b=pop;&sum&&&sum%$b+$b*f((map$_/$b|0,@_),$b)}

```

Try it online!

```
sub f {
  $b = pop;                  #extract the base $b from the end of the param list
  &sum                       #&sum returns the sum of the input list @_
                             #since &sub without parens uses @_ as params
                             #if sum > 0
  &&
  &sum % $b +                #then return last base $b digit of the sum plus
    $b *                     #$b times
    f( (map$_/$b|0,@_), $b ) #the recursive result for the same list
                             #but with last digit removed from each list elem
                             #else return 0
}

```

# Answer
> 2 votes
# PowerShell Core, 129 bytes

```
param($n,$b)$r=@{}
$n|%{do{$r[$i++]+=$_}while($_=[Math]::Floor($_/$b))$i=0}
$l=$r.Count
-join($r|% V*|%{"+$_%$b"+"*$b"*--$l})|iex

```

Try it online!

# Answer
> 2 votes
# Prolog (SWI), 76 bytes

```
I+B+O:-sumlist(I,S),S>0,maplist([A,A//B]>>!,I,Q),Q+B+W,O is S mod B+B*W;O=0.

```

Try it online!

-3 thanks to Jo King

More interesting, without `sumlist` or `maplist`:

# Prolog (SWI), 86 bytes

```
E+H-[H|T]-B-[H//B|Y]:-E-T-B-Y.
0-A-_-A.
I+B+O:-S-I-B-Q,S>0,Q+B+W,O is S mod B+B*W;O=0.

```

Try it online!

# Answer
> 1 votes
# Julia, 35 bytes

```
i^b=any(i.>0)&&sum(i)%b+b*(i.÷b)^b

```

Try it online!

# Answer
> 1 votes
# Retina 0.8.2, 161 bytes

```
\d+
$*
{`^([1,]+)(;1+)
$1$2;$1
T`,`_`;.*
^([1,]+;(1+);)\2*
$1
\G((?=.*?;((1)+))\2|1|(,))
$3$4
}`^,+;
;
{`\G(;1+;)|1(?<=(1+);1+)(?=1*;)
$1$2
}`^(;1+;1*);
$1
r`1\G

```

Try it online! Link includes test cases. Explanation:

```
\d+
$*

```

Convert to unary.

```
{`
}`

```

Repeat until all of the input numbers have been reduced to zero.

```
^([1,]+)(;1+)
$1$2;$1

```

Duplicate the input list.

```
T`,`_`;.*

```

Sum the duplicate copy.

```
^([1,]+;(1+);)\2*
$1

```

Reduce it modulo the base.

```
\G((?=.*?;((1)+))\2|1|(,))
$3$4

```

Integer divide the list by the base.

```
^,+;
;

```

Remove the list if it's zero.

```
{`\G(;1+;)|1(?<=(1+);1+)(?=1*;)
$1$2
}`^(;1+;1*);
$1

```

Convert the sums from the input base.

```
r`1\G

```

Convert to decimal.

# Answer
> 1 votes
# Knight, 109 bytes

```
;=j!=bP;W=xP E++"=x"=j+1j"Ex";=r=m=s 1;Ws;=s=i 0;W<i j;=s+sE+"x"=i+1iE++++"=x"i"/x"i" b";=r+r*m%s b=m*m bO-rT

```

Try it online!

-1 byte thanks to Aiden Chow

# Answer
> 1 votes
# Factor \+ `math.unicode`, 72 bytes

```
:: f ( I b -- n ) I Σ dup 0 > [ b mod I [ b /i ] map b f b * + ] when ;

```

Try it online!

* `:: f ( I b -- n ) ... ;` Define a word (function) named \\$f\\$ that takes two arguments from the data stack and returns one. The double `::` as opposed to `:` enables lexical variables inside the definition.
* `I Σ dup 0 >` Is the sum of \\$I\\$ greater than zero?
* `[ ... ] when` If so, then call `[ ... ]`.
* `b mod` Take the sum of \\$I\\$ (which is still on the data stack thanks to `dup`) modulo \\$b\\$.
* `I [ b /i ] map` Divide each number in \\$I\\$ by \\$b\\$ (integer results only) and place the result on the data stack.
* `b f` Call \\$f\\$ on the above list with the same original base, \\$b\\$.
* `b *` Multiply the result of the above call by \\$b\\$.
* `+` Add the sum of \\$I\\$ modulo \\$b\\$ which is still on the data stack.

# Answer
> 1 votes
# APL (Dyalog Classic), 20 bytes

```
0{⍺⊥⍺|+/⍵⊤⍨⍺⍴⍨⌈⍺⍟⌈/⍵}

```

Try it online!

**Usage:**

```
      ncarry←{⍺⊥⍺|+/⍵⊤⍨⍺⍴⍨⌈⍺⍟⌈/⍵}
      3 ncarry 13 2 9
21
      12 ncarry 1000 576 23 1 141
1573
      2 ncarry 1000 576 23 1 141
307
      4 ncarry 1 2 3 4 5 6 7 8 9 10
11
      5 ncarry 1 2 3 5 8 13 21 34 55
77

```

---
Tags: code-golf, number, arithmetic, integer, base-conversion
---


title: Add parentheses to Polish notation

text:
# Question
Title: Add parentheses to Polish notation
In most programming languages, arithmetic is written with *infix notation* -- i.e. the operator is put in between the operands -- e.g. `1+2`. In contrast, with **Polish notation** (a.k.a *prefix notation*), the operator comes *before* the operands -- e.g. `+1 2`. As long as the number of operands for each operator is fixed, this means that parentheses are never necessary, unlike with infix notation.

## The Challenge

Given a string consisting of nonnegative integers (digits 0 through 9), spaces, `+`, `-`, `*`, and `/` representing a single expression in Polish notation, add parentheses around each sub-expression, maintaining the whitespace. The parentheses should start right before the operator and end right after the last operands. You can assume each function has arity 2 (i.e. it takes in exactly 2 operands). You can also assume there will be no extra preceding zeros (e.g. `000` or `09`).

## Test Cases

| Input | Output |
| --- | --- |
| `+1 2` | `(+1 2)` |
| `++ 1 2 3` | `(+(+ 1 2) 3)` |
| `+1 +2 3` | `(+1 (+2 3))` |
| `* *1 2 /3 0` | `(* (*1 2) (/3 0))` |
| `//30 300/18 205` | `(/(/30 300)(/18 205))` |
| `/ -20/ 30 30 999` | `(/ (-20(/ 30 30)) 999)` |
| `/////1 2 3 4 5 6` | `(/(/(/(/(/1 2) 3) 4) 5) 6)` |
| `/1/2/3/4/5/6/7/8 9` | `(/1(/2(/3(/4(/5(/6(/7(/8 9))))))))` |

Standard loopholes are forbidden. As this is , the shortest program wins.

# Answer
> 15 votes
# Regex (Perl / PCRE / Python`regex`), ~~48~~ ~~47~~ ~~45~~ ~~44~~ 43 bytes

```
s~([*-/]( *(\d++|\((?1)\))){2})(?!\))~($1)~

```

Try it online! \- Perl
Try it online! \- PCRE1
Try it online! \- PCRE2
Try it online! \- Python `import regex`

This is a single regex substitution to be repeatedly applied until it has nothing to match (or until there is no change, where necessary or convenient).

In the following explanation,  represents a space:

```
s~         # Begin substitution - match the following:
(          # Define subroutine (?1); $1 = the following (the entire match):
    [*-/]  # Character class of the four arithmetic operators. This also
           # includes "," and ".", but those are guaranteed not to be in the
           # input.
    (
        ␣*        # Any number of spaces, minimum zero.
        (         # Define subroutine (?2) as an argument to an operator:
            \d++  # Any number of digit characters, minimum one; force all of
                  # them to be consumed (prevent backtracking).
        |  # or...
            \(    # An opening parenthesis
            (?1)  # Recursively call (?1)
            \)    # A closing parenthesis
        )
    ){2}   # Do the above twice (for two arguments).
)
(?!\))     # Assert there is no closing parenthesis following this, as that
           # would indicate that this expression has already been parenthesized.
~          # Replace with the following:
($1)       # Preserve $1 (the entire match), and surround it with parentheses.
~          # Flags:
           # No global flag. For better efficiency, adding the "g" flag
           # would allow the substitution loop to end sooner, but it's
           # not needed.

```

Saved 1 byte by using `{2}` instead of a subroutine call for the second argument (shamelessly stolen from Neil's regex).

## Bonus: Convert Polish notation to infix notation, ~~58~~ 52 bytes

```
s~([*-/]) *(\d++|\((?2)(?1)(?2)\)) *((?2))~($2$1$3)~

```

Try it online! \- PCRE2

```
s~        # Begin substitution - match the following:
([*-/])   # Define subroutine (?1): Character class of the four arithmetic
          # operators. This also includes "," and ".", but those are guaranteed
          # not to be in the input.
␣*        # Any number of spaces, minimum zero.
(         # Define subroutine (?2) as an argument to an operator:
    \d++  # Any number of digit characters, minimum one; force all of
          # them to be consumed (prevent backtracking).
|  # or...
    \(    # An opening parenthesis
    (?2)  # An argument
    (?1)  # An operator
    (?2)  # An argument
    \)    # A closing parenthesis
)
␣*        # Any number of spaces, minimum zero.
(         # $3 = the following:
    (?2)  # second argument
)
          # No need for "(?!\))", because parenthesized expressions won't be in
          # ARGUMENT ARGUMENT OPERATOR format.
~         # Replace with the following:
($2$1$3)  # ( argument1 operator argument2 )
~         # No flags

```

See also Convert from postfix notation to infix notation, which adds parsing of operator precedence.

# Regex (Perl / Boost), ~~47~~ 46 bytes

```
s~([*-/] *(\d++|\((?1)\)) *(?2))(?!\))~\($1\)~

```

Try it online! \- Perl
**Try it online! \- Boost**

Boost needs parentheses escaped in its replacement argument, because its conditional-replacement syntax uses parentheses. This isn't compatible with PCRE or Python`regex`, as they will interpret it as a literal `\(` and `\)`.

This exposes a bug in Boost's subroutine call processing. If `{2}` is used to match two arguments, instead of `(?2)` to match the second argument, it makes an incorrect full match. Example:

`+(+ 1 2) 3`

If the regex `([*-/]( *(\d++|\((?1)\))){2})(?!\))` is used, it matches `+(+ 1 2)` instead of the entire expression, so the closing parenthesis is added in the wrong place.

But if the regex `([*-/]( *(\d++|\(([*-/]( *\d++){2})\))){2})(?!\))` (with `(?1)` replaced with itself to one level of depth) is used instead, it correctly matches the full string.

The bug is still present in the latest version of Boost. I have reported it.

# Regex (PCRE / Ruby), ~~47~~ ~~46~~ 44 bytes

```
s~([*-/]( *(\d++|\(\g<1>\))){2})(?!\))~(\1)~

```

Try it online! \- PCRE1
Try it online! \- PCRE2
**Try it online! \- Ruby**

Ported to Ruby's subroutine syntax.

## \\$\large\textit{Functions}\\$

# Ruby, ~~75~~ ~~74~~ ~~69~~ ~~67~~ 66 bytes

*-5 bytes thanks to Steffan*
*-1 byte thanks to Dingus*

```
->s{0while s[/([*-\/]( *(\d++|\(\g<1>\))){2})(?!\))/]&&="(#$1)";s}

```

Try it online!

# Python (with `regex`), ~~107~~ ~~106~~ 105 bytes

```
import regex
f=lambda s,p=0:s==p and s or f(regex.sub('([*-/]( *(\d++|\((?1)\))){2})(?!\))',r'(\1)',s),s)

```

Try it online!

# Python 3.8+ (with `regex`), ~~101~~ ~~100~~ 99 bytes

```
lambda s:[s:=regex.sub('([*-/]( *(\d++|\((?1)\))){2})(?!\))',r'(\1)',s)for i in s][-1]
import regex

```

Can't Try it online! \- Confirmed to work on my machine, but `regex` is not installed on TIO or ATO.

Just like in Remove redundant parentheses, it's guaranteed that a fewer number of substitution iterations will be needed than the number of characters in the input, so this "do this for each character of `s`" trick works. The maximum number of substitutions approaches \\$1/2\\$ of the number of characters in the input string:

$$\lim\_{n\to\infty}{n\over {2n+2}}= {1\over 2}$$

# PowerShell, 100 bytes

```
[char[]]($p="$args")|%{$p=$p-replace'[*-/](?> *(\d+|\(((\()|[^)]|(?<-3>.))+\))){2}(?!\))','($&)'};$p

```

Try it online!

Uses Neil's regex with an additional -8 byte golf. Applies the substitution the same number of times as the length of the input in characters.

# PHP, 104 bytes

```
function($s){while($p!=$s=preg_replace('~([*-/]( *(\d++|\((?1)\))){2})(?!\))~','($1)',$p=$s));return$s;}

```

Try it online!

Thanks to Steffan for pointing out a 1 byte golf that has the added bonus of making this anonymous rather than recursive. Knocking off an additional 2 bytes from that has the further bonus of removing the "Undefined variable" warnings from this non-recursive function.

## \\$\large\textit{Full programs}\\$

# MATL, ~~54~~ 48 bytes

*-6 bytes thanks to Luis Mendo*

```
t"'([*-/]( *(\d++|\((?1)\))){2})(?!\))' '($1)'YX

```

Try it online!

This too applies the substitution the same number of times as the length of the input in characters.

# Perl `-p`, ~~51~~ ~~50~~ 49 bytes

```
1while s;([*-/]( *(\d++|\((?1)\))){2})(?!\));($1)

```

Try it online!

# PHP `-F`, 98 bytes

```
<?for($s=$argn;$p!=$s=preg_replace('~([*-/]( *(\d++|\((?1)\))){2})(?!\))~','($1)',$p=$s););echo$s;

```

Try it online!

# Answer
> 5 votes
# Rust Nightly, ~~332~~ ~~319~~ ~~307~~ 292 bytes

Can probably be golfed a lot more.

```
|b:&[char]|b.iter().chain([&' ']).scan((vec![9],1),|(a,q),&b|Some(if '0'>b{let mut o=if*q<1{*q=1;let mut u=format!("");while{let z=a.last_mut()?;*z-=1;*z<1}{a.pop();u.push(')')};u.push(b);u}else{b.into()};if b!=' '{o.insert(o.len()-1,'(');a.push(2)}o}else{*q=0;b.into()})).collect::<String>()

```

Playground Link

# Answer
> 5 votes
# MATL, ~~93~~ ~~92~~ ~~90~~ ~~89~~ ~~86~~ ~~85~~ 84 bytes

```
t"t'(?<!\()[*-/]'1&XXX<t?:&)w0XH&)40hwb'\d+|[\(-/ ]'XX"@gt1)t47>Ew41>-H+XH2=?41XH]&h

```

Try it online! Or verify all test cases.

The code uses a non-recursive approach, based on the facts that

* each operator must have a `(` immediately before, and
* the corresponding `)` must be placed immediately after the first number for which the count of numbers minus operators to the right of the `(` equals `2`.

The procedure is as follows:

Repeat these steps as many times as the input length (it would suffice to repeat as many times as the number of operators in the input string):

1. Find the first operator (`+-/*`) that is not predeced by `(`, if any.
2. Insert `(` right before that.
3. Take the substring after that position until the end and split it into groups, where each group is either a number (one or more digits), an operator, an opening or closing parenthesis, or whitespace (one or more spaces).
4. Start a counter at `0`. For each group from the previous step, increment the counter if the group is a number, and decrement it if the group is an operator.
5. When the counter reaches `2`, insert `)` right after that group.

# Answer
> 5 votes
# Curry (PAKCS), 102 bytes

```
f(s++t)|all(<'!')t=g s++t
g(' ':s)=' ':g s
g s|all(>'/')s=s
g(c:s++t)|elem c"+-*/"='(':c:g s++g t++")"

```

Try it online!

# Answer
> 5 votes
# Prolog (SWI), ~~292~~ ~~274~~ ~~125~~ ~~91~~ 129 bytes

* -18 bytes thanks to Steffan
* -999999 bytes thanks to Seffan
* -19 bytes thanks to JoKing
* -15 bytes by myself :). I realized I didn't really need to return the value "Z" since it's only possible value could be a space.
* +28 bytes to fix spacing bug :(

Just like my other answer inputs require a trailing space. I'm very new to prolog so this is probably nowhere near optimal.

```
N+Z:-N=32,$N,\X,X+Z;N/Z.
$N:-put(N).
\N:-get0(N).
32/32.
X/Z:-X<48,$40,$X,\D,D+W,W+Z,$41;X^Z.
X^Z:-X>48,$X,\W,W^Z;X=Z.
:- \X,X+_.

```

TIO

# Answer
> 4 votes
# Pip, 50 bytes

```
W#aI@aQsOPOaEIaLT0OxPBt&'(.POaEL{Oa~XIa:$'WDQxO')}

```

Try It Online! (Note: the footer is because DSO doesn't flush the output buffer until a newline is output.)

### Explanation

Loop through the input string.

* If the first character is a space, pop and output it.
* If the first character is an operator:
    + Output an open paren.
    + Pop and output the operator.
    + Push 1 (representing a close-paren) and 0 (representing the space between an operator's first and second operands) to a stack.
* Else (this is a number):
    + Output the first run of digits in the string.
    + Remove the first run of digits from the string.
    + Pop the stack; while the result is 1, output a close-paren and repeat.

### Ungolfed

```
$expr: a
$stack: ""
W # $expr {
 I @ $expr Q " " {
  O PO $expr
 } EI $expr LT "0" {
  O '(
  O PO $expr
  $stack PB 1
  $stack PB 0
 } EL {
  O $expr ~ `^\d+`
  $expr : $'
  W DQ $stack {
   O ')
  }
 }
}

```

# Answer
> 4 votes
# Ruby, 129 bytes

```
f=->(s){def k a;i,j=a.shift;j=~/\d/?(i+j): i+"("+j+k(a)+k(a)+")"end;h,t=s.scan(/(.*[^ ])( *)$/)[0];k(h.scan(/( *)([0-9]+|.)/))+t}

```

Try it online!

# Answer
> 4 votes
# Retina 0.8.2, ~~67~~ ~~66~~ 58 bytes

```
+`[*-/](?> *\d+| *\(((\()|[^)]|(?<-2>.))+\)){2}(?!\))
($&)

```

Try it online! Link includes test cases. Explanation: Much like @Deadcode's answer, the expression tries to find unparenthesised expressions to parenthesise. Explanation:

```
+`

```

Repeat until no more substitutions can be made.

```
[*-/]

```

Match an operator. Edit: Saved 1 byte thanks to @Deadcode.

```
(?> *\d+

```

Atomically match an integer parameter, ...

```
| *\(((\()|[^)]|(?<-2>.))+\))

```

... or a balanced parenthesised parameter, ... (Edit: Saved a further 8 bytes thanks to @Deadcode)

```
{2}

```

... twice.

```
(?!\))

```

Ensure that the operator wasn't previously parenthesised. (This test shamelessly stolen from @Deadcode to save 1 byte.)

```
($&)

```

Parenthesise the operator and its parameters.

Alternative approach, ~~60~~ 58 bytes:

```
(?<=(()\d+|[^*-/]|(\2|())(?<-2>.))*)\d+
$&$#4$*)
[*-/]
($&

```

Try it online! Link includes test cases. Explanation:

```
(?<=(()\d+|[^*-/]|(\2|())(?<-2>.))*)\d+
$&$#4$*)

```

Consider the minimum number of integers that would complete the prefix expression at any given point; this value increases at an operator and (obviously) decreases at an integer. Working back from a given integer, up to the point that the value decreases below the current value, count the number of times it is equal. This is the number of parentheses that should be appended.

```
[*-/]
($&

```

Prefix a `(` to each operator.

# Answer
> 4 votes
# Pip, 47 bytes

```
O({a:POysNa?a.VfaLT0?pJa.(fMJt)a}Y(aw,+XD,XX))y

```

This is a different enough approach that I thought it warranted its own answer. Try It Online!

### Explanation

First, we tokenize the input:

```
(aw,+XD,XX)
 a           Command-line argument
(         )  Find all matches of this regex:
  w            Run of whitespace
   ,           or
    +XD        Run of digits
       ,       or
        XX     Any single character

```

Now we're going to run a recursive descent parser on this list of tokens, popping each token as it's parsed. Unfortunately, functions in Pip are call-by-value rather than call-by-reference, so we store the list in the global variable `y` and modify that at each step. This also means our function doesn't actually take any arguments. Calling a function with no arguments can be a bit tricky in Pip, so sometimes we'll call it with a dummy argument that gets ignored.

```
{a:POysNa?a.VfaLT0?pJa.(fMJt)a}
{                             }  Recursive function, parses y and returns a parenthesized string
   POy                           Pop the first token from y
 a:                              Store it in the local variable a
      sNa?                       If it contains a space (whitespace token):
          a.                      Concatenate it to
            Vf                    a recursive call to the current function
              aLT0?              Else, if it is lexicographially earlier than "0" (operator):
                     a.(    )     Concatenate it to
                        f          the current function
                         MJ        called on each character in
                           t       "10" (i.e., called twice)
                                   and the results joined into a single string
                   pJ             Join the string "()" on the above result
                             a   Else (number token), just return the token

```

This function parses exactly one expression. In particular, if the input had trailing spaces, the final whitespace token is not parsed and remains in `y`. Therefore, the overall program is:

```
O({...}Y(...))y
        (...)    Tokenize the input
       Y         Yank the list of tokens into y
 (           )   Call, with that argument
  {...}          the parser function
O                Output the resulting parenthesized expression without a newline
              y  Autoprint the remainder of y, if any, with a trailing newline

```

# Answer
> 3 votes
# Python, 186 bytes

```
lambda s,a=[]:(t:=s.rstrip(),[a:=c<'!'and a[:-1]+[c+a[-1]]or a+[c.isdigit()and c or"("+c+a.pop()+a.pop()+")"]for c in re.findall("\d+|.",t)[::-1]],a)[2][-1]+' '*(len(s)-len(t))
import re
```

Attempt This Online!

Handling trailing whitespace added a lot of bytes, even though leading whitespace didn't.

If we didn't have to handle trailing whitespace:

# Python, 149 bytes

```
lambda s,a=[]:[a:=c<'!'and a[:-1]+[c+a[-1]]or a+[c.isdigit()and c or"("+c+a.pop()+a.pop()+")"]for c in re.findall("\d+|.",s)[::-1]][-1][-1]
import re
```

Attempt This Online!

If there was no whitespace or multi-digit numbers:

## Python, 90 bytes

```
lambda s,a=[]:[a:=a+[c.isdigit()and c or"("+c+a.pop()+a.pop()+")"]for c in s[::-1]][-1][0]
```

Attempt This Online!

# Answer
> 3 votes
# Charcoal, 46 bytes

```
⊞υω⭆θ⎇№+-*/ι∧⊞Ｏ⊞Ｏυ⁺⊟υ)ω⁺(ι⎇›№⭆χλι№⭆χλ§θ⊕κ⁺ι⊟υι

```

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

```
⊞υω

```

Start with `0` on top of the stack.

```
⭆θ

```

Loop through the input characters.

```
⎇№+-*/ι

```

If this is an operator, then...

```
∧⊞Ｏ⊞Ｏυ⁺⊟υ)ω

```

... increment the top of the stack, push `0` to the top of the stack, and...

```
⁺(ι

```

... output the operator prefixed with a `(`.

```
⎇›№⭆χλι№⭆χλ§θ⊕κ

```

Otherwise, if this is a digit but the next isn't, then...

```
⁺ι⊟υ

```

... output the digit followed by a number of `)`s given by the top of the stack.

```
ι

```

Otherwise, just output the character.

# Answer
> 3 votes
# nearley, 78 bytes

```
m->_ p _{%a=>a.flat(1/0)%}
p->[\d]:+|[-+/*] _ p _ p{%a=>['(',a,')']%}
_->" ":*

```

Post-processing functions for production rules, denoted by `{%...%}`, are evaluated in JavaScript. Each function is called with an array of post-processed results for each terminal or non-terminal from which the rule is produced.

This EBNF grammar is defined by three non-terminal production rules `m`, `p`, and `_`.

* `_` is zero or more spaces
* `p` is one or more digits OR one of `-`, `+`, `/`, `*` followed by `_`, `p`, `_`, then `p`.
* `m` is `_`, `p`, then `_`.

The post-processing function of `p` wraps the result in parentheses when it is produced by `[-+/*] _ p _ p`, and the post-processing function of `m` flattens the nested array of characters produced from parsing the complete input.

You can test it in the Nearley Parser Playground, but you'll need to add the the code above and the test cases yourself since there's no permalink feature.

Alternatively, if you're comfortable with the Developer Tools in your browser, you can evaluate the following snippet on the console while loaded on that page to save yourself from having to insert the test cases manually.

```
localStorage.playgroundState=String.raw`{"active":0,"compiled_grammar":"module.exports={ParserRules:[{name:'m',symbols:['_','p','_'],postprocess:a=>a.flat(1/0)},{name:'p$ebnf$1',symbols:[/[\\d]/]},{name:'p$ebnf$1',symbols:[/[\\d]/,'p$ebnf$1'],postprocess:a=>[a[0],...a[1]]},{name:'p',symbols:['p$ebnf$1']},{name:'p',symbols:[/[-+/*]/,'_','p','_','p'],postprocess:a=>['(',a,')']},{name:'_$ebnf$1',symbols:[]},{name:'_$ebnf$1',symbols:[{literal:' '},'_$ebnf$1'],postprocess:a=>[a[0],...a[1]]},{name:'_',symbols:['_$ebnf$1']}],ParserStart:'m'}","tabs":[{"name":"Add parentheses to Polish notation","editor_value":"m->_ p _{%a=>a.flat(1/0)%}\np->[\\d]:+|[-+/*] _ p _ p{%a=>['(',a,')']%}\n_->\" \":*","errors":[],"tests":["+1 2","++ 1 2 3","    +1    +2 3","* *1 2 /3 0  ","//30 300/18 205","/ -20/ 30 30  999","/////1 2 3 4 5 6","/1/2/3/4/5/6/7/8 9"]}]}`;location.reload()

```

# Answer
> 3 votes
# Prolog (SWI), ~~178~~ ~~177~~ 175 bytes

*-3 bytes thanks to Steffan*

```
S/L:-atom_codes(S,L).
[C|T]*P*R:-C=32,T*Q*R,P=[C|Q];C>47,[C|T]+P+R;T*E*Q,Q*F*R,append([[40,C],E,F,[41]],P).
[N|T]+[N|P]+R:-N>47,T+P+R.
X+_+X.
S^T:-S/L,L*P*R,append(P,R,M),T/M.

```

Try it online!

### Explanation

The other Prolog answer cleverly reads characters from stdin one at a time. I wanted to try a more "traditional" solution, a predicate which takes a string and generates another string.

```
S/L:-atom_codes(S,L).

```

Define the `/` operator as a shortcut for converting an atom or string to a list of codepoints and vice versa.

```
[C|T]*P*R:-

```

The `*` operator is the main workhorse here. It takes a list of codepoints (the first of which is `C` and the remainder of which are `T`) and parses one Polish-notation expression from the beginning of it, returning the correctly parenthesized parsed expression in `P` and the rest of the list of codepoints in `R`. It has three branches:

```
C=32,T*Q*R,P=[C|Q]

```

If `C` is a space, parse everything after the space and prepend a space to the result.

```
C>47,[C|T]+P+R

```

If `C` is a digit, parse a run of digits using the `+` operator (defined below).

```
T*E*Q,Q*F*R,append([[40,C],E,F,[41]],P).

```

Otherwise, `C` is an operator. Parse a subexpression `E`, then parse another subexpression `F`. Finally, concatenate an open paren, the operator `C`, both subexpressions, and a close paren together to form the result `P`.

To parse a run of digits:

```
[N|T]+[N|P]+R:-N>47,T+P+R.

```

If the list of codepoints starts with a digit `N`, parse a run of digits from the portion following `N`, and prepend `N` to the result.

```
X+_+X.

```

Otherwise, the remainder is the same as the input. The result is a "don't care" (`_`), which apparently works because (based on its use in the calling predicate) it has to be a list, and the empty list is the first possibility Prolog tries.

The `^` operator is the main predicate:

```
S^T:-S/L,L*P*R,append(P,R,M),T/M.

```

It takes a string `S`, converts it to a list of codepoints `L`, parses `L` into a parenthesized expression `P` and remainder `R`, concatenates `P` and `R` into `M` (so as to keep any trailing spaces), and converts `M` back into the string result `T`.

---

If I can take and return lists of codepoints instead of strings, this solution is **145 bytes**:

```
[C|T]*P*R:-C=32,T*Q*R,P=[C|Q];C>47,[C|T]+P+R;T*E*Q,Q*F*R,append([[40,C],E,F,[41]],P).
[N|T]+[N|P]+R:-N>47,T+P+R.
X+_+X.
X^Y:-X*P*R,append(P,R,Y).

```

# Answer
> 2 votes
# Python3, 226 bytes

```
lambda s:f(s)[0]
import re
f=lambda s:((' '*O[0].count(' '))+'('+O[0].lstrip()+(J:=f(s[len(O[0]):]))[0]+(T:=f(J[1]))[0]+')',T[1])if(O:=re.findall('^(?:\s+)*[\*\-\+/]',s))else((O:=re.findall('^(?:\s+)*\d+',s))[0],s[len(O[0]):])

```

Try it online!

# Answer
> 2 votes
# C (GCC), 174 bytes

```
#define p putchar(
f(char *x){int s[100]={0},*S=s,b,c;for(;*x;){if(b=*x==32)p*x++);for(c=0;isdigit(*x);b=c=1)p*x++);for(*S+=c;*S==2;)p')'),*S=0,*--S+=1;b||++S+p'(')+p*x++);}}
```

Attempt This Online!

Note: as it is, it works up to `100` nested brackets.

# Answer
> 2 votes
# 05AB1E, ~~32~~ 30 bytes

```
ÎĆü2vyÇн₆%Ígi'(?>0}y¬?dRJi')×?

```

Input as a list of characters.

Try it online or verify all test cases.

Port of *@Neil*'s Charcoal answer, so make sure to upvote him as well!

**Explanation:**

```
Î              # Push 0 and the input character-list
 Ć             # Enclose it; append its own head
  ü2           # Pop and push its overlapping pairs
 v             # Loop over each pair of characters `y`:
  y            #  Push the current pair `y`
   Ç           #  Convert both to its codepoint integer
    н          #  Pop and leave just the first integer
     ₆%        #  Modulo-36
       Í       #  +2
        g      #  Then pop and push the length
         i     #  If this is 1 (which means it's an operator character):
          '(? '#   Print "("
          >    #   Increase the current value by 1
          0    #   Push a new 0
         }     #  Close the if-statement
  y            #  Push pair `y` again
   ¬           #  Push its first character (without popping the pair)
    ?          #  Pop and output this first character
     d         #  Check for both characters whether they're digits
      R        #  Reverse the pair
       J       #  Join them together to a string
        i      #  If this is "01":
         ')×  '#   Pop the top value, and push a string with that many ")"
            ?  #   Pop and print it

```

# Answer
> 1 votes
# C (clang), ~~136~~ ~~132~~ 125 bytes

```
#define p putchar(
x;*s;r(n){for(;*s&&n<2;x||p*s<40?n--,*s++:p'(')+!!r(!p*s++))))for(x=!++n;*s>47;)x=p*s++);}f(*a){s=a;r(0);}

```

Try it online!

---
Tags: code-golf, string
---