# Question
Title: Plant trees in a park - As fast as you can!
This challenge is inspired by this app. The test cases are borrowed from that app.

---

This is a challenge, where the objective is to solve the largest test cases in the least amount of time. There are provided some smaller test cases, so that people might test their algorithms faster.

---

You'll be given a square input grid, of dimensions **n-by-n** where **9 \<= n \<= 12**. This grid will be divided into **n** areas, where the cells of each area has a unique identifiers (I'll use lower case letters from **a-l** in the the text here, but you may choose whatever you like, for instance integers **1-12**).

The input may look like this (optional input format):

```
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg

```

Or, easier to visualize:

## Challenge:

You are to place **2\*n** trees in this park, according to the following rules:

* There shall be exactly **2** trees per column, and **2** trees per row
* All areas shall have exactly **2** trees.
* No trees can be adjacent to another tree, vertically, horizontally or diagonally

The solution to the layout above is:

Note: There is only one solution to each puzzle

### Additional rules:

* The input and output formats are optional
    + The output might for instance be a list of indices, a grid with **1/0** indicating if there's a tree in that position, or a modified version of the input where the trees are indicated
* The execution time must be deterministic
* The program must finish withing 1 minute at @isaacg's computer
    + Specs: 4 CPUs, i5-4300U CPU @ 1.9 GHz, 7.5G of RAM.
* In case your program can't solve the two largest test case in one minute each then the time for the second largest (**n=11**) will be your score. You'll lose against a solution that solves the largest case.

### Test cases:

I might edit this list if submissions seems to be customized to fit these test cases.

**12-by-12**:

```
--- Input ---
aaaaabccccdd
aaaaabccccdd
aaaaabbbbddd
eeeafffgbghh
eeaafffgbghh
eefffffggghh
eeefijffghhh
iieiijjjjkhh
iiiiijjjjkhk
lljjjjjjjkkk
llllllkkkkkk
llllllkkkkkk
--- Solution ---
aaaaabcccCdD
aaaaaBcCccdd
aAaaabbbbdDd
eeeaffFgBghh
eeAaFffgbghh
eefffffGgGhh
EeefijffghhH
iiEiIjjjjkhh
IiiiijjjjkHk
lljJjJjjjkkk
lLllllkkKkkk
lllLllKkkkkk

```

**11-by-11**:

```
--- Input ---
aaaaaaabbcc
adddabbbbcc
edddbbbbbbc
eddddbbbbbb
effffggghhh
effffgghhii
eefffjjhhii
eeeejjjhhii
eeejjjjkiii
jjjjjjkkiii
jjjjjkkkiii
--- Solution ---
aaAaaaabbCc
adddAbBbbcc
eDddbbbbbbC
eddDdBbbbbb
effffggGhHh
eFfffGghhii
eefFfjjhHii
EeeejjjhhiI
eeEjjjjKiii
JjjjJjkkiii
jjjjjkKkIii

```

**10-by-10**

```
--- Input ---
aaaaabccdd
aeaabbbccd
aeaabfbgcd
eeeaafggcd
eeeaafghcd
eeeiifghcd
ieiiigghcd
iiijighhcd
jjjjighhcd
jjjggghhdd
--- Solution ---
aaAaabccdD
aeaaBbBccd
aEaabfbgcD
eeeaaFgGcd
eEeAafghcd
eeeiiFghCd
IeiIigghcd
iiijigHhCd
JjJjighhcd
jjjgGghHdd

```

**9-by-9**

```
--- Input ---
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg
--- Solution ---
aAbBbbbcc
adddbbBcC
adEeEcccc
AdddefgCc
hhhDiFggg
hDddifffG
hhhiIfFfg
HiHiifffg
iiiiiIgGg
--- Input ---
aaabbbccc
aaaabbccc
aaaddbcce
ffddddcce
ffffddeee
fgffdheee
fggfhhhee
iggggheee
iiigggggg
--- Solution ---
aaAbBbccc
AaaabbcCc
aaaDdBcce
fFddddcCe
fffFdDeee
fGffdheeE
fggfHhHee
IggggheeE
iiIgggGgg

```

# Answer
> 7 votes
## JavaScript (ES6), 271 bytes

Takes input as an array of arrays of characters. Returns an array of bitmasks (integers) describing the position of the trees on each row, where the least significant bit is the leftmost position.

```
f=(a,p=0,r=[S=y=0],w=a.length)=>a.some((R,y)=>a.some((_,x)=>r[y]>>x&1&&(o[k=R[x]]=-~o[k])>2),o=[])?0:y<w?[...Array(1<<w)].some((_,n)=>(k=n^(x=n&-n))<=x*2|k&-k^k|n&(p|p/2|p*2)||r.some((A,i)=>r.some((B,j)=>A&B&n&&i<y&j<i))?0:(w=r[y],f(a,r[y++]=n,r),r[--y]=w,S))&&S:S=[...r]

```

### Formatted and commented

```
f = (                                           // given:
  a,                                            //   - a = input matrix
  p = 0,                                        //   - p = previous bitmask
  r = [                                         //   - r = array of tree bitmasks
        S = y = 0 ],                            //   - S = solution / y = current row
  w = a.length                                  //   - w = width of matrix
) =>                                            //
  a.some((R, y) => a.some((_, x) =>             // if there's at least one area with more
    r[y] >> x & 1 && (o[k = R[x]] = -~o[k]) > 2 // than two trees:
  ), o = []) ?                                  //
    0                                           //   abort right away
  :                                             // else:
    y < w ?                                     //   if we haven't reached the last row:
      [...Array(1 << w)].some((_, n) =>         //     for each possible bitmask n:
        (k = n ^ (x = n & -n)) <= x * 2 |       //       if the bitmask does not consist of
        k & - k ^ k |                           //       exactly two non-consecutive bits,
        n & (p | p / 2 | p * 2) ||              //       or is colliding with the previous
        r.some((A, i) => r.some((B, j) =>       //       bitmask, or generates more than two
          A & B & n && i < y & j < i            //       trees per column:
        )) ?                                    //
          0                                     //         yield 0
        :                                       //       else:
          (                                     //
            w = r[y],                           //         save the previous bitmask
            f(a, r[y++] = n, r),                //         recursive call with the new one
            r[--y] = w,                         //         restore the previous bitmask
            S                                   //         yield S
          )                                     //
      ) && S                                    //     end of some(): return false or S
    :                                           //   else:
      S = [...r]                                //     this is a solution: save a copy in S

```

### Test cases

This snippet includes an additional function to display the results in a more readable format. It is too slow to solve the last test case.

Expected runtime: ~5 seconds.

```
f=(a,p=0,r=[S=y=0],w=a.length)=>a.some((R,y)=>a.some((_,x)=>r[y]>>x&1&&(o[k=R[x]]=-~o[k])>2),o=[])?0:y<w?[...Array(1<<w)].some((_,n)=>(k=n^(x=n&-n))<=x*2|k&-k^k|n&(p|p/2|p*2)||r.some((A,i)=>r.some((B,j)=>A&B&n&&i<y&j<i))?0:(w=r[y],f(a,r[y++]=n,r),r[--y]=w,S))&&S:S=[...r]

format = (a, w) => a.map(n => [...('0'.repeat(w) + n.toString(2)).slice(-w)].reverse().join('')).join('\n')

console.log(format(f([
  [..."aabbbbbcc"],
  [..."adddbbbcc"],
  [..."adeeecccc"],
  [..."adddefgcc"],
  [..."hhhdifggg"],
  [..."hdddifffg"],
  [..."hhhiifffg"],
  [..."hihiifffg"],
  [..."iiiiiiggg"]
]), 9));

console.log(format(f([
  [..."aaabbbccc"],
  [..."aaaabbccc"],
  [..."aaaddbcce"],
  [..."ffddddcce"],
  [..."ffffddeee"],
  [..."fgffdheee"],
  [..."fggfhhhee"],
  [..."iggggheee"],
  [..."iiigggggg"]
]), 9));

console.log(format(f([
  [..."aaaaabccdd"],
  [..."aeaabbbccd"],
  [..."aeaabfbgcd"],
  [..."eeeaafggcd"],
  [..."eeeaafghcd"],
  [..."eeeiifghcd"],
  [..."ieiiigghcd"],
  [..."iiijighhcd"],
  [..."jjjjighhcd"],
  [..."jjjggghhdd"]
]), 10));
```

# Answer
> 7 votes
# C, official time: 5ms for 12x12

```
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <omp.h>

#define valT char
#define posT int

#ifndef _OPENMP
#  warning Building without OpenMP support
#  define omp_get_max_threads() 1
#  define omp_get_num_threads() 1
#  define omp_get_thread_num() 0
#endif

#define MIN_THREADED_SIZE 11

static void complete(posT n, valT *workspace) {
    const posT s = n * 3 + 2;

    const valT *regions = workspace;
    valT *output = &workspace[n*2+1];

    for(posT y = 0; y < n; ++ y) {
        for(posT x = 0; x < n; ++ x) {
//          putchar(output[y*s+x] ? '*' : '-');
            putchar(regions[y*s+x] + (output[y*s+x] ? 'A' : 'a'));
        }
        putchar('\n');
    }

    _Exit(0);
}

static void solveB(const posT n, valT *workspace, valT *pops, const posT y) {
    const posT s = n * 3 + 2;

    const valT *regions = workspace;
    const valT *remaining = &workspace[n];
    valT *output = &workspace[n*2+1];

    for(posT r = 0; r < n; ++ r) {
        if(pops[r] + remaining[r] < 2) {
            return;
        }
    }

    for(posT t1 = 0; t1 < n - 2; ++ t1) {
        posT r1 = regions[t1];
        if(output[t1+1-s]) {
            t1 += 2;
            continue;
        }
        if(output[t1-s]) {
            ++ t1;
            continue;
        }
        if((pops[t1+n] | pops[r1]) & 2 || output[t1-1-s]) {
            continue;
        }
        output[t1] = 1;
        ++ pops[t1+n];
        ++ pops[r1];
        for(posT t2 = t1 + 2; t2 < n; ++ t2) {
            posT r2 = regions[t2];
            if(output[t2+1-s]) {
                t2 += 2;
                continue;
            }
            if(output[t2-s]) {
                ++ t2;
                continue;
            }
            if((pops[t2+n] | pops[r2]) & 2 || output[t2-1-s]) {
                continue;
            }
            output[t2] = 1;
            ++ pops[t2+n];
            ++ pops[r2];
            if(y == 0) {
                complete(n, &workspace[-s*(n-1)]);
            }
            solveB(n, &workspace[s], pops, y - 1);
            output[t2] = 0;
            -- pops[t2+n];
            -- pops[r2];
        }
        output[t1] = 0;
        -- pops[t1+n];
        -- pops[r1];
    }
}

static void solve(const posT n, valT *workspace) {
    const posT s = n * 3 + 2;

    valT *regions = workspace;
    valT *remaining = &workspace[n];
    valT *pops = &workspace[n*s];
//  memset(&remaining[n*s], 0, n * sizeof(valT));

    for(posT y = n; (y --) > 0;) {
        memcpy(&remaining[y*s], &remaining[(y+1)*s], n * sizeof(valT));
        for(posT x = 0; x < n; ++ x) {
            valT r = regions[y*s+x];
            valT *c = &remaining[y*s+r];
            valT *b = &pops[r*3];
            if(*c == 0) {
                *c = 1;
                b[0] = y - 1;
                b[1] = x - 1;
                b[2] = x + 1;
            } else if(x < b[1] || x > b[2] || y < b[0]) {
                *c = 2;
            } else {
                b[1] = b[1] > (x - 1) ? b[1] : (x - 1);
                b[2] = b[2] < (x + 1) ? b[2] : (x + 1);
            }
        }
//      memset(&output[y*s], 0, (n+1) * sizeof(valT));
    }
    memset(pops, 0, n * 2 * sizeof(valT));

    posT sz = (n + 1) * s + n * 3;
    if(n >= MIN_THREADED_SIZE) {
        for(posT i = 1; i < omp_get_max_threads(); ++ i) {
            memcpy(&workspace[i*sz], workspace, sz * sizeof(valT));
        }
    }

#pragma omp parallel for if (n >= MIN_THREADED_SIZE)
    for(posT t1 = 0; t1 < n - 2; ++ t1) {
        valT *workspace2 = &workspace[omp_get_thread_num()*sz];
        valT *regions = workspace2;
        valT *output = &workspace2[n*2+1];
        valT *pops = &workspace2[n*s];

        posT r1 = regions[t1];
        output[t1] = pops[t1+n] = pops[r1] = 1;
        for(posT t2 = t1 + 2; t2 < n; ++ t2) {
            posT r2 = regions[t2];
            output[t2] = pops[t2+n] = 1;
            ++ pops[r2];
            solveB(n, &regions[s], pops, n - 2);
            output[t2] = pops[t2+n] = 0;
            -- pops[r2];
        }
        output[t1] = pops[t1+n] = pops[r1] = 0;
    }
}

int main(int argc, const char *const *argv) {
    if(argc < 2) {
        fprintf(stderr, "Usage: %s 'grid-here'\n", argv[0]);
        return 1;
    }

    const char *input = argv[1];
    const posT n = strchr(input, '\n') - input;
    const posT s = n * 3 + 2;

    posT sz = (n + 1) * s + n * 3;
    posT threads = (n >= MIN_THREADED_SIZE) ? omp_get_max_threads() : 1;
    valT *workspace = (valT*) calloc(sz * threads, sizeof(valT));
    valT *regions = workspace;

    for(posT y = 0; y < n; ++ y) {
        for(posT x = 0; x < n; ++ x) {
            regions[y*s+x] = input[y*(n+1)+x] - 'a';
        }
    }

    solve(n, workspace);

    fprintf(stderr, "Failed to solve grid\n");
    return 1;
}

```

