Advent of Code 2020 Solution Megathread - Day 11: Seating System

 IDENTIFICATION DIVISION. PROGRAM-ID. AOC-2020-11-2. AUTHOR. ANNA KOSIERADZKA. ENVIRONMENT DIVISION. INPUT-OUTPUT SECTION. FILE-CONTROL. SELECT INPUTFILE ASSIGN TO "d11.input" ORGANIZATION IS LINE SEQUENTIAL. DATA DIVISION. FILE SECTION. FD INPUTFILE. 01 INPUTRECORD PIC X(99). WORKING-STORAGE SECTION. 01 FILE-STATUS PIC 9 VALUE 0. 01 WS-ARR OCCURS 93 TIMES. 05 WS-ROW PIC X OCCURS 98 TIMES. 01 WS-ARR-2 OCCURS 93 TIMES. 05 WS-ROW-2 PIC X OCCURS 98 TIMES. 01 DI PIC S9 VALUE 0. 01 DJ PIC S9 VALUE 0. LOCAL-STORAGE SECTION. 01 N-ROWS UNSIGNED-INT VALUE 93. 01 N-COLS UNSIGNED-INT VALUE 98. 01 K-MAX UNSIGNED-INT VALUE 98. 01 I UNSIGNED-INT VALUE 1. 01 J UNSIGNED-INT VALUE 1. 01 K UNSIGNED-INT VALUE 1. 01 X UNSIGNED-INT VALUE 1. 01 Y UNSIGNED-INT VALUE 1. 01 OCCUPIED-ADJACENT UNSIGNED-INT VALUE 0. 01 OCCUPIED UNSIGNED-INT VALUE 0. 01 CHANGES UNSIGNED-INT VALUE 0. PROCEDURE DIVISION. 001-MAIN. OPEN INPUT INPUTFILE. PERFORM 002-READ UNTIL FILE-STATUS = 1. CLOSE INPUTFILE. PERFORM 004-ONE-ROUND WITH TEST AFTER UNTIL CHANGES = 0. PERFORM 008-COUNT-OCCUPIED. DISPLAY OCCUPIED. STOP RUN. 002-READ. READ INPUTFILE AT END MOVE 1 TO FILE-STATUS NOT AT END PERFORM 003-PROCESS-LINE END-READ. 003-PROCESS-LINE. MOVE INPUTRECORD TO WS-ARR(I). ADD 1 TO I. 004-ONE-ROUND. MOVE 0 TO CHANGES. PERFORM VARYING I FROM 1 BY 1 UNTIL I > N-ROWS MOVE WS-ARR(I) TO WS-ARR-2(I) END-PERFORM. PERFORM VARYING I FROM 1 BY 1 UNTIL I > N-ROWS AFTER J FROM 1 BY 1 UNTIL J > N-COLS PERFORM 005-PROCESS-SEAT END-PERFORM. 005-PROCESS-SEAT. * - If a seat is empty (L) and there are no occupied seats * adjacent to it, the seat becomes occupied. * - If a seat is occupied (#) and four or more seats adjacent to * it are also occupied, the seat becomes empty. * - Otherwise, the seat's state does not change. IF WS-ROW(I, J) = '.' THEN EXIT PARAGRAPH END-IF. PERFORM 006-COUNT-OCCUPIED-ADJACENT. IF WS-ROW(I, J) = 'L' AND OCCUPIED-ADJACENT = 0 THEN MOVE '#' TO WS-ROW(I, J) ADD 1 TO CHANGES END-IF. IF WS-ROW(I, J) = '#' AND OCCUPIED-ADJACENT > 4 THEN MOVE 'L' TO WS-ROW(I, J) ADD 1 TO CHANGES END-IF. 006-COUNT-OCCUPIED-ADJACENT. MOVE 0 TO OCCUPIED-ADJACENT. PERFORM VARYING DI FROM -1 BY 1 UNTIL DI > 1 AFTER DJ FROM -1 BY 1 UNTIL DJ > 1 PERFORM 007-COUNT-OCCUPIED-ADJACENT-IN-DIRECTION END-PERFORM. IF WS-ROW-2(I, J) = '#' THEN SUBTRACT 1 FROM OCCUPIED-ADJACENT END-IF. 007-COUNT-OCCUPIED-ADJACENT-IN-DIRECTION. PERFORM VARYING K FROM 1 BY 1 UNTIL K > K-MAX COMPUTE X = I + K * DI COMPUTE Y = J + K * DJ IF X < 1 OR Y < 1 OR X > N-ROWS OR Y > N-COLS THEN EXIT PERFORM END-IF IF WS-ROW-2(X, Y) = 'L' THEN EXIT PERFORM END-IF IF WS-ROW-2(X, Y) = '#' THEN ADD 1 TO OCCUPIED-ADJACENT EXIT PERFORM END-IF END-PERFORM. 008-COUNT-OCCUPIED. MOVE 0 TO OCCUPIED. PERFORM VARYING I FROM 1 BY 1 UNTIL I > N-ROWS AFTER J FROM 1 BY 1 UNTIL J > N-COLS IF WS-ROW(I, J) = '#' THEN ADD 1 TO OCCUPIED END-IF END-PERFORM. 

data Seat = E | O | F deriving (Show, Eq) type Seats = Map (Int,Int) Seat getNeighbours :: ((Int,Int) -> (Int, Int) -> Bool) -> (Int,Int) -> [(Int, Int)] getNeighbours f idx = filter (f idx) [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)] --rules :: Seats -> Seat -> Seat rules :: Int -> [(Int,Int)] -> Seat -> Seat rules _ _ F = F rules _ ns E | null ns = O rules g ns O | null (drop g ns) = O rules _ _ _ = E parse :: [String] -> Seats parse seats = let idxs = [((i,j), f s) | (i, row) <- zip [0..] seats, (j, s) <- zip [0..] row ] in M.fromList idxs where f '.' = F f 'L' = E f '#' = O doTask :: (Seats -> (Int, Int) -> (Int, Int) -> Bool) -> Int -> Seats -> Int doTask f g seats = let seats' = M.mapWithKey (rules g . getNeighbours (f seats)) seats in if seats == seats' then M.size $ M.filter (== O) seats else doTask f g seats' main = do seats <- readFile "day11_input" <&> lines <&> parse print (doTask task1N 3 seats) print (doTask task2N 4 seats) where task1N seats (i,j) (di,dj) = Just O == seats !? (i+di, j+dj) task2N seats (i, j) (di, dj) = case seats !? (i+di, j+dj) of Just F -> task2N seats (i+di, j+dj) (di, dj) Just O -> True _ -> False 

