Day 17: Conway Cubes

First I give myself 2 methods that help me deal with the neighbors. I only ever store the active cubes, since I didn't want to deal with a resizing grid.

Each generation of the simulation I go through each of the active cubes to find which of the neighbors I should care about checking. Then, I look at each of them and check their current status and how many active neighbors they have and update the new grid generation accordingly.

Once I'm done, the length of the active cube list is my answer

data = input_data.split('\n')

def gen_neighbors(x,y,z):
    x_list = [x-1, x, x+1]
    y_list = [y-1, y, y+1]
    z_list = [z-1, z, z+1]
    output = []
    for h in x_list:
        for j in y_list:
            for k in z_list:
                output.append((h,j,k))
    output.remove((x,y,z))
    return output
def check_active_neightbors(x,y,z):
    neighbors = gen_neighbors(x,y,z)
    active_count = 0
    for neighbor in neighbors:
        if neighbor in active_cubes:
            #print(f'Cube ({x}, {y}, {z}) is bordered by ({neighbor[0], neighbor[1], neighbor[2]})')
            active_count = active_count + 1
    return active_count


active_cubes = []

for indeY,row in enumerate(data):
    for indeX, val in enumerate(list(row)):
        if val == '#':
            active_cubes.append((indeX, indeY, 0))

round_count = 6
for i in range(round_count):
    potential_cubes = list(active_cubes)
    for cube in active_cubes:
        potential_cubes = potential_cubes + gen_neighbors(cube[0], cube[1], cube[2])
    potential_cubes = list(set(potential_cubes))
    
    new_active_cubes = []
    for cube in potential_cubes:
        active_neighbors = check_active_neightbors(cube[0], cube[1], cube[2])
        if cube in active_cubes:
            if active_neighbors == 2 or active_neighbors == 3:
                new_active_cubes.append(cube)
        else:
            if active_neighbors == 3:
                new_active_cubes.append(cube)
    active_cubes = new_active_cubes
print(len(active_cubes))

This is almost identical, except I added a 4th dimension 'w' per the instructions. And I added a nicer output at the end so that I could see the progress of the calculations. I was getting a bit nervous sitting ther waiting. I wasn't sure if it was going to take minutes or days.

data = input_data.split('\n')

def gen_neighbors(x,y,z,w):
    x_list = [x-1, x, x+1]
    y_list = [y-1, y, y+1]
    z_list = [z-1, z, z+1]
    w_list = [w-1, w, w+1]
    output = []
    for h in x_list:
        for j in y_list:
            for k in z_list:
                for l in w_list:
                    output.append((h,j,k,l))
    output.remove((x,y,z,w))
    return output
def check_active_neightbors(x,y,z,w):
    neighbors = gen_neighbors(x,y,z,w)
    active_count = 0
    for neighbor in neighbors:
        if neighbor in active_cubes:
            #print(f'Cube ({x}, {y}, {z}) is bordered by ({neighbor[0], neighbor[1], neighbor[2]})')
            active_count = active_count + 1
    return active_count


active_cubes = []

for indeY,row in enumerate(data):
    for indeX, val in enumerate(list(row)):
        if val == '#':
            active_cubes.append((indeX, indeY, 0, 0))

round_count = 6
for i in range(round_count):
    potential_cubes = list(active_cubes)
    for cube in active_cubes:
        potential_cubes = potential_cubes + gen_neighbors(cube[0], cube[1], cube[2], cube[3])
    potential_cubes = list(set(potential_cubes))
    
    new_active_cubes = []
    for cube in potential_cubes:
        active_neighbors = check_active_neightbors(cube[0], cube[1], cube[2], cube[3])
        if cube in active_cubes:
            if active_neighbors == 2 or active_neighbors == 3:
                new_active_cubes.append(cube)
        else:
            if active_neighbors == 3:
                new_active_cubes.append(cube)
    active_cubes = new_active_cubes
    print(f'Generation {i} Complete')
    print(f'{len(active_cubes)} cubes are currently active')

• This has some similarities to Day 11. You might be able to use some of what you learned there. The rules for this are simpler, but the grid itself is much more complex

