title: Paper Folding for the win

text:
# Question
Title: Paper Folding for the win
# Paper Folding for the win

---

"How many times can you fold a paper?" - This well known question led to many arguments, competition, myths and theories.

Well, the answer to that question depends on many properties of the paper (length, strength, thickness, etc...).

In this challenge we will try to fold a piece of paper as much as we can, however, there will be some constraints and assumptions.

---

### Assumptions:

* The paper will be represented in pixel-sized cells. The length and width of the paper is `N x M` respectively (which means you can not fold a pixel/cell in the middle).
* Unlike real paper, each spot (pixel) of the paper has its own thickness.

---

### A paper:

A paper will be represented as a 2D `M x N` Matrix as the top-view of the paper. Each cell of the matrix will contain a number that will represent the thickness of the paper's pixel. Area with no paper is the cell with the number 0.

Paper representation example:

```
     Option 1                        Option 2

2 1 1 1 1 1 1 1 2              [[2,1,1,1,1,1,1,1,2],
1 1 1 1 2 1 1 1 1              [1,1,1,1,2,1,1,1,1],
1 1 1 2 3 2 1 1 1              [1,1,1,2,3,2,1,1,1],
1 1 1 1 2 1 1 1 1              [1,1,1,1,2,1,1,1,1],
2 1 1 1 1 1 1 1 2              [2,1,1,1,1,1,1,1,2]]

```

---

### A fold:

A fold is a manipulation on the matrix defined as follows:

Assuming there is a 2 pixels fold from the right side of the paper in the example above, the size of the paper will now be `N-2 x M` and the new thickness of the pixels will be the summation of the previous thickness of the cell + the thickness of the mirrored cell relative to the fold cut:

```
            ___
           /   \
          \/<-- |
2 1 1 1 1 1 1|1 2            2 1 1 1 1 3 2
1 1 1 1 2 1 1|1 1            1 1 1 1 2 2 2
1 1 1 2 3 2 1|1 1    ===>    1 1 1 2 3 3 2
1 1 1 1 2 1 1|1 1            1 1 1 1 2 2 2
2 1 1 1 1 1 1|1 2            2 1 1 1 1 3 2

```

---

### Constraints:

* You can fold a paper from 4 directions only: Top, Left, Right, Bottom.
* The fold will be symmetric, which means, if you fold 2 pixels of the paper from the left, all of the cells in the first and second columns will be folded 2 pixels "mirrorly".
* A thickness threshold of a paper cell will be given in each case, a cell can not exceed that threshold at any time, which means, you will not be able to fold the paper, if that specific fold will result exceeding the thickness threshold.
* Number of pixels being fold must be between 0 and the length/width of the paper.
* Do not exceed with your folding the initial dimensions and position of the paper. ( there is no pixel -1 )

---

### Input:

* A paper (represented as described before)
* Thickness threshold

---

### Output:

* A list of folds that yields a valid paper (with no pixels exceeding the thickness threshold) folded in any way you want (using any heuristic or algorithm you've implemented).

---

### Scoring:

The goal is writing a program that will output a set of folds that result in the minimum possible number of remaining pixels for any input.

Since this is a , the shortest code wins.

---

### Examples:

**Example:**

```
Threshold: 9

1 1 1 1 1 1
1 1 1 1 1 1    fold 2 pixels from top   2 2 2 2 2 2    fold 3 pixels from right   4 4 4    fold 1 pixel from top
1 1 1 1 1 1    ======================>  2 2 2 2 2 2    =======================>   4 4 4    =====================>   8 8 8    No more fold possible
1 1 1 1 1 1

Optional outputs:
[2T,3R,1T]
------------or----------
[[2,top],[3,right],[1,top]]
------------or----------
Top 2
Right 3
Top 1
------or any other sensible readable way------
--------notice the order is inportant---------

```

---

### Some Test cases:

**Case 1:**

```
N = 17 , M = 11 , Threshold =  16
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 1 2 1 1 0 0 0 0 0 0
0 0 0 0 0 1 1 2 3 2 1 1 0 0 0 0 0
0 0 0 0 1 1 1 1 2 1 1 1 1 0 0 0 0
0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

```

**Case 2:**

```
N = 20 , M = 9 , Threshold =  32
1 1 1 1 1 1 1 1 1 8 8 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 8 1 1 8 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 8 1 1 1 1 8 1 1 1 1 1 1 1
1 1 1 1 1 1 8 1 1 1 1 1 1 8 1 1 1 1 1 1
1 1 1 1 1 8 1 1 1 1 1 1 1 1 8 1 1 1 1 1
1 1 1 1 1 1 8 1 1 1 1 1 1 8 1 1 1 1 1 1
1 1 1 1 1 1 1 8 1 1 1 1 8 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 8 1 1 8 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 8 8 1 1 1 1 1 1 1 1 1

```

**Case 3:**

```
N = 10 , M = 10 , Threshold =  29
1 1 1 1 1 1 1 1 1 1
1 1 9 1 1 1 1 9 1 1
1 9 9 9 1 1 9 9 9 1
1 1 9 1 1 1 1 9 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 9 1 1 1 1 9 1 1
1 9 9 9 1 1 9 9 9 1
1 1 9 1 1 1 1 9 1 1
1 1 1 1 1 1 1 1 1 1

```

**Case 4:**

```
N = 20 , M = 12 , Threshold =  23
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 4 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3
1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4
1 1 1 3 4 3 1 1 1 1 1 1 1 1 1 1 2 3 4 4
1 1 1 1 3 1 1 1 1 1 1 1 1 1 2 2 3 4 4 4
1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 3 4 4 4 3
1 1 1 1 1 1 1 1 2 2 2 2 2 3 4 4 4 3 3 2
2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 3 3 2 1 1
4 3 2 1 1 1 1 1 2 2 3 3 2 2 1 1 1 1 1 1
5 4 3 2 1 1 1 3 3 2 2 1 1 1 1 1 1 1 1 1

```

---

## Check validity

This nodejs program will:

1. Check if your folded papers are valid
2. Check if your steps are valid

# How to use:

Call the desired function in the footer.

Call **validator** with threshold, initial paper, and a list of steps with the format `[x,d]` for folding `x` pixels from `d` direction. `d` is one of the following strings: "RIGHT","LEFT","TOP","BOTTOM". This function will print if the final paper as a matrix and the amount of pixels reduced.

Output will look like this:

```
*** PAPER IS VALID ***
Init length: 240, New length: 180, Pixels removed (score): 60

```

Or, if the paper isn't valid:

```
*** PAPER UNVALID ***
NO SCORE :(

```

**You can see call examples commented in the code.**

You can also remove the comment in the line `// console.log(paper); // If you want to print the paper after each step` to "debug" and print the folded paper after each fold.

# Answer
# , 425 bytes

```
p=function(m,t){
d=dim(m);r=d[1];c=d[2]
l=apply(matrix(c(seq(l=r-1),rep(0,r+c-2),seq(l=c-1)),,2),1,function(f){n=array(0,pmax(g<-(f-1)%%d+1,h<-(d-f-1)%%d+1))
`if`(f,n[1:g[1],]<-m[g[1]:1,],n[,1:g[2]]<-m[,g[2]:1])
n[1:h[1],1:h[2]]=n[1:h[1],1:h[2]]+m[(i=g%%d+1)[1]:r,i[2]:c]
if(max(n)<=t)cbind(c(T=f[1],L=f[2]),p(n,t))})
if(!is.null(l))l[[order(sapply(l,function(f){for(x in seq(ncol(f))){d=pmax(f[,x],d-f[,x])};prod(d)}))[1]]]}

```

Try it online!

This came out *much* longer than I expected, and also slows-down a lot for big sheets of paper with large thresholds (which could be foreseen from the approach).

Recursively tries each possible fold, keeping only results that don't exceed the threshold at any pixel, and choosing the series of folds that gives the smallest folded size.

Output is 2d list of folds, with 'T' row indicating position of horizontal folds from top, and 'L' row indicating position of vertical folds from left.

Ungolfed version:

```
fold_paper=p=function(m,t){             # m=matrix of paper thicknesses; t=threshold thickness;
    d=dim(m);r=d[1];c=d[2]              # get paper dimensions;
    fold_list=apply(                    # iterate over list of possible folds to this paper...
        matrix(c(seq(l=r-1),rep(0,r+c-2),seq(l=c-1)),,2),1,
                                        # as a matrix: each row is a possible fold, and the 2
                                        # columns represent positions vertical & horizontal folds;
        function(f){
            new_m=array(0,pmax(g<-(f-1)%%d+1,h<-(d-f-1)%%d+1))
                                        # make a new matrix for each trial fold, then...
            if(f)                       # if it's a horizontal fold...
                 new_m[1:g[1],]<-m[g[1]:1,]
                                        # add the relevant rows of m, reversed,
            else new_m[,1:g[2]]<-m[,g[2]:1])
                                        # otherwise add the relevant cols of m, reversed;
            new_m[1:h[1],1:h[2]]=new_m[1:h[1],1:h[2]]+m[(i=g%%d+1)[1]:r,i[2]:c]
                                        # and now add all the unfolded elements of m
            if(max(new_m)<=t)               # now, if we didn't exceed the paper thickness threshold...
                cbind(c(T=f[1],L=f[2]),p(new_m,t))
                                        # add this fold to the list (labelled with 'T' and 'L',
                                        # and recursively call function with newly_folded paper;
        }
    )
    if(!is.null(fold_list))             # if we ended-up with a list containing any valid folds,
        fold_list[[                     # return the element containing the set of folds with...
            which.min(                  # the lowest value of...
                sapply(fold_list,function(folds){
                    for(x in seq(ncol(folds))){d=max(folds[,x],d-folds[,x])};prod(d)}))]]
                                        # the number of remaining pixels, calculated from the product
                                        # of the remaining cols & rows after applying all the folds
}

```
> 2 votes

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


title: Give Me a Ladder!

text:
# Question
Title: Give Me a Ladder!
I think everyone is familiar with the game of snakes & ladders1. Imagine we have a 10x10 board like this:

```
=============================================================
|     |     |     |     |     |     |     |     |     |     |
| 100 | 99  | 98  | 97  | 96  | 95  | 94  | 93  | 92  | 91  |
------+-----+-----+-----+-----+-----+-----+-----+-----+------
|     |     |     |     |     |     |     |     |     |     |
| 81  | 82  | 83  | 84  | 85  | 86  | 87  | 88  | 89  | 90  |
------+-----+-----+-----+-----+-----+-----+-----+-----+------
|     |     |     |     |     |     |     |     |     |     |
| 80  | 79  | 78  | 77  | 76  | 75  | 74  | 73  | 72  | 71  |
------+-----+-----+-----+-----+-----+-----+-----+-----+------
|     |     |     |     |     |     |     |     |     |     |
| 61  | 62  | 63  | 64  | 65  | 66  | 67  | 68  | 69  | 70  |
------+-----+-----+-----+-----+-----+-----+-----+-----+------
|     |     |     |     |     |     |     |     |     |     |
| 60  | 59  | 58  | 57  | 56  | 55  | 54  | 53  | 52  | 51  |
------+-----+-----+-----+-----+-----+-----+-----+-----+------
|     |     |     |     |     |     |     |     |     |     |
| 41  | 42  | 43  | 44  | 45  | 46  | 47  | 48  | 49  | 50  |
------+-----+-----+-----+-----+-----+-----+-----+-----+------
|     |     |     |     |     |     |     |     |     |     |
| 40  | 39  | 38  | 37  | 36  | 35  | 34  | 33  | 32  | 31  |
------+-----+-----+-----+-----+-----+-----+-----+-----+------
|     |     |     |     |     |     |     |     |     |     |
| 21  | 22  | 23  | 24  | 25  | 26  | 27  | 28  | 29  | 30  |
------+-----+-----+-----+-----+-----+-----+-----+-----+------
|     |     |     |     |     |     |     |     |     |     |
| 20  | 19  | 18  | 17  | 16  | 15  | 14  | 13  | 12  | 11  |
------+-----+-----+-----+-----+-----+-----+-----+-----+------
|     |     |     |     |     |     |     |     |     |     |
| 1   | 2   | 3   | 4   | 5   | 6   | 7   | 8   | 9   | 10  |
=============================================================

```

The task is to (sort of) paint a ladder on this board from a smaller number to a bigger one. Kind of an ASCII art using these characters `/\ | _` only.

The board's dimensions are 61x31 characters fixed like above. To illustrate the task, let's draw some ladders e.g. from 7 to 31, 22 to 77, 54 to 96, and 68 to 89 like this:

```
=============================================================
|     |     |     |     |     |     |     |     |     |     |
| 100 | 99  | 98  | 97  | 96  | 95  | 94  | 93  | 92  | 91  |
------+-----+-----+-----+-\_\-+-----+-----+-----+-----+------
|     |     |     |     |  \_\|     |     |     |     |     |
| 81  | 82  | 83  | 84  | 85\_\ 86  | 87  | 88  | 89  | 90  |
------+-----+-----+-----+----\_\----+-----+-----+/_/--+------
|     |     |     |     |     \_\   |     |     /_/   |     |
| 80  | 79  | 78  | 77  | 76  |\_\  | 74  | 73 /_/72  | 71  |
------+-----+-----+/_/--+-----+-\_\-+-----+---/_/-----+------
|     |     |     /_/   |     |  \_\|     |  /_/|     |     |
| 61  | 62  | 63 /_/64  | 65  | 66\_\ 67  | / / | 69  | 70  |
------+-----+---/_/-----+-----+----\_\----+-----+-----+------
|     |     |  /_/|     |     |     \_\   |     |     |     |
| 60  | 59  | /_/ | 57  | 56  | 55  |\ \  | 53  | 52  | 51  |
------+-----+/_/--+-----+-----+-----+-----+-----+-----+------
|     |     /_/   |     |     |     |     |     |     |     |
| 41  | 42 /_/43  | 44  | 45  | 46  | 47  | 48  | 49  | 50  |
------+---/_/-----+-----+-----+-----+-----+-----+-----+------
|     |  /_/|     |     |     |     |     |     |     |     |
| 40  | /_/ | 38  | 37  | 36  | 35  | 34  | 33  | 32  | 31  |
------+-|_|-+-----+-----+-----+-----+-----+-----+-----+/_/---
|     | |_| |     |     |     |     |     |     |     /_/   |
| 21  | | | | 23  | 24  | 25  | 26  | 27  | 28  | 29 /_/30  |
------+-----+-----+-----+-----+-----+-----+-----+---/_/------
|     |     |     |     |     |     |     |     |  /_/|     |
| 20  | 19  | 18  | 17  | 16  | 15  | 14  | 13  | /_/ | 11  |
------+-----+-----+-----+-----+-----+-----+-----+/_/--+------
|     |     |     |     |     |     | __________/_/   |     |
| 1   | 2   | 3   | 4   | 5   | 6   | _________/_/9   | 10  |
=============================================================

```

## Challenge

Given the two distinct numbers that are both in the range of `1..100`, draw a ladder from the smaller number to the bigger one, assuming that their arrangements and positions are fixed like above. **You are not required to print the whole table**. Only the ladder would suffice, but it must be placed in the right position on a 31`x`61 ASCII sheet.

Note that sometimes the ladder has two parts, i.e. direct (horizontal or vertical) and slant. The direct part must always come first.

# Rules

Standard rules apply. If any clarifications or more rules are needed, please inform me in the comments. Happy golfing!

1. In case you have never heard of it (which would be really odd), please refer to the linked Wikipedia article. I skipped elaborating the game rules for the sake of brevity **and** being on topic.

# Answer
> 4 votes
# Charcoal, 130 bytes

```
ＦχＦχ⊞υ×⁶⎇﹪ι²⁻⁹κκ≔⁻ＬυＮθ≔⁻ＬυＮη≔⊕§υηζ≔×³÷ηχηＪ§υθ×³÷θχ Ｆ›ζⅈ«≦⊕ζ »Ｆ⁻ζ⁺ⅈ⁻ⅉηＧ←←↑→↘→²_Ｆ⁻ⅈ⁺ζ⁻ⅉηＧ↑←↙→²_Ｗ›ⅉη«≔⎇›⁻ⅉη↔⁻ζⅈ²∨›ζⅈ³ιＰ✳ι¹←←✳ι¹→¿›ⅉη_

```

Try it online! Link is to verbose version of full 198-byte program that includes drawing the entire background. Explanation:

```
ＦχＦχ⊞υ×⁶⎇﹪ι²⁻⁹κκ

```

Get the X-coordinates of all 100 squares (since each row reverses direction).

```
≔⁻ＬυＮθ≔⁻ＬυＮη

```

Input the starting and ending square, but subtract from 100.

```
≔⊕§υηζ≔×³÷ηχη

```

Calculate the destination character.

```
Ｊ§υθ×³÷θχ

```

Jump to the start character.

```
 Ｆ›ζⅈ«≦⊕ζ »

```

Erase the start character, and if this is a right-leaning ladder, then erase the next character too (this is because right-leaning ladders start 1 character further right than left-leaning ladders for some reason).

```
Ｆ⁻ζ⁺ⅈ⁻ⅉηＧ←←↑→↘→²_

```

Draw the horizontal part of a right-leaning ladder, if applicable. This is complicated slightly because the horizontal part does not start 1 character further right.

```
Ｆ⁻ⅈ⁺ζ⁻ⅉηＧ↑←↙→²_

```

Draw the horizontal part of a left-leaning ladder, if applicable.

```
Ｗ›ⅉη«

```

Repeat until the top of the ladder is reached.

```
≔⎇›⁻ⅉη↔⁻ζⅈ²∨›ζⅈ³ι

```

Work out which direction we're going in (3 = up left, 2 = up, 1 (default) = up right).

```
Ｐ✳ι¹←←✳ι¹→

```

Draw the next section of ladder.

```
¿›ⅉη_

```

Draw the next rung, unless we've got to the top of the ladder.

# Answer
> 5 votes
# Python 2, 316 bytes

```
def f(m):
 r=[list(' '*61)for y in range(31)]
 (y,x),(b,a)=[[(109-p)/10*3,1+min(p%20,19-p%20)*6]for p in[max(m)-1,min(m)-1]]
 while y<b:c=cmp(a,x);r[y][x:x+4]=r"  /|\___/|\ "[c%3::3];x+=c;y+=1
 if x==a:r[y-1][x+2-(r[y-1][x]>' ')]=" "
 while x-a:c=cmp(a,x)+1;r[y-2][x+c:x+2+c]="__";r[y-1][x+c*3/2]="_";x+=c-1
 print r

```

Try it online! (footer paints over grid for pretty output)

Function that inputs a list of two numbers and outputs a list of lists of characters.

### How it works

We find character coordinates of the higher point (e.g. 96), then translate it along diagonal, vertical, or horizontal movements to the coordinates of the lower point (e.g. 54), modifying the character matrix `r` as we go.

```
def f(m):
    r = [list('.'*61) for y in range(31)]
    m = [max(m)-1,min(m)-1]
    # (x,y) is the higher point
    # (a,b) is the lower point
    # x increases right; y increases down
    (y,x),(b,a) = [[(109-p)/10*3,1+min(p%20,19-p%20)*6] for p in m]
    # move (x,y) to (a,b) via 1-unit translations
    # \ diagonal
    while x < a and y < b:
        r[y][x+1:x+4] = "\\_\\"
        x += 1
        y += 1
    # / diagonal
    while x > a and y < b:
        r[y][x:x+3] = "/_/"
        x -= 1
        y += 1
    # straight down
    while x == a and y < b:
        r[y][x+1:x+4] = "|_|"
        y += 1
    # remove space at the bottom of the ladder
    # (r[y-1][x]!='.' deals with off-by-one error in the case of
    # \ diagonals with no straight segment)
    if x == a:
        r[y-1][x+2-(r[y-1][x]!='.')] = " "
    # left
    while x > a:
        r[y-2][x+1] = "_"
        r[y-2][x] = "_"
        r[y-1][x] = "_"
        x -= 1
    # right
    while x < a:
        r[y-2][x+2] = "_"
        r[y-2][x+3] = "_"
        r[y-1][x+3] = "_"
        x += 1
    return r

```

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


# Question
Title: Make two programs communicate with each other
**Task:**

Your task is to create two programs in different languages that can communicate one-way to each other. Your sending (tx) program will take input, for either stdin or a query, and send it along to the receiving (rx) program. Your rx program will then print out the data that it receives.

**Rules:**

* The two programs must communicate one way from the tx to the rx side, so anything typed in tx will appear in rx.
* They will be running on the same computer, in different shells/windows.
* They will be running in separate instances, and you are not allowed to chain them (in bash, `prog1 | prog2`)
* The programs must be written in different languages.
* They can use any data transfer method, but you must be able to transfer ASCII text.
* This is a , so the most up voted answer wins.
    + Note to voters: look for creativity!

# Answer
# Bash and GNU Awk communicating on TCP

Bash transmitter:

```
cat>/dev/tcp/localhost/8080

```

GNU Awk receiver:

```
BEGIN{getline<"/inet/tcp/8080/0/0";print}

```

Sample run:

Bash in terminal 1:

```
bash-4.2$ cat>/dev/tcp/localhost/8080
Bash says hello to Awk
^D

```

GNU Awk in terminal 2:

```
bash-4.2$ gawk 'BEGIN{getline<"/inet/tcp/8080/0/0";print}'
Bash says hello to Awk

```

Both `bash` and `gawk` provides special filenames (/dev/tcp/*host*/*port* in `bash` since 2.04, /*net-type*/*protocol*/*local-port*/*remote-host*/*remote-port* in `gawk` since 3.1.0) for simple networking. These are extensions not specified in the POSIX shell and Awk language standards.
> 6 votes

# Answer
# C and PERL communicating via keyboard status lights

My friend and I got inspired by this one last night.

We use Perl for the sender program and C for the receiver.

The medium of exchange was the keybord status lights!

Three virtual signal lines were used: Caps Lock, Num Lock and Scroll lock, being used as Clock, Serial Data, and Start Of Byte signals.

The sender program pulses those keyboard lights and the receiver polls them and checks the state. Data is sent serially as binary, in 8 bit bytes.

You can see the transmitter and receiver programs in operation, in the attached video, as well as the flashing of the lights during the transmission. Video of operation

Source for both programs is attached. Given the question requirements, we didn't try to minimize the size like we would in a normal golfing attempt.

## C Code (receiver)

```
#include <X11/Xlib.h>
#include <stdio.h>
#include <unistd.h>

int main(void)
{
    Display* dpy = XOpenDisplay(":0");
    XKeyboardState x;
    char keys_return[32];
    int b = 0;
    while (1) {
        unsigned char output = 0;
        printf(" \b");
        fflush(stdout);
        while (XQueryKeymap(dpy, keys_return)) //wait for start signal
            if (keys_return[9] == 64) {
                break;
            }
        for (b = 0; b < 8; b++) {
            do {
                XGetKeyboardControl(dpy, &x);
            } while (!(x.led_mask & 1)); //wait for clock to be high
            if (x.led_mask & 2)
                output |= 128;
            if (b != 7)
                output >>= 1;
            do {
                XGetKeyboardControl(dpy, &x);
            } while ((x.led_mask & 1)); //wait for clock to be low
        }
        printf("%c", output);
    }
    XCloseDisplay(dpy);
    return 0;
}

```

## PERL code (transmitter)

```
use X11::Xlib ':all';
use strict;
use warnings;
use feature 'say';
use Time::HiRes qw(sleep);

use constant {
    DATA  => 77,
    START => 78,
    CLOCK => 66
};

my $display = X11::Xlib->new;

sub transmit_str {
    my ($str) = @_;
    foreach my $char ( split( //, $str ) ) {
        my $ordchar = ord($char);
        for my $i ( 0 .. 7 ) {
            for my $j ( 0 .. 1 ) {
                if ( $i == 0 ) {
                    $display->fake_key( START, !($j) );
                }
                if ( $ordchar & 1 ) {
                    $display->fake_key( DATA, 1 );
                    $display->fake_key( DATA, 0 );
                }
                $display->flush;
                sleep(0.025) if(!$j);
                $display->fake_key( CLOCK, 1 );
                $display->fake_key( CLOCK, 0 );
                $display->flush;
                sleep(0.05);
            }
            $ordchar >>= 1;
        }
    }
}
while ( my $stdin = <STDIN> ) {
    transmit_str($stdin);
}

```
> 12 votes

# Answer
# Original Lisp Eliza communicating with yes

Original Eliza lisp code "communicating" with with unix `yes` utility.

First create a FIFO special file:

```
mkfifo in

```

Then we make the two programs communicate together (*which means that the patient will answer YES to all questions*).

```
clisp coselleliza1969and1972.lisp < in | tee out.txt | yes 'yes.'  > in

```

Output is inifnite and starts with:

```
TELL ME YOUR PROBLEMS. PLEASE TERMINATE INPUT WITH A PERIOD OR A QUESTION MARK.
IS THERE SOMETHING BOTHERING YOU?
WHY ARE YOU SO SURE?
I SEE.
I UNDERSTAND.
CAN YOU BE MORE INFORMATIVE?
WHY ARE YOU SO SURE?
I SEE.
I UNDERSTAND.
PERHAPS YOU'D RATHER TALK ABOUT SOMETHING ELSE.

```

More variety if it communicates with another instance of itself:

```
clisp coselleliza1969and1972.lisp < in | clisp coselleliza1969and1972.lisp | tee out.txt > in

```

Output starts with:

```
TELL ME YOUR PROBLEMS. PLEASE TERMINATE INPUT WITH A PERIOD OR A QUESTION MARK.
WHY ARE YOU CONCERNED OVER MY PROBLEMS?
I AM NOT SURE I UNDERSTAND YOU FULLY.
SUPPOSE * WHY WERE NOT I CONCERNED OVER YOUR PROBLEMS.
IS IT BECAUSE YOU ARE NOT SURE YOU UNDERSTAND I FULLY THAT YOU CAME TO ME?
YOU SAY YOU CONCERNED OVER MY PROBLEMS?
POSSIBLY THAT IS FOR THE BETTER.
SUPPOSE YOU SAY I CONCERNED OVER YOUR PROBLEMS.
POSSIBLY * POSSIBLY THAT REALLY IS NOT FOR THE BETTER.
OH? I SAY YOU CONCERNED OVER MY PROBLEMS?
WHAT IF REALLY WERE FOR THE BETTER?
PLEASE GO ON.
CAN YOU ELABORATE ON THAT?
WHAT DOES THAT SUGGEST TO YOU?
TELL ME MORE ABOUT YOUR PROBLEMS.
WHAT MAKES YOU THINK I ELABORATE ON THAT?
PERHAPS THAT CONCERNS YOUR PROBLEMS.
WHAT ABOUT YOUR OWN PROBLEMS?
WHO ARE YOU REALLY TALKING ABOUT?
YOU DON'T SEEM QUITE CERTAIN.
EARLIER YOU SAID YOU WERE NOT SURE YOU UNDERSTAND I FULLY.
TELL ME MORE ABOUT * WHO.
SUPPOSE YOU DON'T SEEM QUITE CERTAIN.
OH? I SAID I WAS NOT SURE I UNDERSTAND YOU FULLY?
ARE YOU STILL NOT SURE YOU UNDERSTAND I FULLY?
WHAT MAKES YOU THINK I DON'T SEEM QUITE CERTAIN?
WOULD YOU LIKE TO DISCUSS YOUR PROBLEMS?
DO YOU SAY YOU SAID YOU WAS NOT SURE YOU UNDERSTAND I FULLY FOR SOME SPECIAL REASON?
DID YOU THINK * MIGHT NOT BE I STILL NOT SURE I UNDERSTAND YOU FULLY?
WHO ARE YOU REALLY TALKING ABOUT?
SUPPOSE YOU LIKE TO DISCUSS MY PROBLEMS.
OH? I SAY I SAID I WAS NOT SURE I UNDERSTAND YOU FULLY FOR SOME SPECIAL REASON?
WHAT MAKES YOU THINK I THINK * MIGHT NOT BE YOU STILL NOT SURE YOU UNDERSTAND I FULLY?
* WHO PERHAPS ARE I REALLY TALKING ABOUT.
WHO ARE YOU REALLY TALKING ABOUT?
WHAT ELSE WOULD YOU LIKE TO DISCUSS?
TELL ME MORE ABOUT YOURSELF?
SUPPOSE YOU THINK YOU THINK * MIGHT NOT BE I STILL NOT SURE I UNDERSTAND YOU FULLY.
WHY THE UNCERTAIN TONE?
SUPPOSE * WHO WERE NOT I REALLY TALKING ABOUT.
OH? I LIKE TO DISCUSS?
WHY DO YOU SAY THAT JUST NOW?
WHAT MAKES YOU THINK I THINK I THINK * MIGHT NOT BE YOU STILL NOT SURE YOU UNDERSTAND I FULLY?
I AM NOT SURE I UNDERSTAND YOU FULLY.
OH? YOU REALLY TALKING ABOUT?
PLEASE GO ON.
WHAT ELSE DO YOU LIKE?
WHO ARE YOU REALLY TALKING ABOUT?
SUPPOSE YOU THINK YOU THINK YOU THINK * MIGHT NOT BE I STILL NOT SURE I UNDERSTAND YOU FULLY.
HOW LONG HAVE YOU BEEN NOT SURE YOU UNDERSTAND I FULLY?
DID YOU TELL ME YOU WERE NOT SURE YOU UNDERSTAND I FULLY?
OH? I REALLY TALKING ABOUT?
MAYBE NOW WE CAN DISCUSS WHY YOU ARE NOT SURE YOU UNDERSTAND I FULLY.
WHAT MAKES YOU THINK I LIKE?
POSSIBLY * WHO REALLY ARE NOT I REALLY TALKING ABOUT.
WHO ARE YOU REALLY TALKING ABOUT?
SUPPOSE YOU BEEN NOT SURE I UNDERSTAND YOU FULLY.
OH? I TELL YOU I WAS NOT SURE I UNDERSTAND YOU FULLY?
WOULD YOU LIKE TO DISCUSS YOUR PROBLEMS?
THAT'S QUITE INTERESTING.

```
> 9 votes

# Answer
# PHP + Bash

Bash - rx.sh

```
#!/bin/bash
tail -f output

```

PHP - tx.php

```
<?php
$fd=fopen("output", "w");
$msg = print_r($_GET, true);
fputs($fd, $msg);
fclose($fd);
?>

```

Query the program with `rx.php?<message>` or alternately, using a third language,

query.html

```
<body>
Enter the message to send:
<form action="tx.php" method="get">
<input type="text" name="message">
<input type="submit" value="Submit">
</form>
</body>

```
> 5 votes

# Answer
# Perl and Rebol via `ps` (process status)

tx.pl

```
use strict;
use warnings;

my $line;

while (chomp(my $msg = <>)) {
    $line++;
    $0 = "!!$line!!$msg";
    last if $msg eq 'q';
}

```

rx.reb

```
Rebol []

get-ps-msg: has [ps msg] [
    ps: copy ""
    call/output "ps" ps
    parse ps [thru "!!" copy msg to #"^/"]
    msg
]

print-msg: func [m /no-warning] [
    unless no-warning [print-warning? m]
    print next next find last m "!!"
]

print-warning?: func [m /local prev new] [
    prev: first back back tail m
    new:  last m
    prev: to-integer copy/part prev find prev "!!"
    new:  to-integer copy/part new  find new  "!!"
    if new != (prev + 1) [print ["WARNING: Out of sequence, expected" prev + 1 "but got" new]]
]

messages: []                     ; state: records all messages
until [not none? m: get-ps-msg]  ; lets wait until first msg appears
print-msg/no-warning append messages m

; loop until messages disappear from ps
until [
    if m != last messages [print-msg append messages m]
    none? m: get-ps-msg
]

```

So whats going on here? Well if you start `tx.pl` and then look at `ps` in another session you will see something like this:

```
$ ps
  PID TTY           TIME CMD
32171 ttys001    0:00.02 -bash
32432 ttys001    0:00.01 perl tx.pl

```

Perl allows you to amend what appears in the CMD (Command) column of `ps` by amending the `$0` variable. So for e.g. if `tx.pl` was this:

```
$0 = "hello mum!";
sleep 10;

```

Then you'll see this in `ps` while the script is still running:

```
$ ps
  PID TTY           TIME CMD
32171 ttys001    0:00.02 -bash
32433 ttys001    0:00.01 hello mum!

```

So we can use this to send messages from one script to another. The Rebol receiving script simply monitors `ps` for all messages sent to `ps` from the Perl script.

NB. The Rebol script does contain some extra bits that aren't really necessary (see warnings & recording all messages).

Usage: Do `perl tx.pl` and `rebol -qws rx.reb` in separate sessions and everything you type into transmitting session will appear in the receiving session. Once the transmitting session is closed (enter 'q' or ^C) then the receiving script automatically quits.

Tested on Mac OSX 10.7. Requires Rebol 2 at this moment because `call/output` not currently implemented in Rebol 3.
> 5 votes

# Answer
# sh tx with awk rx connected by a fifo

tx in sh... make a fifo, read user input and send it to fifo, remove fifo.

Run this in one terminal, enter a line and start the receiver in a different terminal.

```
(yeti@aurora:4)~$ mkfifo F ; read X ; echo $X > F ; rm F
xyzzy

```

rx in awk ... read fifo, print line and terminate.

```
(yeti@aurora:5)~$ awk '1' F
xyzzy

```

A direct connection of tx and rx by a pipe would be shorter but far less interesting.

The fifo would allow tx and rx to be run by different UIDs if the fifo's permissions are set to alow read by others.
> 4 votes

# Answer
# q and k

Receiver, `rx.q`, in q

```
\p 29010

```

Transmitter, `tx.k`, in k

```
.z.pi:{`::29010(-1;x)};

```
> 3 votes

# Answer
# Shell script and not-quite-HTML

Sending code:

```
#!/bin/sh
cat >> ~/receiver.html

```

Receiving code - must be located at `~/receiver.html`:

```
<meta http-equiv="Refresh" content="1">

```
> 3 votes

# Answer
# C++

```
#include<iostream>
#include<fstream>
using namespace std;
int main()
{
    char input[100];
    cin>>input;
    ofstream inputfile("temp.txt");
    inputfile<<input;
    inputfile.close();
    return 0;
}

```

# C++11

```
#include<iostream>
#include<fstream>
using namespace std;
int main()
{
    char output[100];
    ifstream outputfile("temp.txt");
    outputfile>>output;
    inputfile.close();
    cout<<output;
    return 0;
}

```

They communicate through a text file. In C++ code the input is written in a text file and is then collected by C++11 code.

But, `C++ is a subset of C++11`
If the asker feels cheated please comment I'll delete this answer! sorry :P
> 2 votes

# Answer
# Prolog and PHP

Tx: `writer.pl`

```
start :-
    open('file', write, Str),
    read(In),
    write(Str,In),
    nl(Str),
    close(Str).

```

Rx: `reader.php`

```
<?php
echo file_get_contents('file');

```

Usage:

```
$ gprolog
['writer.pl'].
start.
hello.

```

And then:

```
$ php reader.php

```
> 2 votes

# Answer
# VBS and Python

### communicating over microphone and speakers in cleartext

Works astonishingly well out of the box

## transmit

```
CreateObject("sapi.spvoice").Speak WScript.Arguments.Item(0)

```

## receive

```
import speech_recognition as sr

r = sr.Recognizer()
m = sr.Microphone()

try:
    while True:
        print("listening")
        with m as source: audio = r.listen(source)
        try:
            value = r.recognize_google(audio)
            print("repeating: " + value)
        except sr.UnknownValueError:
            print("¯\_(ツ)_/¯")
except KeyboardInterrupt:
    pass

```

(this is 90% straight from the quickstart examples, might as well just run `python -m speech_recognition`)
> 0 votes

---
Tags: popularity-contest
---


title: Pyramid Scheme Negation

text:
# Question
Title: Pyramid Scheme Negation
In my language Pyramid Scheme, there is a slightly funny construct: the empty triangle:

```
^
-

```

When given no arguments, it returns `0`. To generate `1` using this construct, we could use this:

```
   ^
  /!\
 ^---
 -

```

This simply passes `0` to the negation function. We can continue negating this result:

```
 ^
/!\
---^
  /!\
 ^---
 -

```

To get 0. One more negation gives:

```
   ^
  /!\
 ^---
/!\
---^
  /!\
 ^---
 -

```

## Challenge

Given an integer **n** ≥ 1, output the empty pyramid being negated **n** times in the described fashion.

## Test cases

```
input
output

1
   ^
  /!\
 ^---
 -

2
 ^
/!\
---^
  /!\
 ^---
 -

3
   ^
  /!\
 ^---
/!\
---^
  /!\
 ^---
 -

6
 ^
/!\
---^
  /!\
 ^---
/!\
---^
  /!\
 ^---
/!\
---^
  /!\
 ^---
 -

```

# Answer
# Charcoal, 17 bytes

```
ＦＮ«↙^→/!\¶³‖Ｔ»↓^-

```

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

```
ＦＮ«

```

Loop for the appropriate number of negations.

```
↙^→/!\¶³

```

Print a negation function. (The `³` expands to `---`.)

```
‖Ｔ

```

Reflect the canvas.

```
»↓^-

```

At the end of the loop, print the empty triangle.
> 9 votes

# Answer
# Pyramid Scheme,
~~31655 bytes, non-competing (obviously...)~~
~~16989~~ ~~12901~~ 8465 bytes, somewhat-competing

So, I thought this would be a funny thing to try.

## Edits:

```
      ^    ^  ^          ^             ^  ^        ^          ^        ^      ^  ^          ^          ^                ^       ^                 ^          ^
     ^-   / \ -^        / \           ^- / \       -^        / \      ^-     / \ -^        / \        / \              ^-      / \               / \        / \
    ^-   /set\ -^      /set\         ^- /set\       -^      /set\    ^-     /set\ -^      /set\      /set\            / \     /set\             /   \      /out\
   ^-   ^-----^ -^    ^-----^       ^- ^-----^       -^    ^-----^   -^    ^-----^ -^    ^-----^    ^-----^          ^---^   ^-----^           /     \    ^-----^
  ^-   /f\   / \ -^  /t\   /f\     ^- /r\   /+\       -^  /r\   /+\   -^  /r\   /+\ -^  /r\   /+\  /r\   /+\        ^-  / \ /l\   /0\         / loop  \  /s\   /d\
  -^   ---  /chr\ -^ ---   ---    ^-  ---  ^---^       -^ ---  ^---^   -^ ---  ^---^ -^ ---  ^---^ ---  ^---^      ^-  /   \---   ---        ^---------^ ---   ---
   -^      ^----- / \            / \      /r\ /e\       -^    /r\ /f\   -^    /r\ /c\ -^    /r\ /d\    /r\ /e\    ^-  /     \               /!\       / \
    -^    / \    ^---^          ^---^     --- ---       / \   --- ---    -^   --- --- / \   --- ---    --- ---   ^-  /       \             ^---      /   \
     -^  /47 \  / \  -^        / \  -^                 /   \              -^         /   \                      ^-  /         \           /!\       /     \
      -^ ----- /set\  -^      /set\  -^               /     \              -^       /     \                    ^-  /           \         ^---      /       \
       -^     ^-----^  -^    ^-----^  -^             /       \              -^     /       \                  ^-  /      ?      \       / \       ^---------^
        -^   /a\   / \  -^  /t\   /+\  -^           /         \              -^   /         \                ^-  ^---------------^     /<=>\     / \       / \
         -^  ---  /chr\  -^ ---  ^---^  -^         ^-----------^             ^-  ^-----------^              ^-  /!\             / \   ^-----^   /   \     /set\
         / \     ^-----  / \    /t\ /a\  -^       / \         / \           ^-  / \         / \            ^-  ^---            /   \ /l\   /n\ /     \   ^-----^
        /   \   / \     /   \   --- ---   -^     /set\       /set\         ^-  /set\       /set\          ^-  /?\             /     \---   ---/       \ /l\   /+\
       /     \ /33 \   /     \             -^   ^-----^     ^-----^       ^-  ^-----^     ^-----^        ^-  ^---^           /       \       /         \---  ^---^
      /       \-----  /       \             -^ /r\   /+\   /r\   /+\     ^-  /r\   /+\   /r\   /+\      ^-  /m\ / \         ^---------^     /           \   /l\ /1\
     /         \     ^---------^            / \---  ^---^  ---  ^---^   ^-   ---  ^---^  ---  ^---^    ^-   ---/   \       / \       / \   /             \  --- ---
    ^-----------^   / \       / \          /   \   /r\ /s\     /r\ /s\ ^-        /r\ /d\     /r\ /d\  ^-      /     \     /out\     /out\ /               \
   / \         ^-  /set\     /set\        /     \  --- ---     --- ---/ \        --- ---     --- --- ^-      /       \   ^-----^   ^-----/                 \
  /set\       ^-  ^-----^   ^-----^      ^-------^                   /   \                          ^-      ^---------^ /s\   /c\ /e\   /                   \
 ^-----^     ^-  /b\   / \ /d\   / \    ^-      ^-                  /     \                        ^-      / \       / \---   --- ---  /                     \
/n\   /#\   ^-   ---  /chr\---  /chr\  ^-      ^-                  /       \                      / \     /out\     /out\             /                       \
---  ^---  ^-        ^-----    ^----- ^-      / \                 /         \                    /   \   ^-----^   ^-----            /                         \
    /l\   / \       / \       / \    ^-      /   \               ^-----------^                  /     \ /s\   /s\ /s\               /                           \
   /ine\ /   \     /92 \     /45 \  ^-      /     \              -^         / \                /       \---   --- ---              /                             \
   -----/     \    -----     ----- ^-      /       \              -^       /set\              /         \                         /                               \
       /       \                  ^-      /         \              -^     ^-----^            ^-----------^                       /                                 \
      /         \                ^-      ^-----------^              -^   /r\   /+\          / \         / \                     /                                   \
     ^-----------^              ^-       -^         / \              -^  ---  ^---^        /set\       /   \                   ^-------------------------------------^
    / \         ^-             / \        -^       /set\              -^     /r\ /s\      ^-----^     /     \                 / \                                   / \
   /set\       ^-             /   \        -^     ^-----^             / \    --- ---     /m\   /n\   / loop  \               /   \                                 /   \
  ^-----^     ^-             /     \        -^   /r\   /c\           ^---^               ---   ---  ^---------^             /     \                               /     \
 /s\   / \   ^-             /       \        -^  ---   ---          / \  -^                        / \       / \           /       \                             /   ?   \
 ---  /chr\ ^-             /         \        -^                   /set\  -^                      /   \     /set\         /         \                           ^---------^
     ^-----/ \            ^-----------^        -^                 ^-----^  -^                    / <=> \   ^-----^       ^-----------^                         /!\       ^-
    / \   /   \           -^         / \        -^               /r\   /+\  -^                  ^-------^ /m\   /-\     / \         / \                       ^---      / \
   /32 \ /     \           -^       /set\        -^              ---  ^---^  -^                / \     / \---  ^---^   /set\       /   \                     / \       /out\
   -----/       \           -^     ^-----^       / \                 /r\ /a\  -^              /<=>\   /-1 \   /m\ /2\ ^-----^     /     \                   /   \     ^-----
       ^---------^           -^   /t\   /+\     /   \                --- ---  / \            ^-----^  -----   --- ---/k\   /l\   / loop  \                 /  ?  \   /t\
      / \       / \           -^  ---  ^---^   /     \                       /   \          /m\   /2\                ---   ---  ^---------^               ^-------^  ---
     /set\     /set\           -^     /t\ /d\ /       \                     /     \         ---   ---                          / \       / \             /!\     ^-
    ^-----^   ^-----^          / \    --- ---/         \                   /       \                                          /   \     /set\           ^---    / \
   /e\   / \ /c\   / \        /   \         ^-----------^                 /         \                                        / <=> \   ^-----^         / \     /out\
   ---  /chr\---  /chr\      /     \       / \         / \               ^-----------^                                      ^-------^ /k\   /-\       /<=>\   ^-----
       ^-----    ^-----     /       \     /set\       /set\             / \         / \                                    / \     / \---  ^---^     ^-----^ /r\
      / \       / \        /         \   ^-----^     ^-----^           /set\       /set\                                  /<=>\   /-1 \   /k\ /2\   /+\   /1\---
     /10 \     /94 \      ^-----------^ /t\   /+\   /t\   /+\         ^-----^     ^-----^                                ^-----^  -----   --- ---  ^---^  ---
     -----     -----     / \         / \---  ^---^  ---  ^---^       /r\   /+\   /r\   /+\                              /k\   /2\                 /k\ /m\
                        /set\       /set\   /t\ /d\     /t\ /d\      ---  ^---^  ---  ^---^                             ---   ---                 --- ---
                       ^-----^     ^-----^  --- ---     --- ---          /r\ /b\     /r\ /e\
                      /t\   /+\   /t\   /+\                              --- ---     --- ---
                      ---  ^---^  ---  ^---^
                          /t\ /b\     /t\ /e\
                          --- ---     --- ---

```

Try it online!

## Explanation

```
(set n (# line)) // Set n to line input

(set space (chr 32))
(set newline (chr 10))
(set caret (chr 94))
(set fslash (chr 47))
(set bang (chr 33))
(set bslash (chr 92))
(set dash (chr 45))

// Left triangle
(set lt fslash)
(set lt (+ lt bang)) (set lt (+ lt bslash)) (set lt (+ lt newline))
(set lt (+ lt dash)) (set lt (+ lt dash)) (set lt (+ lt dash))

// Right triangle
(set rt caret) (set rt (+ rt newline))
(set rt (+ rt space)) (set rt (+ rt space))
(set rt (+ rt fslash)) (set rt (+ rt bang)) (set rt (+ rt bslash))
(set rt (+ rt newline))
(set rt (+ rt space)) (set rt (+ rt caret))
(set rt (+ rt dash)) (set rt (+ rt dash)) (set rt (+ rt dash))
(set rt (+ rt newline))

// n = mod(m,2)
((set m n) (loop (<=> (<=> m 2) -1) (set m (- m 2))))

// Print the top and the first triangle
(? (! (? m ( // If m
    (out space space) (out space)
))) ( // Else
    (out space caret) (out newline)
))

(set l 0)
(loop (! (! (<=> l n))) ( // While l < n
    ((set k l) (loop (<=> (<=> k 2) -1) (set k (- k 2)))) // k = mod(l,2)
    (? (! (? (! (<=> (+ k m) 1)) ( // If xor(k,m)
        (out rt)
    ))) ( // Else
        (out lt)
    ))
(set l (+ l 1))
))
(out space dash) // Final triangle

```
> 14 votes

# Answer
# Python 2, 94 bytes

```
i=input();print i%2*2*" "+" ^"
while i:print['/!\\\n---^','  /!\\\n ^---'][i%2];i-=1
print" -"

```

Try it online!

Trying to golf this... 3 `print` statements seem awfully redundant.
> 6 votes

# Answer
# Proton, 101 bytes

```
a=>{k=" ^---"for i:0..a print(["   ^",k,"---^"][i?~i%2+1:i]+"\n"+" "*(~i%2)*2+"/!\\")print(k+"\n -")}

```

Try it online!

also too long lol
> 3 votes

# Answer
# Perl 5, 77+1 (-p) bytes

```
$\=' ^
 _';map$_%2?$\=~s,\^,  ^
  /!\\
 ^---,:$\=~s,  \^,^
/!\\
---^,,1..$_}{

```

try it online
> 3 votes

# Answer
# Funky, 95 bytes

```
n=>{print((n%2)?" ^":"   ^")fori=n i>0i--print({"  /!\\\n ^---","/!\\\n---^"}[i%2])print"   -"}

```

Try it online!
> 2 votes

# Answer
# JavaScript (ES6), ~~77~~ 74 bytes

```
n=>(s=`^
  /!\\
 ^---`,n%2?`   `+s:` ^`)+`
/!\\
---${s}`.repeat(n/2)+`
 -`

```

### Try it:

```
f=

n=>(s=`^
  /!\\
 ^---`,n%2?`   `+s:` ^`)+`
/!\\
---${s}`.repeat(n/2)+`
 -`
```

```
<input oninput=o.innerHTML=f(value)>
<pre id=o>
```
> 2 votes

# Answer
# Retina, ~~70~~ ~~68~~ 60 bytes

*thanks to @MartinEnder for -8 bytes*

```
.+
$*
r`11
21
1
¶  /!\¶ ^---
2
¶/!\¶---^
^¶( *)
$1 ^$&
$
¶ -

```

Try it online!
> 2 votes

# Answer
# Java 8, 104 bytes

```
n->{String r=n%2>0?"   ^\n":" ^\n";for(;n-->0;r+=n%2<1?"  /!\\\n ^---\n":"/!\\\n---^\n");return r+" -";}

```

**Explanation:**

Try it here.

```
n->{                       // Method with integer parameter and String return-type
  String r=                //  Result-String, starting at:
           n%2>0?          //  If the input is odd:
            "   ^\n"       //   Start the result at "   ^" + new-line
           :               //  Else (the input is even):
            " ^\n";        //   Start the result at " ^" + new-line
  for(;n-->0;              //  Loop the input amount of times
    r+=n%2<1?              //   If the current row is even:
        "  /!\\\n ^---\n"  //    Append the result-String with "  /!\" + new-line
                           //                                  " ^---" + new-line
       :                   //   Else (the current row is odd):
        "/!\\\n---^\n"     //    Append the result-String with "/!\" + new-line
                           //                                  "---^" + new-line
  );                       //  End of loop
  return r                 //  Return the result-String
          +" -";           //   + " -"
}                          // End of method

```
> 2 votes

# Answer
# Python 2, 73 bytes

```
lambda n:n%2*'  '+' ^%s\n -'%(-~n/2*r"""
/!\
---^
  /!\
 ^---""")[n%2*9:]

```

Try it online!

Golfing TFeld's solution.
> 2 votes

# Answer
# Python 3, 167 bytes

```
def f(n):
	g=[[" "]*5for _ in'  '*-~n];a=["^","/!\\","---"]
	for i in range(n):
		for r,R in zip(a,g[i*2:]):R[(i-n)%2*2+(r>"]"):]=r
	g[-2][1]="^";g[-1][1]="-";return g

```

Try it online!

-4 bytes thanks to Mr. Xcoder
-1 byte thanks to Jonathan Frech
> 1 votes

# Answer
# Python 2, 100 bytes

```
lambda n:n%2*'  '+' ^\n'+'\n'.join(['/!\\\n---^','  /!\\\n ^---'][i%2]for i in range(n,0,-1))+'\n -'

```

Try it online!
> 1 votes

# Answer
# SOGL V0.12, 25 bytes

```
 ^¶ -”.∫2%«I"X¬ΒNN┘y7¹‘∆ž

```

Try it Here!
> 1 votes

# Answer
# C (gcc), 87 bytes

```
f(n){for(puts(n%2?"   ^":" ^");n;)puts(n--%2?"  /!\\\n ^---":"/!\\\n---^");puts(" -");}

```

Try it online!
> 1 votes

# Answer
# Python 2, 82 bytes

```
def f(n):x=n%2;print' '*x*2,'^'+(-~n/2*"\n/!\\\n---^\n  /!\\\n ^---")[x*9:]+'\n -'

```

Try it online!
> 1 votes

# Answer
# 05AB1E, 42 bytes

```
É·>'^ú¶•2ÂŸ§'vôÅ•"-
 ^\!/"ÅвJ12ôIL<Rè`„ -J

```

Try it online or verify some more test cases.

**Minor 42 bytes alternative:**

```
É·ðú„^
•e
QΣœKΔ•"- ^
\!/"ÅвJ8₂‚£ILRè»…
 -J

```

Try it online or verify some more test cases.

**Explanation:**

```
É              # Check if the (implicit) input-integer is odd (1 if odd; 0 if even)
 ·             # Double that (2 if odd; 0 if even)
  >            # Increase it by 1 (3 if odd; 1 if even)
   '^         '# Push string "^"
     ú         # Pad it with the input%2*2+1 amount of leading spaces
¶              # Push a newline character "\n"
•2ÂŸ§'vôÅ•    '# Push compressed integer 193455283599881836
 "-\n ^\!/"Åв  # Convert it to custom base-"-\n ^\!/"
               # (which converts it to base-length and indices it into the string)
  J            # Join this list of characters together to a single string:
               #  "  /!\\n ^---\n/!\\n---^\n"
   12ô         # Split it into parts of size 12: ["  /!\\n ^---\n","/!\\n---^\n"]
      IL       # Push a list in the range [1, input]
        <      # Decrease each by 1 to make the range [0, input)
         R     # Reverse it to range (input, 0]
          è    # Index each into the pair of strings (0-based and modulair)
           `   # Pop and push all strings separated to the stack
„ -            # Push string " -"
J              # Join all strings on the stack together
               # (and output the result implicitly)

É·             # Same as above
  ðú           # Pad a space character with that many spaces
    „^\n       # Push string "^\n"
•e\nQΣœKΔ•     # Push integer 11080812880919929
"- ^\n\!/"ÅвJ  # Same as above: "/!\\n---^  /!\\n ^---"
8₂‚            # Push 8 and 26 paired together: [8,26]
   £           # Split the string into parts of that size: ["/!\\n---^","  /!\\n ^---"]
    IL         # Push a list in the range [1, input]
      R        # Reverse it to range [input, 1]
       è       # Index each into the pair of strings (0-based and modulair)
        »      # Join this list with newline delimiter
…\n -          # Push string "\n -"
J              # Join all strings on the stack together
               # (and output the result implicitly)

```

See this 05AB1E tip of mine (section *How to compress large integers?*) to understand why `•2ÂŸ§'vôÅ•` is `193455283599881836` and `•e\nQΣœKΔ•` is `11080812880919929`.
The compressed ASCII-string was generation with this 05AB1E tip.
> 1 votes

# Answer
# Ruby, 97 94 bytes

```
puts "  "*(a%2)+" ^";f=->n{puts""+["/!\\\n---^","  /!\\\n ^---"][n%2];(n>1)?f[n-1]:puts(" -")}

```

Try It Online!

I was unable to find a way to fit the entire thing in one function, so `f` is set to the lambda.

Based on TotallyHuman's Python answer.
> 1 votes

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


title: Find all reachable nodes in a graph

text:
# Question
Title: Find all reachable nodes in a graph
You are given a directed graph in an adjacency dictionary format. This can be whatever format is most natural for your language. For instance, in python, this would be a dictionary with keys of nodes and values which are lists of nodes which that node has an edge to. For instance:

```
G={1: [2, 3], 2: [3], 3: [1], 4:[2]}

```

Be reasonable. A dictionary of frozen sets is not allowed, even if it makes your code shorter. A list of lists is fine, if your language doesn't have dictionaries.

Your task is to implement a function that takes a directed graph and a starting node, and outputs all nodes reachable from the starting node. The output format is also flexible. A return value from a function is fine, so is print, etc.

Test case:

```
G={1: [2, 3], 2: [3], 3: [1], 4:[2]}
s=1

R(G,s)
{1,2,3}

```

Fewest characters wins. I will clarify if needed.

# Answer
> 8 votes
# Mathematica ~~63 40~~ 37

My earlier submission was incorrect. I had misinterpreted what `ConnectedComponents` returns. The present approach relies on Belisarius' suggestion to use`VertexOutComponent`. 3 additional chars saved by alephalpha.

The following generates an 11 by 11 adjacency matrix of 0's and 1's, where 1 indicates that the vertex with the row number is connected directly to the vertex corresponding to column number of the cell. (`SeedRandom` ensures that your matrix `a` will match mine.)

```
SeedRandom[21]
a = Array[RandomChoice[{0.9, 0.1} -> {0, 1}] &, {11, 11}];

```

---

## Example

(37 chars)

```
 AdjacencyGraph@a~VertexOutComponent~4

```

> {4, 1, 7, 8, 9, 3}

---

## Verifying

The directed graph displays how to reach vertices `{1, 7, 8, 9, 3}` from vertex 4.

```
AdjacencyGraph[a, ImagePadding -> 30, VertexLabels -> "Name"]

```

# Answer
> 4 votes
# Python 2.7 - 80 65

```
def R(G,s):
 k=a={s}
 while k:a=a|k;k|=set(G[k.pop()])-a
 print a

```

# Answer
> 4 votes
### GolfScript, 27 24 characters

```
{:G,{G{1$&},{)||}/}*}:C;

```

This code implements the operator `C` which takes starting node and graph on the stack and leaves a list of reachable notes on the stack after execution.

*Example (online):*

```
[1] [[1 [2 3]][2 [3]][3 [1]][4 [2]]] C
# returns [1 2 3]

```

# Answer
> 2 votes
# J - 19 15 char

J doesn't have a dictionary type, and is generally garbage with representing things the way people are used to in other languages. This is a bit idiosyncratic with how it represents things, but that's because J and graphs don't blend well, and not because I'm looking for optimal ways of representing directed graphs. But even if it doesn't count, I think it's a concise, interesting algorithm.

```
~.@(],;@:{~)^:_

```

This is a function which takes a graph on the left and a list of nodes to start with on the right.

Graphs are lists of boxed lists, and the nodes are indices into the list that represents the graph. J indexes from zero, so nodes are nonnegative integers, but you can skip 0 and pretend to have 1-based indexing by using an empty list (`''`) in the 0 place. (Indented lines are input to the J console, lines flush with the margin are output.)

```
   2 4;1 2 4;0;0 2;1   NB. {0: [2, 4], 1: [1, 2, 4], 2: [0], 3: [0, 2], 4:[1]}
+---+-----+-+---+-+
|2 4|1 2 4|0|0 2|1|
+---+-----+-+---+-+
   '';2 3;3;1;2        NB. {1: [2, 3], 2: [3], 3: [1], 4:[2]}
++---+-+-+-+
||2 3|3|1|2|
++---+-+-+-+
   '';'';2;9;1 7 8 9;3 6;4 8;7;'';3;'';7   NB. the big Mathematica example
+++-+-+-------+---+---+-++-++-+
|||2|9|1 7 8 9|3 6|4 8|7||3||7|
+++-+-+-------+---+---+-++-++-+

```

Lists of numbers are just space-separated lists of numbers. In general a scalar (just one number in a row) is not the same as a one-item list, but I use only safe operations that end up promoting scalars to one-item lists, so everything's cool.

The function explained (supposing we invoke as `graph ~.@(],;@:{~)^:_ nodes`):

* `{~` \- For each node in `nodes`, take the list of adjacent nodes from `graph`.
* `;@:` \- Turn the list of adjacencies into a list of nodes.
* `],` \- Prepend `nodes` to this list.
* `~.@` \- Throw out any duplicates.
* `^:_` \- Repeat this procedure with the same `graph` until it results in no change to the right hand argument, i.e. there are no new nodes to discover.

The verb in action:

```
   ('';2 3;3;1;2) ~.@(],;@:{~)^:_ (1)           NB. example in question
1 2 3
   f =: ~.@(],;@:{~)^:_                         NB. name for convenience
   (2 4;1 2 4;0;0 2;1) f 2
2 0 4 1
   ('';'';2;9;1 7 8 9;3 6;4 8;7;'';3;'';7) f 4  NB. Mathematica example
4 1 7 8 9 3

```

If you don't like this graph representation, here's a couple quick verbs for converting to/from adjacency matrices.

```
   a=:<@#i.@#        NB. adj.mat. to graph
   mat=:0,0,.0 1 1 0,0 0 1 0,1 0 0 0,:0 1 0 0
   mat               NB. adj.mat. for {1:[2,3],2:[3],3:[1],4:[2]}
0 0 0 0 0
0 0 1 1 0
0 0 0 1 0
0 1 0 0 0
0 0 1 0 0
   a mat
++---+-+-+-+
||2 3|3|1|2|
++---+-+-+-+
   A=:+/@:=&>/i.@#   NB. graph to adj.mat.
   A a mat
0 0 0 0 0
0 0 1 1 0
0 0 0 1 0
0 1 0 0 0
0 0 1 0 0

```

For anyone wondering why the graph is the left argument to the verb, it's because that's the general convention in J: control information on the left, data on the right. Consider list search, `list i. item`, and the sequential machine dyad, `machine ;: input`.

# Answer
> 2 votes
# APL (Dyalog Extended), 7 bytes

```
⌂search

```

Try it online!

A library function that does the job. Takes the graph on its left and the start node on its right, and gives the list of reachable nodes using breadth-first search.

Since APL has neither sets nor dicts, the closest input format is a nested vector of vectors like `(2 3)(3)(1)(2)`. And, just by coincidence, Dyalog APL's graph library uses this exact format as the representation for graphs.

Because a built-in is boring, here is another solution without it (which is still short):

# APL (Dyalog Unicode), 10 bytes

```
(∪/⊢,⌷⍨)⍣≡

```

Try it online!

Same input format and left/right argument order. Returns the same result, but nested once. Keeping one level of nesting throughout the `⍣≡`-loop gives several advantages in terms of golfing.

### How it works

```
(∪/⊢,⌷⍨)⍣≡  ⍝ Tacit infix function. left←graph, right←node
(      )⍣≡  ⍝ Repeat until the right arg converges...
     ⌷⍨     ⍝ Simulate following all possible edges from input node(s)
            ⍝ which gives a vector of nested vectors of nodes
   ⊢,       ⍝ Prepend the (nested) list of initial nodes
 ∪/         ⍝ Reduce by set union;
            ⍝ preserve the order of existing nodes by
            ⍝ having the input on the left end

Example run:
  graph←(2 3)(3)(1)(2) ⋄ node←1
  First iteration:
       ⌷⍨     ⊂2 3  ⍝ extract index 1 of graph
     ⊢,       1(2 3)
   ∪/         ⊂1 2 3
  (      )⍣≡  Converged? No.
  Second iteration:
       ⌷⍨     (2 3)(3)(1)  ⍝ extract indices 1, 2, 3 of graph
     ⊢,       (1 2 3)(2 3)(3)(1)
   ∪/         ⊂1 2 3
  (      )⍣≡  Converged? Yes, stop.

```

# Answer
> 1 votes
## Python 2.7 (using networkx) - 71

```
from networkx import*
single_source_shortest_path(DiGraph(G),s).keys()

```

**Sample Run**

```
>>> G={1: [2, 3], 2: [3], 3: [1], 4:[2]}
>>> s=1
>>> from networkx import*
>>> single_source_shortest_path(DiGraph(G),s).keys()
[1, 2, 3]

```

# Answer
> 1 votes
# JavaScript (ECMAScript 6) - 70 Characters

```
f=(G,s)=>{y=Set([s]);y.forEach(x=>G[x].forEach(z=>y.add(z)));return y}

```

**Test**

```
G={1: [2, 3], 2: [3], 3: [1], 4:[2]}
s=1
f(G,s)

```

Returns a set containing:

```
1,2,3

```

# Answer
> 1 votes
# Mathematica, 29 chars

```
{s}//.l_List:>(l⋃##&@@(l/.G))

```

### Example:

```
G = {1 -> {2, 3}, 2 -> {3}, 3 -> {1}, 4 -> {2}}; s = 1;
{s}//.l_List:>(l⋃##&@@(l/.G))

```

> {1, 2, 3}

# Answer
> 1 votes
# Python – ~~54~~ 52 + 7 + 7

```
def R(G,s,A):
    A|={s}
    for n in set(G[s])-A:R(G,n,A)

```

`R` needs to be called with an empty set as an additional argument. This set contains the output, when `R` has finished. Example of usage:

```
G = {1: [2, 3], 2: [3], 3: [1], 4:[2]}
A=set()
R(G,1,A)
print A

```

If you consider this way of output cheating, keep in mind that it’s very normal in C, for example. Anyway, you may want to charge 7 additional chars for the intialisation of the empty set (`A=set()`) and 7 for the `print` line.

# Answer
> 1 votes
# K4 , 12 bytes

The code is:

```
{?,/x,G x}/1

```

Here's an example of its use:

```
  G:1 2 3 4!(2 3;3;1;2)
  {?,/x,G x}/1
1 2 3
  H:(!12)!(();();2;9;1 7 8 9;3 6;4 8;7;();3;();7)
  {?,/x,H x}/4
4 1 7 8 9 3

```

input is a dictionary from int to int or list of int

the basic op is `G s`, retrieve the child nodes for `s`

this is then stuffed into the built-in convergence operator `/`

the rest is to, at each stage, prepend the parent node, flatten the results down to a vector, and dedupe them -- this is needed to make the answer actually converge

btw, for an extra three characters, you can have *all* the reachability lists:

```
  {G(?,/,)'G x}/G
1 2 3 4!(2 3 1;3 1 2;1 2 3;2 3 1)
  {H(?,/,)'H x}/H
0 1 2 3 4 5 6 7 8 9 10 11!(();();,2;9 3;1 7 8 9 3;3 6 9 4 8 1 7;4 8 1 7 9 3;,7;();3 9;();,7)

```

this is the same general idea, applied to the basic op of `G G`

# Answer
> 0 votes
## Python, 72 chars

```
def R(G,s):
 r=[s]
 for i in G:r+=sum((G[x]for x in r),[])
 print set(r)

```

Terribly inefficient because nodes can appear in `r` multiple times. Fortunately, not a judging criterion.

# Answer
> 0 votes
# Haskell, 64 bytes

```
import Data.List
n#v=nub$id=<<length n`take`iterate(>>=(n!!))[v]

```

Takes input as a zero-based list of lists, try it online!

### Explanation / Ungolfed

The term `vertices >>= (adjacencyList !!)` takes a list of `vertices`, looks up all reachable vertices of them and returns them as a list.

So we repeatedly do this starting with the input vertex `[v]`

```
                       iterate(>>=(n!!))[v]

```

take as many elements from that list as there are nodes in the graph

```
         length n`take`

```

concatenate the result

```
    id=<<

```

and finally remove all the duplicates

```
nub$

```

.

# Answer
> 0 votes
# Java 10, 130 characters

A curried lambda that takes the graph as a `Map<Integer, List<Integer>>` and an `int` start node. Output is returned as a `Set<Integer>`.

```
import java.util.*;

```

```
g->s->{var o=new TreeSet();o.add(s);for(var x:g.keySet())for(var n:new TreeSet(o))o.addAll(g.get(n));return o;}

```

Try It Online

This carries out a slightly stupid breadth-first search just past a maximum possible non-cyclical path length (the number of graph nodes).

# Answer
> 0 votes
## Clojure, 52 bytes

```
#(nth(iterate(fn[A](set(mapcat % A)))[%2])(count %))

```

This implicitly assumes that all nodes have outgoing vertices.

## ~~54 bytes~~

```
#(loop[A[%2]B[]](if(= A B)A(recur(set(mapcat % A))A)))

```

The nifty part is the `(mapcat % A)`, which uses the input argument `{1 [2, 3], 2 [3], 3 [1], 4 [2]}` as a function (given a key it returns the corresponding value) and concatenates all the ids together. Then it is just a matter of iterating this procedure until we have converged.

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


title: Find the maximum flow

text:
# Question
Title: Find the maximum flow
Given a directed network, with a single source and a single sink, it is possible to find the maximum flow through this network, from source to sink. For example, take the below network, \\$G\\$:

Here, the source is node **0** and the sink **5**. We can see, from the minimum cut-maximum flow theorem, that the maximum flow through this network is \\$70\\$ (given by the cut \\$\\{0\\} / \\{1, 2, 3, 4, 5\\}\\$)

### Minimum cut-maximum flow theorem

For a network, a cut is a line that divides a network in two, with the sink and source in different halves. For the above network, one such cut, \\$C\\$, is \\$\\{0, 1, 3\\} / \\{2, 4, 5\\}\\$. Every cut has a value, which depends on which edges in the network is passes through. The above cut, \\$C\\$, passes through the edges \\$1-2, 3-2\\$ and \\$3-4\\$, which have the weights \\$40, 45\\$ and \\$30\\$ respectively. The value of a cut is defined, for the set of crossed edges \\$S\\$, as

> The sum of the weights of all the edges in \\$S\\$ which pass **from** the source **to** the sink

Therefore, the value of \\$C\\$ is \\$40 + 45 + 30 = 115\\$ but the value of the cut \\$\\{0, 3\\} / \\{1, 2, 4, 5\\}\\$ would be \\$20 + 45 + 30 = 95\\$ (Note that \\$10\\$ is not included as it passes from the sink towards the source).

The minimum cut-maximum flow theorem states that

> The maximum flow through a network is equal to the minimum value of all cuts in that network

The minimum cut of all the cuts in \\$G\\$ is \\$\\{0\\} / \\{1, 2, 3, 4, 5\\}\\$ which has a value of \\$70\\$. Therefore, the maximum flow through \\$G\\$ is also \\$70\\$.

## Challenge

Write a function of full program that, when given a directed network as input, outputs the maximum flow through that network. You may, of course, use any method or algorithm to compute the maximum flow, not just the minimum cut-maximum flow theorem. This was simply included as one method.

You may take input in any convenient method or format, such as an adjacency matrix, a list of nodes and edges, etc. The input will always have 2 or more nodes, will be a connected graph, and will have exactly 1 source and 1 sink. The weights of the edges will always be natural numbers, as will the maximum flow. The output should reflect this, and can also be in any convenient method or format.

This is , so the shortest code, in bytes, wins.

## Test cases

Both the network and the adjacency matrix are included for each test case.

Network \\$G\\$ (above):

```
[[ 0, 20,  0, 50,  0,  0],
 [ 0,  0, 40, 10,  0,  0],
 [ 0,  0,  0,  0, 25, 25],
 [ 0,  0, 45,  0, 30,  0],
 [ 0,  0,  0,  0,  0, 50],
 [ 0,  0,  0,  0,  0,  0]] -> 70 ({0} / {1, 2, 3, 4, 5})

```

---

```
[[ 0, 10, 17,  0,  0,  0,  0],
 [ 0,  0,  0,  2, 13,  0,  0],
 [ 0,  5,  0,  0,  4,  8,  0],
 [ 0,  0,  0,  0,  0,  0, 20],
 [ 0,  0,  0, 18,  0,  0,  0],
 [ 0,  0,  0,  0,  1,  0,  7],
 [ 0,  0,  0,  0,  0,  0,  0]] -> 27 (Multiple cuts e.g. {0, 1, 2} / {3, 4, 5, 6})

```

---

```
[[ 0,  6,  2,  7,  4,  0,  0,  0],
 [ 0,  0,  0,  0,  0, 10,  0,  0],
 [ 0,  8,  0,  0,  0,  0,  9,  4],
 [ 0,  0, 11,  0,  0,  0,  0,  0],
 [ 0,  0,  0,  5,  0,  0,  0,  0],
 [ 0,  0, 13,  0,  0,  0,  0, 16],
 [ 0,  0,  0, 14,  0,  0,  0, 12],
 [ 0,  0,  0,  0,  0,  0,  0,  0]] -> 19 ({0} / {1, 2, 3, 4, 5, 6, 7})

```

---

```
[[ 0, 40, 50,  0,  0,  0,  0,  0,  0],
 [ 0,  0,  0, 30, 10,  0,  0,  0,  0],
 [ 0,  0,  0, 40,  0,  0, 10,  0,  0],
 [ 0,  0,  0,  0, 15, 10,  0,  0,  0],
 [ 0,  0,  0,  0,  0,  0,  0,  0, 20],
 [ 0,  0,  0,  0,  0,  0, 15, 20,  0],
 [ 0,  0,  0,  0,  0,  0,  0, 30,  0],
 [ 0,  0,  0,  0,  0,  0,  0,  0, 50],
 [ 0,  0,  0,  0,  0,  0,  0,  0,  0]] -> 40 ({0, 1, 2, 3, 4} / {5, 6, 7, 8})

```

---

```
[[ 0, 5, 8, 3, 3, 7, 0, 0, 0, 7],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 4],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 9],
 [ 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
 [ 0, 0, 0, 0, 0, 0, 0, 4, 0, 0],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 6, 0],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 6],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 5],
 [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] -> 28 ({0, 1, 3, 5, 8} / {2, 4, 6, 7, 9})

```

---

```
[[0, 5],
 [0, 0]] -> 5

```

# Answer
# Charcoal, ~~37~~ ~~36~~ 34 bytes

```
Ｉ⌊ＥＥＸ²⁻Ｌθ²↨⁺Ｘ²⊖Ｌθ⊗ι²ΣＥθ∧§ιμΣΦλ¬§ιξ

```

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

```
   Ｅ…Ｘ²⁻Ｌθ²Ｘ²⊖Ｌθ                    Loop over all cuts...
  Ｅ             ↨⊗ι²                ... converted to base 2
                    ΣＥθ∧§ιμ         Sum rows in source cut
                           ΣΦλ¬§ιξ  Sum columns in sink cut
Ｉ⌊                                  Print the minimum

```

The range is constructed so that the base 2 values are `100...000` to `111...110` whereby the `1` bits refer to the source cut (thus the left bit, which is actually element `0`, is the source itself) and the `0` bits refer to the sink cut.
> 7 votes

# Answer
# JavaScript (ES6), 96 bytes

```
f=(m,k=1,b)=>k*2>>m.length?b:f(m,k+2,m.map((r,y)=>r.map((v,x)=>t+=k>>y&~k>>x&1&&v),t=0)|t>b?b:t)

```

Try it online!

### Commented

```
f = (                   // f is a recursive function taking:
  m,                    //   m[] = adjacency matrix
  k = 1,                //   k = counter, initialized to 1 and always odd
  b                     //   b = best value so far, initially undefined
) =>                    //
  k * 2 >> m.length ?   // if k is greater than or equal to 2 ** (m.length - 1):
    b                   //   stop the recursion and return b
  :                     // else:
    f(                  //   do a recursive call to f:
      m,                //     pass m[] unchanged
      k + 2,            //     add 2 to k
                        //     we make sure that k remains odd so that the source
                        //     is always included in the 1st half of the cut
      m.map((r, y) =>   //     for each row r[] at position y in m[]:
        r.map((v, x) => //       for each value v at position x in r[]:
          t +=          //         update t:
            k >> y &    //           if the y-th bit in k is set
            ~k >> x & 1 //           and the x-th bit in k is not set:
            && v        //             add v to t, otherwise add nothing
        ),              //       end of inner map()
        t = 0           //       start with t = 0
      ) |               //     end of outer map()
      t > b ? b : t     //     if t <= b or b is still undefined, update b to t
    )                   //   end of recursive call

```
> 6 votes

# Answer
# 05AB1E, 27 bytes

```
ā2.ŒʒD{Q}<ʒZ%PË}εнèøyθè˜O}ß

```

Takes the input in a similar format as the test cases in the challenge description.

Try it online or verify all test cases.

**Explanation:**

```
ā          # Push a list in the range [1, (implicit) input-length]
           # (without popping the input itself)
 2.Œ       # Get all partitions of two parts of this list
           # (note: this also contains partitions with empty parts, but that doesn't
           #  matter, since the second filter also takes care of those)
    ʒ   }  # Filter out partitions where the first item of the first part is larger
           # than the first item of the second part, by:
     D{    #  Sorting the two parts of a copy (based on their first items)
       Q   #  Check that the partition and sorted partition are still the same
<          # Now decrease the values of each remaining partition by 1
 ʒ    }    # Filter out partitions where the sink and source are in the same part, by:
  Z        #  Getting the flattened maximum (without popping)
   %       #  Modulo this maximum on each value,
           #  this causes this maximum (the sink) to become 0 as well
    P      #  Take the product of both partitions (empty parts become 1)
     Ë     #  And check that both products are the same (thus both 0)
ε        } # Now that we have all valid cuts left, we map the partitions to:
 н         #  Get the first part of the current partition
  è        #  Index its values into the (implicit) input-matrix
   ø       #  Zip/transpose; swapping rows/columns
    yθ     #  Get the last part of the current partition
      è    #  Index its values into this transposed list of lists
       ˜O  #  And get the flattened sum
ß          # After the map: pop and push the minimum
           # (after which it is output implicitly as result)

```

Try it online to see a step-by-step input to output process.
> 3 votes

# Answer
# Jelly, 24 bytes

```
JṖŒPỊẸ$Ƈ,ḟ@Œp;U$ʋ€Jœị⁸§Ṃ

```

A monadic Link accepting a list of lists of non-negative integers (an adjacency matrix), which yields the maximal flow integer.

**Try it online!** Or see the test-suite.

### How?

Implements the minimum-cut maximal-flow method.

```
JṖŒPỊẸ$Ƈ,ḟ@Œp;U$ʋ€Jœị⁸§Ṃ - Link: adjacency matrix, A (n by n)
J                        - range of length (A) -> [1,2,3,...,n]
 Ṗ                       - pop -> [1,2,3,...,n-1]
  ŒP                     - power-set (all posible selections)
       Ƈ                 - keep only those for which:
      $                  -   last two links as a monad:
    Ị                    -     insignificant (true for 1, false for 2,3,...)
     Ẹ                   -     any? (i.e. only the selections containing a 1)
                 €       - for each:
                  J      -   with range of length (A) as the right argument of
                ʋ        -   last four links as a dyad - i.e. f(selections, J)
          @              -     with swapped arguments:
         ḟ               -       filter discard those from (J) which are in (selection)
        ,                -     (selection) pair (that) - i.e. a cut
           Œp            -     Cartesian product - i.e. all pairs of nodes where lines
                                                   could be present across this cut
               $         - last two links as a monad:
              U          -   reverse each
             ;           -   concatenate (giving us the pairs of nodes in both orders)
                     ⁸   - chain's left agument, A
                   œị    - (pair) multi-dimensional index into (A) (vectorises)
                      §  - sum each resulting list of weights
                       Ṃ - minimum

```
> 1 votes

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


title: bandit24 brute forcing program

text:
# Question
Title: bandit24 brute forcing program
I was doing the bandit wargame from overthewire.org and because I am a script kiddie, I googled the answer for level 24.

```
password="UoMYTrfrBFHyQXmg6gzctqAwOmw1IohZ"
for i in {0000..9999}
//looping to try any possible pin code
do
echo $password' '$i >> wordlist.txt
//save password and possible pin code into wordlist
done

```

I saw the bash script, and thought, "Well I couldn't have done that because I'm not good at bash." but then I realized that this problem could be done in other languages.

The challenge is simple.

1. Pipe the password in from stdin.
2. Append a space in-between the password and the pin or output it separately
3. Output all PIN combinations. Make sure that there are 4 digits outputted.
4. BONUS flush the output after each line. This is done automatically with `std::endl`.

I went ahead and did it in C++

```
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
        string key; //1
        getline(cin, key); //I heard that std::getline is
        //only standard for linux, so for practical
        //purposes use cin.getline(char*,size)
        for(int i = 0; i < 10000; i++){   //3
                cout << key << setfill('0') << ' ' //2
                << setw(4) << i << endl;  //4
        }
        return 0;
}

```

Obviously it can do better than 301 bytes, but you get the gist.

Also any language is acceptable as long as it can produce the same formatted strings separated by new lines or line breaks.

# Answer
> 2 votes
# 05AB1E, ~~9~~ 7 bytes

```
žh4ã€‚»

```

Try it online.

**Explanation:**

```
žh       # Push builtin string "0123456789"
  4ã     # Get the cartesian product of 4: ["0000","0001",...,"9998","9999"]
    €    # Map each string to:
     ‚   #  Pair it with the (implicit) input-string
      »  # Join each inner list by spaces, and then all strings by newlines
         # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Charcoal, 15 bytes

```
Ｅ×χφ⁺⁺θ ⭆◧Ｉι⁴Σλ

```

Try it online! Link is to verbose version of code. Test case uses shortened password to avoid TIO output limit. Explanation:

```
 ×χφ            Multiply predefined variables 10 with 1000
Ｅ               Map over implicit range
           ι    Current index
          Ｉ     Cast to string
         ◧  ⁴   Left-pad to width literal `4`
        ⭆    Σλ Convert non-digits to zeros
    ⁺⁺θ         Concatenate with the password and a space
                Implicitly output each entry on its own line

```

# Answer
> 2 votes
# Pyth, 12 bytes

```
V^jkUT4++QdN

```

Try it online!

## Explanation

```
V^jkUT4++QdN
V             : For n in
 ^    4       : repeated cartesian product 4 times of
  jkUT        : "0123456789"
       ++QdN  : output input + ' ' + n

```

# Answer
> 1 votes
# Octave, 33 bytes

```
@(a)fprintf([a,' %04u\n'],0:9999)

```

Try it online!

# Answer
> 1 votes
# Ruby, 32 bytes

```
10000.times{|i|puts$_+" %04i"%i}

```

Suggested by Dingus. Try it online!

```
->a{(0..9999).to_a.map(&:to_s).map{|x|a+" "+x.rjust(4,"0")}.join("\n")};

```

Try it online!

# Answer
> 1 votes
# Japt `-R`, 11 bytes

Takes input as a single element array. If we can use comma as the delimiter instead of space, the last 3 characters can be removed.

```
ïL²o ùT4)m¸

```

Try it

# Answer
> 1 votes
# Jelly, (8?) 10 bytes

8 if we may output delimited by multiple spaces (replace `K€Y` with `G`).

```
ØDṗ4ɠ,ⱮK€Y

```

**Try it online!**

### How?

```
ØDṗ4ɠ,ⱮK€Y - Main Link: no arguments
ØD         - digit characters = "0123456789"
   4       - four
  ṗ        - Cartesian power -> list of all pins
    ɠ      - read a line from STDIN
      Ɱ    - map (across the pins) applying:
     ,     -   pair
       K€  - join each with a space character
         Y - join with newlines
           - implicit print

```

---
Tags: code-golf
---


title: Number of domino tilings

text:
# Question
Title: Number of domino tilings
Write a program or function that given positive *n* and *m* calculates the number of valid distinct domino tilings you can fit in a *n* by *m* rectangle. This is sequence A099390 in the *Online Encyclopedia of Integer Sequences*. You may take input in as function argument(s), CLA or on stdin, in any reasonable format. You must return or print a single integer as output.

Each tiling must not leave any gaps, and every distinct tiling is counted, including rotations, reflections, etc. For example, the tilings for 2x3 are:

```
|--    |||    --|
|--    |||    --|

```

Example inputs/outputs:

```
1,  9 -> 0
2,  2 -> 2
2,  3 -> 3
4,  4 -> 36
4,  6 -> 281
6,  6 -> 6728
7, 10 -> 53175517

```

Your program should theoretically work for any *n* and *m*, but if your program requires too much memory or your data type overflows it's excused. Your program must work correctly for any *n, m* \<= 8 however.

---

Shortest code in bytes wins.

# Answer
> 3 votes
# Pyth, ~~30~~ 29 bytes

```
L?bsmy-tb]dfq1.a-VThbb1y*FUMQ

```

Try it online: Demonstration / Test Suite

All example inputs run in the online compiler. The last one takes a few seconds though.

### Explanation:

In my code I'll define a recursive function `y`. The function `y` takes a list of 2D-coordinates and returns the number of different domino tilings using these coordinates. E.g. `y([[0,0], [0,1]]) = 1` (one horizontal domino), `y([[0,0], [1,1]]) = 0` (coordinates are not adjacent) and `y([[0,0], [0,1], [1,0], [1,1]]) = 2` (either two horizontal or two vertical dominoes). After defining the function I'll call it with all coordinates `[x,y]` with `x in [0, 1, m-1], y in [0, 1, n-1]`.

How does the recursive function work? It's quite simple. If the list of coords is empty, there is exactly one valid tiling and `y` returns `1`.

Otherwise I take the first coordinate in the list `b[0]`, and search the remaining coordinates for a neighbors. If there is no neighbor to `b[0]`, then there is no tiling possible, therefore I return 0. If there is one or more neighbors, then the number of tilings is (the number of tilings where I connect `b[0]` with the first neighbor via a domina, plus the number of tilings where I connect `b[0]` with the second neighbor, plus ...) So I call the function recursively for each neighbor with the shortened list (by removing the two coords `b[0]` and neighbor). Afterwards I sum up all results and return them.

Because of the order of the coords there are always only two neighbors possible, the one on the right side and the one below. But my algorithm doesn't care about that.

```
                          UMQ  convert the input numbers into ranges
                        *F     Cartesian product (coords of each square)
L                              define a function y(b):
 ?b                              if len(b) > 0:
           f         b             filter b for squares T, which satisfy:
              .a-VThb                Euclidean distance between T and b[0]
            q1                       is equal to 1 (direct neighbors)
    m                              map each neighbor d to:
      -tb]d                          remove d from b[1]
     y                               and call recursively y with the rest
   s                               sum all those values and return them
                                 else:
                      1            return 1 (valid domino tiling found)
                       y*FUMQ  Call y with all coords and print the result

```

# Answer
> 3 votes
# Matlab, 292

I am sure this can be shortened a lot just by porting it into another language.

The basic idea is bruteforcing: I came up with kind of an enumeration of all ways how to place `m*n/2` domino bricks on an `m*n` board. But this enumeration also includes many invalid tilings (bricks that overlap or go outside of the board.) So the program constructs all those tilings, and only counts the valid ones. The runtime complexity is about `O(2^(m*n/2) * m*n)`. Memory is not a problem for the `8x8` as it only needs `O(m*n)` memory. But the time needed for `8x8` is about 20 days.

Here the fully commented version that explains what is going on.

PS: If anyone knows how to make the Matlab syntax highlighting work, please include the corresponding tag in this answer!

```
function C=f(m,n)
d = ceil(m*n/2);%number of dominoes
%enumeration: %the nth bit in the enumeration says whether the nth
% domino pice is upright or not. we enumerate like this:
% firt piece goes top left:
% next piece goes to the left most column that has an empty spot, in the
% top most empty spot of that column
C=0;%counter of all valid tilings
for e=0:2^d-1 %go throu all enumerations
    %check whether each enumeration is valid
    A = ones(m,n);
    %empty spots are filled with 1
    %filled spots are 0 (or if overlapping <0)
    v=1;%flag for the validity. hte grid is assumed to be valid until proven otherwise
    for i=1:d %go throu all pieces, place them in A
        %find the column where to place:
        c=find(sum(A)>0,1);
        %find the row where to place:
        r=find(A(:,c)>0,1);
        %find direction of piece:
        b=de2bi(e,d);
        if b(i)
            x=0;y=1;
        else
            x=1;y=0;
        end
        %fill in the piece:
        try
            A(r:r+y,c:c+x)=A(r:r+y,c:c+x)-1;
        catch z
            v=0;break;
        end
        %check whether A has no overlapping pieces
        if any(A(:)<0)
            v=0;break;
        end
    end
    %if valid, count it as valid
    if v && ~norm(A(:))
        disp(A)
        C=C+1;
    end
end

```

Here the fully golfed one:

```
function C=f(m,n);m=4;n=6;d=ceil(m*n/2);C=0;for e=0:2^d-1;A=ones(m,n);v=1;for i=1:d;c=find(sum(A)>0,1);r=find(A(:,c)>0,1);b=de2bi(e,d);if b(i);x=0;y=1;else;x=1;y=0;end;try;A(r:r+y,c:c+x)=A(r:r+y,c:c+x)-1;catch z;v=0;break;end;if any(A(:)<0);v=0;break;end;end;if v && ~norm(A(:));C=C+1;end;end

```

# Answer
> 3 votes
# APL (Dyalog Extended), 26 bytes

```
{⍎0⍕√|×/⌾/¨2×2○○,⍵}⍳÷∘⊂1∘+

```

Try it online!

A monadic tacit function that takes a 2-element vector `n m` as its sole argument.

A port of fireflame241's Python answer, and in turn an implementation of the formula:

$$ T(n,k)^2 = \left| \prod^n\_{a=1}{\prod^k\_{b=1}{2 \cos \frac{a\pi}{n+1}+2i \cos \frac{b\pi}{k+1}}} \right| $$

Turns out that the results before rounding are pretty accurate (under `1e-14` relative error for the test cases), except when the result is expected to be zero.

### How it works

```
{⍎0⍕√|×/⌾/¨2×2○○,⍵}⍳÷∘⊂1∘+  ⍝ input←n m
                   ⍳        ⍝ 2D array of all pairs of 1..n , 1..m
                    ÷∘⊂     ⍝ divided by wrapped pair of
                       1∘+  ⍝ (n+1)(m+1)
{               ,⍵}  ⍝ Ravel the 2D array, giving a vector of pairs
           2×2○○     ⍝ 2×cos(pi × each number)
        ⌾/¨          ⍝ Convert each pair x,y to x + yi
      ×/  ⍝ Product of all complex numbers
     |    ⍝ Abs
    √     ⍝ Sqrt
 ⍎0⍕      ⍝ Round the number by converting to string with
          ⍝ zero digits under decimal point, then evaling it back

```

# Answer
> 2 votes
# C89, 230 bytes

```
f(n,m,b)int*b;{int s,i;s=i=0;
while(b[i])if(++i==n*m)return 1;
if(i/n<m-1){b[i]=b[i+n]=1;s+=f(n,m,b);b[i]=b[i+n]=0;}
if(i%n<n-1&&!(b[i]|b[i+1])){b[i]=b[i+1]=1;s+=f(n,m,b);b[i]=b[i+1]=0;}
return s;}
g(n,m){int b[99]={};return f(n,m,b);}

```

For readability I handwrapped this answer - all newlines can safely be removed to get to 230 bytes.

Defines a function `int g(int n, int m)` that returns the number of tilings. It uses a helper function `f` that iterates over all valid tilings by placing one domino, recursing, and then removing the domino on a shared board.

# Answer
> 1 votes
# JavaScript (ES7),  ~~149 ... 145~~  142 bytes

Expects `(n)(m)`.

```
m=>g=(n,a=[...Array(N=2**m-1).fill(0),1])=>n?g(n-1,a.map((_,i)=>a.reduce((p,c,k)=>p+c*!(h=(x,y)=>y&~x|(x?h(x>>1,x&!y):~k&~i&N))(k&i),0))):a[N]

```

Try it online!

### How?

I've described the algorithm in my Python answer to *Domino Recurrence Generator*.

The main difference is that it's shorter in JS to combine both state compatibility tests into the following recursive function than to use a regular expression.

```
( h = (x, y) =>
    y & ~x | (
      x ?
        h(x >> 1, x & !y)
      :
        ~k & ~i & N
    )
)(k & i)

```

# Answer
> 1 votes
# Python 3.8 (pre-release), ~~133~~ ~~121~~ 115 bytes

```
lambda m,n:round(abs(prod(2*cos((i//n+1)*pi/-~m)+2j*cos((i%n+1)*pi/-~n)for i in range(m*n)))**.5)
from math import*

```

Try it online!

(Python 3.8 adds `math.prod` for product)

*-12 bytes thanks to @Bubbler*

Implements the following formula (from OEIS A187596):

```
T(n,k)^2 = absolute value of Prod(Prod( 2*cos(a*Pi/(n+1)) + 2*i*cos(b*Pi/(k+1)), a = 1..n), b = 1..k), where i = sqrt(-1)

```

Since this multiplies (floating-point) complex numbers together, this loses precision for sufficiently large `n`, which is permitted by the challenge rules (effectively, data type overflows).

# Answer
> 0 votes
# Python 243

I opted for a brute force approach:

* generate m\*n/2 directions;
* try and fit the domino on the m\*n board.

If they all fit and no spaces are left we have a valid entry.

Here is the code:

```
import itertools as t
m,n=input()
c,u=0,m*n
for a in t.product([0,1],repeat=u/2):
 l,k,r,h=[' ',]*u,0,'-|',[1,m]
 for t in a:
  l[k]=r[t]
  k+=h[t]
  if k%m<m and k/m<n and l[k]==' ':l[k]=r[t]
  k=''.join(l).find(' ',1)
 if k<0:c+=1
print c

```

---
Tags: code-golf, combinatorics, tiling
---


title: Domino Recurrence Generator

text:
# Question
Title: Domino Recurrence Generator
## Challenge

We once had a challenge to count domino tilings of m by n grid, and we all know that, for any fixed number of rows, the number of domino tilings by columns forms a linear recurrence. Then why not have a challenge to compute **the linear recurrence**?!

Let's define \\$D\_m(n)\\$ as the number of domino tilings on a grid of \\$m\\$ rows and \\$n\\$ columns. Then the task is: given a single integer \\$m \ge 1\\$ as input, **output the linear recurrence relation for** \\$D\_m(n)\\$.

If the relation has order \\$k\\$ (that is, \\$D\_m(n+k)\\$ depends on \\$k\\$ previous terms), you need to output the coefficients \\$a\_i\\$ of the recurrence relation

$$ D\_m(n+k)=a\_{k-1}D\_m(n+k-1) + a\_{k-2}D\_m(n+k-2) + \cdots + a\_0 D\_m(n) $$

in the order of \\$a\_0\\$ to \\$a\_{k-1}\\$ or the reverse. There are infinitely many correct such relations; you don't need to minimize the order of the relation. **But,** to ensure that the result is at least minimally useful, **the order \\$k\\$ cannot exceed \\$2^m\\$ for any input value of \\$m\\$.**

(Side note: An actual sequence is defined only if the initial \\$k\\$ terms are given along with the recurrence equation. That part is omitted for simplicity of output, and to give incentive to approaches not using the brute-forced terms.)

Note that, for odd \\$m\\$, every odd-column term will be zero, so you will get a recurrence different from the OEIS entries which strip away zeroes (e.g. 3 rows, 5 rows, 7 rows).

Standard rules apply. The shortest code in bytes wins.

## Examples

Here are the representations from the OEIS, adjusted for odd \\$m\\$. Initial terms start at \\$D\_m(0)\\$, and the coefficients are presented from \\$a\_{k-1}\\$ to \\$a\_0\\$. Again, your program only needs to output the coefficients. To empirically check the correctness of your output of length \\$k\\$, plug in the \\$k\\$ initial terms from the respective OEIS entry, and see if the next \\$k\\$ terms agree.

```
m = 1
Initial terms [1, 0]  # D(0) = 1, D(1) = 0
Coefficients  [0, 1]  # D(n+2) = D(n)

m = 2
Initial terms [1, 1]
Coefficients  [1, 1]

m = 3
Initial terms [1, 0, 3, 0]
Coefficients  [0, 4, 0, -1]  # D(n+4) = 4D(n+2) - D(n)

m = 4
Initial terms [1, 1, 5, 11]
Coefficients  [1, 5, 1, -1]

m = 5
Initial terms [1, 0, 8, 0, 95, 0, 1183, 0]
Coefficients  [0, 15, 0, -32, 0, 15, 0, -1]

m = 6
Initial terms [1, 1, 13, 41, 281, 1183, 6728, 31529]
Coefficients  [1, 20, 10, -38, -10, 20, -1, -1]

```

## Possible approaches

There is at least one way to find the recurrence without brute forcing the tilings, outlined below:

1. Compute the transition matrix \\$A\\$ of \\$2^m\\$ states, so that the target sequence is in the form of \\$D\_m(n) = u^T A^n v\\$ for some column vectors \\$u,v\\$.
2. Find the characteristic polynomial or minimal polynomial of \\$A\\$ as

$$x^k - a\_{k-1}x^{k-1} - a\_{k-2}x^{k-2} - \cdots - a\_0 $$

3. Then the corresponding recurrence relation is

$$s\_{n+k} = a\_{k-1}s\_{n+k-1} + a\_{k-2}s\_{n+k-2} + \cdots + a\_0s\_n$$

An example algorithm of computing the minimal polynomial of a matrix can be found on this pdf.

(Of course, you can just brute force the domino tilings for small \\$n\\$ and plug into a recurrence finder.)

# Answer
> 5 votes
# APL (Dyalog Unicode), 72 bytes

```
{⍵=1:⍳2⋄(2*⌈⍵÷2)(⌷⌹⍉⍤↑)⍉L↑⍉↑,¨+.×\(L←2*⍵)⍴⊂∘.((0∊+)⍱1∊2|×≢¨⍤⊆⊣)⍨⍸1⍴⍨⍵⍴2}

```

Try it online! (uses a polyfill for ⍤ since TIO is not updated to 18.0 yet)

Requires `⎕pp←2` (implicit rounding of output) and `⎕IO←0` (0-indexing).

We compute a transition matrix, then use the approach listed in S. Białas and M.Białas to find the minimum polynomial and hence the recurrence relation.

### Defining the Transition Matrix

Each possible binary fill of a column of \\$m\\$ cells is one state, so there are \\$2^m\\$ states.

For `m=3`, one example state (`1 0 0`) is

```
█
▒
▒

```

The first cell is filled (it is the right side of a horizontal domino sticking out from the previous column), but the second and third cells are empty. This could occur e.g. as the second column in the following tiling (`n=4`, `3×4` grid):

```
━━┃┃
┃┃┃┃
┃┃━━

```

When considering state transitions, we have to be careful to avoid double counting.

My approach is to require full horizontal dominos to be placed whenever possible, then vertical dominos can optionally be placed in the next state's column.

For example, if the current state is `1 0 0`:

```
█
▒
▒

```

then we force horizontal dominos on the bottom two rows

```
█▒
━━
━━

```

so the next state would have to be `0 1 1`:

```
▒
█
█

```

This rule guarantees the current column to be filled in completely. In addition, it avoids double-counting transitions because it never places vertical dominos in the current column.

Vertical dominos go in the next column. There is no space for vertical dominos in the past example. As an example where vertical dominos can be placed, take the current state to be `1 1 1`:

```
█▒
█▒
█▒

```

One possibility would be to place no vertical dominos at all, so `1 1 1 → 0 0 0` is a valid state transition.

In addition, a vertical domino can be placed in either of two positions:

```
█┃        █▒
█┃   or   █┃
█▒        █┃

```

so `1 1 1 → 1 1 0` and `1 1 1 → 0 1 1` are valid state transitions.

### Obtaining the Recurrence from the Transition Matrix.

The paper describes the approach well, but I modified it a little while golfing.

As given, the problem is to find coefficients \\$a\_i\\$ for a given recurrence order \\$k\\$ such that, for all \\$n\\$¸

$$a\_0 D\_m(n) + a\_1 D\_m(n+1) + \cdots + a\_{k-1}D\_m(n+k-1) = D\_m(n+k)$$

With regards to powers of the transition matrix \\$A\\$, this can be rewritten as finding coefficients $c\_i$ such that

$$c\_1 A^1 + c\_2 A^2 + \cdots + c\_k A^k = A^{k+1}$$

(the paper starts with \\$A^0=I\_L\\$, but that is expensive in terms of bytes)

Let \\$L=2\*m\\$ be the width (and height) of the transition matrix \\$A\\$. Denoting the entries of \\$A^i\\$ as \\$a\_{11}^{(i)}, a\_{12}^{(i)}, \ldots a\_{LL}^{(i)}\\$, we can rewrite the recurrence as \\$L^2\\$ equations

$$ \begin{align\*} c\_1 a\_{11}^{(1)} + c\_2 a\_{11}^{(2)} + &\cdots + c\_k a\_{11}^{(k)} = a\_{11}^{(k+1)} \\ c\_1 a\_{12}^{(1)} + c\_2 a\_{12}^{(2)} + &\cdots + c\_k a\_{12}^{(k)} = a\_{12}^{(k+1)} \\ &\\;\\;\\,\vdots \\ c\_1 a\_{LL}^{(1)} + c\_2 a\_{LL}^{(2)} + &\cdots + c\_k a\_{LL}^{(k)} = a\_{LL}^{(k+1)} \end{align\*} $$

Treating \\$a\_{hi}^{(j)}\\$ as constants (since we know \\$A\\$), this is a system of \\$L^2\\$ equations in \\$k\\$ variables \\$c\_i\\$.

Let \\$B\\$ be the augmented matrix for this massive system of equations for \\$k=L\\$. Solving the full \\$B\\$ would give a recurrence of order \\$L=2^m\\$, but we need a smaller recurrence.

To find a smaller recurrence, we simple use a smaller \\$k\\$. The bulk of the paper is in proving that the minimum possible \\$k\\$ is the rank of \\$B\\$. However, for this specific problem, the minimum \\$k\\$ is \\$k\_0=2^{\lceil \frac{m}{2} \rceil}\\$ (Source --- floor since the row \\$k\\$ has \\$m=k-1\\$). Thus we can take the \\$k\_0 \times (k\_0+1)\\$ submatrix at the top left of \\$B\\$ and solve it to find the \\$k\_0\\$ coefficients of a useful recurrence.

```
{⍵=1:⍳2⋄(2*⌈⍵÷2)(⌷⌹⍉⍤↑)⍉L↑⍉↑,¨+.×\(L←2*⍵)⍴⊂∘.((0∊+)⍱1∊2|×≢¨⍤⊆⊣)⍨⍸1⍴⍨⍵⍴2}
{...} ⍝ Dfn with right argument m
⍵=1:⍳2⋄ ⍝ Special case m=1: return [0 1]
⍝ Compute the transition matrix A:
 ⍸1⍴⍨⍵⍴2  ⍝ All 2^m states: cartesian m-th power of [0 1]
            ⍝ (m=1 yields a vector of scalars rather than vectors, which is why we need a special case for m=1)
 ∘.{...}⍨ ⍝ Outer product with itself (all current→next state pairs) using function:
  ⍱         ⍝ Neither of the following are true:
  (0∊+)       ⍝ 0→0 in mapping (invalid since we require a horizontal domino when the current state has a 0)
  1∊2|×≢¨⍤⊆⊣  ⍝ Some run of 1→1 has odd length (requires a half vertical domino, impossible)
⍝ Compute the minimal polynomial of A
 +.×\(L←2*⍵)⍴⊂ ⍝ Produce matrix powers of A: A, A*2, ... A*L, where L=2*m
 ↑,¨           ⍝ B: Ravel each (Vec A*k) and join into single (L×L) × L matrix
 ⍉L↑⍉          ⍝ B': Trim to first L rows (for numerical stability in later gauss-jordan elimination)
 (2*⌈⍵÷2) ⍝ Rank r
 ⌷⌹⍉⍤↑ ⍝ Compute recurrence coefficients α←first r entries of b˜÷B̃
  ⍉⍤↑   ⍝ B̃: columns 0 to r-1, inclusive, of B' (taller than B̃ in paper)
  ⌷     ⍝ b˜: r-th column of B' (taller than b˜ of paper)
  ⌹     ⍝ matrix divide b˜÷B̃ to get coefficients

```

# Answer
> 3 votes
# Python 2,  ~~327 ... 249~~  246 bytes

*Saved 37 bytes thanks to fireflame241!*

This is using a port of my JS answer to *Number of domino tilings* to feed SymPy's `find_linear_recurrence()` method.

```
import re,sympy,sympy.abc as s
L=[1];N=2**input()-1;a=[0]*N+L;R=range(N+1)
for _ in[0]+R:a=[sum(a[k]*(~k&~i&N<bool(re.match("0b(0*11)*0*$",bin(k&i))))for k in R)for i in R];L+=a[-1:]
print sympy.sequence(L,(s.n,1,N+3)).find_linear_recurrence(N+3)

```

Try it online! or Run a test suite

## How?

### State transitions

Given \\$n-1\\$ rows that are entirely filled and given an \\$n\\$th row which is partially filled with state \\$S\_m(n)\\$, we want to find out what are the compatible states \\$S\_m(n+1)\\$ for the next row.

In the example below, we have \\$m=5\\$ and \\$S\_5(n)=7\\$ (in blue). There are three valid ways of setting the next row while completing the \\$n\\$th row. The compatible states \\$S\_5(n+1)\\$ for the next row are \\$24\\$, \\$27\\$ and \\$30\\$.

As a rule of thumb, empty cells in the \\$n\\$th row have to be filled with vertical dominoes (in yellow) and we may then insert horizontal dominoes (in green) in the remaining free spaces of the new row.

In the Python code, we use the variables `k` and `i` for \\$S\_m(n)\\$ and \\$S\_m(n+1)\\$ respectively.

For the vertical dominoes, we make sure that the bits that are cleared in `k` are not cleared in `i` by testing if the following expression evaluates to \\$0\\$:

```
~k & ~i & N

```

where `N` is a constant bit mask set to \\$2^m-1\\$.

For the horizontal dominoes, we make sure that the islands of bits that are set in both `k` and `i` all include an even number of bits. We do that with a regular expression:

```
re.match("0b(0*11)*0*$", bin(k & i))

```

Both tests are combined into:

```
~k & ~i & N < bool(re.match("0b(0*11)*0*$", bin(k & i)))

```

### Number of valid tilings

The variable `a` holds a list of \\$2^m\\$ entries describing how many times each state appeared in the previous iteration. We update `a` by using the above tests: the new value for `a[i]` is the sum of all previous values `a[k]` for all pairs of compatible states `(k,i)`:

```
a = [sum(a[k] * (...) for k in R) for i in R]

```

The total number of valid tilings is the number of times we reach the 'full' state (\\$2^m-1\\$) for the last row, which is `a[-1]`.

### Final solution

We use this method to compute the first \\$2^m+2\\$ terms of the sequence in the list `L` and inject it into `find_linear_recurrence()` to get the final solution.

**Note**: According to OEIS (and as already pointed out by fireflame241), computing \\$2^{\lceil m/2\rceil}\\$ terms would be enough and would make the code faster, but also a bit longer.

# Answer
> 1 votes
# Python 3.8, 228 bytes

Similarly to Arnauld's answer, this uses my answer to Number of domino tilings to feed SymPy's `find_linear_recurrence` function.

```
from math import*
import sympy,sympy.abc as s
def f(m):N=2**m+2;return sympy.sequence([round(abs(prod(2*cos((i//k+1)*pi/-~m)+2j*cos((i%k+1)*pi/-~k)for i in range(m*k)))**.5)for k in range(N)],(s.n,1,N)).find_linear_recurrence(N)

```

Try it online!. TIO doesn't have sympy in its Python 3.8 installation, so the link includes a polyfill of `math.prod`, which is new to 3.8.

Since this multiplies (floating-point) complex numbers together, it loses precision for \\$m\geq 5\\$, leading to a completely incorrect recurrence.

---
Tags: code-golf, combinatorics, grid, tiling, dominoes
---