#ifndef AOC2020_DAY11_H #define AOC2020_DAY11_H  #include <stdbool.h> #include <stdlib.h>  #include "parsing.h"  /// Potential options for a seat typedef enum { SEAT_FLOOR, ///< Seat gone SEAT_EMPTY, ///< No one in seat SEAT_FULL, ///< Seat occupied } SeatType; /// A grid of seats (1D, but to be indexed as 2D) typedef struct { GridSize size; SeatType* cells; } Grid; Grid* parse(const char* filename); int part1(const char* filename); bool first_visible_full(SeatType* cells, int x, int y, int width, int height, int xdir, int ydir); int part2(const char* filename); int day11(void); #endif 

#include "Day11.h"  #include <stdbool.h> #include <stdio.h> #include <string.h>  #include "parsing.h"  /// Parse the input file, a 2D grid of '.', '#', or 'L'. Grid* parse(const char* filename) { FILE* fp; fp = fopen(filename, "r"); if (fp == NULL) { printf("Couldn't open the file!\n"); exit(EXIT_FAILURE); } GridSize size = measure_grid(fp); SeatType* cells = (SeatType*)malloc(sizeof(SeatType) * size.height * size.width); for (int y = 0; y < size.height; y++) { for (int x = 0; x < size.width; x++) { switch (getc(fp)) { case '.': cells[y * size.width + x] = SEAT_FLOOR; break; case 'L': cells[y * size.width + x] = SEAT_EMPTY; break; case '#': cells[y * size.width + x] = SEAT_FULL; break; default: printf("Bad char.\n"); exit(EXIT_FAILURE); } } getc(fp); // Burn newline } fclose(fp); Grid* grid = (Grid*)malloc(sizeof(Grid)); grid->size = size; grid->cells = cells; return grid; } /// Free a grid's memory static void free_grid(Grid* grid) { free(grid->cells); free(grid); } /// Change a grid one timestep based on the rules from part 1 /// /// 1. An empty seat with no occupied seats around it gets filled. /// 2. A full seat with >= 4 occupied neighbors gets departed. /// 3. Floor... floor never changes. static bool evolve_grid(Grid* grid) { bool changed = false; SeatType new_cells[grid->size.height * grid->size.width]; SeatType* cells = grid->cells; GridSize size = grid->size; /// Check if a given x, y coordinate seat is occupied #define FULL(_x, _y) (cells[(_y)*size.width + _x] == SEAT_FULL)  for (int y = 0; y < grid->size.height; y++) { for (int x = 0; x < grid->size.width; x++) { int idx = y * size.width + x; if (cells[idx] == SEAT_FLOOR) { new_cells[idx] = SEAT_FLOOR; // Floor never changes, short circuit continue; } int occupied = 0; if (y > 0 && FULL(x, y - 1)) occupied++; if (y < size.height - 1 && FULL(x, y + 1)) occupied++; if (x > 0 && FULL(x - 1, y)) occupied++; if (x < size.width - 1 && FULL(x + 1, y)) occupied++; if (y > 0 && x > 0 && FULL(x - 1, y - 1)) occupied++; if (y > 0 && x < size.width - 1 && FULL(x + 1, y - 1)) occupied++; if (y < size.height - 1 && x > 0 && FULL(x - 1, y + 1)) occupied++; if (y < size.height - 1 && x < size.width - 1 && FULL(x + 1, y + 1)) occupied++; if (cells[idx] == SEAT_EMPTY && occupied == 0) { new_cells[idx] = SEAT_FULL; changed = true; } else if (cells[idx] == SEAT_FULL && occupied >= 4) { new_cells[idx] = SEAT_EMPTY; changed = true; } else { new_cells[idx] = cells[idx]; } } } #undef FULL  memcpy(grid->cells, new_cells, sizeof(SeatType) * size.width * size.height); return changed; } /// Check to see if the first visible chair in a given direction is full or not. /// Skip over floor spaces, and stop at the edge of the grid. bool first_visible_full(SeatType* cells, int x, int y, int width, int height, int xdir, int ydir) { int px = x + xdir; int py = y + ydir; SeatType val = SEAT_FLOOR; while (px >= 0 && py >= 0 && px < width && py < height && (val = cells[py * width + px]) == SEAT_FLOOR) { px += xdir; py += ydir; } return (val == SEAT_FULL); } /// Change a grid one timestep based on the rules from part 2 /// /// 1. An empty seat with no occupied seats around it gets filled. /// 2. A full seat with >= 5 occupied neighbors gets departed. /// 3. Floor... floor never changes. /// /// For this one, "around it" means the first seat in that direction /// that isn't floor. static bool evolve_grid2(Grid* grid) { bool changed = false; SeatType new_cells[grid->size.height * grid->size.width]; SeatType* cells = grid->cells; GridSize size = grid->size; /// Convenience macro for checking first_visible_full in a given direction #define SEE_FULL(xdir, ydir) \ (first_visible_full(cells, x, y, size.width, size.height, xdir, ydir))  for (int y = 0; y < grid->size.height; y++) { for (int x = 0; x < grid->size.width; x++) { int idx = y * size.width + x; if (cells[idx] == SEAT_FLOOR) { new_cells[idx] = SEAT_FLOOR; // Floor never changes continue; } int occupied = 0; if (SEE_FULL(-1, -1)) occupied++; if (SEE_FULL(-1, 0)) occupied++; if (SEE_FULL(-1, 1)) occupied++; if (SEE_FULL(0, -1)) occupied++; if (SEE_FULL(0, 1)) occupied++; if (SEE_FULL(1, -1)) occupied++; if (SEE_FULL(1, 0)) occupied++; if (SEE_FULL(1, 1)) occupied++; if (cells[idx] == SEAT_EMPTY && occupied == 0) { new_cells[idx] = SEAT_FULL; changed = true; } else if (cells[idx] == SEAT_FULL && occupied >= 5) { new_cells[idx] = SEAT_EMPTY; changed = true; } else { new_cells[idx] = cells[idx]; } } } #undef SEE_FULL  memcpy(grid->cells, new_cells, sizeof(SeatType) * size.width * size.height); return changed; } /* static void print_grid(Grid* grid) { printf("\n"); for (int y = 0; y < grid->size.height; y++) { for (int x = 0; x < grid->size.width; x++) { switch (grid->cells[y * grid->size.width + x]) { case SEAT_EMPTY: printf("L"); break; case SEAT_FLOOR: printf("."); break; case SEAT_FULL: printf("#"); break; default: printf("Bad seat type.\n"); exit(EXIT_FAILURE); } } printf("\n"); } } */ /// Part one, how many seats occupied after steady state /// given the rules above? int part1(const char* filename) { Grid* grid = parse(filename); while (evolve_grid(grid)) {} int occupied = 0; int size = grid->size.height * grid->size.width; for (int i = 0; i < size; i++) { if (grid->cells[i] == SEAT_FULL) occupied++; } free_grid(grid); return occupied; } /// Part two, how many seats occupied after steady state given /// the rules above? int part2(const char* filename) { Grid* grid = parse(filename); while (evolve_grid2(grid)) {} int occupied = 0; int size = grid->size.height * grid->size.width; for (int i = 0; i < size; i++) { if (grid->cells[i] == SEAT_FULL) occupied++; } free_grid(grid); return occupied; } /// Run both parts int day11() { printf("====== Day 11 ======\n"); printf("Part 1: %d\n", part1("data/day11.txt")); printf("Part 2: %d\n", part2("data/day11.txt")); return EXIT_SUCCESS; } 