• Part of the difficulty of this one is that you don't know how big your grid is going to be. Either you need to make it big enough to account for the entirety of the simulation's 6-step lifespan, or you need to come up with a way to resize it. Or you need to make it so you don't have a real grid at all. But the method you choose may dramatically affect your performance, which is especially important in part B

• I was anxious about how long part B was taking, so I went ahead and gave myself periodic status updates. That helped me know my performance was at least good enough to wait for without burning my code to the ground in pursuit of better optimization. I'm afraid of how long gen 7 would take though.

• This is based off of Conway's Game of Life which is a fairly cellular automata. Basically it simulates how various patterns propagate. People do really neat stuff with it

• The example initial state is known as a 'glider' and it's a basic pattern that can be generated in Conway's Game of Life. When using the default rules of the game in a 2D space, that pattern will repeat forever, slowly moving forward as it does. It's also used sometimes as an unofficial symbol for hackers.

Overall there's clearly a faster + smarter way to go about it. Like keeping track of only active cubes and their respective numbers of active neighbors, instead of iterating through all coordinates where I'm doing a lot of unnecessary comparisons. However, I just wanted to be done with this problem :)

import sys
from collections import defaultdict
import copy

def neighbors(space):
    new_space = copy.deepcopy(space)

    for x in range(-15, 15):
        for y in range(-15, 15):
            for z in range(-15, 15):
                for w in range(-15, 15):
                    count = 0
                    for dx in (-1, 0, 1):
                        for dy in (-1, 0, 1):
                            for dz in (-1, 0, 1):
                                for dw in (-1, 0, 1):
                                    if (dx or dy or dz or dw) and space.get((x + dx, y + dy, z + dz, w + dw), '.') == '#':
                                        count += 1
                    if space.get((x, y, z, w), '.') == '#' and not (2 <= count <= 3):
                        new_space[(x, y, z, w)] = '.'
                    elif space.get((x, y, z, w), '.') == '.' and count == 3:
                        new_space[(x, y, z, w)] = '#'

    return new_space

def main():
    space = defaultdict(str)

    for idx_1, line in enumerate(sys.stdin):
        for idx_2, val in enumerate(line.strip()):
            space[(idx_1, idx_2, 0, 0)] = val

    for x in range(6):
        space = neighbors(space)

    num = 0
    for s in space.values():
        if s == '#':
            num += 1

    print(num)


if __name__ == '__main__':
    main()

public override string SolvePart1()
{
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input17))
	{
		var board = new Dictionary<Vec3, bool>();
		string line;
		int yParse = 0;
		while ((line = fs.ReadLine()) != null)
		{
			for (int xParse = 0; xParse < line.Length; xParse++)
			{
				board.Add(new Vec3(xParse, yParse, 0), line[xParse] == '#');
			}
			yParse++;
		}

		var lowerBound = new Vec3(-1, -1, -1);
		var upperBound = new Vec3(8, 8, 1);

		bool[] boundsIncrease = new bool[6]; // Xlow, Xhigh, Ylow, Yhigh, Zlow, Zhigh
		for (int timeStep = 0; timeStep < 6; timeStep++)
		{
			var iterBoard = new Dictionary<Vec3, bool>();
			for (var z = lowerBound.Z; z <= upperBound.Z; z++)
			{
				for (var y = lowerBound.Y; y <= upperBound.Y; y++)
				{
					for (var x = lowerBound.X; x <= upperBound.X; x++)
					{
						var curr = new Vec3(x, y, z);
						var currState = board.ContainsKey(curr) && board[curr];
						var currNeighbors = curr.GetNeighbors();
						var neighborCount = currNeighbors.Sum(n => (board.ContainsKey(n) && board[n]) ? 1 : 0);

						var newState = (!currState && neighborCount == 3) || (currState && (neighborCount == 2 || neighborCount == 3));
						iterBoard.Add(curr, newState);

						if (newState)
						{
							if (x == lowerBound.X)
							{
								boundsIncrease[0] = true;
							}
							if (x == upperBound.X)
							{
								boundsIncrease[1] = true;
							}
							if (y == lowerBound.Y)
							{
								boundsIncrease[2] = true;
							}
							if (y == upperBound.Y)
							{
								boundsIncrease[3] = true;
							}
							if (z == lowerBound.Z)
							{
								boundsIncrease[4] = true;
							}
							if (z == upperBound.Z)
							{
								boundsIncrease[5] = true;
							}
						}
					}
				}
			}
			board = iterBoard;
			lowerBound = new Vec3(lowerBound.X - (boundsIncrease[0] ? 1 : 0), lowerBound.Y - (boundsIncrease[2] ? 1 : 0), lowerBound.Z - (boundsIncrease[4] ? 1 : 0));
			upperBound = new Vec3(upperBound.X + (boundsIncrease[1] ? 1 : 0), upperBound.Y + (boundsIncrease[3] ? 1 : 0), upperBound.Z + (boundsIncrease[5] ? 1 : 0));
		}
		return $"Total cells alive: {board.Values.Count(b => b)}";
	}
}

public override string SolvePart2()
{
	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input17))
	{
		var board = new Dictionary<Vec4, bool>();
		string line;
		int yParse = 0;
		while ((line = fs.ReadLine()) != null)
		{
			for (int xParse = 0; xParse < line.Length; xParse++)
			{
				board.Add(new Vec4(xParse, yParse, 0, 0), line[xParse] == '#');
			}
			yParse++;
		}

		var lowerBound = new Vec4(-1, -1, -1, -1);
		var upperBound = new Vec4(8, 8, 1, 1);

		bool[] boundsIncrease = new bool[8]; // Xlow, Xhigh, Ylow, Yhigh, Zlow, Zhigh, Wlow, Whigh
		for (int timeStep = 0; timeStep < 6; timeStep++)
		{
			var iterBoard = new Dictionary<Vec4, bool>();
			for (var w = lowerBound.W; w <= upperBound.W; w++)
			{
				for (var z = lowerBound.Z; z <= upperBound.Z; z++)
				{
					for (var y = lowerBound.Y; y <= upperBound.Y; y++)
					{
						for (var x = lowerBound.X; x <= upperBound.X; x++)
						{
							var curr = new Vec4(x, y, z, w);
							var currState = board.ContainsKey(curr) && board[curr];
							var currNeighbors = curr.GetNeighbors();
							var neighborCount = currNeighbors.Sum(n => (board.ContainsKey(n) && board[n]) ? 1 : 0);

							var newState = (!currState && neighborCount == 3) || (currState && (neighborCount == 2 || neighborCount == 3));
							iterBoard.Add(curr, newState);

							if (newState)
							{
								if (x == lowerBound.X)
								{
									boundsIncrease[0] = true;
								}
								if (x == upperBound.X)
								{
									boundsIncrease[1] = true;
								}
								if (y == lowerBound.Y)
								{
									boundsIncrease[2] = true;
								}
								if (y == upperBound.Y)
								{
									boundsIncrease[3] = true;
								}
								if (z == lowerBound.Z)
								{
									boundsIncrease[4] = true;
								}
								if (z == upperBound.Z)
								{
									boundsIncrease[5] = true;
								}
								if (w == lowerBound.W)
								{
									boundsIncrease[6] = true;
								}
								if (w == upperBound.W)
								{
									boundsIncrease[7] = true;
								}
							}
						}
					}
				}
			}
			board = iterBoard;
			lowerBound = new Vec4(lowerBound.X - (boundsIncrease[0] ? 1 : 0), lowerBound.Y - (boundsIncrease[2] ? 1 : 0), lowerBound.Z - (boundsIncrease[4] ? 1 : 0), lowerBound.W - (boundsIncrease[6] ? 1 : 0));
			upperBound = new Vec4(upperBound.X + (boundsIncrease[1] ? 1 : 0), upperBound.Y + (boundsIncrease[3] ? 1 : 0), upperBound.Z + (boundsIncrease[5] ? 1 : 0), upperBound.W + (boundsIncrease[7] ? 1 : 0));
		}
		return $"Total cells alive: {board.Values.Count(b => b)}";
	}
}

public class Vec3 : IEquatable<Vec3>
{
	public int X { get; set; }
	public int Y { get; set; }
	public int Z { get; set; }

	public Vec3(int x, int y, int z)
	{
		X = x;
		Y = y;
		Z = z;
	}

	public List<Vec3> GetNeighbors()
	{
		var offsets = new List<int>() { -1, 0, 1 };
		var ret = new List<Vec3>();
		foreach (var xOff in offsets)
		{
			foreach (var yOff in offsets)
			{
				foreach (var zOff in offsets)
				{
					if (!(xOff == 0 && yOff == 0 && zOff == 0))
					{
						ret.Add(new Vec3(X + xOff, Y + yOff, Z + zOff));
					}
				}
			}
		}
		return ret;
	}

	public override bool Equals(object obj)
	{
		return Equals(obj as Vec3);
	}

	public bool Equals(Vec3 other)
	{
		return other != null &&
			   X == other.X &&
			   Y == other.Y &&
			   Z == other.Z;
	}

	public override int GetHashCode()
	{
		return HashCode.Combine(X, Y, Z);
	}
}
public class Vec4 : IEquatable<Vec4>
{
	public int X { get; set; }
	public int Y { get; set; }
	public int Z { get; set; }
	public int W { get; set; }

	public Vec4(int x, int y, int z, int w)
	{
		X = x;
		Y = y;
		Z = z;
		W = w;
	}

	public List<Vec4> GetNeighbors()
	{
		var offsets = new List<int>() { -1, 0, 1 };
		var ret = new List<Vec4>();
		foreach (var xOff in offsets)
		{
			foreach (var yOff in offsets)
			{
				foreach (var zOff in offsets)
				{
					foreach (var wOff in offsets)
					{
						if (!(xOff == 0 && yOff == 0 && zOff == 0 && wOff == 0))
						{
							ret.Add(new Vec4(X + xOff, Y + yOff, Z + zOff, W + wOff));
						}
					}
				}
			}
		}
		return ret;
	}

	public override bool Equals(object obj)
	{
		return Equals(obj as Vec4);
	}

	public bool Equals(Vec4 other)
	{
		return other != null &&
			   X == other.X &&
			   Y == other.Y &&
			   Z == other.Z &&
			   W == other.W;
	}

	public override int GetHashCode()
	{
		return HashCode.Combine(X, Y, Z, W);
	}
}

I should probably refactor some of this into an AoC toolbox - both the VecN code and some of the automata stuff too. I also need to get with the times on C# and make the VecN types into structs - that would cut down some of the boilerplate, at least.

This was similar to the previous grid problem we did (which I am not a fan of), except instead of actually storing a grid, I maintained a set of only the active cubes. From there, it was just a matter of generating each of their neighbors and then checking them according to the rules specified in the problem.

My biggest hangup in working on the problem were my debugging prints after each cycle did not match their examples. I was trying to debug it cycle by cycle and comparing my print out to their example and it didn't match, so I spent a lot of time trying to figure out what was wrong. Eventually, I just let it run for all six cycles and realized my counts were the same (even if the visualization was different). This was annoying, but c'est la vie.

Once again, I made use of comprehensions and itertools.

import itertools
import sys

# Constants

ACTIVE   = '#'
INACTIVE = '.'

# Classes

class SparseSpace:
    def __init__(self, layer):
        self.actives = set([
            (x, y, 0)
            for y, row in enumerate(layer) for x, cube in enumerate(row)
            if cube == ACTIVE
        ])

    def count_neighbors(self, x, y, z):
        return sum(1 for neighbor in neighbors(x, y, z) if neighbor in self.actives)

    def cycle(self):
        new_actives = set()
        candidates  = list(self.actives) + flatten(
            neighbors(*cube) for cube in self.actives
        )

        for candidate in candidates:
            count = self.count_neighbors(*candidate)
            if candidate in self.actives and (count == 2 or count == 3):
                new_actives.add(candidate)
            elif candidate not in self.actives and (count == 3): 
                new_actives.add(candidate)

        self.actives = new_actives

# Functions

def read_layer(stream=sys.stdin):
    return [line.strip() for line in sys.stdin]

def flatten(iterable):
    return list(itertools.chain.from_iterable(iterable))

def neighbors(x, y, z):
    return (
        (x + dx, y + dy, z + dz)
        for dx, dy, dz in itertools.product((-1, 0, 1), repeat=3)
        if dx or dy or dz
    )

# Main Execution

def main():
    layer = read_layer()
    space = SparseSpace(layer)

    for cycle in range(1, 7):
        space.cycle()

    print(len(space.actives))

if __name__ == '__main__':
    main()

Part 2 was the same as Part 1 but with an extra dimension, so I've only provided a small diff here. I was pleasantly surprised to see my code finish only in about 5 seconds.

--- day17-A.py	2020-12-17 11:26:58.762164422 -0500
+++ day17-B.py	2020-12-17 11:31:00.010481412 -0500
@@ -13,13 +13,13 @@
 class SparseSpace:
     def __init__(self, layer):
         self.actives = set([
-            (x, y, 0)
+            (x, y, 0, 0)
             for y, row in enumerate(layer) for x, cube in enumerate(row)
             if cube == ACTIVE
         ])
 
-    def count_neighbors(self, x, y, z):
-        return sum(1 for neighbor in neighbors(x, y, z) if neighbor in self.actives)
+    def count_neighbors(self, x, y, z, w):
+        return sum(1 for neighbor in neighbors(x, y, z, w) if neighbor in self.actives)
 
     def cycle(self):
         new_actives = set()
@@ -44,11 +44,11 @@
 def flatten(iterable):
     return list(itertools.chain.from_iterable(iterable))
 
-def neighbors(x, y, z):
+def neighbors(x, y, z, w):
     return (
-        (x + dx, y + dy, z + dz)
-        for dx, dy, dz in itertools.product((-1, 0, 1), repeat=3)
-        if dx or dy or dz
+        (x + dx, y + dy, z + dz, w + dw)
+        for dx, dy, dz, dw in itertools.product((-1, 0, 1), repeat=4)
+        if dx or dy or dz or dw
     )
 
 # Main Execution

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


def read_cube_slice(cube_slice, dimension):
    active_cubes = []
    for x in range(0, len(cube_slice)):
        for y in range(0, len(cube_slice[0])):
            if(cube_slice[x][y] == "#"):
                if dimension == 3:
                    active_cubes.append([x, y, 0])
                elif dimension == 4:
                    active_cubes.append([x, y, 0, 0])
    return active_cubes


def find_adjacent(pos, dimension):
    adjacent = []
    for x in range(pos[0]-1, pos[0]+2):
        for y in range(pos[1]-1, pos[1]+2):
            for z in range(pos[2]-1, pos[2]+2):
                if dimension == 3:
                    if not([x, y, z] == pos):
                        adjacent.append([x, y, z])
                elif dimension == 4:
                    for w in range(pos[3]-1, pos[3]+2):
                        if not([x, y, z, w] == pos):
                            adjacent.append([x, y, z, w])
    return adjacent


def count_active_neighbors(pos, active_cubes, dimension):
    count = 0
    for x in range(pos[0]-1, pos[0]+2):
        for y in range(pos[1]-1, pos[1]+2):
            for z in range(pos[2]-1, pos[2]+2):
                if dimension == 3:
                    if (not([x, y, z] == pos)) and [x, y, z] in active_cubes:
                        count += 1
                elif dimension == 4:
                    for w in range(pos[3]-1, pos[3]+2):
                        if (not([x, y, z, w] == pos)) and [x, y, z, w] in active_cubes:
                            count += 1
    return count


def cycle(active_cubes, dimension):

    # find cubes near existing active cubes
    cubes_to_check = []
    for cube in active_cubes:
        adjacent_cubes = find_adjacent(cube, dimension)
        for adjacent_cube in adjacent_cubes:
            if not adjacent_cube in cubes_to_check:
                cubes_to_check.append(adjacent_cube)

    # check status for all cubes in cubes_to_check
    new_active_cubes = []
    for cube in cubes_to_check:
        count = count_active_neighbors(cube, active_cubes, dimension)
        if (cube in active_cubes and (count == 2 or count == 3)) or (not cube in active_cubes and count == 3):
            new_active_cubes.append(cube)
    return new_active_cubes


def cycles(cycle_count, active_cubes, dimension):
    for n in range(1, cycle_count + 1):
        active_cubes = cycle(active_cubes, dimension)
        print("Finished cycle", n)
    print("Active cubes after 6 cycles for",
          dimension, "dimensions:",  len(active_cubes))


active_cubes = read_cube_slice(cube_slice, 3)
cycles(6, active_cubes, 3)

active_cubes = read_cube_slice(cube_slice, 4)
cycles(6, active_cubes, 4)

using Memoize

function main()

    input = []
    open("Day17/input.txt") do fp
        input = readlines(fp)
    end

    map = Dict{Tuple{Int,Int,Int}, Int}()
    for (idx, row) in enumerate(input)
        for (jdx, char) in enumerate(row)
            if char == '#'
                map[(jdx, idx, 0)] = 1
            end
        end
    end

    simulate!(map, 6)
    println(sum(values(map)))

end

@memoize function nearest_neighbors(location)

    return ((i,j,k) for i in location[1]-1:location[1]+1
                    for j in location[2]-1:location[2]+1
                    for k in location[3]-1:location[3]+1
                    if (i, j, k) != location)
end

function num_active_neighbors(neighbors, map)
    return sum([get(map, neighbor, 0) for neighbor in neighbors])
end

function simulate!(map, rounds)

    for round in 1:rounds

        changes = Dict() # To minimize deepcopying
        curr_active = (key for (key, value) in map if value == 1)
        active_neighbors = Set((location for active in curr_active for location in nearest_neighbors(active)))
        
        for active in curr_active
            if !(1 < num_active_neighbors(nearest_neighbors(active), map) < 4)
                changes[active] = 0
            end
        end

        for neighbor in active_neighbors
            if num_active_neighbors(nearest_neighbors(neighbor), map) == 3
                changes[neighbor] = 1
            end
        end

        apply_changes!(map, changes)
    end
end

function apply_changes!(map, changes)
    for (location, change) in changes
        map[location] = change
    end
end

main()

@@ -7,7 +7,7 @@ function main()
         input = readlines(fp)
     end
 
-    map = Dict{Tuple{Int,Int,Int}, Int}()
+    map = Dict{NTuple{3,Int}, Int}()
     for (idx, row) in enumerate(input)
         for (jdx, char) in enumerate(row)
             if char == '#'
@@ -19,9 +19,21 @@ function main()
     simulate!(map, 6)
     println(sum(values(map)))
 
+    map_4d = Dict{NTuple{4,Int}, Int}()
+    for (idx, row) in enumerate(input)
+        for (jdx, char) in enumerate(row)
+            if char == '#'
+                map_4d[(jdx, idx, 0, 0)] = 1
+            end
+        end
+    end
+
+    simulate!(map_4d, 6)
+    println(sum(values(map_4d)))
+
 end
 
-@memoize function nearest_neighbors(location)
+@memoize function nearest_neighbors(location::NTuple{3,Int})
 
     return ((i,j,k) for i in location[1]-1:location[1]+1
                     for j in location[2]-1:location[2]+1
@@ -29,15 +41,25 @@ end
                     if (i, j, k) != location)
 end
 
+# There's gotta be a better way to do this lol
+@memoize function nearest_neighbors(location::NTuple{4,Int})
+
+    return ((i,j,k, l) for i in location[1]-1:location[1]+1
+                       for j in location[2]-1:location[2]+1
+                       for k in location[3]-1:location[3]+1
+                       for l in location[4]-1:location[4]+1
+                       if (i, j, k, l) != location)
+end
+
 function num_active_neighbors(neighbors, map)
     return sum([get(map, neighbor, 0) for neighbor in neighbors])
 end
 
-function simulate!(map, rounds)
+function simulate!(map::Dict{T,Int}, rounds) where T <: NTuple
 
     for round in 1:rounds
 
-        changes = Dict() # To minimize deepcopying
+        changes = Dict{T,Int}() # To minimize deepcopying
         curr_active = (key for (key, value) in map if value == 1)
         active_neighbors = Set((location for active in curr_active for location in nearest_neighbors(active)))

