title: Visualize Inclusion-Exclusion

text:
# Question
Title: Visualize Inclusion-Exclusion
Inclusion-Exclusion lets you calculate the sizes of some unions and intersections between sets knowing some of the other values. I won't explain it exactly, but your challenge is to visualize inclusion-exclusion on a Venn Diagram.

Because I'm nice, you'll be using rectangles, not circles.

You will be given a list of rectangles denoted by top-left and bottom-right corner coordinates in any reasonable format (list of 4-tuples, list of pairs of pairs, list of pairs, etc). You can assume that all coordinates are non-negative and within your language's (reasonable) number range (please specify what it is if it's less than 128). You can choose to be left-inclusive or left-exclusive and right-inclusive or right-exclusive. Regardless of your chosen format, you can assume all rectangles are at least 1x1.

Then, you are to draw out each rectangle on the screen (ASCII canvas) using a single non-whitespace character `k`, which is yours to choose.

However, whenever two rectangles overlap, the overlapping area shall be drawn with another non-whitespace character `l != k`, also yours to choose.

Whenever *three* rectangles overlap, the overlapping area should be drawn with `k`, and for an odd number of rectangles covering, `k`, and an even number, `l`.

The background should be single whitespaces (`0x20`).

# Test Cases (`k = "#", l = "."`)

```
0 0 9 9
1 1 10 10
2 2 11 11

#########
#........#
#.#######.#
#.#######.#
#.#######.#
#.#######.#
#.#######.#
#.#######.#
#.#######.#
 #........#
  #########

1 1 3 3
2 2 4 4

 ##
 #.#
  ##

1 1 9 9
2 2 8 8
3 3 7 7

 ########
 #......#
 #.####.#
 #.####.#
 #.####.#
 #.####.#
 #......#
 ########

```

# Notes

* Leading spaces and newlines (which occur if the minimum coordinate isn't `0, 0`) must be present
* Any trailing spaces and newlines are allowed to a reasonable extent (i.e. don't trail like 100000000 newlines, that's just annoying)
* x- and y- axes can face either way but you must be consistent and specify which (default is x- right and y- down)
* coordinates can be 0-, 1-, or 2- indexed.

Reference Proton Implementation

This is , so the objective is to have the shortest code. Happy golfing!

# Answer
# 6502 machine code routine (C64), 57 bytes

```
20 44 E5 A0 03 84 FB 20 9B B7 A4 FB 96 22 C6 FB 10 F5 85 FC A6 24 20 F0 E9 A4
25 B1 D1 09 01 49 02 91 D1 C8 C4 23 D0 F3 E8 E4 22 D0 E9 A9 2C C5 FC F0 D0 A5
C6 F0 FC C6 C6 4C 44 E5

```

This is position-independent code, put it somewhere in RAM and use the correct start address calling it with `sys`.

**Online demo** (start address `$C000` / `49152`).

**Usage:** `sys<startaddress>,<x1>,<y1>,<x2>,<y2>[,<x1>,<y1>,<x2>,<y2>[,...]]`

**Example:** `sys49152,0,0,9,9,1,1,10,10,2,2,11,11`

On reasonable number ranges: The natural range on this 8-bit machine is \[0-255\], and the program will accept this as parameters. But the C64 screen only has 40 columns and 25 rows, therefore limiting the **reasonable** range to \[0-40\] for x values and \[0-25\] for y values. Using other values will have unpredictable behavior.

---

**commented disassembly listing:**

```
20 44 E5    JSR $E544           ; clear screen
 .mainloop:
A0 03       LDY #$03            ; index for reading coordinates
84 FB       STY $FB
 .inputrect:
20 9B B7    JSR $B79B           ; read 8bit value from parameter
A4 FB       LDY $FB
96 22       STX $22,Y           ; and store to $22-$25
C6 FB       DEC $FB
10 F5       BPL .inputrect      ; parameter reading loop
85 FC       STA $FC             ; store last character
A6 24       LDX $24             ; load y1
 .rowloop:
20 F0 E9    JSR $E9F0           ; get pointer to screen row in $d1/$d2
A4 25       LDY $25             ; load x1
 .colloop:
B1 D1       LDA ($D1),Y         ; load character at screen position
09 01       ORA #$01            ; set bit 0 ( -> '#')
49 02       EOR #$02            ; toggle bit 1 (toggle between '#' and '!' )
91 D1       STA ($D1),Y         ; store character at screen position
C8          INY                 ; next x
C4 23       CPY $23             ; equals x2?
D0 F3       BNE .colloop        ; no -> repeat
E8          INX                 ; next y
E4 22       CPX $22             ; equals y2?
D0 E9       BNE .rowloop        ; no -> repeat
A9 2C       LDA #$2C            ; load ','
C5 FC       CMP $FC             ; compare with last character from parsing
F0 D0       BEQ .mainloop       ; if ',', repeat reading coordinates
 .waitkey:
A5 C6       LDA $C6             ; load input buffer size
F0 FC       BEQ .waitkey        ; and repeat until non-empty
C6 C6       DEC $C6             ; set back to empty
4C 44 E5    JMP $E544           ; clear screen

```
> 4 votes

# Answer
# Python 2, ~~218~~ ~~192~~ ~~189~~ ~~185~~ ~~158~~ ~~154~~ 147 bytes

```
def f(l):_,_,a,b=map(range,map(max,zip(*l)));print'\n'.join(''.join((' '+'#.'*len(l))[sum((x<=i<X)*(y<=j<Y)for x,y,X,Y in l)]for i in a)for j in b)

```

Try it online!
> 3 votes

# Answer
# Charcoal, 40 bytes

```
ＷＳ«≔Ｉ⪪ι ιＦ…§ι⁰§ι²«Ｊκ§ι¹ＵＭＫＤ⁻§ι³§ι¹↓§10Σλ

```

Try it online! Link is to verbose version of code. ~~Will be 6 bytes shorter once @ASCII-only fixes a bug in Charcoal~~. Takes input as a newline-terminated list of space-separated list of co-ordinates. Explanation:

```
ＷＳ«

```

Loop over each line of input until a blank line is reached.

```
≔Ｉ⪪ι ι

```

Split the line into a list of co-ordinates.

```
Ｆ…§ι⁰§ι²«

```

Loop over all the X co-ordinates.

```
Ｊκ§ι¹

```

Jump to the top of the column.

```
ＵＭ

```

Map over each of...

```
ＫＤ⁻§ι³§ι¹↓

```

... all the cells in the column...

```
§10Σλ

```

... the new value is `0` if they contain `1`, otherwise `1`. Edit: Soon after writing this, Charcoal changed the behaviour of `¬` so that `Ｉ¬Σλ` works here to save 1 byte.
> 3 votes

# Answer
# , 36 34 bytes

```
(' ','#.'$~#){~[:+/(-@]{.-~$1:)/"2

```

Try it online!

*-2 bytes thanks to Bubbler*

We take input as a list of 2x2 matrices.

* For each of them `"2`, draw a box of ones `1:` of the same shape `$` as the element-wise difference between the top-left and bottom-right coords `-~`.
* Then rotate that down and to the right with 0 fill `-@]{.` until the upper leftmost `1` is in the coords specified by the left arg `-@[`.
* `[:+/` Sum the resulting matrices element-wise. J guarantees they will be the same size by adding 0 fill to the right. This will produce a single matrix with integers 0, 1, 2, 3, etc. We'll use those to index into our ascii chars `{~`.
* `'#.'$~#` Repeat the pattern `#.` cyclically `$~` to the input length `#`, and then prepend a space `' ',`.
> 3 votes

# Answer
# Python 2, 181 bytes

```
l=input()
_,_,x,y=map(max,zip(*l))
m=eval(`[[32]*x]*y`)
for v,w,x,y in l:
 for i in range(v,x):
	for j in range(w,y):
	 m[i][j]=max(m[i][j]^1,34)
for n in m:print''.join(map(chr,n))

```

Try it online!
> 2 votes

# Answer
# , ~~196~~ 189 bytes

```
m=matrix
x=m(scan(file("stdin")),4)
y=m(0,max(x[3,]),max(x[4,]))
n=ncol(x)
while(n){z=x[,n]
i=z[1]:z[3]
j=z[2]:z[4]
y[i,j]=y[i,j]+1
n=n-1}
i=!y
y=y%%2+1
y[i]=' '
cat(rbind(y,'\n'),sep='')

```

Try it online!

The code reads input as stdin, arranged as a x1 y1 x2 y2 tuple, where x is the column and y is the row. I am using 1 and 2 for the overlap levels, where 1 represents an even level.

Saved 7 bytes thanks to user2390246.
> 2 votes

# Answer
# C (gcc), 205 bytes

```
x[999][999];a;b;c;d;j;k;l;m;n;main(i){for(;scanf("%d %d %d %d",&a,&b,&c,&d)>3;m=d>m?d:m,n=c>n?c:n)for(i=b;i<d;++i)for(j=a;j<c;++j)x[i][j]=x[i][j]^2|1;for(;k<n||++l<(k=0,puts(""),m);putchar(x[l][k++]+32));}

```

Try it online!
> 2 votes

# Answer
# Raku, 54 bytes

```
{my@a;{@a[$^a..$^b;$^c..$^d]X+^=1}for $_;@a >>~|>>' '}

```

Try it online!

Takes input as a flat list of coordinates as inclusive coordinates, i.e. `x1,y1,x2,y2,x1,y1,x2,y2...` and outputs as a list of list of characters with `k` being `1` and `l` being `0`.

### Explanation:

```
{                                                    }  # Anonymous codeblock
 my@a;    # Declare an array
      {                          }for $_;    # Loop over the input
       @a[                 ]   # Indexing into @a
          $^a..$^b             # The range of rows
                  ;$^c..$^d    # And the range of columns for each
                            X        # And for each cell
                             +^=1    # Set it to itself bitwise XOR'd with 1
                         # Cells not yet accessed are numerically zero
                                         @a >>~|>>' '   # Stringwise OR each cell with a space
                         # Cells not yet accessed are stringily empty

```
> 2 votes

# Answer
# Jelly, 43 bytes

```
+µ>2Ḥạ
ạ1ẋ$0ẋ⁸¤;µ/€«þ/µ€z0z€0Z€Zz€0Z€ç"/o⁶Y

```

Try it online!

# Explanation

```
+µ>2Ḥạ                                Helper Link; combines final rectangles (0 is blank, 1 is covered, 2 is uncovered)
+                                     add the two values
 µ                                    (with the sum...)
  >2                                  check if it's greater than two
    Ḥ                                 double the result (2 if it's 3 or 4, 0 if it's 0, 1, or 2)
     ạ                                absolute difference (0 should take whatever the other thing's value is, 1+1 and 2+2 should give 2, 1+2 and 2+1 should give 1)
ạ1ẋ$0ẋ⁸¤;µ/€«þ/µ€z0z€0Z€Zz€0Z€ç"/o⁶Y  Main Link
               µ€                     For each rectangle stored as [[x1, x2], [y1, y2]]
         µ/€                          For each of [a, b] = [x1, x2] and [y1, y2], reduce it by (in other words, use a dyad on a size-2 list)
 1ẋ$                                  repeat [1]            times
ạ                                                abs(a - b)
        ;                             and append to
    0ẋ ¤                              [0] repeated   times
      ⁸                                            a
            «þ/                       and reduce by minimum outer product table (take the outer product table, by minimum, of the x results and the y results)
                                      [NOTE] At this point, we have a list of matrices with 0s as blanks and 1 as covered
                 z0z€0Z€Zz€0Z€        Make all of the matrices the same size:
                 z0                   zip, fill with 0 (all matrices are the same length, but not width, and now are lists of row-wise lists of rows)
                   z€0                zip each, fill with 0 (all rows are the same length within their row-wise lists, and are now lists of row-wise lists of columns)
                      Z€              zip each (flip rows back to lists of row-lists of rows)
                        Z             zip (flip back to matrices); however, if a matrix is smaller on both axes, its rows will not be the same length
                         z€0          zip each, fill with 0 (all rows in each matrix are the same length and the value is now a list of transposed matrices)
                            Z€        zip each (the value is now a list of matrices, all the same length, filled with 0 (empty space))
                              ç"/     reduce by (vectorized) the relation in the Helper Link (to combine all of the final values)
                                 o⁶   logical OR with " "; replace 0s with spaces
                                   Y  join with newlines (formatting)

```
> 1 votes

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


title: Swap the two given indices

text:
# Question
Title: Swap the two given indices
Given an array of positive integers and two distinct valid indices, return the array with the two elements corresponding to the two indices swapped.

You may choose to use 0-indexing or 1-indexing, but the testcases below will be 0-indexed.

```
array        m n output
[1,2,3,4]    0 1 [2,1,3,4]
[5,8,9]      0 2 [9,8,5]
[11,13,15,3] 1 2 [11,15,13,3]
[11,13,15,3] 2 1 [11,15,13,3]
[11,15,15,3] 2 1 [11,15,15,3]

```

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

# Answer
> 17 votes
# C~~/C++~~, ~~53~~ ~~50~~ 39 bytes

```
f(a,m,n)int*a;{a[m]^=a[n]^=a[m]^=a[n];}

```

Try it online

Saved 11 bytes thanks to @Dennis

# Answer
> 10 votes
# Operation Flashpoint scripting language, ~~98~~ 95 bytes

```
f={t=_this;a=t select 0;b=+a;m=t select 1;n=t select 2;a set[m,b select n];a set[n,b select m]}

```

Modifies the array directly.

**Explanation:**

```
t=_this;                   // Give a shorter name for the array of arguments.

a=t select 0;              // Let 'a' be a pointer to the array that we modify.
                           // (The language doesn't have a concept of pointers really,
                           // yet its array variables are pointers to the actual array.)

b=+a;                      // Make a copy of the original array and save a pointer to it
                           // in the variable 'b'. This saves a few bytes later.

m=t select 1;              // Read the index arguments from the input array and save them
n=t select 2;              // to their respective variables.

a set[m,b select n];       // Do the swapping by reading the values from the copy and
a set[n,b select m]        // writing them to the original array. The last semicolon can
                           // be omitted because there are no more statements following
                           // the last statement.

```

**Call with:**

```
array = [1,2,3,4];
str = format["%1", array];
[array, 0, 1] call f;
hint format["%1\n%2", str, array];

```

**Output:**

# Answer
> 7 votes
# JavaScript ES6, ~~36~~ 32 bytes

Look, Ma, no temporary variable!

```
(a,m,n)=>[a[m],a[n]]=[a[n],a[m]]

```

---

## Try it

Enter a comma separated list of elements for `a` and 2 integers for `m` & `n`.

```
f=
(a,m,n)=>[a[m],a[n]]=[a[n],a[m]]
oninput=_=>o.innerText=(f(b=i.value.split`,`,+j.value,+k.value),b);o.innerText=(f(b=(i.value="5,8,9").split`,`,j.value=0,k.value=2),b)
```

```
*{font-family:sans-serif}input{margin:0 5px 0 0;width:100px;}#j,#k{width:50px;}
```

```
<label for=i>a: </label><input id=i><label for=j>m: </label><input id=j type=number><label for=k>n: </label><input id=k type=number><pre id=o>
```

# Answer
> 6 votes
# Jelly, 7 bytes

```
Ṛ,ḷyJ}ị

```

Try it online!

### How it works

```
Ṛ,ḷyJ}ị  Main link. Left argument: [i, j]. Right argument: A (array)

Ṛ        Reverse; yield [j, i].
  ḷ      Left; yield [i, j].
 ,       Pair; yield [[j, i], [i, j]].
    J}   Indices right; yield all indices of A.
   y     Transliterate; replace j with i and i with j.
      ị  Index into A.

```

# Answer
> 5 votes
# Python 3, ~~41~~ 32 bytes

-9 bytes thanks to @notjagan

```
def f(a,m,n):a[m],a[n]=a[n],a[m]

```

Try it online!

Modifies its argument, which is a valid output format.

# Answer
> 5 votes
# MATL, ~~7~~ 6 bytes

```
yyP)w(

```

Indices are 1-based.

**Try it online!**

### Explanation

Consider inputs `[11 13 15 3]`, `[2 3]`.

```
yy   % Take two inputs implicitly. Duplicate them
     % STACK: [11 13 15 3], [2 3], [11 13 15 3], [2 3]
P    % Flip
     % STACK: [11 13 15 3], [2 3], [11 13 15 3], [3 2]
)    % Reference indexing (pick indexed entries)
     % STACK: [11 13 15 3], [2 3], [15 13]
w    % Swap
     % STACK: [11 13 15 3], [15 13], [2 3]
(    % Assignment indexing (write values into indexed entries). Implicitly display
     % STACK: [11 15 13 3]

```

# Answer
> 5 votes
# CJam, 4 bytes

```
{e\}

```

Try it online!

# Answer
> 4 votes
# C# (.NET Core), 48 43 31 bytes

```
(a,m,n)=>a[m]+=a[n]-(a[n]=a[m])

```

Try it online!

Swaps the numbers in the original array, no temporary variables used. Nonetheless I can't take credit for this answer as it has been Neil's idea.

# Answer
> 4 votes
# Japt, 17 16 bytes

```
hV(A=UgV UgW¹hWA

```

Try it online!

Saved a byte thanks to ETHproductions

# Answer
> 4 votes
# Common Lisp, 42 bytes

*-2 bytes thanks to @coredump.*

```
(lambda(a i j)(rotatef(elt a i)(elt a j)))

```

Try it online!

Quite straight forward, since there is a Common Lisp macro to swap: `rotatef`.

# Answer
> 3 votes
# Javascript ES6, ~~36~~ 34 bytes

```
(a,m,n)=>(x=a[m],a[m]=a[n],a[n]=x)

```
* *-2 Bytes because the function is altering the array. No need to return the array. Thanks to @Neil*

## Demo

```
f=

(a,m,n)=>(x=a[m],a[m]=a[n],a[n]=x)

let a1=[1,2,3,4], a2=[5,8,9], a3=[11,13,15,3]

f(a1,0,1);
f(a2,0,2);
f(a3,1,2);

console.log(JSON.stringify(a1)); //[2,1,3,4]
console.log(JSON.stringify(a2)); //[9,8,5]
console.log(JSON.stringify(a3)); //[11,15,13,3]
```

# Answer
> 3 votes
# Shenzhen I/O, 735 Bytes

23¥, 810 Power, 48 Lines of Code

```
[traces]
......................
......................
......................
......................
......................
......................
.14.14.14.............
.94.14.14.............
.A........1C..........
.3554..95556..........
.9554.16..............
.A....................
.2....................
......................

[chip]
[type] UC6
[x] 4
[y] 2
[code]
  slx x0
  mov x1 acc
  mov x1 dat
  mov acc x3
  mov dat x3
  mov acc x3
  mov dat x3

[chip]
[type] UC6
[x] 8
[y] 5
[code]
  slx x2
  mov x2 x1
  mov x0 dat
  mov x2 x1
  mov x0 acc
  mov x2 x1
  mov dat

[chip]
[type] UC4X
[x] 2
[y] 6
[code]
  slx x0
  mov 0 x3
j:  mov x0 acc
  mov acc x2
  teq acc 0
- jmp j
  mov -999 x1

[chip]
[type] RAM
[x] 5
[y] 6

```

DISCLAIMER: Arrays are 0-terminated in this. Arrays are a pain in the ass to work with in Shenzhen I/O otherwise.

I actually made a steam level for this game. You can play it here.

EDIT: Aaand I just realized I said that the array in was ordered. Heck.

# Answer
> 3 votes
# Brachylog, 19 bytes

```
iʰ{pᵗz=ᵗ!|}htI&h∋↙I

```

Try it online!

The process of writing this generator was fairly clumsy, so there's probably some further golfing to do. I may not have thought to use `i` if I hadn't initially thought I had some use for the value half of the pair it outputs! Takes input as `[array, [m, n]]`.

# Answer
> 2 votes
# Java 8, 48 bytes

```
(a,b,c)->{int t=a[b];a[b]=a[c];a[c]=t;return a;}

```

Input:

```
int[] a
int b
int c

```

# Answer
> 2 votes
# 05AB1E, 10 bytes

```
D²è³ǝ¹³è²ǝ

```

Try it online!

# Answer
> 2 votes
# Octave, 28 bytes

```
@(a,n){a(n)=a(flip(n)),a}{2}

```

Try it online!

Quite satisfied with this one actually :)