use std::fs::File; use std::io::prelude::*; // --- file read fn read_file(filename: &str) -> std::io::Result<String> { let mut file = File::open(filename)?; let mut contents = String::new(); file.read_to_string(&mut contents)?; Ok(contents) } // --- model #[derive(Debug, Eq, PartialEq, Copy, Clone)] enum Cell { Floor, Empty, Occupied } impl From<char> for Cell { fn from(c: char) -> Self { match c { 'L' => Cell::Empty, '#' => Cell::Occupied, _ => Cell::Floor } } } #[derive(Debug, Eq, PartialEq, Clone)] struct Layout { grid: Vec<Vec<Cell>>, width: usize, height: usize } impl From<&str> for Layout { fn from(s: &str) -> Self { let grid: Vec<Vec<Cell>> = s.lines().map(|line| line.trim().chars().map(Cell::from).collect()).collect(); Layout { width: grid[0].len(), height: grid.len(), grid } } } #[derive(Debug, Eq, PartialEq, Clone, Copy)] struct Pos { x: usize, y: usize } impl Pos { fn neighbours(&self) -> impl Iterator<Item = Pos> + '_ { let xmin = if self.x == 0 { 0 } else { self.x - 1 }; let ymin = if self.y == 0 { 0 } else { self.y - 1 }; let xmax = self.x + 1; let ymax = self.y + 1; (ymin..=ymax).flat_map( move |y| (xmin..=xmax).map( move |x| Pos { x, y } ) ).filter(move |p| p != self) } } #[derive(Debug, Eq, PartialEq)] struct Offset { x: i64, y: i64 } impl std::ops::Add<&Offset> for Pos { type Output = Pos; fn add(self, off: &Offset) -> Pos { Pos { x: (self.x as i64 + off.x) as usize, y: (self.y as i64 + off.y) as usize } } } impl Layout { fn valid_pos(&self, p: &Pos) -> bool { p.x < self.width && p.y < self.height } fn current(&self, p: &Pos) -> Cell { self.grid[p.y][p.x] } fn occupied_neighbours(&self, p: &Pos) -> usize { p.neighbours() .filter(|p| self.valid_pos(p) && self.current(p) == Cell::Occupied ).count() } fn find_seat_in_direction(&self, p: &Pos, dir: &Offset) -> Cell { let mut pos = *p; loop { pos = pos + dir; if !self.valid_pos(&pos) { return Cell::Floor; } else { let c = self.current(&pos); if c != Cell::Floor { return c; } } } } fn visible_occupied_seats(&self, p: &Pos) -> usize { let directions = vec![ Offset { x: -1, y: -1 }, Offset { x: 0, y: -1 }, Offset { x: 1, y: -1 }, Offset { x: -1, y: 0 }, Offset { x: 1, y: 0 }, Offset { x: -1, y: 1 }, Offset { x: 0, y: 1 }, Offset { x: 1, y: 1 } ]; directions.iter() .filter(|d| self.find_seat_in_direction(p, d) == Cell::Occupied) .count() } fn iter(&self) -> impl Iterator<Item = Cell> + '_ { self.grid.iter().flat_map(|row| row.iter().cloned()) } fn count_occupied_seats(&self) -> usize { self.iter().filter(|c| *c == Cell::Occupied).count() } fn next_generation<F>(&self, f: F) -> Layout where F: Fn(&Pos) -> Cell { let grid = self.grid.iter().enumerate().map( |(y,row)| row.iter().enumerate().map( |(x,_)| f(&Pos { x, y }) ).collect() ).collect(); Layout { width: self.width, height: self.height, grid } } fn next_generation_v1(&self) -> Layout { self.next_generation(|p| match self.current(p) { Cell::Floor => Cell::Floor, Cell::Empty => { if self.occupied_neighbours(p) == 0 { Cell::Occupied } else { Cell::Empty } } Cell::Occupied => { if self.occupied_neighbours(p) >= 4 { Cell::Empty } else { Cell::Occupied } } } ) } fn next_generation_v2(&self) -> Layout { self.next_generation(|p| match self.current(p) { Cell::Floor => Cell::Floor, Cell::Empty => { if self.visible_occupied_seats(p) == 0 { Cell::Occupied } else { Cell::Empty } } Cell::Occupied => { if self.visible_occupied_seats(p) >= 5 { Cell::Empty } else { Cell::Occupied } } } ) } } // --- problems fn run_until_stable<F>(layout: &Layout, f: F) -> Layout where F: Fn(&Layout) -> Layout { let mut current = layout.clone(); loop { let next = f(&current); if next == current { return current; } else { current = next; } } } fn part1(layout: &Layout) -> usize { let stable = run_until_stable(layout, Layout::next_generation_v1); stable.count_occupied_seats() } fn part2(layout: &Layout) -> usize { let stable = run_until_stable(layout, Layout::next_generation_v2); stable.count_occupied_seats() } fn main() { let input = read_file("./input.txt").unwrap(); let layout: Layout = input.as_str().into(); println!("part1 {:?}", part1(&layout)); println!("part2 {:?}", part2(&layout)); } #[cfg(test)] mod tests { use super::*; fn test_grid() -> &'static str { "L.LL.LL.LL LLLLLLL.LL L.L.L..L.. LLLL.LL.LL L.LL.LL.LL L.LLLLL.LL ..L.L..... LLLLLLLLLL L.LLLLLL.L L.LLLLL.LL" } fn test_grid_with_occupied_seats() -> &'static str { "L.LL.LL.LL ##LLLLL.LL L.L.L..L.. LLLL.LL.LL L.LL.LL.LL L.LLLLL.LL ..L.L..... LLLLLLLLLL L.LLLLLL.L L.LLLLL.LL" } #[test] fn test_init() { let layout = Layout::from(test_grid()); assert_eq!(layout.current(&Pos { x: 0, y: 0 }), Cell::Empty); assert_eq!(layout.current(&Pos { x: 1, y: 0 }), Cell::Floor); } #[test] fn test_bounds() { let layout = Layout::from(test_grid()); assert!(layout.valid_pos(&Pos { x: 0, y: 0 })); assert!(layout.valid_pos(&Pos { x: 9, y: 9 })); assert!(!layout.valid_pos(&Pos { x: 10, y: 0 })); assert!(!layout.valid_pos(&Pos { x: 0, y: 10 })); } #[test] fn test_neighbours() { let ns: Vec<Pos> = Pos { x: 0, y: 0 }.neighbours().collect(); assert!(ns.contains(&Pos { x: 1, y: 0 })); assert!(ns.contains(&Pos { x: 0, y: 1 })); assert!(ns.contains(&Pos { x: 1, y: 1 })); assert_eq!(ns.len(), 3); let ns: Vec<Pos> = Pos { x: 5, y: 0 }.neighbours().collect(); assert!(ns.contains(&Pos { x: 4, y: 0 })); assert!(ns.contains(&Pos { x: 6, y: 0 })); assert!(ns.contains(&Pos { x: 4, y: 1 })); assert!(ns.contains(&Pos { x: 5, y: 1 })); assert!(ns.contains(&Pos { x: 6, y: 1 })); assert_eq!(ns.len(), 5); let ns: Vec<Pos> = Pos { x: 0, y: 8 }.neighbours().collect(); assert!(ns.contains(&Pos { x: 0, y: 7 })); assert!(ns.contains(&Pos { x: 0, y: 9 })); assert!(ns.contains(&Pos { x: 1, y: 7 })); assert!(ns.contains(&Pos { x: 1, y: 8 })); assert!(ns.contains(&Pos { x: 1, y: 9 })); assert_eq!(ns.len(), 5); let ns: Vec<Pos> = Pos { x: 6, y: 3 }.neighbours().collect(); assert!(ns.contains(&Pos { x: 5, y: 2 })); assert!(ns.contains(&Pos { x: 6, y: 2 })); assert!(ns.contains(&Pos { x: 7, y: 2 })); assert!(ns.contains(&Pos { x: 5, y: 3 })); assert!(ns.contains(&Pos { x: 7, y: 3 })); assert!(ns.contains(&Pos { x: 5, y: 4 })); assert!(ns.contains(&Pos { x: 6, y: 4 })); assert!(ns.contains(&Pos { x: 7, y: 4 })); assert_eq!(ns.len(), 8); } #[test] fn test_occupied_neighbours() { let layout = Layout::from(test_grid()); assert_eq!(layout.occupied_neighbours(&Pos { x: 0, y: 0 }), 0); let layout = Layout::from(test_grid_with_occupied_seats()); assert_eq!(layout.occupied_neighbours(&Pos { x: 0, y: 0 }), 2); } #[test] fn test_generations_v1() { let layout = Layout::from(test_grid()); let gen1 = layout.next_generation_v1(); assert_eq!(gen1, Layout::from( "#.##.##.## #######.## #.#.#..#.. ####.##.## #.##.##.## #.#####.## ..#.#..... ########## #.######.# #.#####.##" )); let gen2 = gen1.next_generation_v1(); assert_eq!(gen2, Layout::from( "#.LL.L#.## #LLLLLL.L# L.L.L..L.. #LLL.LL.L# #.LL.LL.LL #.LLLL#.## ..L.L..... #LLLLLLLL# #.LLLLLL.L #.#LLLL.##" )); let gen3 = gen2.next_generation_v1(); assert_eq!(gen3, Layout::from( "#.##.L#.## #L###LL.L# L.#.#..#.. #L##.##.L# #.##.LL.LL #.###L#.## ..#.#..... #L######L# #.LL###L.L #.#L###.##" )); } #[test] fn test_generations_v2() { let layout = Layout::from(test_grid()); let gen1 = layout.next_generation_v2(); assert_eq!(gen1, Layout::from( "#.##.##.## #######.## #.#.#..#.. ####.##.## #.##.##.## #.#####.## ..#.#..... ########## #.######.# #.#####.##" )); let gen2 = gen1.next_generation_v2(); assert_eq!(gen2, Layout::from( "#.LL.LL.L# #LLLLLL.LL L.L.L..L.. LLLL.LL.LL L.LL.LL.LL L.LLLLL.LL ..L.L..... LLLLLLLLL# #.LLLLLL.L #.LLLLL.L#" )); let gen3 = gen2.next_generation_v2(); assert_eq!(gen3, Layout::from( "#.L#.##.L# #L#####.LL L.#.#..#.. ##L#.##.## #.##.#L.## #.#####.#L ..#.#..... LLL####LL# #.L#####.L #.L####.L#" )); } } 