Compiled with GCC 7 using the `-O3` and `-fopenmp` flags. Should have similar results on any version of GCC with OpenMP installed.

```
gcc-7 Trees.c -O3 -fopenmp -o Trees

```

Input and output format are as given in the question.

On my machine this takes ~~0.009s~~ ~~0.008s~~ 0.005s for the 12x12 example, and ~~0.022s~~ ~~0.020s~~ 0.019s to run all the examples. On the benchmark machine, isaacg reports 5ms for the 12x12 example using the original (non-threaded) version of the code.

Usage:

```
./Trees 'aaabbbccc
aaaabbccc
aaaddbcce
ffddddcce
ffffddeee
fgffdheee
fggfhhhee
iggggheee
iiigggggg'

```

---

Just a simple brute-force solver, working on one row at a time. It runs at a good speed by recognising impossible situations early (e.g. no region cells remaining, but less than 2 trees in the region).

The first update improves cache hits by putting related data close together in memory, and makes the possible-trees-remaining-in-segment calculations slightly smarter (now accounts for the fact that trees cannot be adjacent). It also extracts the outermost loop so that fewer special cases are needed in the hottest part of the algorithm.

The second update makes the outermost loop run in parallel across the available processors (using OpenMP), giving a linear speed boost. This is only enabled for n \>= 11, since the overhead of spawning threads outweighs the benefits for smaller grids.

# Answer
> 5 votes
# Java (OpenJDK 8), Official Timing: 1.2s on 12x12

edit: no longer code golf

```
import java.util.*;

// Callable method, takes an int[][] and modifies it
static void f(int[][] areas){
    List<List<BitSet>> areaBitSets = new ArrayList<>();
    List<List<BitSet>> areaTreeBitSets = new ArrayList<>();
    for(int i = 0; i < areas.length; i++){
        areaBitSets.add(new ArrayList<BitSet>());
        areaTreeBitSets.add(new ArrayList<BitSet>());
    }

    // Add a bitset to our list representing each possible square, grouped by area
    for(int i=0; i < areas.length; i++){
        for(int j=0; j < areas.length; j++){
            BitSet b = new BitSet();
            b.set(i*areas.length + j);
            areaBitSets.get(areas[i][j]).add(b);
        }
    }

    // Fold each set onto itself so each area bitset has two trees
    for(int i=0; i < areas.length; i++){
        for(int j=0; j<areaBitSets.get(i).size()-1; j++){
            for(int k=j+1; k <areaBitSets.get(i).size(); k++){
                if(canFoldTogether(areaBitSets.get(i).get(j),areaBitSets.get(i).get(k), areas.length)){
                    BitSet b = (BitSet)areaBitSets.get(i).get(j).clone();
                    b.or(areaBitSets.get(i).get(k));
                    areaTreeBitSets.get(i).add(b);
                }
            }
        }
    }

    // Starting with area 0 add each area one at a time doing Cartesian products
    Queue<BitSet> currentPossibilities = new LinkedList<>();
    Queue<BitSet> futurePossibilities = new LinkedList<>();
    currentPossibilities.addAll(areaTreeBitSets.get(0));

    for(int i=1; i < areaTreeBitSets.size(); i++){
        while(!currentPossibilities.isEmpty()){
            BitSet b= (BitSet)currentPossibilities.poll().clone();

            for(BitSet c: areaTreeBitSets.get(i)){
                if(canFoldTogether(b,c,areas.length)){
                    BitSet d=(BitSet)b.clone();
                    d.or(c);
                    futurePossibilities.add(d);
                }
            }
        }
        currentPossibilities.addAll(futurePossibilities);
        futurePossibilities.clear();
    }

    // Get final output and modify the array
    BitSet b = currentPossibilities.poll();
    for(int i=0; i<areas.length*areas.length; i++){
        areas[i/areas.length][i%areas.length] = b.get(i)?1:0;
    }
}

// Helper method which determines whether combining two bitsets
// will still produce a valid output
static boolean canFoldTogether(BitSet a, BitSet b, int size){

    // See if there are trees too close to each other
    int c=-1;
    while((c=a.nextSetBit(c+1))>=0){
        int d=-1;
        while((d=b.nextSetBit(d+1))>=0){
            int r1=c/size;
            int r2=d/size;
            int c1=c%size;
            int c2=d%size;

            int rDifference = r1>r2 ? r1-r2 : r2-r1;
            int cDifference = c1>c2 ? c1-c2 : c2-c1;
            if(rDifference<2 && cDifference<2)
                return false;
        }
    }

    // Check for row and column cardinality
    BitSet f,g;
    for(int i=0; i<size; i++){
        f = new BitSet();
        f.set(i*size,(i+1)*size);
        g=(BitSet)f.clone();
        f.and(a);
        g.and(b);
        f.or(g);
        if(f.cardinality()>2){
            return false;
        }

        f=new BitSet();
        for(int j = 0; j<size; j++){
            f.set(j*size+i);
        }
        g=(BitSet)f.clone();
        f.and(a);
        g.and(b);
        f.or(g);
        if(f.cardinality()>2){
            return false;
        }
    }

    return true;
}

```

Try it online!

TIO link is for the 12x12 test case. TIO reports 2.429s for the run time.

Takes an array of integers as the input and modifies the array to contain 1s for trees and 0s for non-trees.

This runs for all testcases. The largest testcase runs on my machine in less than a second, although I have a pretty powerful machine

Test code for the 12x12, can modify for others

```
public static void main(String[] args){
    int[][] test = {{0,  0,  0,  0,  0,  1,  2,  2,  2,  2,  3,  3},
            {0,  0,  0,  0,  0,  1,  2,  2,  2,  2,  3,  3},
            {0,  0,  0,  0,  0,  1,  1,  1,  1,  3,  3,  3},
            {4,  4,  4,  0,  5,  5,  5,  6,  1,  6,  7,  7},
            {4,  4,  0,  0,  5,  5,  5,  6,  1,  6,  7,  7},
            {4,  4,  5,  5,  5,  5,  5,  6,  6,  6,  7,  7},
            {4,  4,  4,  5,  8,  9,  5,  5,  6,  7,  7,  7},
            {8,  8,  4,  8,  8,  9,  9,  9,  9,  10,  7,  7},
            {8,  8,  8,  8,  8,  9,  9,  9,  9,  10,  7,  10},
            {11,  11,  9,  9,  9,  9,  9,  9,  9,  10,  10,  10},
            {11,  11,  11,  11,  11,  11,  10,  10,  10,  10,  10,  10},
            {11,  11,  11,  11,  11,  11,  10,  10,  10,  10,  10,  10}};

    long l = System.currentTimeMillis();
    f(test);
    System.out.println("12x12: " + (System.currentTimeMillis() - l) + "ms");

    for(int[] t : test){
        System.out.println(Arrays.toString(t));
    }

}

```

Produces this on my machine:

```
12x12: 822ms
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0]

```

# Answer
> 4 votes
# Clingo, ≈ 7 ms for 12×12, 116 bytes

```
{t(X,Y):c(X,Y,Z)}=2:-Z=1..n.
:-X=1..n,{t(X,1..n)}!=2.
:-Y=1..n,{t(1..n,Y)}!=2.
:-t(X,Y),t(X+1,Y;X+1,Y+1;X,Y+1;X-1,Y+1).

```

(Newlines are optional and not counted.)

Run with `clingo plant.lp - -c n=<n>` where `<n>` is the grid size. The input format is a list of `c(X,Y,Z).` statements for each cell (`X`, `Y`) colored `Z`, with 1 ≤ `X`, `Y`, `Z``n`, separated by optional whitespace. The output includes `t(X,Y)` for each tree at (`X`, `Y`).

The time is pretty meaningless as it’s basically just startup time, so consider this a vote for larger test cases.

### Demo

```
$ clingo plant.lp -c n=12 - <<EOF
> c(1,1,1). c(2,1,1). c(3,1,1). c(4,1,1). c(5,1,1). c(6,1,2). c(7,1,3). c(8,1,3). c(9,1,3). c(10,1,3). c(11,1,4). c(12,1,4).
> c(1,2,1). c(2,2,1). c(3,2,1). c(4,2,1). c(5,2,1). c(6,2,2). c(7,2,3). c(8,2,3). c(9,2,3). c(10,2,3). c(11,2,4). c(12,2,4).
> c(1,3,1). c(2,3,1). c(3,3,1). c(4,3,1). c(5,3,1). c(6,3,2). c(7,3,2). c(8,3,2). c(9,3,2). c(10,3,4). c(11,3,4). c(12,3,4).
> c(1,4,5). c(2,4,5). c(3,4,5). c(4,4,1). c(5,4,6). c(6,4,6). c(7,4,6). c(8,4,7). c(9,4,2). c(10,4,7). c(11,4,8). c(12,4,8).
> c(1,5,5). c(2,5,5). c(3,5,1). c(4,5,1). c(5,5,6). c(6,5,6). c(7,5,6). c(8,5,7). c(9,5,2). c(10,5,7). c(11,5,8). c(12,5,8).
> c(1,6,5). c(2,6,5). c(3,6,6). c(4,6,6). c(5,6,6). c(6,6,6). c(7,6,6). c(8,6,7). c(9,6,7). c(10,6,7). c(11,6,8). c(12,6,8).
> c(1,7,5). c(2,7,5). c(3,7,5). c(4,7,6). c(5,7,9). c(6,7,10). c(7,7,6). c(8,7,6). c(9,7,7). c(10,7,8). c(11,7,8). c(12,7,8).
> c(1,8,9). c(2,8,9). c(3,8,5). c(4,8,9). c(5,8,9). c(6,8,10). c(7,8,10). c(8,8,10). c(9,8,10). c(10,8,11). c(11,8,8). c(12,8,8).
> c(1,9,9). c(2,9,9). c(3,9,9). c(4,9,9). c(5,9,9). c(6,9,10). c(7,9,10). c(8,9,10). c(9,9,10). c(10,9,11). c(11,9,8). c(12,9,11).
> c(1,10,12). c(2,10,12). c(3,10,10). c(4,10,10). c(5,10,10). c(6,10,10). c(7,10,10). c(8,10,10). c(9,10,10). c(10,10,11). c(11,10,11). c(12,10,11).
> c(1,11,12). c(2,11,12). c(3,11,12). c(4,11,12). c(5,11,12). c(6,11,12). c(7,11,11). c(8,11,11). c(9,11,11). c(10,11,11). c(11,11,11). c(12,11,11).
> c(1,12,12). c(2,12,12). c(3,12,12). c(4,12,12). c(5,12,12). c(6,12,12). c(7,12,11). c(8,12,11). c(9,12,11). c(10,12,11). c(11,12,11). c(12,12,11).
> EOF
clingo version 5.1.0
Reading from plant.lp ...
Solving...
Answer: 1
c(1,1,1) c(2,1,1) c(3,1,1) c(4,1,1) c(5,1,1) c(6,1,2) c(7,1,3) c(8,1,3) c(9,1,3) c(10,1,3) c(11,1,4) c(12,1,4) c(1,2,1) c(2,2,1) c(3,2,1) c(4,2,1) c(5,2,1) c(6,2,2) c(7,2,3) c(8,2,3) c(9,2,3) c(10,2,3) c(11,2,4) c(12,2,4) c(1,3,1) c(2,3,1) c(3,3,1) c(4,3,1) c(5,3,1) c(6,3,2) c(7,3,2) c(8,3,2) c(9,3,2) c(10,3,4) c(11,3,4) c(12,3,4) c(1,4,5) c(2,4,5) c(3,4,5) c(4,4,1) c(5,4,6) c(6,4,6) c(7,4,6) c(8,4,7) c(9,4,2) c(10,4,7) c(11,4,8) c(12,4,8) c(1,5,5) c(2,5,5) c(3,5,1) c(4,5,1) c(5,5,6) c(6,5,6) c(7,5,6) c(8,5,7) c(9,5,2) c(10,5,7) c(11,5,8) c(12,5,8) c(1,6,5) c(2,6,5) c(3,6,6) c(4,6,6) c(5,6,6) c(6,6,6) c(7,6,6) c(8,6,7) c(9,6,7) c(10,6,7) c(11,6,8) c(12,6,8) c(1,7,5) c(2,7,5) c(3,7,5) c(4,7,6) c(5,7,9) c(6,7,10) c(7,7,6) c(8,7,6) c(9,7,7) c(10,7,8) c(11,7,8) c(12,7,8) c(1,8,9) c(2,8,9) c(3,8,5) c(4,8,9) c(5,8,9) c(6,8,10) c(7,8,10) c(8,8,10) c(9,8,10) c(10,8,11) c(11,8,8) c(12,8,8) c(1,9,9) c(2,9,9) c(3,9,9) c(4,9,9) c(5,9,9) c(6,9,10) c(7,9,10) c(8,9,10) c(9,9,10) c(10,9,11) c(11,9,8) c(12,9,11) c(1,10,12) c(2,10,12) c(3,10,10) c(4,10,10) c(5,10,10) c(6,10,10) c(7,10,10) c(8,10,10) c(9,10,10) c(10,10,11) c(11,10,11) c(12,10,11) c(1,11,12) c(2,11,12) c(3,11,12) c(4,11,12) c(5,11,12) c(6,11,12) c(7,11,11) c(8,11,11) c(9,11,11) c(10,11,11) c(11,11,11) c(12,11,11) c(1,12,12) c(2,12,12) c(3,12,12) c(4,12,12) c(5,12,12) c(6,12,12) c(7,12,11) c(8,12,11) c(9,12,11) c(10,12,11) c(11,12,11) c(12,12,11) t(1,7) t(1,9) t(2,3) t(2,11) t(3,5) t(3,8) t(4,10) t(4,12) t(5,5) t(5,8) t(6,2) t(6,10) t(7,4) t(7,12) t(8,2) t(8,6) t(9,4) t(9,11) t(10,1) t(10,6) t(11,3) t(11,9) t(12,1) t(12,7)
SATISFIABLE

Models       : 1+
Calls        : 1
Time         : 0.009s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

```

To make the input/output format easier to deal with, here are Python programs to convert from and to the format given in the challenge.

### Input

```
import sys
print(' '.join("c({},{},{}).".format(x + 1, y + 1, ord(cell) - ord('a') + 1) for y, row in enumerate(sys.stdin.read().splitlines()) for x, cell in enumerate(row)))

```

### Output

```
import re
import sys
for line in sys.stdin:
    c = {(int(x), int(y)): int(z) for x, y, z in re.findall(r'\bc\((\d+),(\d+),(\d+)\)', line)}
    if c:
        t = {(int(x), int(y)) for x, y in re.findall(r'\bt\((\d+),(\d+)\)', line)}
        n, n = max(c)
        for y in range(1, n + 1):
            print(''.join(chr(ord('aA'[(x, y) in t]) + c[x, y] - 1) for x in range(1, n + 1)))
        print()

```

---
Tags: grid, game, fastest-code
---


title: Knight-fill a grid

text:
# Question
Title: Knight-fill a grid
A knight fill is a flood fill using the connectivity of the knight chess piece. Specifically:

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

```

(0 is the initial point, 1s show the connected cells)

## Challenge

Given a 2D grid of spaces and walls, and an initial location, perform a knight-fill on the grid. Shortest code wins.

## Rules

* You may take input and produce output in any format you like (image, string, array, whatever). You may take the initial location as part of the input grid or as a separate coordinate. For the purpose of this explanation, the following format will be used:

```
########    # = wall
########    x = initial location
## x  ##
##    ##
########
##    ##
########
########

```
* Output is a copy of the input grid with the knight-fill result added
* Your fill must not be in the same "colour" as the space or walls, but can be the same as the initial location marker. For example given the image above, a valid output would be:

```
########    # = wall
########    @ = fill (could also have been x)
## @ @##
## @ @##
########
##@ @ ##
########
########

```
* You may assume that the input grid will always contain a 2-cell wall on all sides
* You may assume that the initial location will never be inside a wall
* You may assume that the grid will never be larger than 1000x1000
* Builtins are fine
* Shortest code (in bytes) wins

## Test Cases

In all test cases, `#` denotes a wall,  denotes empty space, and `x` denotes the initial location of the fill. `@` denotes the output fill.

```
Input 1:

########
########
## x  ##
##    ##
########
##    ##
########
########

Output 1:

########
########
## @ @##
## @ @##
########
##@ @ ##
########
########

Input 2:

############
############
## ##    x##
## ##     ##
#####     ##
##        ##
############
############

Output 2:

############
############
## ##@@@@@##
##@##@@@@@##
#####@@@@@##
## @@@@@@@##
############
############

Input 3:

####################
####################
##  ##            ##
##  ##            ##
##  ##  ########  ##
##  ##  ########  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ##    ##  ##
##  ##  ########  ##
##  ##  ########  ##
##  ##        ##  ##
##  ##       x##  ##
##  ############  ##
##  ############  ##
##                ##
##                ##
####################
####################

Output 3:

####################
####################
##@@##@@@@@@@@@@@@##
##@@##@@@@@@@@@@@@##
##@@##@@########@@##
##@@##@@########@@##
##@@##@@##    ##@@##
##@@##@@##    ##@@##
##@@##@@##    ##@@##
##@@##@@##    ##@@##
##@@##@@########@@##
##@@##@@########@@##
##@@##@@@@@@@@##@@##
##@@##@@@@@@@@##@@##
##@@############@@##
##@@############@@##
##@@@@@@@@@@@@@@@@##
##@@@@@@@@@@@@@@@@##
####################
####################

Input 4:

################
################
##           ###
##     x     ###
##  #######  ###
##  #######  ###
##  ##   ##  ###
##  ##   ##  ###
##  ##   ##  ###
##  ########  ##
##  ########  ##
##        ##  ##
##        ##  ##
################
################

Output 4:

################
################
##   @   @   ###
## @   @   @ ###
##  #######  ###
##@ ####### @###
##  ##   ##  ###
## @##   ##@ ###
##  ##   ##  ###
##@ ########@ ##
##  ########  ##
## @   @  ## @##
##   @   @##  ##
################
################

Input 5:

##############
##############
##         ###
##         ###
##         ###
##   ###   ###
##   #x#   ###
##   ###   ###
##         ###
##         ###
##         ###
##############
##############

Output 5:

##############
##############
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@###@@@###
##@@@#@#@@@###
##@@@###@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##@@@@@@@@@###
##############
##############

```

# Answer
> 4 votes
# Octave, 73 bytes

```
function a=F(s,a)do;b=a;until(a=~s&imdilate(a,de2bi(")0#0)"-31)))==b;a+=s

```

Online Demo!

\*Some changes applied to run in rextester.

A function that takes a 2d array of 0 & 2 as wall and an array of 0 & 1 as initial location and outputs an array of 0 & 1 & 2.

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

```
f=(s,l=s.search`
`,t=s.replace(eval(`/(x| )([^]{${l-2}}(....)?|[^]{${l+l}}(..)?)(?!\\1)[x ]/`),'x$2x'))=>s==t?s:f(t)

v=(s,l=s.search`
`)=>!/^(#+)\n\1\n[^]*x[^]*\n\1\n\1$/.test(s)|s.split`
`.some(s=>s.length-l|!/^##.+##$/.test(s))&&`Invalid Input`
```

```
textarea{font-family:monospace}
```

```
<textarea rows=11 cols=33 oninput=o.value=v(this.value)||f(this.value)></textarea><textarea rows=11 cols=33 id=o reaodnly></textarea>
```

Based on my answer to Detect Failing Castles. Fills using `x`s.

# Answer
> 2 votes
# Python 3, ~~394 387 381 356 352 347 319 313 154~~139 bytes

* **154 bytes after only counting the core function and not the function concerning I/O formatting**
* saved 7 bytes: thanks to @Jacoblaw and @Mr.Xcoder: `except:0`
* saved 28 bytes!!!: Thanks to @ovs: got rid of `try: except` block and several other golf
* Thanks to @Dave for the beautiful test module.
* saved 6 bytes: `g[(a,b)]` as just `g[a,b]`
* **@nore saved 15 bytes!!!**:

```
def x(g,a,b,m):
 if(a,b)in g and"!">g[a,b]or m:
  g[a,b]="@"
  for i in 1,2,-1,-2:
   for j in 3-abs(i),abs(i)-3:g=x(g,a+i,b+j,0)
 return g

```

Try it online!

# Answer
> 1 votes
## Mathematica, 117 bytes

The usual story: powerful built-ins but long names…

```
HighlightGraph[g,ConnectedComponents[h=Subgraph[g=KnightTourGraph@@Dimensions@#,Flatten@#~Position~1],#2]~Prepend~h]&

```

Try it at the Wolfram sandbox!

It takes two inputs: first is the input grid as an array of `0`s (for the walls) and `1`s (for spaces), then a single integer for the starting position, found by numbering the grid along the rows from top to bottom, e.g.

```
1  2  3  4  5
6  7  8  9  10
11 12 13 14 ...

```

You can call the function like `HighlightGraph[...~Prepend~h]&[{{0,0,...,0}, {0,0,...,0}, ..., {0,0,...,0}}, 20]`.

The `KnightTourGraph` function constructs a graph with vertices corresponding to positions in the grid and edges corresponding to valid knight moves, then we take the `Subgraph` of the vertices that aren't walls, and find the `ConnectedComponents` of the starting vertex. The output is a graph (shown rotated 90º anticlockwise) with the non-wall vertices highlighted red, and the filled vertices highlighted yellow. For example, for the first test case, the output looks like:

---
Tags: code-golf, grid, image-processing, chess
---


title: Pause twice as long

text:
# Question
Title: Pause twice as long
Your challenge is to print the input, wait any amount of time, print the input, wait twice the time you initially waited, print the input again, and so on. The initial delay must be less than 1 hour, and you must have an accuracy of +/- 5% in the subsequent delays. Other than that, there is no restriction on the delay time.

Example:

Input: `hi`.

Output: `hi` (1ms pause) `hi` (2ms pause) `hi` (4ms pause) `hi` (8ms pause) `hi` (16ms pause), etc.

Also allowed:

`hi` (1 minute pause) `hi` (2 minute pause) `hi` (4 minute pause) `hi` (8 minute pause) `hi` (16 minute pause), etc.

Input must be provided at the start of the program (STDIN, command-line parameter, function param, etc.) and will be a string.

The initial delay can't be 0.

# Answer
# 05AB1E, 6 bytes

Code:

```
[=No.W

```

Explanation:

```
[        # Start an infinite loop
 =       # Print the top of the stack without popping
  No     # Compute 2 ** (iteration index)
    .W   # Wait that many milliseconds

```

Try it online!
> 11 votes

# Answer
# Scratch, 8 blocks + 3 bytes

Equivalent in Python:

```
import time
n = 1
while 1:
    print("x")
    time.sleep(n)
    n = n * 2

```
> 14 votes

# Answer
# MATL, 8 bytes

```
`GD@WY.T

```

The first pause is 2 seconds.

Try it at MATL Online. Or see a modified version that displays the time elapsed since the program started. (If the interpreter doesn't work, please refresh the page and try again).

Or see a gif:

### Explanation

```
`     % Do...while
  G   %   Push input
  D   %   Display
  @   %   Push iteration index (1-based)
  W   %   2 raised to that
  Y.  %   Pause for that time
  T   %   Push true. This will be used as loop confition
      % End (implicit). The top of the stack is true, which produces an infinite loop

```
> 4 votes

# Answer
# Python 3, ~~60~~ 56 bytes

```
import time
def f(x,i=1):print(x);time.sleep(i);f(x,i*2)

```

Changelog:

* changed recursive lambda to recursive function (-4 bytes)
> 4 votes

# Answer
# Octave, ~~42~~ 41 bytes

```
x=input('');p=1;while p*=2,pause(p),x,end

```

Saved one byte thanks to rahnema1, `p*=2` is shorter than `p=p*2`.

I can't believe I haven't been able to golf this down, but it was actually not that easy.

* The input must be in the start, so the first part is impossible to avoid.
* I need a number that gets doubled, and it must be initialized in front of the loop
    + It would be possible to use the input as a conditional for the loop, but then I would have to have `p*=2` somewhere else.
    + Pause doesn't have a return value, otherwise it could have been `while pause(p*=2)`
> 4 votes

# Answer
## Mathematica ~~34~~ ~~32~~ ~~30~~ 29 Bytes

Original solution 34 Bytes:

```
For[x=.1,1<2,Pause[x*=2];Print@#]&

```

Shave off 2 bytes with Do

```
x=1;Do[Pause[x*=2];Print@#,∞]&

```

Shave off one more Byte with @MartinEnder's recursive solution

```
±n_:=#0[Print@n;Pause@#;2#]&@1

```

@ngenisis uses ReplaceRepeated recursion to shave off another byte

```
1//.n_:>(Print@#;Pause@n;2n)&

```
> 4 votes

# Answer
# Ruby, ~~34~~ ~~28~~ ~~23~~ 22 (+2 for `-n`) = 24 bytes

3 bytes saved thanks to Value Ink!

1 byte saved thanks to daniero

```
loop{print;sleep$.*=2}

```

Starts at `2`, then `4`, etc.

### Explanation

```
-n                       # read a line from STDIN
  loop{                } # while(true):
       print;            # print that line
             sleep$.*=2  # multiply $. by 2, then sleep that many seconds.
                         # $. is a Ruby special variable that starts at 1.

```
> 3 votes

# Answer
# Java (OpenJDK 8), 113 bytes

```
interface M{static void main(String[]a)throws Exception{for(int i=1;;Thread.sleep(i*=2))System.out.print(a[0]);}}

```

Try it online!

-60 bytes thanks to Leaky Nun!
> 3 votes

# Answer
# R, ~~50~~ 48 bytes

```
function(x,i=1)repeat{cat(x);Sys.sleep(i);i=i*2}

```

returns an anonymous function which has one mandatory argument, the string to print. Prints no newlines, just spits `x` out on the screen. `i` is an optional argument that defaults to `1`, waits for `i` seconds and doubles `i`.

*-2 bytes thanks to pajonk*

Try it online!
> 3 votes

# Answer
# R, ~~44~~ 43 bytes