defmodule AdventOfCode.CharSpace do
  @moduledoc "Data structure representing an infinite 3D grid of characters by a map of {x, y, z} => char"

  alias __MODULE__, as: T

  @type t :: %T{
          grid: grid,
          empty_char: char
        }

  @typep grid :: %{coordinates => char}

  @type coordinates :: {integer, integer, integer}

  defstruct ~w[grid empty_char]a

  # List of coords that produce the 26 coordinates surrounding a given coord when added to it
  @adjacent_deltas for x <- -1..1,
                       y <- -1..1,
                       z <- -1..1,
                       not (x == 0 and y == 0 and z == 0),
                       do: {x, y, z}

  @spec from_input(String.t(), char) :: t()
  def from_input(input, empty_char \\ ?.) do
    charlists =
      input
      |> String.split()
      |> Enum.map(&String.to_charlist/1)

    grid =
      for {line, y} <- Enum.with_index(charlists),
          {char, x} <- Enum.with_index(line),
          into: %{},
          do: {{x, y, 0}, char}

    update(%T{empty_char: empty_char}, grid)
  end

  @doc "Gets the value at the given coordinates."
  @spec at(t(), coordinates) :: char
  def at(%T{} = t, coords) do
    Map.get(t.grid, coords, t.empty_char)
  end

  @doc "Applies `fun` to each cell in the CharSpace to produce a new CharSpace."
  @spec map(t(), ({coordinates, char} -> char)) :: t()
  def map(%T{} = t, fun) do
    grid = for({coords, _} = entry <- t.grid, into: %{}, do: {coords, fun.(entry)})

    update(t, grid)
  end

  @doc """
  Returns the number of cells in the CharSpace containing `char`.
  This returns `:infinity` when passed the CharSpace's empty char.
  """
  @spec count_chars(t(), char) :: non_neg_integer() | :infinity
  def count_chars(%T{empty_char: empty_char}, empty_char), do: :infinity

  def count_chars(%T{} = t, char) do
    Enum.count(t.grid, fn {_, c} -> c == char end)
  end

  @doc "Returns a list of values from the 26 cells adjacent to the one at `coords`."
  @spec adjacent_values(t(), coordinates) :: list(char)
  def adjacent_values(%T{} = t, coords) do
    @adjacent_deltas
    |> Enum.map(&sum_coordinates(coords, &1))
    |> Enum.map(&at(t, &1))
  end

  defp update(t, grid) do
    bounds = get_bounds(grid, t.empty_char)

    %{t | grid: fill(grid, bounds, t.empty_char)}
  end

  defp get_bounds(grid, empty_char) do
    [{x, y, z} | nonempties] = nonempty_coords(grid, empty_char)
    acc = {x..x, y..y, z..z}

    nonempties
    |> Enum.reduce(acc, &min_maxer/2)
    |> Tuple.to_list()
    |> Enum.map(&pad_range/1)
    |> List.to_tuple()
  end

  defp nonempty_coords(grid, empty_char) do
    for {coords, value} <- grid, not match?(^empty_char, value), do: coords
  end

  defp min_maxer({x, y, z}, {xmin..xmax, ymin..ymax, zmin..zmax}) do
    {min(x, xmin)..max(x, xmax), min(y, ymin)..max(y, ymax), min(z, zmin)..max(z, zmax)}
  end

  defp fill(grid, {x_bounds, y_bounds, z_bounds}, empty_char) do
    all_coords = for x <- x_bounds, y <- y_bounds, z <- z_bounds, do: {x, y, z}

    Enum.reduce(all_coords, grid, fn coords, g -> Map.put_new(g, coords, empty_char) end)
  end

  defp sum_coordinates({x1, y1, z1}, {x2, y2, z2}), do: {x1 + x2, y1 + y2, z1 + z2}

  defp pad_range(l..r), do: (l - 1)..(r + 1)
end