data=open("input10.txt","r").read().strip().split("\n") data=[list(row) for row in data] def count_adj_visible(row,col,prev,part1=False): s=0 for rinc,colinc in [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]: r=row c=col while True: r=r+rinc c=c+colinc if(r<0 or r>=len(prev)) or (c<0 or c>=len(prev[row]) or prev[r][c]=="L"): break if(prev[r][c]=="#"): s+=1 break if(part1): break return s def solve(table,part1=False): table=[row.copy() for row in table] while True: prev=[row.copy() for row in table] for row in range(len(table)): for col in range(len(table[row])): if(table[row][col]!="."): n=count_adj_visible(row, col, prev,part1) if(n==0 and prev[row][col]=="L"): table[row][col]="#" if(n>=(4 if part1 else 5)and prev[row][col]=="#"): table[row][col]="L" if(prev==table):break return "\n".join(["".join(row)for row in table]).count("#") print("part 1 ans =",solve(data,part1=True)) print("part 2 ans =",solve(data)) 

module Main where import qualified Data.Map.Strict as M import Data.Maybe (mapMaybe) type Coordinate = (Int, Int) toCoordinateMap :: [[a]] -> M.Map (Int, Int) a toCoordinateMap a = M.fromList $ do (y, row) <- zip [0 ..] a (x, v) <- zip [0 ..] row pure ((x, y), v) findAdjSeats :: Coordinate -> M.Map (Int, Int) Char -> [Coordinate] findAdjSeats (x, y) seats = filter (`M.member` seats) [ (x-1, y-1), (x, y-1), (x+1, y-1), (x-1, y), (x+1, y), (x-1, y+1), (x, y+1), (x+1, y+1) ] findFirstSeatInSight :: Coordinate -> M.Map Coordinate Char -> [Coordinate] findFirstSeatInSight coord seatMap = mapMaybe (firstInSight coord) [ (-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1) ] where firstInSight (x, y) (dx, dy) = (x-dx, y-dy) `M.lookup` seatMap >>= aux where aux seat = if seat == 'L' || seat == '#' then Just (x-dx, y-dy) else firstInSight (x-dx, y-dy) (dx, dy) runSimulation :: M.Map Coordinate Char -> (Coordinate -> M.Map Coordinate Char -> [Coordinate]) -> Int -> Int runSimulation seatMap findAdjSeatsF occupiedSeats = if seatMap == nextCycle then length $ M.filter (== '#') nextCycle else runSimulation nextCycle findAdjSeatsF occupiedSeats where noOccupiedAdjSeats = not . any ((== Just '#') . (`M.lookup` seatMap)) moreOrEqThanNOccupiedSeats n = (>= n) . length . filter ((== Just '#') . (`M.lookup` seatMap)) nextCycle = M.mapWithKey (\coordinate c -> case c of '.' -> '.' 'L' -> if noOccupiedAdjSeats $ findAdjSeatsF coordinate seatMap then '#' else 'L' '#' -> if moreOrEqThanNOccupiedSeats occupiedSeats $ findAdjSeatsF coordinate seatMap then 'L' else '#' _ -> error $ "cannot do" ++ show c ) seatMap main :: IO () main = do input <- lines <$> readFile "input.txt" let seatMap = toCoordinateMap input print $ runSimulation seatMap findAdjSeats 4 print $ runSimulation seatMap findFirstSeatInSight 5 