Crossed out 44 is still regular 44 ;(

This answer already provides a decent solution, but we can save some more bytes.

```
function(x)repeat{cat(x);Sys.sleep(T<-T*2)}

```

Anonymous function taking practically anything printable as argument `x`. Starts at 2 seconds and doubles every time afterwards. Abuses the fact that `T` is by default defined as `TRUE` which evaluates to `1`.

~~Also, as long as this comment still gets a green light from OP, we can make it even shorter, but I don't think it is in the spirit of the challenge.~~ Wait times of 0 are not allowed anymore.

```
function(x)repeat cat(x)

```
> 3 votes

# Answer
## Alice, 16 bytes

```
1/?!\v
T\io/>2*.

```

Try it online! (Not much to see there of course, but you can check how often it was printed within one minute.)

### Explanation

```
1    Push 1 to the stack. The initial pause duration in milliseconds.
/    Reflect to SE. Switch to Ordinal.
i    Read all input.
!    Store it on the tape.
/    Reflect to E. Switch to Cardinal.
>    Move east (does nothing but it's the entry of the main loop).
2*   Double the pause duration.
.    Duplicate it.
     The IP wraps around to the first column.
T    Sleep for that many milliseconds.
\    Reflect to NE. Switch to Ordinal.
?    Retrieve the input from the tape.
o    Print it.
\    Reflect to E. Switch to Cardinal.
v    Move south.
>    Move east. Run another iteration of the main loop.

```
> 3 votes

# Answer
# Cubix, 30 bytes

```
/(?:u<q.;1A>?ou2$/r;w;q^_q.\*/

```

Try it here

This maps onto a cube with side length 3.

```
      / ( ?              # The top face does the delay.  It takes the stack element with the
      : u <              # delay value, duplicates and decrements it to 0.  When 0 is hit the
      q . ;              # IP moves into the sequence which doubles the delay value.
1 A > ? o u 2 $ / r ; w  # Initiates the stack with one and the input.  For input hi this
; q ^ _ q . \ * / . . .  # gives us 1, -1, 10, 105, 104.  There is a little loop that prints
. . . . . . . . . . . .  # each item in the stack dropping it to the bottom until -1 is hit.
      . . .              # Then the delay sequence is started om the top face
      . . .
      . . .

```
> 2 votes

# Answer
# Bash, 37 bytes

```
for((t=1;;t*=2)){ sleep $t;echo $1;};

```

For some reason TIO won't show the output until you stop the program execution.

Try it online!
> 2 votes

# Answer
# PHP, 31 bytes

```
for(;;sleep(2**$i++))echo$argn;
for(;;sleep(1<<$i++))echo$argn;

```

sleeps 1, 2, 4, 8, ... seconds. Run as pipe with `php -nR '<code>'`

Will work until the 63rd print (on a 64 bit machine), after that there will be no more waiting.
Version 1 will yield warnings `sleep() expects parameter 1 to be integer, float given`,
Version 2 will yield one warning `sleep(): Number of seconds must be greater than or equal to 0`.

Insert `@` before `sleep` to mute the warnings.
> 2 votes

# Answer
# TI-Basic, 21 bytes

```
Prompt Str0
1
While 1
Disp Str0
Wait Ans
2Ans
End

```
> 2 votes

# Answer
# JS (ES6), ~~44~~ ~~42~~ ~~40~~ ~~38~~ 36 bytes

Crossed out 44 is still 44

```
i=1,y=x=>setTimeout(y,i*=2,alert(x))

```

Don't like alert bombs?

```
i=1,y=x=>setTimeout(y,i*=2,console.log(x))

```

Technically correct, but loophole-abusing:

```
y=x=>(x&&alert(x),y())

```

-3 bytes thanks to Cyoce, -2 thanks to Business Cat, -2 thanks to Neil
> 1 votes

# Answer
# Python 3, 61 bytes

```
import time;i=1;x=input()
while 1:print(x);time.sleep(i);i*=2

```

Similar to @L3viathan's golf, but uses `while` loop
> 1 votes

# Answer
# CJam, 26 bytes

```
qKes{es1$-Y$<{W$o;2*es}|}h

```

Doesn't work properly on TIO.

The first pause is 20 milliseconds.

**Explanation**

```
q                           e# Push the input.
 K                          e# Push 20 (the pause time).
  es                        e# Push the time (number of milliseconds since the Unix epoch).
    {                       e# Do:
     es1$-                  e#  Subtract the stored time from the current time.
          Y$<{              e#  If it's not less than the pause time:
              W$o           e#   Print the input.
                 ;2*es      e#   Delete the stored time, multiply the pause time by 2, push
                            e#     the new time.
                      }|    e#  (end if)
                        }h  e# While the top of stack (not popped) is truthy.
                            e#  (It always is since the time is a positive integer)

```
> 1 votes

# Answer
# C, 51 bytes

```
main(c,v)char**v;{puts(v[1]);sleep(c);main(2*c,v);}

```

# C, 35 bytes as a function

```
c=1;f(n){puts(n);sleep(c*=2);f(n);}

```

Takes input as a command line argument.
> 1 votes

# Answer
## Batch, 62 bytes

```
@set/at=%2+0,t+=t+!t
@echo %1
@timeout/t>nul %t%
@%0 %1 %t%

```

This turned out to be a byte shorter than explicitly doubling `t` in a loop:

```
@set t=1
:g
@echo %1
@timeout/t>nul %t%
@set/at*=2
@goto g

```
> 1 votes

# Answer
# Reticular, 12 bytes

```
1idp~dw2*~2j

```

Try it online!

## Explanation

```
1idp~dw2*~2j
1               push 1 (initial delay)
 i              take line of input
  d             duplicate it
   p            print it
    ~           swap
     d          duplicate it
      w         wait (in seconds)
       2*       double it
         ~      swap
          2j    skip next two characters
1i              (skipped)
  d             duplicate input
   p            print...
                etc.

```
> 1 votes

# Answer
# PowerShell, ~~35~~ ~~33~~ ~~30~~ 29 Bytes

With a helpful hint from whatever and Joey

```
%{for($a=1){$_;sleep($a*=2)}}

```

## Explanation

```
%{          # Foreach
for($a=1){  # empty for loop makes this infinite and sets $a
$_;         # prints current foreach item
sleep($a*=2)# Start-Sleep alias for $a seconds, reassign $a to itself times 2
}}          # close while and foreach

```

Executed with:

```
"hi"|%{for($a=1){$_;sleep($a*=2)}}

```
> 1 votes

# Answer
## C#, ~~80~~ 79 bytes

```
s=>{for(int i=1;;System.Threading.Thread.Sleep(i*=2))System.Console.Write(s);};

```

*Saved one byte thanks to @raznagul.*
> 1 votes

# Answer
# Python 2, 54 bytes

Uses a lengthy calculation instead of timing libraries.

```
def f(x,a=1):
 while 1:a*=2;exec'v=9**9**6;'*a;print x

```
> 1 votes

# Answer
# Python 3, 49 bytes

```
b=input();x=6**6
while 1:print(b);exec("x+=1;"*x)

```

Uses the slight delay of the `+=` operation and executes it `x` times. `x` doubles by adding one to itself as many times as the value of `x`.

It starts at `6^6` (46656) to stick to the maximum of 5% variation in the delay.
> 1 votes

# Answer
# Perl 6, 39 bytes

```
print(once slurp),.&sleep for 1,2,4...*

```

Try it (`print` overridden to add timing information)

## Expanded:

```
  print(        # print to $*OUT
    once slurp  # slurp from $*IN, but only once
  ),
  .&sleep       # then call sleep as if it was a method on $_

for             # do that for (sets $_ to each of the following)

  1, 2, 4 ... * # deductive sequence generator

```
> 0 votes

# Answer
# Common Lisp, 49 bytes

```
(do((a(read))(i 1(* 2 i)))(())(print a)(sleep i))

```

first delay should be `1` second.
> 0 votes

# Answer
# Pyth, 7 bytes

```
#|.d~yT

```

Explanation:

```
#           Infinitely loop
  .d         Delay for
      T      10 seconds
    ~y       and double T each time
 |           print input every iteration, too

```
> 0 votes

# Answer
## TI-BASIC, 36 bytes

Initial wait period is 1 second.

```
1→L
Input Str1
checkTmr(0→T
While 1
While L>checkTmr(T
End
Disp Str1
2L→L
End

```
> 0 votes

# Answer
# Racket, 51 bytes

```
(λ(s)(do([n 1(* n 2)])(#f)(displayln s)(sleep n)))

```

## Example

```
➜  ~  racket -e '((λ(s)(do([n 1(* n 2)])(#f)(displayln s)(sleep n)))"Hello")'
Hello
Hello
Hello
Hello
Hello
^Cuser break

```
> 0 votes

# Answer
## QBIC, 13 bytes

```
;{?A┘q=q*2_Zq

```

Explanation:

```
;{     Get cmd line param as A$, start an infinite loop
?A┘    Print A$, insert a newline in the QBIC syntax
q=q*2  Double q, which is a num var starting at 1
_Zq    _Z is QBIC's sleep command, this sleeps for q seconds

```
> 0 votes

# Answer
# PHP, 51 bytes

```
<?php $i=1;while(1){echo $argv[1];sleep($i*=2);}?>

```
> 0 votes

# Answer
# APL (Dyalog), 14 bytes

Takes the initial delay (in units of 2 seconds) as left argument and string (any array, actually) as right argument. If this isn't allowed, add the 2 bytes `1∘` to on the left hand side to tie a fixed left argument and thus convert this dyadic function to a monadic one.

```
{(⎕DL⍺×2)∇⎕←⍵}

```

Try it online in a slightly modified version which uses a custom function `∆_` instead of `⎕←`. The function `∆_` displays a timestamp before output.

`{` anonymous function

`⎕←⍵` output the right argument

`(``)∇` call the function itself, but this time with the following argument:

`⍺×2` twice the left argument

`⎕DL`**D**e**l**ay that many seconds, and return the elapsed pause time
> 0 votes

# Answer
## SAS, 93 bytes

```
%macro p(s);%let n=0;%do%while(1);%put &s;%let r=%sysfunc(sleep(%eval((&n+1)*2)));%end;%mend;

```
> 0 votes

# Answer
# Forth, 49 bytes

The function `f` takes a string as a parameter, which can be pushed to the stack with `S" [string]"` or `S\" [string]"` or `s\" [string]"`. See this document for the differences.

```
: g + dup ms dup 2over type recurse ;
: f 1 1 g ;

```

**Try it online** *(Not much to see there of course, but you can check how often it was printed within one minute.)*
> 0 votes

# Answer
# GNU Make, ~~59~~ 58 bytes

```
a:1
%:;echo $X;sleep $*;make -f$(MAKEFILE_LIST) $$(($**2))

```

Uses `$(MAKEFILE_LIST)` for recursion and shell's arithmetic expansion for calculation. The value of `$(MAKE)` is assumed to be just `make`. Could shave 19 more bytes speculating on the value of `$(MAKEFILE_LIST)`, but decided not to.

The input is through `X` variable which is expected to be set on the command line (`X=hi`).

---

This one is more Makey, but also more verbose (82 bytes):

```
P=$(info $X)$(shell sleep $1)$(eval$(call $0,$(shell expr $(1) \* 2)))
$(call P,1)

```

Here, Make is expanding and evaluating a variable recursively. Shell is still used for sleeping and calculation, but that's it.
> 0 votes

# Answer
# S.I.L.O.S, 85 bytes

```
a=1
loadLine
lbla
m=256
M=get m
lblT
printChar M
m+1
M=get m
if M T
wait a
a*2
GOTO a

```

Try it online!

Hey! This isn't the longest one here!
> 0 votes

# Answer
# C, ~~64~~ 63 bytes

```
main(int i,char**s){for(;;){dprintf(2,"%s",s[1]);sleep(i*=2);}}

```

Sleeps four seconds initially. Accepts the first command line argument as the string to repeat.

Or, if I can print a newline:

# C, 53 bytes

```
main(int i,char**s){for(;;){puts(s[1]);sleep(i*=2);}}

```
> 0 votes

# Answer
# shortC, ~~42~~ ~~40~~ 38 bytes

```
AXJargv[1]);Uargc*=2

```

Explanation:

```
A                     start main function
 X                    while...
  J       );          printing...
   argv[1]            the first command-line argument
            Uargc*=2  sleeping for an exponentially growing number of seconds

```
> 0 votes

# Answer
# tcl, 45

```
incr i;while 1 {puts $argv;after [incr i $i]}

```

# demo

---

# Alternative approach with same size

```
while 1 {puts $argv;after [expr 2**[incr i]]}

```

# demo
> 0 votes

# Answer
# VBA, 57 Bytes

Anonymous VBE immediate function that takes input from cell `[A1]` and output that value on the intervals of `86*2^(i-1)` seconds (that is `1 minute 26 seconds` and doubling)

```
i=1:Do:Application.Wait Now+CDate(i/1E3):?[A1]:i=i*2:Loop

```

the time period may be reduced to every `1` second for +2 bytes by replacing `1E3` with `86400`
> 0 votes

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


title: Golf me a card dealer

text:
# Question
Title: Golf me a card dealer
Frank has been working IT his whole life. Each day he responds to tickets, organizes equipment, and reports to his boss. One day, near the closing time on friday, Frank is doing his final inventory and sorting come cables in the supply closet. Suddenly, the door closes and locks from the outside! Such audacity! Frank shakes the door to try and let anyone know that he's stuck in the closet. Blast, nobody comes to his aid. With no cellphone, and no internet connection, Frank settles in with his laptop. After countless games of solitaire, frank decides to make his own card game....

## Challenge:

In this case, you are frank (but not really). Your challenge is to create a dealer that can deal hands of cards, that could be dealt realistically. Your program needs to do 2 things: deal hands of cards according to an input, and take all the hands and reshuffle them. You must do this in the least ammount of bytes possible.

## Rules:

Possible cards include all classic numbers and faces (a,2,3,4,5,6,7,8,9,10,j,q,k) and all suits (c,s,h,d), and two jokers (0j).

If a card is dealt, it cannot be dealt again until the program is given the reshuffle command, or it runs out of cards.

valid inputs are '**d**' to deal a hand of 6 cards, and '**r**' to reshuffle. **NOTE** that you can only deal out 9 hands before you run out of cards. Your program can either:
Automatically reshuffle,
Or give a 'X' to indicate that the dealer is out of cards.

your program needs to be able to take multiple commands over its running span.

All possible hands need to be able to be dealt in every order. Though, your program does **NOT** have to be random.

## Examples:

We deal twice, the first hand yields the 2 of hearts, a 4 of spades, 9 of clubs, a joker, an ace of spades, and a 6 of diamonds. The second hand yields the 3 of hearts, the 10 of diamonds, the 10 of clubs, the king of clubs, the ace of diamonds, and the queen of spades. this is **VALID** because this is possible in real life.

> d
> 2h4s9c0jas6d
> d
> 3h10d10ckcadqs

We deal twice, the first hand yields a mass of 5 cards (indicated by the dashes) and a 6 of hearts. The second hand deals another mass of 5 cards (again, the dashes) and another 6 of hearts. This is **INVALID** because it cannot happen in real life.

> d
> -----6h
> d
> 6h-----

we deal once, reset, and deal again. some of the cards from the first and the second deal match. this is **VALID** because cardstacks are renewed when shuffled.

> d
> 123456
> r
>
> d
> 456789

## Scoring:

As with any golf, the lowest byte count wins! Good luck!

# Answer
> 1 votes
# Pyth - ~~42~~ 41 bytes

Will need to restructure this.

```
VcQ\rj<c9.S++M*+md"jqka"}2T"cshd"m"0j"2lN

```

Try it online here.

Stops giving cards after 9 deals.

# Answer
> 1 votes
## Javascript (ES6), 189 bytes

```
i=>{for(n=52,d=['0j','0j'];n;d[n+1]='123456789JQKA'[--n>>2]+(n<4?0:'')+'cdhs'[n&3]);i.forEach(c=>{c!='r'&&n-54||(d.sort((a,b)=>Math.random()-.5),n=0);c=='d'&&console.log(d.slice(n,n+=6))})}

```

Demo:

```
let F =
i=>{for(n=52,d=['0j','0j'];n;d[n+1]='123456789JQKA'[--n>>2]+(n<4?0:'')+'cdhs'[n&3]);i.forEach(c=>{c!='r'&&n-54||(d.sort((a,b)=>Math.random()-.5),n=0);c=='d'&&console.log(d.slice(n,n+=6))})}

F([..."rddrdddddd"]);
```

# Answer
> 1 votes
## Python 3, ~~184 192~~ 179 bytes

```
d=lambda:[(v+s,'10'+s)[v=='1']for v in'123456789JQKA'for s in'SCHD']+['0J']*2
_=0;c=d()
while 1:
 if input()<'r'*(len(c)>5):[print(c.pop())for i in'_'*6]
 else:c=d();del c[_];_+=1

```

Edit: jokers Edit 2: switched from using random and shuffling the list to cycling through the list and deleting 1 index from it incrementally.

Try it

# Answer
> 1 votes
## 05AB1E, 56 bytes

Automatically reshuffles.

```
9L>"ajqk"Sì"cshd"â€J„0jD‚ì©UvXg>y'rQ~i®U}y'dQiX.r6ô¬,¦˜U

```

**Explanation**

Generate the list of cards:

```
9L>"ajqk"Sì                     # list of card values, excluding jokers
           "cshd"â€J            # cartesian product with suits to generate all cards except jokers
                    „0jD‚ì      # add the jokers
                          ©U    # store in register and X

```

The actual function:

```
v                             # for each in input
         i  }                 # if
 Xg>                          # we're out of cards
        ~                     # or
    y'rQ                      # it's an explicit reshuffle
          ®U                  # get full list of cards from register and store in X
                              # then
             y'dQi            # if it's a draw
                  X.r         # shuffle current list of cards
                     6ô¬,     # print a list of 6 cards
                         ¦˜U  # save the rest of the cards in X

```

Try it online

# Answer
> 1 votes
## PHP, 342 bytes

Update of @hd-s version.

```
$c=explode(",","2,3,4,5,6,7,8,9,T,J,Q,K,A");$a=["h"=>$c,"d"=>$c,"s"=>$c,"c"=>$c,"0"=>["J","J"]];$b=$a;$f=0;foreach(explode(",",$argv[1])as$g){if($g=='d'&&$f<54){$f+=6;for($i=0;$i<6;$i++){$s=array_keys($a)[rand(0,4)];$l=rand(1,count($a[$s])-1);if(isset($a[$s][$l])){echo$a[$s][$l].$s;unset($a[$s][$l])}else{$i--}}echo PHP_EOL}else{$f=0;$a=$b}}

```

Please test before qualifying. PHP 5.3+

## Changes:

* All variables renamed to be 1 byte long
* The card array is just reset at the end
* All cards dealt check shortened
* Couple of spaces removed

Total bytes saved: **69**

# Answer
> 0 votes
## PowerShell v2+, ~~174~~ 158 bytes

```
$a=(2..10+[char[]]'ajqk'|%{$i=$_;[char[]]'cshd'|%{"$i$_"}})+'0j'+'1j';$x=,0
for(){switch(read-host){'d'{$a|?{$_-notin$x}|Random -c 6|%{$x+=$_;$_}}'r'{$x=,0}}}

```

Creates an array of the number and suit combinations, plus two jokers (note they're unique), stores that into `$a`. This forms our full deck. Sets array `$x` equal to `[0]`. This represents the cards that we've already dealt. Then enters an infinite `for` loop. Performs a `read-host` to get the `d` or `r` (other behavior is undefined).

For `d`ealing, pipes `$a` a `Where-Object` to pull out the items that are `-notin$x` (i.e., the cards we haven't dealt yet). Those are piped to `Get-Random` with a `-c`ount of `6`, which will randomly select 6 distinct elements. We store those newly-dealt cards into `$x`, and the card is placed `$_` onto the pipeline, which will get flushed when the next `read-host` happens and output one-per-line thanks to the default behavior of `Write-Output`. If the user attempts to `d`eal when `$a = $x` (i.e., all cards have been dealt), then the `Get-Random` will be selecting from nothing, and so nothing will be output.

For the `r`eshuffling, we just set `$x` back to `,0` as the original array.

Note you'll need to `ctrl-c` or otherwise force quit the program.

### Example execution

```
PS C:\Tools\Scripts\golfing> .\golf-card-dealer.ps1
d
8c
5h
as
ah
1j
ac
d
5d
2h
8s
6h
2c
qs
d
8h
6d
10c
10h
6s
4h
d
js
9h
4c
6c
qd
kd
d
3d
jc
8d
2s
3h
4d
d
kh
jd
3c
0j
jh
10d
d
9s
7s
ks
kc
qc
9d
d
5s
9c
7c
4s
10s
7d
d
7h
5c
3s
qh
2d
ad
d
d
d
r
d
3c
qs
2s
kd
2h
qc
d
ks
2d
5s
qd
kc
js

PS C:\Tools\Scripts\golfing>

```

# Answer
> 0 votes
## PHP, 411 bytes

This will generate a random outcome for each play (each deal(`d`)) and then once it's used all the cards, it will reshuffle the deck, clearing the play space.

To run, input comma separated commands: `php card_dealer_golf.php d,d,d,d,r`

```
$c=explode(",","a,2,3,4,5,6,7,8,9,10,j,q,k");$a=["h"=>$c,"d"=>$c,"s"=>$c,"c"=>$c,"0"=>["J","J"]];$cd=0;foreach(explode(",",$argv[1]) as $cmd){if($cd>=54){$cmd="r";}if($cmd=='d'){$cd+=6;for($i=0;$i<6;$i++){$s=array_keys($a)[rand(0,4)];$l=rand(1,count($a[$s])-1);if(isset($a[$s][$l])){echo$a[$s][$l].$s;unset($a[$s][$l]);}else{$i--;}}echo PHP_EOL;}else{$cd=0;$a=["h"=>$c,"d"=>$c,"s"=>$c,"c"=>$c,"0"=>["J","J"]];}}

```

Output:

```
$ php card_dealer_golf.php d,d,d,d,r
10djs5cjh2h3h
3cJ06d2d7d3s
9s6s7h4d6c4s
10c4c3d7c8h6h

```

Ungolfed version

```
$cards = explode(",","a,2,3,4,5,6,7,8,9,10,j,q,k");
$a = [
        "h" => $cards,
        "d" => $cards,
        "s" => $cards,
        "c" => $cards,
        "0" => ["J","J"]
    ];
$cd=0;
foreach(explode(",",$argv[1]) as $cmd) {
        if($cd>=54) {$cmd = "r";}
        if($cmd=='d'){
                $cd+=6; //+6 cards dealt
                for($i=0;$i<6;$i++){
                    $suit = array_keys($a)[rand(0,4)]; //get random suit
                    $l=rand(1,count($a[$suit])-1); //get random card from suit
                    if(isset($a[$suit][$l])){ //if the card is still in the deck
                        echo $a[$suit][$l].$suit; //output it
                        unset($a[$suit][$l]); //remove from deck
                    }else{
                        $i--; //card not in deck, decrease the cards dealt in this round to be regenered
                    }
                }
                echo PHP_EOL;
        }else{
                //reshuffle logic. reset deck and amount of cards dealth
                $cd=0;
                $a = [
                        "h" => $cards,
                        "d" => $cards,
                        "s" => $cards,
                        "c" => $cards,
                        "0" => ["J","J"]
                ];
        }
}

```

---
Tags: code-golf, card-games
---


title: Convert phones to calculation

text:
# Question
Title: Convert phones to calculation
# Introduction

OnePlus is a Chinese smartphone manufacturer founded in December 2013. Their latest phone, OnePlus 5, was unveiled on June 20, 2017.

I am sure you have seen that the name of the phone can easily be translated to a sum.

`OnePlus` can be written like `1+` thus `OnePlus 2 = (1+ 2) = 3`

# Input

The name of one OnePlus phone. The above list in the only possible input

```
OnePlus 1
OnePlus 2
OnePlus X
OnePlus 3
OnePlus 3T
OnePlus 5

```

# Output

The sum of the name (a number **not a string**)

```
OnePlus 1 => 2
OnePlus 2 => 3
OnePlus X => an integer
OnePlus 3 => 4
OnePlus 3T => 27 (T = Today = 23 thus 1+3+23=27)
OnePlus 5 => 6

```

# Rules

The input can be written in different versions. This applies to every names. For example

```
OnePlus 1
OnePlus1
One+ 1
One+1
1+ 1
1+1

```
* The output for `OnePlus X` is an integer that should be different from the other phones names. Whatever you want except `2,3,4,27,6`
* The `T` in `OnePlus 3T` will always be `23` which is the day I am posting this.
* This is , so the shortest solution (in bytes) wins.

# Answer
# 05AB1E, 10 bytes

```
0Uθ.VT26:>

```

Try it online!

`θ` has been replaced by `®è` on TIO since it hasn't been pulled there yet. Alternatively, `¤` would work too.

Explanation:

```
0Uθ.VT26:> "Accepts a single line from STDIN"\
0          "Push 0"\
 U         "Assign to X"\
  θ        "(implicit input)"\ "Take the last element"\
   .V      "Eval as 05AB1E code"\
     T     "Push 10"\
      26   "Push 26"\
        :  "Infinitely replace"\
         > "Increment"\

```
> 1 votes

# Answer
# Retina, ~~26~~ 16 bytes

*-10 bytes thanks to @MartinEnder*

```
O
1
T
995
.
$*
1

```

Try it online!
> 3 votes

# Answer
# Perl 5, 21 bytes

20 bytes of code + `-p` flag.

```
$_=/\d$/?$&+1:27*/T/

```

Try it online!

If the input ends with an integer (`/\d$/`), then we add one to it (`$&+1`) and outputs it. Otherwise, we output `27*/T/` which is `27` if the inputs contains a `T`, and `0` otherwise.
> 1 votes

# Answer
# C# (.NET Core), 138 bytes

```
using System.Linq;s=>s.Replace("One","1").Replace("Plus","+").Replace("T","+23").Replace("X","9").Split('+').Select(e=>int.Parse(e)).Sum()

```

Try it online!
> 0 votes

# Answer
# Java 8, ~~79~~ 61 bytes

```
s->{int x=s.charAt(s.length()-1);return x<58?x-47:x<85?27:9;}

```

**Explanation:**

Try it here with all possible test cases.

```
s->{                             // Method with String parameter and integer return-type
  int x=s.charAt(s.length()-1);  //  Get the last characters of the input
  return x<58?                   //  If it's a digit:
          x-47                   //   Return that digit + 1
         :x<85?                  //  Else if it's a 'T':
          27                     //   Return 27
         :                       //  Else (it's a 'X')
          9;                     //   Return 9 (unique digit other than 2,3,4,6,27)
}                                // End of method

```
> 0 votes

# Answer
# C (gcc), ~~65~~ ~~63~~ 48 bytes

```
f(char*s){s+=strlen(s)-1;s=*s?*s^84?*s-47:27:9;}

```

Try it online!
> 0 votes

# Answer
# Excel VBA, ~~87~~ 51 bytes

Anonymous VBE immediate window function that takes input from cell `[A1]` and outputs OnePlus math to the VBE immediate window

```
i=Asc(Right([A1],1)):?IIf(i<58,i-47,IIf(i<85,27,9))

```

## Old Version

Anonymous VBE immediate window function that takes input from cell `[A1]` that and outputs OnePlus math to the VBE immediate window

```
?Application.Evaluate("="&Replace(Replace(Replace([A1],"One",1),"Plus","+"),"T","+23"))

```

### Input/Output

As a result of the `Application.Evaluate` call this solution is afforded access to all of the Excel WorkSheet Functions

```
[A1]="OnePlus 3T"
?Application.Evaluate("="&Replace(Replace(Replace([A1],"One",1),"Plus","+"),"T","+23"))
 23

[A1]="OnePlusPi()"
?Application.Evaluate("="&Replace(Replace(Replace([A1],"One",1),"Plus","+"),"T","+23"))
 4.14159265358979

[A1]="One+Day(Now())"
?Application.Evaluate("="&Replace(Replace(Replace([A1],"One",1),"Plus","+"),"T","+23"))
 26

```
> 0 votes

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


title: Plant trees on a golf course!

text:
# Question
Title: Plant trees on a golf course!
This challenge is inspired by this app.

---

This is a much easier version of this challenge. This challenge is , while the other one is .

---

You'll be given a square input grid, of dimensions **6-by-6** which is divided into **6** areas, where the cells of each area have a unique identifier (I'll use lower case letters from **a-f** in the the text here, but you may choose whatever you like, for instance integers **1-6**).

The input may look like this (optional input format):

```
aabbbb
aabbbb
aaccbb
acccdb
ecccdb
eeefff

```

Or, easier to visualize:

## Challenge:

You are to place **6** trees in this park, according to the following rules:

* There shall be exactly **1** tree per column, and **1** tree per row
* All areas shall have exactly **1** tree.
* No trees can be adjacent to another tree, vertically, horizontally or diagonally

The solution to the layout above is:

Note: There is only one solution to each puzzle

### Additional rules:

* The input and output formats are optional
    + The output might for instance be a list of indices, a grid with **1/0** indicating if there's a tree in that position, or a modified version of the input where the trees are indicated
* The execution time must be deterministic
* The program must finish within 1 minute on a reasonable modern laptop
* Brownie points if you don't brute force!

### Test cases:

```
aabbbb
aabbbb
aaccbb
acccdb
ecccdb
eeefff
---
aAbbbb
aabbbB
aaCcbb
acccDb
Ecccdb
eeeFff
----------
aabccc
aacccc
aaddce
aeeeee
aeeefe
eeeeee
---
aaBccc
aacccC
aadDce
Aeeeee
aeeeFe
eEeeee
----------
aaaabb
aacbbb
aadddb
addeef
ddddee
dddeee
---
aaaaBb
aaCbbb
Aadddb
addeeF
dDddee
dddEee
----------
abbbcd
abebcd
addddd
dddddd
effdff
eeffff
---
abBbcd
abebCd
Addddd
dddDdd
effdfF
eEffff

```

Same test cases on a format that's a bit easier to parse:

```
Test case 1:
[1,1,2,2,2,2;1,1,2,2,2,2;1,1,3,3,2,2;1,3,3,3,4,2;5,3,3,3,4,2;5,5,5,6,6,6]
Test case 2:
[1,1,2,3,3,3;1,1,3,3,3,3;1,1,4,4,3,5;1,5,5,5,5,5;1,5,5,5,6,5;5,5,5,5,5,5]
Test case 3:
[1,1,1,1,2,2;1,1,3,2,2,2;1,1,4,4,4,2;1,4,4,5,5,6;4,4,4,4,5,5;4,4,4,5,5,5]
Test case 4:
[1,2,2,2,3,4;1,2,5,2,3,4;1,4,4,4,4,4;4,4,4,4,4,4;5,6,6,4,6,6;5,5,6,6,6,6]

```

# Answer
# C, ~~223~~ 182 bytes

```
O[15],U;main(y,v)char**v;{if(y>7)for(;y-->2;printf("%06o\n",O[y]));else for(int*r,x=1,X=8;X<14;U&x|*r|O[10-y]*9&x*9?0:(U^=O[9-y]=*r=x,*r=main(y+1,v),U^=x),x*=8)r=O+v[1][y*7-++X]-88;}

```

Takes input as an argument in the format given in the question. Writes output to stdout as a grid of 0s with 1s where the trees go.

```
./TreesMin 'aabbbb
aabbbb
aaccbb
acccdb
ecccdb
eeefff'

```

Sample output:

```
010000
000001
001000
000010
100000
000100

```

## Breakdown

```
O[15],                                  // Tree positions & region usage
U;                                      // Column usage (bitmask)
main(y,v)char**v;{                      // Recursive main function
  if(y>7)                               // Finished grid?
    for(;y-->2;printf("%06o\n",O[y]));  //  Print it (rows are padded octal)
  else                                  // Not finished:
    for(int*r,x=1,X=8;X<14;             //  Loop over columns
      U&x|*r|O[10-y]*9&x*9              //   Current cell violates rules?
        ?0                              //    Do nothing
        :(U^=O[9-y]=*r=x,               //   Else: mark cell
          *r=main(y+1,v),               //    Recurse
          U^=x)                         //    Unmark cell
      ,x*=8)                            //   Advance to next column
      r=O+v[1][y*7-++X]-88;             //   Region pointer for current iteration
}

```

It's an adaptation of my answer to the fastest-code version of this question. Doesn't have as much short-circuiting, but it's plenty fast enough for 6x6 grids.
> 2 votes

# Answer
# Clingo, 66 bytes

```
1{t(X,Y):c(X,Y,Z)}:-Z=1..n.:-t(X,Y),2{t(X,J;I,Y;X-1..X+1,Y..Y+1)}.

```

Run with `clingo plant.lp - -c n=<n>` where `<n>` is the grid size. The input format is a list of `c(X,Y,Z).` statements for each cell (`X`, `Y`) colored `Z`, with 1 ≤ `X`, `Y`, `Z``n`, separated by optional whitespace. The output includes `t(X,Y)` for each tree at (`X`, `Y`).

### Demo

```
$ clingo plant.lp - -c n=6 <<EOF
> c(1,1,1). c(2,1,1). c(3,1,2). c(4,1,2). c(5,1,2). c(6,1,2).
> c(1,2,1). c(2,2,1). c(3,2,2). c(4,2,2). c(5,2,2). c(6,2,2).
> c(1,3,1). c(2,3,1). c(3,3,3). c(4,3,3). c(5,3,2). c(6,3,2).
> c(1,4,1). c(2,4,3). c(3,4,3). c(4,4,3). c(5,4,4). c(6,4,2).
> c(1,5,5). c(2,5,3). c(3,5,3). c(4,5,3). c(5,5,4). c(6,5,2).
> c(1,6,5). c(2,6,5). c(3,6,5). c(4,6,6). c(5,6,6). c(6,6,6).
> EOF
clingo version 5.1.0
Reading from plant.lp ...
Solving...
Answer: 1
c(1,1,1) c(2,1,1) c(3,1,2) c(4,1,2) c(5,1,2) c(6,1,2) c(1,2,1) c(2,2,1) c(3,2,2) c(4,2,2) c(5,2,2) c(6,2,2) c(1,3,1) c(2,3,1) c(3,3,3) c(4,3,3) c(5,3,2) c(6,3,2) c(1,4,1) c(2,4,3) c(3,4,3) c(4,4,3) c(5,4,4) c(6,4,2) c(1,5,5) c(2,5,3) c(3,5,3) c(4,5,3) c(5,5,4) c(6,5,2) c(1,6,5) c(2,6,5) c(3,6,5) c(4,6,6) c(5,6,6) c(6,6,6) t(1,5) t(2,1) t(6,2) t(3,3) t(5,4) t(4,6)
SATISFIABLE

Models       : 1+
Calls        : 1
Time         : 0.045s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

```

To make the input/output format easier to deal with, here are Python programs to convert from and to the format given in the challenge.

### Input

```
import sys
print(' '.join("c({},{},{}).".format(x + 1, y + 1, ord(cell) - ord('a') + 1) for y, row in enumerate(sys.stdin.read().splitlines()) for x, cell in enumerate(row)))

```

### Output

```
import re
import sys
for line in sys.stdin:
    c = {(int(x), int(y)): int(z) for x, y, z in re.findall(r'\bc\((\d+),(\d+),(\d+)\)', line)}
    if c:
        t = {(int(x), int(y)) for x, y in re.findall(r'\bt\((\d+),(\d+)\)', line)}
        n, n = max(c)
        for y in range(1, n + 1):
            print(''.join(chr(ord('aA'[(x, y) in t]) + c[x, y] - 1) for x in range(1, n + 1)))
        print()

```
> 1 votes

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


title: Game of Life and Fatigue

text:
# Question
Title: Game of Life and Fatigue
Stewie's Game of Life and Fatigue is quite similar to the more famous Conway's Game of Life.

---

The universe of the Stewie's Game of Life and Fatigue (GoLF) is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of three possible states, alive, dead or tired. Every cell interacts with its eight neighbors, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

* Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
* Any live cell with two or three live neighbours lives on to the next generation.
* Any live cell with more than three live neighbours dies, as if by overpopulation.
* Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
* **Any cell that has been alive for two consecutive generations dies, as if by fatigue.** It can't wake to life again until next generation
* **Any cell that is outside the boundary of the input grid are dead, as if it's fallen off a cliff.**

---

# Challenge:

Your challenge is to take a grid of dimensions **n-by-m** representing the initial state of a GoLF, and an integer **p**, and output the state of the Game after **p** generations.

### Rules:

* Input and output formats are optional, but the input/output grids should have the same representation
* You may choose any printable symbols to represent live and dead cells (I'll use `1` for live cells and `0` for dead cells).
* You may choose if you have 0 or 1-indexed. In the examples, `p=1` means the state after one step.
* Shortest code in each language wins
* Built-in function for cellular automation are allowed

---

### Test cases:

In the examples, I've only included the input grid in the input, not **p**. I've provided outputs for various **p**-values. You shall only output the grid that goes with a given input **p**.

```
Input:
0   0   0   0   0
0   0   1   0   0
0   0   1   0   0
0   0   1   0   0
0   0   0   0   0

--- Output ---
p = 1
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

p = 2
0   0   0   0   0
0   0   1   0   0
0   0   0   0   0
0   0   1   0   0
0   0   0   0   0

p = 3 -> All dead
---

Input:
0   1   0   0   0   0
0   0   1   0   0   0
1   1   1   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0

--- Output ---
p = 1
0   0   0   0   0   0
1   0   1   0   0   0
0   1   1   0   0   0
0   1   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0

p = 2
0   0   0   0   0   0
0   0   0   0   0   0
1   0   0   0   0   0
0   1   1   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0

p = 3
0   0   0   0   0   0
0   0   0   0   0   0
0   1   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0
0   0   0   0   0   0

p = 4 -> All dead
Input
0   1   1   0   1   1   0
1   1   0   1   1   1   1
0   1   0   0   0   1   0
0   0   0   1   1   0   1
1   0   0   1   0   1   1
0   0   1   1   0   1   1
1   1   0   0   0   0   1

--- Output ---
p = 1
1   1   1   0   0   0   1
1   0   0   1   0   0   1
1   1   0   0   0   0   0
0   0   1   1   0   0   1
0   0   0   0   0   0   0
1   0   1   1   0   0   0
0   1   1   0   0   1   1

p = 2
1   0   0   0   0   0   0
0   0   0   0   0   0   0
1   0   0   1   0   0   0
0   1   1   0   0   0   0
0   1   0   0   0   0   0
0   0   0   0   0   0   0
0   0   1   1   0   0   0

p = 3
0   0   0   0   0   0   0
0   0   0   0   0   0   0
0   1   1   0   0   0   0
1   1   0   0   0   0   0
0   1   1   0   0   0   0
0   0   1   0   0   0   0
0   0   0   0   0   0   0

p = 4
0   0   0   0   0   0   0
0   0   0   0   0   0   0
1   1   1   0   0   0   0
1   0   0   0   0   0   0
1   0   1   0   0   0   0
0   1   1   0   0   0   0
0   0   0   0   0   0   0

p = 5
0   0   0   0   0   0   0
0   1   0   0   0   0   0
1   0   0   0   0   0   0
0   0   1   0   0   0   0
1   0   0   0   0   0   0
0   1   0   0   0   0   0
0   0   0   0   0   0   0

p = 6
0   0   0   0   0   0   0
0   0   0   0   0   0   0
0   1   0   0   0   0   0
0   1   0   0   0   0   0
0   1   0   0   0   0   0
0   0   0   0   0   0   0
0   0   0   0   0   0   0

p = 7
0   0   0   0   0   0   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   0   0   0   0   0
0   0   0   0   0   0   0

p = 8
0   0   0   0   0   0   0
0   0   0   0   0   0   0
0   1   0   0   0   0   0
0   0   0   0   0   0   0
0   1   0   0   0   0   0
0   0   0   0   0   0   0
0   0   0   0   0   0   0

p = 9 -> All dead

```

Yes, I'm aware that all initial seeds won't end in all cells being dead.

# Answer
# Golly RuleLoader, 295 bytes

```
@RULE Y
@TABLE
n_states:3
neighborhood:Moore
symmetries:permute
var z={1,2}
var y=z
var x=z
var w=z
var u=z
var a={0,z}
var b=a
var c=a
var d=a
var e=a
var f=a
var g=a
var h=a
0,z,y,x,0,0,0,0,0,1
z,a,0,0,0,0,0,0,0,0
z,y,x,w,u,a,b,c,d,0
2,a,b,c,d,e,f,g,h,0
1,a,b,c,d,e,f,g,h,2
@COLORS
2 255 0 0

```

Input grid should be pasted in, boundaries are in the rulename (eg `5`*`3` is `Y:P5,3`), press space to advance.
> 4 votes

# Answer
# MATL, ~~34~~ ~~30~~ 25 bytes

*5 bytes removed thanks to a suggestion by @CalculatorFeline!*

```
0ii:"wy*~wt3Y6QZ+5:7mb*]&

```

Try it online!

Inputs are a matrix and a number. The matrix uses `;` as row separator. The matrices for the three test cases are entered as

```
[0 0 0 0 0; 0 0 1 0 0; 0 0 1 0 0; 0 0 1 0 0;0 0 0 0 0]
[0 1 0 0 0 0; 0 0 1 0 0 0; 1 1 1 0 0 0; 0 0 0 0 0 0; 0 0 0 0 0 0; 0 0 0 0 0 0; 0 0 0 0 0 0]
[0 1 1 0 1 1 0; 1 1 0 1 1 1 1; 0 1 0 0 0 1 0; 0 0 0 1 1 0 1; 1 0 0 1 0 1 1; 0 0 1 1 0 1 1; 1 1 0 0 0 0 1]

```

### Explanation

```
0     % Push 0. This represents the generation previous to the input one. Actually
      % This should be an array of zeros, but thanks to broadcasting it is
      % equivalent (and saves bytes)
i     % Input: array with starting generation
i     % Input: number of iterations, p.
      % STACK (bottom to top): 0, array with initial generation, p
:"    % Do the following p times
      %   STACK: previous gen, current gen
  wy  %   Swap, duplicate from below
      %   STACK: current gen, previous gen, current gen
  *~  %   Multiply element-wise, negate. This creates a mask of cells that do not
      %   die of fatigue (they were 0 in the current or in the previous generation)
      %   STACK: current gen, fatigue mask
  wt  %   Swap, duplicate
      %   STACK: Fatigue mask, current gen, current gen
  3Y6 %   Push predefined literal: 8-neighbourhood: [1 1 1; 1 0 1; 1 1 1]
      %   STACK: Fatigue mask, current gen, current gen, 8-neighbourhood
  Q   %   Add 1 element-wise. This gives [2 2 2; 2 1 2; 2 2 2], which will be
      %   used as convolution kernel. Active cells with 2 neighbours will give 5;
      %   inactive cells with 3 neighbours will give 6; and active cells with 3
      %   neighbours will give 7
      %   STACK: Fatigue mask, current gen, current gen, convolution kernel
  Z+  %   2D convolution, keeping size
      %   STACK: Fatigue mask, current gen, convolution result
  5:7 %   Push array [5 6 7]
  m   %   Ismember, element-wise. Cells that give true will survive, unless fatigued
      %   STACK: Fatigue mask, current gen, cells that can survive
  b   %   Bubble up
      %   STACK: Current gen, cells that can survive, fatigue mask
  *   %   Multiply element-wise. This tells which cells survive considering fatigue.
      %   The result is the new generation
      %   STACK: "Current" gen which now becomes old, "new" gen which now becomes
      %   current
]     % End
&     % Specify that implicit display will show only top of the stack

```
> 3 votes

# Answer
# APL (Dyalog Classic 16.0), 59 bytes

```
⌊{((3∊⌊{⍵,⍵-c}+/,⍵)∧.1>1|c)×(.1×c)+1⌈c←2 2⌷⍵}⎕U233A 3 3⍣⎕⊢⎕

```

Try it online! (emulated on Classic 15.0)

---

# APL (Dyalog Unicode 16.0), 85 bytes

```
⌊{((3∊⌊{⍵,⍵-c}+/,⍵)∧.1>1|c)×(.1×c)+1⌈c←2 2⌷⍵}⌺3 3⍣⎕⊢⎕

```

Try it online! (emulated on Unicode 15.0)

---

Prompts for grid and then for **p**. Prints the new grid after **p** generations.

Note that this uses the new  (Stencil) primitive which is not included in the Classic character set, hence a shorter version and a less-bytes version.

Explanation to follow…
> 3 votes

# Answer
# Java 8, 333 bytes

```
int[][]G(int p,int[][]s){for(int h=s.length,w=s[0].length,y,x,n,a,b,t[][]=new int[h][w],i=0;i++<2*p;)for(y=0;y<h;++y)for(x=0;x<w;++x)if(i%2>0){for(n=0,a=y-2;++a<y+2;)for(b=x-2;++b<x+2;)n+=a>=0&a<h&b>=0&b<w&(a!=y|b!=x)&&s[a][b]>0?1:0;t[y][x]=s[y][x]<1?n==3?1:0:n<2|n>3|s[y][x]>1?0:2;}else s[y][x]=i==2*p&t[y][x]>1?1:t[y][x];return s;}

```

Explanation:

```
int[][]G(int p,int[][]s){
    for(int h=s.length,w=s[0].length,y,x,n,a,b,t[][]=new int[h][w],       //height, width, vars, temp array
            i=0;i++<2*p;)                                                 //for 2*generations: 1. calculate in temporary t, 2. copying to s
        for(y=0;y<h;++y)                                                  //for each row
            for(x=0;x<w;++x)                                              //for each column
                if(i%2>0){                                                //1. calculate
                    for(n=0,a=y-2;++a<y+2;)                               //n = number of alive cells around [y][x]. row above, at and below y
                        for(b=y-2;++b<y+2;)                               //column left, at and right of x
                            n+=a>=0&a<h&b>=0&b<w&(a!=y|b!=x)&&s[a][b]>0?1:0;    //if within bounds and not the cell itself, add 1 if alive.
                    t[y][x]=s[y][x]<1?n==3?1:0:n<2|n>3|s[y][x]>1?0:2;     //save next state in temporary, depending on rules. alive cells become 2.
                }
                else                                                      //2. copy temporary t to s
                    s[y][x]=i==2*p&t[y][x]>1?1:t[y][x];                   //if last generation, replace 2 by 1
    return s;
}

```
> 2 votes

---
Tags: code-golf, grid, matrix, cellular-automata, game-of-life
---


title: Stealing sequences: Robbers

text:
# Question
Title: Stealing sequences: Robbers
This is . This is the **Robbers** thread. For the cops thread, go here.

I've noticed a number of OEIS challenges since I joined the site. It seems only fair that we have a cops-and-robbers challenge that determines who is the master of online integer sequences, once and for all.

## Cops

Write a program or function that, given no input, deterministically prints any sequence from the OEIS. By deleting some subset of the characters, your program must be able to print a different OEIS sequence when run in the same language. The new sequence must be entirely new, not just the first by a different name or with a different offset. Neither sequence may be simply a repeated constant value.

You must provide the first function, along with the name of the OEIS sequence so correctness can be verified. It's OK if behavior gets questionable around your language's MAX\_INT value or 256, whichever is larger.

## Robbers

Delete characters from some Cop's submission such that your new program outputs any other sequence from the OEIS. Provide the new function along with the name of the new OEIS sequence. Your new sequence may not simply be a repeated constant value.

It's in your best interest to delete as many characters from the Cop's submission as possible. If another robber (anyone except the Cop who authored the original program) comes along and finds a shorter solution that finds another *different* sequence, that robber steals your point. (Note that simply golfing off characters and printing the same sequence is not sufficient to steal the point.)

## Rules & Scoring

If, after one week, nobody has been able to crack your solution, you can mark your solution as safe by providing the second program along with the name of the sequence it generates.

You get one point for each safe posting and one point for each submission you crack. Note that another robber can steal your point from the cracked submission at any time by providing a shorter program that yields a different sequence.

Cops may only post one challenge per language.

The player with the most points at 12:00 UTC on 7 July wins.

# Answer
> 5 votes
# C (gcc), Govind Parmar 142 bytes deleted

Golfed more thanks to @StephenS. I'm not sure it matters, but just for the spirit of the site!

```
#include<stdio.h>
#include<limits.h>
main(){int i,n;for(i=0;i<INT_MAX;i++){n=i;printf("%d,",n);}}

```

Try it online!

Sequence: A001477

# Answer
> 2 votes
PHP, Jörg Hülsermann, 1 byte deleted

```
for(;;)echo+$i,",";

```

Produces A000004

# Answer
> 2 votes
# MarioLANG, marcosm, 13 bytes deleted

```
>+:<
===#=

```

Try it online!

A109613.

# Answer
> 2 votes
# cQuents, Stephen S, 1 byte deleted

```
=0,11:z+y

```

A022345.

# Answer
> 1 votes
# PHP, Jörg Hülsermann, 5 bytes deleted

```
for(;;)echo+$i;

```

Produces A000004

# Answer
> 1 votes
# Python 2, juniorRubyist, 253 bytes deleted

```
while True:print 6,4

```

Try it online!

Not sure how valid this is, because of the newlines, but I believe whitespace is irrelevant. TIL that if I could add a comma at the end, it would fix the whitespace.

A226294

# Answer
> 0 votes
# Python 2, juniorRubyist, 114 bytes deleted cracked

```
import zlib, base64;exec(zlib.decompress(base64.b64decode('eJzLtDUAAAHoANc=')))
while True:print i,;exec(zlib.decompress(base64.b64decode('eJzL1LY1BAAC1AED')))

```

Try it online!

A001477.

---
Tags: sequence, cops-and-robbers, rosetta-stone
---


# Question
Title: Classify Quadrilaterals | Help me with my math exam!
Help! My math exam is coming up soon and I didn't study! 1 Part of the exam is to classify a quadrilateral given its vertex coordinates, which I, unfortunately, do not know how to do. 2

So, your challenge is to write a program to do this for me so I don't fail!

# Challenge

Given four vertices such that no three of them are colinear, determine the most specific classification of the quadrilateral formed by those four vertices.

What I mean by "most specific classification" is that even though all squares are rectangles, if the shape is a square, you should indicate that it is a square and not indicate that it is a rectangle.

# Input

Input will be given as four (x, y) coordinates. You may take these as a list of length 4 of lists/tuples of length 2. Alternatively, you can take input as a list of the x-coordinates and a list of the respective y-coordinates.

For example, if my shape has vertices at points `(0, 0)`, `(5, 0)`, `(6, 1)`, and `(1, 1)`, you may choose to take input in either of the following formats or something similar:

```
[(0, 0), (5, 0), (6, 1), (1, 1)]
([0, 5, 6, 1], [0, 0, 1, 1])

```

You may assume that the quadrilateral is not self-intersecting and that the points are given in the correct order (that is, two consecutive points in the input will be connected by a line segment in the quadrilateral).

# Output

You will need a unique output for each of the following classes of quadrilaterals:

* Square
* Rectangle
* Rhombus
* Parallelogram
* Trapezoid/Trapezium
* Kite
* Quadrilateral

This could be the exact name itself, a character, an integer, etc.

# Rules

* Standard Loopholes Apply
* If your programming language has a built-in that will perform this exact task, that built-in is not allowed.
* Built-ins for finding the distance between two points are allowed.
* Built-ins for finding the angle between two lines are allowed.

At this point, if you know all of the terms, you are ready to start programming! (Test Cases are at the end)

# Terminology

This section is for anyone who needs clarification on the definitions of the different shapes.

## Square

A quadrilateral is a square if and only if all 4 of its sides are equal in length and every pair of adjacent sides is perpendicular (that is, it is both a rectangle and a rhombus).

## Rectangle

A quadrilateral is a rectangle if and only if every pair of adjacent sides is perpendicular.

## Rhombus

A quadrilateral is a rhombus if and only if all 4 of its sides are equal.

## Parallelogram

A quadrilateral is a parallelogram if and only if each pair of opposite sides is parallel and each pair of opposite angles is equal. Both of these conditions imply each other so you only need to check for one of them.

## Trapezoid/Trapezium

A quadrilateral is a trapezoid/trapezium if and only if it has at least one pair of parallel sides.

## Kite

A quadrilateral is a kite if two opposite pairs of adjacent sides are equal in length; that is, two of its adjacent sides are equal and the other two are also equal.

# Test Cases

```
input as (x, y) * 4 -> full name
[(0, 0), (1, 0), (1, 1), (0, 1)] -> square
[(0, 0), (1, 1), (-1, 3), (-2, 2)] -> rectangle
[(0, 0), (5, 0), (8, 4), (3, 4)] -> rhombus
[(0, 0), (5, 0), (6, 1), (1, 1)] -> parallelogram
[(0, 0), (4, 0), (3, 1), (1, 1)] -> trapezoid/trapezium
[(0, 0), (1, 1), (0, 3), (-1, 1)] -> kite
[(0, 0), (2, 0), (4, 4), (0, 1)] -> quadrilateral

```

# Links (Desmos Graphing Calculator)

Here are links to visualizations of each of the test cases.

Square
Rectangle
Rhombus
Parallelogram
Trapezoid/Trapezium
Kite
Quadrilateral

# Winning Criteria

I can't bring a computer into the exam obviously, so I need you to write the shortest code possible so I can memorize it. I need to write it into the margins and run it using TryItOfflineTM so to fit it into the margins your program needs to be as small as possible!

1 Of course I actually did :P
2 Of course I actually do :P

# Answer
# APL (Dyalog), ~~104~~ ~~89~~ ~~80~~ ~~82~~ ~~81~~ ~~79~~ 78 bytes

```
⍙←{⍵⍺⍺1⌽⍵}
⎕←(|x){⍵≡2⌽⍵:≡⍙¨0⍺⍵⋄2 4=+/1=2|+⍙↑⍵(=⍙⍺)}2|1+-⍙(12○x←-⍙⎕+.×1 0J1)÷○1

```

Try it online!

---

# Input/Output

Takes a 4×2 matrix of coordinates as input

Outputs

* `1 1 1` for Square
* `1 1 0` for Rhombus
* `1 0 1` for Rectangle
* `1 0 0` for Parallelogram
* `1 0` for Kite
* `0 1` for Trapezium
* `0 0` for Quadrilateral

---

# Algorithm

First, find all 4 side lengths and angles of the quadrilateral

If both pairs of opposite angles are equal (`OA`), then the shape is some kind of parallelogram. Determine if all side lengths are equal (`AS`, Adjacent Sides) and if all angles are equal (`AA`).

```
+--------+----------------+----------------+
|        |       AA       |      ~AA       |
+--------+----------------+----------------+
|   AS   |     Square     |    Rhombus     |
|--------+----------------+----------------+
|  ~AS   |    Rectangle   |  Parallelogram |
+--------+----------------+----------------+

```

If not `OA`, then:

* Determine if there are exactly 2 pairs of equal adjacent sides and if they are separated (`aabb` instead of `aaab`). If so, the shape is a kite.
* Determine if there are exactly 1 pair of parallel opposite sides. If so, the shape is a trapezium.
* Otherwise, the shape is a quadrilateral.

---

# Code

`⍙←{⍵⍺⍺1⌽⍵}` defines a new operator. In APL, an operator means a higher-order function. This operator takes 1 functional argument (`⍺⍺`) and returns a monadic function that:

1. Rotates (`1⌽`) the argument ()
2. Apply `⍺⍺` between it and

This is especially useful for scalar functions since most of them implicitly map across array arguments, allowing  to apply those between each adjacent pair of elements with wrap around. For example `+⍙1 2 3 4` is `1 2 3 4 + 2 3 4 1` which evaluates to `3 5 7 5`.

---

`x←-⍙⎕+.×1 0J1` converts the input coordinate matrix into an array of complex numbers representing the vectors of the 4 sides of the shape.

* , when referenced, takes and returns input
* `1 0J1` represents the vector \[1,i\] ("vector" in the mathematical sense, and "i" as the square root of -1). In APL, a complex number `a+bi` is written `aJb`
* `+.×` matrix multiplication. Mathematically, the result would be a 4×1 matrix. However, `+.×` is called "inner product" in APL which generalizes matrix multiplication and vector inner product and allows you to do even stuff like "multiply" a 3-dimensional array with a 2-dimensional one. In this case, we are multiplying a 4×2 matrix and a 2-element vector, resulting in a 4-element vector (of the complex number representations of the 4 given vertices).
* `-⍙` is pairwise subtraction with wrap around as noted above. This gives the vectors of the 4 sides of the shape (as complex numbers). These vectors point in the "reverse" direction but that doesn't matter.
* `x←` stores that into the variable `x`

---

`2|1+-⍙(12○x)÷○1` finds (a representation of) the exterior angles at the 4 vertices of the shape.

* `12○x` finds the principal argument, in radians, of each of the 4 side vectors.
* `÷○1` divides by π so that the angles are easier to work with. Thus, all angles are expressed as a multiple of a straight angle.
* `-⍙` Pairwise subtraction with wrap around as noted above. This gives the 4 exterior angles.
* `2|1+` The principal argument is capped (-1,1\] and pairwise subtraction makes the range (-2,2\]. This is bad since the same angle has 2 different representations. By doing "add 1 mod 2", the angle is re-capped at (0,2\]. Although all angles are 1 more than what it should be, it's fine if we keep that in mind.

---

`|x` finds the magnitude of each of the 4 side vectors

---

`{⍵≡2⌽⍵:≡⍙¨0⍺⍵⋄2 4=+/1=2|+⍙↑⍵(=⍙⍺)}` defines and applies a function with the array of 4 exterior angles as right argument  and the array of 4 side lengths as right argument .

* The function has a guarded expression. In this case, `⍵≡2⌽⍵` is the guard.
* If the guard evaluates to `1` then the next expression `≡⍙¨0⍺⍵` is executed and its value returned.
* If the guard evaluates to `0`, that expression is skipped and the one after that `2 4=...=⍙⍺)` gets executed instead.

---

`⍵≡2⌽⍵` checks if both pairs of opposite angles are equal.

* `2⌽⍵` rotates the angles array by 2 places.
* `⍵≡` checks if that is the same as  itself

---

`≡⍙¨0⍺⍵` returns a unique value for each parallelogram-type shape.

* `0⍺⍵` is the 3-element array of the scalar `0`, the side lengths array , and the angles array .
* `≡⍙¨` executes `≡⍙` for each of those elements.
* `≡⍙` checks if all values of an array are equal by checking if rotating it by 1 gives the same array. Scalars do not rotate so `≡⍙0` returns `1`. As noted above, `≡⍙⍺` checks for a rhombus and `≡⍙⍵` checks for a rectangle.

---

`2 4=+/1=2|+⍙↑⍵(=⍙⍺)` returns a unique value for each non-parallelogram-type shape. This is achieved by intertwining the checks for kite and trapezium.

---

`2=+/1=2|+⍙⍵` checks for a trapezium.

* `+⍙⍵` gives the adjacent angle sums. The interior angles of parallel lines sum to a straight angle, thus so does the exterior angles of parallel sides of a quadrilateral. So, each pair of parallel sides should lead to two `1` or `-1` in the adjacent angle sums.
* `1=2|` However, the angles in  are 1 more than what they should be, so the angles actually sum to `1` or `3`. This can be checked by "mod 2 equals 1".
* `+/` sums the array. This gives a count of adjacent angle sums which is `1` or `3`.
* `2=` check if that equals 2. (I.e. if there is exactly one pair of parallel sides)

---

`4=+/1=2|+⍙(=⍙⍺)` checks for a kite.

* `(=⍙⍺)` gives an array indicating which adjacent sides are equal. Unlike , `=` work element-wise. Thus, this is a 4-element array with `1`s where the length of that side is equal to that of the "next" side.
* `+⍙` Pairwise sum with wrap around.
* `1=2|` Since `(=⍙⍺)` gives a boolean array (one with only `0`s and `1`s), the only possible values of pairwise sum are `0`, `1` and `2`. So `1=2|` is same as just `1=`.
* `+/` sums the array. This gives a count of pairwise sums which is `1`.
* `4=` check if that equals 4. The only way that happens is if `(=⍙⍺)` is `1 0 1 0` or `0 1 0 1`. As noted above, this means the shape is a kite.

---

`2 4=+/1=2|+⍙↑⍵(=⍙⍺)` intertwines the above checks.

* `⍵(=⍙⍺)` is the 2-element nested array of the array  and the array `(=⍙⍺)`
* promotes the nested array to a proper matrix. Since `⍵(=⍙⍺)` is a 2-element array of 4-element arrays, the result is a 2×4 matrix.
* `+⍙` Since  (and, by extension, ) rotates the last (horizontal) axis, `+⍙` to a matrix is same as applying `+⍙` to each row individually.
* `1=2|` both residue/mod (`|`) and equals (`=`) works on a per-element basis, even to matrices.
* `+/` By default, reduce (`/`) works along the last (horizontal) axis. So `+/` sums along rows and turn a 2×4 matrix into a 2-element simple array.
* `2 4=` Since `=` works per-element, this checks the kite and trapezium conditions simultaneously.
> 8 votes

# Answer
## Mathematica, 195 bytes

```
Which[s=Differences@{##,#};l=Norm/@s;r=#.#2==#2.#3==0&@@s;Equal@@l,If[r,1,2],#==#3&&#2==#4&@@l,If[r,3,4],MatchQ[l,{a_,b_,b_,a_}|{a_,a_,b_,b_}],5,#+#3=={0,0}||#2+#4=={0,0}&@@Normalize/@s,6,1>0,7]&

```

With whitespace:

```
Which[
    s = Differences @ {##,#};
    l = Norm /@ s;
    r = #.#2 == #2.#3 == 0& @@ s;

    Equal @@ l, If[r, 1, 2],
    # == #3 && #2 == #4& @@ l, If[r, 3, 4],
    MatchQ[l, {a_,b_,b_,a_}|{a_,a_,b_,b_}], 5,
    #+#3 == {0,0} || #2+#4 == {0,0}& @@ Normalize /@ s, 6,
    1 > 0, 7
]&

```

Outputs `1` for squares, `2` for rhombi, `3` for rectangles, `4` for parallelograms, `5` for kites, `6` for trapezoids, and `7` for anything else. I'd post a TIO link, but this apparently doesn't work in Mathics.

If the four points are `P`, `Q`, `R`, and `S`, then `{##,#}` is `{P,Q,R,S,P}`, so `s` is the list of side vectors `{Q-P,R-Q,S-R,P-S}`, `l` is the lengths of those vectors, and `r` is the condition that the angle between `Q-P` and `R-Q` as well as the angle between `R-Q` and `S-R` are both `90` degrees.

Thus, if all the sides lengths are equal, then the quadrilateral is a rhombus. If `r` holds, it is in fact a square, otherwise it's just a plain rhombus.

Ruling out rhombi, if both pairs of opposite side lengths are equal, then the quadrilateral is still parallelogram. If `r` holds, it is in fact a rectangle, otherwise, it's just a plain parallelogram.

Ruling out parallelograms, the list of side lengths `l` is of the form `{a,b,b,a}` or `{a,a,b,b}` for some `a` and `b`, then the quadrilateral is a kite. Note that it can't additionally be a trapezoid or it would in fact be a rhombus.

Ruling out parallelograms and kites, if the quadrilateral has a pair of parallel sides, then it is a trapezoid. We check this by `Normalize`ing the side vectors and checking whether a pair of opposite vectors adds to `{0,0}`.

Ruling out all of the above, if `1 > 0` (it better be), then the quadrilateral is just a plain old quadrilateral.
> 3 votes

# Answer
# Python 2, ~~463~~ ~~410~~ ~~408~~ 397 bytes

Saved 53 bytes by using a tuple in the sixth line instead of indexing into a list.

Saved 11 bytes by shifting to output integers 1 through 7 instead of the first letter of each shape. The integers correspond as follows:

1. Square
2. Rectangle
3. Rhombus
4. Parallelogram
5. Trapezoid
6. Kite
7. Quadrilateral

```
from numpy import *;D=dot
from numpy.linalg import *;N=norm
def P(a,b):x=D(a,b);y=N(a)*N(b);return x==y or x==-y
def Q(a,b):return int(N(a)==N(b))
L=input()
a,b,c,d=tuple([(L[i][0]-L[(i+1)%4][0],L[i][1]-L[(i+1)%4][1]) for i in range(4)])
g=7
e=Q(a,c)+Q(b,d)
if e==2:
 g=(1if D(a,b)==0 else 3) if Q(a,b) else 2 if D(a,b)==0 else 4
elif P(a,c) or P(b,d):
 g = 5
elif Q(a,b) or Q(b,c):
 g = 6
print g

```

Try it online!

## Ungolfed to show the logic

Shown as a function, to show output for the different test input. note I changed the "Rectangle" test example from the one originally provided in the question, which was not a rectangle.

The logic rests on dot products and the norm (length) of the vectors formed by the sides of the quadrilateral to assess whether sides are equal in length, parallel on opposite sides, or perpendicular to adjacent sides.

```
def S(va, vb):
    return (va[0]-vb[0], va[1]-vb[1])
def dot(sa,sb):      # Eventually replaced with numpy.dot
    return(sa[0]*sb[0]+sa[1]*sb[1])
def norm(s):         # Eventually replaced by numpy.linalg.norm
    return (s[0]**2+s[1]**2)**.5
def isperp(a,b):     # Test if lines/vectors are perpendicular
    return dot(a,b)==0
def ispar(a,b):      # Test if lines/vectors are parallel
    x = dot(a,b)
    y = norm(a)*norm(b)
    return x == y or x == -y
def iseq(a,b):       # Test if lines/vectors are equal in length
    return norm(a)==norm(b)

def f(L):
    #Define the four sides
    s = []
    for i in range(4):
        s.append(S(L[i],L[(i+1)%4]))  # I refer often so shorter names may eventually

    guess = 'Q'
    eqsides = 0           # These 6 lines eventually golfed using integer arithmetic by returning an int from iseq()
    if iseq(s[0], s[2]):
        eqsides += 1
    if iseq(s[1],s[3]):
        eqsides += 1
    if eqsides == 2:
    # Opposite sides are equal, so square, rhombus, rectangle or parallelogram
        if iseq(s[0],s[1]):       #Equal adjacent sides, so square or rhombus
            guess='S' if isperp(s[0], s[1]) else 'H'
        else:                     # rectangle or Parallelogram
            guess='R' if isperp(s[0], s[1]) else 'P'
    elif ispar(s[0],s[2]) or ispar(s[1],s[3]):
        guess = 'T'
    elif iseq(s[0],s[1]) or iseq(s[1],s[2]):
        guess = 'K'
    return guess

#test suite:
print f([(0, 0), (1, 0), (1, 1), (0, 1)]) # -> square
print f([(0, 0), (1, 1), (-1, 3), (-2, 2)]) # -> rectangle
print f([(0, 0), (5, 0), (8, 4), (3, 4)]) #  -> rhombus
print f([(0, 0), (5, 0), (6, 1), (1, 1)]) #  -> parallelogram
print f([(0, 0), (4, 0), (3, 1), (1, 1)]) # -> trapezoid/trapezium
print f([(0, 0), (1, 1), (0, 3), (-1, 1)]) #-> kite
print f([(0, 0), (2, 0), (4, 4), (0, 1)]) #-> quadrilateral

```

Try it online!
> 1 votes

# Answer
## Batch, 287 bytes

```
@set/aa=%3-%1,b=%4-%2,c=%5-%1,d=%6-%2,e=%7-%1,f=%8-%2,g=a*a+b*b,h=(h=c-a)*h+(h=d-b)*h,i=(i=c-e)*i+(i=d-f)*i,j=e*e+f*f,p=!(i-g)+!(j-h),q=!(h-g),r=!(a*e+b*f),k=q+!(j-i)^|!(j-g)+!(h-i),t=!(a*(f-d)-b*(e-c))+!((c-a)*f-(d-b)*e)
@if %p%==2 (echo 1%r%%q%)else if %k%==2 (echo 1)else (echo 1%t%)

```

Outputs in binary: `1` = Kite, `10` = Quadrilateral, `11` = Trapezium, `100` = Parallelogram, `101` = Rhombus, `110` = Rectangle, `111` = Square. Explanation: `g, h, i, j` are the squares of the lengths of the sides. `p` is the number of pairs of opposite sides with the same length, `q` distinguishes between parallelograms/rectangles and rhobmi/squares by checking whether the opposite pairs are in fact equal, `r` distinguishes between parallelograms/rhombi and rectangles/squares via a perpendicularity check, `k` checks for a kite by looking for pairs of equal adjacent sides and `t` checks for a trapezium via a couple of parallel side checks.
> 0 votes

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