title: AoCG2021 Day 23: Finding the best seat

text:
# Question
Title: AoCG2021 Day 23: Finding the best seat
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

Related to AoC2020 Day 11, Part 2.

---

You enter the waiting area for a ferry, and you see a bunch of people sitting at a bunch of seats. The seats form a grid like this (`.` is a floor, `L` is an empty seat and `#` is an occupied seat):

```
LL.#L
#.L.L
L.L.L
L.L#.
.#L#L

```

Now, since you value privacy a lot, you try to pick a seat that has the minimum number of people visible from it. A seat is visible from another seat if there is no other seat (empty or occupied; floor doesn't count) exactly on the straight line between the two.

For example (rows and columns are numbered from the top left, starting at 1):

* R1C1 sees R2C1 (directly below it) and the two occupied seats on R5 (because the slope does not allow any other seat in between) but does not see R1C4 (blocked by R1C2) or R4C4 (blocked by R3C3).
* R1C2 does not see R5C4 (due to R3C3 at slope 2/1) but sees the other four.
* R3C1 and R4C3 see all five occupied seats.
* R4C1 sees only two.

Therefore, R4C1 is the best choice for you, and the anti-privacy (the number of occupied seats you can see) of that seat is 2.

Given a grid like this, calculate the minimum anti-privacy over all empty seats.

**Input:** A rectangular grid with three distinct values (you can choose which values to use) for floor, empty seat, and occupied seat, respectively. It is guaranteed that the input contains at least one empty seat.

**Output:** The answer to the problem.

Standard rules apply. The shortest code in bytes wins.

## Test cases

```
L -> 0

LL# -> 0

####
####
####
###L -> 9

.#L.
L..L
#L#L
LL.# -> 3

LL.#L
#.L.L
L.L.L
L.L#.
.#L#L -> 2

```

# Answer
# JavaScript (Node.js), 122 bytes

```
a=>w=>Math.min(...a.map((x,i)=>a.map((y,j)=>t+=x|y&!a.some((z,k)=>z<2&(p=k-i)*(q=j-k)>0&p/(k%w-i%w)==q/(j%w-k%w)),t=0)|t))

```

Try it online!

Input flatten array and width. `L` -\> 0, `#` -\> 1, `.` -\> 2.
> 4 votes

# Answer
# Charcoal, 89 bytes

```
ＷＳ⊞υι≔⟦⟧θＦＬυＦ⌕Ａ§υιL⊞θΣＥυ↨¹Ｅ⌕Ａλ#⬤υ⬤π∨⁼ς.∨∧⁼ρι⁼σκ∨∧⁼ρμ⁼σξ∨⁻×⁻ρι⁻σξ×⁻ρμ⁻σκ∨⁻‹ρι‹μρ⁻‹σκ‹ξσＩ⌊θ

```

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated lines. Explanation:

```
ＷＳ⊞υι

```

Input the grid.

```
≔⟦⟧θ

```

Start building up the anti-privacy numbers.

```
ＦＬυＦ⌕Ａ§υιL

```

Loop over all of the empty seats. (These loops have to use `For` rather than `Map` because Charcoal only has 11 loop variables, I'm already using 10, and each `Map` uses up an extra loop variable. Also, taking the minimum of a doubly nested loop is tricky when the inner loop could be empty.)

```
⊞θΣＥυ↨¹Ｅ⌕Ａλ#⬤υ⬤π∨⁼ς.∨∧⁼ρι⁼σκ∨∧⁼ρμ⁼σξ∨⁻×⁻ρι⁻σξ×⁻ρμ⁻σκ∨⁻‹ρι‹μρ⁻‹σκ‹ξσ

```

Loop over all occupied seats, then check all seats, counting only those occupied seats that are visible.

```
Ｉ⌊θ

```

Output the minimum number of visible occupied seats.

To check whether a seat blocks the view between an empty seat and an occupied seat, I need to know:

* That the seat is on the line joining the empty and occupied seats
* That the seat is between the empty and occupied seats

Testing that the seat is on the line is done using the cross product of the displacements - `(s−e)×(s−o)` is zero in that case. Testing that the seat is between the other seats could have been done using the dot product - both `(s−e)⋅(o−e)` and `(s−o)⋅(e−o)` need to be strictly positive. Unfortunately this takes 94 bytes and it was golfier to test that the seat is in the minimal containing rectangle but is not actually either the empty or occupied seat under consideration.

80 bytes using the newer version of Charcoal on ATO:

```
ＷＳ⊞υιＩ⌊ΣＥυＥ⌕ＡιL↨¹ΣＥυＥ⌕Ａν#⬤υ⬤ς∨⁼τ.∨∧⁼σκ⁼δλ∨∧⁼σξ⁼δρ∨⁻×⁻σκ⁻δρ×⁻σξ⁻δλ∨⁻‹σκ‹ξσ⁻‹δλ‹ρδ

```

Attempt This Online! Link is to verbose version of code. Byte savings come from being able to use 12 loop variables (particularly useful for the outer loop as I get both the row and index) and being able to flatten a list of lists. A further byte could be saved if at least one seat was occupied.
> 4 votes

# Answer
# Pari/GP, 148 bytes

```
a->c=concat;[p,q]=[c([[[i,j]|j<-[1..#a],a[i,j]==t]|i<-[1..#a~]])|t<-[1,2]];vecmin([#[1|y<-q,![u*v~>0|z<-c(p,q),!matdet(Mat([u=x-z,v=z-y]~))]]|x<-p])

```

Try it online!
> 2 votes

# Answer
# TypeScript Types, 994 bytes

```
//@ts-ignore
type a<T,N=[]>=T extends`${N["length"]}`?N:a<T,[...N,0]>;type b<A,B>=A extends[...B,...infer X]?b<X,B>:A;type c<A,B>=[]extends A|B?Exclude<A|B,[]>:c<B,b<A,B>>;type d<A,B,X=0>=B extends[infer Y,...infer B]?d<e<A,[Y[],[1,0]][X][Y]>,B,X>:A;type e<T,P=0,N=[1,0][P]>=T extends[N,...infer T]?T:[...T,P];type f<T>=d<[],T,1>;type g<T,N=[]>=(T extends T?(x:()=>T)=>0:0)extends(x:infer U)=>0?U extends()=>infer V?g<Exclude<T,V>,[...N,0]>:N:0;type h<G,P,S,Q=[d<P[0],S[0]>,d<P[1],S[1]>],V=G[Q[0]["length"]][Q[1]["length"]]>=Q extends 0[][]?[2,V]extends[V,2]?Q:[0,V]extends[V,0]?h<G,Q,S>:never:never;type i<T,K=keyof T>=T extends T?keyof T extends K?T:never:0;type M<G,P={[X in keyof G]:G[X]extends infer R?{[Y in keyof R]:[a<X>,a<Y>]}:0}[number][number],S=(P extends P?c<P[0],P[1]>extends[0]?P|[f<P[0]>,P[1]]|[P[0],f<P[1]>]|[f<P[0]>,f<P[1]>]:never:0),>=i<{[X in keyof G]:G[X]extends infer R?{[Y in keyof R]:R[Y]extends 1?g<S extends S?h<G,[a<X>,a<Y>],S>:0>:never}:0}[number][number]>["length"]

```

Try It Online!

## Ungolfed / Explanation

<pre><code>// Convert a string literal representing a number to a `Nat`
type StrNumToNat<T, N=[]> = T extends `${N["length"]}` ? N : StrNumToNat<T, [...N, 0]>

type ModNat<A, B> = A extends [...B, ...infer X] ? ModNat<X, B> : A

// Calculate the GCD of two `Nat`s using the Euclidean algorithm
type GcdNat<A, B> = [] extends A | B ? Exclude<A | B, []> : GcdNat<B, ModNat<A, B>>

// Add if `X` is `0`, subtract if `X` is `1`
type AddOrSubInt<A, B, X=0> = B extends [infer Y, ...infer B] ? AddOrSubInt<IncOrDecInt<A, [Y[],[1,0]][X][Y]>, B, X> : A

// Increment if `P` is `0`, decrement if `P` is `1`
type IncOrDecInt<T, P=0, N=[1,0][P]> = T extends [N, ...infer T] ? T : [...T, P]

type NegInt<T> = AddOrSubInt<[], T, 1>

type CountUnion<T,N=[]>=(T extends T?(x:()=>T)=>0:0)extends(x:infer U)=>0?U extends()=>infer V?CountUnion<Exclude<T,V>,[...N,0]>:N:0;

// Filter a union of tuples for those with the shortest length
type Shortest<T, K=keyof T> = T extends T ? keyof T extends K ? T : never : 0

// Extrapolate the line of sight for a given slope.
// If the first seat is occupied, return its position; otherwise, return never.
type GetSeat<
  Grid,
  Pos,
  Slope,
  // Add Slope to Pos
  NextPos = [AddOrSubInt<Pos[0], Slope[0]>, AddOrSubInt<Pos[1], Slope[1]>],
  // Get the value at NextPos
  NextSeatVal = Grid[NextPos[0]["length"]][NextPos[1]["length"]],
> =
  // Both coordinates of NextPos are non-negative
  NextPos extends 0[][]
    // If NextSeatVal == 2
    ? [2, NextSeatVal] extends [NextSeatVal, 2]
      // Return NextPos
      ? NextPos
      // Otherwise, if NextSeatVal == 0
      : [0, NextSeatVal] extends [NextSeatVal, 0]
        // Continue down the line of sight
        ? GetSeat<Grid, NextPos, Slope>
        // Otherwise, return never
        : never
    : never

type Main<
  Grid,
  Positions = {
    // Map over the rows
    [X in keyof Grid]: Grid[X] extends infer Row ? {
      // Map over the cells
      [Y in keyof Row]:
        // Return the coordinate as a [Nat, Nat]
        [StrNumToNat<X>, StrNumToNat<Y>]
    } : 0
  // Collect a union of all results
  }[number][number],
  Slopes = (
    // Map over Positions
    Positions extends Positions
      // (note that Positions is now a singular [Nat, Nat])
      // If X and Y are coprime
      ? GcdNat<Positions[0], Positions[1]> extends [0]
        // Return a union of this slope and all reflections of it
        ? Positions
        | [NegInt<Positions[0]>, Positions[1]]
        | [Positions[0], NegInt<Positions[1]>]
        | [NegInt<Positions[0]>, NegInt<Positions[1]>]
        : never
      : 0
  ),
> =
// Get the shortest of:
Shortest<
  {
    // Map over the rows
    [X in keyof Grid]: Grid[X] extends infer Row ? {
      // Map over the cells
      [Y in keyof Row]:
        // If this seat is empty
        Row[Y] extends 1
          // Return the number of slopes where an occupied seat is visible
          ? CountUnion<Slopes extends Slopes ? GetSeat<Grid, [StrNumToNat<X>, StrNumToNat<Y>], Slopes> : 0>
          // Otherwise, return never
          : never
    } : 0
  // Unionize
  }[number][number]
// To number
>["length"]
```
</code></pre>
> 1 votes

# Answer
# Wolfram Language (Mathematica), 95 bytes

```
Min[p=Position;Count[Or@@@#,1<0]&/@Outer[Det@{u=#-#3,v=#3-#2}==0<u.v&,#~p~1,#~p~2,p[#,1|2],1]]&

```

Try it online!
> 0 votes

# Answer
# Python3, 363 bytes:

```
from math import*
r=range
k=lambda x,y:(x//(c:=gcd(x,y)),y//c)
def p(i,t,b,x,y):
 if i==t:return 1
 return((u:=b[(n:=i[0]+x)][(m:=i[1]+y)])!='L'or(n,m)==t)and u!='#'and p((n,m),t,b,x,y)
g=lambda b,d:min([sum([p(i,j,b,*k(j[0]-i[0],j[1]-i[1]))for i in d if d[i]=='#'])for j in d if d[j]=='L'])
f=lambda b:g(b,{(x,y):b[x][y]for x in r(len(b))for y in r(len(b[x]))})

```

try it online!
> 0 votes

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


title: Tips for golfing in Add++

text:
# Question
Title: Tips for golfing in Add++
Add++ is the Language of the Month for January 2022, and so I'm asking for tips for golfing in it. Please stick to tips specific to Add++, and avoid general tips such as "remove whitespace" or "avoid comments".

Please post separate tips as individual answers

# Answer
## Use `L` for the main function, `D` for helper functions

Unnamed<sup>*</sup> lambdas have the syntax

```
L<flags>,<code>

```

For example. This is much shorter than the named version

```
D,<name>,<flags>,<code>

```

For a single byte function name, using a lambda is 3 bytes shorter, and this increases as the name grows longer.

\*: Lambdas are stored in the interpreter as functions with the names `lambda 1`, `lambda 2`, etc. so can be accessed this way

If you're submitting a function submission, the main function should always be an unnamed lambda, and any helper functions should be named. Consider,

```
L,€{lambda 2}
L,'

```

vs

```
L,€g
D,g,@,'

```

which saves 5 bytes
> 7 votes

# Answer
## Call your helper functions `I`, `K`, `Y`, `Z`, `g`, `k`, `l`, `u` or `w`

Add++ doesn't have any way to combine multiple functional builtins into one command (for those familiar, like Jelly's  quicks). If you want to e.g. filter on a complex condition, you'll need to define a helper function containing the code for that condition.

When calling other functions from functional mode, you surround the name with `{...}`:

```
D,main,@,€{triple}
D,triple,@,3*

```

However, if the braces are omitted, it will only take the next character immediately after the quick. In this case, if there's a name clash between a builtin and a user-defined function, the interpreter defaults to the builtin.

So, for this example,

```
D,main,@,€f
D,f,@,5+

```

The  will actually call the `f` builtin (prime factors), not the function `f` (add 5).

If the builtin isn't defined however, such as `g`, it will use the function instead. Therefore, you can save 2 bytes per helper function call like

```
D,main,@,€g
D,g,@,5+

```

The undefined builtins are `I`, `K`, `Y`, `Z`, `g`, `k`, `l`, `u` and `w`, so name your helper functions these first, then move onto having to use braces if you have more than 9 helpers
> 7 votes

# Answer
Always use `D` Loop when you use `W` if you want to execute once and go to start of the loop if the condition is 1. This will prevent from duplicating the code.
> 5 votes

# Answer
# Use `&` to swap variables.

This

```
A:1
B:2
; Start of the Swap
C:A
A:B
B:C
; End of the Swap

```

Can be shortened to

```
A:1
B:2
; Start of the Swap
A&B
; End of the Swap

```

(This can be useful if you try to swap in loops)
> 0 votes

---
Tags: code-golf, tips
---


# Question
Title: AoCG2021 Day 25: Stitching maps together
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

Related to AoC2020 Day 20, Part 1. (This day is a dreaded one for many of you, I know :P)

*Obligatory final "but you're not Bubbler" explanation*.

---

As the train carries you to the destination, you've got some spare time. You open the travel booklet for the vacation spot, and its map is divided into nine pieces... in random order and orientation. Apparently you got a brain teaser version of the booklet or something.

The map pieces are represented as a square grid of zeros and ones, and they are rotated and/or flipped in a random orientation. The four edges of each map piece are the clues: if two pieces have a common edge pattern (one of the four sides), two pieces are stitched together on that edge.

If two pieces look like this:

```
Piece 1:
#..##
##...
#.#.#
.#.##
....#

Piece 2:
#.###
.....
.#...
##..#
.##..

```

The right edge of Piece 1 and the top edge of Piece 2 match; you can flip Piece 2 with respect to its main diagonal, and then join the two horizontally.

You can't decide the orientation of the whole map yet, but at least you can assemble the 3x3 map and tell which piece goes to the center. This is the objective of this challenge.

The edge patterns are all distinct; for any given pattern that appears in the input, there are either exactly two pieces (for interior edges) or one (for outer edges) with that pattern. Also, every interior edge pattern is asymmetric, so that you can uniquely join the edges together (modulo orientation as a whole).

**Input:** A list of nine square grids of zeros and ones, representing the nine map pieces; you can choose any other two distinct values (numbers, chars, or strings) for zeros and ones.

**Output:** The square grid that corresponds to the center piece (any orientation is fine), or its index (0- or 1-based) in the input.

Standard rules apply. The shortest code in bytes wins.

## Test case

Uses `#`s and `.`s.

```
Input:
.###.#
#####.
..#..#
#..##.
.#.###
..####

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

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

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

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

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

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

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

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

Answer: 2nd-to-last piece (8th with 1-indexing)

```

# Answer
> 6 votes
# Charcoal, 51 bytes

```
Ｆ⁹«≔⟦⟧θＷＳ⊞θκ⊞υ⁺Ｅ²⭆θ§μ±κＥ²§θ±κ»ＩΦ⁹⬤§υι⊙υ∧⁻ιξ∨№νλ№ν⮌λ

```

Try it online! Link is to verbose version of code. Outputs the 0-indexed index of the of the centre piece. Explanation:

```
Ｆ⁹«

```

Loop over the 9 pieces.

```
≔⟦⟧θＷＳ⊞θκ

```

Input the piece.

```
⊞υ⁺Ｅ²⭆θ§μ±κＥ²§θ±κ

```

Extract the four edges.

```
»ＩΦ⁹⬤§υι⊙υ∧⁻ιξ∨№νλ№ν⮌λ

```

Output the index of the piece whose (possibly reversed) edges all appear on other pieces.

# Answer
> 3 votes
# TypeScript Types, 738 bytes

```
//@ts-ignore
type a<A>=A extends[0,...infer B]?B:[];type b<C,P=0>=[C]extends[P]?C:b<C|c<C>|e<C>,C>;type c<T,X=[]>=T extends[...infer T,infer A]?c<T,[...X,A]>:X;type d<T,K=keyof T>=T extends T?keyof T extends K?T:never:0;type e<G>={[X in keyof G]:G[X]extends infer R?{[Y in keyof R]:G[Y][X]}:0};type f<g,h,i=g,j=h>=[g]extends[never]?Extract<h,[{},[...d<h[1]>,0],[...d<h[2]>,0]]>[0]:i extends i?b<i>extends infer k?k extends k?j extends j?(j[0][0]extends c<k>[0]?[[...j[1],0],j[2]]:c<j[0]>[0]extends k[0]?[a<j[1]>,j[2]]:e<j[0]>[0]extends c<e<k>>[0]?[j[1],[...j[2],0]]:c<e<j[0]>>[0]extends e<k>[0]?[j[1],a<j[2]>]:never)extends infer l?l extends l?f<Exclude<g,i>,h|[k,...l]>:0:0:0:0:0:0;type M<P>=f<Exclude<P[number],P[0]>,[P[0],[0,0],[0,0]]>

```

Try It Online!

## Ungolfed / Explanation

```
type DecNat<A> = A extends [0, ...infer B] ? B : []

// Get all orientations of a square by repeatedly reflecting Cur
type Orientations<Cur, Prev=0> =
  // If Cur == Prev,
  [Cur] extends [Prev]
    // Return Cur, which must include all orientations
    ? Cur
    // Otherwise, set Prev to Cur and add to Cur its reflection over the lines Y=0 and X=Y
    : Orientations<Cur | Reverse<Cur> | TransposeSquare<Cur>, Cur>

type Reverse<T, X=[]> = T extends [...infer T, infer A] ? Reverse<T, [...X, A]> : X

// Filter a union of tuples for those with the smallest length
type Shortest<T, K=keyof T> = T extends T ? keyof T extends K ? T : never : 0

// e.g. [[1, 2], [3, 4]] to [[1, 3], [2, 4]]
type TransposeSquare<Grid> = {
  [X in keyof Grid]: Grid[X] extends infer Row ? {
    [Y in keyof Row]: Grid[Y][X]
  } : 0
}

type Assemble<
  // A union of 2d grids of 0s and 1s
  RemainingPieces,
  // A union of map entries of the form [Piece, X, Y], where X and Y are Nats
  CurrentMap,
  /* aliases for mapping */
  CurrentPiece = RemainingPieces,
  MapEntry = CurrentMap
> =
  // If there are no more remaining pieces,
  [RemainingPieces] extends [never]
    // Return the center piece (assumes 3x3)
    ? Extract<CurrentMap, [{}, [...Shortest<CurrentMap[1]>, 0], [...Shortest<CurrentMap[2]>, 0]]>[0]
    : (
      // Map over RemainingPieces, binding CurrentPiece
      CurrentPiece extends CurrentPiece ?
        // Map over the orientations of CurrentPiece, binding OrientedPiece
        Orientations<CurrentPiece> extends infer OrientedPiece ? OrientedPiece extends OrientedPiece ?
          // Map over CurrentMap, binding MapEntry
          MapEntry extends MapEntry ?
            // Check each relative position
            (
              // If the top edge of MapEntry matches the bottom edge of OrientedPiece
              MapEntry[0][0] extends Reverse<OrientedPiece>[0]
                // [X + 1, Y]
                ? [[...MapEntry[1], 0], MapEntry[2]]
              // If the bottom edge of MapEntry matches the top edge of OrientedPiece
              : Reverse<MapEntry[0]>[0] extends OrientedPiece[0]
                // [X - 1, Y]
                ? [DecNat<MapEntry[1]>, MapEntry[2]]
              // If the left edge of MapEntry matches the right edge of OrientedPiece
              : TransposeSquare<MapEntry[0]>[0] extends Reverse<TransposeSquare<OrientedPiece>>[0]
                // [X, Y + 1]
                ? [MapEntry[1], [...MapEntry[2], 0]]
              // If the right edge of MapEntry matches the left edge of OrientedPiece
              : Reverse<TransposeSquare<MapEntry[0]>>[0] extends TransposeSquare<OrientedPiece>[0]
                // [X, Y - 1]
                ? [MapEntry[1], DecNat<MapEntry[2]>]
              : never
            // Bind the above to Position, and if it's not never,
            ) extends infer Position ? Position extends Position ?
              // Recurse:
              Assemble<
                // Remove CurrentPiece from RemainingPieces
                Exclude<RemainingPieces, CurrentPiece>,
                // Add OrientedPiece to CurrentMap at Position
                CurrentMap | [OrientedPiece, ...Position]
              >
      // An excessive number of unreachable states
      : 0 : 0 : 0 : 0 : 0 : 0
    )

type Main<Pieces> =
  // Start the map with Pieces[0] as (2, 2), so that coordinates always stay non-negative for 3x3 grids
  Assemble<
    Exclude<Pieces[number], Pieces[0]>,
    [Pieces[0], [0,0], [0,0]]
  >

```

# Answer
> 2 votes
# Pari/GP, 114 bytes

```
a->l=[[m[1,],m[#m,],m[,1]~,m[,#m]~]|m<-a];[i|i<-[1..#a],vecsum([#[1|f<-concat(l),e==f||e==Vecrev(f)]|e<-l[i]])==8]

```

Try it online!

A port of @Neil's answer.

# Answer
> 2 votes
# 05AB1E (legacy), 20 bytes

```
ε4F¬søí}\)}D€íå4ôPƶà

```

Port of *@Neil*'s Charcoal answer.

Takes the input-pieces as a list of lines, so the input is a list of list of strings. Outputs the 1-based index of the center piece. (Could alternatively output the 0-based index by replacing the `ƶà` with `1k`.)

Try it online.

Uses the legacy version of 05AB1E, because the zip/transpose builtin `ø` works on list of strings. In the new version of 05AB1E, this would have been 21 bytes by using the `ÅΔ` (get the index of the first truthy result), by taking the input-pieces as matrices of 0s/1s: Try it online (the header transforms the input).

**Explanation:**

```
ε           # Map over the pieces of the input-list:
 4F         #  Loop 4 times:
   ¬        #   Get the first row (without popping the list of lines)
    s       #   Swap so the piece is at the top again
     øí     #   Rotate it once clockwise:
     ø      #   Zip/transpose; swapping rows/columns
      í     #   Reverse each line
  }\        #  After the loop: discard the matrix
    )       #  Wrap the four edges in a list
}D          # After the map: duplicate the list of edges
  €í        # Reverse each edge in the copy
    å       # Check for each if it's in the list of edges
            # (which unfortunately flattens the entire list)
     4ô     # So split it into parts of size 4 again
       P    # Check for each if all four were truthy by taking the product
        ƶ   #  Multiply each 0/1 by its 1-based index
         à  #  Extract the maximum of this list
            # OR:
        1k  #  Get the 0-based index of the first truthy result (1)
            # (after which this index is output implicitly as result)

```

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

```
Pick[#,Total[Outer[Boole[#==#2||#==Reverse@#2]&,e={#[[1]],Last@#,First/@#,Last/@#}&/@#,e,2],{2,4}],8]&

```

Try it online!

A port of @Neil's answer.

# Answer
> 1 votes
# Python3, 182 bytes:

```
r=range
e=lambda s:[s[0],s[-1],[*(j:=[*zip(*s)])[0]],[*j[-1]]]
lambda b:[i for i in r(len(b))if all(any(j in(h:=e(b[y]))or j[::-1]in h for y in r(len(b))if y!=i)for j in e(b[i]))][0]

```

Try it online!

---
Tags: code-golf, grid, puzzle-solver, tiling
---


# Question
Title: AoCG2021 Day 24: Is the bus company cheating?
Part of **Advent of Code Golf 2021** event. See the linked meta post for details.

Related to AoC2020 Day 13, Part 2.

Why Bubbler isn't posting this; Why Riker isn't posting this

---

A shuttle bus service runs between the sea port (where you are) to the airport (where you need to go). Each bus has an ID number that also indicates how often the bus leaves for the airport - more precisely, the number of minutes between the departure of two consecutive buses of that ID. Every bus departed at the same time some time in the past at the timestamp of zero.

The shuttle company is running a contest: one gold coin for anyone that can find the earliest timestamp such that the first bus ID departs at that time and each subsequent listed bus ID departs at that subsequent minute.

The list of bus IDs looks like this:

```
7,13,x,x,59,x,31,19

```

where `x` means "don't care". So the objective here is to find the timestamp `t` where:

* Bus 7 departs at `t`.
* Bus 13 departs at `t+1`.
* Bus 59 departs at `t+4`.
* Bus 31 departs at `t+6`.
* Bus 19 departs at `t+7`.

The earliest timestamp `t` for this list is 1068781.

However, you suspect that the company won't want to give out any gold coins, because sometimes the list looks like this:

```
7,7

```

which is obviously impossible - Bus 7 cannot depart at `t` *and* `t+1` for any `t`.

Given the list of Bus IDs, determine if you can earn a gold coin or not.

**Input:** The list of bus IDs, possibly with some holes. A bus ID is always positive. A hole can be represented using any value that is not a positive integer (e.g. 0, -1, `"x"`); alternatively, you may represent holes by `1`, since they have the same effect (a `1` can always go anywhere). The list is guaranteed to be non-empty.

**Output:** A value representing the answer. You can choose to

* output truthy/falsy using your language's convention (swapping is allowed), or
* use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

The test cases use 0 for the holes in the list.

Truthy:

```
[7, 13, 0, 0, 59, 0, 31, 19]
[1, 2, 3, 4, 5]
[0]
[999]
[1, 3, 5, 7, 9, 11, 13, 15]

```

Falsey:

```
[7, 7]
[3, 1, 4, 1, 5, 9, 2]
[4, 0, 4]

```

# Answer
> 7 votes
# Pari/GP, 45 bytes

```
a->i=1;iferr(chinese([Mod(i--,b)|b<-a])',e,1)

```

Try it online!

Taking holes as 1.

Tries applying the Chinese remainder theorem built-in. If it throws an error, the bus company is cheating.

# Answer
> 4 votes
# Wolfram Language (Mathematica), ~~42~~ ~~38~~ 37 bytes

```
Head@ChineseRemainder[i=0;i++&/@#,#]&

```

Try it online!

Input holes as `1`. Returns `Integer` for truthy, and `ChineseRemainder` for falsy.

Another built-in. `ChineseRemainder` returns unevaluated if impossible (an integer if possible), so checking the head collapses these into two fixed values.

---

Slightly less boring (**43 bytes**):

```
Sum[Mod[j--,],{,i=0;#},{,j=i++;GCD[,#]}]<1&

```

Try it online!

Input holes as `1` or `-1`. Same approach as Neil's Charcoal answer.

# Answer
> 4 votes
# Jelly, 8 bytes

```
P+€TọµẠƇ

```

Try it online!

Outputs an empty list for falsy.

```
P        Product
 +€      Foreach, added to
   T     0...input length
    ọ    Number of times each divides each - 0 for falsy
     µẠƇ Filter by all truthy

```

# Answer
> 3 votes
# JavaScript (Node.js), 56 bytes

```
a=>eval("for(i=1+a.join``;a.some(n=>++x%n,x=i--)*i;);i")

```

Try it online!

Use `0` for a hole. Too slow for most testcases.

Simple idea:

```
for t := (large enough number) domnto 0 do
    if (t is valid) then return true
return false

```

Although \\$\prod a\_i\\$ would be large enough. Calculating the product is a bit longer than just concat them.

---

# JavaScript, 62 bytes

```
a=>a.some(o=(t,i)=>(g=j=>j&&(t%j?o:o[j]??=i%j)-i%j|g(j-1))(t))

```

Use *hole* for a *hole*. A faster version.

---

# JavaScript (Node.js), 65 bytes

```
a=>a.some((x,i)=>a.some(g=(y,j,_,z=x)=>z%y?g(z%y,j,a,y):(i-j)%y))

```

Try it online!

Use *hole* for a *hole*. The fast version in polynomial time complexity.

# Answer
> 3 votes
# Charcoal, 23 bytes

```
⬤θ⬤θ⬤…·²ι∨∨﹪ιν﹪λν¬﹪⁻κμν

```

Try it online! Link is to verbose version of code. Accepts `-1` as a hole. Outputs a Charcoal boolean, i.e. `-` for possible, nothing for impossible. Explanation: Any factor common to two of the elements must also divide the difference in their indices, otherwise the application of the Chinese Remainder Theorem would fail at that point.

```
 θ                      Input array
⬤                       All elements satisfy
   θ                    Input array
  ⬤                     All elements satisfy
     …·                 Inclusive range
       ²                From literal integer `2`
        ι               To outer value
    ⬤                   All elements satisfy
             ν          Potential factor
           ﹪            Does not divide
            ι           Outer value
          ∨             Logical Or
                ν       Potential factor
              ﹪         Does not divide
                ν       Inner value
         ∨              Logical Or
                      ν Potential factor
                 ¬﹪     Divides
                    κ   Outer index
                   ⁻    Minus
                     μ  Inner index
                        Implicitly print

```

# Answer
> 3 votes
# Haskell, ~~65~~ 52 bytes

```
f l=or[all(==0)$zipWith mod[t..]l|t<-[0..product l]]

```

Try it Online!

Uses 1 for a hole.

-13 bytes thanks to xnor

# Answer
> 3 votes
# TypeScript Types, 332 bytes

```
//@ts-ignore
type a<T,N=[],U=`${T}`>=U extends`${N["length"]}`?N:a<T,[...N,0]>;type b<A,B>=A extends[...B,...infer X]?b<X,B>:A;type c<A,B>=[]extends A|B?Exclude<A|B,[]>:c<B,b<A,B>>;type M<T,X={[K in keyof T]:[a<T[K]>,a<K>]}[number],Y=X>=0 extends(X extends X?Y extends Y?b<X[1],c<X[0],Y[0]>>extends b<Y[1],c<X[0],Y[0]>>?1:0:0:0)?0:1

```

Represents holes with `1`s.

Try It Online!

## Ungolfed / Explanation

I suspect this just applies the Chinese Remainder Theorem, but I haven't looked into it.

```
// Convert a number literal or a string literal representing a number to a `Nat`
type NumOrStrNumToNat<T, N=[], U=`${T}`> = U extends `${N["length"]}` ? N : NumOrStrNumToNat<T, [...N, 0]>

type ModNat<A, B> = A extends [...B, ...infer X] ? ModNat<X, B> : A

// Calculate the GCD of two `Nat`s using the Euclidean algorithm
type GcdNat<A, B> = [] extends A | B ? Exclude<A | B, []> : GcdNat<B, ModNat<A, B>>

type Main<
  T,
  // Convert an e.g. T of [1,5,3] to [Nat(1), Nat(0)] | [Nat(5), Nat(1)] | [Nat(3), Nat(1)]
  X = { [K in keyof T]: [NumOrStrNumToNat<T[K]>, NumOrStrNumToNat<K>] }[number],
  Y = X
> =
  // Return 0 if any of the following return 0
  0 extends (
    // Map over X cross Y
    X extends X ? Y extends Y ?
      // Return 1 if X[1] and Y[1] are equal modulo the GCD of X[0] and Y[0]
      ModNat<X[1], GcdNat<X[0], Y[0]>> extends ModNat<Y[1], GcdNat<X[0], Y[0]>> ? 1 : 0
    : 0 : 0
  ) ? 0 : 1

```

# Answer
> 2 votes
# Vyxal, 8 bytes

```
Π'?ẏ+?ḊA

```

Try it Online!

Outputs an empty list as falsy and a list with items as truthy, taking holes as 1.

```
Π        # Absolute value of product
 '       # Range 1...n filtered by
  ?ẏ+    # Add 0...input length to that
      ḊA # All divisible by
     ?   # Input

```

# Answer
> 2 votes
# 05AB1E, 9 bytes

```
PLʒ∞<+IÖP

```

Port of *@emanresuA*'s Vyxal answer, also taking `1` as holes and outputting an empty list for falsey.

Try it online or verify all test cases (uses a find\_first  instead of filter `ʒ` to speed the test suite up).

**Explanation:**

```
P         # Take the product of the (implicit) input-list
 L        # Pop and push a list in the range [1,product(innput)]
  ʒ       # Filter this list by:
   ∞      #  Push an infinite positive list: [1,2,3,...]
    <     #  Decrease each by 1: [0,1,2,...]
     +    #  Add the current integer to it: [y,y+1,y+2,...]
      IÖ  #  Check if the first input amount of values are divisible by the input-values
          #  at the same positions (it'll transform the list into the smallest of the
          #  two, causing the infinite list to shrink to the input-size)
        P #  Check if all are truthy by taking the product
          # (after which the filtered list is output implicitly)

```

# Answer
> 1 votes
# Python3, 88 bytes

```
lambda L,t=1:t>lcm(*L)or any((t-i)%b for i,b in enumerate(L))*f(L,t+1)
from math import*
```

Attempt This Online!

Uses 1s as holes. Returns 0 (falsy) if possible, and 1 (truthy) if impossible.

Some test cases cannot be completed due to memory limit with recursion. The iterative version however can finish and gives the correct results: Attempt This Online!

This is a bruteforce search for all numbers `t` between 1 and the LCM (least common multiple) of all bus IDs. If we find a `t` that has the correct remainders when divided by all bus IDs `b`: `(t-i) % b == 0` then the bus schedule is possible.

---
Tags: code-golf, decision-problem, number-theory
---


title: Tips for golfing in VB.net

text:
# Question
Title: Tips for golfing in VB.net
Any general tips for golfing in VB.net?

This, similar to Pascal, is a very rarely used language, thus having very few resources online

Visual Basic.NET (VB.NET) is a multi-paradigm, managed, type-safe, object-oriented computer programming language. Along with C# and F#, it is one of the main languages targeting the .NET Framework. VB.NET can be viewed as an evolution of Microsoft's Visual Basic 6 (VB6) but implemented on the Microsoft.NET Framework.

(Quoted from https://stackoverflow.com/questions/tagged/vb.net)

Please post each tip as a separate answer

# Answer
> 2 votes
If there is no parameters, you can remove the '()' when you call a function.

```
Console.ReadLine().Split()
Console.ReadLine.Split

```

# Answer
> 0 votes
You don't have to test booleans, you can test integers, it's true if not 0.

```
if(a<>0,do this,do that)
if(a,do this, do that)

```

---
Tags: code-golf, tips
---


title: Tips for golfing in Visual Basic .NET

text:
# Question
Title: Tips for golfing in Visual Basic .NET
## This page is not for Visual Basic Tips

Visual Basic .NET (VB.NET) is an multi-paradigm dialect of that was developed and released by Microsoft in 2002 as a replacement for Visual Basic. The current version of VB.Net as of Feb 2018 is Visual Basic .NET 15.0.

Unlike Visual Basic (VB), Visual Basic .NET (VB.NET) is fully integrated with the Microsoft .NET Framework giving it access to a far wider range of classes to access. Additionally, the bit width of integers and longs in VB.NET are `32` and `64` bits, respectively - twice that available to VB.

> Some helpful links

# Answer
> 2 votes
# `Dim` Variables implicitly as variants

VB.NET is capable of assuming object type at compile time - with numerics being dimmed into 32-bit spaces this means that

```
Module M
Sub Main
Dim i As Byte
Dim j As Short
Dim k As Integer
Dim l As Long
For i=128To 2^8-1 Step 64
For j=2^7*i To 2^15-1 Step 64^2
For k=2^16*j To 2^31-1 Step 2^24
For l=2^31*k To 2^62-1 Step 2^48
Console.Write(i & j & k & l)
Next
Next
Next
Next
End Sub
End Module

```

Try it online! (266 bytes)

May be trimmed down by `dim`ming `i`, `j`, `k` as variants, (note that because the default numeric type of a variant is a 32 Bit `Integer` `l` must still be `dim`med as a `Long` as it shall hold a 64 bit value)

```
Module M
Sub Main
Dim i,j,k,l As Long
For i=128To 2^8-1 Step 64
For j=2^7*i To 2^15-1 Step 64^2
For k=2^16*j To 2^31-1 Step 2^24
For l=2^31*k To 2^62-1 Step 2^48
Console.Write(i &j &k &l)
Next
Next
Next
Next
End Sub
End Module

```

Try it online! (226 bytes)

or even further to 218 bytes by combining `Next` statements

```
Module M
Sub Main
Dim i,j,k,l As Long
For i=128To 2^8-1 Step 64
For j=2^7*i To 2^15-1 Step 64^2
For k=2^16*j To 2^31-1 Step 8^8
For l=2^31*k To 2^62-1 Step 2^48
Console.Write(i &j &k &l)
Next l,k,j,i
End Sub
End Module

```

Try it online! (218 bytes) For a total savings of 40 bytes without impacting the output.

# Answer
> 2 votes
# Combine `Dim` Statements

The VB6 command

```
Dim i As Double
Dim j As Double
Dim k as Double
Dim l As Double

```

Can be rewritten as

```
Dim i,j,k,l as Double

```

Note that this is dissimilar from VB6 where only `l` would be defined as a double and `i,j,k` would be defined as variants.

# Answer
> 2 votes
# `Imports` keyword

You can use the `Imports` keyword in order to save bytes when using multiple class methods or a class method multiple times

## 92 bytes

```
module e
sub main
console.write(console.readline)
console.writeline("hi")
end sub
end module

```

## 91 bytes

```
imports system.console
module e
sub main
write(readline)
writeline("hi")
end sub
end module

```

---
Tags: code-golf, tips, basic
---


title: Self-unshuffling strings

text:
# Question
Title: Self-unshuffling strings
To shuffle a string \\$s\\$, Alice applies the following algorithm:

* She takes the ASCII code of each character, e.g. `"GOLF"`\\$\[ 71, 79, 76, 70 \]\\$
* She sorts this list from lowest to highest: \\$\[ 70, 71, 76, 79 \]\\$
* She reduces each value modulo the length of the string (4 in this case), leading to the list \\$A = \[ 2, 3, 0, 3 \]\\$
* For each character at position \\$n\\$ (0-indexed) in the original string, she exchanges the \\$n\\$-th character with the \\$A\[n\]\\$-th character:
    + exchange \\$s\[0\]\\$ with \\$s\[2\]\\$: `"GOLF"` is turned into `"LOGF"`
    + exchange \\$s\[1\]\\$ with \\$s\[3\]\\$: `"LOGF"` is turned into `"LFGO"`
    + exchange \\$s\[2\]\\$ with \\$s\[0\]\\$: `"LFGO"` is turned into `"GFLO"`
    + exchange \\$s\[3\]\\$ with \\$s\[3\]\\$: this one doesn't change anything

She then sends the shuffled string `"GFLO"` to Bob.

## Task

Your task is to help Bob understand Alice's message by applying the reverse algorithm: given a shuffled string as input, output the original string.

The input string is guaranteed to contain only printable ASCII characters (codes 32 to 126).

This is , so the shortest answer wins.

## Test cases

**Input:**

```
AAA
GFLO
ron'llckR'o
Br b,!mn oGognooid
eAies a.turel vee.st hnrw .v

```

**Output:**

```
AAA
GOLF
Rock'n'roll
Good morning, Bob!
As we travel the universe...

```

# Answer
> 7 votes
# MATL, 19 bytes

```
tStn\Q!tfhP!"t@)@P(

```

Try it online! Or verify all test cases.

### Explanation

The reverse algorithm is the same as the direct one just applying the swapping steps in reverse order.

```
t       % Input (implicit): string s of length N (row vector of chars of size 1×N)
S       % Sort (by ASCII codes)
tn      % Duplicate, number of elements: gives N
\       % Modulo (of ASCII codes), element-wise. Gives a 1×N numeric vector
Q       % Add 1 (because MATL uses 1-based indexing)
!       % Transpose into a column vector, of size N×1
tf      % Duplicate, find. Gives the N×1 column vector [1; 2; ...; N]
h       % Concatenate horizontally. Gives an N×2 matrix
P       % Flip vertically (for N=1 flips horizontally, but that still works)
!       % Transpose into a 2×N matrix
!"      % For each column
  t     %   Duplicate the (partially processed) string: (*)
  @     %   Push current column: 2×1 vector of the form [s(k); k]: (**)
  )     %   Read elements (**) from string (*). Gives 2×1 char vector: (***)
  @P    %   Push current column, flip: gives [k; s(k)]: (****)
  (     %   Write (***) into (*) at positions (****)
        % End (implicit)
        % Display (implicit)

```

# Answer
> 4 votes
# Charcoal, 47 bytes

```
≔⪪Ｓ¹θＷ⌊⁻θυＦ№θι⊞υιＷυ«≔℅⊟υι≔§θιη§≔θι§θＬυ§≔θＬυη»↑θ

```

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

```
≔⪪Ｓ¹θ

```

Split the input string into characters.

```
Ｗ⌊⁻θυＦ№θι⊞υι

```

Sort them in ascending order.

```
Ｗυ«

```

Process the sorted characters.

```
≔℅⊟υι

```

Get the ASCII code of the next character in reverse order.

```
≔§θιη§≔θι§θＬυ§≔θＬυη

```

Swap the character at the current index with the character at that position (cyclically reduced modulo the length of the string).

```
»↑θ

```

Output the final character array vertically so it prints as a string.

# Answer
> 4 votes
# , 34 32 31 bytes

```
<(C.>)/@,~i.@#;&~./@,.#|3 u:/:~

```

Try it online!

Uses Luis Mendo's insight "The reverse algorithm is the same as the direct one just applying the swapping steps in reverse order."

After that, we turn the problem into a single fold of all the swaps, using J's "Permute" verb `C.`, which can implement swaps directly. The only hiccup is that it doesn't allow self swaps, so we have to turn cases like `3 3 C. 'GOLF'` into `3 C. 'GOLF'`, which we do by call unique `&~.` while creating the swap pair.

# Answer
> 3 votes
# , 104 bytes

```
function(s){i=sort(v<-utf8ToInt(s))%%(n=nchar(s))+1
for(j in n:1)v[rev(w)]=v[w<-c(j,i[j])]
intToUtf8(v)}

```

Try it online!

# Answer
> 2 votes
# Scala, 101 92 bytes

```
s=>(s.sorted.map(_%s.size).zipWithIndex:\s){case((c,i),b)=>b.updated(c,b(i))updated(i,b(c))}

```

Saved 9 bytes thanks to @user.

Straightforward monadic-style implementation:

* `(s.sorted.map(_%s.size).zipWithIndex:\s)` creates the array "`A`" and traverses its elements (incl. corresponding index) from right to left via folding (`:\` = `foldRight`, accumulator initialized by input string `s`)
* `{case((c,i),b)=>b.updated(c,b(i))updated(i,b(c))}` updates the accumulator value `b` by swapping `b(i)` and `b(c)`. This part is quite verbose, since there is no `b.swap(c,i)` built-in.

Try it online!

# Answer
> 2 votes
# Python3, 155 bytes:

```
def g(s,x,l):
 for i in range(l):h=s[(j:=(l-1-i))];s[j]=s[x[j]];s[x[j]]=h;
def f(s):
 s=[*s];g(s,[ord(i)%(t:=len(s))for i in sorted(s)],t);return''.join(s)

```

Try it online!

# Answer
> 2 votes
# Python 3, 143 bytes

```
def u(i):
 m=len(i);p=list;i=p(i);a=[x%m for x in sorted(p(map(ord,i)))]
 for l in range(1-m,1):i[-l],i[a[-l]]=i[a[-l]],i[-l]
 return''.join(i)

```

I found it easiest to transform the input to a list and then back again, but I wouldn't be surprised if there is a more compact way to accomplish this.

Try it online!

# Answer
> 1 votes
# Vyxal, 30 bytes

```
:C₌sL:‹£%Ṙ(:¥n"İn¥"$Z÷→÷Ȧ←÷Ȧ&‹

```

Try it Online!

What a mess of 30 bytes. Probably gonna be outgolfed by better stack control.

## Explained

```
:C₌sL:‹£%Ṙ(:¥n"İn¥"$Z÷→÷Ȧ←÷Ȧ&‹
:                              # Push two copies of the input string
 C                             # and get the character code of each letter in the second copy
  ₌sL                          # push that sorted and it's length (parallel apply)
     :‹£                       # place the length of the string - 1 into the register - this will keep track of the nth character we're getting
        %Ṙ                     # reverse the list of each character code modulo the length of the string - this gets us our modulo indices (A[n])
          (                    # for each index n in that list:
           :                   #   The top of the stack is the first copy of the input string from earlier - we want to preserve this because we're modifying it with assignment, so make another copy to extract characters from
            ¥n"İ               #  that string's (register)th and nth character
                n¥"            #  push the list [n, register]
                   $Z          #  and then push zipped([n, register], [(register)th char, nth char]) - this allows us to create a list of [index to assign, character to assign]
                     ÷→        #  Place the last pair into the ghost variable for a bit, as we need to focus on the first pair of assignment.
                       ÷Ȧ      #  string[n] = (register)th char
                         ←÷Ȧ   #  string[register] = nth char
                            &‹ #  Increment the register to swap the next character position.
                               # After all that, the final string is implicitly printed.

```

# Answer
> 1 votes
# Lua, ~~231~~ 220 bytes

```
s=...t={}s:gsub(".",load('table.insert(t,(...):byte())u=s.sub'))table.sort(t)for i=#t,1,-1 do a=t[i]%#t+1 i,j=math.min(a,i),math.max(a,i)s=u(s,1,i-1)..u(s,j,j)..u(s,i+1,j-1)..(i~=j and u(s,i,i)..u(s,j+1)or"")end print(s)

```

Try it online!

# Answer
> 1 votes
# Brachylog, 82 bytes

```
lL∧L⟦₅R⁰∧?oạ%ᵐ↙L;R⁰z↔I∧?g,I↰ˡ↙1c
g;R⁰z{[[X,[A,B]],R]∧(A R∧X∋↙B.∨B R∧X∋↙A.∨X∋↙R.)}ᵐ

```

Try it online!

I couldn't find any reasonable way to swap 2 elements by index in Brachylog, so the second line is a verbose and ugly implementation of that.

Since Brachylog is prolog based, I could have applied the transform forwards and let it calculate the inverse automatically, but it was easier to just reverse the list.

# Answer
> 1 votes
# 05AB1E, 16 bytes

```
Ç{Dg%ā<øRvDyèyRǝ

```

Try it online or verify all test cases.

The shuffle method described in the challenge description would be this:

```
Ç{Dg%ā<øvDyèyRǝ

```

Try it online or verify all test cases.

And the top program simply reverses the list of indices to unshuffle.

We can add a trailing `=` after the programs above to see the intermediate steps: try it online.

**Explanation:**

```
Ç          # Convert the (implicit) input to a list of codepoint-integers
 {         # Sort them from lowest to highest
  Dg       # Duplicate, pop and push the length
    %      # Modulo the codepoints by this length
     ā     # Push a list in the range [1,length] (without popping)
      <    # Decrease each by 1 to make the range [0,length)
       ø   # Create pairs of the two lists
        R  # Reverse this list of pairs
v          # Loop over each pair of indices `y` of this list:
 D         #  Duplicate the current string
           #  (which is the implicit input in the first iteration)
  yè       #  Pop one string, and get the character-pair at indices `y`
    yRǝ    #  Insert them at back in the string at the reversed indices-pair `y`
           # (after the loop, the resulting string is output implicitly)

```

The swapping portion is taken from my answer here.

# Answer
> 1 votes
# Ruby, 70 bytes

```
->s{r=0;s.bytes.sort.reverse.map{|c|s[c],s[r]=s[r-=1],s[c%=s.size]};s}

```

Try it online!

# Answer
> 1 votes
# K (ngn/k), ~~36~~ 34 bytes

```
{x{x[y]:x@|y;x}/|+(!#x;(#x)!x@<x)}

```

Try it online!

As with the other answers, applies the swaps in the opposite order.

* `(...;(#x)!x@<x)` mod the sorted ASCII character codes by the length of the input
* `(!#x;...)` generate indices from 0..len(input)
* `|+` transpose this pair of lists into a list of pairs, then reverse its order
* `x{...}/` set up a fold, seeded with `x` (the original input), and this list of pairs indicating the order of the swaps
    + `{x[y]:x@|y;x}` swap the pair of elements of this current iteration, returning the modified list

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


title: AoCG2021 Leftover: Recursive Combat

text:
# Question
Title: AoCG2021 Leftover: Recursive Combat
This challenge is one of the two challenges which were planned for Advent of Code Golf 2021, but didn't fit into the 25-day schedule.

Related to AoC2020 Day 22, Part 2.

---

Combat is a simple two-player card game played with a deck of cards. A unique positive integer is written on each card. The game proceeds as follows:

* Shuffle and split the cards so that each player has their own deck.
* For each round...
    + Both players draw their top card. The one with the higher-numbered card wins the round. The winner places both cards at the bottom of their own deck, so that the winner's card is above the other card.
* If a player owns all cards, the player wins.

**Recursive Combat** is a variant of Combat. The only difference is how to decide the winner of each round.

* Before either player deals a card, if there was a previous round in this game that had exactly the same cards in the same order in the same players' decks, the game instantly ends in a win for player 1. Previous rounds from other games are not considered. (This prevents infinite games of Recursive Combat.)
* Otherwise, this round's cards must be in a new configuration; the players begin the round by each drawing the top card of their deck as normal. If both players have at least as many cards remaining in their deck as the value of the card they just drew, the winner of the round is determined by playing a **new game of Recursive Combat**, where each player takes that many cards from the top of their own deck (excluding the cards drawn) to the "sub-game". When the sub-game ends, the cards are returned to the decks as they were before the sub-game, and the parent game proceeds like Combat: the winner of the sub-game (= the winner of the round) puts the two cards drawn at the bottom of their own deck, so that the winner's card is above the other card.
* Otherwise, at least one player must not have enough cards left in their deck to recurse; the winner of the round is the player with the higher-value card.

Note that the winner's card might have lower value than the other card in this version.

Let's call the two players Player 1 and Player 2. Given both player's decks at start, determine whether Player 1 will win the game of Recursive Combat or not.

Both decks are given as list of values written on each card. You can choose which side will be the top of the deck. It is guaranteed that both decks are non-empty and all numbers are unique positive integers.

For output, you can choose to

* output truthy/falsy using your language's convention (swapping is allowed), or
* use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Standard rules apply. The shortest code in bytes wins.

## Test cases

**P1 wins**

```
P1's deck, P2's deck (first number at the top)
[43, 19], [2, 29, 14] (by infinite loop prevention)
[10, 8, 2] [4, 3, 5, 6, 9, 1, 7]
[2, 1, 10, 8] [7, 6, 5, 3, 9, 4]
[2, 1, 7, 8, 9, 4, 5, 6] [10, 3]

```

**P2 wins**

```
P1's deck, P2's deck (first number at the top)
[9, 2, 6, 3, 1], [5, 8, 4, 7, 10]
[6, 2, 1, 8, 9, 4], [7, 3, 10, 5]
[4, 6, 2, 1, 3], [8, 10, 7, 9, 5]
[7, 4, 9, 2, 6, 1, 3], [10, 8, 5]

```

# Answer
# JavaScript, ~~146~~ ~~145~~ 134 bytes

```
c=d=>(d[[[A,B]=d,B]]^=Y=B[0])?(X=A[0])?d[w=A[X]+B[Y]?c(d.map(a=>a.slice(1,a[0]+1))):Y>X|0].push(d[w].shift(),d[w^1].shift())&&c(d):1:0

```

Try it online!

Takes the decks as an array of arrays of integers, top first; this array will be modified. Returns 0 for player 1 winning, 1 for player 2 winning.

-12 from the original by removing `h` and instead reusing `d`, as well as a modification of an idea from tsh.

## Explanation

```
(d[[[A,B]=d,B]]^=Y=B[0])?…:0

```
* `A` and `B` are set to the decks of player 1 and 2, respectively.
* The default `toString` of arrays joins with commas, which is injective for arrays of integers, but not for arrays of arrays of integers – for example, it does not distinguish `[[1,2],[3]]` and `[[1],[2,3]]`. For that reason, `toString` is instead (implicitly) called on a new array, which lists the elements of A once and the elements of B twice. This distinguishes all possibilities because the numbers that appear twice must be from B while the numbers that appear once must be from A.
* Additional properties of `d` are used to keep track of which configurations of cards have been seen before.
    + Indexing with a new string finds `undefined`, which gets converted to 0 before the XOR makes it equal `B[0]`.
    + Indexing with a previously-seen string finds the previous value of `B[0]`, which is necessarily equal to the current value, thus the XOR changes it to 0. (Player 1 wins immediately.)
    + If `B` is empty, `B[0]` is `undefined`, which also gets converted to 0. The string has to be new, making the result 0. (Player 1 wins immediately.)
* Also, `Y` is set to Player 2's top card.

```
(X=A[0])?…:1

```
* `X` is set to Player 1's top card; Player 2 wins immediately if Player 1's deck is empty.

```
d[w=A[X]+B[Y]?c(d.map(a=>a.slice(1,a[0]+1))):Y>X|0]…

```
* `A[X]` and `B[Y]` check whether the players have enough cards for a recursive sub-game, yielding the value of the last card to be used if there are enough, or `undefined` if there are not enough. The sum is a positive integer (truthy) if both are positive integers, or `NaN` (falsy) if at least one is `undefined`.
* If there are enough cards, `c` is called to determine the winner of the recursive sub-game, using `slice` to extract the appropriate cards.
* Otherwise, `Y>X` determines the winner, and `|0` converts it to an integer, 0 or 1.
* `w` is set to the (0-indexed) winner.

```
d[w=…].push(d[w].shift(),d[w^1].shift())&&c(d)

```
* The two `shift`s take out the top cards of the winner and non-winner in that order, and `push` puts them on the bottom of the winner's deck.
* Finally, `c(d)` calls the function again to repeat the analysis.
> 4 votes

# Answer
# Charcoal, 114 bytes

```
⊞υ⟦⟧≔⟦✂θ⟧ηＷυ«≔№§υ±¹θε⊞§υ±¹✂θ¿›⬤θ∧κ›Ｌκ§κ⁰ε«⊞υ⟦⟧⊞η✂θＵＭθ✂κ¹⊕§κ⁰»«¿›⬤θκε≔‹§θ⁰§θ¹ε«≔∧⊟υ¬§θ⁰ε≔⊟ηθ»Ｆ²⊞§θε§§θ⁺λε⁰ＵＭθΦκν»»ε

```

Try it online! Link is to verbose version of code. Takes input as a pair of lists and outputs `-` if player 2 wins, nothing if player 1 wins. Explanation: Charcoal doesn't really do recursion, so here's an iterative approach.

```
⊞υ⟦⟧

```

Start tracking previously seen positions for the top-level game.

```
≔⟦✂θ⟧η

```

Create a dummy "calling game state" for the top-level game.

```
Ｗυ«

```

Repeat until all games have been resolved.

```
≔№§υ±¹θε

```

See whether this position has been seen in this game or not.

```
⊞§υ±¹✂θ

```

Save a (shallow) copy of this position to this game.

```
¿›⬤θ∧κ›Ｌκ§κ⁰ε«

```

If a recursive game is possible, then:

```
⊞υ⟦⟧

```

Start tracking previously seen positions for the sub-game.

```
⊞η✂θ

```

Save the calling game state for the sub-game.

```
ＵＭθ✂κ¹⊕§κ⁰

```

Create the state for the sub-game.

```
»«¿›⬤θκε

```

Otherwise, if this is a new position and both players still have cards, then...

```
≔‹§θ⁰§θ¹ε

```

... see who wins this position.

```
«≔∧⊟υ¬§θ⁰ε≔⊟ηθ»

```

Otherwise, remove the previously seen positions for this game, see whether Player 1 lost by running out of cards, and restore the calling game state.

```
Ｆ²⊞§θε§§θ⁺λε⁰

```

Append the top card of both the winner and loser to the winner's hand.

```
ＵＭθΦκν

```

And remove them from the top of both players' hands.

```
»»ε

```

Output whether Player 2 won.
> 2 votes

# Answer
# Wolfram Language (Mathematica), 127 bytes

```
f=##!={}&&Check[#&@@@#,#&@@#=={}]/.{c__}:>MapAt[#~Join~{c}[[{n,-n}]]&,Rest/@#,n=If[f@@Check[{##2}[[;;#]]&@@@#',0<c],2,1]]~f~##&

```

Try it online!

Input a list containing the decks in order, i.e. as `[{P1, P2}]`. Returns `False` if P1 wins, and `True` if P2 wins.

```
##&!={}&&                       check for a loop
Check[#&@@@#,                   attempt to take one card from each deck
  #&@@#=={}]                      if not possible, check which deck is empty
/.{c__}:>                       the current round's cards are c:
 MapAt[#~Join~{c}[[{n,-n}]]&,     append both cards in the correct order
   Rest/@#,                         to the winner's deck,
   n=If[                            deciding the winner by:
     f@@Check[{##2}[[;;#]]&@@@#',     attempt to play a subgame
       0<c],                            if not possible, the higher card
     2,1]                           bool -> player number
 ]~f~##                           recurse

```
> 2 votes

# Answer
# Python3, 264 bytes:

```
k=lambda x,y,a,b,h,r:([a,[y,x]+a][r],[[x,y]+b,b][r],h+[[a+[x],b+[y]]])
def f(a,b,h=[]):
 if[a,b]in h:return 1
 if not all([a,b]):return len(a)>0
 x,y=a.pop(),b.pop()
 if x<=len(a)and y<=len(b):return f(*k(x,y,a,b,h,f(a[-x:],b[-y:])))
 return f(*k(x,y,a,b,h,x>y))

```

Try it online!
> 2 votes

# Answer
# Scala, 150 bytes

```
(a,b,s)=>if(a.isEmpty)2 else if(b.isEmpty|s(a->b))1 else if(a(0)>b(0))f(a.tail:+a(0):+b(0),b.tail,s+(a->b)) else f(a.tail,b.tail:+b(0):+a(0),s+(a->b))

```

Try it on Scastie
> 1 votes

# Answer
# Python 3, 262 bytes

```
def r(a,b,h=[]):
    while 1:
        if h.count((a,b))or not b:return 1
        if not a:return 2
        h.append((a.copy(),b.copy()));c,d=a.pop(0),b.pop(0)
        if len(a)>=c and len(b)>=d:q=r(a[:c],b[:d]);a+=([],[c,d])[q];b+=([d,c],[])[q]
        else:a+=([c,d],[])[d>c];b+=([d,c],[])[c>d]

```

Takes the top of the deck as element 0 in the lists, and returns 1 for Player 1 winning, 0 for player 2 winning.

Try it online!
> 1 votes

---
Tags: code-golf, decision-problem, game, recursion
---


title: Square snowflake

text:
# Question
Title: Square snowflake
Produce this square snowflake.

```
XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX
XX   X   X   X   X   X   X   X   X   X   X   X   X   X   X   XX
X XXXX   XXXXX   XXXXX   XXXXX   XXXXX   XXXXX   XXXXX   XXXX X
  XX       X X   X X       X X   X X       X X   X X       XX
X X XXX XXXX       XXXX XXXX       XXXX XXXX       XXXX XXX X X
XXX XX   X X X   X X X   X X X   X X X   X X X   X X X   XX XXX
X   X XXXX XXX   XXX XXXXX XXX   XXX XXXXX XXX   XXX XXXX X   X
      XX               X X   X   X   X X               XX
X   X X XXX XXX XXX XXXX               XXXX XXX XXX XXX X X   X
XXX XXX XX   X   X   X X X   X   X   X X X   X   X   XX XXX XXX
X X X   X XXXX   XXXXX XXX XXX   XXX XXX XXXXX   XXXX X   X X X
  XXXXX   XX       X X   X X X   X X X   X X       XX   XXXXX
X X   X X X XXX XXXX   XXXXX       XXXXX   XXXX XXX X X X   X X
XXXX XX XXX XX   X X X X   X X   X X   X X X X   XX XXX XX XXXX
X       X   X XXXX XXX XX XXXX   XXXX XX XXX XXXX X   X       X
              XX                               XX
X       X   X X XXX XXX XXX XXX XXX XXX XXX XXX X X   X       X
XXXX XX XXX XXX XX   X   X   X   X   X   X   XX XXX XXX XX XXXX
X X   X X X X   X XXXX   XXXXX   XXXXX   XXXX X   X X X X   X X
  XXXXX   XXXXX   XX       X X   X X       XX   XXXXX   XXXXX
X X X   X X   X X X XXX XXXX       XXXX XXX X X X   X X   X X X
XXX XXX XXXX XX XXX XX   X X X   X X X   XX XXX XX XXXX XXX XXX
X   X X X       X   X XXXX XXX   XXX XXXX X   X       X X X   X
      XXXXX XXX       XX               XX       XXX XXXXX
X   X X   X X X X   X X XXX XXX XXX XXX X X   X X X X   X X   X
XXX XXXX XXXX   XXX XXX XX   X   X   XX XXX XXX   XXXX XXXX XXX
X X X       X X X X X   X XXXX   XXXX X   X X X X X       X X X
  XXXXX   XXXXX   XXXXX   XX       XX   XXXXX   XXXXX   XXXXX
X X   X   X   X X X   X X X XXX XXX X X X   X X X   X   X   X X
XXXX XXX XXX XX XXXX XX XXX XX   XX XXX XX XXXX XX XXX XXX XXXX
X               X       X   X XXX X   X       X               X
                              XXX
X               X       X   X XXX X   X       X               X
XXXX XXX XXX XX XXXX XX XXX XX   XX XXX XX XXXX XX XXX XXX XXXX
X X   X   X   X X X   X X X XXX XXX X X X   X X X   X   X   X X
  XXXXX   XXXXX   XXXXX   XX       XX   XXXXX   XXXXX   XXXXX
X X X       X X X X X   X XXXX   XXXX X   X X X X X       X X X
XXX XXXX XXXX   XXX XXX XX   X   X   XX XXX XXX   XXXX XXXX XXX
X   X X   X X X X   X X XXX XXX XXX XXX X X   X X X X   X X   X
      XXXXX XXX       XX               XX       XXX XXXXX
X   X X X       X   X XXXX XXX   XXX XXXX X   X       X X X   X
XXX XXX XXXX XX XXX XX   X X X   X X X   XX XXX XX XXXX XXX XXX
X X X   X X   X X X XXX XXXX       XXXX XXX X X X   X X   X X X
  XXXXX   XXXXX   XX       X X   X X       XX   XXXXX   XXXXX
X X   X X X X   X XXXX   XXXXX   XXXXX   XXXX X   X X X X   X X
XXXX XX XXX XXX XX   X   X   X   X   X   X   XX XXX XXX XX XXXX
X       X   X X XXX XXX XXX XXX XXX XXX XXX XXX X X   X       X
              XX                               XX
X       X   X XXXX XXX XX XXXX   XXXX XX XXX XXXX X   X       X
XXXX XX XXX XX   X X X X   X X   X X   X X X X   XX XXX XX XXXX
X X   X X X XXX XXXX   XXXXX       XXXXX   XXXX XXX X X X   X X
  XXXXX   XX       X X   X X X   X X X   X X       XX   XXXXX
X X X   X XXXX   XXXXX XXX XXX   XXX XXX XXXXX   XXXX X   X X X
XXX XXX XX   X   X   X X X   X   X   X X X   X   X   XX XXX XXX
X   X X XXX XXX XXX XXXX               XXXX XXX XXX XXX X X   X
      XX               X X   X   X   X X               XX
X   X XXXX XXX   XXX XXXXX XXX   XXX XXXXX XXX   XXX XXXX X   X
XXX XX   X X X   X X X   X X X   X X X   X X X   X X X   XX XXX
X X XXX XXXX       XXXX XXXX       XXXX XXXX       XXXX XXX X X
  XX       X X   X X       X X   X X       X X   X X       XX
X XXXX   XXXXX   XXXXX   XXXXX   XXXXX   XXXXX   XXXXX   XXXX X
XX   X   X   X   X   X   X   X   X   X   X   X   X   X   X   XX
XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX XXX

```

TIO link, and a more square spaced-out version.

**How it's made**

You start with a initial crystal (cell) at the center. Then, a new crystal is formed simultaneously at each empty space that touches exactly one existing crystal, looking at the 8 cells orthogonally or diagonally adjacent to it. Crystals remain indefinitely. Here is the snowflake after 3 steps, marking the crystals added at each step.

```
333 333
32   23
3 111 3
  101
3 111 3
32   23
333 333

```

We continue this for 31 steps, making a 63-by-63 snowflake with 1833 crystals.

This process is the Life-like (totalistic) cellular automaton B1/S012345678, also known as H-trees or Christmas Life.

**Output**

Output or print in any 2D array format with two distinct entries for crystal and empty space, or anything that displays as such. The grid must by exactly 63 by 63, that is having no wasted margin. It's fine to have trailing spaces for non-crystals or jagged arrays truncated to the last crystal in each row. A trailing newline is also OK.

Bit representations are not valid unless they display with two distinct symbols for the bits by default.

---

I also posted this challenge on Anarchy Golf. It requires a strict output format of the ASCII art above of `X`'s and spaces.

# Answer
# MATL, ~~21~~ 19 bytes

```
l31:"TTYat3Y6Z+1=Y|

```

**Try it online!**

### Explanation

```
l         % Push 1 (this is the initial 1×1 array)
31:"      % Do 31 times
  TTYa    %   Extend with a frame of zeros in 2D
  t       %   Duplicate
  3Y6     %   Push [1 1 1; 1 0 1; 1 1 1] (8-neighbourhood; predefined literal)
  Z+      %   2D convolution, maintaining size. This gives the number of active
          %   neighbours for each cell
  1=      %   Equal to 1? Element-wise
  Y|      %   Logical OR
          % End (implicit)
          % Display (implicit)

```
> 20 votes

# Answer
# APL (Dyalog Unicode), ~~31~~ ~~29~~ 27 bytes

```
(⊢∨1={≢⍸⍵}⌺3 3)⍣≡∘.×⍨32=⍳63

```

Try it online!

-4 bytes thanks to @ngn.

A full program that prints a boolean matrix.

### How it works

```
(⊢∨1={≢⍸⍵}⌺3 3)⍣≡∘.×⍨32=⍳63
                     32=⍳63  ⍝ A 63-length vector whose center element is 1
                             ⍝ and the rest is 0
                 ∘.×⍨  ⍝ Outer product self by ×, giving initial state of CA
(             )⍣≡  ⍝ Run the cellular automaton until it stabilizes...
     {≢⍸⍵}⌺3 3     ⍝ Count ones in 3-by-3 subgrids
   1=              ⍝ Test if the 3×3 subgrid has exactly one alive cell
 ⊢∨                ⍝ or the cell is already alive

```
> 10 votes

# Answer
# Python 2 with scipy, 105 bytes

```
from scipy.signal import*
A=[1],
K=1,1,1
exec"A=convolve2d(A,[K,(1,9,1),K]);A=(A>8)+(A==1)+0;"*31
print A

```

Try it online!

Use convolution to grow the array. The convolution kernel used is:

```
[[1, 1, 1]
 [1, 9, 1]
 [1, 1, 1]]

```

and the criteria for living cell is:

```
c >= 9 or c==1

```

aka when the cell is already living or when there is exactly 1 neighbor.

Note that NumPy by default only prints a summary of a large array, like so:

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

```

Thus, I have to call `numpy.set_printoptions` to force Numpy to prints the entire array. This part is not included in the byte count, since I dont't think it's relevant to the actual problem.

This 114 bytes function returns the array instead of printing it out, thus circumventing the print option problem.
> 9 votes

# Answer
# , 38 34 bytes

```
3 3(1 e.+/,4&{)@,;._3^:31*/~0=i:62

```

Try it online!

*-3 bytes thanks to ngn*

*-1 byte thanks to Bubbler*

Try it online!

Core ideas taken from Bubbler's elegant APL answer -- be sure to upvote him.

This was an experiment to see how close I could get using J, which lack's APL diamond operator and so is at a disadvantage.

Instead, J has SubArrays, which requires you to manually add the padding of zeros. I opted here to add all the padding at once, up front: a 125 x 125 matix of zeros with a 1 in the center.

After each iteration, we'll lose 2 from our dimension, so after 31 iterations we'll be down to 63 x 63, which is what we need.
> 7 votes

# Answer
# JavaScript (ES6),  ~~149 138 136~~  135 bytes

Returns a binary matrix.

```
f=k=>k>31?m:f(-~k,m=(k?m:a=[...Array(63)]).map((r=a,y)=>r.map((v,x)=>k?v|!~(g=d=>d--&&g(d)-~~(m[y+~-(d/3)]||0)[x-1+d%3])(9):x*y==961)))

```

Try it online!

### Commented

The same `map()` loops are used to initialize the 63x63 binary matrix `m[]` and to recursively update it. Doing a separate initialization of `m[]` before entering the recursion would cost more bytes.

```
f = k =>                         // f is a recursive function taking a counter k
  k > 31 ?                       // if k is greater than 31:
    m                            //   stop recursion and return m[]
  :                              // else:
    f(                           //   do a recursive call:
      -~k,                       //     increment k
      m = (                      //     update m[]
        k ? m                    //     if this is not the first iteration, use m[]
          : a = [...Array(63)]   //     otherwise, use a vector a[] of 63 entries
      ).map((r = a, y) =>        //     for each row r[] at position y, using a[]
                                 //     as a fallback for the first iteration:
        r.map((v, x) =>          //       for each value v at position x:
          k ?                    //         if this is not the first iteration:
            v | !~(              //           if v is already set, let it set
              g = d =>           //           or use the result of the recursive
                                 //           function g taking a direction d
              d-- &&             //             decrement d; stop if it's zero
              g(d) -             //             recursive call
              ~~(                //             subtract 1 if the cell at ...
                m[y + ~-(d / 3)] //               ... y + dy ...
                || 0             //
              )[x - 1 + d % 3]   //               ... and x + dx is set
            )(9)                 //           initial call to g with d = 9
          :                      //         else (first iteration):
            x * y == 961         //           set the cell iff x = y = 31 (because 31
                                 //           is prime, it's safe to test xy = 31²)
        )                        //       end of inner map()
      )                          //     end of outer map()
    )                            //   end of recursive call

```
> 6 votes

# Answer
# T-SQL, ~~330~~ ~~266~~ 232 bytes

This takes a long time to execute(reason: must be something wrong with the question).

-22 Bytes thanks to @RossPresser

```
SELECT top 3969' 'z,IDENTITY(INT,0,1)i,63x
INTO t FROM sys.messages
WHILE @@ROWCOUNT>0UPDATE
t SET z=1WHERE(SELECT SUM(1*z)FROM t x
WHERE(t.i/x-i/x)/2=0and(t.i%x-i%x)/2=0)=1or i=1984and''=z
SELECT string_agg(z,'')FROM t GROUP BY i/x

```

This will execute in Microsoft SQL Server 2017 or higher. Try it online on dbfiddle.uk; link is set to use markdown for output so you can see the whole snowflake.

Before execute press ctrl-t for output to text instead of grid. This takes 60 seconds to execute on my computer.
> 4 votes

# Answer
# Python 2, 125 bytes

```
s="%64c"%10
exec's*=63;s="".join(s[n][(s[n+3967:][:191]*3)[::64].strip()=="X":n!=2015]or"X"for n in range(4032));'*32
print s

```

Try it online!

This answer is by user "clock" based on hallvabo's solution, on the Anarchy Golf version of this challenge that I submitted. Note that output there is strict and is required to be exactly the picture of X's and spaces to STDOUT via a full program, with only an allowance for a trailing newline.

The most interesting part of this answer, in my opinion, is the concise construction `(s[n+3967:][:191]*3)[::64]` after `s*=63` to get the nine neighbors of the cell counting itself in a flat newline-joined string representing the grid. To check if there's exactly one `X` among them, `.strip()` is called to get rid of whitespace on either side, and the result is checked to equal just `"X"`.

It's interesting how simulating the steps on the string representation of the output directly (rather than an array of bits) not only saves on doing a conversion to characters later but also allows string-specific methods to be used in a golfy way.

Another neat trick, borrowed from hallvabo, is `"%64c"%10` used to initialize `s` to 63 spaces followed by a newline for a line of the initial empty grid. Using the `%c` format, which converts an ASCII value to a character, is shorter than `" "*63+"\n"` or `"%64s"%"\n"`.
> 4 votes

# Answer
# Wolfram Language (Mathematica) \+ my LifeFind package, 47 bytes

```
<<Life`
Last@CA[{{1}},31,Rule->"B1/S01234568"]&

```

There isn't any living cell with 7 living neighbors in the first 31 steps, so I can golf the rule by 1 byte: `B1/S012345678` -\> `B1/S01234568`.
> 4 votes

# Answer
# Charcoal, ~~38~~ 37 bytes

```
Ｊ³¹¦³¹XＦ³²«ＵＭＫＡXＦ⁶³Ｆ⁶³«Ｊκλ›⁼№ＫＭX¹⁼ＫＫX

```

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

```
Ｊ³¹¦³¹X

```

Output the `X` in the centre of the square.

```
Ｆ³²«

```

Grow the snowflake 31 times. (The last loop is just used for its side-effect of replacing the `-`s with `X`s.)

```
ＵＭＫＡX

```

Change all the `-`s to `X`s.

```
Ｆ⁶³Ｆ⁶³«

```

Iterate over the square.

```
Ｊκλ

```

Jump to each position in the square.

```
›⁼№ＫＭX¹⁼ＫＫX

```

If the cell does not yet have an `X` but it has one neighbouring `X` then print a `-`.
> 3 votes

# Answer
# 05AB1E, 31 bytes

```
1¸¸31F0δ.ø¬0*¸.øD2Fε0.øü3O}ø}Θ~

```

05AB1E and matrices are not a good combination.. :/

Outputs as a 63x63 matrix of 0s and 1s for spaces and crystals respectively.

Try it online. (The footer is to pretty-print it, feel free to remove it to see the actual result.)

**Explanation:**

```
1¸¸            # Start with a matrix containing 1: [[1]]
 31F           # Loop 31 times:
    0δ.ø       #  Surround each row with leading and trailing 0
               #   i.e. [[1,1,1],[1,1,1],[1,1,1]] → [[0,1,1,1,0],[0,1,1,1,0],[0,1,1,1,0]]
    ¬          #  Take the first row (without popping the matrix)
               #   → [0,1,1,1,0]
     0*        #  Multiply each value by 0
               #   → [0,0,0,0,0]
       ¸       #  Wrap it into a list
               #   → [[0,0,0,0,0]]
        .ø     #  And surround the matrix with that row of 0s
               #   i.e. [[0,0,0,0,0],[0,1,1,1,0],[0,1,1,1,0],[0,1,1,1,0],[0,0,0,0,0]]
    D          #  Duplicate it
     2F        #  Loop 2 times:
       ε       #   Map each row to:
        0.ø    #    Surround the row with leading and trailing 0
               #     i.e. [0,1,1,1,0] → [0,0,1,1,1,0,0]
           ü3  #    Create overlapping triplets
               #     → [[0,0,1],[0,1,1],[1,1,1],[1,1,0],[1,0,0]]
             O #    Sum each triplet
               #     → [1,2,3,2,1]
       }ø      #   After the map: transpose/zip; swapping rows/columns
               #    i.e. [[0,0,0,0,0],[1,2,3,2,1],[1,2,3,2,1],[1,2,3,2,1],[0,0,0,0,0]]
               #     → [[0,1,1,1,0],[0,2,2,2,0],[0,3,3,3,0],[0,2,2,2,0],[0,1,1,1,0]]
      }Θ       #  After the inner loop: check for each whether it's 1 (1 if 1; 0 otherwise)
               #   i.e. [[1,2,3,2,1],[2,4,6,4,2],[3,6,9,6,3],[2,4,6,4,2],[1,2,3,2,1]]
               #    → [[1,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,1]]
        ~      #  Take the bitwise-OR of the values at the same positions in the matrices
               #   → [[1,0,0,0,1],[0,1,1,1,0],[0,1,1,1,0],[0,1,1,1,0],[1,0,0,0,1]]
               # (after the loop, the resulting matrix is output implicitly)

```
> 3 votes

# Answer
# Jelly, ~~41~~ 34 bytes

```
ı*Ɱ5I;$Ṗ+)FċⱮẹ1ịƲ;
32×1ıWÇṛ¡’ÆiḞŒṬ

```

Try it online!

*-7 because to nobody's surprise there's two shorter ways to get \\$32+32i\\$ than `“ ‘Æị`, the symmetry of the neighborhood lets  golf to `I`, we can trade two `¤`s and a  for `)` and `$`,  exists, `œ|` is overkill, and selfing `ċⱮ` is outright superfluous*

This is an absolute mess that could probably be outdone easily by someone with any clue as to how to mimic others' convolution-based approach. Outputs a two-dimensional list of ones and zeros, which are conveniently translated to the example's Xs and spaces by the testing footer provided.

```
ı*Ɱ5I;$Ṗ+)FċⱮẹ1ịƲ;    Monadic helper link: grow a list of complex numbers
         )            For each number:
ı*Ɱ5                  raise the imaginary unit 1j to each power from 1 to 5,
    I;$               prepend the differences between its adjacent elements,
       Ṗ              remove the extra 1j,
        +             and add each to the number.
          F           Flatten the resulting list of lists,
               ịƲ     take the elements at indices
             ẹ1       which are indices of 1 in
           ċⱮ         the list of how many times each element occurs,
                 ;    and append the original list.

32×1ıWÇṛ¡’ÆiḞŒṬ    Niladic main link: generate the snowflake
32                 Set the argument to 32,
  ×1ı              then multiply it by 1+1j
     W             and wrap it in a singleton list.
      Ç ¡          Grow that a number of times equal to
       ṛ ’         the argument minus 1.
          ÆiḞ      Convert the complex numbers to pairs of integers,
             ŒṬ    and interpret the pairs as coordinates of 1s in a 2D array.

```
> 3 votes

# Answer
# PHP, 206 bytes

```
for($a[][]=1;++$n<32;){$b=$a;for($i=$n;$i>=-$n;$i--)for($j=$n;$j>=-$n;$j--){$a[$i][$j]=$a[$i][$j]&1;$c=0;for($k=2;--$k>-2;)for($l=2;--$l>-2;)if($k|$l)$c+=$b[$i+$k][$j+$l];1!=$c?:$a[$i][$j]=1;}}var_dump($a);

```

Try it online!

Well I'm getting used to horrible PHP answers :D don't blame the language, there are libs for matrixes.. displays an unordered array of 1 and 0, but with proper keys. change the first loop value (32) to generate any size snowflake..

24 bytes could have been saved by removing `$a[$i][$j]=$a[$i][$j]&1;` if we only needed the truthy values.
> 2 votes

# Answer
# Python 2, ~~146~~ 130 bytes

Prints a 2d-list of booleans.

```
R=range(63)
for i in R:m=[[i>0==(x*y-961)*0**m[y][x]*~-sum(sum(k[x+x%~x:x+2])for k in m[y+y%~y:y+2])for x in R]for y in R]
print m

```

Try it online!
> 2 votes

# Answer
# , ~~144~~ ~~122~~ 118 bytes

```
m=matrix(!-2112:2112,65)
for(k in 1:31){l=m;for(i in 67:4159)if(sum(l[i+-3:5%/%3+-1:1*65][-5])==1)m[i]=1}
m[2:64,2:64]

```

Try it online!

My first code golf attempt (except for secret ones that I never dared to post...), so nothing really clever going on, I'm afraid...

*Edit 1: -4 bytes to remove useless variable definition*

*Edit 2: thanks to Giuseppe: -18 bytes!*

*Edit 3: thanks **again** to Giuseppe: -4 more bytes*
> 2 votes

# Answer
# Java (JDK), 243 bytes

```
v->{int N=63,K=N*N,g[][]=new int[N][N],w[]=new int[K],i=31,x,c,y;for(g[i][i]=1;i-->0;){for(x=K;x-->0;w[x]=c==1?x+1:0)for(c=0,y=K;y-->0;)if(g[y%N][y/N]>0&(Math.abs(x%N-y%N)|Math.abs(x/N-y/N))<2)c++;for(int z:w)if(z-->0)g[z%N][z/N]=1;}return g;}

```

Try it online!

## Explanations

Basically, the algorithm is to fill two grids by consecutive merges to keep the data from being changed at runtime. For each square, we check if there are neighbours set (using a second full loop instead of a smaller 1-square distance to avoid byte-costly constraints). If there's exactly one neighbour, the square is added to the writing (to-be-merged) grid. Then when all the computation is done, the writing-grid is merged to the main grid. When all the 31 loops are done, the resulting grid is returned.

```
v->{
  int N=63,
      K=N*N,
      g[][]=new int[N][N],          // the grid and return-value, we read from it
      w[]=new int[K],               // the temp array to write in
      i=31,                         // the main iterator to expand the snowflakes
      x,c,y;                        // x the position being tested, c the count of neighbours, y the neighbour candidates
  for(    g[i][i]=1;                // Init the snowflake in its center
          i-->0;                    // Expand the snowflake 31 times
    ){
    for(    x=K;                     // init x to match all the positions
            x-->0;                   // For each position
            w[x]=c==1?x+1:0          // If the counter is exactly 1,
                                     // set x as a position that's not empty.
                                     // and store x+1 instead of 1 or x to ease the merge operation
                                     // and leave 0 as a default value
       )
      for(c=0,y=K;y-->0;)            // Reset the count and loop through all squares again
        if(  g[y%N][y/N]>0           // if y is set
            &( Math.abs(x%N-y%N)     // and if x and y are neighbours
              |Math.abs(x/N-y/N))<2
          )
          c++;                       // Then increase the neighbour-count.
    for(int z:w)                     // For each value to be merged
      if(z-->0)                      // which is +1'd and non default
        g[z%N][z/N]=1;               // Then place it in the grid.
  }
  return g;                          // Return the grid
}

```
> 1 votes

# Answer
# C (gcc), ~~207~~ ~~206~~ 192 bytes

-1 -14 bytes thanks to ceilingcat!

```
#define F(x)for(x=64;--x;
#define z M[r][c]
M[65][65]={[32][32]=32},r,c,i=32,x;main(s){for(;--i;)F(r))F(c)z=s-!z?z:i)for(s=0,x=-9;x++;)s+=M[x/3-~r][x%3-~c]>i;F(r)puts(""))F(c))putchar(33-!z);}

```

Try it online!

To avoid having to use two tables (one for current iteration and one for the next), each new crystal is written using the current iteration number, instead of just using 1. This allows for ignoring any crystals from the current iteration when counting neighbours.

A lot of the counting is done backwards for golfing reasons, including the iteration number, which is why we seed the table with 32 in the middle.

The table is made too large so as to have padding, allowing us to count neighbours without having to care about edge-cases.

A more elegant solution is bound to exist. This many loops is hardly ever a good sign.

```
#define F(x)for(x=64;--x;       To make recurring loops more compact.
                                Goes from 63 down to 1, to skip padding in table.
M[65][65]={[32][32]=32},        Make padded table seeded with first crystal.
r,c,i=32,x,y;main(s){           Misc variables; i holds iteration.
for(;--i;)F(r))F(c)             Loop through table for each iteration.
s==!M[r][c]?M[r][c]=i:0)        Update current cell according to neighbour count
                                found in loop below. We only update if cell is empty
                                (M[r][c] == 0) and if s == 1, combined as shown.
for(s=0,x=r-2;x++<=r;)          Go through 3x3 grid with current cell in center.
for(y=c-2;y++<=c;)
s+=M[x][y]>i;                   If a cell contains a crystal NOT from current gen,
                                increase our neighbour count.

F(r)puts(""))F(c))              Output loop
putchar(33-!M[r][c]);}          Make any non-zero cell a exclamation mark; space otherwise

```
> 1 votes

# Answer
# JavaScript (V8), 465 bytes

```
[w=1414812756,269488144,357569872,285212944,22304e3,286265616,353718608,69648,1414856704,269553680,357650768,17830160,1426150656,286327056,1364280656,0,w,1343229968,1162876240,83886352,1146377472,1414533392,1078284624,327680,1078219860,1414811664,1145062736,89392384,1141130324,1427395664,1073758277,5].map(e=>(Array(32).fill().map(l=>(c.push(1&e?"X":" "),e>>=1),c=[]),c.slice(1).reverse``.concat(c)),o=e=>console.log(e.join``)||e).map(o).reverse``.slice(1).map(o);

```

Try it online!
> 0 votes

---
Tags: code-golf, kolmogorov-complexity, grid, cellular-automata
---