13 votes

Day 11: Seating System

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


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>

14 comments

  1. JRandomHacker
    Link
    This was a fun one. I love me a good cellular automata. C# Part 1 public override string SolvePart1() { var board = new SeatCell[STRIDE * ROWS]; using (var fs = new...

    This was a fun one. I love me a good cellular automata.
    C#

    Part 1
    public override string SolvePart1()
    {
    	var board = new SeatCell[STRIDE * ROWS];
    	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input11))
    	{
    		var row = 0;
    		string line;
    		while ((line = fs.ReadLine()) != null)
    		{
    			for (int col = 0; col < line.Length; col++)
    			{
    				board[row * STRIDE + col] = new SeatCell(line[col]);
    			}
    			row++; 
    		}
    	}
    
    	bool done = false;
    	while (!done)
    	{
    		done = true;
    		var newBoard = new SeatCell[STRIDE * ROWS];
    		for (int i = 0; i < newBoard.Length; i++)
    		{
    			var neighbors = GetAllNeighbors(i);
    			var neighborCount = neighbors.Select(n => board[n]).Count(seat => seat.Current == SeatCell.State.FILLED);
    
    			if (board[i].Current == SeatCell.State.EMPTY && neighborCount == 0)
    			{
    				done = false;
    				newBoard[i] = new SeatCell('#');
    			}
    			else if (board[i].Current == SeatCell.State.FILLED && neighborCount >= 4)
    			{
    				done = false;
    				newBoard[i] = new SeatCell('L');
    			}
    			else
    			{
    				newBoard[i] = board[i];
    			}
    		}
    		board = newBoard;
    	}
    	return $"{board.Count(seat => seat.Current == SeatCell.State.FILLED)} filled seats";
    }
    
    Part 2
    public override string SolvePart2()
    {
    	var board = new SeatCell[STRIDE * ROWS];
    	using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input11))
    	{
    		var row = 0;
    		string line;
    		while ((line = fs.ReadLine()) != null)
    		{
    			for (int col = 0; col < line.Length; col++)
    			{
    				board[row * STRIDE + col] = new SeatCell(line[col]);
    			}
    			row++; 
    		}
    	}
    
    	bool done = false;
    	while (!done)
    	{
    		done = true;
    		var newBoard = new SeatCell[STRIDE * ROWS];
    		for (int i = 0; i < newBoard.Length; i++)
    		{
    			var neighbors = GetAllNeighborsSighted(i, board);
    			var neighborCount = neighbors.Select(n => board[n]).Count(seat => seat.Current == SeatCell.State.FILLED);
    
    			if (board[i].Current == SeatCell.State.EMPTY && neighborCount == 0)
    			{
    				done = false;
    				newBoard[i] = new SeatCell('#');
    			}
    			else if (board[i].Current == SeatCell.State.FILLED && neighborCount >= 5)
    			{
    				done = false;
    				newBoard[i] = new SeatCell('L');
    			}
    			else
    			{
    				newBoard[i] = board[i];
    			}
    		}
    		board = newBoard;
    	}
    	return $"{board.Count(seat => seat.Current == SeatCell.State.FILLED)} filled seats";
    }
    
    Helpers
    public List<int> GetAllNeighbors(int center)
    {
    	var ret = new List<int>();
    	var hasTop = center >= STRIDE;
    	var hasBottom = center < (ROWS - 1) * STRIDE;
    	var hasLeft = center % STRIDE != 0;
    	var hasRight = center % STRIDE != STRIDE - 1;
    
    	if (hasTop && hasLeft)
    		ret.Add(center - STRIDE - 1);
    	if (hasTop)
    		ret.Add(center - STRIDE);
    	if (hasTop && hasRight)
    		ret.Add(center - STRIDE + 1);
    	if (hasLeft)
    		ret.Add(center - 1);
    	if (hasRight)
    		ret.Add(center + 1);
    	if (hasBottom && hasLeft)
    		ret.Add(center + STRIDE - 1);
    	if (hasBottom)
    		ret.Add(center + STRIDE);
    	if (hasBottom && hasRight)
    		ret.Add(center + STRIDE + 1);
    
    	return ret;
    }
    public List<int> GetAllNeighborsSighted(int center, SeatCell[] board)
    {
    	var ret = new List<int>();
    	Func<int, bool> hasTop = (i) => i >= STRIDE;
    	Func<int, bool> hasBottom = (i) => i < (ROWS - 1) * STRIDE;
    	Func<int, bool> hasLeft = (i) => i % STRIDE != 0;
    	Func<int, bool> hasRight = (i) => i % STRIDE != STRIDE - 1;
    
    	var temp = center;
    	while (hasTop(temp))
    	{
    		temp -= STRIDE;
    		if (board[temp].Current != SeatCell.State.FLOOR)
    		{
    			ret.Add(temp);
    			break;
    		}
    	}
    	temp = center;
    	while (hasTop(temp) && hasLeft(temp))
    	{
    		temp -= (STRIDE + 1);
    		if (board[temp].Current != SeatCell.State.FLOOR)
    		{
    			ret.Add(temp);
    			break;
    		}
    	}
    	temp = center;
    	while (hasTop(temp) && hasRight(temp))
    	{
    		temp -= (STRIDE - 1);
    		if (board[temp].Current != SeatCell.State.FLOOR)
    		{
    			ret.Add(temp);
    			break;
    		}
    	}
    	temp = center;
    	while (hasLeft(temp))
    	{
    		temp -= 1;
    		if (board[temp].Current != SeatCell.State.FLOOR)
    		{
    			ret.Add(temp);
    			break;
    		}
    	}
    	temp = center;
    	while (hasRight(temp))
    	{
    		temp += 1;
    		if (board[temp].Current != SeatCell.State.FLOOR)
    		{
    			ret.Add(temp);
    			break;
    		}
    	}
    	temp = center;
    	while (hasBottom(temp))
    	{
    		temp += STRIDE;
    		if (board[temp].Current != SeatCell.State.FLOOR)
    		{
    			ret.Add(temp);
    			break;
    		}
    	}
    	temp = center;
    	while (hasBottom(temp) && hasLeft(temp))
    	{
    		temp += (STRIDE - 1);
    		if (board[temp].Current != SeatCell.State.FLOOR)
    		{
    			ret.Add(temp);
    			break;
    		}
    	}
    	temp = center;
    	while (hasBottom(temp) && hasRight(temp))
    	{
    		temp += (STRIDE + 1);
    		if (board[temp].Current != SeatCell.State.FLOOR)
    		{
    			ret.Add(temp);
    			break;
    		}
    	}
    	return ret;
    }
    
    public class SeatCell
    {
    	public enum State { FLOOR, EMPTY, FILLED }
    
    	public State Current { get; set; }
    	public SeatCell(char c)
    	{
    		switch (c)
    		{
    			case '.':
    				Current = State.FLOOR;
    				break;
    			case 'L':
    				Current = State.EMPTY;
    				break;
    			case '#':
    				Current = State.FILLED;
    				break;
    			default:
    				throw new Exception();
    		}
    	}
    }
    
    Commentary

    This was a satisfying one. The part1/part2 solvers themselves are identical, aside from the "neighbor list" helper and the "seat-empties" count.

    There's definitely a cleaner way to do the line-of-sight search for part 2, but I wanted to get something down quickly.

    4 votes
  2. PapaNachos
    (edited )
    Link
    This one ended up being really annoying. Mostly because I missed one critical part of the rules in part B, so I spend like an hour tracking down a bug that wasn't there. FML. Oh well, more time...

    This one ended up being really annoying. Mostly because I missed one critical part of the rules in part B, so I spend like an hour tracking down a bug that wasn't there. FML.

    Oh well, more time spent writing code means more time listening to eurobeat.

    And it was an interesting problem, I just wish I had read the instructions more carefully.

    Day 11 Part A – Python

    For this one I made a list that stored the vector information for one step in each direction. I just stepped through it to find if the seat in each direction was occupied or empty (or out of bounds. It's also important to change the entire grid at the same time. If you overwrite it while you're still working on it, you'll fuck everything up. Rather than checking if my seat arrangement was the same, I just made sure I was using a hashable type and stored a list of hashes which I could compare against

    #seats = tuple(test_input.split('\n'))
    seats = tuple(data_input.split('\n'))
    
    width = len(seats)
    height = len(seats[0])
    
    print(width)
    print(height)
    
    one_step_from_seatden = [(0,1),(1,0),(1,1),(0,-1),(-1,0),(-1,-1),(-1,1),(1,-1)]
    
    def check_surrounding(x,y,seats):
        count = 0
        for step in one_step_from_seatden:
            x_step = x + step[0]
            y_step = y + step[1]
            if x_step < width and y_step < height and x_step >= 0 and y_step >= 0:
                if seats[x_step][y_step] == '#':
                    count = count + 1
        return count
    
    def iterate_seats(seats):
        new_seats = []
        for x in range(width):
            new_row = []
            for y in range(height):
                seat_count = check_surrounding(x,y,seats)
                if seats[x][y] == 'L' and seat_count == 0:
                    new_row.append('#')
                elif seats[x][y] == '#' and seat_count >= 4:
                    new_row.append('L')
                else:
                    new_row.append(seats[x][y])
            new_seats.append(tuple(new_row))
        return new_seats
    
    hash_list = []
    while True:
        seat_hash = hash(seats)
        if seat_hash in hash_list:
            break
        else:
            seats = tuple(iterate_seats(seats))
            hash_list.append(seat_hash)
    print(len(hash_list))
    
    seat_count = 0
    for row in seats:
        seat_count = seat_count + row.count('#')
    print(seat_count)
    
    Day 11 Part B – Python For this one I converted my check surroundings method to keep stepping in a direction until it found a seat or exited a grid.... then after an hour of searching I added a check to make it stop if found an empty seat. I missed that portion of the rules. FFFFFUUUUCCCCCKKKK.

    I also shoved a couple of debugging tools in there that I made while searching for why my shit wasn't working.

    #seats = tuple(test_input.split('\n'))
    seats = tuple(data_input.split('\n'))
    
    width = len(seats)
    height = len(seats[0])
    
    print(width)
    print(height)
    
    one_step_from_seatden = [(0,1),(1,0),(1,1),(0,-1),(-1,0),(-1,-1),(-1,1),(1,-1)]
    
    def check_surrounding(x,y,seats):
        count = 0
        for step in one_step_from_seatden:
            seat_found = False
            x_step = x + step[0]
            y_step = y + step[1]
            while x_step < width and y_step < height and x_step >= 0 and y_step >= 0 and seat_found == False:
                if seats[x_step][y_step] == '#':
                    seat_found = True
                    count = count + 1
                elif seats[x_step][y_step] == 'L':
                    seat_found = True
                else:
                    x_step = x_step + step[0]
                    y_step = y_step + step[1]
        return count
    def print_seats(seats):
        for row in seats:
            print(''.join(row))
    
    def iterate_seats(seats):
        new_seats = []
        #count_grid = []
        for x in range(width):
            new_row = []
            count_row = []
            for y in range(height):
                seat_count = check_surrounding(x,y,seats)
                #count_row.append(str(seat_count))
                if seats[x][y] == 'L' and seat_count == 0:
                    new_row.append('#')
                elif seats[x][y] == '#' and seat_count >= 5:
                    new_row.append('L')
                else:
                    new_row.append(seats[x][y])
            new_seats.append(tuple(new_row))
            #count_grid.append(count_row)
        #print_seats(count_grid)
        return new_seats
    
    hash_list = []
    while True:
        #print_seats(seats)
        #print(check_surrounding(0,0,seats))
        seat_hash = hash(seats)
        #print(seat_hash)
        if seat_hash in hash_list:
            break
        else:
            seats = tuple(iterate_seats(seats))
            hash_list.append(seat_hash)
    print(len(hash_list))
    
    seat_count = 0
    for row in seats:
        seat_count = seat_count + row.count('#')
    print(seat_count)
    
    Tips and Commentary
    • Read the instructions carefully. Read them again. One more time for good measure. If you get stuck, go read the instructions again. Seriously, I wasted like an hour because I misunderstood one of the rules

    • You can deal with this grid in the same way you dealt with your grid on day 3, reuse your own code shamelessly

    • Hashing is a technique of converting anything into a unique* number called a hash. If you convert something into a hash and store the hash, you can then compare other objects to that hash. If the hashes match you have the same thing
      *Not technically unique, but a good hash function will rarely have duplicates when it shouldn't. These false duplicates are called collisions

    • Make sure not to update your seat arrangement until you're finished doing all your calculations. If you make changes mid-operation, the incoming or outgoing people will mess up your results

    • Make sure you don't have your x and y coordinates swapped

    4 votes
  3. Nuolong
    Link
    Python I wasn't a big fan of this problem! My solutions are admittedly not the best, but they worked out in the end and they're easy for me to understand. Will definitely look forward to seeing...

    Python
    I wasn't a big fan of this problem! My solutions are admittedly not the best, but they worked out in the end and they're easy for me to understand. Will definitely look forward to seeing others' better solutions. It was especially difficult for me to debug the program (in one instance, I was missing a critical rule in part B, like @PapaNachos wrote). My incompetent reading strikes again!

    Repo link

    Part 1 I padded the entire seating matrix with floors, just because I didn't want to have to deal with special cases for the edge seats. Though there probably is just be an entirely easier way to solve this problem, I decided to go with this. Then I used a boolean flag so that I could keep running my function until equilibrium.
    #!/usr/bin/env python3
    
    import sys
    
    INPUT_COLS = 92
    INPUT_ROWS = 99
    
    # calculates new matrix of seats. marks if any changes were made
    def adjacents(seats):
        adj_mat = [['.' for _ in range(INPUT_COLS + 2)]]
        changed = False
        for i in range(1, INPUT_ROWS + 1):
            row = []
            for j in range(1, INPUT_COLS + 1):
                count = 0
    
                if seats[i-1][j-1] == '#':
                    count += 1
                if seats[i+1][j] == '#':
                    count += 1
                if seats[i+1][j-1] == '#':
                    count += 1
                if seats[i][j-1] == '#':
                    count += 1
                if seats[i][j+1] == '#':
                    count += 1
                if seats[i-1][j] == '#':
                    count += 1
                if seats[i-1][j+1] == '#':
                    count += 1
                if seats[i+1][j+1] == '#':
                    count += 1
    
                if seats[i][j] == 'L' and not count:
                    row.append('#')
                    changed = True
                elif seats[i][j] == '#' and count >= 4:
                    row.append('L')
                    changed = True
                else:
                    row.append(seats[i][j])
    
            adj_mat.append(["."] + row + ["."])
    
        adj_mat.append(['.' for _ in range(INPUT_COLS + 2)])
    
        return adj_mat, changed
    
    # count num of occupied seats
    def count_occ(seats):
        count = 0
        for i in range(1, INPUT_ROWS + 1):
            for j in range(1, INPUT_COLS + 1):
                if seats[i][j] == '#':
                    count += 1
    
        return count
    
    def main():
    
        # read input into 2D matrix, pad it with "floor"
        seats = [['.' for _ in range(INPUT_COLS + 2)]]
    
        for _ in range(INPUT_ROWS):
            seats.append(["."] + list(sys.stdin.readline().strip()) + ["."])
    
        seats.append(['.' for _ in range(INPUT_COLS + 2)])
    
        # flag
        changed = True
        while changed:
            seats, changed = adjacents(seats)
    
        print(count_occ(seats))
    
    if __name__ == '__main__':
        main()
    
    Part 2 A similar approach to part 1 with padding and a flag system for handling the equilibrium. The important rule I missed was in regards to how an empty seat blocks off the sight of an occupied seat. As a result, I wasted time trying to debug my program.
    #!/usr/bin/env python3
    
    import sys
    
    INPUT_COLS = 92
    INPUT_ROWS = 99
    
    # calculates new matrix of seats. marks if any changes were made
    def sights(seats):
        adj_mat = [['.' for _ in range(INPUT_COLS + 2)]]
        changed = False
        for i in range(1, INPUT_ROWS + 1):
            row = []
            for j in range(1, INPUT_COLS + 1):
                count = 0
    
                # nw
                x = i - 1
                y = j - 1
                while x and y:
                    if seats[x][y] == "L":
                        break
                    elif seats[x][y] == "#":
                        count += 1
                        break
                    x -= 1
                    y -= 1
    
                # n
                x = i - 1
                y = j
                while x:
                    if seats[x][y] == "L":
                        break
                    elif seats[x][y] == "#":
                        count += 1
                        break
                    x -= 1
    
                # ne
                x = i - 1
                y = j + 1
                while x and y != INPUT_COLS + 1:
                    if seats[x][y] == "L":
                        break
                    elif seats[x][y] == "#":
                        count += 1
                        break
                    x -= 1
                    y += 1
    
                # e
                x = i
                y = j + 1
                while y != INPUT_COLS + 1:
                    if seats[x][y] == "L":
                        break
                    elif seats[x][y] == "#":
                        count += 1
                        break
                    y += 1
    
                # se
                x = i + 1
                y = j + 1
                while x != INPUT_ROWS + 1 and y != INPUT_COLS + 1:
                    if seats[x][y] == "L":
                        break
                    elif seats[x][y] == "#":
                        count += 1
                        break
                    x += 1
                    y += 1
    
                # s
                x = i + 1
                y = j
                while x != INPUT_ROWS + 1:
                    if seats[x][y] == "L":
                        break
                    elif seats[x][y] == "#":
                        count += 1
                        break
                    x += 1
    
                # sw
                x = i + 1
                y = j - 1
                while x != INPUT_ROWS + 1 and y:
                    if seats[x][y] == "L":
                        break
                    elif seats[x][y] == "#":
                        count += 1
                        break
                    x += 1
                    y -= 1
    
                # w
                x = i
                y = j - 1
                while y:
                    if seats[x][y] == "L":
                        break
                    elif seats[x][y] == "#":
                        count += 1
                        break
                    y -= 1
    
                if seats[i][j] == 'L' and not count:
                    row.append('#')
                    changed = True
                elif seats[i][j] == '#' and count >= 5:
                    row.append('L')
                    changed = True
                else:
                    row.append(seats[i][j])
    
            adj_mat.append(["."] + row + ["."])
    
        adj_mat.append(['.' for _ in range(INPUT_COLS + 2)])
    
        return adj_mat, changed
    
    # count num of occupied seats
    def count_occ(seats):
        count = 0
        for i in range(1, INPUT_ROWS + 1):
            for j in range(1, INPUT_COLS + 1):
                if seats[i][j] == '#':
                    count += 1
    
        return count
    
    def main():
    
        # read input into 2D matrix, pad it with "floor"
        seats = [['.' for _ in range(INPUT_COLS + 2)]]
    
        for _ in range(INPUT_ROWS):
            seats.append(["."] + list(sys.stdin.readline().strip()) + ["."])
    
        seats.append(['.' for _ in range(INPUT_COLS + 2)])
    
        # flag
        changed = True
        while changed:
            seats, changed = sights(seats)
    
        print(count_occ(seats))
    
    if __name__ == '__main__':
        main()
    
    4 votes
  4. pnutzh4x0r
    Link
    Python Repo Link Part 1 This was pretty straightforward. The only trick I used was to pad the grid with extra floor cells to avoid having to do boundary checks. import collections import copy...

    Python

    Repo Link

    Part 1

    This was pretty straightforward. The only trick I used was to pad the grid with extra floor cells to avoid having to do boundary checks.

    import collections
    import copy
    import sys
    
    # Constants
    
    EMPTY     = 'L'
    OCCUPIED  = '#'
    FLOOR     = '.'
    THRESHOLD = 4
    
    # Functions
    
    def read_grid(stream=sys.stdin):
        grid = []
    
        for line in stream:
            grid.append([FLOOR] + list(line.strip()) + [FLOOR])
    
        grid.insert(0, list(FLOOR * len(grid[0])))
        grid.append(grid[0])
    
        return grid
    
    def count_occupied(grid):
        return sum(row.count(OCCUPIED) for row in grid)
    
    def count_neighbors(grid, row, col):
        count = 0
    
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                if (dx or dy) and (grid[row + dx][col + dy] == OCCUPIED):
                    count += 1
    
        return count
    
    def simulate(old_grid):
        width    = len(old_grid[0]) - 1
        height   = len(old_grid) - 1
        new_grid = copy.deepcopy(old_grid)
    
        for row in range(1, height):
            for col in range(1, width):
                neighbors = count_neighbors(old_grid, row, col)
                if old_grid[row][col] == EMPTY and neighbors == 0:
                    new_grid[row][col] = OCCUPIED
                elif old_grid[row][col] == OCCUPIED and neighbors >= THRESHOLD:
                    new_grid[row][col] = EMPTY
    
        return new_grid
    
    # Main Execution
    
    def main():
        old_grid = read_grid()
        new_grid = simulate(old_grid)
    
        while count_occupied(old_grid) != count_occupied(new_grid):
            old_grid = new_grid
            new_grid = simulate(old_grid)
    
        print(count_occupied(new_grid))
    
    if __name__ == '__main__':
        main()
    
    Part 2

    For this part, I only had to modify the threshold for flipping seats and added a search_direction function to check for occupied or empty seats in all eight directions (rather than adjacent cells).

    --- day11-A.py	2020-12-11 08:23:32.798334763 -0500
    +++ day11-B.py	2020-12-11 08:29:50.231573314 -0500
    @@ -9,7 +9,7 @@
     EMPTY     = 'L'
     OCCUPIED  = '#'
     FLOOR     = '.'
    -THRESHOLD = 4
    +THRESHOLD = 5
     
     # Functions
     
    @@ -32,11 +32,26 @@
     
         for dx in (-1, 0, 1):
             for dy in (-1, 0, 1):
    -            if (dx or dy) and (grid[row + dx][col + dy] == OCCUPIED):
    +            if (dx or dy) and search_direction(grid, row, col, dx, dy):
                     count += 1
     
         return count
     
    +def search_direction(grid, row, col, dx, dy):
    +    width  = len(grid[0]) - 1
    +    height = len(grid) - 1
    +
    +    while (0 < row < height) and (0 < col < width):
    +        row += dx
    +        col += dy
    +
    +        if grid[row][col] == OCCUPIED:
    +            return True
    +        elif grid[row][col] == EMPTY:
    +            return False
    +
    +    return False
    +
     def simulate(old_grid):
         width    = len(old_grid[0]) - 1
         height   = len(old_grid) - 1
    
    4 votes
  5. Crestwave
    Link
    I was too tired to think of a clean solution for this; I might clean it up tomorrow and usually wait to post until then, but I thought it would be fun to post the completely unedited solutions!...

    I was too tired to think of a clean solution for this; I might clean it up tomorrow and usually wait to post until then, but I thought it would be fun to post the completely unedited solutions! Part 1 and part 2 take over 10 and 17 seconds respectively to process my input. :)

    I also missed the rule @PapaNachos pointed out, but thankfully it didn't take me long to debug since the example had step-by-step states. Really, the coverage of the examples is a huge part in determining how hard it is for me to solve it; the passport one took me a while because I passed all the examples immediately but failed the actual input in ~5 distinct ways!

    (My choice of music was evermore and it kept me distracted enough to go through with my hacky solutions)

    Part 1
    #!/usr/bin/awk -f
    {
    	chars = split($0, char, "")
    	for (i = 1; i <= chars; ++i)
    		layout[i, NR] = char[i]
    }
    
    END {
    	for (i in layout)
    		change[i] = layout[i]
    
    	for (;;) {
    		state = 0
    		for (i in layout) {
    			occupied = 0
    			split(i, xy, SUBSEP)
    
    			for (x = xy[1]-1; x <= xy[1]+1; ++x)
    				for (y = xy[2]-1; y <= xy[2]+1; ++y)
    					if (layout[x, y] == "#")
    						occupied += 1
    	
    			if (layout[i] == "L") {
    				if (! occupied) {
    					change[i] = "#"
    					state = 1
    				}
    			} else if (layout[i] == "#") {
    				if (occupied > 4) {
    					change[i] = "L"
    					state = 1
    				}
    			}
    		}
    
    		for (i in change)
    			layout[i] = change[i]
    
    		if (! state)
    			break
    	}
    
    	occupied = 0
    	for (i in layout)
    		if (layout[i] == "#")
    			occupied += 1
    
    	print occupied
    }
    
    Part 2
    #!/usr/bin/awk -f
    {
    	chars = split($0, char, "")
    	for (i = 1; i <= chars; ++i) {
    		layout[i, NR] = char[i]
    	}
    }
    
    END {
    	for (y = 1; y <= NR; ++y) {
    		for (x = 1; x <= chars; ++x) {
    			printf("%s", layout[x, y])
    		}
    		print ""
    	}
    	
    	print ""
    	for (i in layout)
    		change[i] = layout[i]
    
    	for (;;) {
    		state = 0
    		for (i in layout) {
    			occupied = 0
    			split(i, xy, SUBSEP)
    
    			for (j = 1; layout[xy[1]-j, xy[2]-j] != ""; ++j) {
    				if (layout[xy[1]-j, xy[2]-j] == "#") {
    					occupied += 1
    					break
    				}
    				if (layout[xy[1]-j, xy[2]-j] == "L") {
    					break
    				}
    			}
    
    			for (j = 1; layout[xy[1]+j, xy[2]-j] != ""; ++j) {
    				if (layout[xy[1]+j, xy[2]-j] == "#") {
    					occupied += 1
    					break
    				}
    				if (layout[xy[1]+j, xy[2]-j] == "L") {
    					break
    				}
    			}
    
    			for (j = 1; layout[xy[1]-j, xy[2]+j] != ""; ++j) {
    				if (layout[xy[1]-j, xy[2]+j] == "#") {
    					occupied += 1
    					break
    				}
    				if (layout[xy[1]-j, xy[2]+j] == "L") {
    					break
    				}
    			}
    
    			for (j = 1; layout[xy[1]+j, xy[2]+j] != ""; ++j) {
    				if (layout[xy[1]+j, xy[2]+j] == "#") {
    					occupied += 1
    					break
    				}
    				if (layout[xy[1]+j, xy[2]+j] == "L") {
    					break
    				}
    			}
    
    			for (j = 1; layout[xy[1]-j, xy[2]] != ""; ++j) {
    				if (layout[xy[1]-j, xy[2]] == "#") {
    					occupied += 1
    					break
    				}
    				if (layout[xy[1]-j, xy[2]] == "L") {
    					break
    				}
    			}
    
    			for (j = 1; layout[xy[1]+j, xy[2]] != ""; ++j) {
    				if (layout[xy[1]+j, xy[2]] == "#") {
    					occupied += 1
    					break
    				}
    				if (layout[xy[1]+j, xy[2]] == "L") {
    					break
    				}
    			}
    
    			for (j = 1; layout[xy[1], xy[2]-j] != ""; ++j) {
    				if (layout[xy[1], xy[2]-j] == "#") {
    					occupied += 1
    					break
    				}
    				if (layout[xy[1], xy[2]-j] == "L") {
    					break
    				}
    			}
    
    			for (j = 1; layout[xy[1], xy[2]+j] != ""; ++j) {
    				if (layout[xy[1], xy[2]+j] == "#") {
    					occupied += 1
    					break
    				}
    				if (layout[xy[1], xy[2]+j] == "L") {
    					break
    				}
    			}
    
    			#for (x = xy[1]-1; layout[x, y]; --x) {
    			#	y = xy[2] - 1
    			#	if (layout[x, y] == "#") {
    			#		occupied += 1
    			#	}
    			#}
    
    			#for (x = xy[1]-1; x <= xy[1]+1; ++x) {
    			#	for (y = xy[2]-1; y <= xy[2]+1; ++y) {
    			#		if (layout[x, y] == "#") {
    			#			occupied += 1
    			#		}
    			#	}
    			#}
    	
    						#print occupied
    			if (layout[i] == "L") {
    				if (! occupied) {
    					change[i] = "#"
    					state = 1
    				}
    			} else if (layout[i] == "#") {
    				if (occupied >= 5) {
    					change[i] = "L"
    					state = 1
    				}
    			}
    		}
    
    		for (i in change)
    			layout[i] = change[i]
    
    		if (! state) {
    			break
    		}
    		#if (++k == 3) break
    	}
    
    	for (y = 1; y <= NR; ++y) {
    		for (x = 1; x <= chars; ++x) {
    			printf("%s", layout[x, y])
    		}
    		print ""
    	}
    
    	occupied = 0
    	for (i in layout) {
    		if (layout[i] == "#") {
    			occupied += 1
    		}
    	}
    
    	print occupied
    }
    
    4 votes
  6. spit-evil-olive-tips
    Link
    Part 1 import copy import sys def parse_input(input_path): seats = [] with open(input_path) as input_file: for line in input_file: row = [False if char == 'L' else None for char in line]...
    Part 1
    import copy
    import sys
    
    
    def parse_input(input_path):
        seats = []
        with open(input_path) as input_file:
            for line in input_file:
                row = [False if char == 'L' else None for char in line]
                seats.append(row)
    
        return seats
    
    
    def print_seats(seats):
        chars = {
            True: '#',
            False: 'L',
            None: '.',
        }
        for row in seats:
            line = ''.join(chars[seat] for seat in row)
            print(line)
    
    
    def count_neighbors(seats, row, col):
        count = 0
        for delta_row in [-1, 0, 1]:
            for delta_col in [-1, 0, 1]:
                if delta_row == 0 and delta_col == 0:
                    continue
    
                neighbor_row = row + delta_row
                neighbor_col = col + delta_col
                if neighbor_row < 0 or neighbor_col < 0:
                    continue
    
                try:
                    if seats[neighbor_row][neighbor_col]:
                        count += 1
                except IndexError:
                    continue
    
        return count
    
    
    def step(current):
        changed = False
        new = copy.deepcopy(current)
        for row, row_seats in enumerate(current):
            for col, seat in enumerate(row_seats):
                if seat is None:
                    continue
    
                neighbors = count_neighbors(current, row, col)
                if seat is False and neighbors == 0:
                    print(f'{row}, {col} -> occupied')
                    new[row][col] = True
                    changed = True
    
                if seat is True and neighbors >= 4:
                    print(f'{row}, {col} -> empty')
                    new[row][col] = False
                    changed = True
    
        return new, changed
    
    
    def main():
        seats = parse_input(sys.argv[1])
    
        for i in range(100):
            print(f'\n\n-- generation {i} --')
            print_seats(seats)
            seats, changed = step(seats)
            if not changed:
                break
    
        total = 0
        for row in seats:
            total += sum(1 if seat else 0 for seat in row)
    
        print(total)
    
    
    if __name__ == '__main__':
        main()
    
    Part 2

    For part 2, I only changed my count_neighbors function, as well as changing the limit for emptying a seat from 4 to 5.

    def count_neighbors(seats, row, col):
        count = 0
        for delta_row in [-1, 0, 1]:
            for delta_col in [-1, 0, 1]:
                if delta_row == 0 and delta_col == 0:
                    continue
    
                neighbor_row, neighbor_col = row, col
                while True:
                    neighbor_row += delta_row
                    neighbor_col += delta_col
    
                    if neighbor_row < 0 or neighbor_col < 0:
                        break
    
                    try:
                        occupied = seats[neighbor_row][neighbor_col]
                    except IndexError:
                        break
    
                    if occupied is True:
                        count += 1
    
                    if occupied is not None:
                        break
    
        return count
    
    @@ -58,7 +67,7 @@
                     new[row][col] = True
                     changed = True
     
    -            if seat is True and neighbors >= 4:
    +            if seat is True and neighbors >= 5:
                     print(f'{row}, {col} -> empty')
                     new[row][col] = False
                     changed = True
    
    
    3 votes
  7. clone1
    Link
    Mit scheme. Went with vectors today. Part 1 & 2 (define (get-lines parse-line f) (with-input-from-file f (lambda () (let loop ((line (read-line)) (lines '())) (if (eof-object? line) (reverse...

    Mit scheme. Went with vectors today.

    Part 1 & 2
    (define (get-lines parse-line f)
      (with-input-from-file f
        (lambda ()
          (let loop ((line (read-line))
                     (lines '()))
            (if (eof-object? line)
                (reverse lines)
                (loop (read-line)
                      (cons (parse-line line) lines)))))))
    
    (define (2d-vector-ref vec x y)
      (vector-ref (vector-ref vec x) y))
    
    (define (vector-map-with-index proc vect)
      (let* ((length (vector-length vect))
             (new-vect (make-vector length)))
        (for-each (lambda (i)
                    (vector-set! new-vect
                                 i
                                 (proc i (vector-ref vect i))))
                  (iota length))
        new-vect))
    
    (define (board seats count-nearby limit)
      (vector-map-with-index
       (lambda (y row)
         (vector-map-with-index
          (lambda (x seat)
            (if (eq? seat #\.) #\.
                (let ((nearby (count-nearby seats y x)))
                  (cond ((= nearby 0) #\#)
                        ((>= nearby limit) #\L)
                        (else seat)))))
          row))
       seats))
    
    (define (count-filled seats)
      (count (lambda (seat) (eq? seat #\#))
             (append-map (lambda (row) (vector->list row))
                         (vector->list seats))))
    
    (define (board-loop seats count-nearby seat-limit)
      (let loop ((seats seats))
        (let ((new-seats (board seats count-nearby seat-limit)))
          (if (equal? seats new-seats) (count-filled new-seats)
              (loop new-seats)))))
    
    (define (make-in-range seats)
      (let ((h (vector-length seats))
            (w (vector-length (vector-first seats))))
        (lambda (row col)
          (and (<= 0 row (- h 1))
               (<= 0 col (- w 1))))))
    
    (define directions '((-1 . -1) (0 . -1) (1 . -1) (-1 . 0) (1 . 0) (-1 . 1) (0 . 1) (1 . 1)))
    
    (define (one seats)
      (define (count-nearby seats row col)
        (let ((in-range? (make-in-range seats)))
          (define (adjacent-seats)
            (filter-map (lambda (direction)
                          (let ((row (+ row (car direction)))
                                (col (+ col (cdr direction))))
                            (and (in-range? row col)
                                 (2d-vector-ref seats row col))))
                        directions))
          (count (lambda (seat) (eq? seat #\#)) (adjacent-seats))))
      (board-loop seats count-nearby 4))
    
    (define (two seats)
      (define (count-nearby seats row col)
        (let ((in-range? (make-in-range seats)))
          (define (seat-in-direction? direction)
            (let ((drow (car direction))
                  (dcol (cdr direction)))
              (let loop ((row (+ row drow))
                         (col (+ col dcol)))
                (if (not (in-range? row col)) #f
                    (let ((seat (2d-vector-ref seats row col)))
                      (case seat
                        ((#\L) #f)
                        ((#\#) #t)
                        (else (loop (+ row drow) (+ col dcol)))))))))
          (count seat-in-direction? directions)))
      (board-loop seats count-nearby 5))
    
    (define (run lines)
      (display "One: ") (display (one lines)) (newline)
      (display "Two: ") (display (two lines)) (newline))
    
    (run (list->vector (get-lines string->vector "input")))
    
    3 votes
  8. wycy
    (edited )
    Link
    Rust Edited to optimize solution. I was originally keeping track of previously seen states with a HashSet thinking it'd be like a Game of Life, but ended up only needing to check when there were...

    Rust

    Edited to optimize solution. I was originally keeping track of previously seen states with a HashSet thinking it'd be like a Game of Life, but ended up only needing to check when there were zero changes.

    Rust
    use std::env;
    use std::io::{self, prelude::*, BufReader};
    use std::fs::File;
    use std::fmt;
    //use std::collections::HashSet;
    
    static ALL_DIRS: &'static [(i64,i64)] = &[(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)];
    
    #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
    enum Square {
        Floor,
        Chair,
        Person,
    }
    impl fmt::Display for Square {
        fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
            match *self {
                Self::Floor  => write!(f, "."),
                Self::Chair  => write!(f, "L"),
                Self::Person => write!(f, "#"),
    
            }
        }
    }
    
    fn count_neighbors_p1(map: &Vec<Vec<Square>>, x: i64, y: i64, xdim: i64, ydim: i64) -> i64 {
        let mut neighbors = 0;
        for dir in ALL_DIRS {
            let (nx,ny) = (x + dir.0, y + dir.1);
            if (0..xdim).contains(&nx) && (0..ydim).contains(&ny) {
                match map[nx as usize][ny as usize] {
                    Square::Person => { neighbors += 1; continue; },
                    _ => {},
                }
            } else {
                continue;
            }
        }
        neighbors
    }
    
    fn count_neighbors_p2(map: &Vec<Vec<Square>>, x: i64, y: i64, xdim: i64, ydim: i64) -> i64 {
        let mut neighbors = 0;
        'outer: for dir in ALL_DIRS {
            for i in 1.. {
                let (nx,ny) = (x + i*dir.0, y + i*dir.1);
                if (0..xdim).contains(&nx) && (0..ydim).contains(&ny) {
                    match map[nx as usize][ny as usize] {
                        Square::Person => { neighbors += 1; continue 'outer; },
                        Square::Chair => continue 'outer,
                        _ => {},
                    }
                } else {
                    continue 'outer;
                }
            }
        }
        neighbors
    }
    
    fn seat_map(input: &Vec<String>) -> Vec<Vec<Square>> {
        let ydim: usize = input.len();
        let xdim: usize = input.iter().next().unwrap().len();
        let mut chairs = vec![vec![Square::Floor; ydim]; xdim];
        for y in 0..input.len() as usize {
            let mut line = input[y].chars();
            for x in 0..xdim as usize {
                match line.next().unwrap().to_string().as_ref() {
                    "L" => chairs[x][y] = Square::Chair,
                    "." => chairs[x][y] = Square::Floor,
                    "#" => unreachable!("Found a person in input file."),
                    other => panic!("Unknown map square: {}", other),
                }
            }
        }
        chairs
    }
    
    fn part1(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 ydim: usize = input.len();
        let xdim: usize = input.iter().next().unwrap().len();
        let mut chairs = seat_map(&input);
    
        //let mut seen: HashSet<Vec<Vec<Square>>> = HashSet::new();
    
        'main_lp: loop {
            let current = chairs.clone();
            let mut changes = 0;
            for y in 0..ydim as usize {
                for x in 0..xdim as usize {
    
                    // Count neighbors
                    let people = count_neighbors_p1(&current, x as i64, y as i64, xdim as i64, ydim as i64);
    
                    // If a seat is empty (L) and there are no occupied seats
                    // adjacent to it, the seat becomes occupied.
                    if current[x][y] == Square::Chair && people == 0 {
                        chairs[x][y] = Square::Person;
                        changes += 1;
                    }
    
                    // If a seat is occupied (#) and four or more seats adjacent to it are
                    // also occupied, the seat becomes empty.
                    if current[x][y] == Square::Person && people >= 4 {
                        chairs[x][y] = Square::Chair;
                        changes += 1;
                    }
                }
            }
            // Check if previously seen
            /*match seen.get(&chairs) {
                Some(_) => { break 'main_lp; },
                None => { seen.insert(chairs.clone()); },
            }*/
            if changes == 0 { break 'main_lp; }
        }
    
        let part1 = chairs
            .iter()
            .flat_map(|x| x.iter().filter(|x| x == &&Square::Person))
            .count();
    
        println!("Part 1: {}", part1); // 2273
    
        Ok(())
    }
    
    fn part2(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 ydim: usize = input.len();
        let xdim: usize = input.iter().next().unwrap().len();
        let mut chairs = seat_map(&input);
    
        //let mut seen: HashSet<Vec<Vec<Square>>> = HashSet::new();
    
        'main_lp: loop {
            let current = chairs.clone();
            let mut changes = 0;
            for y in 0..ydim as usize {
                for x in 0..xdim as usize {
    
                    // Count neighbors
                    let people = count_neighbors_p2(&current, x as i64, y as i64, xdim as i64, ydim as i64 );
    
                    // If a seat is empty (L) and there are no occupied seats
                    // adjacent to it, the seat becomes occupied.
                    if current[x][y] == Square::Chair && people == 0 {
                        chairs[x][y] = Square::Person;
                        changes += 1;
                    }
    
                    // If a seat is occupied (#) and five or more seats adjacent to it are
                    // also occupied, the seat becomes empty.
                    if current[x][y] == Square::Person && people >= 5 {
                        chairs[x][y] = Square::Chair;
                        changes += 1;
                    }
                }
            }
            // Check if previously seen
            /*match seen.get(&chairs) {
                Some(_) => { break 'main_lp; },
                None => { seen.insert(chairs.clone()); },
            }*/
            if changes == 0 { break 'main_lp; }
        }
    
        let part2 = chairs
            .iter()
            .flat_map(|x| x.iter().filter(|x| x == &&Square::Person))
            .count();
    
        println!("Part 2: {}", part2); // 2064
    
        Ok(())
    }
    
    fn main() {
        let args: Vec<String> = env::args().collect();
        let filename = &args[1];
        part1(&filename).unwrap();
        part2(&filename).unwrap();
    }
    
    3 votes
  9. [3]
    nothis
    (edited )
    Link
    This is driving me mad, I have a solution to part 1 that outputs the correct end result for the test data but a wrong number for the actual input data. I honestly don't know what to even look for,...

    This is driving me mad, I have a solution to part 1 that outputs the correct end result for the test data but a wrong number for the actual input data. I honestly don't know what to even look for, it's a perfect match for the test.

    EDIT:

    I got it to work by basically redoing the whole thing. I suspect @wycy is right and I accidentally searched a perfectly square-shaped area (rows == columns) while the final input was a rectangular area. I didn't make any assumptions about that, though and thought I determined the height and width correctly in my first attempt, so maybe it was something else? Who cares! It works now!

    I'm not printing anything in these solutions but it was fun to see the area fill up in debug mode, I love it when the solution produces a bit of an animation.

    Part 1+2 (Python)
    with open("input.txt") as inputFile:
        area = inputFile.read().split("\n")
    
    
    def cell(row, column, area):
        """return content of cell, if row/column out of bounds, return '!'"""
        if row > len(area) - 1 or row < 0 or column > len(area[0]) - 1 or column < 0:
            return "!"
        return area[row][column]
    
    
    directions = [
        [+0, +1],  # right
        [-1, +1],  # top right
        [-1, +0],  # top
        [-1, -1],  # top left
        [+0, -1],  # left
        [+1, -1],  # bottom left
        [+1, +0],  # bottom
        [+1, +1]]  # bottom right
    
    
    def adjacent(row, column, area):
        adjacent = []
        for direction in directions:
            adjacent.append(cell(row + direction[0], column + direction[1], area))
        return adjacent
    
    
    def visible(row, column, area):
        visible = []
        for direction in directions:
            rDir = direction[0]
            cDir = direction[1]
            seen = "."
            while seen == ".":
                seen = cell(row + rDir, column + cDir, area)
                rDir += direction[0]
                cDir += direction[1]
            visible.append(seen)
        return visible
    
    
    def change(row, column, area, lookFunction, maxSeen):
        a = lookFunction(row, column, area)
        occupidedCount = a.count("#")
        if area[row][column] == "L" and occupidedCount == 0:
            return "#"
        elif area[row][column] == "#" and occupidedCount >= maxSeen:
            return "L"
        return area[row][column]
    
    
    def timeStep(area, lookFunction, maxSeen):
        newArea = []
        occupidedCount = 0
        changes = 0
        for r in range(0, len(area)):
            row = []
            for c in range(0, len(area[0])):
                newCell = change(r, c, area, lookFunction, maxSeen)
                if newCell != area[r][c]:
                    changes += 1
                row.append(newCell)
            newArea.append(row)
            occupidedCount += row.count("#")
        return newArea, occupidedCount, changes
    
    
    def stabilize(area, lookFunction, maxSeen):
        changes = 99999
        occupidedCount = -1
        while changes > 0:
            area, occupidedCount, changes = timeStep(area, lookFunction, maxSeen)
        return occupidedCount
    
    
    tempArea = area.copy()
    adjacentCount = stabilize(area, adjacent, 4)
    area = tempArea
    visibleCount = stabilize(area, visible, 5)
    
    print("Seats occuppied (adjacent):", adjacentCount)
    print("Seats occupied (visible):", visibleCount)
    
    3 votes
    1. [2]
      wycy
      Link Parent
      Did you perhaps set up a square map but have non-square input data? I see the sample is a 10x10 square but my input was something like 91x97.

      Did you perhaps set up a square map but have non-square input data? I see the sample is a 10x10 square but my input was something like 91x97.

      3 votes
      1. nothis
        Link Parent
        I don't think so, but that could be it! Anyway, I just redid the whole thing from scratch and it works, now! No idea why, lol.

        I don't think so, but that could be it! Anyway, I just redid the whole thing from scratch and it works, now! No idea why, lol.

        3 votes
  10. jzimbel
    (edited )
    Link
    Elixir I went try-hard on this one and defined + documented a CharGrid data structure in a separate module, since this kind of input tends to get used a lot in AoC puzzles. I also went a little...

    Elixir

    I went try-hard on this one and defined + documented a CharGrid data structure in a separate module, since this kind of input tends to get used a lot in AoC puzzles.

    I also went a little crazy making several functions that take other functions as arguments to modify their behavior, in order to avoid repeating code as much as possible. The result is questionably readable but runs well, and makes sense to me, at least for the next day or so. 😄

    CharGrid data structure
    defmodule AdventOfCode.CharGrid do
      @moduledoc "Data structure representing a grid of characters by a map of {x, y} => char"
    
      alias __MODULE__
    
      @type t :: %CharGrid{
              grid: grid,
              width: non_neg_integer,
              height: non_neg_integer
            }
    
      @typep grid :: %{coordinates => char}
    
      @type coordinates :: {non_neg_integer, non_neg_integer}
    
      @enforce_keys ~w[grid width height]a
      defstruct @enforce_keys
    
      # List of coords that produce the 8 coordinates surrounding a given coord when added to it
      @adjacent_deltas for x <- -1..1, y <- -1..1, not (x == 0 and y == 0), do: {x, y}
    
      @spec from_input(String.t()) :: t()
      def from_input(input) do
        charlists =
          input
          |> String.split()
          |> Enum.map(&String.to_charlist/1)
    
        height = length(charlists)
        width = length(hd(charlists))
    
        grid =
          for {line, y} <- Enum.with_index(charlists),
              {char, x} <- Enum.with_index(line),
              into: %{} do
            {{x, y}, char}
          end
    
        %CharGrid{
          grid: grid,
          width: width,
          height: height
        }
      end
    
      @doc "Gets the value at the given coordinates."
      @spec at(t(), coordinates) :: char | nil
      def at(%CharGrid{} = t, coords) do
        t.grid[coords]
      end
    
      @doc "Applies `fun` to each cell in the CharGrid to produce a new CharGrid."
      @spec map(t(), ({coordinates, char} -> char)) :: t()
      def map(%CharGrid{} = t, fun) do
        %{t | grid: for({coords, _} = entry <- t.grid, into: %{}, do: {coords, fun.(entry)})}
      end
    
      @doc "Returns the number of cells in the CharGrid for which `fun` returns a truthy value."
      @spec count(t(), ({coordinates, char} -> as_boolean(term))) :: non_neg_integer()
      def count(%CharGrid{} = t, fun) do
        Enum.count(t.grid, fun)
      end
    
      @doc "Returns a list of values from the up to 8 cells adjacent to the one at `coords`."
      @spec adjacent_values(t(), coordinates) :: list(char)
      def adjacent_values(%CharGrid{} = t, coords) do
        @adjacent_deltas
        |> Enum.map(&sum_coordinates(coords, &1))
        |> Enum.map(&at(t, &1))
        |> Enum.reject(&is_nil/1)
      end
    
      @doc """
      Returns a list of values from the up to 8 cells reachable by a chess queen's move from the
      cell at `coords`.
    
      The optional `empty_char` (default `?.`) dictates which cells are considered unoccupied.
      """
      @spec queen_move_values(t(), coordinates, char) :: list(char)
      def queen_move_values(%CharGrid{} = t, coords, empty_char \\ ?.) do
        @adjacent_deltas
        |> Enum.map(&find_nonempty_on_line(t, &1, sum_coordinates(coords, &1), empty_char))
        |> Enum.reject(&is_nil/1)
      end
    
      defp find_nonempty_on_line(t, step, coords, empty_char) do
        case t.grid[coords] do
          ^empty_char -> find_nonempty_on_line(t, step, sum_coordinates(coords, step), empty_char)
          val -> val
        end
      end
    
      defp sum_coordinates({x1, y1}, {x2, y2}), do: {x1 + x2, y1 + y2}
    end
    
    Parts 1 and 2
    defmodule AdventOfCode.Day11 do
      alias AdventOfCode.CharGrid
    
      def part1(args) do
        count_occupied(args, fn grid -> grid_mapper(grid, &CharGrid.adjacent_values/2, 4) end)
      end
    
      def part2(args) do
        count_occupied(args, fn grid -> grid_mapper(grid, &CharGrid.queen_move_values/2, 5) end)
      end
    
      defp count_occupied(input, map_func_generator) do
        input
        |> CharGrid.from_input()
        |> run_until_stable(map_func_generator)
        |> CharGrid.count(&match?({_, ?#}, &1))
      end
    
      defp run_until_stable(grid, map_func_generator) do
        run_until_stable(grid, nil, map_func_generator)
      end
    
      defp run_until_stable(grid, grid, _), do: grid
    
      defp run_until_stable(grid, _, map_func_generator) do
        grid
        |> CharGrid.map(map_func_generator.(grid))
        |> run_until_stable(grid, map_func_generator)
      end
    
      defp grid_mapper(grid, adjacent_finder, occupied_tolerance) do
        fn
          {coords, ?L} ->
            grid
            |> adjacent_finder.(coords)
            |> Enum.any?(&(&1 == ?#))
            |> if(do: ?L, else: ?#)
    
          {coords, ?#} ->
            grid
            |> adjacent_finder.(coords)
            |> Enum.count(&(&1 == ?#))
            |> Kernel.<(occupied_tolerance)
            |> if(do: ?#, else: ?L)
    
          {_, char} ->
            char
        end
      end
    end
    
    2 votes
  11. Gyrfalcon
    (edited )
    Link
    Language: Julia Repository Messy solution for this one, but part 2 was not as bad as I initially thought. Part 1 using Memoize function main() input = [] open("Day11/input.txt") do fp input =...

    Messy solution for this one, but part 2 was not as bad as I initially thought.

    Part 1
    using Memoize
    
    function main()
    
        input = []
        open("Day11/input.txt") do fp
            input = readlines(fp)
        end
        seats = []
        for row in input
            seat_row = []
            for char in row
                push!(seat_row, seat_type(char))
            end
            push!(seats, seat_row)
        end
    
        result_1 = simulate(seats)
    
        println(result_1)
        
    end
    
    function seat_type(seat_code)
        if seat_code == 'L'
            # Empty, can be filled
            return (false, true)
        else
            # Empty, can't be filled
            return (false, false)
        end
    end
    
    @memoize function valid_neighbors(location, max)
        y = location[1] .+ [1, 0, -1]
        x = location[2] .+ [1, 0, -1]
        y = y[max[1] .>= y .> 0]
        x = x[max[2] .>= x .> 0]
        return [(y_val, x_val) for x_val in x for y_val in y]
    end
    
    function simulate(seats)
    
        max = (length(seats), length(seats[1]))
        changed_seats = 1
        new_seats = deepcopy(seats)
        while changed_seats > 0
            changed_seats = 0
            for ydx = 1:max[1]
                for xdx = 1:max[2]
                    if seats[ydx][xdx][2] == false
                        continue
                    elseif seats[ydx][xdx][1] == false
                        neighbors = valid_neighbors((ydx,xdx), max)
                        adjacent = 0
                        for neighbor in neighbors
                            if neighbor == (ydx, xdx)
                                continue
                            end
                            adjacent += seats[neighbor[1]][neighbor[2]][1]
                        end
                        if adjacent == 0
                            new_seats[ydx][xdx] = (true, true)
                            changed_seats += 1
                        else
                            continue
                        end
                    elseif seats[ydx][xdx][1] == true
                        neighbors = valid_neighbors((ydx,xdx), max)
                        adjacent = 0
                        for neighbor in neighbors
                            if neighbor == (ydx, xdx)
                                continue
                            end
                            adjacent += seats[neighbor[1]][neighbor[2]][1]
                        end
                        if adjacent >= 4
                            new_seats[ydx][xdx] = (false, true)
                            changed_seats += 1
                        else
                            continue
                        end
                    end
                end
            end
            seats = deepcopy(new_seats)
        end
    
        return count([seat[1] for row in seats for seat in row])
    
    end
    
    main()
    

    Decided to do memoization again since my nearest neighbor lookup is slow, will probably do it again for the second part since that looks to be even more expensive for my not so great design pattern.

    Part 2 additions
    @memoize function valid_neighbors2(location, seats, max)
        neighbors = []
        directions = [(1,1), (1,0), (1,-1), (0,1), (0,-1), (-1, 1), (-1,0), (-1,-1)]
        multiplier = 1
        while length(directions) > 0
            for idx = length(directions):-1:1
                neighbor = location .+ (directions[idx] .* multiplier)
                if any(neighbor .> max) || any(neighbor .< 1)
                    deleteat!(directions, idx)
                elseif seats[neighbor[1]][neighbor[2]][2] == true
                     push!(neighbors, neighbor)
                     deleteat!(directions, idx)
                end
            end
            multiplier += 1
        end
        return neighbors
    end
    
    function simulate2(seats)
    
        max = (length(seats), length(seats[1]))
        changed_seats = 1
        new_seats = deepcopy(seats)
        while changed_seats > 0
            changed_seats = 0
            for ydx = 1:max[1]
                for xdx = 1:max[2]
                    if seats[ydx][xdx][2] == false
                        continue
                    elseif seats[ydx][xdx][1] == false
                        neighbors = valid_neighbors2((ydx,xdx), seats, max)
                        adjacent = 0
                        for neighbor in neighbors
                            if neighbor == (ydx, xdx)
                                continue
                            end
                            adjacent += seats[neighbor[1]][neighbor[2]][1]
                        end
                        if adjacent == 0
                            new_seats[ydx][xdx] = (true, true)
                            changed_seats += 1
                        else
                            continue
                        end
                    elseif seats[ydx][xdx][1] == true
                        neighbors = valid_neighbors2((ydx,xdx), seats, max)
                        adjacent = 0
                        for neighbor in neighbors
                            if neighbor == (ydx, xdx)
                                continue
                            end
                            adjacent += seats[neighbor[1]][neighbor[2]][1]
                        end
                        if adjacent >= 5
                            new_seats[ydx][xdx] = (false, true)
                            changed_seats += 1
                        else
                            continue
                        end
                    end
                end
            end
            seats = deepcopy(new_seats)
        end
    
        return count([seat[1] for row in seats for seat in row])
    
    end
    

    Part 2 was actually not too bad since I had split out the neighbor finding code in part 1.

    2 votes
  12. 3d12
    Link
    I agree with others, this was a very fun problem in comparison to Day 10, especially part 2. I admit I got a little far behind, I had to take a bit of a break for my own mental health, because I...

    I agree with others, this was a very fun problem in comparison to Day 10, especially part 2. I admit I got a little far behind, I had to take a bit of a break for my own mental health, because I was losing way too much sleep staying up to get these coded. I have today off, and a couple days next week, and basically no plans, so I definitely intend to get caught up as much I can. :)

    Part 1
    const fs = require('fs');
    const readline = require('readline');
    
    let seatingArray = []
    
    async function openFileForReading(file) {
    	const fileStream = fs.createReadStream(file);
    
    	const rl = readline.createInterface({
    		input: fileStream,
    		crlfDelay: Infinity
    	});
    
    	for await (const line of rl) {
    		seatingArray.push(line);
    	}
    }
    
    function numNeighbors(array, row, col) {
    	let neighbors = 0;
    	for (let rowIter = 0; rowIter < array.length; rowIter++) {
    		let currentRow = array[rowIter];
    		if (rowIter >= (row-1) // covers the row above
    			&& rowIter <= (row+1) // covers the row below
    		) {
    			for (let colIter = 0; colIter < currentRow.length; colIter++) {
    				if (colIter >= (col-1) // covers the column left
    					&& colIter <= (col+1) // covers the column right
    				) {
    					if (rowIter != row || colIter != col) { // don't count the evalSpot
    						let evalSpot = currentRow[colIter];
    						if (evalSpot == '#') {
    							neighbors++;
    						}
    					}
    				}
    			}
    		}
    	}
    	return neighbors;
    }
    
    function newSeating(array) {
    	let newArray = [];
    	for (let rowIter = 0; rowIter < array.length; rowIter++) {
    		let currentRow = array[rowIter];
    		let newRow = [];
    		for (let colIter = 0; colIter < currentRow.length; colIter++) {
    			let neighbors = numNeighbors(array, rowIter, colIter);
    			let evalSpot = currentRow[colIter];
    			if (evalSpot == 'L' && neighbors == 0) {
    				newRow.push('#');
    			} else if (evalSpot == '#' && neighbors >= 4) {
    				newRow.push('L');
    			} else {
    				newRow.push(evalSpot);
    			}
    		}
    		newArray.push(newRow);
    	}
    	return newArray;
    }
    
    function compareArrays(array1, array2) {
    	if (array1.length != array2.length) { return false; }
    	for (let rowIter = 0; rowIter < array1.length; rowIter++) {
    		let currentRow1 = array1[rowIter];
    		let currentRow2 = array2[rowIter];
    		if (currentRow1.length != currentRow2.length) { return false; }
    		for (let colIter = 0; colIter < currentRow1.length; colIter++) {
    			let currentSpot1 = currentRow1[colIter];
    			let currentSpot2 = currentRow2[colIter];
    			if (currentSpot1 != currentSpot2) { return false; }
    		}
    	}
    	return true;
    }
    
    (async function mainExecution() {
    	await openFileForReading('input.txt');
    	let oldSeats = seatingArray;
    	let newSeats = [];
    	let iterations = 0;
    	while (true) {
    		newSeats = newSeating(oldSeats);
    		iterations++;
    		let same = compareArrays(oldSeats, newSeats);
    		if (!same) {
    			oldSeats = newSeats;
    		} else {
    			console.log("Finished! After " + (iterations-1) + " iterations, the positions stop changing!");
    			console.log(newSeats.map((element) => { return element.join(''); }).join('\n'));
    			console.log("At this point, there are " + newSeats.map((element) => { return element.filter(element => element == '#') }).map((element) => { return element.length }).reduce((a,b) => { return a + b; }) + " occupied seats");
    			return;
    		}
    	}
    })();
    
    Part 2
    const fs = require('fs');
    const readline = require('readline');
    
    let seatingArray = []
    
    async function openFileForReading(file) {
    	const fileStream = fs.createReadStream(file);
    
    	const rl = readline.createInterface({
    		input: fileStream,
    		crlfDelay: Infinity
    	});
    
    	for await (const line of rl) {
    		seatingArray.push(line);
    	}
    }
    
    function findNextNeighbor(array, row, col, rowMod, colMod) {
    	let newRow = row;
    	let newCol = col;
    	while (newRow >= 0 && newRow < array.length && newCol >= 0 && newCol < array[row].length) {
    		newRow += rowMod;
    		if (newRow >= 0 && newRow < array.length) {
    			let rowRef = array[newRow];
    			newCol += colMod;
    			if (newCol >= 0 && newCol < rowRef.length) {
    				let newCell = rowRef[newCol];
    				if (newCell == '#') {
    					return true;
    				} else if (newCell == 'L') {
    					return false;
    				}
    			}
    		}
    		
    	}
    	return false;
    }
    
    function numNeighbors(array, row, col) {
    	let neighbors = 0;
    	let directions = [ [1,0], 	// down
    			[1,1], 		// down-right
    			[0,1], 		// right
    			[-1,1], 	// up-right
    			[-1,0], 	// up
    			[-1,-1], 	// up-left
    			[0,-1], 	// left
    			[1,-1] ] 	// down-left
    	for (const direction of directions) {
    		if (findNextNeighbor(array, row, col, direction[0], direction[1])) {
    			neighbors++;
    		}
    	}
    	return neighbors;
    }
    
    function newSeating(array) {
    	let newArray = [];
    	for (let rowIter = 0; rowIter < array.length; rowIter++) {
    		let currentRow = array[rowIter];
    		let newRow = [];
    		for (let colIter = 0; colIter < currentRow.length; colIter++) {
    			let evalSpot = currentRow[colIter];
    			if (evalSpot == 'L') {
    				let neighbors = numNeighbors(array, rowIter, colIter);
    				if (neighbors == 0) {
    					newRow.push('#');
    				} else {
    					newRow.push(evalSpot);
    				}
    			} else if (evalSpot == '#') {
    				let neighbors = numNeighbors(array, rowIter, colIter);
    				if (neighbors >= 5) {
    					newRow.push('L');
    				} else {
    					newRow.push(evalSpot);
    				}
    			} else {
    				newRow.push(evalSpot);
    			}
    		}
    		newArray.push(newRow);
    	}
    	return newArray;
    }
    
    function compareArrays(array1, array2) {
    	if (array1.length != array2.length) { return false; }
    	for (let rowIter = 0; rowIter < array1.length; rowIter++) {
    		let currentRow1 = array1[rowIter];
    		let currentRow2 = array2[rowIter];
    		if (currentRow1.length != currentRow2.length) { return false; }
    		for (let colIter = 0; colIter < currentRow1.length; colIter++) {
    			let currentSpot1 = currentRow1[colIter];
    			let currentSpot2 = currentRow2[colIter];
    			if (currentSpot1 != currentSpot2) { return false; }
    		}
    	}
    	return true;
    }
    
    (async function mainExecution() {
    	await openFileForReading('input.txt');
    	let oldSeats = seatingArray;
    	let newSeats = [];
    	let iterations = 0;
    	while (true) {
    		newSeats = newSeating(oldSeats);
    		iterations++;
    		let same = compareArrays(oldSeats, newSeats);
    		if (!same) {
    			oldSeats = newSeats;
    		} else {
    			console.log("Finished! After " + (iterations-1) + " iterations, the positions stop changing!");
    			console.log(newSeats.map((element) => { return element.join(''); }).join('\n'));
    			console.log("At this point, there are " + newSeats.map((element) => { return element.filter(element => element == '#') }).map((element) => { return element.length }).reduce((a,b) => { return a + b; }) + " occupied seats");
    			return;
    		}
    	}
    })();
    
    2 votes