title: Binary Puzzle Solver

text:
# Question
Title: Binary Puzzle Solver
## Introduction

### Rules of the puzzle:

The puzzle Binary (also known as Takuzu or Subiku) is very simple to understand, and has only a few rules:
Since the name of the game is binary it's pretty obvious, but you can only fill in zeros and ones.

1. No more than two of the same digit can be vertically or horizontally adjacent to each other
2. Each row and each column must contain an equal amount of zeros and ones (this implicitly means every binary game will always have even dimensions).
3. There may be no duplicated rows and no duplicated columns (with the exact same order of zeros and ones).

You can play the game at www.binarypuzzle.com if you want to.

### Tactics:

Due to rule 1, we can always fill in a digit if:
\- There are already two of the same digit vertically or horizontally adjacent to each other, in which case we can fill in the opposite digit at both sides. I.e. `.11...``0110..`.
\- There are two of the same digit vertically or horizontally with only one gap in between them. I.e. `.1.1..``.101..`

Due to rule 1, when three gaps are left and we cannot have three adjacent of the same digit, we can fill in one of the gaps. I.e. `.0.1.0``10.1.0` (We still have to fill in two ones, and we cannot have three adjacent ones in the middle, so the first gap has to be a `1`.)

Due to rule 2, we can always fill in the remaining gaps in a row or column if halve of them is already filled in with the opposite digit. I.e. `.1.011``010011`

Due to rule 3, we can always fill in the opposite digits if only two are left to solve on an equally ordered line. I.e. `101100 & 1..100``101100 & 110100`

Due to rule 3, we can sometimes fill in a gap when three gaps are left on an equally ordered line. I.e. `010011 & .1.01.``010011 & .1.010` (Here we cannot fill in a `1` at the end, because that would mean we have to fill in zeros at the other two gaps, making both lines equal in order.)

### Example:

We start with the following 6x6 grid with some ones and zeros filled in (and the dots are gaps we have yet to fill in):

```
.1....
.10.0.
1.11..
.1....
...1.0
......

```

Due to rules 1 & 2 we can fill in these digits:

```
.1.01.
.1010.
101100
010011
.0.1.0
.010..

```

Due to rule 1 we can fill in a 1 at row 5, column 1:

```
.1.01.
.1010.
101100
010011
10.1.0
.010..

```

Due to rule 3 we can fill in a 0 at row 1, column 6 (when looking at row 4):

```
.1.010
.1010.
101100
010011
10.1.0
.010..

```

Now we can continue to fill gaps with digits due to rules 1 & 2:

```
.1.010
010101
101100
010011
10.1.0
.010.1

```

Now we can finish row 5 due to rule 3 (when looking at row 3):

```
.1.010
010101
101100
010011
100110
.010.1

```

And then we can finish the puzzle due to rules 1 & 2:

```
011010
010101
101100
010011
100110
101001

```

## Challenge:

The challenge is simply: given the starting grid, output the solved puzzle.

NOTE: You don't have to implement the rules above. You of course can, and it should give you hints on how to implement this challenge, but bruteforcing the solution with the rules in mind is completely fine.
How you solve it is up to you, but the challenge is to output the solved puzzle.

### Challenge rules:

* Input and output format for the grid is flexible, but please state what you use. (I.e. 2D byte-array; String with newlines; etc.)
* This above also applies to the characters used. In the example I've used `01.`, but if you want you can use `ABx` instead. Please state what input/output format and characters you've used.
* You can assume only the following grid sizes will be used: `6x6`; `8x8`; `10x10`; `12x12`; `14x14`; `16x16`.

### General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code.
* Also, please add an explanation if necessary.

### Test cases:

The dots are only added for readability, feel free to use spaces or anything else you prefer for gaps instead. Both in and output format is flexible.

```
Input:
1..0..
..00.1
.00..1
......
00.1..
.1..00

Output:
101010
010011
100101
011010
001101
110100

Input:
.1....
.10.0.
1.11..
.1....
...1.0
......

Output:
011010
010101
101100
010011
100110
101001

Input:
.......1..
.00..0..1.
.0..1..0.0
..1...1...
1.1......1
.......1..
.0..1...0.
....11...0
.0.0..1..0
0...0...1.

Output:
0110010101
1001100110
1001101010
0110011001
1010100101
0101010110
1001101001
0110110100
1010011010
0101001011

```

# Answer
> 4 votes
# Brachylog, 34 bytes

```
{ℕ<2}ᵐ²&≜{d?ọᵐctᵐ=&{ḅlᵐ⌉<3}ᵐ}&\↰₂&

```

Try it online!

This is pretty damn slow, so the test case on TIO is 4x4. I am currently running the 6x6 test case on my computer to see how much time it takes.

This takes a list of lists as input. The unknown values should be indicated with variables, that is with all-uppercase strings (and they should all be different, as otherwise you would be indicating that some cells must have the same value)

### Explanation

We constrain the values to be in `{0,1}`, then we try instantiations of the variables until one respects all 3 rules. This is why this is so slow (because it will try all of them until finding one; and because in that case Brachylog is not implemented well enough so that constraints can be imposed before trying a possible matrix).

```
                                 &  Output = Input
{   }ᵐ²                             Map two levels on the Input (i.e. each cell):
 ℕ<2                                  The cell is either 0 or 1
       &≜                           Assign values to all cells
         {                  }       Define predicate 2:
          d?                          The Input with no duplicates is still the Input
                                        (i.e. all rows are different)
           ?ọᵐctᵐ=                    All occurences of 1s and 0s for each rows are equal
                  &{      }ᵐ          Map on rows:
                    ḅlᵐ                 Get the lengths of runs of equal values
                       ⌉<3              The largest one is strictly less than 3
                             &\↰₂   Apply predicate 2 on the transpose of the Input
                                      (i.e. do the same checks but on columns)

```

# Answer
> 3 votes
## JavaScript (ES6), ~~274~~ 270 bytes

Takes input as a 2D array, where empty cells are marked with `2`. Prints all possible solutions to the console.

```
f=(a,x=0,y=0,w=a.length,p,R=a[y])=>(M=z=>!a.some((r,y)=>/(0|1),\1,\1/.exec(s=r.map((v,x)=>(v=z?v:a[x][y],b-=v&1,c-=!v,m|=v&2,v),b=c=w/2))||b*c<0|o[b*c||s]&(o[s]=1),o={}))(m=0)&M(1)&&(m?R&&[0,1].map(n=>(p=R[x])==n|p>1&&(R[x]=n,f(a,z=(x+1)%w,y+!z),R[x]=p)):console.log(a))

```

### How it works

The first part of the code uses the `M()` function to check the validity of the current board, both horizontally and vertically.

```
M = z =>
  !a.some((r, y) =>
    /(0|1),\1,\1/.exec(
      s = r.map((v, x) =>
        (
          v = z ? v : a[x][y],
          b -= v & 1,
          c -= !v,
          m |= v & 2,
          v
        ),
        b = c = w / 2
      )
    ) ||
    b * c < 0 |
    o[b * c || s] &
    (o[s] = 1),
    o = {}
  )

```

It maps a full row or column to the string ***s***. This is actually an array coerced to a string, so it looks like `"1,2,2,0,2,2"`.

It uses:

