9 votes

Day 17: Conway Cubes

Today's problem description: https://adventofcode.com/2020/day/17


Join the Tildes private leaderboard! You can do that on this page, by entering join code 730956-de85ce0c.

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

7 comments

  1. PapaNachos
    (edited )
    Link
    Part B took a bit to calculate, I'm not really sure how I would even go about speeding it up. Maybe preallocating space? Or an improved search method? As always, listening to eurobeat helps you be...

    Part B took a bit to calculate, I'm not really sure how I would even go about speeding it up. Maybe preallocating space? Or an improved search method?

    As always, listening to eurobeat helps you be better at both code and video games. It's a scientifically proven fact

    Day 17 Part A – Python

    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))
    
    Day 17 Part B – Python

    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')
    
    Tips and Commentary
    • 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.

    4 votes
  2. Nuolong
    Link
    Python Repo Link I really didn't feel like doing this problem at first, but it was nice to get through it without much debugging at all. The hardest part was starting, though something even harder...

    Python
    Repo Link

    I really didn't feel like doing this problem at first, but it was nice to get through it without much debugging at all. The hardest part was starting, though something even harder would be writing faster code! Behold my beautiful nested for loop code! Part 1 runs in about a second, while Part 2 runs in ~2 minutes.

    Part 2 Part 1 can be seen in my repo link. Didn't post it because it would be redundant. I just made a dictionary where key values were tuples of the coordinates, and values were either inactive ('.') or active ('#'). That's how I inserted the input. For the function I just brute force iterated through all coordinates to find each of their neighbor counts and change their values accordingly to the rules. For the hard-coded ranges (-15 to 15), I was just too lazy to do the math to find the most appropriate bounds. So I picked a high-enough number that would simulate the infinite bounds given the number of cycles we had to run.

    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()
    
    4 votes
  3. JRandomHacker
    Link
    I think the best feeling on an AoC problem is when you just know that your part 2 code is going to be a snap once you read the next half of the problem. C# Part 1 public override string...

    I think the best feeling on an AoC problem is when you just know that your part 2 code is going to be a snap once you read the next half of the problem.
    C#

    Part 1
    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)}";
    	}
    }
    
    Part 2
    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)}";
    	}
    }
    
    Helpers
    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);
    	}
    }
    
    Commentary Modifying part 1 for part 2 is literally just changing the Vec3s to Vec4s and adjusting the bounds-check.

    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.

    3 votes
  4. pnutzh4x0r
    Link
    Python Repo Link Part 1 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...

    Python

    Repo Link

    Part 1

    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 (diff)

    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
    
    3 votes
  5. nothis
    Link
    Python I really had fun with today's. I first naively checked all cubes in a 40x40x40 space (initially just 20x20x20 which apparently wasn't large enough after 6 cycles), which worked for part 1...

    Python

    I really had fun with today's. I first naively checked all cubes in a 40x40x40 space (initially just 20x20x20 which apparently wasn't large enough after 6 cycles), which worked for part 1 but got way too slow.

    For part 2, I first created a list of cubes near already active ones and only checked those. This certainly is not the most efficient way to do this but after 10 minutes or so, it spit out the correct 4D solution. I'm kinda tempted to revisit this later and look into a multi-threaded solution but for now it's a slow but working compromise.

    Sidenote: I've also switched to lower-case-and-underscore naming for variables and functions since that seems to be more popular than camel case for Python.

    Part 1+2
    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)
    
    2 votes
  6. Gyrfalcon
    Link
    Language: Julia Repository This one was neat. Using some careful typing I was able to reuse the majority of my code from part 1, and along with memoization, keep the run time very short. A first...

    This one was neat. Using some careful typing I was able to reuse the majority of my code from part 1, and along with memoization, keep the run time very short. A first run including compilation is about 8 seconds, with subsequent timed runs taking advantage of the cache completing in about half a second. I chose to use a dictionary to connect the locations with their values, which I think made things much easier, no worrying about preventing negative values or allocating extra space.

    Part 1
    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()
    
    Part 2 diff
    @@ -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)))
    
    2 votes
  7. jzimbel
    (edited )
    Link
    Elixir I get some kind of perverse enjoyment out of defining fully fleshed-out data structures for these grid problems rather than just attacking the problem in a quick-and-dirty way, so I created...

    Elixir

    I get some kind of perverse enjoyment out of defining fully fleshed-out data structures for these grid problems rather than just attacking the problem in a quick-and-dirty way, so I created two new, fully unit-tested, CharSpace and CharHyperspace modules to handle creating and updating the grid of cells for each part. This made my actual solution code very concise. It also runs... decently fast? Around 80ms for part1, 3.4s for part 2.

    I'm sure it would be possible to generalize the infinite grid concept for an arbitrary number of dimensions using macros (rather than making separate, nearly identical modules for 3D, 4D, etc), but I need some more practice with simpler macro-writing problems before trying this one.

    CharSpace module (3D infinite grid)
    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
    
    CharHyperspace module (4D infinite grid)
    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
    
    Parts 1 and 2
    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
    
    1 vote