struct CoordinateDirection<'a> { coordinates: (usize, usize), direction: (i8, i8), maximum: &'a (usize, usize), } impl Iterator for CoordinateDirection<'_> { type Item = (usize, usize); fn next(&mut self) -> Option<(usize, usize)> { if (self.direction.0 < 0 && self.coordinates.0 == 0) || (self.direction.0 > 0 && self.coordinates.0 >= self.maximum.0) || (self.direction.1 < 0 && self.coordinates.1 == 0) || (self.direction.1 > 0 && self.coordinates.1 >= self.maximum.1) { return None; } self.coordinates = ( (self.coordinates.0 as i8 + self.direction.0) as usize, (self.coordinates.1 as i8 + self.direction.1) as usize, ); Some(self.coordinates) } } fn all_coordinate_generators<'a>( seat: &'a Seat, maximum: &'a (usize, usize), ) -> Vec<CoordinateDirection<'a>> { let iterator_generator = |(dx, dy)| CoordinateDirection { coordinates: seat.coordinates.clone(), maximum: &maximum, direction: (dx, dy), }; vec![ iterator_generator((1, 0)), iterator_generator((1, 1)), iterator_generator((1, -1)), iterator_generator((-1, 0)), iterator_generator((-1, 1)), iterator_generator((-1, -1)), iterator_generator((0, 1)), iterator_generator((0, -1)), ] } fn new_state(seat: &Seat, arrangement: &Vec<Vec<Seat>>) -> Seat { if seat.state == State::Floor { return seat.clone(); } let maximum = (arrangement[0].len() - 1, arrangement.len() - 1); let mut visual_iters = all_coordinate_generators(seat, &maximum); let mut occupied_count = 0; for coor_iter in visual_iters.iter_mut() { if let Some((x, y)) = coor_iter.next() { if arrangement[y][x].state == State::Occupied { occupied_count += 1; } } } let state = if occupied_count >= 4 && seat.state == State::Occupied { State::Unoccupied } else if occupied_count == 0 && seat.state == State::Unoccupied { State::Occupied } else { seat.state.clone() }; Seat { coordinates: seat.coordinates.clone(), state, } } fn new_state_visually(seat: &Seat, arrangement: &Vec<Vec<Seat>>) -> Seat { if seat.state == State::Floor { return seat.clone(); } let maximum = (arrangement[0].len() - 1, arrangement.len() - 1); let mut visual_iters = all_coordinate_generators(seat, &maximum); let mut occupied_count = 0; for coor_iter in visual_iters.iter_mut() { if let Some((x, y)) = coor_iter .skip_while(|(x, y)| arrangement[*y][*x].state == State::Floor) .next() { if arrangement[y][x].state == State::Occupied { occupied_count += 1; } } } let state = if occupied_count > 4 && seat.state == State::Occupied { State::Unoccupied } else if occupied_count == 0 && seat.state == State::Unoccupied { State::Occupied } else { seat.state.clone() }; Seat { coordinates: seat.coordinates.clone(), state, } } fn reach_stability_count( input: &Vec<Vec<Seat>>, state_check: &dyn Fn(&Seat, &Vec<Vec<Seat>>) -> Seat, ) -> usize { let mut old_arrangement = input.clone(); loop { let mut new_arrangement = vec![]; for row in old_arrangement.iter() { let mut new_row = vec![]; for seat in row.iter() { new_row.push(state_check(&seat, &old_arrangement)); } new_arrangement.push(new_row); } if new_arrangement == old_arrangement { break; } old_arrangement = new_arrangement; } old_arrangement .iter() .flat_map(|v| v) .filter(|s| (*s).state == State::Occupied) .count() } 

$grid = File.readlines('11.txt').map do |line| line.strip.each_char.map do |c| case c when '.' then :floor when 'L' then :empty when '#' then :occupied end end end $rows = $grid.length $columns = $grid[0].length def get_neighbors(i, j) neighbors = [] neighbors.push $grid[j - 1][i] unless j == 0 # N neighbors.push $grid[j - 1][i + 1] unless j == 0 or i == $columns - 1 # NE neighbors.push $grid[j][i + 1] unless i == $columns - 1 # E neighbors.push $grid[j + 1][i + 1] unless j == $rows - 1 or i == $columns - 1 # SE neighbors.push $grid[j + 1][i] unless j == $rows - 1 # S neighbors.push $grid[j + 1][i - 1] unless j == $rows - 1 or i == 0 # SW neighbors.push $grid[j][i - 1] unless i == 0 # W neighbors.push $grid[j - 1][i - 1] unless j == 0 or i == 0 # NW neighbors end def count_occupied $grid.map { |row| row.count :occupied }.sum end current_occupied = 0 last_occupied = nil until current_occupied == last_occupied last_occupied = current_occupied new_grid = [] $rows.times do new_grid.push [nil] * $columns end (0...$rows).each do |j| (0...$columns).each do |i| neighbors = get_neighbors(i, j) if $grid[j][i] == :empty and neighbors.none? :occupied new_grid[j][i] = :occupied elsif $grid[j][i] == :occupied and neighbors.count(:occupied) >= 4 new_grid[j][i] = :empty else new_grid[j][i] = $grid[j][i] end end end $grid = new_grid current_occupied = count_occupied end puts count_occupied 

$grid = File.readlines('11.txt').map do |line| line.strip.each_char.map do |c| case c when '.' then :floor when 'L' then :empty when '#' then :occupied end end end $rows = $grid.length $columns = $grid[0].length def seats_in_sight(i, j) seats = [] beam_slopes = [ [-1, 0], # N [-1, 1], # NE [0, 1], # E [1, 1], # SE [1, 0], # S [1, -1], # SW [0, -1], # W [-1, -1], # NW ] beam_slopes.each do |y, x| j_copy, i_copy = j, i while true j_copy += y i_copy += x break unless 0 <= j_copy and j_copy < $rows and 0 <= i_copy and i_copy < $columns if [:empty, :occupied].include? $grid[j_copy][i_copy] seats.push $grid[j_copy][i_copy] break end end end seats end def count_occupied $grid.map { |row| row.count :occupied }.sum end def render_grid $grid.map do |row| row.map do |cell| case cell when :floor then '.' when :empty then 'L' when :occupied then '#' end end.join end.join "\n" end current_occupied = 0 last_occupied = nil until current_occupied == last_occupied last_occupied = current_occupied new_grid = [] $rows.times do new_grid.push [nil] * $columns end (0...$rows).each do |j| (0...$columns).each do |i| neighbors = seats_in_sight(i, j) if $grid[j][i] == :empty and neighbors.none? :occupied new_grid[j][i] = :occupied elsif $grid[j][i] == :occupied and neighbors.count(:occupied) >= 5 new_grid[j][i] = :empty else new_grid[j][i] = $grid[j][i] end end end $grid = new_grid current_occupied = count_occupied end puts count_occupied 

#include <string> #include <vector> #include <fstream> #include <iostream> #include <sstream> #include "gif.h"  int main() { GifWriter g; int width; int height; std::ifstream file("day11_test1_output"); std::string temp; std::stringstream ss; std::getline(file, temp); ss << temp; ss >> width; std::getline(file, temp); ss << temp; ss >> height; GifBegin(&g, "day11.gif", width, height, 100); //Gif gif("day11.gif", width, height, 1); std::vector<uint8_t> image((width+2)*(height+2)*4); int y = 0; while (std::getline(file, temp)) { for (int x = 0; x < width; x++) { uint8_t r = 220; uint8_t g = 0; uint8_t b = 220; if (temp.at(x) == '#') { r = 0; g = 255; b = 0; } if (temp.at(x) == '.') { r = 0; g = 0; b = 0; } const int one_d_map = x + width * y; image[(one_d_map * 4) + 0] = r; image[(one_d_map * 4) + 1] = g; image[(one_d_map * 4) + 2] = b; image[(one_d_map * 4) + 3] = 255; } if (y == 9) { GifWriteFrame(&g, image.data(), width, height, 100); //image.clear(); y = 0; } else { y++; } } GifWriteFrame(&g, image.data(), width, height, 100); GifWriteFrame(&g, image.data(), width, height, 100); GifWriteFrame(&g, image.data(), width, height, 100); GifWriteFrame(&g, image.data(), width, height, 100); GifWriteFrame(&g, image.data(), width, height, 100); GifWriteFrame(&g, image.data(), width, height, 100); GifWriteFrame(&g, image.data(), width, height, 100); GifWriteFrame(&g, image.data(), width, height, 100); GifWriteFrame(&g, image.data(), width, height, 100); GifEnd(&g); return 0; } 

10 10 L.LL.LL.LL LLLLLLL.LL L.L.L..L.. LLLL.LL.LL L.LL.LL.LL L.LLLLL.LL ..L.L..... LLLLLLLLLL L.LLLLLL.L L.LLLLL.LL #.##.##.## #######.## #.#.#..#.. ####.##.## #.##.##.## #.#####.## ..#.#..... ########## #.######.# #.#####.## #.LL.L#.## #LLLLLL.L# L.L.L..L.. #LLL.LL.L# #.LL.LL.LL #.LLLL#.## ..L.L..... #LLLLLLLL# #.LLLLLL.L #.#LLLL.## #.##.L#.## #L###LL.L# L.#.#..#.. #L##.##.L# #.##.LL.LL #.###L#.## ..#.#..... #L######L# #.LL###L.L #.#L###.## #.#L.L#.## #LLL#LL.L# L.L.L..#.. #LLL.##.L# #.LL.LL.LL #.LL#L#.## ..L.L..... #L#LLLL#L# #.LLLLLL.L #.#L#L#.##