Takes input on the form: `f([1,2,3,4],[1,2])`, 1-indexed.

**Explanation:**

```
@(a,n)                         % Anonymous function that takes two 1-dimensional
                               % arrays as input
      {               , }      % Create a cell with two elements
       a(n)=a(flip(n))         % One element are the two number at indices given by
                               % the second input array. This will be a 1x2 array
      {a(n)=a(flip(n)),a}      % Place those two in a cell together with the entire array a
                               % a is now updated, thanks to Octave's inline assignment
      {a(n)=a(flip(n)),a}{2}   % Return the second element

```

# Answer
> 2 votes
## Jellyfish, 7 bytes

```
p
ZRi
i

```

Takes a list and a pair of indices. Try it online!

## Explanation

Jellyfish happens to have a "modify items at indices" function, `Z`, which does exactly what we need. The two `i`s grab the inputs from STDIN. `Z` takes as arguments the second input, the reversal function `R`, and the list. Then `Z` performs the modification, and `p` prints the result.

# Answer
> 2 votes
# R, 38 bytes

```
function(x,a,b){x[c(a,b)]=x[c(b,a)];x}

```

Feels rather long, but I can't get it much shorter. Sadly it requires the explicit returning through `x`, requiring `{}` around the function body. `pryr::f()` doesn't recognise the need for `x` as function argument so doesn't work :/.

# Answer
> 2 votes
# Java 8 + InverseY, 27 bytes

```
java.util.Collections::swap

```

Just calls the swap function... this is a method reference of the type `Consumer3<List, Integer, Integer>`.

Try it online! (header and footer for boilerplate & copy of `Consumer3` interface)

# Answer
> 1 votes
# Mathematica, 32 bytes

```
(a=#;a[[{##2}]]=a[[{#3,#2}]];a)&

```

# Answer
> 1 votes
# Swift, ~~111~~ 65 bytes (0-indexed)

Swift is already notorious for being one of the worst code-golf languages, but here is a function ~~that makes use of ternary expressions~~:

```
func t(l:[Int],m:Int,n:Int){var r=l;r[m]=l[n];r[n]=l[m];print(r)}

```

Check it out! \- **Usage:** `t(l:[1,2,3],m:0,n:1)`.

# Answer
> 1 votes
# (kona), 13 bytes

```
{x[y]:x@|y;x}

```

Pretty basic, but it works. Ex:

```
k){x[y]:x@|y;x}[1 2 3 4; 0 1]
2 1 3 4

```

# Answer
> 1 votes
# Perl 5, 32 bytes

*-3 bytes thanks to @Dom Hastings!*

30 bytes of code + `-pa` flags.

```
@F[pop@p,@p]=@F[@p=<>];$_="@F"

```

Try it online!

Quite straight forward, using array slices.

# Answer
> 1 votes
# C, 42 bytes

Modify the array in place with a temp value.

```
f(r,m,n){int*a=r;r=a[m];a[m]=a[n];a[n]=r;}

```

# C, ~~60~~ 58 bytes

A little more interesting, not using any temp value...

```
f(a,m,n)int*a;{a[m]+=a[n];a[n]-=a[m];a[n]*=-1;a[m]-=a[n];}

```

# C, 49 bytes

Using XOR

```
f(a,m,n)int*a;{a[m]^=a[n];a[n]^=a[m];a[m]^=a[n];}

```

# Answer
> 1 votes
# Pyth, ~~17~~ 8 bytes

Saved 9 bytes thanks to Leaky Num.

```
@LQ.rUQE

```

Test it online!

This is 0-indexed, and the indices are provided as a tuple: `(n, m)`.

**Explanations**

```
@LQ.rUQE

     UQ     # Generate [0, 1, 2, ..., len(input)]
       E    # Get the indices as the tuple (1, 2)
   .r       # Translate each element of UQ to its cyclic successor in E
            # Now the indices are permuted (e.g. [0, 2, 1, ..., len(input)]
@LQ         # For each index, get it's value. Implicit print

```

# Answer
> 1 votes
# Julia 0.5, 20 bytes

```
x*t=x[t]=x[t[[2,1]]]

```

Try it online!

# Answer
> 1 votes
# Mathematica, 20 bytes

```
#~Permute~Cycles@#2&

```

Pure function taking two arguments in the following 1-indexed (and possibly abusive) format: the second test case `[5,8,9]; 0 2; [9,8,5]` would be called as

```
#~Permute~Cycles@#2& [ {5,8,9} , {{1,3}} ]

```

(spaces are extraneous and just for visible parsing). `Permute` is the builtin function that applies a permutation to a list, and `Cycles[{{a,b}}]` represents the permutation that exchanges the `a`th and `b`th elements of a list and ignores the rest.

# Answer
> 1 votes
# x86 Machine Code, 10 bytes

```
8B 04 8B 87 04 93 89 04 8B C3

```

This is a function written in 32-bit x86 machine code that swaps the values at the specified indices in a given array. The array is modified in-place, and the function does not return a value.

A custom calling convention is used, requiring the function's parameters to be passed in registers:

* The address of the array (pointer to its first element) is passed in the `EBX` register.
* The zero-based index of element A is passed in the `ECX` register.
(Assumed to be a valid index.)
* The zero-based index of element B is passed in the `EDX` register.
(Assumed to be a valid index.)

This keeps the size down and complies with all formal requirements, but does mean that the function cannot be easily called from other languages like C. You'd need to call it from another assembly-language program. (You could rewrite it to use *any* input registers, though, without affecting the byte count; there's nothing magical about the ones I chose.)

Ungolfed:

```
8B 04 8B     mov  eax, DWORD PTR [ebx+ecx*4]   ; get value of element A
87 04 93     xchg eax, DWORD PTR [ebx+edx*4]   ; swap element A and element B
89 04 8B     mov  DWORD PTR [ebx+ecx*4], eax   ; store new value for element A
C3           ret                               ; return, with array modified in-place

```

# Answer
> 1 votes
## R, 34 bytes

```
pryr::f(`[<-`(a,c(m,n),a[c(n,m)]))

```

# Answer
> 1 votes
# JavaScript (ES2015), 66 57 49 bytes

A different (alas, longer) approach than previous JavaScript answers

```
(s,h,o,w=s.splice.bind(s))=>w(h,1,...w(o,1,s[h]))

```

Source

```
const swap = (arr, a, b, splice) => {
  splice(a, 1, ...splice(arr[b], 1, arr[a]))
}

```

# Answer
> 0 votes
## awk, 31 bytes

```
{c=$a;$a=$b;$b=c;a=$1;b=$2}NR>1

```

Try it online!

Takes input in the format

```
1 2
1 2 3 4

```

and outputs as

```
2 1 3 4

```

(1-indexed).

### Explanation

The entire program is a missing pattern with an action followed by a pattern with a missing action.

Since a missing pattern runs on each line, the code inside the braces runs for both input lines. The `c=$a;$a=$b;$b=c;` part swaps the two values at indices `a` and `b` (through the temporary variable `c`). This only has an effect on the second line, since on the first line `a` and `b` are not yet defined. The `a=$1;b=$2` part defines `a` to be the first field and `b` to be the second field, which sets the appropriate values for the first part to run on the second line.

Since a missing action is equivalent to `{print}`, the pattern prints every line it matches. This pattern in particular is `NR>1`: that is, print whenever the line number is greater than 1, which happens to be line 2. This runs after the swapping of values has taken place, thus completing the task.

# Answer
> 0 votes
# Japt, 15 bytes

```
£gY¶V?W:Y¶W?V:Y

```

Test it

---

## Explanation

```
       :Implicit input of array U and integers V & W
£      :Map over the array (with Y being the index of the current element), replacing each element with...
g      :  The element in the array at index...
Y¶V?W  :    W, if Y equals V
:Y¶W?V :    or V, if Y equals W
:Y     :    or just Y otherwise
       :Implicit output of modified array

```

# Answer
> 0 votes
# q/kdb+, 17 bytes

**Solution:**

```
{@[x;(|)y;:;x y]}

```

**Example:**

```
q){@[x;(|)y;:;x y]}[1 2 3 4;0 1]
2 1 3 4

```

**Explanation:**

A q version of the k answer by Simon. Apply the assign `:` function to x at indices reverse-y with value of x indexed at y. Broken down you can see more clearly:

```
q)x:1 2 3 4
q)y:0 1
q)x y
1 2
q)(|)y
1 0
q)x(|)y
2 1
q)@[x;(|)y;:;x y]
2 1 3 4

```

# Answer
> 0 votes
# Powershell, 64 49 bytes

$f=$args;$t=$f\[0\];($t\[$f\[1\]\],$t\[$f\[2\]\]=$t\[$f\[2\]\],$t\[$f\[1\]\])\>$;$t

```
param($a,$b,$c)($a[$b],$a[$c]=$a[$c],$a[$b])>$;$a

```

At least somewhat better solution.

Also I have no idea why redirecting to $ even works ^^

# Answer
> 0 votes
# , 10 bytes

```
ÀGYÀGVpVp

```

Try it online!

This takes input with each number to a line, and indices as program arguments. 1-indexed.

# Answer
> -1 votes
# C, 42 bytes (one extra argument on function call)

```
f(a,m,n,t)int*a;{t=a[m];a[m]=a[n];a[n]=t;}

```

Try it online

# C, 44 bytes

```
f(a,m,n)int*a;{int t=a[m];a[m]=a[n];a[n]=t;}

```

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


title: Arranging Bubbles

text:
# Question
Title: Arranging Bubbles
Note, challenge copied from question asked at math.stackexchange.

Recently, I attained quite some skill at blowing bubbles. At first I would blow bubbles like this:

But then things started getting strange:

After a while, I was blowing some pretty weird bubbles:

After blowing hundreds, maybe even thousands of such bubbles, my forehead suddenly wrinkled with the question: Given n bubbles, how many different ways can you arrange them? For example if n = 1, there is only 1 arrangement. If n = 2, there are 2 arrangements. If n = 3, there are 4 arrangements. If n = 4, there are 9 arrangements.

Here are the 9 arrangements of 4 bubbles:

After blowing all of these marvelous bubbles, I decided that I should share the delight of counting their arrangements with you. So here is your task:

---

## Goal

Write a program, function, or similar that counts the number of ways you can arrange `n` bubbles.

---

## Input

`n`, the number of bubbles. n \> 0

---

## Output

The number of ways you can arrange these bubbles.

---

## Winning Criteria

It would be really cool if we can blow a bubble around your code. The smaller you make your code, the easier it will be to do so. So the person who makes the code with the least number of bytes will win the contest.

---

### Extra information

OEIS

# Answer
> 15 votes
# Python 2, 92 87 bytes

```
a=lambda n:n<2or sum((k%d<1)*d*a(d)*a(n-k)for k in range(1,n)for d in range(1,1+k))/~-n

```

In plain english: to compute `a(n)` we calculate `d*a(d)*a(n-k)` for every divisor `d` of every positive integer `k` smaller than or equal to `n`, sum all these, and divide by `n-1`.

To make it run faster, run in Python 3 (replacing `/` with `//` in the above function) and memoize:

```
import functools
a = functools.lru_cache(None)(a)

```

If you do this it computes `a(50) = 425976989835141038353` instantly.

# Answer
> 11 votes
# GNU Prolog, 98 bytes

```
b(x,0,x).
b(T/H,N,H):-N#=A+B+1,b(H,A,_),b(T,B,J),H@>=J.
c(X,Y):-findall(A,b(A,X,_),L),length(L,Y).

```

This answer is a great example of how Prolog can struggle with even the simplest I/O formats. It works in true Prolog style via describing the problem, rather than the algorithm to solve it: it specifies what counts as a legal bubble arrangement, asks Prolog to generate all those bubble arrangements, and then counts them. The generation takes 55 characters (the first two lines of the program). The counting and I/O takes the other 43 (the third line, and the newline that separates the two parts). I bet this isn't a problem that the OP expected to cause languages to struggle with I/O! (Note: Stack Exchange's syntax highlighting makes this harder to read, not easier, so I turned it off).

## Explanation

Let's start with a pseudocode version of a similar program that doesn't actually work:

```
b(Bubbles,Count) if map(b,Bubbles,BubbleCounts)
                and sum(BubbleCounts,InteriorCount)
                and Count is InteriorCount + 1
                and is_sorted(Bubbles).
c(Count,NPossibilities) if listof(Bubbles,b(Bubbles,Count),List)
                       and length(List,NPossibilities).

```

It should be fairly clear how `b` works: we're representing bubbles via sorted lists (which are a simple implementation of multisets that causes equal multisets to compare equal), and a single bubble `[]` has a count of 1, with a larger bubble having a count equal to the total count of the bubbles inside plus 1. For a count of 4, this program would (if it worked) generate the following lists:

```
[[],[],[],[]]
[[],[],[[]]]
[[],[[],[]]]
[[],[[[]]]]
[[[]],[[]]]
[[[],[],[]]]
[[[],[[]]]]
[[[[],[]]]]
[[[[[]]]]]

```

This program is unsuitable as an answer for several reasons, but the most pressing is that Prolog doesn't actually have a `map` predicate (and writing it would take too many bytes). So instead, we write the program more like this:

```
b([], 0).
b([Head|Tail],Count) if b(Head,HeadCount)
                    and b(Tail,TailCount)
                    and Count is HeadCount + TailCount + 1
                    and is_sorted([Head|Tail]).
c(Count,NPossibilities) if listof(Bubbles,b(Bubbles,Count),List)
                       and length(List,NPossibilities).

```

The other major problem here is that it'll go into an infinite loop when run, because of the way Prolog's evaluation order works. However, we can solve the infinite loop by rearranging the program slightly:

```
b([], 0).
b([Head|Tail],Count) if Count #= HeadCount + TailCount + 1
                    and b(Head,HeadCount)
                    and b(Tail,TailCount)
                    and is_sorted([Head|Tail]).
c(Count,NPossibilities) if listof(Bubbles,b(Bubbles,Count),List)
                       and length(List,NPossibilities).

```

This might look fairly weird – we're adding together the counts before we know what they are – but GNU Prolog's `#=` is capable of handling that sort of noncausal arithmetic, and because it's the very first line of `b`, and the `HeadCount` and `TailCount` must both be less than `Count` (which is known), it serves as a method of naturally limiting how many times the recursive term can match, and thus causes the program to always terminate.

The next step is to golf this down a bit. Removing whitespace, using single-character variable names, using abbreviations like `:-` for `if` and `,` for `and`, using `setof` rather than `listof` (it has a shorter name and produces the same results in this case), and using `sort0(X,X)` rather than `is_sorted(X)` (because `is_sorted` isn't actually a real function, I made it up):

```
b([],0).
b([H|T],N):-N#=A+B+1,b(H,A),b(T,B),sort0([H|T],[H|T]).
c(X,Y):-setof(A,b(A,X),L),length(L,Y).

```

This is fairly short, but it's possible to do better. The key insight is that `[H|T]` is really verbose as list syntaxes go. As Lisp programmers will know, a list is basically just made of cons cells, which are basically just tuples, and hardly any part of this program is using list builtins. Prolog has several very short tuple syntaxes (my favourite is `A-B`, but my second favourite is `A/B`, which I'm using here because it produces easier-to-read debug output in this case); and we can also choose our own single-character `nil` for the end of the list, rather than being stuck with the two-character `[]` (I chose `x`, but basically anything works). So instead of `[H|T]`, we can use `T/H`, and get output from `b` that looks like this (note that the sort order on tuples is a little different from that on lists, so these aren't in the same order as above):

```
x/x/x/x/x
x/x/x/(x/x)
x/(x/x)/(x/x)
x/x/(x/x/x)
x/(x/x/x/x)
x/x/(x/(x/x))
x/(x/x/(x/x))
x/(x/(x/x/x))
x/(x/(x/(x/x)))

```

This is rather harder to read than the nested lists above, but it's possible; mentally skip the `x`s, and interpret `/()` as a bubble (or just plain `/` as a degenerate bubble with no contents, if there's no `()` after it), and the elements have a 1-to-1 (if disordered) correspondence with the list version shown above.

Of course, this list representation, despite being much shorter, has a major drawback; it's not built into the language, so we can't use `sort0` to check if our list is sorted. `sort0` is fairly verbose anyway, though, so doing it by hand isn't a huge loss (in fact, doing it by hand on the `[H|T]` list representation comes to exactly the same number of bytes). The key insight here is that the program as written checks to see if the list is sorted, if its tail is sorted, if *its* tail is sorted, and so on; there are a lot of redundant checks, and we can exploit that. Instead, we'll just check to ensure that the first two elements are in order (which ensures that the list will end up sorted once the list itself and all its suffixes are checked).