* The regular expression `/(0|1),\1,\1/` to detect 3 or more consecutive identical digits.
* The counters ***b*** and ***c*** to keep track of the number of *ones* and *zeros*. Both counters are initialized to ***w / 2*** and decremented each time a *one* or a *zero* (respectively) is encountered. This leads to either:
    + ***b = c = 0******b * c = 0*** → the line is complete and correct (as many *zeros* as *ones*)
    + ***b \> 0 AND c \> 0******b * c \> 0*** → the line is not complete but correct so far (we don't have more than ***w / 2*** *zeros* or more than ***w / 2*** *ones*)
    + ***b \< 0 OR c \< 0******b * c \< 0*** → the line is invalid
* The flag ***m*** (for 'missing') which is non-zero if there's at least one remaining *two* on the board.
* The object ***o*** to keep track of all line patterns encountered so far.

If the board is invalid, we stop immediately. If the board is valid and complete, we print it to the console. Otherwise, the second part of the code attempts to replace each *2* with either a *zero* or a *one* with recursive calls:

```
[0, 1].map(n =>
  (p = a[y][x]) == n |
  p > 1 && (
    a[y][x] = n,
    f(a, z = (x + 1) % w, y + !z),
    a[y][x] = p
  )
)

```

### Demo

```
f=(a,x=0,y=0,w=a.length,p,R=a[y])=>(M=z=>!a.some((r,y)=>/(0|1),\1,\1/.exec(s=r.map((v,x)=>(v=z?v:a[x][y],b-=v&1,c-=!v,m|=v&2,v),b=c=w/2))||b*c<0|o[b*c||s]&(o[s]=1),o={}))(m=0)&M(1)&&(m?R&&[0,1].map(n=>(p=R[x])==n|p>1&&(R[x]=n,f(a,z=(x+1)%w,y+!z),R[x]=p)):console.log(a))

console.log('Example #1')
f([
  [1,2,2,0,2,2],
  [2,2,0,0,2,1],
  [2,0,0,2,2,1],
  [2,2,2,2,2,2],
  [0,0,2,1,2,2],
  [2,1,2,2,0,0]
])

console.log('Example #2')
f([
  [2,2,2,2,2,2,2,1,2,2],
  [2,0,0,2,2,0,2,2,1,2],
  [2,0,2,2,1,2,2,0,2,0],
  [2,2,1,2,2,2,1,2,2,2],
  [1,2,1,2,2,2,2,2,2,1],
  [2,2,2,2,2,2,2,1,2,2],
  [2,0,2,2,1,2,2,2,0,2],
  [2,2,2,2,1,1,2,2,2,0],
  [2,0,2,0,2,2,1,2,2,0],
  [0,2,2,2,0,2,2,2,1,2]
])
```

# Answer
> 2 votes
# Jelly, ~~53~~ 51 bytes

```
ṡ€3ḄFf0,7L
SḤnLṀȯÇ
⁻QȯÇ
Fṣ©2L’0,1ṗż@€®F€s€LÇÐḟZÇ$Ðḟ

```

Takes a list of lists representing the grid, containing `0`, `1`, and `2` (the spaces). Returns a list of lists of lists, each list of lists is in the same format (although with no `2`s) and represents a possible solution to the input.

**Try it online!** (this wont run any of the question's test cases due to memory limitations - all 2nSpaces grids are created as a list of list of lists of integers - but I've put a relatively hefty case there with a single solution). The footer separates out and formats the grids.

Pure brute force method - implements the rules and checks them for each grid that could be formed by replacing any of the `2`s with `1`s or `0`s.

```
ṡ€3ḄFf0,7L - Link 1, # of runs of 3 1s or 3 0s by row: list of lists
ṡ€3        - all contiguous slices of length 3 for €ach list
   Ḅ       - convert all results from binary
    F      - flatten into one list
     f     - filter keep values in:
      0,7  -   0 paired with 7: [0,7]
         L - length

SḤnLṀȯÇ - Link 2, unequal counts of 1s and 0s by column ...or link 1: list of lists
S       - sum (vectorises, hence "by column", counts 1s since only 1s or 0s appear)
 Ḥ      - double
   L    - length (number of rows - OK since square)
  n     - not equal? (vectorises)
    Ṁ   - maximum (1 if any not equal)
     ȯÇ - ... or last link (1) as a monad

⁻QȯÇ - Link 3, rows are unique ...or link 2: list of lists
 Q   - unique
⁻    - not equal?
  ȯÇ - ... or last link (2) as a monad

Fṣ©2L’0,1ṗż@€®F€s€LÇÐḟZÇ$Ðḟ - Main link: list of lists
F                           - flatten
 ṣ©2                        - split at 2s and copy the result to the register
    L                       - length (# of such slices)
     ’                      - decrement (# of 2s)
      0,1                   - 0 paired with 1
         ṗ                  - Cartesian power (all binary lists of length # of 2s)
             ®              - recall value from register (the flat version split at 2s)
          ż@€               - zip (reversed @rguments) for €ach (1s & 0s where 2s were)
              F€            - flatten €ach
                s€L         - split €ach into chunks of length length(input) (into rows)
                    Ðḟ      - filter discard if:
                   Ç        -   call last link(3) as a monad
                         Ðḟ - filter discard if:
                        $   -   last two links as a monad:
                      Z     -     transpose
                       Ç    -     call last link(3) as a monad

```

---
Tags: code-golf, game, binary, binary-matrix
---


title: May the fourth be with flu

text:
# Question
Title: May the fourth be with flu
Since tomorrow is the 4th of May, here's a little Star Wars themed post to prepare you mentally to all the bad jokes coming tomorrow.

**BACKSTORY**

During a session of the galactic senate all the senators are sitting in an `n*n` grid. A sudden outbreak of JarJar flu (which lasts forever and causes the infected to speak like JarJar Binks) causes some of the senators to get infected.

Here's an example with a `6*6` grid where the `X` are the infected senators, the corresponding list is : `[[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[0,5]]`:

After that the infection begins to spread step by step. Two senators are **adjacent** if they share a whole edge on the grid (i.e., top,bottom,right,left), which means we exclude diagonals.

We can conclude a senator can be adjacent to 2,3 or 4 other senators and claim the following rules for the infection :

* A senator that has been infected stays infected forever
* A senator is infected at a step if he was adjacent to 2 or more infected senator at the previous step

Here's an example with the previous grid which shows the 2 first steps of the infection :

After the nexts steps all the senate will be infected

**YOUR TASK**

Your code doesn't need to handle invalid inputs like a list greater than `n*n` or coordinates that aren't distincts.

Your code will take as input a list of couples of integers (or a binary grid or any other format that suits your language) and an integer `n` (which can be unnecessary if you use another format than a list) , for instance :

```
8 [[1,2],[1,1],[7,4],[2,7],[4,3]]

```

n being the side of the grid which means the grid will be a n\*n grid, and the list of couples of integers being the coordinates of the cells of the initally infected senators.

The bottom left of the grid is \[0,0\] and the top right is \[n-1,n-1\]. The top left is \[0,n-1\].

Your code must output an integer :

`-1` or a falsy value or an error if the whole grid will never be totally infected or the minimum number of steps required to infect the whole grid

**Test cases**

```
6 [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]] => 7

4 [[1,1][0,3][1,0][3,0][3,3]] => 9

```

Remember that this is , thus the shortest answer in bytes wins !

# Answer
# MATL, ~~29~~ 28 bytes

```
tn:"tlY6Z+1>Z|t?@.]]Nl=?l_]&

```

Input is in the form of a 2D matrix of 1's and 0's

Try it at **MATL Online**

**Explanation**

```
        % Implicitly grab user input as a 2D matrix
t       % Duplicate the inputs
n:      % Count the number of elements in the input (N) and create the array [1...N]
"       % Loop this many times (maximum number of steps we analyze)
  t     % Duplicate the top element
  lY6   % Push the 2D array => [0 1 0; 1 0 1; 0 1 0]
  Z+    % Perform 2D convolution (and maintain the size)
  l>    % Find all values that are >= 2
  Z|    % Perform an element-wise OR with the previous state
  t?    % If all elements are 1's
    @.  % Push the current index and break out of the loop
  ]     % End of if
]       % End of for loop
Nl=?    % If there is only one element on the stack
  l_    % Push a negative one
]       % End of if statement
&       % Display the top stack element

```
> 2 votes

# Answer
# APL (Dyalog 16.0), 54 characters or 60 bytes

Takes enclosed matrix as argument, returns the step number which completes infection, i.e. 1=is already fully infected. 0=does not fully spread, which is just 1 + the OP's numbers.

54 characters (Unicode):

```
(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⌺3 3)⊃⍵:⍵⋄(⊂f⊃⍵),⍵}⍣≡

```

60 bytes (Classic):

```
(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⎕U233A 3 3)⊃⍵:⍵⋄(⊂f⊃⍵),⍵}⍣≡

```

is equivalent to `⎕U233A`

Examples' run:

```
      g←(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⌺3 3)⊃⍵:⍵ ⋄ (⊂f⊃⍵),⍵}⍣≡
      ⎕IO←0
      b←⊂⊖⍉~@(⎕JSON'[[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]]')⊢0⍴⍨2⍴6
      g b
8
      b←⊂⊖⍉~@(⎕JSON'[[1,1],[0,3],[1,0],[3,0],[3,3]]')⊢0⍴⍨2⍴4
      g b
10

```

The steps are as follows:

```
┌─────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────────┐
│ X       X   │ X X     X   │ X X X   X   │ X X X X X   │ X X X X X   │ X X X X X   │ X X X X X   │ X X X X X X │
│   X         │ X X X       │ X X X X     │ X X X X X   │ X X X X X   │ X X X X X   │ X X X X X X │ X X X X X X │
│     X X     │   X X X     │ X X X X     │ X X X X     │ X X X X X   │ X X X X X X │ X X X X X X │ X X X X X X │
│             │     X       │   X X X     │ X X X X X   │ X X X X X X │ X X X X X X │ X X X X X X │ X X X X X X │
│     X       │     X X     │     X X X   │   X X X X X │ X X X X X X │ X X X X X X │ X X X X X X │ X X X X X X │
│       X   X │     X X X X │     X X X X │     X X X X │   X X X X X │ X X X X X X │ X X X X X X │ X X X X X X │
└─────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────────┘
┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│ X     X │ X     X │ X     X │ X     X │ X     X │ X     X │ X   X X │ X X X X │ X X X X │ X X X X │
│         │         │         │         │       X │     X X │   X X X │ X X X X │ X X X X │ X X X X │
│   X     │   X     │   X X   │   X X X │   X X X │   X X X │   X X X │   X X X │ X X X X │ X X X X │
│   X   X │   X X X │   X X X │   X X X │   X X X │   X X X │   X X X │   X X X │   X X X │ X X X X │
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘

```
> 3 votes

# Answer
# Python, 231 bytes

```
g=input()
q=lambda r,c:g[r][c]if(0<=r<m)*(0<=c<m)else 0
m=len(g);p=t=0;n=range(m)
while not all([r for k in g for r in k]):h=[[g[r][c]or sum([q(r+1,c),q(r-1,c),q(r,c+1),q(r,c-1)])>1 for c in n] for r in n];t+=1;0/(g!=h);g=h
print t

```

It raises an error if it isn't possible.

Try it online!
> 2 votes

# Answer
# Pyth, 49 bytes

```
J^UE2*lK.uS{+NeMf>hT1r8S@Jsmm+VdkNs_MB_MBU2Q)qJeK

```

Test suite.

Uses 1-indexing for the output.
> 2 votes

# Answer
## JavaScript (ES6), 132 bytes

```
f=s=>(w=s.search`\n`,t=` `.repeat(w+1),t+=s+t,t=s.replace(/0/g,(_,i)=>1-t[i]-t[i+=w]-t[i+=2]-t[i+w]>>>31),t==s?0/!/0/.test(s):1+f(t))

```

Where `\n` represents the literal newline character. Takes input as a string of `0`s and `1`s in a newline-delimited array. Returns `NaN` if the grid will never become fully infected.
> 1 votes

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


title: Enumerate binary trees

text:
# Question
Title: Enumerate binary trees
## Binary trees

A binary tree is a tree with nodes of three types:

* terminal nodes, which have no children
* unary nodes, which have one child each
* binary nodes, which have two children each

We can represent them with the following grammar, given in BNF (Backus–Naur form):

```
<e> ::=
      <terminal>
    | <unary>
    | <binary>

<terminal> ::=
    "0"

<unary> ::=
    "(1" <e> ")"

<binary> ::=
    "(2" <e> " " <e> ")"

```

In this grammar the nodes are given in preorder and each node is represented by a digit which is the number of children it has.

## Motzkin numbers

Motzkin numbers (OEIS) (Wikipedia) have many interpretations, but one interpretation is that the `n`th Motzkin number is the number of distinct binary trees with `n` nodes. A table of Motzkin numbers starts

```
N          Motzkin number M(N)
1          1
2          1
3          2
4          4
5          9
6         21
7         51
8        127
    ...

```

e.g. `M(5)` is 9, and the nine distinct binary trees with 5 nodes are

```
1      (1 (1 (1 (1 0))))
2      (1 (1 (2 0 0)))
3      (1 (2 0 (1 0)))
4      (1 (2 (1 0) 0))
5      (2 0 (1 (1 0)))
6      (2 0 (2 0 0))
7      (2 (1 0) (1 0))
8      (2 (1 (1 0)) 0)
9      (2 (2 0 0) 0)

```

## Task

Take a single positive integer `n` as input and output all of the distinct binary trees with `n` nodes.

Examples for `n` from 1 to 5 with parenthesis included for readability

```
0

(1 0)

(1 (1 0))
(2 0 0)

(1 (1 (1 0)))
(1 (2 0 0))
(2 0 (1 0))
(2 (1 0) 0)

(1 (1 (1 (1 0))))
(1 (1 (2 0 0)))
(1 (2 0 (1 0)))
(1 (2 (1 0) 0))
(2 0 (1 (1 0)))
(2 0 (2 0 0))
(2 (1 0) (1 0))
(2 (1 (1 0)) 0)
(2 (2 0 0) 0)

```

## Input

The input will be one positive integer.

## Output

The output should be an intelligible representation of the distinct binary trees with that many nodes. It is not compulsory to use the exact string given by the BNF grammar above: it is sufficient that the syntax used give an unambiguous representation of the trees. E.g. you could use `[]` instead of `()`, an extra level of brackets `[[]]` instead of `[]`, outer parenthesis are present or missing, extra commas or no commas, extra spaces, parenthesis or no parenthesis, etc.

All of these are equivalent:

```
(1 (2 (1 0) 0))
[1 [2 [1 0] 0]]
1 2 1 0 0
12100
(1 [2 (1 0) 0])
.:.--
*%*55
(- (+ (- 1) 1))
-+-11

```

Also a variation purposed by @xnor in a comment. Since there is a way to translate this to a format that can be understood it is acceptable.

```
[[[]][]]  is (2 (1 0) 0)

```

To make this easier to understand convert some of the `[]` to `()` like so

```
[([])()]

```

Now if you start with

```
[]

```

then insert a binary which needs two expressions you get

```
 [()()] which is 2

```

and then for the first () insert a unary which needs one expression you get

```
 [([])()] which is 21

```

but since `[]` or `()` with no inner bracketing can represent 0 which needs no more expressions you can interpret it as

```
 2100

```

Note that answers should work theoretically with infinite memory, but will obviously run out of memory for an implementation-dependent finite input.

## Variations of output

```
BNF             xnor       Christian   Ben
b(t, b(t, t))   [{}{{}{}}] (0(00))     (1, -1, 1, -1)
b(t, u(u(t)))   [{}{(())}] (0((0)))    (1, -1, 0, 0)
b(u(t), u(t))   [{()}{()}] ((0)(0))    (1, 0, -1, 0)
b(b(t, t), t)   [{{}{}}{}] ((00)0)     (1, 1, -1, -1)
b(u(u(t)), t)   [{(())}{}] (((0))0)    (1, 0, 0, -1)
u(b(t, u(t)))   [({}{()})] ((0(0)))    (0, 1, -1, 0)
u(b(u(t), t))   [({()}{})] (((0)0))    (0, 1, 0, -1)
u(u(b(t, t)))   [(({}{}))] (((00)))    (0, 0, 1, -1)
u(u(u(u(t))))   [(((())))] ((((0))))   (0, 0, 0, 0)

```

## A possible place to check for duplicate trees

One place to check for a duplicate is with M(5).
This one tree was generated twice for M(5) from M(4) trees

```
(2 (1 0) (1 0))

```

the first by adding a unary branch to

```
(2 (1 0) 0)

```

and second by adding a unary branch to

```
(2 0 (1 0))

```

## Understanding BNF

BNF is composed of simple rules:

```
<symbol> ::= expression

```

where on the left is a symbol name surrounded by `<>`.
On the right is the expression for constructing the symbol. Some rules use other rules in the construction, e.g.

```
<e> ::= <terminal>

```

`e` can be a `terminal`

and some rules have characters that are used in constructing the symbol, e.g.

```
<terminal> ::= "0"

```

`terminal` is just the character zero.

Some rules have multiple ways of constructing them, e.g.

```
<e> ::=
      <terminal>
    | <unary>
    | <binary>

```

An `e` can be a `<terminal>` or a `<unary>` or a `<binary>`.

And some rules are a sequence of parts, e.g.

```
<unary> ::= "(1" <e> ")"

```

A `unary` is the characters `(1` followed by what can be constructed for `e` followed by `)`.

You always start with the starting rule, which for this `<e>`.

Some simple examples:

The simplest sequence is just `0`. So we start with the starting rule `<e>` and see that there are three choices:

```
  <terminal>
| <unary>
| <binary>

```

so take the first one `<terminal>`. Now a terminal has no choices and is `0`. So replace `<terminal>` with `0` in the `<e>` rule and you are done.

Then next one is `(1 0)`. Start with `<e>` and use rule `<unary>` which has

```
"(1" <e> ")"

```

Now this needs an `<e>` so we go back to `<e>` and make a choice of one of the three, this time choosing, `<terminal>` which gives `0`. Replacing `0` into `(1 <e> )` gives `(1 0)`, and this is replaced into `<unary>` so `<e>` is `(1 0)`.

# Answer
> 13 votes
## Haskell, 68 bytes

```
t 0=[""]
t 1=["0"]
t n=['(':x++y++")"|k<-[1..n-1],x<-t k,y<-t$n-k-1]

```

Terminal nodes are represented by `0`, unary and binary nodes by `(e)` resp. `(ee)`, so the two three-node trees are given as `(00)` and `((0))`.

Examples:

```
*Main> t 5
["(0(00))","(0((0)))","((0)(0))","((00)0)","(((0))0)","((0(0)))","(((0)0))","(((00)))","((((0))))"]
*Main> length $ t 8
127
*Main> length $ t 15
113634

```

# Answer
> 5 votes
## CJam (37 bytes)

```
0aa{_2m*2\f+1Y$f+++:e__&}qi:A*{,A=},p

```

Online demo. Note that this is not very efficient, and you probably don't want to try calculating input `5` online.

Dissection to follow.

# Answer
> 5 votes
## Pyth (24 21 19 bytes)

This is based on my Python 3 solution.

```
f!|sTf<sY0._T^}1_1t

```

It's my first time using Pyth so this is likely still golfable.

**Example**, output when input is `4`:

```
[[1, 0, -1], [1, -1, 0], [0, 1, -1], [0, 0, 0]]

```

1 represents a binary node, 0 represents a unary node, and -1 represents a terminal node. There is an implied terminal node at the end of every tree.

**Explanation**:

```
f!|sTf<sY0._T^}1_1t
f                    filter
             ^    t  length n-1 lists of elements
              }1_1   from [1, 0, -1]
 !|                  for when both
   sT                sum of list is 0, and
     f    ._T        for each prefix of list,
      <sY0           sum of prefix is non-negative.

```

# Answer
> 4 votes
## brainfuck, 107 bytes

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

```

Formatted:

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

```

Try it online

Input is taken as a byte, and the tree `12100` is represented as `\x01\x02\x03\x02`: to convert back, translate `tr/\x01\x02\x03/012/`, reverse the string, and add a final `0`. Trees are separated by `\xfe`. (The output can be made easier to read by e.g. changing the first `-` into `-36` and the `.` into `+47.-47`, where `-36` means a string of 36 `-` characters, etc.)

This approach makes use of the property (which Ben Frankel also used): considering the possible nodes as `-1, 0, 1` and disregarding the final `-1` node, a list represents a valid tree if and only if (1) all prefixes of the list have non-negative sum, and (2) the sum of the entire list equals `0`. The first condition is maintained while generating intermediate nodes, so only the second condition needs to be checked at the end.

The tape is divided into 5-node cells,

```
i d x 0 0

```

where `i` is the index (descending from left to right), `d` is the partial sum, and `x` is the element.

Sketch of control flow:

```
take n and push initial node
while stack is non-empty:
    if rightmost node can be decremented:
        decrement rightmost node
        if there are less than n nodes:
            push new node
        else if valid tree:
            print
    else:
        backtrack (pop)

```

Note that sometimes a value is stored or initialized as one or two greater than the actual (conceptual) value and adjusted as needed.

# Answer
> 3 votes
## Python 3 (138 134 128 121 119 bytes)

```
from itertools import*
lambda n:[any(sum(t[:k])<0for k in range(n))|sum(t)or print(t)for t in product(*[[-1,0,1]]*~-n)]

```

Example output, for `n=5`:

```
(0, 0, 0, 0)
(0, 0, 1, -1)
(0, 1, -1, 0)
(0, 1, 0, -1)
(1, -1, 0, 0)
(1, -1, 1, -1)
(1, 0, -1, 0)
(1, 0, 0, -1)
(1, 1, -1, -1)

```

1 represents a binary node, 0 represents a unary node, and -1 represents a terminal node. There is an implied terminal node at the end of every tree.

The program starts taking too long at around `n=17`.

# Answer
> 3 votes
## JavaScript (Firefox 30-57), 79 bytes

```
f=(m,l=0)=>m?[for(n of[1,0,-1])if(l>n&l<=m+n)for(a of f(m-1,l-n))[...a,n]]:[[]]

```

Where `-1` represents a terminal, `0` a unary node and `1` a binary node. Starts getting slow at `m=14` on my PC. Recursively works back from the end of the tree.

* The number of unaccounted-for nodes `l` is limited by the fact that there may only be 1 node left at the end.
* The type of the next node `n` is limited by the need to have enough unaccounted-for nodes to be its children.

# Answer
> 2 votes
## Prolog, 149 144 138 137 131 107 bytes

```
e(L,L)-->[0].

e([_|A],L)-->
    [1],
    e(A,L).

e([_,_|A],L)-->
    [2],
    e(A,B),
    e(B,L).

e(M,E):-
    length([_|L],M),
    e(L,[],E,[]).

?- e(5,S).
S = [1, 1, 1, 1, 0] ;
S = [1, 1, 2, 0, 0] ;
S = [1, 2, 0, 1, 0] ;
S = [1, 2, 1, 0, 0] ;
S = [2, 0, 1, 1, 0] ;
S = [2, 0, 2, 0, 0] ;
S = [2, 1, 0, 1, 0] ;
S = [2, 1, 1, 0, 0] ;
S = [2, 2, 0, 0, 0].

```

And to count the solutions

```
e_count(N,Count) :-
    length([_|Ls], N),
    findall(., phrase(e(Ls,[]),E), Sols),
    length(Sols, Count).

?- e_count(N,Count).
N = Count, Count = 1 ;
N = 2, Count = 1 ;
N = 3, Count = 2 ;
N = Count, Count = 4 ;
N = 5, Count = 9 ;
N = 6, Count = 21 ;
N = 7, Count = 51 ;
N = 8, Count = 127 ;
N = 9, Count = 323 ;
N = 10, Count = 835 ;
N = 11, Count = 2188 ;
N = 12, Count = 5798 ;
N = 13, Count = 15511 ;
N = 14, Count = 41835 ;
N = 15, Count = 113634

```

# Answer
> 1 votes
## Python, 71 bytes

```
f=lambda n:{(a+b,)for k in range(n)for a in f(k)for b in f(n+~k)}or[()]

```

This represents trees as nested tuples such as `((((),), ()),)`, which can be transformed into `((())())` by removing commas, spaces, and the outermost `()`.

An earlier 76-byte version:

```
f=lambda n:{'('+a+b+')'for k in range(n)for a in f(k)for b in f(n+~k)}or['']

```

# Answer
> 1 votes
## CJam, 38 bytes

Uses a different approach that Peter Taylor's CJam answer.

```
3rim*{:(1\+[{1$+}*])\:(_:z#|!},

```

Output will be something like `1110120020102100`. Each tree is a group of `n` digits (where `n` is the input number).

The basic idea is that we generate each possible string of digits `0`, `1`, and `2`, and then filter only the ones that are well-formed trees.

---
Tags: code-golf, graph-theory, binary-tree
---


title: Subsequence Substitution

text:
# Question
Title: Subsequence Substitution
Most languages come with a built-in to search a string for all occurrences of a given substring and replace those with another. I don't know of any language that generalises this concept to (not necessarily contiguous) subsequences. So that's your task in this challenge.

The input will consist of three strings `A`, `B` and `C`, where `B` and `C` are guaranteed to be of the same length. If `B` appears as a subsequence in `A` it should be replaced with `C`. Here is a simple example:

```
A: abcdefghijklmnopqrstuvwxyz
B: ghost
C: 12345

```

It would be processed like this:

```
abcdefghijklmnopqrstuvwxyz
      ||      |   ||
abcdef12ijklmn3pqr45uvwxyz

```

If there are several ways to find `B` as a subsequence, you should greedily replace the left-most one:

```
A: abcdeedcba
B: ada
C: BOB

Result:   BbcOeedcbB
and NOT:  BbcdeeOcbB

```

The same applies if `B` could be found in multiple disjoint places:

```
A: abcdeedcbaabcde
B: ed
C: 12

Result:   abcd1e2cbaabcde
and NOT:  abcd112cbaabc2e (or similar)

```

When `B` does not appear in `A`, you should output `A` unchanged.

## Rules

As stated above, take three strings `A`, `B` and `C` as input and replace the left-most occurrence of `B` as a subsequence in `A` with `C`, if there is any.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You may take the three strings in any consistent order which you should specify in your answer. You may assume that `B` and `C` have the same length. All strings will only contain alphanumeric characters.

Standard rules apply.

## Test Cases

Each test case is four lines: `A`, `B`, `C` followed by the result.

```
abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz

abcdeedcba
ada
BOB
BbcOeedcbB

abcdeedcbaabcde
ed
12
abcd1e2cbaabcde

121
121
aBc
aBc

abcde
acb
123
abcde

ABC
ABCD
1234
ABC

012345678901234567890123456789
42
TT
0123T5678901T34567890123456789

edcbaedcbaedcbaedcba
abcde
12345
edcbaedcbaedcbaedcba

edcbaedcbaedcbaedcbaedcba
abcde
12345
edcb1edc2aed3bae4cba5dcba

daccdedca
ace
cra
dcrcdadca

aacbcbabcccaabcbabcaabbbbca
abaaaccbac
1223334444
aacbcbabcccaabcbabcaabbbbca

aacbcbabcccaabcbabcaabbbbcac
abaaaccbac
1223334444
1ac2cb2bccc33b3bab4aa4bbbc44

```

## Leaderboard

The Stack Snippet at the bottom of this post generates leaderboards from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the snippet:

```
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
/* Configuration */

var QUESTION_ID = 77719; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 8478; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "http://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();

    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
```

```
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
```

# Answer
> 3 votes
# Jelly, ~~23~~ ~~22~~ 21 bytes

```
='T€ŒpfṢ€$ḢṬœp³ż⁵$³Ḋ?

```

Try it online! Note that the last two test cases will run out of memory.

### Verification

```
$ head -n 5 test-cases
abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz

$ cat subseq-short
while read s; do
        read p; read r; read o; echo $o; read
        timeout 1s jelly eun $1 "='T€ŒpfṢ€$ḢṬœp³ż⁵$³Ḋ?" "'$s'" "'$p'" "'$r'"
        (($?)) && echo '(killed)'
done < test-cases
$ ./subseq-short
abcdef12ijklmn3pqr45uvwxyz
abcdef12ijklmn3pqr45uvwxyz
BbcOeedcbB
BbcOeedcbB
abcd1e2cbaabcde
abcd1e2cbaabcde
aBc
aBc
abcde
abcde
ABC
ABC
0123T5678901T34567890123456789
0123T5678901T34567890123456789
edcbaedcbaedcbaedcba
edcbaedcbaedcbaedcba
edcb1edc2aed3bae4cba5dcba
edcb1edc2aed3bae4cba5dcba
dcrcdadca
dcrcdadca
aacbcbabcccaabcbabcaabbbbca
(killed)
1ac2cb2bccc33b3bab4aa4bbbc44
(killed)

```

### How it works

```
='T€ŒpfṢ€$ḢṬœp³ż⁵$³Ḋ?  Main link. Arguments: string s, pattern p, replacement r

='                     Compare each character of s with each character of p.
                       This yields a 2D list. Each row corresponds to a char in p.
  T€                   Compute the truthy indices of each row, i.e., the indices
                       of all occurrences of that char in s.
   Œp                  Compute the Cartesian product of the lists of indices.
        $              Combine the two links to the left into a monadic chain:
      Ṣ€                 Sort each list of indices.
     f                   Filter, removing all non-sorted lists of indices.
         Ḣ             Head; take the first (sorted) list of indices.
          Ṭ            Truth; generate a list with 1's at those indices.
           œp³         Partition; split s at all 1's, removing those characters.
                  Ḋ?   If the partition has more than more than one element:
              ż⁵$        Zip the partition with r.
                 ³       Else, return s.

```

# Answer
> 12 votes
## Python 2, 88 bytes

```
def f(a,b,c,o=""):
 for q in a:x=q==b[:1];o+=c[:x]or q;b=b[x:];c=c[x:]
 print[o,a][c>'']

```

A function that takes in the three strings and outputs the result to STDOUT. The function simply does one pass over the string, taking the appropriate char and updating `b,c` as we go.

For testing (after replacing the `print` with `return`):

```
S = """
<test cases here>
"""

for T in S.split("\n\n"):
    A,B,C,D = T.split()
    assert f(A,B,C) == D

```

# Answer
> 9 votes
## Java 7, 141

I think there's some more I can do with this, but I've gotta run for now. It's just a simple iterate/replace, keeping an index in A and B.

```
char[]h(char[]a,char[]b,char[]c){char[]d=a.clone();int i=0,j=0,k=b.length;for(;i<a.length&j<k;i++)if(a[i]==b[j])d[i]=c[j++];return j==k?d:a;}

```

Whitespaced for your pleasure:

```
char[]h(char[]a,char[]b,char[]c){
    char[]d=a.clone();
    int i=0,j=0,k=b.length;
    for(;i<a.length&j<k;i++)
        if(a[i]==b[j])d[i]=c[j++];
    return j==k?d:a;
}

```

# Answer
> 7 votes
## Lua, 121 Bytes

Straightforward solution, `gsub` allows us to iterate exactly once on each character and to replace them in a new instance of the string.

It takes input via 3 command-line argument and output a string to STDOUT.

```
a,b,c=...d=a:gsub(".",function(s)if b:find(s)then b=b:sub(2)x=c:sub(1,1)c=c:sub(2)return x end end)print(b~=''and a or d)

```

### Ungolfed

```
a,b,c=...               -- unpack the arguments into a, b and c
d=a:gsub(".",function(s)-- iterate over each character of the first argument
  if b:find(s)then      -- if the current character is in the set b
    b=b:sub(2)          -- remove it from b
    x=c:sub(1,1)        -- save the replacement character in x
    c=c:sub(2)          -- remove it from c
    return x            -- replace the current character with x
  end
end)
print(b~=''             -- if b is empty, we replaced all the character
      and a or d)       -- so output the result of gsub, else, output the first argument

```

# Answer
> 6 votes
# Python 3, 127 bytes.

Saved 16 bytes thanks to Katenkyo.

Still working on this a bit, man was this nastier than I thought it would be.

```
f=lambda a,b,c:a.replace(b[0],c[0],1)[:a.index(b[0])+1]+f(a[a.index(b[0])+1:],b[1:],c[1:])if b and all(x in a for x in b)else a

```

Explanation: Awww yeah, recursion.

Test cases:

```
assert f('abcdeedcba', 'ada', 'BOB') == 'BbcOeedcbB'
assert f('abcdeedcbaabcde', 'ed', '12') == 'abcd1e2cbaabcde'
assert f('012345678901234567890123456789', '42', 'TT') == '0123T5678901T34567890123456789'
assert f('ABC', 'ABCD', '1234') == 'ABC'

```

# Answer
> 5 votes
# Python 3.5, 87 bytes

```
import re
lambda s,p,r:re.sub('(.*?)'.join(p),'\g<%d>'.join(r)%(*range(1,len(r)),),s,1)

```

repl.it to verify all test cases.

### How it works

* `'(.*?)'.join(p)` builds a search pattern that matches the subsequence to be replaced and anything between its elements.

Since the quantifiers are lazy, each `(.*?)` will match as few characters as possible.

For the pattern `ghost`, the constructed regex is `g(.*?)h(.*?)o(.*?)s(.*?)t`.
* `'\g<%d>'.join(r)%(*range(1,len(r)),)` builds the replacement string, using string formatting.

Each `\g<n>` refers to the **n**th captured group, just like `\n` would.

For the replacement `12345`, the constructed string is `1\g<1>2\g<2>3\g<3>4\g<4>5`.
* `re.sub(...,...,s,1)` performs at most one replacement in the string `s`.

# Answer
> 4 votes
# Pyth, 27

```
.xuXG.*HC,hSI#.nM*FxRcQ1zwQ

```

Test Suite

The test suite omits the last two cases because they will run out of memory. The algorithm used here is to find all of the indices of each character in the second string in the first string, then find all possible orderings of those indices and take only the ones that are in sorted order. Then use the first one of these in sorted order as the list of indices in the first string to update with values from the third string.

I feel like there should be something shorter than `.nM*F`...

# Answer
> 4 votes
# MATL, 33 bytes

```
y!=[]0b"@n:!<@*fX<h5Mt?}.]]?iw(}x

```

**Try it online!**

### Explanation

```
y!      % Implicitly input first two strings. Duplicate the first and transpose
=       % Compare the two strings element-wise. Gives a 2D array with all combinations
[]      % Push empty array. Indices of matching elements will be appended to this
0       % Push a 0. This is the index of last character used up in first string
b       % Bubble up (rearrange elements in stack) to move 2D array to top
"       % For each column of that array (each char of the second string)
  @     %   Push current column
  n:!   %   Transform into column array of consecutive values starting from 1
  <     %   Compare with index of last character used up of first string
  @*    %   Push current column again. Multiply element-wise (logical AND)
  fX<   %   Find index of first matching character, or empty if there's none
  h     %   Append to array containing indices of matching elements
  5Mt   %   Push index of matching character again. Duplicate
  ?}    %   If it's empty
    .   %     Break loop
  ]     %   End if
]       % End for
        % The top of the stack now contains a copy of the index of last matching
        % character, or an empty array if there was no match
?       % If non-empty: all characters were matched
  i     %   Input third string
  w     %   Swap top two elements in stack
  (     %   Assign the characters of the third string to first string at found indices
}       % Else: the original string needs to be output
  x     %   Delete (partial) array of matching indices. Leave original string in stack
        % End if
        % Implicitly display (either modified string or original string)

```

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

```
(a,b,c)=>[...b].every((q,i)=>r[p=a.indexOf(q,p)]=~p++&&c[i],p=0,r=[...a])?r.join``:a

```

## Explanation / Test

```
var solution =

(a,b,c)=>
  [...b].every((q,i)=>
    r[p=a.indexOf(q,p)]=~p++&&c[i],
    p=0,
    r=[...a]
  )?r.join``
  :a

// Test
var testCases = `abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz

abcdeedcba
ada
BOB
BbcOeedcbB

abcdeedcbaabcde
ed
12
abcd1e2cbaabcde

121
121
aBc
aBc

abcde
acb
123
abcde

ABC
ABCD
1234
ABC

012345678901234567890123456789
42
TT
0123T5678901T34567890123456789

edcbaedcbaedcbaedcba
abcde
12345
edcbaedcbaedcbaedcba

edcbaedcbaedcbaedcbaedcba
abcde
12345
edcb1edc2aed3bae4cba5dcba

daccdedca
ace
cra
dcrcdadca

aacbcbabcccaabcbabcaabbbbca
abaaaccbac
1223334444
aacbcbabcccaabcbabcaabbbbca

aacbcbabcccaabcbabcaabbbbcac
abaaaccbac
1223334444
1ac2cb2bccc33b3bab4aa4bbbc44`
.split`\n\n`.map(c=>c.split`\n`);
document.write("<pre>"+testCases.map(c=>(r=solution(c[0],c[1],c[2]))+" : "+(r==c[3]?"PASS":"FAIL")).join`\n`);
```

# Answer
> 3 votes
## JavaScript (ES6), ~~84~~ 76 bytes

```
(a,b,c)=>a.replace(RegExp([...b].join`(.*?)`),c.replace(/\B/g,(_,i)=>'$'+i))

```

Because I was sure that this was a job for RegExp.

Edit: Saved 8 bytes thanks to @MartinBüttner♦.

A port of @KevinLau's Ruby answer took 82 bytes:

```
([...a],[...b],[...c])=>(d=a.map(e=>e==b[0]?c.shift(b.shift()):e),b[0]?a:d).join``

```

I also tried a recursive RegExp solution but that took 90 bytes:

```
f=(a,[b,...d],[c,...e])=>b?a.replace(RegExp(b+'(.*'+d.join`.*`+'.*)'),(_,s)=>c+f(s,d,e)):a

```

# Answer
> 3 votes
## Julia, ~~89~~ 70 bytes

```
f(s,a,b,i=0)=(o=join(["$a "[i+1]!=c?c:b[i+=1]for c=s]);i<endof(a)?s:o)

```

Uses an index `i` to iterate through the pattern/replacement strings as we go. -19 bytes thanks to @Dennis!

# Answer
> 2 votes
# C, 98 bytes

```
char*f(i,o,s,r)char*i,*o,*s,*r;{char*I=i,*O=o;for(;*i;++i,++o)*o=*i==*s?++s,*r++:*i;return*s?I:O;}

```

# /\* Expanded code \*/

```
char *f(i, o, s, r)
    char *i, *o, *s, *r;
{
    char *I=i, *O=o;
    for (;  *i;  ++i,++o)
        *o = (*i==*s) ? (++s,*r++) : *i;
    return *s ? I : O;
}

```

Arguments are: **i**nput string, **o**utput buffer, **s**earch string, **r**eplacement.

After remembering the start of input and output, we walk the input, replacing and advancing the substitution whenever we hit one. At the end, if we've run out of substitutions, return the output buffer, else the unmodified input.

## /\* Tests \*/

```
struct T
{
    const char *input;
    const char *search;
    const char *replace;
    const char *expected;
};

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    int i;
    static const struct T test[] = {
        { "abcdefghijklmnopqrstuvwxyz",
          "ghost",
          "12345",
          "abcdef12ijklmn3pqr45uvwxyz"},
        { "abcdeedcba",
          "ada",
          "BOB",
          "BbcOeedcbB"},
        { "abcdeedcbaabcde",
          "ed",
          "12",
          "abcd1e2cbaabcde"},
        { "121",
          "121",
          "aBc",
          "aBc"},
        { "abcde",
          "acb",
          "123",
          "abcde"},
        { "ABC",
          "ABCD",
          "1234",
          "ABC"},
        { "012345678901234567890123456789",
          "42",
          "TT",
          "0123T5678901T34567890123456789"},
        { "edcbaedcbaedcbaedcba",
          "abcde",
          "12345",
          "edcbaedcbaedcbaedcba"},
        { "edcbaedcbaedcbaedcbaedcba",
          "abcde",
          "12345",
          "edcb1edc2aed3bae4cba5dcba"},
        { "daccdedca",
          "ace",
          "cra",
          "dcrcdadca"},
        { "aacbcbabcccaabcbabcaabbbbca",
          "abaaaccbac",
          "1223334444",
          "aacbcbabcccaabcbabcaabbbbca"},
        { "aacbcbabcccaabcbabcaabbbbcac",
          "abaaaccbac",
          "1223334444",
          "1ac2cb2bccc33b3bab4aa4bbbc44"
        }
    };

    for (i = 0;  i < (sizeof test) / (sizeof test[0]);  ++i) {
        const struct T *t = test+i;
        char *out = malloc(strlen(t->input)+1);
        char *result = f(t->input, out, t->search, t->replace);
        if (strcmp(t->expected, result))
            printf("Failed test %d; result = \"%s\"\n", i, result);
    }
    return EXIT_SUCCESS;
}

```

# Answer
> 2 votes
# R, 76 bytes

```
function(a,b,c){s=substr;for(x in 1:nchar(b)){a=sub(s(b,x,x),s(c,x,x),a)};a}

```

uses `sub` to replace first match

Ungolfed

```
function(a,b,c){                    # function with 3 arguments as per description
  s=substr;                         # alias for substr (saves 1 byte)
   for(x in 1:nchar(b)){            # index 1 to number character in b
     a=sub(s(b,x,x),s(c,x,x),a)};   # replace first instance of b[x] in a
                                    # with c[x] and reassign to a
 a}                                 # return a

```

# Answer
> 2 votes
## C++, 204 bytes

### Golfed

```
#include<iostream>
#include<string>
int main(){std::string a, b, c;std::cin>>a>>b>>c;int t=0;for(int x=0;x<b.length();x++){t=a.find(b[x],t);if(t!=-1){a.replace(t,1,c.substr(x,1));}}std::cout<<a;return 0;}

```

### Ungolfed

```
#include<iostream>
#include<string>

int main()
{
    std::string a, b, c;
    std::cin>>a>>b>>c;
    int t = 0;
    for (int x=0;x<b.length();x++) {
        t = a.find(b[x], t);
        if (t != -1) {
            a.replace(t,1,c.substr(x, 1));
        }
    }
    std::cout<<a;
    return 0;
}

```

# Answer
> 2 votes
## Retina, 63 bytes

```
.+$
$&¶;$&
+`^(.)(.*¶)(.)([^;]+);(.*?)\1
$2$4$5$3;
A1`
;

G2=`.

```

Input is taken in order `B`, `C`, `A`, separated by linefeeds.

Try it online.

# Answer
> 2 votes
## JavaScript (ES6), ~~100~~ 95 bytes

```
(a,b,c)=>1?(t=[...a].map(e=>b[0]==e?(u=c[0],b=b.slice(1),c=c.slice(1),u):e).join``,b==""?t:a):a

```

This is a valid JavaScript Lambda function. Outputs as function `return`. Takes in three arguments (`a,b,c`). Add `f=` at the beginning and invoke like `f(arg1,arg2,arg3)`.

```
f=(a,b,c)=>1?(t=[...a].map(e=>b[0]==e?(u=c[0],b=b.slice(1),c=c.slice(1),u):e).join``,b==""?t:a):a

console.log(f(prompt("Value for A"),prompt("Value for B"),prompt("Value for C")))
```

# Answer
> 2 votes
# Haskell, 87 bytes

```
x@((a,b):c)#(d:e)|a==d,([],z)<-c#e=([],b:z)|0<1=(d:)<$>x#e
x#y=(x,y)
a!b=snd.(zip a b#)

```

I noticed the lack of a Haskell answer, and decided to fix that. This defines a ternary function `!` with argument order pattern-replacement-string. Try it here.

## Explanation

The auxiliary function `#` takes a list `x` of character pairs (pattern and replacement) and a string `y`. If the "pattern" characters in `x` form a subsequence of `y`, it returns the empty list and `y` with each pattern character replaced by its counterpart. Otherwise, it returns the pair `(x,y)`. The function `!` zips the pattern and replacement strings into `x`, applies `#` to `x` and the third string, and returns the second component of the result.

```
x@((a,b):c)#(d:e)  -- First case of #: both arguments nonempty.
  |a==d,           -- If the pattern char matches the string's head,
   ([],z)<-c#e     -- and the pattern's tail is a subsequence of the string's tail,
  =([],b:z)        -- tack the replacement char to the recursion result.
  |0<1             -- Otherwise,
  =(d:)<$>x#e      -- recurse with the same pairs and tack string's head to result.
x#y=(x,y)          -- If either argument is empty, just pair them.

```

If the pattern is a subsequence of the string, the code runs in **O(n)** time, making one recursive pass through the string and greedily constructing the replacement in the process. However, if the pattern is not a subsequence, it runs in **O(2n)** time in the worst case. This is because at every position where the pattern and string have a matching character, the function calls itself to check whether the pattern is actually a subsequence, finds out it's not, and calls itself a second time to actually compute the result.

# Answer
> 2 votes
# C (gcc), ~~67~~ ~~62~~ ~~61~~ 59 bytes

```
f(s,a,b)char*s,*a,*b;{*s==*a?*s=*b++,a++:1;*a&&f(s+1,a,b);}

```

Try it online!

# Answer
> 1 votes
# Octave, 97 bytes

```
function A=U(A,B,C)t=0;for s=B if p=find(A(t+1:end)==s,1) D(t=p+t)=~0;else return;end;end;A(D)=C;

```

Iterate over the subsequence to replace; find first occurrence of first character, find next character in remaining string, repeat. The one interesting bit of this is:

```
D(t=p+t)=~0

D(     )      %// D is a logical mask of characters to replace in the input string
  t=p+t       %// t is the current end of D
              %// p is the location of the character to replace
              %// update t and use as index to grow D
        =~0   %// make it so, number 1

```

Since ideone is still not accepting functions with names other than '', I'll just leave a sample run here. Inputs are only shown for the first few test cases for brevity. `key` is the expected output, `ans` is the function output.

```
A = abcdefghijklmnopqrstuvwxyz
B = ghost
C = 12345
key = abcdef12ijklmn3pqr45uvwxyz
ans = abcdef12ijklmn3pqr45uvwxyz
A = abcdeedcba
B = ada
C = BOB
key = BbcOeedcbB
ans = BbcOeedcbB
A = abcdeedcbaabcde
B = ed
C = 12
key = abcd1e2cbaabcde
ans = abcd1e2cbaabcde
key = aBc
ans = aBc
key = abcde
ans = abcde
key = ABC
ans = ABC
key = 0123T5678901T34567890123456789
ans = 0123T5678901T34567890123456789
key = edcbaedcbaedcbaedcba
ans = edcbaedcbaedcbaedcba
key = edcb1edc2aed3bae4cba5dcba
ans = edcb1edc2aed3bae4cba5dcba
key = dcrcdadca
ans = dcrcdadca
key = aacbcbabcccaabcbabcaabbbbca
ans = aacbcbabcccaabcbabcaabbbbca
key = 1ac2cb2bccc33b3bab4aa4bbbc44
ans = 1ac2cb2bccc33b3bab4aa4bbbc44

```

# Answer
> 1 votes
# Ruby, ~~70~~ ~~64~~ ~~59~~ 58 bytes

Anonymous function. Walk through the string `a` to build a new string with letters replaced in accordance to the next character in `b` and `c`, then if all characters in `b` are exhausted at the end, return the newly constructed string, otherwise return the original string.

@histocrat helped save 6 bytes via `gsub`.

Saved 1 byte thanks to @Cyoce.

```
->a,b,c{i=0;s=a.gsub(/./){$&==b[i]?c[~-i+=1]:$&};b[i]?a:s}

```

Try it online!

# Answer
> 1 votes
# Python 3, 123 Bytes

A different approach I wanted to share, which is a few bytes shorter. There are no rules against standard library/regex, right?

```
import re
j=''.join
m='(.*?)'
def f(A,B,C):
 *r,l=(re.findall(m+m.join(B)+'(.*)',A)or[[A]])[0]
 print(j(map(j,zip(r,C)))+l)

```

PS. This is my first golf. Let me know of any issues/improvements.

# Answer
> 1 votes
# Pyth, 22 bytes

```
|eJ:Ej"(.*?)"+E\$3s.iJ

```

Verify all test cases in the Pyth Compiler.

### Background

We build a regex from the pattern by appending a `$` and placing `(.*?)` between all characters. This regex will match the subsequence to be replaced and anything between its elements, and anything up to the end of the string.

Since the quantifiers are lazy, each `(.*?)` will match as few characters as possible.

For the pattern ghost, the constructed regex is `g(.*?)h(.*?)o(.*?)s(.*?)t(.*?)$`.

If the pattern matches the input, the builtin `r<str><regex>3` will return an array containing the prematch (everything before the subsequence), all captured groups (everything in between and after the subsequence), and the postmatch (the empty string).

If the pattern does not match, the builtin will return a singleton array containing the original input.

### How it works

```
|eJ:Ej"(.*?)"+E\$3s.iJQ  (implicit) Store the first line of input in Q.

             +E\$        Read the third line of input (pattern) and append '$'.
     j"(.*?)"            Join the result, separating by "(.*?)".
    E                    Read the third line of input (string).
   :             3       Match the string against the regex, as detailed above.
  J                      Save the returned array in J.
 e                       Extract the last element of J. This is an empty string
                         for a successful match or the original string.
|                        Logical OR; replace an empty string with the following:
                   .iJQ    Interleave J and the replacement.
                  s        Flatten the resulting array of strings.

```

# Answer
> 1 votes
# Jelly, 23 bytes

```
Ṭœpż⁵
0ẋai1
⁴='-;ç\ñ⁴P?

```

This is two bytes longer than my other Jelly answer, but it finishes instantly. Try it online!

### Verification

```
$ head -n 5 test-cases
abcdefghijklmnopqrstuvwxyz
ghost
12345
abcdef12ijklmn3pqr45uvwxyz

$ cat subseq-fast
while read s; do
        read p; read r; read o; echo $o; read
        timeout 10s jelly eun $1 "Ṭœpż⁵¶0ẋai1¶⁴='-;ç\ñ⁴P?" "'$p'" "'$s'" "'$r'"
        (($?)) && echo '(killed)'
done < test-cases
$ ./subseq-fast
abcdef12ijklmn3pqr45uvwxyz
abcdef12ijklmn3pqr45uvwxyz
BbcOeedcbB
BbcOeedcbB
abcd1e2cbaabcde
abcd1e2cbaabcde
aBc
aBc
abcde
abcde
ABC
ABC
0123T5678901T34567890123456789
0123T5678901T34567890123456789
edcbaedcbaedcbaedcba
edcbaedcbaedcbaedcba
edcb1edc2aed3bae4cba5dcba
edcb1edc2aed3bae4cba5dcba
dcrcdadca
dcrcdadca
aacbcbabcccaabcbabcaabbbbca
aacbcbabcccaabcbabcaabbbbca
1ac2cb2bccc33b3bab4aa4bbbc44
1ac2cb2bccc33b3bab4aa4bbbc44

```

### How it works

```
⁴='-;ç\ñ⁴P?  Main link. Arguments: pattern p, string s, replacement r

⁴='          Compare each character of s with each character of p.
             This yields a 2D list. Each row corresponds to a char in p.
   -;        Prepend -1 to the 2D list, yielding a ragged array.
     ç\      Cumulatively reduce the array by the second helper link.
         P?  If the product of the resulting list is non-zero:
       ñ       Call the first helper link with the list and s as arguments.
        ⁴      Else, return s.

Ṭœpż⁵        First helper link. Arguments: L (list of indices), r (replacement)

Ṭ            Truth; generate a list with 1's at those indices.
 œp          Partition; split s at all 1's, removing those characters.
   ż⁵        Zip the partition with r.

0ẋai1        Second helper link. Arguments: n (integer), B (list of Booleans)

0ẋ           Generate a list of n zeroes.
  a          Perform logical AND with B.
             This zeroes out the with n elements of B.
   i1        Compute the first index of 1.

```

# Answer
> 1 votes
# Julia, ~~93~~ ~~90~~ 86 bytes

```
f(s,p,r)=(try s=join([match(Regex(join("^$p\$","(.*?)")),s).captures';[r...""]])end;s)

```

Having to test separately if the match was successful kinda destroys the score. A substitution would require casting to `Base.SubstitutionString`, which probably isn't worth it...

### Test run

```
julia> f(s,p,r)=(try s=join([match(Regex(join("^$p\$","(.*?)")),s).captures';[r...""]])end;s)
f (generic function with 1 method)

julia> f("aacbcbabcccaabcbabcaabbbbca","abaaaccbac","1223334444")
"aacbcbabcccaabcbabcaabbbbca"

julia> f("aacbcbabcccaabcbabcaabbbbcac","abaaaccbac","1223334444")
"1ac2cb2bccc33b3bab4aa4bbbc44"

```

# Answer
> 1 votes
# CJam, 29 bytes

```
l_ll.{2$#_3$<@+\)@>}s_2$,>@@?

```

Try it online! or verify all test cases.

# Answer
> 1 votes
# Java 7, 102 bytes

```
void L(char[]s,char[]l,char[]r){for(int x=0,y=0;x<s.length&&y<l.length;x++)if(s[x]==l[y])s[x]=r[y++];}

```

**Detailed** *try here*

```
// String, Lookup, Replacement
void L(char[]s, char[]l, char[]r)
{
    for(int x=0, y=0; x < s.length && y < l.length; x++)
        if(s[x] == l[y])
            s[x] = r[y++];
}

```

# Answer
> 1 votes
# Julia, ~~62~~ ~~59~~ 58 bytes

```
f(s,p,r)=(try s[[i=findnext(s,c,i+1)for c=p]'],i=r,0end;s)

```

I/O is in form of character arrays.

### Verification

```
julia> f(s,p,r)=(try s[[i=findnext(s,c,i+1)for c=p]'],i=r,0end;s)
f (generic function with 2 methods)

julia> F(s,p,r)=join(f([s...],[p...],[r...])) # string/char array conversion
F (generic function with 1 method)

julia> F("aacbcbabcccaabcbabcaabbbbca","abaaaccbac","1223334444")
"aacbcbabcccaabcbabcaabbbbca"

julia> F("aacbcbabcccaabcbabcaabbbbcac","abaaaccbac","1223334444")
"1ac2cb2bccc33b3bab4aa4bbbc44"

```

# Answer
> 1 votes
# PHP, ~~130~~ 109 bytes

I´d still like it shorter; could save 3 bytes (`""<`) if `B` was guaranteed to not contain `0`.

```
for($s=($a=$argv)[1];""<$c=$a[2][$i++];)if($p=strpos(_.$s,$c,$p+1))$s[$p-1]=$a[3][$k++];echo$k<$i-1?$a[1]:$s;

```

takes arguments from command line. Run with `-r`.

Replaces the characters when it finds them;
prints copy if all characters have been replaced; original else.

# Answer
> 0 votes
# Perl, 80 + 1 = 81 bytes

Run with the `-p` flag

```
$a=join"(.*?)",split//,<>;$b.=$_." .\$".++$;."."for split//,<>;chop$b;s/$a/$b/ee

```

Try it online!

The code procedurally generates a search and replace regex command, which it then executes in the last bit of code.

The string `ghost` in the first example gets turned into the string `g(.*?)h(.*?)o(.*?)s(.*?)t(.*?)`, which means a `g` followed by 0 or more characters, followed by an `h` followed by 0 or more characters, followed by etc. The `*?` quantifier means that the search should be non-greedy and "gobble" as few characters as possible, instead of the default of matching as much as possible.

The string `12345` then gets turned into `1 .$1.2 .$2.3 .$3.4 .$4.5 .$5`, which gets evaluated after the regex is performed. Each of `$1,$2,$3,$4,$5` is actually a backreference to a capture group (in parentheses) from the first string.

# Answer
> 0 votes
## Clojure, 113 bytes

```
#(apply str((reduce(fn[[b c r]a](if(=(first b)a)[(rest b)(rest c)(conj r(first c))][b c(conj r a)]))[%2%3[]]%)2))

```

A basic `reduce`, not too happy about all those long `first`, `rest` and `conj` function calls. Hoping to see a better approach.

# Answer
> 0 votes
# Perl 5, 100 bytes

```
sub{($x,$y,$z)=@_;$y[$n++]=$_ for(split//,$z);$o=$x;$/&=$x=~s/$_/$y[$m++]/ for(split//,$y);$"?$o:$x}

```

This probably can be made shorter, but it's bed time now.

# Answer
> 0 votes
# PHP\>=7.1, 102 Bytes Non Competing

```
for([,$t,$s,$r]=$argv;a&$c=$s[$i];$y.=$r[$i]."$".++$i)$x.="$c(.*?)";echo preg_replace("#$x#",$y,$t,1);

```

Online Version

replace `[,$t,$s,$r]` with `list(,$t,$s,$r)` to use it in former PHP versions +4 Bytes

Expanded

```
for([,$t,$s,$r]=$argv;a&$c=$s[$i];
$y.=$r[$i]."$".++$i) # make replacement in after loop
  $x.="$c(.*?)"; # make search regex
echo preg_replace("#$x#",$y,$t,1); # replace 1 Time and Output

```

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


title: Where did Jill end up?

text:
# Question
Title: Where did Jill end up?
Jill lives in the (magnetic) north pole. One day, Jill decided to go for a walk, travelling in the four directions (north, east, west, south) for some lengths, with the help of a compass. Your task is to find whether Jill ended up where Jill lives, i.e. the magnetic north pole.

Only south is defined at the north pole. Walking north or south changes the latitude, while walking east or west changes the longitude. The longitude is not defined at the north pole. As a result, Jill would have ended up at the north pole if and only if the distances Jill walked to the south sum up to be equal to the sum of the distances Jill walked to the north, and the distance Jill walked east and west do not matter.

# Input

A list of pairs of (direction, amount). The input shall be valid. The amounts will be integers. Acceptable formats include:

* `"N200"`
* `"200N"`
* `200i` (complex number)
* `(0, 200)` (0123 for NESW)
* `(200,0)` (the above reversed)

# Output

Two consistent values, one for the case that Jill did end up in the magnetic north pole, and one for the case that Jill did not.

# Testcases

Truthy inputs:

```
S100, E50, N50, W50, N50
S10, E1000, S30, W400, S10, W10, N50
S30, N30
S10, E50, E50, N10

```

Falsey inputs:

```
S100
S10, E314, N5
S300, W135, S10, E35, N290

```

# Scoring

This is . Shortest answer in bytes wins. Standard loopholes apply.

# Answer
> 5 votes
# Jelly, 3 bytes

```
SĊṆ

```

Input is in form of complex numbers, which will be real or purely imaginary.

Try it online!

### How it works

```
SĊṆ  Main link. Argument: A (array of directions)

S    Take the sum of A.
 Ċ   Get the imaginary part of the sum.
  Ṇ  Take the logical NOT of the imaginary part.

```

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

Takes input as an array of *\[orientation, distance\]* arrays, with *0123* = *NESW*. Returns a boolean.

```
a=>!a.reduce((p,[o,d])=>p+--o%2*d,0)

```

The result of the modulo in JS has the same sign as the dividend:

* ***(0 - 1) % 2 == -1*** (north)
* ***(2 - 1) % 2 == 1*** (south)

***.map()* alternative, 36 bytes**

```
a=>a.map(([o,d])=>a=~~a+--o%2*d)&&!a

```

### Test cases

```
let f =

a=>!a.reduce((p,[o,d])=>p+--o%2*d,0)

// truthy
console.log(f([[2,100], [1,50], [0,50], [3,50], [0,50]]))
console.log(f([[2,10], [1,1000], [2,30], [3,400], [2,10], [0,50]]))
console.log(f([[2,30], [0,30]]))
console.log(f([[2,10], [1,50], [1,50], [0,10]]))

// falsy
console.log(f([[2,100]]))
console.log(f([[2,10], [1,314], [0,5]]))
console.log(f([[2,300], [3,135], [2,10], [1,35], [0,290]]))
```

# Answer
> 1 votes
## Batch, 78 bytes

```
@set l=0
@for %%s in (%*)do @set t=%%s&call set/al+=%%t:i=*0%%
@cmd/cset/a!l

```

Takes input as command-line arguments in complex format (e.g. `-100 50i 50 -50i 50`). Outputs `1` if Jill arrives back at the pole, `0` if not.

# Answer
> 1 votes
# Pyth, 3 bytes

```
!es

```

Input as a list of complex numbers.

Try it online!

```
!es
  s  # Sum
 e   # Imaginary part
!    # Not

```

# Answer
> 0 votes
# Mathematica, 10 bytes

```
1>Im@Tr@#&

```

Pure function taking a list of complex numbers (same format, and implementation, as Dennis's Jelly answer). `1>` saves a byte over `0==`, and is valid thanks to the facts that distances will always be integers and you can't go north from the north pole.

# Answer
> 0 votes
# Java 7, 135 bytes

```
boolean c(String[]a){int n=0,s=0,c,i;for(String x:a){c=x.charAt(0);i=new Short(x.substring(1));n+=c==78?i:0;s+=c==83?i:0;}return n==s;}

```

Those restricted input-format are pretty annoying, but I guess that was the main part of the challenge..

**Explanation:**

```
boolean c(String[]a){             // Method with String-array parameter and boolean return-type
  int n=0,                        //  North-sum
      s=0,                        //  South-sum
      c,i;                        //  Two temp integers to save bytes
  for(String x:a){                //  Loop over the input-array
    c=x.charAt(0);                //   Set `c` to the first character
    i=new Short(x.substring(1));  //   Set `i` to the actual number
    n+=c==78?i:0;                 //   If `c` == 'N': increase the North-sum with `i`
    s+=c==83?i:0;                 //   If `c` == 'S': increase the South-sum with `i`
  }                               //  End of loop
  return n==s;                    //  Return if the North- and South-sums are equal
}                                 // End of method

```

**Test code:**

Try it here.

```
class M{
  static boolean c(String[]a){int n=0,s=0,c,i;for(String x:a){c=x.charAt(0);i=new Short(x.substring(1));n+=c==78?i:0;s+=c==83?i:0;}return n==s;}

  public static void main(String[] a){
    System.out.println(c(new String[]{ "S100", "E50", "N50", "W50", "N50" }));
    System.out.println(c(new String[]{ "S10", "E1000", "S30", "W400", "S10", "W10", "N50" }));
    System.out.println(c(new String[]{ "S30", "N30" }));
    System.out.println(c(new String[]{ "S10", "E50", "E50", "N10" }));
    System.out.println(c(new String[]{ "S100" }));
    System.out.println(c(new String[]{ "S10", "E314", "N5" }));
    System.out.println(c(new String[]{ "S300", "W135", "S10", "E35", "N290" }));
  }
}

```

**Output:**

```
true
true
true
true
false
false
false

```

# Answer
> 0 votes
**Microsoft Sql Server, 94 bytes**

```
select sign(sum(iif(m like'[NS]%',stuff(m,1,1,iif(m like'S%','-','')),0)))+1 from a group by g

```

Check it.

# Answer
> 0 votes
# Python, 23 bytes

```
lambda s:sum(s).imag==0

```

Input as a list of complex numbers.

---
Tags: code-golf, math
---


title: Find the coterminal angle on [0, 2π)

text:
# Question
Title: Find the coterminal angle on [0, 2π)
This challenge is very simple:

Given an angle measure in degrees or radians (your choice), output the angle between 0 and 2π non-inclusive \[0º, 360º) that is coterminal with it.

## Input

A positive or negative angle measure. You can pick if you want to take it in degrees or in radians.

## Output

The angle on \[0, 2π) that is coterminal with the input angle. If you take the input in degrees, the output must also be in degrees; if you take it in radians, the output must be in radians too. The coterminal angle is essentially a the angle mod 360°.

## Examples (in degrees)

```
745 -> 25
1728 -> 288
90 -> 90
0 -> 0
360 -> 0
-50 -> 310
-543.21 -> 176.79

```

# Answer
> 2 votes
# 05AB1E, 4 bytes

```
360%

```

Try it online!

```
360  # push 360
   % # pop a,b: push (a % b)

```

# Answer
> 5 votes
# Python 3, 14 bytes

```
lambda n:n%360

```

Try it online!

# Answer
> 4 votes
# R, 11 bytes

takes input from stdin in degrees

```
scan()%%360

```

Try it online!

# Answer
> 4 votes
# MATL, ~~5~~ 4 bytes

```
360\

```

Try it online!

My first attempt with MATL!

*-1 byte, just realised `i` is not necessary for recording the input...*

# Answer
> 4 votes
# Python 3, 13 bytes

```
360..__rmod__

```

Explanation: `num.__rmod__(x)` is equivalent to `x%num` (rmod is modulo from the right.).

# Answer
> 4 votes
# 05AB1E, 4 bytes

Just because there were no answers using radians.

```
žq·%

```

Try it online!

# Answer
> 3 votes
# CJam, 12 bytes

```
rd360:X%X+X%

```

All those extra bytes because CJam gives negative results for mods...

Try it online!

# Answer
> 2 votes
# Jelly, 4 bytes

```
%360

```

**Try it online!**

I was kind of hoping `Æ°°` would do it for 3.

# Answer
> 2 votes
# Java 7, ~~44~~ 43 bytes

Crossed out 44 is still regular 44 ;(

```
float c(float n){return(n%=360)<0?n+360:n;}

```

**Explanation:**

Java uses remainder instead of actual modulo for negative numbers (source). So we'll have to manually fix the negative cases.

```
float c(float n){    // Method with float input and float return-type
  return(n%=360)<0?  //  If input mod-360 is negative
   n+360             //   Return input mod-360 + 360
  :                  //  Else:
   n;                //   Return input mod-360
}                    // End of method

```

**Test code:**

Try it here.

```
class M{
  static float c(float n){return(n%=360)<0?n+360:n;}

  public static void main(String[] a){
    System.out.print(c(745) + "; ");
    System.out.print(c(1728) + "; ");
    System.out.print(c(90) + "; ");
    System.out.print(c(0) + "; ");
    System.out.print(c(360) + "; ");
    System.out.print(c(-50) + "; ");
    System.out.print(c(-543.21f));
  }
}

```

**Output:**

```
25.0; 288.0; 90.0; 0.0; 0.0; 310.0; 176.78998

```

# Answer
> 2 votes
# Japt, ~~14 11 10~~ 4 bytes

```
u#Ũ

```

Try it online!

Takes input in degrees.

# Explanation

```
 u#Ũ
Uu360
U     # (implicit input)
 u    # modulo
  360 # 360
      # (implicit output)

```

# Answer
> 2 votes
# C, 69 43 bytes

This *seems* like an excessively trivial challenge, and indeed in many languages it is. The trick is in the implementation details of the modulo operator.

When both modulo operands are positive, nothing interesting happens. But when one of the operands is negative, then the results start depending on your interpretation of what should happen. You can either always return a positive result, return a result whose sign depends on the dividend, or return a result whose sign depends on the divisor.

Programming languages are quite divided on which behavior they choose to implement. The lucky ones for this challenge are the ones that always return a positive result, since that's what the test cases call for.

If you happen to be golfing in a language that implements modulo dependent on the sign of the dividend, then you have to do extra work to compensate for negative inputs—and to make sure that this compensation does not break positive inputs!

Here's a further golfed implementation in C (thanks to ais523):

```
f(double*n){*n=fmod(fmod(*n,360)+360,360);}

```

Try it online!

Notice that C is also hobbled here by the unfortunate omission of a modulo operator (*a la* `%`) for floating-point operations. Instead, you have to call a library function.

# Answer
> 1 votes
# JavaScript (ES6), ~~21~~ ~~19~~ 18 bytes

Takes input in degrees.

```
n=>(n%360+360)%360

```
* Saved 2 bytes thanks to Luke.
* Saved 1 byte thanks to Neil.

---

## Try it

```
f=
n=>(n%360+360)%360
i.addEventListener("input",_=>o.innerText=f(+i.value))
console.log(f(745)) // 25
console.log(f(1728)) // 288
console.log(f(90)) // 90
console.log(f(0)) // 0
console.log(f(360)) // 0
console.log(f(-50)) // 310
console.log(f(-543.21)) // 176.79
```

```
<input id=i type=number><pre id=o>
```

# Answer
> 1 votes
# Fourier, ~~22~~ ~~14~~ 6 bytes

```
I%360o

```

Try it online!

Simply outputs the input modulo 360.

Note that since the interpreter for TIO is written in Python, this will not work on http://beta-decay.github.io/editor

# Answer
> 1 votes
# Mathematica, 10 bytes

```
#~Mod~360&

```

Pure function taking any type of numerical input in degrees. Does what it says on the tin.

# Answer
> 1 votes
# x86 Assembly (targeting the x87 FPU), 23 bytes

As is standard with 32-bit calling conventions, the double-precision floating-point parameter is passed on the stack, and returned at the top of the x87 FPU stack. Assemble with MASM:

```
.MODEL flat
.686                              ; fucomip requires a Pentium Pro or later CPU

CONST SEGMENT
divisor  DD  043b40000r           ; 360.0f
CONST ENDS

PUBLIC _CoterminalAngle
_TEXT SEGMENT
_CoterminalAngle PROC
   fld      DWORD PTR [divisor]   ; single-precision takes fewer bytes to store; we don't need the precision
   fld      QWORD PTR [esp + 4]   ; load parameter from stack

   fprem                          ; st(0) = parameter % 360
                                  ; st(1) = 360

   fldz
   fucomip  st(0), st(1)          ; st(0) < 0?
   jbe      Finished
   fadd     st(0), st(1)          ; fixup negative modulo by adding 360
Finished:

    fstp    st(1)                 ; discard st(1); result is left in st(0)
    ret
_CoterminalAngle ENDP
_TEXT ENDS

END

```

To call from C:

```
extern double CoterminalAngle(double value);

```

In bytes:

```
43B40000

D9 05 00 00 00 00
DD 44 24 04
D9 F8
D9 EE
DF E9
76 02
D8 C1
DD D9
C3

```

**Notes:**

As the comment indicates, to minimize code size, I've stored the divisor constant (`360.0f`) as a single-precision floating-point value. This means it is half the length it would be if it were a double-precision value, and we don't need the precision to store a proper representation of the value. Upon loading, the x87 FPU will implicitly extend it to its native ten-byte extended-precision format.

We're also playing it fast-and-lose with the `FPREM` instruction for golfing purposes, assuming it does not need to reduce the exponent of the input value by more than 63. The *careful* (read: correct) way to call it would be iteratively, in a loop, continuing to execute it as long as the "parity" flag is set.
For example:

```
RemainderLoop:
   fprem
   fstsw  ax
   sahf
   jp     RemainderLoop

```

That would add 6 bytes to the total.

---

# x86 Assembly (targeting AVX), 47 bytes

By way of comparison (and for completeness), here's an AVX implementation. It's more bytes, but also more efficient. The parameter is passed in `XMM0`, and the result is returned in the same register, as with any x86-64 or vector x86-32 calling convention.

```
43 B4 00 00    | divisor  DD  043b40000r           ; 360.0f

```

```
               | ; Load single-precision FP value, and convert it to double-precision.
C5 EA 5A 15 00 | vcvtss2sd  xmm2, xmm2, DWORD PTR [divisor]
    00 00 00   |
               | ; Divide input parameter (XMM0) by divisor (XMM2), and store result in XMM1.
C5 FB 5E CA    | vdivsd     xmm1, xmm0, xmm2
               |
               | ; Truncate the result of the division to the nearest integer.
C5 FB 2C C1    | vcvttsd2si eax, xmm1
C5 F3 2A C8    | vcvtsi2sd  xmm1, xmm1, eax
               |
               | ; Multiply the truncated result by divisor (XMM2).
C5 F3 59 CA    | vmulsd     xmm1, xmm1, xmm2
               |
               | ; Subtract this temporary value (XMM1) from the original input (XMM0).
C5 FB 5C C1    | vsubsd     xmm0, xmm0, xmm1
               |
               | ; See if the result is negative.
C5 F1 57 C9    | vxorpd     xmm1, xmm1, xmm1   ; xmm1 = 0
C5 F9 2F C8    | vcomisd    xmm1, xmm0         ; result < 0?
76 04          | jbe        Finished
C5 FB 58 C2    | vaddsd     xmm0, xmm0, xmm2   ; fixup negative modulo by adding divisor (XMM2)
               |
               | Finished:
C3             | ret

```

Of course, it would be even more efficient to multiply by the reciprocal, instead of dividing. But that means more precision is required to store the divisor, and would thus slightly increase the size of the code.

# Answer
> 0 votes
# PHP, 29 Bytes

```
<?=($v=$argn%360)>=0?:$v+360;

```

# Answer
> 0 votes
## Python 2 REPL - 11 bytes

```
input()%360

```

If we've got a wierd input function, we might as well abuse it, right?

# Answer
> 0 votes
## Pyth - 5 bytes

```
%Q360

```

Would be shorter if `%360` meant `Q%360` instead of `360%Q`, but oh well...

---
Tags: code-golf, math, trigonometry
---


title: Can I Sp|Lit this wo|Rd?

text:
# Question
Title: Can I Sp|Lit this wo|Rd?
Note that this is similar to my other challenge, but it is widened to be similar to most challenges (input -\> truthy/falsey), instead of asking you all to brute force something. If this makes it a dupe, let me know, but I posted it on Sandbox and asked on chat, and didn't get any negative responses.

# Input

Input will be a "word" consisting of `a`-`z`, `A`-`Z`, `-`, and `'`. The case is important. Instead of my previous challenge, where you run through all permutations, in this challenge, you will be given a permutation. Your program's response on invalid input does not matter. Input can be taken in reasonable text input formats, and can contain a trailing newline if required.

# Output

Output will be a standard truthy/falsey values on if the permutation can be split in half. A permutation can be split in half if the width values (see below) of one half of the word equal the point values of the other half, or if the same is true if the middle word is removed. Trailing newlines allowed if required.

Please note that "half" does not mean that you have moved halfway into the string. "Half" means that the points on both sides are equal.

Examples:

`W` is 5 points. `i` is 1 point. Splitting the permutation `Wiiiii` in half will result in `W | iiiii`, with 5 points on each side of the `|`.

`T` is 3 points. Splitting the permutation `TTTT` in half will result in `TT | TT`, with 6 points on each side of the `|`.

`w` is 4 points. a is 3 points. Splitting the permutation `waw` in half will result in `w (a) w`, with 5.5 points on each side. The points from `a` are distributed to both sides, as `a` is split in half.

See the test cases for more clarification.

# Letter Scores

```
Width  Characters
1      i l I '
2      f j r t -
3      a b c d e g h k n o p q s u v x y z
4      m w A B C D E F G H J K L N O P Q R S T U V X Y Z
5      M W

```

# Test Cases

`( )` indicate that the permutation can be split if the character inside the parantheses is cut in half. `|` indicates that the permutation can be split in between those two letters.

Input : Output : Visualization

```
a : truthy : (a)
ab : truthy : a|b
Ab : falsey
AB : truthy : A|B
r- : truthy : r|-
iiiiw : truthy : iiii|w
iiiiiiW : truthy : iiiii(i)W
STEPHEN : truthy : STE(P)HEN
STEphen : truthy : STE|phen
STEpheN : falsey
splitwoRdS : truthy : splitw|oRdS

```

And here's a visualization for `splitwoRdS`:

```
s p l i t w | o R d S
3 3 1 1 2 4   3 4 3 4

```

# Answer
# Jelly, ~~52~~ 50 bytes

```
Œuðẇ⁾MW+=
ẇÐ€“fjrt“il-“I'”T_@Ç+3µ€Hx2FŒṖṖLÐṂS€E$€Ṁ

```

**Try it online!** (exceeds memory limitations on TIO for the "splitwoRdS" test case)

Although slower and more memory hungry than the below 50 byte alternative that borrows the reduction method from fireflame241's answer:

```
Œuðẇ⁾MW+=
ẇÐ€“fjrt“il-“I'”T_@Ç+3µ€Hx2F+\©ð_ø®ṪHµẠ¬

```

### How?

```
Œuðẇ⁾MW+= - Link 1, character index offset helper: character list c (of length one)
Œu        - to uppercase
  ð       - dyadic chain separation (call that u)
    ⁾MW   - char pair literal ['M', 'W']
   ẇ      - sublist exists in? (is u in there - True if c is 'm', 'w', 'M', or 'W')
        = - equal? (vectorised u=c? [1] for uppercase or non-alpha c, [0] for lowercase c)
       +  - add the two results (vectorises)

ẇÐ€“fjrt“il-“I'”T_@Ç+3µ€Hx2FŒṖṖLÐṂS€E$€Ṁ - Main link: character list w
                      µ€                 - for each c in w:
   “fjrt“il-“I'”                         -   list of character lists: ["fjrt","il-","I'"]
ẇÐ€                                      -   sublist (w) exists in, mapped across right
                T                        -   truthy indexes (gets [the index at which the character was found] or an empty list)
                   Ç                     -   call the last link (1) as a monad
                 _@                      -   subtract with reversed @rguments
                    +3                   -   add 3
                        H                - halve (vectorises)
                         x2              - times two (repeats each list)
                           F             - flatten into a single list
                            ŒṖ           - partitions (all ways to split the list into contiguous slices)
                              Ṗ          - pop (remove the right-most; the only one of length 1)
                                ÐṂ       - filter keep those with minimal:
                               L         -   length
                                     $€  - last two links as a monad for €ach
                                  S€     -   sum €ach
                                    E    -   all (two) equal? (1 for a split, 0 otherwise)
                                       Ṁ - maximum (1 if any split was possible, 0 otherwise)

```
> 3 votes

# Answer
# Jelly, 79 bytes

```
“¡-Ị’b26
“µııẈḟ(µ⁹\fy¦°Ẓ=ȮH@Q0Ẋƈẏ9Ė=ẹṬɗƇ’ðœ?øØa;ØA;⁾'-ð,ø5Rx¢
¢yHx2+\©ð_ø®ṪHµẠ¬

```

Try it online!
> 3 votes

# Answer
# Retina, 88 bytes

```
T`MWi\lI'`551
T`-fjrt`2
T`m\wL`4
T`l`3
\d
$*1
+`^ ?1(1* 1*( 1*)+)1 ?$
$1
^ ?(1+) \1? ?$

```

Try it online!
> 2 votes

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


title: Tell me my console dimensions!

text:
# Question
Title: Tell me my console dimensions!
Output terminal dimensions (columns and rows) in any two-number decimal format\*. For example, an output could be `80x25`.

---

Inspiration. Prompt.
* Output must have both measures on a single or two consecutive lines, and there may be no more than one leading and/or trailing line of output (optionally followed by a newline). The (up to four) lines must be no longer than max(cols,1+len(str(cols))+len(str(rows))).

# Answer
> 27 votes
# \*sh, 9

```
stty size

```

Output:

```
97 364

```

# Answer
> 20 votes
# 8086 machine code, 11 bytes (as a function, non-competing)

Not really competing since it doesn't have visible output. This is just showing the shortest way to find the current screen dimensions, without the boilerplate code required for printing.

```
00000000  6a 40 1f a0 84 00 40 8a  26 4a 00                 |j@....@.&J.|
0000000b

```

### How it works:

```
6a 40           |   push 0x40       ; bios data segment
1f              |   pop ds
a0 84 00        |   mov al, [0x84]  ; console rows - 1
40              |   inc ax
8a 26 4a 00     |   mov ah, [0x4a]  ; console columns

```

---

# 8086 machine code, 48 bytes (as a complete program)

```
00000000  1f bf 30 01 a0 84 04 40  e8 1a 00 b0 78 aa a0 4a  |..0....@....x..J|
00000010  04 e8 11 00 8d 8d d0 fe  8d 75 ff 06 1f fd ac cd  |.........u......|
00000020  29 e2 fb cd 20 d4 0a 0c  30 aa c1 e8 08 75 f6 c3  |)... ...0....u..|
00000030

```

### How it works:

```
                |   org 0x100
                |   use16
1f              |       pop ds              ; clear ds (the stack always contains 0 on entry)
bf 30 01        |       mov di, d           ; set destination ptr
a0 84 04        |       mov al, [0x484]     ; console rows - 1
40              |       inc ax
e8 1a 00        |       call to_ascii       ; convert to ascii
b0 78           |       mov al, 'x'
aa              |       stosb
a0 4a 04        |       mov al, [0x44a]     ; console columns
e8 11 00        |       call to_ascii
8d 8d d0 fe     |       lea cx, [di-d]      ; number of characters to print
8d 75 ff        |       lea si, [di-1]      ; set source ptr
06              |       push es
1f              |       pop ds
fd              |       std                 ; reverse direction flag
ac              |   @@: lodsb               ; load (al = *si--)
cd 29           |       int 0x29            ; print al to console, bypassing stdout
e2 fb           |       loop @b             ; repeat while (--cx != 0)
cd 20           |       int 0x20            ; terminate
                |
                |   to_ascii:
d4 0a           |       aam 10              ; ah = (al / 10), al = (al % 10)
0c 30           |       or al, 0x30         ; convert al to ascii number
aa              |       stosb               ; store (*di++ = al)
c1 e8 08        |       shr ax, 8           ; shift ah to al
75 f6           |       jnz to_ascii        ; repeat if non-zero
c3              |       ret
                |
                |   d rb 0

```

# Answer
> 18 votes
# Bash, ~~22~~ 20 characters

```
echo $COLUMNS $LINES

```

Thanks to:

* Doorknob for optimal output format (2 characters)

Sample run:

```
bash-4.3$ echo $COLUMNS $LINES
80 24

```

# Answer
> 14 votes
## xterm, 6 bytes

As you don't need specific formate, you can simply use the **`resize`** (6 character) command of `xterm`:

```
$ resize
COLUMNS=120;
LINES=31;
export COLUMNS LINES;

```

# Answer
> 13 votes
# sh, 20 bytes

```
tput lines;tput cols

```

.. Too obvious, maybe..

# Answer
> 12 votes
# Python 3, 30 bytes

```
import os
os.get_terminal_size

```

As it does not work in TIO, an alternative is used there:

Try it online!

# Answer
> 11 votes
# C (linux only), ~~63~~ 61

```
short m[4];main(){ioctl(0,21523,m);printf("%dx%d",*m,m[1]);}

```

# Answer
> 8 votes
# APL (Dyalog), 3 bytes

(Posting an answer already since this really isn't my challenge.)

`⎕SD`**S**creen **D**imensions

Sample run:

```
      ⎕SD
25 79

```

# Answer
> 8 votes
## C#, 59 bytes

```
using c=System.Console;_=>c.WindowWidth+"x"+c.WindowHeight;

```

Compiles to a `Func<int, string`, however, the input is not used.

# Answer
> 7 votes
# NodeJS, ~~50~~ ~~48~~ 46 bytes

```
> s=process.stdout;console.log(s.columns,s.rows)
80 25

```

Uses `process.stdout`s `columns` and `rows` values.

# Answer
> 6 votes
# Ruby, ~~41~~ ~~36~~ 21 + 13 = 34 bytes

Run with the command line flag `-rio/console`

```
p IO.console.winsize

```

This is my first Ruby golf, so tell me if there is anything I can do better.

*5 bytes saved thanks to SztupY*

*2 bytes saved thanks to manatwork*

---

This outputs height then width as a length two list.

Example output:

```
[25, 80]

```

# Answer
> 6 votes
# GNU Forth, 7 bytes

```
form .s

```

> form – urows ucols gforth “form”
>
> The number of lines and columns in the terminal.

## Sample Output

```
<2> 24 80

```

Try It Online !

# Answer
> 4 votes
# Swift, 99 bytes

```
import Foundation;var w=winsize();ioctl(STDOUT_FILENO,UInt(TIOCGWINSZ),&w);print(w.ws_col,w.ws_row)

```

Thanks to the guys at Vapor for their Console package.

# Answer
> 4 votes
# PowerShell + Mode, 11 Bytes?

Output may not be acceptable in current form.

the `mode` command is a default windows utility

Meta Post regarding usage of `mode` without specifying `con`

```
(mode)[3,4]

```

gets the output of mode:

```
<Whitespace>
Status for device CON:
----------------------
    Lines:          3000
    Columns:        120
    Keyboard rate:  31
    Keyboard delay: 1
    Code page:      850

```

then the 4th & 5th lines (`[3,4]`) outputting:

```
PS H:\> (mode)[3,4]
    Lines:          3000
    Columns:        120

```

# Answer
> 4 votes
# C# 94 bytes (whole app)

MetaColon's whole app answer can be shortened quite a lot:

```
using c=System.Console;class P{static void Main(){c.Write(c.WindowWidth+' '+c.WindowHeight);}}

```

# Answer
> 3 votes
# Batch, ~~25~~ ~~19~~ ~~18~~ 17 bytes

Saved 6 bytes by piping directly to the "find" command.
Saved 1 byte thanks to Adám / OP.
Saved 1 byte thanks to comment by OP.

```
mode con|find "n"

```

This outputs the command itself since echo is on but, as commented by OP, a leading line is OK.

---

Depending on your setup, it may work with only 13 bytes. However, it seems that having anything using COM ports will cause overly verbose output.

```
mode|find "n"

```

# Answer
> 3 votes
# C#, 85 Bytes

```
()=>System.Console.Write(System.Console.WindowWidth+"x"+System.Console.WindowHeight);

```

If you want a whole application code, we'd have **115 101 94 Bytes**:

```
using C=System.Console;class P{static void Main()=>C.Write(C.WindowWidth+"x"+C.WindowHeight);}

```

However you could mean the *Buffer* size as well, we'd have **85 Bytes** again

```
()=>System.Console.Write(System.Console.BufferWidth+"x"+System.Console.BufferHeight);

```

Or as a whole application code (obviously **115 101 94 Bytes** again):

```
using C=System.Console;class P{static void Main()=>C.Write(C.BufferWidth+"x"+C.BufferHeight);}

```

*Saved 14 Bytes in the whole application code with the help of Caius Jard*

# Answer
> 2 votes
# 8th, ~~24~~ ~~16~~ 12 bytes

*Revised after Anders Tornblad comment.*

```
con:size? .s

```

Returns the current size of the console in rows and columns printing stack content.

Output:

```
2  n: 000000000285e5e0 1   300
1  n: 000000000285e4c0 1   90

```

# Answer
> 2 votes
# Java 8 (no libraries), Windows, 270 bytes

Posting seperately by recommendation of Adam.

```
interface B{static void main(String[] a)throws Exception{Object[]r=new java.io.BufferedReader(new java.io.InputStreamReader(Runtime.getRuntime().exec("cmd /c mode").getInputStream())).lines().toArray();System.out.print(r[3]+"\n"+r[4]);}}

```

Ungolfed:

```
interface B {
    static void main(String[] a) throws Exception {
        Object[] r = new java.io.BufferedReader(new java.io.InputStreamReader(
                Runtime.getRuntime().exec("cmd /c mode").getInputStream())
        ).lines().toArray();
        System.out.print(r[3] + "\n" + r[4]);
    }
}

```

# Answer
> 2 votes
# Java + \*nix, 113

```
interface B{static void main(String[] a)throws Exception{new ProcessBuilder("stty","size").inheritIO().start();}}

```

Ungolfed:

```
interface B{
    static void main(String[] a)throws Exception{
        new ProcessBuilder("stty","size").inheritIO().start();
    }
}

```

`ProcessBuilder.inheritIO` causes a child process input/output to be inherited; this is the default in C with `exec`. In Java, the default is "piped." As you can see, this is way shorter than using `Runtime.getRuntime().exec()` (which is also deprecated) and constructing a `BufferedReader` through a long and convoluted call that is the result of the Java API designers' apparent unwillingness to add an overload for convenience.

# Answer
> 1 votes
# C (linux, C89 only), ~~45~~ 41

inspired by https://codegolf.stackexchange.com/a/118696/42186 by @dieter

```
main(m){ioctl(0,21523,&m);write(1,&m,4);}

```

this outputs the size as binary data. Not sure if this counts as "any format". You would need something extra (less, hexdump, od, ascii table) (or an esoteric terminal emulator that automatically does this for you) to make it human readable. Example usage:

```
$ ./a.out | od -sAn
     58    204

```

The terminal size is 204 cols by 58 rows.

Thanks to @Random832 for using `od` instead of `hexdump`.

# Answer
> 1 votes
# Red, 19 Bytes

```
system/console/size

```

Output:

```
>> system/console/size
== 106x26

```

Can also get the screen resolution as in the previous question

# Answer
> 1 votes
# Kotlin + Jline 2, 58 bytes

```
{print(jline.TerminalFactory.get().run{"$width $height"})}

```

Because why not. Turns out the standard lib actually has no way to determine console size so pulling in a library is required, lest you want to gold launching another process and parsing the input stream... *would be a shame if somebody did that..*

# Answer
> 1 votes
# Commodore 64 BASIC, 7 bytes

```
?"40x25

```

The C64 has a fixed-size text console of 40 x 25 characters. It is not necessary to query the console size, which is a good thing, as there is no way to query it.

# Answer
> 1 votes
# Stacked, 7 bytes

```
termdim

```

Leaves output on the stack, as is allowed per default. Example usage:

```
λ stacked -pe "termdim"
(117 26)

```

Bonus: `termdim'x'#`` to have it `117x26`.

---
Tags: code-golf
---