DEV Community

Cover image for Advent of Code 2020 Solution Megathread - Day 24: Lobby Layout
Ryan Palo
Ryan Palo

Posted on

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

Christmas Eve is here! Don't spend too much time on this one. There's a holiday afoot!

The Puzzle

In today’s puzzle, we've finally reached it to the resort at last. Their lobby is being renovated and we're tasked with flipping tiles on an a hexagonal grid to figure out what the pattern is to look like.

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19
Enter fullscreen mode Exit fullscreen mode

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 07:25AM 12/24/2020 PST.

Language Count
Python 1
Haskell 1
Rust 1

Merry Coding!

Top comments (9)

Collapse
 
neilgall profile image
Neil Gall

Aww, I'm sad it's almost over. I learned loads about hexagonal grids however from this fantastic page. Rust as ever this year with proper modelling and tests...

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);
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
bgaster profile image
Benedict Gaster

That reference is great... thanks!

Collapse
 
neilgall profile image
Neil Gall

One of the best things about doing these challenges is forcing you to learn things you might not otherwise need. Next time I have a hex tile problem, even if it's just in AoC, I'll remember there are well trodden techniques to use, even if I've forgotten the details.

Thread Thread
 
bgaster profile image
Benedict Gaster

Yes, the best part of AoC is how much I've learned.

Collapse
 
meseta profile image
Yuan Gao • Edited

Since I already implemented cellular automata with Tensorflow in multiple previous days, I re-use it again. Also, luckily I'd done a fair bit of hex grids in game dev before. A small bonus: Python has native support for complex numbers, which can be used to write compact code involving complex arithmetic or, in this case, just using complex numbers to hold a 2-vector.

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)))
Enter fullscreen mode Exit fullscreen mode
Collapse
 
bgaster profile image
Benedict Gaster • Edited

Well back to Haskell today, although not 100% sure this was a good choice. The problem being that updating an ever growing floor map in part 2 meant that after about 50 iterations it starts to get pretty slow. So much so I had to add some prints, inititally, to check it was actually making progress. However, it was and it kindly got to the right answer. Another issue was that as I'd choosen to use a map that used the position as a key, which for me were complex numbers, then i had to convert to string and back, as Haskell won't allow "real" numbers to have order defined that is needed for maps, at least I could not resolve that issue. Ahh well it still worked out pretty nicely, if not a little on the slow side.

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)
Enter fullscreen mode Exit fullscreen mode
Collapse
 
kudostoy0u profile image
Kudos Beluga • Edited

Part 1 JS solution is done, part 2 is coming soon!

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);
Enter fullscreen mode Exit fullscreen mode
Collapse
 
rpalo profile image
Ryan Palo

Quick one today! Probably could improve efficiency in the Conway section, but it runs pretty quick so I'm good with it. Forgot for a minute that I needed to loop over the white tiles sharing boundaries with my black tiles too!

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()))
Enter fullscreen mode Exit fullscreen mode
Collapse
 
thibpat profile image
Thibaut Patel

My JavaScript video walkthrough: