## DEV Community is a community of 660,470 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

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

Ryan Palo
Ryan is an engineer in the Sacramento Area with a focus in Python, Ruby, and Rust. Bash/Python Exercism mentor. Coding, physics, calculus, music, woodworking. Message me on DEV!

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.

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

``````Ryan's Leaderboard: 224198-25048a19
``````

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
Rust 1

Merry Coding!

## Discussion (9)

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 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)
}
}

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 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);
}
}
``````
Benedict Gaster

That reference is great... thanks!

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.

Benedict Gaster

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

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 ,
}
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):

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)))
``````
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))]

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 " "

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)
``````
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"],
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);
``````
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()))
``````
Thibaut Patel

My JavaScript video walkthrough: