🌟 Advent of Code (AoC) 2020 🌟

part1$ <in awk -v p1=1 -f d11.awk
part2$ <in awk -f d11.awk

{ split($1, v, ""); for (x in v) { c = x" "NR; cs[c] = m[c] = v[x] } mx = length(v) }
END {
	d[-1]; d[0]; d[1]; for (x in d) { for (y in d) { dirs[x" "y] } } delete dirs[0" "0]
	do {
		delete u
		for (c in cs) {
			if (m[c] == ".") { continue }
			occupied = 0
			for (dir in dirs) {
				split(dir, d); split(c, p)
				occupied += test(p[1] + d[1], p[2] + d[2], d[1], d[2])
			}
			if (m[c] == "L" && occupied == 0) { u[c] = "#" }
			if (m[c] == "#" && occupied >= (p1 ? 4 : 5)) { u[c] = "L" }
		}
		for (x in u) { m[x] = u[x] }
	} while (length(u) > 0)
	for (x in m) { answer += m[x] == "#" }
	print answer
}

function test(x, y, dx, dy) {
	return m[x" "y] == "#" ? 1 : p1 || x <= 0 || y <= 0 || x > mx || y > NR || m[x" "y] == "L" ? 0 : test(x + dx, y + dy, dx, dy)
}

<in sort -n | awk '{ n[NR] = $1 } END { print f(0, 1) } function f(c, i) { return c in s ? s[c] : s[c] = n[i] - c <= 3 ? i == NR ? 1 : f(n[i], i + 1) + f(c, i + 1) : 0 }'

function calculate(list) {
    for (let i = 0; i < 1000; i++) {
        let newState = JSON.parse(JSON.stringify(list))
        let height = list.length;
        let width = list[0].length;
        for (let y = 1; y < height - 1; y++) {
            for (let x = 1; x < width - 1; x++) {
                newState[y][x] = getNewState(list, x, y);
            }
        }

        if (JSON.stringify(list) === JSON.stringify(newState)) {
            console.log("Stable after " + i + " iterations");
            console.log(countAllOccupied(newState) + " occupied seats");
            break;
        }
        list = JSON.parse(JSON.stringify(newState))
    }
}

function countAllOccupied(list) {
    let freeSeats = 0;
    for (let y = 0; y < list.length; y++) {
        for (let x = 0; x < list[y].length; x++) {
            if (list[y][x] === "#") {
                freeSeats++;
            }
        }
    }
    return freeSeats;
}

function see(list, x, y, dx, dy) {
    x = x + dx;
    y = y + dy;
    while (list[y][x] === ".") {
        x = x + dx;
        y = y + dy;
    }
    return list[y][x];
}

function countSurroundingOccupied(list, x, y) {
    let occupied = 0;
    if (see(list, x, y, -1, -1) === "#") { occupied++; }
    if (see(list, x, y, -1, 0) === "#") { occupied++; }
    if (see(list, x, y, -1, 1) === "#") { occupied++; }
    if (see(list, x, y, 0, -1) === "#") { occupied++; }
    if (see(list, x, y, 0, 1) === "#") { occupied++; }
    if (see(list, x, y, 1, -1) === "#") { occupied++; }
    if (see(list, x, y, 1, 0) === "#") { occupied++; }
    if (see(list, x, y, 1, 1) === "#") { occupied++; }
    return occupied;
}

function getNewState(list, x, y) {
    if (list[y][x] === "L" &&
        (see(list, x, y, -1, -1) != "#" &&
            see(list, x, y, -1, 0) != "#" &&
            see(list, x, y, -1, 1) != "#" &&
            see(list, x, y, 0, -1) != "#" &&
            see(list, x, y, 0, 1) != "#" &&
            see(list, x, y, 1, -1) != "#" &&
            see(list, x, y, 1, 0) != "#" &&
            see(list, x, y, 1, 1) != "#")) {
        return "#";
    }
    else if (list[y][x] === "#" && countSurroundingOccupied(list, x, y) >= 5) {
        return "L";
    }
    else {
        return list[y][x];
    }
}

function parseInput(text) {
    const list = text.split("\n");
    for (let i = 0; i < list.length; i++) {
        list[i] = ("B" + list[i] + "B").split("");
    }
    let emptyLine = new Array(list[0].length).fill("B");
    list.unshift(emptyLine);
    list.push(emptyLine);
    calculate(list);
}

async function fetchInput() {
    var response = await fetch('input.txt');
    var text = await response.text();
    parseInput(text);
}

fetchInput();

#include <algorithm>
#include <boost/iostreams/device/mapped_file.hpp>
#include <chrono>
#include <cstring>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>

struct Pos {
    int x;
    int y;
    
    Pos(int _x, int _y) : x(_x), y(_y) { }

    bool operator==(const Pos &rhs) const {
        return x == rhs.x && y == rhs.y;
    }

    bool operator<(const Pos &rhs) const {
        return (x == rhs.x && y < rhs.y) || x < rhs.x;
    }

    Pos &operator+=(const Pos &rhs) {
        x += rhs.x;
        y += rhs.y;
        return *this;
    }
};

namespace std {
    template<>
    struct hash<Pos> {
        size_t operator()(const Pos &pos) const {
            return hash<int>()(pos.x ^ (pos.y << 7));
        }
    };
}

struct SetReducer {
    SetReducer(std::unordered_set<Pos> s = {}) : set(s) {}
    
    SetReducer& operator+= (const SetReducer &rhs) {
        set.insert(rhs.set.begin(), rhs.set.end());
        return *this;
    }

    std::unordered_set<Pos> set;
};

#pragma omp declare reduction(SetReducerInsert: SetReducer: omp_out += omp_in)

struct WaitingArea {
    std::vector<Pos> seats;
    std::unordered_set<Pos> occupied;
    int width;
    int height;
    bool isPart1;
    
    WaitingArea(const char *input, bool part1) : isPart1(part1) {
        int x = 0;
        int y = 0;
        char tile;

        width = std::strchr(input, '\n') - input;
        height = std::strlen(input) / (width + 1);
        
        while ((tile = *input++) != '\0') {
            switch (tile) {
            case '\n':
                x = 0;
                y++;
                break;
            case 'L':
                seats.push_back(Pos(x, y));
                // fallthrough
            default:
                x++;
                break;
            }
        }
        std::sort(seats.begin(), seats.end());
    }

    int countAdjacentOccupied(const Pos &pos) {
        int cnt = 0;
        for (int dy = -1; dy <= 1; dy++) {
            for (int dx = -1; dx <= 1; dx++) {
                if (!(dy == 0 && dx == 0)
                    && occupied.count(Pos(pos.x + dx, pos.y + dy)) > 0) {
                    cnt += 1;
                }
            }
        }
        return cnt;
    }

    bool isOccupiedVisible(const Pos &from, const Pos &dir) {
        Pos pos = from;
        pos += dir;
        while (pos.x >= 0 && pos.x < width && pos.y >= 0 && pos.y < height) {
            if (occupied.count(pos) > 0) {
                return true;
            }
            if (std::binary_search(seats.begin(), seats.end(), pos)) {
                return false;
            }
            pos += dir;
        }
        return false;
    }
    
    int countVisibleOccupied(const Pos &pos) {
        int cnt = 0;
        for (int dy = -1; dy <= 1; dy++) {
            for (int dx = -1; dx <= 1; dx++) {
                if (!(dy == 0 && dx == 0)
                    && isOccupiedVisible(pos, Pos(dx, dy))) {
                    cnt += 1;
                }
            }
        }
        return cnt;        
    }
    
    bool nextGeneration() {
        SetReducer nextOccupied;

#pragma omp parallel for reduction(SetReducerInsert:nextOccupied)
        for (int i = 0; i < seats.size(); i++) {
            const Pos& seat = seats[i];
            if (isPart1) {
                int n = countAdjacentOccupied(seat);
                if (n == 0 || (n < 4 && occupied.count(seat) > 0)) {
                    nextOccupied += SetReducer({seat});
                }
            } else {
                int n = countVisibleOccupied(seat);
                    if (n == 0 || (n < 5 && occupied.count(seat) > 0)) {
                        nextOccupied += SetReducer({seat});
                    }                
            }                
        }

        if (occupied == nextOccupied.set) {
            return true;
        }

        occupied = nextOccupied.set;
        return false;
    }    
};

static void bench(std::function<void()> fn) {
    auto start = std::chrono::high_resolution_clock::now();
    fn();
    auto finish = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(finish - start);
    std::cout << "Took " << duration.count() << " ms\n";
}


int main() {
    boost::iostreams::mapped_file input("input.txt", boost::iostreams::mapped_file::readonly);
    
    WaitingArea wa1(input.const_data(), true);
    WaitingArea wa2(input.const_data(), false);
    
    bench([&]() {
        while (!wa1.nextGeneration()) { }
        std::cout << "Part 1 : " << wa1.occupied.size() << "\n";
    });
        
    bench([&]() {
        while (!wa2.nextGeneration()) { }
        std::cout << "Part 2 : " << wa2.occupied.size() << "\n";
    });
}

Part 1 : 2481
Took 53 ms
Part 2 : 2227
Took 97 ms

import numpy as np
from functools import reduce

input = [list(map(ord, list(i.strip()))) for i in open("input","r")]
sx, sy = len(input), len(input[0])

def pad(a, f = np.zeros):
    res = f((sx+2, sy+2), dtype = np.int8)
    res[1:1+sx,1:1+sy] = a
    return res

is_seat = pad(np.where(np.array(input) == ord('L'), 1, 0), np.ones)

directions = ((-1,-1), (-1, 0), (-1, 1),
              ( 0,-1),          ( 0, 1),
              ( 1,-1), ( 1, 0), ( 1, 1))

def neighbors1(a):
    return reduce(np.add, [a[1+x:1+x+sx,1+y:1+y+sy] for x,y in directions])

def neighbors2(a):
    def los(a, pos, dir):
        while True:
            pos = tuple(np.add(pos, dir))
            if is_seat[pos]: return a[pos]
    return np.array([[sum([los(a, (x,y), dir)
                           for dir in directions])
                      for y in range(1,1+sy)]
                     for x in range(1,1+sx)])

def round(a, neighbors, crowded):
    ns = neighbors(a)
    birth = pad(np.where(ns == 0, 1, 0))
    not_death = pad(np.where(ns < crowded, 1, 0))
    return np.where(a * not_death + birth, 1, 0) * is_seat

def run(neighbors, crowded):
    a = np.zeros((sx+2, sy+2), dtype = np.int8)
    while True:
        b = a
        a = round(a, neighbors, crowded)
        if np.array_equal(a, b): return np.sum(a)

print(run(neighbors1, 4), run(neighbors2, 5))

$ <in sed -E 's/^(.)/\1 /' | awk 'BEGIN { dx = 1; wx = 10; wy = 1 }
/E/ { p1x += $2; wx += $2 }
/W/ { p1x -= $2; wx -= $2 }
/N/ { p1y += $2; wy += $2 }
/S/ { p1y -= $2; wy -= $2 }
/F/ { p1x += dx * $2; p1y += dy * $2; p2x += wx * $2; p2y += wy * $2 }
/R/ || /L/ {
	turn = mod($1 ~ /R/ ? $2 : -$2, 360)
	for (i = turn; i > 0; i -= 90) { px = dx; dx = dy; dy = -px }
	for (i = turn; i > 0; i -= 90) { px = wx; wx = wy; wy = -px }
}
END { print (p1x < 0 ? -p1x : p1x) + (p1y < 0 ? -p1y : p1y) }
END { print (p2x < 0 ? -p2x : p2x) + (p2y < 0 ? -p2y : p2y) }

function mod(n, m) { return n % m + (n < 0 ? m : 0) }'

rdirs = [complex(1,0),complex(0, 1),complex(-1,0),complex(0,-1)]
ldirs = [complex(1,0),complex(0,-1),complex(-1,0),complex(0, 1)]

def eswn(dir, p, sp, wp, d, x):
    offset = rdirs['ESWN'.find(d)] * x
    return (dir, p + offset, sp, wp + offset)
    
def f(dir, p, sp, wp, d, x):
    return dir, p + rdirs[dir] * x, sp + wp * x, wp

def r(dir, p, sp, wp, d, x):
    return (dir + x // 90) % 4, p, sp, wp * rdirs[x // 90]
    
def l(dir, p, sp, wp, d, x):
    return (dir - x // 90) % 4, p, sp, wp * ldirs[x // 90]
    
func = {'E' : eswn, 'S' : eswn, 'W' : eswn, 'N' : eswn,
        'R' : r, 'L' : l, 'F' : f}

dir, p, sp, wp = 0, complex(0,0), complex(0,0), complex(10,-1)
for line in open('input', 'r'):
    dir, p, sp, wp = func[line[0]](dir, p, sp, wp, line[0], int(line[1:]))

print(int(abs(p.real) + abs(p.imag)), int(abs(sp.real) + abs(sp.imag)))

part1$ <in sed -E 's/^(.)/\1 /' | awk -f d12.awk -v p1=1 -v dx=1
part2$ <in sed -E 's/^(.)/\1 /' | awk -f d12.awk -v dx=10 -v dy=1

BEGIN {
	R = "real"; I = "imag"
	wp = complex_make(dx, dy)
	lookup[dirs[0] = "E"] = complex_make(1, 0)
	lookup[dirs[1] = "S"] = complex_make(0, -1)
	lookup[dirs[2] = "W"] = complex_make(-1, 0)
	lookup[dirs[3] = "N"] = complex_make(0, 1)
}

/[EWNS]/ { res = complex_add(p1 ? pos : wp, complex_mult(complex_make($2, 0), lookup[$1])) }
/[EWNS]/ && p1 { pos = res } /[EWNS]/ && !p1 { wp = res }

/F/ { pos = complex_add(pos, complex_mult(wp, complex_make($2, 0))) }

/R|L/ { wp = complex_mult(wp, lookup[dirs[mod(($1 ~ /R/ ? $2 : -$2) / 90, 4)]]) }

END { complex_split(pos, r); print (r[R] < 0 ? -r[R] : r[R]) + (r[I] < 0 ? -r[I] : r[I]) }

function mod(n, m) { return n % m + (n < 0 ? m : 0) }

function complex_add(a, b) {
	complex_split(a, a_)
	complex_split(b, b_)
	return complex_make(a_[R] + b_[R], a_[I] + b_[I])
}

function complex_mult(a, b) {
	complex_split(a, a_)
	complex_split(b, b_)
	return complex_make(a_[R] * b_[R] - a_[I] * b_[I], a_[R] * b_[I] + a_[I] * b_[R])
}

function complex_split(a, r) {
	split(a, v, ",")
	r[R] = v[1]
	r[I] = v[2]
}

function complex_make(r, i) {
	return r","i
}