Day 24: Lobby Layout

public override string SolvePart1()
{
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input24))
	{
		var map = new Dictionary<ValueTuple<int, int>, bool>();
		string line;
		while ((line = fs.ReadLine()) != null)
		{
			var curr = (q: 0, r: 0);
			for (int i = 0; i < line.Length; i++)
			{
				if (line[i] == 'e')
				{
					curr = (curr.q + 1, curr.r);
				}
				else if (line[i] == 'w')
				{
					curr = (curr.q - 1, curr.r);
				}
				else if (line[i] == 'n')
				{
					i++;
					if (line[i] == 'e')
					{
						curr = (curr.q + 1, curr.r - 1);
					}
					else // line[i] == 'w'
					{
						curr = (curr.q, curr.r - 1);
					}
				}
				else // line[i] == 's'
				{
					i++;
					if (line[i] == 'e')
					{
						curr = (curr.q, curr.r + 1);
					}
					else // line[i] == 'w'
					{
						curr = (curr.q - 1, curr.r + 1);
					}
				}
			}
			if (map.ContainsKey(curr))
			{
				map[curr] = !map[curr];
			}
			else
			{
				map.Add(curr, true);
			}
		}
		return $"{map.Values.Count(tile => tile)} black tiles";
	}
}

public override string SolvePart2()
{
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input24))
	{
		var map = new Dictionary<ValueTuple<int, int>, bool>();
		var maxQR = (q: 0, r: 0);
		var minQR = (q: 0, r: 0);
		string line;
		while ((line = fs.ReadLine()) != null)
		{
			var curr = (q: 0, r: 0);
			for (int i = 0; i < line.Length; i++)
			{
				if (line[i] == 'e')
				{
					curr = (curr.q + 1, curr.r);
				}
				else if (line[i] == 'w')
				{
					curr = (curr.q - 1, curr.r);
				}
				else if (line[i] == 'n')
				{
					i++;
					if (line[i] == 'e')
					{
						curr = (curr.q + 1, curr.r - 1);
					}
					else // line[i] == 'w'
					{
						curr = (curr.q, curr.r - 1);
					}
				}
				else // line[i] == 's'
				{
					i++;
					if (line[i] == 'e')
					{
						curr = (curr.q, curr.r + 1);
					}
					else // line[i] == 'w'
					{
						curr = (curr.q - 1, curr.r + 1);
					}
				}
			}
			if (map.ContainsKey(curr))
			{
				map[curr] = !map[curr];
			}
			else
			{
				map.Add(curr, true);
			}

			if (curr.q > maxQR.q)
			{
				maxQR.q = curr.q;
			}
			if (curr.r > maxQR.r)
			{
				maxQR.r = curr.r;
			}
			if (curr.q < minQR.q)
			{
				minQR.q = curr.q;
			}
			if (curr.r < minQR.r)
			{
				minQR.r = curr.r;
			}
		}

		maxQR = (maxQR.q + 1, maxQR.r + 1);
		minQR = (minQR.q - 1, minQR.r - 1);

		for (int t = 0; t < 100; t++)
		{
			var nextMap = new Dictionary<ValueTuple<int, int>, bool>();
			for (int r = minQR.r; r <= maxQR.r; r++)
			{
				for (int q = minQR.q; q <= maxQR.q; q++)
				{
					var curr = (q, r);
					var neighbors = GetNeighbors(curr);
					var count = neighbors.Count(neighbor => map.ContainsKey(neighbor) && map[neighbor]);

					if (map.ContainsKey(curr) && map[curr])
					{
						nextMap.Add(curr, count == 1 || count == 2);
					}
					else
					{
						nextMap.Add(curr, count == 2);
					}
				}
			}

			maxQR = (maxQR.q + 1, maxQR.r + 1);
			minQR = (minQR.q - 1, minQR.r - 1);

			map = nextMap;
		}	 

		
		return $"After 100 days, {map.Values.Count(tile => tile)} black tiles";
	}
}

