Advent of Code 2020 Solution Megathread - Day 24: Lobby Layout

use std::collections::{HashMap, HashSet};
use std::ops::Add;
use strum::IntoEnumIterator;
use strum_macros::EnumIter;
use parser::*;

// -- model

#[derive(Debug, PartialEq, Copy, Clone, EnumIter)]
enum Direction {
    East,
    West,
    NorthEast,
    NorthWest,
    SouthEast,
    SouthWest
}

type Path = Vec<Direction>;

#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
struct HexTile {
    x: i64,
    y: i64,
    z: i64
}

impl HexTile {
    fn new(x: i64, y: i64, z: i64) -> Self {
        assert!(x + y + z == 0);
        HexTile { x, y, z }
    }

    fn from_path(path: &Path) -> Self {
        path.iter().fold(HexTile::new(0, 0, 0), |hex, step| hex + step)
    }

    fn neighbours(&self) -> impl Iterator<Item = HexTile> + '_ {
        Direction::iter().map(move |dir| *self + &dir)
    }
}

impl Add<&Direction> for HexTile {
    type Output = HexTile;

    fn add(self, dir: &Direction) -> Self {
        use Direction::*;
        match dir {
            East      => HexTile::new(self.x + 1, self.y - 1, self.z),
            West      => HexTile::new(self.x - 1, self.y + 1, self.z),
            NorthEast => HexTile::new(self.x + 1, self.y,     self.z - 1),
            NorthWest => HexTile::new(self.x,     self.y + 1, self.z - 1),
            SouthEast => HexTile::new(self.x,     self.y - 1, self.z + 1),
            SouthWest => HexTile::new(self.x - 1, self.y,     self.z + 1)
        }
    }
}

#[derive(Debug, PartialEq, Copy, Clone)]
enum Color {
    White, Black
}

impl Color {
    fn flip(&self) -> Color {
        match self {
            Color::White => Color::Black,
            Color::Black => Color::White
        }
    }
}

#[derive(Debug, Clone)]
struct Grid {
    tiles: HashMap<HexTile, Color>
}

impl Grid {
    fn new() -> Self {
        Grid { tiles: HashMap::new() }
    }

    fn at(&self, tile: &HexTile) -> Color {
        match self.tiles.get(tile) {
            None => Color::White,
            Some(c) => *c
        }
    }

    fn flip(&mut self, tile: &HexTile) {
        match self.tiles.get_mut(tile) {
            None => { 
                self.tiles.insert(*tile, Color::Black);
            }
            Some(c) => {
                *c = c.flip();
            }
        }
    }

    fn count(&self, c: Color) -> usize {
        self.tiles.values().filter(|t| *t == &c).count()
    }

    fn all_tiles_with_margin(&self) -> HashSet<HexTile> {
        let mut all = HashSet::new();
        for tile in self.tiles.keys() {
            all.insert(*tile);
            for n in tile.neighbours() {
                all.insert(n);
            }
        }
        all
    }

    fn next_generation(&self) -> Grid {
        let mut next = Grid::new();
        for tile in self.all_tiles_with_margin().iter() {
            let black = tile.neighbours().filter(|t| self.at(&t) == Color::Black).count();
            let next_c = match self.at(&tile) {
                Color::Black =>
                    if black == 0 || black > 2 { Color::White } else { Color::Black },
                Color::White =>
                    if black == 2 { Color::Black } else { Color::White }
            };
            next.tiles.insert(*tile, next_c);
        }
        next
    }

    fn run_n_generations(&self, n: usize) -> Grid {
        (0..n).fold(self.clone(), |grid, _| grid.next_generation())
    }

}

// -- parser

fn parse_paths(input: &str) -> ParseResult<Vec<Path>> {
    let east = match_literal("e").means(Direction::East);
    let west = match_literal("w").means(Direction::West);
    let north_east = match_literal("ne").means(Direction::NorthEast);
    let north_west = match_literal("nw").means(Direction::NorthWest);
    let south_east = match_literal("se").means(Direction::SouthEast);
    let south_west = match_literal("sw").means(Direction::SouthWest);
    let step = east.or(west).or(north_east).or(north_west).or(south_east).or(south_west);
    let path = one_or_more(step);
    let paths = one_or_more(whitespace_wrap(path));
    paths.parse(input)
}

// -- problems

fn grid_from_paths(paths: &Vec<Path>) -> Grid {
    let mut grid = Grid::new();
    for path in paths {
        grid.flip(&HexTile::from_path(&path));
    }
    grid    
}

fn part1(grid: &Grid) -> usize {
    grid.count(Color::Black)
}

fn part2(grid: &Grid) -> usize {
    let final_grid = grid.run_n_generations(100);
    final_grid.count(Color::Black)
}


fn main() {
    let input = std::fs::read_to_string("./input.txt").unwrap();
    let paths = parse_paths(&input).unwrap().1;
    let grid = grid_from_paths(&paths);
    println!("part 1 {}", part1(&grid));
    println!("part 2 {}", part2(&grid));
}

#[cfg(test)]
mod tests {
    use super::*;

    fn test_paths() -> Vec<Path> {
        parse_paths(
            "sesenwnenenewseeswwswswwnenewsewsw
            neeenesenwnwwswnenewnwwsewnenwseswesw
            seswneswswsenwwnwse
            nwnwneseeswswnenewneswwnewseswneseene
            swweswneswnenwsewnwneneseenw
            eesenwseswswnenwswnwnwsewwnwsene
            sewnenenenesenwsewnenwwwse
            wenwwweseeeweswwwnwwe
            wsweesenenewnwwnwsenewsenwwsesesenwne
            neeswseenwwswnwswswnw
            nenwswwsewswnenenewsenwsenwnesesenew
            enewnwewneswsewnwswenweswnenwsenwsw
            sweneswneswneneenwnewenewwneswswnese
            swwesenesewenwneswnwwneseswwne
            enesenwswwswneneswsenwnewswseenwsese
            wnwnesenesenenwwnenwsewesewsesesew
            nenewswnwewswnenesenwnesewesw
            eneswnwswnwsenenwnwnwwseeswneewsenese
            neswnwewnwnwseenwseesewsenwsweewe
            wseweeenwnesenwwwswnew"
        ).unwrap().1
    }

    fn test_grid() -> Grid {
        grid_from_paths(&test_paths())
    }

    #[test]
    fn test_parser() {
        use Direction::*;
        let paths = parse_paths("esew\nnwwswee");
        assert_eq!(paths, Ok(("", vec![
            vec![East, SouthEast, West],
            vec![NorthWest, West, SouthWest, East, East]
        ])));
    }

    #[test]
    fn test_hextile_from_path() {
        use Direction::*;
        assert_eq!(HexTile::from_path(&vec![East, SouthWest, West]), HexTile::new(-1, 0, 1));
        assert_eq!(HexTile::from_path(&vec![NorthWest, West, SouthWest, East, East]), HexTile::new(0, 0, 0));
    }

    #[test]
    fn test_part1() {
        assert_eq!(part1(&test_grid()), 10);
    }

    #[test]
    fn test_part2() {
        use Color::Black;
        let grid = test_grid();
        assert_eq!(grid.run_n_generations(1).count(Black), 15);
        assert_eq!(grid.run_n_generations(2).count(Black), 12);
        assert_eq!(grid.run_n_generations(3).count(Black), 25);
        assert_eq!(grid.run_n_generations(4).count(Black), 14);
        assert_eq!(grid.run_n_generations(20).count(Black), 132);
        assert_eq!(grid.run_n_generations(30).count(Black), 259);
        assert_eq!(grid.run_n_generations(100).count(Black), 2208);
    }
}

from collections import defaultdict
import numpy as np
import tensorflow as tf

vecs = {
    "e":   1 + 0j ,
    "se":  0 + 1j ,
    "sw": -1 + 1j ,
    "w":  -1 + 0j ,
    "nw":  0 - 1j ,
    "ne":  1 - 1j ,
}
raw = open("input.txt").read().replace("e", "e,").replace("w", "w,").splitlines()
data = [list(map(vecs.__getitem__, line[:-1].split(","))) for line in raw]

tiles_flipped = defaultdict(bool)
for line in data:
    tiles_flipped[sum(line)] ^= True
print("sum", sum(tiles_flipped.values()))

big_enough = 200
grid = np.zeros([big_enough,big_enough])
xdim, ydim = grid.shape

for coord, colour in tiles_flipped.items():
    gc = coord + (1+1j)*big_enough/2
    grid[int(gc.real), int(gc.imag)] = colour

padding = tf.constant([[1, 1], [1, 1]])
neighbors_filt = tf.constant([
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0],
])
conv_filt = tf.reshape(tf.cast(neighbors_filt, tf.float32),  [3, 3, 1, 1])

init_data = tf.cast(grid, tf.bool)

@tf.function
def generate(this_gen):
    padded = tf.pad(this_gen, padding)
    padded = tf.reshape(padded, [1, ydim+2, xdim+2, 1]) # need for tf.nn.convolution

    convolved = tf.nn.convolution(tf.cast(padded, tf.float32), conv_filt)
    neighbors = tf.reshape(convolved, [xdim, ydim])

    rule_nw = tf.math.logical_or(neighbors == 1, neighbors == 2)
    rule_b = (neighbors == 2)

    next_gen = tf.math.logical_or(tf.math.logical_and(this_gen, rule_nw), rule_b)
    return next_gen

generation = init_data
for _ in range(100):
    generation = generate(generation)
print("total", tf.math.reduce_sum(tf.cast(generation, tf.int32)))

replace :: Char -> String -> String -> String
replace c w [] = [] 
replace c w (x:xs) | c == x    = w ++ replace c w xs
                   | otherwise = x : replace c w xs

dir = M.fromList [("nw", (-1) :+ 1), ("ne", 1 :+ 1), 
                  ("w", (-2) :+ 0), ("e", 2 :+ 0), 
                  ("sw", (-1) :+ (-1)), ("se", 1 :+ (-1))]

task1 floor [] = floor
task1 floor (x:xs) = task1 (uFloor x floor) xs 
    where
        uFloor :: String -> M.Map String Int -> M.Map String Int
        uFloor ts = M.insertWith (\_ o -> 1 - o) (show $ tile ts) 1 
        tile = sum . map (fromJust . flip M.lookup dir) . filter (/= "") . splitOn " "

task2 0 !floor = floor
task2 n !floor = task2 (n-1) (aux floor)
    where
        aux floor = let keys = map read (M.keys floor)
                        bs = union keys [ x | f <- keys,
                                            x <- neighbours f  ]
                        kd = map (\k -> (show k, sum (map (\k -> M.findWithDefault 0 (show k) floor) (neighbours k)))) bs
                      in foldr (\(k,s) floor ->  M.insert k (check k s floor) floor) floor kd

        check k s floor | s == 2 || (M.findWithDefault 0 k floor == 1 && s == 1) = 1
                        | otherwise = 0
        neighbours l = map (l+) (M.elems dir)

main = do
    is <- readFile "day24_input" <&> replace 'e' "e " 
                                 <&> replace 'w' "w "
                                 <&> lines
    let floor = task1 M.empty is
    print (sum floor)
    print (sum $ task2 100 floor)

let fs = require("fs"),
    tiles = new Set(),
    valids = ["n", "e", "ne", "nw", "se", "sw"],
    data = fs.readFileSync("input.txt", "utf8").split("\n")
const intoarray = (dir, existing=[]) => {
    let firsttwo = dir[0] + dir[1];
    if (firsttwo) {
        if (valids.indexOf(firsttwo) > -1) {
            existing.push(firsttwo);
            return intoarray(dir.slice(2),existing)
        } else {
            existing.push(firsttwo[0])
            return intoarray(dir.slice(1),existing)
        }
    } else {
        return existing;
    }
}
for (const i in data) {
    let e = 0,
        n = 0;
    for (r of intoarray(data[i])) {
        switch (r) {
            case "e":
                e++
                break;
            case "w":
                e--
                break;
            case "ne":
                n++
                e += 0.5
                break;
            case "nw":
                n++
                e -= 0.5
                break;
            case "se":
                n--
                e += 0.5
                break;
            case "sw":
                n--
                e -= 0.5
                break;
        }
    }
    let col = "b";
    if (tiles.has(n + "," + e)) tiles.delete(n + "," + e)
    else tiles.add(n + "," + e);
}

console.log(tiles.size);

from collections import defaultdict
import sys


BLACK = True
WHITE = False

tiles = defaultdict(bool)
filename = sys.argv[1]
with open(filename, "r") as f:
    for line in f:
        x = 0
        y = 0
        line_iter = iter(line)
        for char in line_iter:
            if char == 'e':
                x += 1
            elif char == 'w':
                x -= 1
            elif char == 'n':
                y += 1
                if next(line_iter) == 'e':
                    x += 0.5
                else:
                    x -= 0.5
            elif char == 's':
                y -= 1
                if next(line_iter) == 'e':
                    x += 0.5
                else:
                    x -= 0.5

        tiles[(x, y)] = not tiles[(x, y)]

print("Part 1:", sum(tiles.values()))

for i in range(100):
    new_tiles = defaultdict(bool)

    # Ensure white tiles around black tiles in input set
    blacks = [coord for coord, color in tiles.items() if color]
    for x, y in blacks:
        tiles[(x + 1, y)]
        tiles[(x - 1, y)]
        tiles[(x + 0.5, y + 1)]
        tiles[(x - 0.5, y + 1)]
        tiles[(x + 0.5, y - 1)]
        tiles[(x - 0.5, y - 1)]

    # Evolve based on rules
    for (x, y), color in tiles.items():
        total = sum([
            (x + 1, y) in tiles and tiles[(x + 1, y)],
            (x - 1, y) in tiles and tiles[(x - 1, y)],
            (x + 0.5, y + 1) in tiles and tiles[(x + 0.5, y + 1)],
            (x - 0.5, y + 1) in tiles and tiles[(x - 0.5, y + 1)],
            (x + 0.5, y - 1) in tiles and tiles[(x + 0.5, y - 1)],
            (x - 0.5, y - 1) in tiles and tiles[(x - 0.5, y - 1)],
        ])
        if color == BLACK and (total == 0 or total > 2):
            new_tiles[(x, y)] = WHITE
        elif color == WHITE and total == 2:
            new_tiles[(x, y)] = BLACK
        else:
            new_tiles[(x, y)] = color

    tiles = new_tiles

print("Part 2:", sum(tiles.values()))