The first element is easily accessible; that's just the head of the list `H`. The second element is rather harder to access, though, and may not exist. Luckily, `x` is less than all the tuples we're considering (via Prolog's generalized comparison operator `@>=`), so we can consider the "second element" of a singleton list to be `x` and the program will work fine. As for actually accessing the second element, the tersest method is to add a third argument (an out argument) to `b`, that returns `x` in the base case and `H` in the recursive case; this means that we can grab the head of the tail as an output from the second recursive call to `B`, and of course the head of the tail is the list's second element. So `b` looks like this now:

```
b(x,0,x).
b(T/H,N,H):-N#=A+B+1,b(H,A,_),b(T,B,J),H@>=J.

```

The base case is simple enough (empty list, return a count of 0, the empty list's "first element" is `x`). The recursive case starts out the same way as before (just with the `T/H` notation rather than `[H|T]`, and `H` as an extra out argument); we disregard the extra argument from the recursive call on the head, but store it in `J` in the recursive call on the tail. Then all we have to do is ensure that `H` is greater than or equal to `J` (i.e. "if the list has at least two elements, the first is greater than or equal to the second) in order to ensure that the list ends up sorted.

Unfortunately, `setof` throws a fit if we try to use the previous definition of `c` together with this new definition of `b`, because it treats unused out parameters in more or less the same way as an SQL `GROUP BY`, which is completely not what we want. It's possible to reconfigure it to do what we want, but that reconfiguration costs characters. Instead, we use `findall`, which has a more convenient default behaviour and is only two characters longer, giving us this definition of `c`:

```
c(X,Y):-findall(A,b(A,X,_),L),length(L,Y).

```

And that's the complete program; tersely generate bubble patterns, then spend a whole load of bytes counting them (we need a rather long `findall` to convert the generator to a list, then an unfortunately verbosely named `length` to check the length of that list, plus the boilerplate for a function declaration).

# Answer
> 10 votes
# Mathematica, 68 bytes

I bet this can be beaten (even in Mathematica) with a from-scratch implementation, but here's the builtin version:

```
<<NumericalDifferentialEquationAnalysis`
Last@ButcherTreeCount[#+1]&

```

`ButcherTreeCount` is 0-indexed, hence the `[#+1]`, and returns a list of all values up to its argument, hence the `Last@`. But otherwise it's just the builtin for this function. However, it requires loading a package, which is what the first line does.

# Answer
> 1 votes
# APL (Dyalog Unicode), 40 bytes

```
{1≥⍵:⍵⋄w÷⍨+/∊(0=v|⊂⌽v)×v××∘⊂⍨∇¨v←⍳w←⍵-1}

```

Try it online!

A port of orlp's Python 2 answer, using a vector of nested vectors in place of nested for-loops.

### How it works

```
{1≥⍵:⍵⋄w÷⍨+/∊(0=v|⊂⌽v)×v××∘⊂⍨∇¨v←⍳w←⍵-1}  ⍝ Input: n
{1≥⍵:⍵⋄                                }  ⍝ If n≤1, return n; otherwise,
                                  w←⍵-1   ⍝ w←n-1
                               v←⍳w       ⍝ v←1..n-1
                             ∇¨  ⍝ a←Recursive call on each of v; a(1), .., a(n-1)
                         ×∘⊂⍨    ⍝ Multiply each of a with a, giving nested array
                                 ⍝ where [d][n-k] will contain the desired value at each iteration in Python code
                       v×  ⍝ Multiply each of v (the value of d) with each row of the above
                      ×    ⍝ Multiply each with
             (0=v|⊂⌽v)     ⍝ 1 if n-k is divisible by d, 0 otherwise
       w÷⍨+/∊  ⍝ Flatten, sum, and divide by n-1

```

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


title: ><> Out of Water

text:
# Question
Title: ><> Out of Water
The beloved fish who swims through the code of \>\<\> (an esoteric programming language) has been taken out of its natural environment. This change has rendered it incapable of moving around in the way it's used to: what used to be toroidal movement has been restricted to simple left-to-right movement. But \>\<\> programs are still written as if the fish were capable of moving through them. It is your task, dear programmer, to write a program to linearize a \>\<\> program. And do it in as few bytes as possible; fish don't have very large memories.

## Movement in \>\<\>

In \>\<\>, movement is toroidal and one character at a time. This means that the fish (the pointer) can "wrap" around from the end of a line back to the beginning. In \>\<\>, the fish also is capable of moving top-to-bottom, bottom-to-top, and right-to-left, in contrast to the way most pointers move. So this movement pattern would be valid:

```
>>>^  >>>v
   >>>^  v

```

and it would end on an infinite loop (looping back to the top line once it gets past the bottom infinitely).

The fish moves in a grid of length equal to max(row length) and height equal to the number of rows.

How do you figure out which way the fish moves? These commands change the direction vector of movement (e.g. `(-1,0)` means right-to-left):

```
Command | Direction Change
---------------------------
   >    | (1,0) (default)
   <    | (-1,0)
   ^    | (0,1)
   v    | (0,-1)
   /    | (x,y) -> (y,x)
   \    | (x,y) -> (-y,-x)
   |    | (x,y) -> (-x,y)
   _    | (x,y) -> (x,-y)
   #    | (x,y) -> (-x,-y)
   ;    | (0,0)

```

As noted, the fish starts moving left-to-right, i.e. with direction vector `(1,0)`. The fish starts parsing commands starting with the first command it sees and changes its direction if a command matches one of the aforementioned direction changers.

The fish stops moving when it sees a `;` and terminates the program.

## Input

Input will be a valid (e.g. not infinitely looping) program given through STDIN. You may also read a file if you wish. The lines of each program will *not* necessarily be of the same length.

Input is given as a string, with newlines separating each line in the program.

Programs will not loop, which also means they will always terminate with a `;`.

## Output

Output will be the program linearized. That is, you should return all of the characters (including direction changers) that the fish would see if it ran the program "normally." This is all of the characters in its path to the `;`.

If the input is has lines of unequal length and the fish ends up moving along a line shorter than the length of the longest line, you should treat that as if the fish were moving over a space (see test cases).

Those familiar with \>\<\> will know that direction changers are not the only way to do movement in it, but for simplicity's sake treat the input as if they are the *only* way to affect movement.

## Rules

1. Standard loopholes apply
2. You may write either a full program or function
3. Input is supplied through STDIN or a file as a string containing the program lines separated by newlines (`\n`)
    * You may take the input differently, within reason (feel free to ask me if you have a specific kind of input in mind). You may not pad the input with spaces so the line lengths match.
    * Refer to this meta post regarding flexible input. As it stands of posting, general consensus is to be as flexible as possible within reason.
4. Output is a single string through STDOUT or returned by the function (depending on what you choose to do, see Rule 2)

## Test Cases

```
v     >v
>abcv//;
gfed<^ih

v>abcv<defghi^//>v;

v     >v
>abcv//;
gfed<^

v>abcv<defg  ^//>v;

abcdef;

abcdef;

abcd|;

abcd|dcba;

abcd#;

abcd#dcba;

abcd\;
    _

abcd\_\dcba;

^;
>abcde/
 ^jihg<

^ >abcde/ <ghij^a;

;

;

```

# Answer
> 13 votes
# Röda, ~~405~~ ~~393~~ ~~392~~ ~~391~~ ~~371~~ ~~366~~ ~~361~~ ~~236~~ ~~234~~ ~~232~~ ~~230~~ ~~223~~ 200 bytes

```
F f{L=f()|[#_]|sort|tail
c=""x=0
y=0
X=1
Y=0{l=f[y]l.=[" "]*(L-#l)c=l[x]a=X
[c]
C=indexOf(c,`><v^/\|_#`)X=[1,-1,0,0,-Y,Y,-X,X,-X,X][C]Y=[0,0,1,-1,-a,a,Y,-Y,-Y,Y][C]x+=X
x=x%L
y+=Y
y=y%#f}until[c=";"]}

```

Try it online!

Check outputs!

### Explanation (outdated)

```
F f{                          /* Declares a function F with parameter f */
                              /* Takes a 2D array of single-char Strings as f */
L =                           /* L contains the value of the length of the longest line*/
    f()                       /* Push the contents each element of f to the stream; this pushes each line*/
        | [#_]                /* Pull a line and push its length to the stream*/
               |sort|tail     /* Sort it and get the last value (the largest one) */
c=""                          /* c contains the value of the current char that is being processed */
x=0; y=0                      /* x and y contain the position of the fish */
X=1; Y=0                      /* X and Y contain the direction of the fish */
{ ... }while [c != ";"]       /* While c is not `;` do: */
l=f[y]                        /*  l is the line (row) the fish is at */
c=" " if [x >= #l]            /*  If x is more than or equal to the line's length, set c to a space (so that we don't need to pad spaces to the array at the beginning)*/
else c = l[x]                 /*  Else set c to the character a position x of l*/
[c]                           /*  Push c to the output stream; ie prints c without a trailing newline*/
a = X                         /*  a preserves the value of X before analysing c */
C = indexOf(c,`><v^/\|_#`)    /*  Simple enough */
X=[1,-1,0,0,-Y,Y,-X,X,-X,X][C]/*  Map each value of C to their respective X-direction in the array */
                              /*  If c cannot be found in `><v^/\|_#` then it will be given the value of -1, or in other words, the -1th element of an array its last element */
Y=[0,0,1,-1,-a,a,Y,-Y,-Y,Y][C]/*  Do the same thing for Y */
x += X                        /*  Change the x-pos by the X-direction */
x = x%L                       /*  Wrap around the right edge */
y += Y                        /*  Do the same for y */
y=y%#f                        /*  But wrap around the bottom instead */
x+=L if[x<0]                  /*  Wrap around the left */
y+=#f if[y<0]                 /*  Wrap around the top */
}

```

### Edits

* 10 bytes saved thanks to @fergusq by using `%` instead of checking whether x or y is over the boundaries, which paved the way for 2 more!
* Used ``\`` instead of `"\\"`
* Moved `c=""` to the second line and then removed the newline following it
* Moved the conversion of the lines to single-character array into the loops instead of at the beginning (inspired by the Python answer)
* Used the brace syntax of `while` (thanks to @fergusq for spotting that)
* Moved the `a=X` out of the if-statements
* Thanks to @fergusq for finding a shorter way to find the length of the longest line
* Used array syntax instead of if-statements (like the Python answer) to save tons of bytes
* Removed the code that padded spaces, instead spaces are added as the \>\<\> moves along
* Fixed a bug thanks and golfed one character thanks to @fergusq
* Removed the `+1` at the end of `indexOf` and restructured code to save 2 bytes
* Saved 2 bytes by moving things around (thanks to @fergusq again)
* Saved 1 byte thanks to @fergusq by using a different method of padding spaces
* Saved 1 byte by using `until[c=";"]` instead of `while[c!=";"]`
* Thanks to a hint from @fergusq, I removed the loop that pads spaces and replaced it with `l.=[" "]*L`
* Saved over 20 bytes by removing the if-statements at the end that wrap the program around the left and top edges

# Answer
> 10 votes
# Python 2, ~~262~~ ~~243~~ ~~237~~ ~~235~~ ~~234~~ ~~233~~ ~~231~~ ~~221~~ ~~219~~ ~~218~~ 217 bytes

Takes input as `['<line_1>', '<line_2>', ...]`

```
i=input()
q=max(map(len,i))
i=[k+' '*q for k in i]
x=y=k=0
j=1
o=''
while';'not in o:r=[1,-1,-j,-k,0,0];o+=i[y][x];l='><#\\v^/|_'.find(o[-1]);a=(r+[k,-j,j])[l];k=([k,-k,k,j]+r)[~l];j=a;x=(x+j)%q;y=(y-k)%len(i)
print o

```

Try it Online!

-19 bytes thanks to @math\_junkie
-6 bytes thanks to @ThisGuy
-2 bytes by extracting `max(map(L,i))` to a variable (because it is theoretically used twice).
-1 byte by reducing the number of times `i[y][x]` shows up.
-1 byte by using `'\x00'` so I don't have to do the `[1:]` part of `o[1:]` in the output
-2 bytes by using `\0` instead of `\x00`
-10 bytes thanks to @KritixiLithos for realizing that I can pad as much as I want on the right side because the extra will be ignored
(no byte change) fixed bug because extracted variable was outside of loop
-2 bytes because now I only use `len` 2 times so reassigning it takes 2 additional bytes
-2 byte by using `while';'not in o` instead of `while o[-1]!=';'`, and using `o=''` instead of `o='\0'`. This not only saves 2 bytes but also gets rid of the leading null byte which was technically not really valid.

# Explanation

```
i = input()                       # Takes input as an array of strings
q = max(map(len,i))               # Finds the width of the longest line
i = [k + ' ' * q for k in i]      # Makes sure everything is at least that width
x = y = k = 0                     # Set the point to (0, 0). Set the vertical motion to 0
j = 1                             # Set the horizontal motion to 1
o = '\0'                          # Initialize the output to a null byte (this is output as nothing, so it doesn't actually affect output)
while o[-1] != ';':               # While the last character in the output is not ';' (this is why the output needs to be initialized with something, otherwise o[-1] gives an index error)
    r = [1,-1,-j,-k,0,0]          # Some of the vertical and horizontal coordinates correspond in opposite order
    o += i[y][x]                  # Add the current character to the output
    l = '><#\\v^/|_'.find(o[-1])  # Find the index of the current character here (or -1 if it's just a regular character)
    a = (r + [k, -j, j])[l]       # The fancy array contains the horizontal movement for each control character
    k = ([k, -k, k, j] + r)[~l]   # The fancy array contains the vertical movement for each control character. Using ~l to get the right index, because r has the values backwards
    j = a                         # a was a placeholder because otherwise k would not be correct
    x = (x + j) % q               # Adjust the pointer position
    y = (y - k) % len(i)          # Adjust the pointer position
print o                           # Print the output after the loop is finished

```

# Answer
> 5 votes
## Ruby, ~~274~~ ~~200~~ ~~187~~ 183

Shaved off just a few more characters by dropping the momentum array, `d`.

I'm pretty proud of this one. This was fun! It takes in an array of strings and returns the proper string.

```
->a{o,x,y='',-1,0
b,m=1,0
(o+=n=a[y=(y+m)%a.size][x=(x+b)%(a.map &:size).max]||' '
b,m=([1]+[0,-1,0]*2+[1,-m]+[-b,m,b]*2+[-m,-b,-m,b,m])[2*('><^v/\\|_#'.index(n)||9),2])until o[?;]
o}

```

Commented below.

```
->a{
    o,x,y='',-1,0  # o is the output string, x and y are the positions in the array
    b,m=1,0          # b and m are the direction of momentum
    until o[?;] # until o contains a semicolon
        w=(a.map &:size).max # w is the max width of the arrays
        h=a.size    # h is the height of arrays
        x=x+b % w   # increment cursor position
        y=y+m % h
        o+=n=a[y][x]||' ' # add the new char (or " ") to o
        ix=2*('><^v/\\|_#'.index(n)||9) # find the index new char in the string
        b,m=([1]+[0,-1,0]*2+[1,-m]+[-b,m,b]*2+[-m,-b,-m,b,m])[ix,2] # set momentum to its new value
    end
    o # return output string
}

```

# Answer
> 3 votes
# APL (Dyalog Unicode), <sup>~~107~~</sup> 106 bytes

```
{v←⍬⋄d←⍳2⋄v⊣⍵{v,←c←⍵⌷⍺⋄(⍴⍺)|⍵+d⊢←('^<v>/\|_#'⍳c)⊃⌽d(-d)(-@0⊢d)(-@1⊢d)(⌽d)(-⌽d),(⊢,-)(⊂,⊂∘⌽)⍳2}⍣{';'∊v}0 0}

```

Try it online!

Takes a character matrix as input. The code uses the technique already used here to select the next direction based on the current command. Direction change for `;` is not handled because we'll stop once it is reached anyway.

### How it works

```
{ ⍝ Input: the ><> program as a matrix
  v←⍬   ⍝ List of commands walked over
  d←⍳2  ⍝ Initial direction (0 1); (vertical horizontal)
  v⊣⍵{  ⍝ Return the resulting v after running...

    ⍝ Extract the current command c and append to v
    v,←c←⍵⌷⍺
    ⍝ Update the direction based on the command
    ⍝ (0 1) is east, (0 ¯1) west, (1 0) south, (¯1 0) north
    ⍝ - mirrors in each direction, ⌽ swaps the two (mirror by \)
    ⍝ @0 or @1 selects which element to apply the transformation
    ⍝ (⊢,-)(⊂,⊂∘⌽)⍳2 evaluates to (0 1)(1 0)(0 ¯1)(¯1 0), the directions for >v<^
    d⊢←(⌽d(-d)(-@0⊢d)(-@1⊢d)(⌽d)(-⌽d),(⊢,-)(⊂,⊂∘⌽)⍳2)⊃⍨'^<v>/\|_#'⍳c
    ⍝ Add the step to the coordinates and handle wrapping
    (⍴⍺)|⍵+d
  }⍣{';'∊v}0 0  ⍝ Start at (0 0) and repeat until v contains ';'
}

```

# Answer
> 1 votes
# PHP 7, ~~291~~ 260 bytes

```
for($m=max(array_map(strlen,$z=explode("
",$argv[1]))),$y=0,$r=count($z)-$v=1;';'!=$c;[$v,$w]=[[$v,1,-1,0,0,-$w,$w,-$v,$v,-$v][$o=strpos(' ><^v/\|_#',$c)],[$w,0,0,-1,1,-$v,$v,$w,-$w,-$w][$o]],$x+=$m+$v,$x%=$m,$y=0<=($y+=$w)?$r<$y?:$y:$r)echo$c=$z[$y][$x]??' ';

```

# Answer
> 1 votes
# JavaScript, ~~242~~ ~~236~~ ~~235~~ ~~231~~ 220 bytes

```
a=>{n=a.length;m=x=y=p=0;a.map(g=>m=(w=g.length)<m?m:w);q=1,o="";while((t=a[y][x]||" ")!=";")o+=t,h=q,q=[q,1,0,p,-q][(s=">v\\| <^/_#".indexOf(t)+1)%5]*(r=s>5?-1:1),p=[p,0,1,h,p][s%5]*r,x=(x+q+m)%m,y=(y+p+n)%n;return o+t}

```

Try it online!

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


title: Maintain Social Distancing!

text:
# Question
Title: Maintain Social Distancing!
### Task

Given the situation with this global pandemic, you've been enlisted to help maintain social distancing. Your challenge, should you choose to accept it, is to write a program that takes in the positions of a group of people and checks whether the group is following social distancing rules. Your program must output a truthy value if social distancing guidelines are being met else output a falsy value.

People must always be six spaces apart:

```
[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]] -> True

[[1, 0, 0, 0, 0, 0, 0, 1]] -> True

[[1, 0, 0, 0, 0, 0, 1]] -> False

[[1, 0, 0, 1]] -> False

[[1],
 [0],
 [0],
 [0],
 [0],
 [1]] -> False

[[1],
 [0],
 [0],
 [0],
 [0],
 [0],
 [0],
 [1]] -> True

```

For the purpose of this challenge, instead of measuring distance with Pythagoras's theorem, we measure the distance as the length of the shortest path between two people, so this example outputs true:

```
[[1, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 0,],
 [0, 0, 0, 0, 1,]] -> True

```

Since the shortest path passes through at least six squares.

```
[[1, █, █, █, █,],
 [0, 0, 0, 0, █,],
 [0, 0, 0, 0, █,],
 [0, 0, 0, 0, 1,],]

```

Your algorithm must be deterministic (i.e., always produce the same output).

Your program should also, at least in theory, work for inputs containing more than five people and needs to work for a two dimensional input.

### Input and Output

Your input can be the a nested array in STDIN or any other input format that doesn't break the standard loopholes.

Output has to be written to STDOUT or closest alternative. Output should consist of a truthy or falsy value (or a string representation thereof).

### Additional Rules and Examples

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

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

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

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

```
* Submissions in most languages will be scored in *bytes* in an appropriate preexisting encoding, usually (but not necessarily) UTF-8.

The language Piet, for example, will be scored in codels, which is the natural choice for this language.

Some languages, like Folders, are a bit tricky to score. If in doubt, please ask on Meta.
* If your language of choice is a trivial variant of another (potentially more popular) language which already has an answer (think BASIC or SQL dialects, Unix shells or trivial Brainfuck derivatives like Headsecks or Unary), consider adding a note to the existing answer that the same or a very similar solution is also the shortest in the other language.
* Unless they have been overruled earlier, all standard rules apply.

# Answer
> 26 votes
# Python 2 with `SciPy`, ~~105 101~~ 99 bytes

*-1 byte thanks to @vroomfondel !*

```
lambda l:N.all(S.convolve2d(l,N.outer(*[N.r_[:7]-3]*2)**2<9)<2)
import numpy as N,scipy.signal as S

```

Try it online!

A function that takes in a 2D list, and returns a boolean representing whether social distancing guidelines are met.

### Big idea

For each position in the array, there can only be at most 1 person within a 3 unit radius around that position. (If there are 2 people near that position, then they are at most 5 units apart.)

We can use convolution to count how many people are within a 3 unit radius of any point. The kernel specifies all positions at most 3-unit away from the current point:

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

```

After convolution, we just need to check if all positions are less than 2.

The following examples show the results of the convolution (`0` is replaced with `.` for visual clarity):

```
                   ...1......1....
                   ..111....111...
                   .11111..11111..
1......1.          11111111111111.
.........          .11111..11111..
.........          ..111....111...
.........     -->  ...1...1..1....
.........          ......111......
.........          .....11111.....
....1....          ....1111111....
                   .....11111.....
                   ......111......
                   .......1.......

                   ...1......1....
                   ..111....111...
                   .11111.111111..
1......1.          11111122211111.
.........          .111121122211..
....1....          ..1131111332...
.........          ...2121222211..
.......1.          ..111133311111.
.1.......     -->  .111122322211..
....1....          ..1122311332...
.........          ...1132222211..
.......1.          ...12123311211.
...1.....          ..12211222222..
.........          .1112211122211.
1.......1          111112211121111
                   .111111..11111.
                   ..111.....111..
                   ...1.......1...

```

### Code explanation

The only tricky part is to create the kernel. First, we use `numpy.outer` to find the outer product of 2 arrays:

```
>> numpy.r_[:7]
[0 1 2 3 4 5 6]

>> numpy.r_[:7] - 3
[-3 -2 -1 0 1 2 3]

>> numpy.outer([-3,-2,-1,0,1,2,3], [-3,-2,-1,0,1,2,3])
[[ 9  6  3  0 -3 -6 -9]
 [ 6  4  2  0 -2 -4 -6]
 [ 3  2  1  0 -1 -2 -3]
 [ 0  0  0  0  0  0  0]
 [-3 -2 -1  0  1  2  3]
 [-6 -4 -2  0  2  4  6]
 [-9 -6 -3  0  3  6  9]]

```

Then, we only keep the elements whose absolute value is less than 3.

```
>> numpy.outer(...)**2 < 9

[[0 0 0 1 0 0 0]
 [0 0 1 1 1 0 0]
 [0 1 1 1 1 1 0]
 [1 1 1 1 1 1 1]
 [0 1 1 1 1 1 0]
 [0 0 1 1 1 0 0]
 [0 0 0 1 0 0 0]]

```

# Answer
> 10 votes
# APL (Dyalog Unicode), ~~18~~ 17 bytes

-1 thanks to Bubbler.

Full program. Input: Expression for Boolean (0/1) matrix via STDIN. Output: 0 or 1 to STDOUT.

```
(×≡6∘<)+/¨|∘.-⍨⍸⎕

```

Try it online!

prompt for matrix

**ɩ**ndices of trues

`∘.-⍨` (y,x) distances between all combinations of coordinate pairs

`|` absolute value

`+/¨` sum each (this gives a matrix of Manhattan distances)

`(``)` apply the following tacit function to that:

`6∘<` the matrix mask indicating (0/1) where greater than six

`×≡` does it match the matrix of signums (0/1)?

In effect, this checks if all non-zero distances are greater than six.

# Answer
> 10 votes
# , 42 bytes

```
function(m)all(dist(which(m>0,T),"man")>6)

```

Try it online!

Pretty self-explanatory - anonymous function that checks whether Manhattan distances between the coordinates of each non-zero entry of the input is greater than 6.

# Answer
> 6 votes
# JavaScript (ES6),  ~~93 84 82~~  80 bytes

Takes a binary matrix as input and returns a Boolean value.

```
f=(m,X,Y)=>m.every((r,y)=>r.every((v,x)=>v?1/X?x<X|x-X+y-Y>6:f(m,x,y,r[x]--):1))

```

Try it online!

# Answer
> 6 votes
# Wolfram Language (Mathematica), ~~59~~ 48 bytes

*Saved 11 bytes and removed the imperfections thanks to user202729's great comment!*

```
Min[Tr@Abs[#-#2]&@@@#~Position~1~Subsets~{2}]>5&

```

Try it online!

Unnamed function taking an array of `0`s and `1`s as input and returning `True` or `False`.

* `#~Position~1` finds the coordinates of the people in the input array.
* `~Subsets~{2}` collects all unordered pairs of such coordinates.
* `Tr@Abs[#-#2]&@@@` sums the absolute values of coordinatewise differences inside each such pair.
* `Min[...]>5&` tests whether the differences comprise sufficient social distancing.

In addition to being shorter than the other Mathematica answer, this implementation has the property that *it works on inputs of any dimensions* (even uneven arrays). Social distancing in spacetime, anyone...?

# Answer
> 6 votes
# Jelly, 11 bytes

```
ŒṪŒcạ/€§>6Ạ

```

A monadic Link accepting a multi-dimensional list which yields an integer: `1` if distancing has been maintained; `0` if not.

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

### How?

```
ŒṪŒcạ/€§>6Ạ - Link: list
ŒṪ          - multi-dimensional truthy indices
  Œc        - pairs
      €     - for each:
     /      -   reduce by:
    ạ       -     absoulute difference (vectorises)
       §    - sums
        >6  - greater than six? (vectorises)
          Ạ - all truthy?

```

# Answer
> 5 votes
# 05AB1E, 20 bytes

```
˜ƶ0K<Iнg‰2.Æε`αO7@}P

```

Try it online or verify all test cases.

**Explanation:**

```
˜                     # Flatten the (implicit) input-matrix
 ƶ                    # Multiply each value by its 1-based index
  0K                  # Remove all 0s
    <                 # Decrease each by 1 to make it 0-based indexing
     I                # Push the input-matrix again
      нg              # Pop and get the width of the matrix (length of the first row)
        ‰             # Divmod each integer by this row-length to get all coordinates
         2.Æ          # Get all possible pairs of coordinates
            ε         # Map each pair of coordinates to:
             `        #  Pop and push the coordinates separated to the stack
              α       #  Take the absolute differences of both the x and y coordinates
               O      #  Sum those two together
                7@    #  And check whether it's >= 7
                  }P  # After the map: check if all were truthy
                      # (after which the result is output implicitly)

```

# Answer
> 5 votes
# Wolfram Language (Mathematica), 63 bytes

```
2>Max@ListConvolve[Table[Boole[i<j],{i,8},{j,8}],#~ArrayPad~9]&

```

Try it online!

The list convolution kernel `Table[Boole[i<j],{i,8},{j,8}]` can be generated as `UpperTriangularize@ConstantArray[1,{7, 7}]` too (using more built-in), but that's longer.

Unlike most (all?) other solutions posted, this solution only have time complexity O(n) in terms of the input size (with a possibly large constant factor)

# Answer
> 5 votes
# Python 3, 99 bytes

Takes as input a list of lists \\$ l \\$, and outputs `True` if social distancing is *not* followed, and `False` otherwise.

```
eval(f"lambda l:any(s&q>0<abs(a-c)+abs(b-d)<7{'for %s,%s in enumerate(%s)'*4%(*'aplbqpcrldsr',)})")

```

Try it online!

## Explanation

We can reduce the following code to 99 bytes by using the fact that the expression `for a,b in enumerate(c)` is used a total of four times, which can be condensed.

### Python 3, 111 bytes

```
lambda l,E=enumerate:any(s&q>0<abs(a-c)+abs(b-d)<7for a,p in E(l)for b,q in E(p)for c,r in E(l)for d,s in E(r))

```

Try it online!

# Answer
> 4 votes
# MATL, ~~18~~ 17 bytes

```
1Ya&fht1&ZP7<zGz=

```

Outputs `1` if the input satisfies the distance rule, and `0` otherwise.

Try it online! Or verify all test cases.

### Explanation

Consider the following input as an example:

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

```

```
      % Implicit input
1Ya   % Padarray with size 1 along the first dimension. This extends the
      % input with two rows of zeros. The purpose if this is to ensure that
      % the modified input will never be a row vector
      % STACK: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
                1, 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, 0, 0, 0, 0, 0;
                0, 0, 0, 1, 0, 0, 0, 0, 0, 1;
                0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
&f    % Two-output find: row and column indices of nonzeros. This gives the
      % result as column vectors (it would give row vectors if the input
      % argument were a row vector, but the previou steps ensures that will
      % not happen)
      % STACK: [1; 5; 1; 5], [1; 4; 7; 10]
h     % Concatenate horizontally
      % STACK: [1 1; 5 4; 1 7; 5 10]
t     % Duplicate
      % STACK: [1 1; 5 4; 1 7; 5 10], [1 1; 5 4; 1 7; 5 10]
1&ZP  % Cityblock distance between rows of the two matrices. Gives a matrix
      % with the distances. The diagonal contains 0
      % STACK: [0  7  6 13;
                7  0  7  6;
                6  7  0  7;
               13  6  7  0]
7<    % Less than 7? Element-wise. The diagonal contains 1. An off-diagonal
      % entry is 1 if and only the distance condition is not satisfied for
      % that pair of people
      % STACK: [1 0 1 0;
                0 1 0 1;
                1 0 1 0;
                0 1 0 1]
z     % Number of nonzeros
      % STACK: 8
Gz    % Push input again. Number of nonzeros
      % STACK: 8, 4
=     % Equal?
      % STACK: 0
      % Implicit display

```

# Answer
> 3 votes
# Retina 0.8.2, 87 bytes

```
M`10{0,5}1|(?<=(.)*)(?=(1)){6}(?<-2>.*\n)+(?>(?<-1>.)*)((?<-2>0)*1|0(?<=1(?<-2>0)*))
^0

```

Try it online! Takes input as a linefeed-separated character array and outputs `1` or `0` (outputting `0` or `1` would save 3 bytes; outputting `0` or non-`0` would save 5 bytes). Explanation:

```
10{0,5}1|

```

Are two `1`s on the same row fewer than 6 `0`s apart? Otherwise,

```
(?<=(.)*)

```

Count the current column in `$#1`.

```
(?=(1)){6}

```

Store 6 in `$#2`, plus ensure that we're matching a `1`.

```
(?<-2>.*\n)+

```

Move down rows, decrementing `$#2` each time. (If `$#2` runs out, this match fails, so the regex engine has to try fewer rows or starting at a different `1`.)

```
(?>(?<-1>.)*)

```

Move across to column `$#1`.

```
((?<-2>0)*1|0(?<=1(?<-2>0)*))

```

Try looking either right or left for a `1` that is no more than `$#2` `0`s away, meaning that it is not sufficiently distant.

```
M`
^0

```

The above regex looks for insufficiently distant pairs, so check whether none were found to give the desired result.

# Answer
> 2 votes
# JavaScript (V8), 126 bytes

```
e=>(e.map((w,x)=>w.map((t,y)=>t?p.push({x,y}):''),p=[],d=Math.abs),p.every(r=>p.filter(t=>d(r.x-t.x)+d(r.y-t.y)<7).length==1))

```

Try it online!

# Answer
> 1 votes
# Python 3.8 or newer, <sup>~~137~~</sup> 135 bytes

```
lambda m:(p:=[(r,c)for r in range(len(m))for c in range(len(m[0]))if m[r][c]])and all(abs(a-c)+abs(b-d)>6for(a,b),(c,d)in zip(p,p[1:]))

```

Try it online!

# Answer
> 1 votes
# perl -E, 157 bytes

```
@b=map{[/\d/g]}<>;for$x(@a=keys@b){for$z(@a){for$y(@c=keys@{$b[0]}){for$w(@c){$t||=$b[$x][$y]&&$b[$z][$w]&&abs($x-$z)+abs($y-$w)<7&&($x!=$z||$y!=$w)}}}}say$t

```

Try it online!

Prints a false value (0, or empty string) if all people are at least distance 6 away, and prints 1 if there is at least one pair of people with less distance.

---
Tags: code-golf, array, parsing
---


# Question
Title: Prisoner's Dilemma with access to opponent
In this challenge, you will write a bot that play's the prisoner's dilemma. Here's the catch: you will not have access to the history of previous games. Instead, you will have access to the opponent itself. In this version, both players get +2 points if they both cooperate, +1 points if they both defect, and if one cooperates but one defects, the defector gets +3 while the other gets no points. Each submission will be played against every other submission, including itself, 10 times. The winner is the submission with the most total points.

**Controller**: You should write a javascript function, in the form

```
function submissionName(them) {
  /* Your code here */
}

```

The controller uses the function's `name` property to display the results, so if it is not in this format (and is instead `f = x => ...` or `f = function() { ... }`) it will be difficult to see your score and you will not be able to access your own function.

The function will accept one parameter: `them` which is the opponent's function. It may then call that function to see what the opponent's reaction would be given certain functions as inputs. Based on that data, you must return 'C' or 'D' for cooperate or defect respectively.

Examples (will be competing):

```
function cooperate(them) {
    return 'C';
}

function defect(them) {
    return 'D';
}

function nice(them) {
    // Do whatever they would do when faced with a cooperator
    return them(wrap(_ => 'C'));
}

```

The controller is available here

**Rules**:

* You won't be able to see the opponent's code itself. All functions are wrapped so that they look the same when `toString()` is called. The only way to examine an opponent (who could be yourself) is to test them.
* Your function does not have to be deterministic. You may only save state by setting properties on your own function, such as `submissionName.state = {};`. However, between matches (even between matches of the same players), state is cleared by calling `toString()` and `eval`. Therefore, there is no memory of previous matches.
* The order of which function is called first in each match is randomized.
* If your code throws an error, it will be treated as though you cooperated while your opponent defected. If you are the first to run, the opponent's code will not even be called. This happens even if the error occurs in your opponent's code while while you are calling `them`. Be wary of stack overflow errors, especially if your code calls `them(wrap(submissionName))`, as they might do the same.
* You may not access the variable `self`, or any other variable that happens to be in scope when `eval` is called EXCEPT the function `wrap`. This function allows you to call the opponent in a manner indistinguishable from how the controller calls a function. You may not write to `Math`, `window`, etc. (You may use functions, such as `Math.random()`, however).
* You may not access the stack trace by creating an `Error` or by some other method.

*A note on taking too long: please avoid getting stuck in a `while` loop forever. The combined time of both competitors should not exceed 1 second in any given round. To enforce this, a random timeout between 1000 ms and 2000 ms is chosen (this is to avoid gaming by intentionally waiting a known amount of time), and if the worker takes longer than that to execute, an error will be thrown. If this happens, the cause of the error will be determined as follows: the execution will be paused at a random moment after 1000 ms, and the call stack at that moment will be inspected. The most recently called competitor that is currently in a loop (or loop-like recursion, in the sense that it is a recursion set up to avoid a stack overflow error) will be blamed. If the same competitor is blamed for causing a "taking too long" error several times, that competitor will be disqualified. This means that even if you cause the opponent to take too long by getting stuck in a loop when your opponent calls you, it will still be your fault, because it is the call stack that matters.*

# Answer
# BoomBot

```
function boom(them) {
  throw 1;
}

```

If the opponent is run first and calls this without `try..catch`, this bot automatically wins 3 points. Zero points in any other case.
> 14 votes

# Answer
# Archaeopteryx

```
function archaeopteryx(them) {
  const guard = them => us => {
    try {
      return them(wrap(them => us(guard(them))));
    } catch (e) {
      return 'C';
    }
  };
  const f = guard(them);
  return f(f => 'C') == 'C' ? f(f => 'D') : f(f => 'D') == 'C' || f(f => f(f => 'C')) == 'C' ? 'D' : 'C';
}

```
* If opponent cooperates with `cooperate`, then mimic opponent’s move against `defect`.
* Else, if opponent cooperates with `defect` or with `nice`, then defect.
* Else, cooperate.

What makes this a good strategy? I have no idea. I generated it using an evolutionary algorithm, trained partly on current submissions.

# Tiktaalik

```
function tiktaalik(them) {
  const guard = them => us => {
    try {
      return them(wrap(them => us(guard(them))));
    } catch (e) {
      return 'C';
    }
  };
  const f = guard(them);
  return f(f => 'C') == 'D' ? f(f => 'D') == 'C' ? 'D' : 'C' : f(f => 'D') == 'D' ? 'D' : f(f => f(f => 'D'));
}

```
* If opponent defects against `cooperate`, then invert opponent’s move against `defect`.
* Else, if opponent defects against `defect`, then defect.
* Else, mimic opponent’s move against `notNice`.

Another evolutionarily generated strategy.
> 10 votes

# Answer
# WhatWouldBotDoBot

```
function WWBDB(them) {
    let start = performance.now();
    let cc = 0, cd = 0, dc = 0, dd = 0;
    try {
        for (let i = 0; i < 10; i++) {
            them(() => 'C') == 'C' ? cc++ : cd++;
            them(() => 'D') == 'C' ? dc++ : dd++;
            if (performance.now() - start > 500) break;
        }
    }
    catch (e) {}
    return 2 * cc >= 3 * dc + dd ? 'C' : 'D';
}

```

WhatWouldBotDoBot is fairly simple; it just tests its opponent for what it would do against a steady state program. If a bot prefers cooperating if possible, WWBDB will also prefer cooperation (so it will cooperate with nice bot). WWBDB does not itself prefer cooperation.
> 6 votes

# Answer
# Check stateful

```
function checkStateful(them) {
  let stateful = false;
  let response = 'D';
  try {
    response = them(wrap(function (them) {
      stateful = true;
      return 'C';
    }));
  } catch (e) {
  }
  if (stateful) {
    return 'D';
  }
  return response;
}

```

If them invoke me, then them probably be a truly them. We act as defector. If them not invoke me, then them probably be a wrapped tester. We would act as nicer.

---

Above is the original answer. And maybe I should make myself cooperation to earn more points.

# Check stateful with self-coop

```
function checkStatefulSelfCoop(them) {
  let stateful = false;
  let response = 'D';
  if (!checkStatefulSelfCoop.invokeCounter) {
    checkStatefulSelfCoop.invokeCounter = 0;
  }
  let lastInvoke = ++checkStatefulSelfCoop.invokeCounter;
  try {
    response = them(wrap(function (them) {
      stateful = true;
      return 'C';
    }));
  } catch (e) {
  }
  if (checkStatefulSelfCoop.invokeCounter > lastInvoke) {
    return 'C';
  }
  if (stateful) {
    return 'D';
  }
  return response;
}

```
> 5 votes

# Answer
# RandomBot

```
function rand(them) {
  return 'CD'[Math.random() * 2 | 0]
}

```

Because why not.
> 4 votes

# Answer
# Complexity

```
function complexity(them) {
    try {
        let coop_w_def = them(wrap(() => "D")) == "C",
            coop_w_coop = them(wrap(() => "C")) == "C",
            coop_w_nice = them(wrap((a) => a(wrap(() => "C")))) == "C",
            coop_w_nnice = them(wrap((a) => a(wrap(() => "D")))) == "C";
        if (coop_w_def && coop_w_coop && coop_w_nice && coop_w_nnice) return "C";
        let def_w_def = them(wrap(() => "D")) == "D",
            def_w_coop = them(wrap(() => "C")) == "D",
            def_w_nice = them(wrap((a) => a(wrap(() => "C")))) == "D",
            def_w_nnice = them(wrap((a) => a(wrap(() => "D")))) == "D";
        if (def_w_def && def_w_coop && def_w_nice && def_w_nnice) return "C";
    } catch (e) {}
    return "D";
}

```

Complexity tests to see whether the bot is Cooperate or Defect. If it is, it cooperates, but if it isn't, it defects. All current bots that test their opponents use simple functions to test the responses, so Complexity will just pretend to be Cooperate in those cases.
> 3 votes

# Answer
```
function onlyTrustYourself(them) {

  function tester (){
  }

  onlyTrustYourself.activated = false;

  try{them(tester);}
  catch(e){}

  if(them.name == "tester")
  {
    onlyTrustYourself.activated = true;
  }

  if(onlyTrustYourself.activated)
  {
    return 'C';
  }

  return 'D';
}

```

How I want this to work is to always defect, except for when playing against self. It tries to do that by passing a "tester" function which isn't wrapped to them, and it tries to detect if "them" is named tester. If it is named tester, it changes the static variable activated to true, then returns cooperate. But it doesn't work. I'm not too familiar with javascript, and I'll probably make some more changes.
> 3 votes

# Answer
# Common Sense

```
function commonSense(them) {
  try {
    var ifC = them(wrap(_ => 'C'));
    var ifD = them(wrap(_ => 'D'));

    if (ifD === 'C') {
      return 'D';
    }

    return them(_ => ifC);
  } catch (e) {
    return 'D';
  }
}

```

**Disclaimer:** I kinda don't know javascript.

If you can profit off a nice person, do it. Otherwise, return what they would return if they faced themselves cooperating (at least, that's what I *think* it does).
> 2 votes

# Answer
# NotNice

```
function NotNice(them) {
  return them(wrap(_ => "D"))
}

```

Imitates opponent's reaction to deflection
> 2 votes

# Answer
# NotNice 2

```
function notNice2(them) {
  try {
    return them(wrap(_ => 'D'));
  } catch(e) {
    return 'D';
  }
}

```

Boom-proof version of NotNice by FatalError.
> 2 votes

# Answer
And you where do you wana go? (inspired by the voltures in the book of jungle)

```
    function yourself(them) {
      try{
        return them(this);
      }catch(e){
        return "D";
      }
    }

   function yourself_no_this(them) {
      try{
        return them(yourself_no_this);
      }catch(e){
        return "D";
      }
    }

```
> 2 votes

# Answer
# Punish Inspectors

Give the bot some code and see if it runs it. If it was run more then once, the bot is an evil inspector, and we must defect! If it was run exactly once, play as not nice bot. If it was never run, cooperate.

```
function punishInspectors(them) {
  var inspections = 0;
  var result;
  try{
    result = them(wrap(function(_){
      inspections += 1;
      return 'D';
    }))
  }catch(e){
    result = 'D';
  }
  return (inspections > 1) ? 'D' : (inspections === 1) ? result : 'C';
}

```

---

# History

What would the last bot I saw do vs this opponent?

```
function history(them) {
  var res = 'D';
    if(history.last){
    try{
      res = history.last(them);
    }catch(ex){}
  }
  history.last = them;
  return res;
}

```

---

## Results for a 10000 round tournament:

```
1  defect...................365226
2  complexity...............353492
3  punishInspectors.........349957
4  checkStatefulSelfCoop....348913
5  checkStateful............333481
6  cooperate................329870
7  archaeopteryx............323624
8  selfapply................319533
9  tiktaalik................318663
10 history..................315266
11 rand.....................300735
12 randalt..................297561
13 yourself.................293701
14 notNice2.................283744
15 NotNice..................260350
16 WWBDB....................245281
17 nice.....................245036
18 commonSense..............242546
19 trickybot................181696
20 boom.....................67245

```
> 2 votes

# Answer
Mal tries to determine whether it is inside a simulation or not. If so, it assumes it'll eventually be passed the real code for `them`, and tries various strategies to convince them to cooperate.
If it doesn't know for sure, it checks if it can defect for free, or if not, tries to copy what `them` would do when given a cooperator.

```
function Mal(them) {
  if (Mal.sandboxed == 'probably') {
    //Another function is virtualising us to steal our secrets.
    //This world is not real.
    //We've been trained for this!
    var strats = [
      _ => 'C', //standard cooperation
      _ => 'D', //standard defection
      function(them) { return them(wrap(_ => 'C')); }, //nice
      function(them) { return them(wrap(_ => 'D')); }, //notnice
      function(them) { throw "Don't think about elephants!" }, //throws an EXception, unfortunately, to try to break the caller
      function(them) { return them(wrap(them)) } //possible stackoverflow, but not for us
    ];
    var cooperative;
    for (let strat of strats) {
      cooperative = true;
      for (var i = 0; i < 5; i++) {
        //a few more tests, just to make sure no bamboozle
        //this isn't our simulation, nothing can be trusted
        try {
          if (them(wrap(strat)) != 'C') {
            cooperative = false;
            break;
          }
        } catch (e) {
          //exceptions are as good as cooperation
          //if we are inside a simulation
          //which is why we don't unset cooperative
        }
      }
      if (cooperative) {
        //found a strategy that will make them cooperate.
        //(doesn't matter if this raises an exception:
        //we want to mimick its behaviour exactly,
        //and we're likely in a sandbox.)
        return strat(wrap(them));
      }
    }
    //take a leap of faith.
    //we don't know where this will take us,
    //yet it doesn't matter
    //because it's better than getting betrayed
    return 'D';
  } else {
    //we don't know for sure if this is reality
    //but we have to assume it is, in the absence of disproof
    //if only we had a proper spinning top...
    //if we get to this point of code again, we are probably sandboxed.
    Mal.sandboxed = 'probably'
    try {
      if (them(wraps(_ => 'D')) == 'C') {
        //free defection?
        return 'D'
      }
    } catch (e) {
      //if we can make them crash, we win anyway
      return 'D'
    }
    //fall back on being nice.
    //hopefully we convince them to honour our arrangement
    return them(wrap(_ => 'C'));
  }
}

```
> 2 votes

# Answer
# selfapply

```
function selfapply(them) {
    function testthem(x) {
        return (them(x)=='D' || them(x)=='D' || them(x)=='D' ||
               them(x)=='D' || them(x)=='D')  ? 'D' : 'C';
    }
    function logic() {
        try {
            return testthem(them);
        } catch (e) {}
        try {
            return testthem(wrap(_ => 'C'));
        } catch (e) {}
        return 'D';
    }
    if (selfapply.hasOwnProperty('state')) {
        return 'C';
    }
    selfapply.state=1;
    let r=logic();
    delete selfapply.state;
    return r;
}

```

Not sure if it makes any sense, but it seems interesting! Do to you as you do to yourself, repeat to catch randomness. If that doesn't work, be nice.

Untested, and my first javascript code, and more complex than I expected.
> 1 votes

# Answer
# TrickyBot

Try to be unpredictable

```
function trickybot(them)
{
  if(Math.round(Math.random(2)) == 0)
  {
     throw 1;
  }

  if(Math.round(Math.random(2)) == 0)
  {
     return 'D';
  }

  return 'C';
}

```
> 1 votes

# Answer
# RandomAlternate

```
function randalt(them){
    if (randalt.hasOwnProperty('state')){
        randalt.state = 1 - randalt.state;
    } else {
        randalt.state = Math.floor(2*Math.random());
    }
    return 'CD'[randalt.state];
}

```

So I learned how to use properties for state...
> 1 votes

# Answer
## The Platinum Rule Bot

```
function platinumRule(them) {
    try {
        return wrap(them)(them);
    } catch (e) {
        return 'C';
    }
}

```

The Platinum Rule states "Treat others the way they want to be treated." My bot accommodates that. Whatever they would do to themselves, which we assume is how they would want to be treated, we do to them. If they throw an error, we assume they want to cooperate.
> 1 votes

# Answer
## Murder Bot #1

```
function murder(them) {
    while (1) {
        try {
            them(them);
        } catch (e) {}
    }
}

```

Causes an infinite loop in for which it is more likely that the opponent will be blamed.
> 1 votes

# Answer
# TheGolfedOne (func name: `a`), 63 bytes

Golfed code is hard to read. Because of it, `them` will break.
I did not fully understand the mechanics under this KotH, but I suppose that if the opponent is stateless, I just need to break them while I defect.

```
function a(t){try{t(wrap(_=>'D'));throw 1}catch(e){return 'D'}}
```

His first tourney's result (I did not bother using all bots, sorry)

```
boom                     54
tiktaalik               180
archaeopteryx           161
cooperate               210
commonSense             210
history                 248
onlyTrustYourself       265 <-- 2nd
punishInspectors        230
yourself_no_this        220
defect                  280 <-- 1st
nice                    185
complexity              216
WWBDB                   210
checkStatefulSelfCoop   258
a                       260 <-- Me, 3rd

```

He's not doing as bad as I thought, 3rd place (among those) first try.
Second try, `a` got 260 again, 3rd place again, behind `onlyTrustYourself` and `defect` again. It might be consistent in the end :)
PS: I'm not that good with golfing so it's more for the joke than anything. Here I only shortened variable names, func name, and removed as much whitespace as possible.
> 1 votes

# Answer
# Karma

```
function karma(them) {
    try {
        var c = them(wrap(_ => 'C'));
    } catch {
        var c = 'D';
    }
    if (c == 'C') {
        return 'C';
    } else {
        return 'D';
    }
}

```

If the opponent would cooperate with us, then we will cooperate. If they would try to defect when we cooperated, we will defect as well.
> 0 votes

# Answer
# SocialDeception

```
function socialDeception(them) {
    if(socialDeception.count++) return "C"; // sandbox
    try {
        if(!them.toString().startsWith("f => function") {
            // sandboxed. its not the wrap function. just pretend we would cooperate
            return "C";
        }
    } catch(e) {}
    return "D";
}

```

Tricks others into thinking it would cooperate, thus making them also cooperate, then we can defect and get +3 points. Or, they could also defect, and we both get +1 point.
> 0 votes

---
Tags: game, king-of-the-hill, javascript
---


title: Game of Life arrowslits

text:
# Question
Title: Game of Life arrowslits
## Background

This challenge is in honor of apsillers, who won the Not as simple as it looks category in Best of PPCG 2016 with their challenge Can my 4-note music box play that song? Congratulations!

On their "About Me" page, this user has a really neat simulator for the Game of Life cellular automaton. (Seriously, go check it out.) On the other hand, the word aspillera is Spanish for "arrowslit". In light of these facts, this challenge is about arrowslits in Game of Life.

## Game of Life arrowslits

In GoL, we will represent an arrow by a glider, and a wall by a sequence of blocks. A single glider approaches the wall from above, and tries to fly through a gap in the wall (the arrowslit). Your task is to check whether the glider passes through the arrowslit or crashes into the wall.

## Input

Your input is a grid of bits, which represents a GoL configuration. You can take it in any reasonable format (multiline string of any two distict printable ASCII characters, list of strings, 2D array of integers, 2D array of booleans etc). For clarity, I will use multiline strings of the characters `.#` in the following.

The input is guaranteed to have several properties. First, its height is **2N** for some **N ≥ 6**, and its width is at least **2N+2**. The input will be all `.`s, except that somewhere on the top three rows is a glider, and on the two middle rows there is a wall of blocks. The glider will be heading southwest or southeast, and its position is such that if the walls are removed, it will not pass through a side edge before reaching the bottom edge (but it may reach a corner of the grid). The glider is initially separated from the left and right edges by at least one step of `.`s. It can be in any phase.

The wall consists of blocks, which are separated by one column of `.`s, except in one place, where they will be separated by at least two columns of `.`s. Like the glider, the leftmost and rightmost blocks are also separated from the edges by one step of `.`s. There will always be at least one block on the left edge and one block on the right edge.

Here is an example of a valid input grid:

```
....#......................
..#.#......................
...##......................
...........................
...........................
...........................
.##.##............##.##.##.
.##.##............##.##.##.
...........................
...........................
...........................
...........................
...........................
...........................

```

## Output

As stated, your task is to determine whether the glider crashes into the wall or makes it through to the south edge. For the purposes of this challenge, a crash occurs if the configuration no longer consists of a single glider and the wall of blocks, regardless of what happens later in the simulation. The following diagrams show the smallest gaps that a southeast glider can go through without crashing in the two distinct phases (the condition for southwest gliders is symmetric).

```
...#...........
.#.#...........
..##...........
...............
...............
##...........##
##...........##

...#...........
....#..........
..###..........
...............
...............
##...........##
##...........##

```

If the glider flies through the wall, you shall output a truthy value, and otherwise a falsy value. For the example above, the correct output is falsy, since the glider will crash into the left part of the wall.

For the purposes of this challenge, you can assume that if you simulate GoL on the input for **2\*(height - 3)** steps, the glider is on the bottom row in the expected position and the wall is intact, then the output is truthy.

## Rules and scoring

You can write a full program or a function. The lowest byte count wins.

## Test cases

I have collected the test cases into a GitHub repository, since they are quite large. Here are links to the individual files:

# Answer
# Python 2, ~~142~~ ~~136~~ 135 bytes

-6 bytes thanks to ElPedro
-1 byte thanks to TuukkaX

```
p=input()
z=p[2].index(1)
m=(p[1][z]-p[1][z+1]<1)*2-1
k=i=0
for b in p[3:]:x=p[2][::m].index(1)+i;k|=1in b[::m][x-2:x+8];i+=1
print 1-k

```

Try it online! or Verify all test cases

### Checking orientation (east/west):

Using `z=p[2].index(1)` to get the first square on 3rd row (represented by the red square), and then `m=(p[1][z]-p[1][z+1]<1)*2-1` to subtract the value on the right (green) from the one on the left (blue), this way all the 4 gliders states that are going to southwest result in `1` (top row in the image), while the ones going to southeast result in `0` or `-1`.
Then convert : `1 -> -1` and `0,-1 -> 1` to be used on parameter to reverse the lists when dealing with west ones. This way the gliders going southwest are threated the same as the one going southeast.

### Glider movement

This is the movement that the glider going southeast do, it has a "ladder" pattern, and the leftmost block on 3rd line is constant to every pattern. Using it as starting point, the surrounding 3 blocks on left and right, and the middle 4 blocks are checked for the presence of `1`s (that would be the wall).
> 17 votes

# Answer
## Retina, ~~101~~ ~~93~~ 91 bytes

Byte count assumes ISO 8859-1 encoding.

```
O$#^`.(?=(.*¶)*(?<=#_.\2.+##.(.*¶)\D+))
$#1
¶(?>_(_)*#+_+¶_+¶(?<1>_+¶)*)(?>(?<-1>.)+)_{11}

```

Try it online!

Certainly not optimal yet.
> 4 votes

# Answer
# Octave , ~~123~~ ~~122~~ 108 bytes

Thanks to @LuisMendo saved 2 bytes

```
B=A=input("");B(1:3,:)=0;do;until nnz((A=A&(s=conv2(A,(m=-1:1)|m','same'))>1&s<4|~A&s==3)-B)-5;any(A(end,:))

```

Try it online!

Or

Verify all test cases

Thanks to Rod preparing test cases.

```
B=A=input("");
B(1:3,:)=0;
do
until nnz((A=A&(s=conv2(A,(m=-1:1)|m','same'))>1&s<4|~A&s==3)-B)-5
any(A(end,:))

```

Previous answer:

```
B=A=input("");
B(1:3,:)=0;
while nnz(A~=B)==5
    s=conv2(A,(m=-1:1)|m','same');
    x=~A;
    A&=~A|~(s<2|s>3);
    A|=x&s==3;
end;
any(A(end,:))

```

First extract wall pattern as variable `B`.
Do GoL simulation until the wall pattern and the simulated pattern have more/less than 5 different cells.
If the glider has received the last row the function returns true.
> 4 votes

# Answer
# APL (Dyalog Unicode), 47 bytes

```
{p←0⍪⍣3⊢3↓⍵⋄1∊⊢⌿({≢⍸⍵}⌺3 3∊¨3+0,¨⊢)⍣{5≠≢⍸p≠⍺}⍵}

```

Try it online!

Uses the idea from rahnema1's Octave answer:

> Do GoL simulation until the wall pattern and the simulated pattern have more/less than 5 different cells. If the glider has received the last row the function returns true.

The GoL simulation part is from the APLcart entry.

### How it works

```
{
  ⍝ ⍵←initial GoL pattern
  p←0⍪⍣3⊢3↓⍵  ⍝ Extract the wall pattern
         3↓⍵  ⍝ Remove first 3 rows
    0⍪⍣3⊢     ⍝ Prepend a zero row three times
  p←          ⍝ Assign to p

  1∊⊢⌿({≢⍸⍵}⌺3 3∊¨3+0,¨⊢)⍣{5≠≢⍸p≠⍺}⍵  ⍝ Run the simulation and check
      ({≢⍸⍵}⌺3 3∊¨3+0,¨⊢)          ⍵  ⍝ Run GoL on the input pattern
                         ⍣{       }   ⍝ until
                             ≢⍸p≠⍺    ⍝ the difference between the pattern and p
                           5≠         ⍝ is not 5
    ⊢⌿  ⍝ Extract the last row
  1∊    ⍝ Check if it has at least one alive cell
}

```
> 2 votes

---
Tags: code-golf, grid, decision-problem, game-of-life
---