public List<ValueTuple<int, int>> GetNeighbors(ValueTuple<int, int> p)
{
	return new List<ValueTuple<int, int>>()
	{
		(p.Item1 + 1, p.Item2),
		(p.Item1 + 1, p.Item2 - 1),
		(p.Item1, p.Item2 - 1),
		(p.Item1 - 1, p.Item2),
		(p.Item1 - 1, p.Item2 + 1),
		(p.Item1, p.Item2 + 1),
	};
}

Red Blob Games has this article, which is pretty much the definitive source for how to implement hex-grids. I went with the Axial coordinate scheme, because it made finding neighboring tiles the easiest (and I didn't care about the visual representation or storage layout, because I was using a Dictionary anyway)

After the hex-grid stuff is done, I basically reused my code from Day 17 verbatim - as usual, just gotta reimplement the "find-neighbors" function and the criteria for toggling cells on or off. I was lazy with the bounds-checking and just expanded the board bounds on every step because I wasn't confident in determining whether new cells were actually pushing the bounds out. Part 2 runs in under 2s, so /shrug.

import time

with open("input.txt") as input_file:
    tiles = input_file.read().split("\n")


# coordinates: "cube-coordinates" with 3 axis [x, y, z]
# see: https://www.redblobgames.com/grids/hexagons/
x, y, z = 0, 1, 2


def get_coordinates(tile_text):
    coordinates = [0, 0, 0]
    while tile_text:
        if tile_text[0] == "e":
            coordinates[x] += 1
            coordinates[y] -= 1
            tile_text = tile_text[1:]
        elif tile_text[0] == "w":
            coordinates[x] -= 1
            coordinates[y] += 1
            tile_text = tile_text[1:]
        elif tile_text[0] == "s" and tile_text[1] == "e":
            coordinates[y] -= 1
            coordinates[z] += 1
            tile_text = tile_text[2:]
        elif tile_text[0] == "n" and tile_text[1] == "w":
            coordinates[y] += 1
            coordinates[z] -= 1
            tile_text = tile_text[2:]
        elif tile_text[0] == "s" and tile_text[1] == "w":
            coordinates[x] -= 1
            coordinates[z] += 1
            tile_text = tile_text[2:]
        elif tile_text[0] == "n" and tile_text[1] == "e":
            coordinates[x] += 1
            coordinates[z] -= 1
            tile_text = tile_text[2:]
    return coordinates


def get_black_tiles(tiles):
    black_tiles = []
    for tile in tiles:
        tile_coordinates = get_coordinates(tile)
        if not tile_coordinates in black_tiles:
            black_tiles.append(tile_coordinates)
        else:
            black_tiles.remove(tile_coordinates)
    return black_tiles


def get_neighbors(tile):
    return [[tile[x] + 1, tile[y] - 1, tile[z]],
            [tile[x] - 1, tile[y] + 1, tile[z]],
            [tile[x] + 1, tile[y], tile[z] - 1],
            [tile[x] - 1, tile[y], tile[z] + 1],
            [tile[x], tile[y] + 1, tile[z] - 1],
            [tile[x], tile[y] - 1, tile[z] + 1]]


def count_neighbors(tile, blacks):
    neighbors = get_neighbors(tile)
    count = 0
    for tile in neighbors:
        if tile in blacks:
            count += 1
    return count


def conway_tiles(tiles, days):
    blacks = get_black_tiles(tiles)
    days_elapsed = 0
    previous_duration = 0

    increases = []
    start_time_total = time.time()
    while days_elapsed <= days:
        start_time = time.time()
        new_blacks = []
        for tile in blacks:
            count = count_neighbors(tile, blacks)
            if count == 1 or count == 2:
                if not tile in new_blacks:
                    new_blacks.append(tile)
            neighbors = get_neighbors(tile)
            for neighbor in neighbors:
                count = count_neighbors(neighbor, blacks)
                if (not neighbor in blacks) and count == 2:
                    if not neighbor in new_blacks:
                        new_blacks.append(neighbor)
        blacks = new_blacks
        days_elapsed += 1

        print("\nDay", str(days_elapsed) + ":", len(blacks))

        # this entire part is just for estimating the time remaining
        duration = time.time() - start_time
        if previous_duration:
            if days_elapsed > 30:
                # ignore first 30 days for estimate
                increases.append(duration / previous_duration)
                average_increase = sum(increases) / len(increases)
                estimated_time_left = 0
                next_duration = duration
                for day in range(0, days - days_elapsed + 1):
                    next_duration = next_duration * average_increase
                    estimated_time_left += next_duration

                print("Time remaining:", estimated_time_left, "seconds")
                print("Estimated total time:",
                      time.time() - start_time_total + estimated_time_left, "seconds")
        previous_duration = duration

    print("\nDone. Total time:", time.time() - start_time_total)


conway_tiles(tiles, 100)

After reading the problem description, I realized that you could solve it by view the tiles as a sort of graph. The only problem is figuring out how to connect the tiles to each other. Initially, I started with a Tile class that had attributes for each direction (ie. e, w, etc.) but soon realized that this approach wouldn't work b/c it would be difficult to connect tiles together (ie. have them reference each other appropriately).

Instead, after some thinking and drawing pictures (I literally used some pencils and colored pens to draw tiles), I realized that you can project the tiles onto a coordinate system where each direction is a particular offset. For instance, w would be (-1, -1) and e is (1, 1). Once I saw this, then the solution was straightforward: make a table of the tiles where the key is the coordinate and the value is the color. To make this table, I would just follow the "steps" in the input and if the location I ended up at was not in the table, then I set it to white, otherwise, I flipped the current value.

import sys

# Constants

WHITE = 0
BLACK = 1

DIRECTIONS = {
    'w' : (-1, -1),
    'e' : ( 1,  1),
    'nw': (-2,  1),
    'ne': (-1,  2),
    'sw': ( 1, -2),
    'se': ( 2, -1),
}

# Functions

def make_tiles(stream=sys.stdin):
    tiles = {(0, 0): WHITE}

    for line in stream:
        flip_tile(line.strip(), tiles)

    return tiles

def flip_tile(steps, tiles):
    x, y = 0, 0

    while steps:
        if steps[0] in ('e', 'w'):
            direction, steps = steps[0] , steps[1:]
        else:
            direction, steps = steps[:2], steps[2:]

        dx, dy = DIRECTIONS[direction]
        x , y  = x + dx, y + dy

    if (x, y) in tiles:
        tiles[x, y] = (tiles[x, y] + 1) % 2
    else:
        tiles[x, y] = BLACK

# Main Execution

def main():
    tiles = make_tiles()
    print(sum(tiles.values()))

if __name__ == '__main__':
    main()

The second part was similar to what we have done for the cellular automata / grid problems previously. In this case, for each round / day, I just found all possible tiles by looking at their neighbors and then counted the number of black tiles and then applied the specified rules to form the next table of tiles.

--- day24-A.py	2020-12-24 09:55:04.694588021 -0500
+++ day24-B.py	2020-12-24 09:54:45.495574037 -0500
@@ -1,5 +1,6 @@
 #!/usr/bin/env python3
 
+import itertools
 import sys
 
 # Constants
@@ -43,10 +44,40 @@
     else:
         tiles[x, y] = BLACK
 
+def flatten(iterable):
+    return set(itertools.chain.from_iterable(iterable))
+
+def neighbors(x, y, tiles):
+    return [(x + dx, y + dy) for dx, dy in DIRECTIONS.values()]
+
+def count_black_neighbors(x, y, tiles):
+    return sum(tiles.get((nx, ny), WHITE) for nx, ny in neighbors(x, y, tiles))
+
+def flip_tiles(tiles):
+    new_tiles = {}
+    old_tiles = flatten(neighbors(x, y, tiles) for x, y in tiles)
+
+    for x, y in old_tiles:
+        black_neighbors = count_black_neighbors(x, y, tiles)
+        tile_color      = tiles.get((x, y), WHITE)
+
+        if tile_color == BLACK and (black_neighbors == 0 or black_neighbors > 2):
+            new_tiles[x, y] = WHITE
+        elif tile_color == WHITE and (black_neighbors == 2):
+            new_tiles[x, y] = BLACK
+        else:
+            new_tiles[x, y] = tile_color
+
+    return new_tiles
+
 # Main Execution
 
 def main():
     tiles = make_tiles()
+
+    for _ in range(100):
+        tiles = flip_tiles(tiles)
+
     print(sum(tiles.values()))

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::HashMap;

extern crate regex;
use regex::Regex;

extern crate point2d;
use point2d::point2d::Point2D;

// Hex Grids: https://www.redblobgames.com/grids/hexagons/

#[macro_use] extern crate lazy_static;
lazy_static! {
    static ref RE_PT: Regex = {
        Regex::new(r"^\((\-*\d),(\-*\d)\)$").unwrap()
    };
}

fn coordinates(input: &str) -> Point2D {
    //let re = Regex::new(r"^\((\-*\d),(\-*\d)\)$").unwrap();
    let caps = RE_PT.captures(&input).unwrap();
    Point2D { x: caps[1].parse().unwrap(), y: caps[2].parse().unwrap() }
}

fn neighbors(pt: &Point2D) -> Vec<Point2D> {
    vec![Point2D{ x: pt.x  , y: pt.y-1 },  // nw
         Point2D{ x: pt.x+1, y: pt.y-1 },  // ne
         Point2D{ x: pt.x+1, y: pt.y   },  // e
         Point2D{ x: pt.x  , y: pt.y+1 },  // se
         Point2D{ x: pt.x-1, y: pt.y+1 },  // sw
         Point2D{ x: pt.x-1, y: pt.y   }]  // w
}

fn adjacent_black(pt: &Point2D, map: &HashMap<Point2D,bool>) -> usize {
    neighbors(&pt).iter().map(|n| map.get(&n).unwrap_or(&false)).filter(|n| *n == &true).count()
}

fn map_extents(map: &HashMap<Point2D,bool>) -> (i64,i64,i64,i64) {
    let xmin = &map.keys().map(|&pt| pt.x).min().unwrap();
    let ymin = &map.keys().map(|&pt| pt.y).min().unwrap();
    let xmax = &map.keys().map(|&pt| pt.x).max().unwrap();
    let ymax = &map.keys().map(|&pt| pt.y).max().unwrap();
    (*xmin,*ymin,*xmax,*ymax)
}

fn expand_map(map: &mut HashMap<Point2D,bool>) {
    let temp = map.clone();
    for (pt,_) in temp.iter() {
        for neighbor in neighbors(pt) {
            match map.get(&neighbor) {
                Some(_) => {},
                None => { map.insert(neighbor, false); }
            }
        }
    }
}

fn day24(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };

    // Build map
    let mut map: HashMap<Point2D,bool> = HashMap::new();
    for line in input {
        let line = line
            .replace("se","(0,1)+")
            .replace("sw","(-1,1)+")
            .replace("nw","(0,-1)+")
            .replace("ne","(1,-1)+")
            .replace("e","(1,0)+")
            .replace("w","(-1,0)+");
        let line = format!("{}(0,0)",line);

        let pt = line.split("+").map(|coord| coordinates(coord)).sum::<Point2D>();
        let x = map.entry(pt).or_insert(false);
        *x = !*x;
    }

    // Part 1
    let part1 = map.iter().filter(|(_,t)| *t == &true).count();
    println!("Part 1: {}", part1); // 500

    // Part 2
    for _ in 0..100 {
        expand_map(&mut map);
        let current = map.clone();
        let (xmin,ymin,xmax,ymax) = map_extents(&current);
        for y in ymin..=ymax {
            for x in xmin..=xmax {
                let pt = Point2D { x: x, y: y};
                let adjacent_black = adjacent_black(&pt,&current);
                match &current.get(&Point2D { x: x, y: y}) {
                    Some(true) => {
                        // Black tile
                        if adjacent_black == 0 || adjacent_black > 2 { map.insert(pt,false); }
                    },
                    _ => {
                        // White tile
                        if adjacent_black == 2 { map.insert(pt,true); }
                    },
                }
            }
        }
    }

    // Part 2
    let part2 = map.iter().filter(|(_,t)| *t == &true).count();
    println!("Part 2: {}", part2); // 4280

    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    day24(&filename).unwrap();
}