defmodule AdventOfCode.CharHyperspace do
  @moduledoc "Data structure representing an infinite 4D grid of characters by a map of {x, y, z, w} => char"

  alias __MODULE__, as: T

  @type t :: %T{
          grid: grid,
          empty_char: char
        }

  @typep grid :: %{coordinates => char}

  @type coordinates :: {integer, integer, integer, integer}

  defstruct ~w[grid empty_char]a

  # List of coords that produce the 80 coordinates surrounding a given coord when added to it
  @adjacent_deltas for x <- -1..1,
                       y <- -1..1,
                       z <- -1..1,
                       w <- -1..1,
                       not (x == 0 and y == 0 and z == 0 and w == 0),
                       do: {x, y, z, w}

  @spec from_input(String.t(), char) :: t()
  def from_input(input, empty_char \\ ?.) do
    charlists =
      input
      |> String.split()
      |> Enum.map(&String.to_charlist/1)

    grid =
      for {line, y} <- Enum.with_index(charlists),
          {char, x} <- Enum.with_index(line),
          into: %{},
          do: {{x, y, 0, 0}, char}

    update(%T{empty_char: empty_char}, grid)
  end

  @doc "Gets the value at the given coordinates."
  @spec at(t(), coordinates) :: char
  def at(%T{} = t, coords) do
    Map.get(t.grid, coords, t.empty_char)
  end

  @doc "Applies `fun` to each cell in the CharHyperspace to produce a new CharHyperspace."
  @spec map(t(), ({coordinates, char} -> char)) :: t()
  def map(%T{} = t, fun) do
    grid = for({coords, _} = entry <- t.grid, into: %{}, do: {coords, fun.(entry)})

    update(t, grid)
  end

  @doc """
  Returns the number of cells in the CharHyperspace containing `char`.

  This returns `:infinity` when passed the CharHyperspace's empty char.
  """
  @spec count_chars(t(), char) :: non_neg_integer() | :infinity
  def count_chars(%T{empty_char: empty_char}, empty_char), do: :infinity

  def count_chars(%T{} = t, char) do
    Enum.count(t.grid, fn {_, c} -> c == char end)
  end

  @doc "Returns a list of values from the 80 cells adjacent to the one at `coords`."
  @spec adjacent_values(t(), coordinates) :: list(char)
  def adjacent_values(%T{} = t, coords) do
    @adjacent_deltas
    |> Enum.map(&sum_coordinates(coords, &1))
    |> Enum.map(&at(t, &1))
  end

  defp update(t, grid) do
    bounds = get_bounds(grid, t.empty_char)

    %{t | grid: fill(grid, bounds, t.empty_char)}
  end

  defp get_bounds(grid, empty_char) do
    [{x, y, z, w} | nonempties] = nonempty_coords(grid, empty_char)
    acc = {x..x, y..y, z..z, w..w}

    nonempties
    |> Enum.reduce(acc, &min_maxer/2)
    |> Tuple.to_list()
    |> Enum.map(&pad_range/1)
    |> List.to_tuple()
  end

  defp nonempty_coords(grid, empty_char) do
    for {coords, value} <- grid, not match?(^empty_char, value), do: coords
  end

  defp min_maxer({x, y, z, w}, {xmin..xmax, ymin..ymax, zmin..zmax, wmin..wmax}) do
    {min(x, xmin)..max(x, xmax), min(y, ymin)..max(y, ymax), min(z, zmin)..max(z, zmax),
     min(w, wmin)..max(w, wmax)}
  end

  defp fill(grid, {x_bounds, y_bounds, z_bounds, w_bounds}, empty_char) do
    all_coords = for x <- x_bounds, y <- y_bounds, z <- z_bounds, w <- w_bounds, do: {x, y, z, w}

    Enum.reduce(all_coords, grid, fn coords, g -> Map.put_new(g, coords, empty_char) end)
  end

  defp sum_coordinates({x1, y1, z1, w1}, {x2, y2, z2, w2}),
    do: {x1 + x2, y1 + y2, z1 + z2, w1 + w2}

  defp pad_range(l..r), do: (l - 1)..(r + 1)
end

defmodule AdventOfCode.Day17 do
  alias AdventOfCode.{CharHyperspace, CharSpace}

  def part1(args) do
    args
    |> CharSpace.from_input()
    |> stream_conway()
    |> Enum.at(6)
    |> CharSpace.count_chars(?#)
  end

  def part2(args) do
    args
    |> CharHyperspace.from_input()
    |> stream_conway()
    |> Enum.at(6)
    |> CharHyperspace.count_chars(?#)
  end

  defp stream_conway(grid) do
    Stream.iterate(grid, &next_cycle/1)
  end

  defp next_cycle(%grid_module{} = grid) do
    grid_module.map(grid, fn
      {coords, ?#} ->
        if count_adjacent_actives(grid, coords) in 2..3, do: ?#, else: ?.

      {coords, ?.} ->
        if count_adjacent_actives(grid, coords) == 3, do: ?#, else: ?.
    end)
  end

  defp count_adjacent_actives(%grid_module{} = grid, coords) do
    grid
    |> grid_module.adjacent_values(coords)
    |> Enum.count(&(&1 == ?#))
  end
end