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

Today and yesterday are very different types of puzzles. This one is a variation on a staple of the AoC series: Conway's Game of Life.

The Puzzle

In today’s puzzle, we're modeling seats on a ferry. Except that this ferry is looking like a 2D grid and these seats are looking like cells, and this puzzle is looking a bit like the Game of Life. Our job is to simulate seating and wait until things stabilize.

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 03:09PM 12/12/2020 PST.

Language	Count
JavaScript	5
Rust	2
Ruby	2
C#	1
C	1
COBOL	1
Elixir	1

Merry Coding!

Comments

[Ryan Palo]

This one went surprisingly well! Still really fast, which I'm loving. And I got to make some more involved macros, which is fun.

Day11.h:

#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

Day11.c:

#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;
}

[Anna]

COBOL, Friday night means I had time to do both parts.

   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.

[Benedict Gaster]

Bit late today as I had to do yesterday first, due to teaching commitments and just to tired to sit down at 10pm to work on it yesterday :-)

Anyway, my first solution, which I won't post here, was very (very) slow, using just lists. So after see looking at comments reddit replaced lists with Map, with the key being the 2D index, it worked out pretty well. Of course, it would have been a lost faster in Rust or C++, just to two arrays, one for the current step, and one for the next, updating in place, and simply switching each step. However I'm trying to do as many of these using Haskell, as most of my other days use Rust and C++ and it's been fun returning to Haskell after quite a while. I feel I've learnt a lot just over these last few days, which always sees like a good outcome. Enough chat, my solution:

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

[Nicholas Treu]

I used Haskell. Definitely not the most efficient or optimized solution:

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

[Neil Gall]

Oops, forgot to post yesterday. Pleased with how this one turned out, especially the unit tests.

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#"
        ));
    }
}

[Kudos Beluga]

Part 1 and 2 js solution, toggle part2 to true or false depending on your needs
I'm not sure about others but it took a long 4-5 seconds for it to compute part 1, 5-6 for part 2 and I'm very disappointed :(

const fs = require("fs")
let data = fs.readFileSync("input.txt","utf8").split("\n");
let part2 = true;
const logit = () => {
    let string = data.join(",");
    string = string.split("").map(e => {
    if (e == "#") return "b";
    }).filter(e => e).length
  console.log(string)
}
  let directions = [
    //right
    {x:1,y:0},
    //left
    {x:0,y:1},
    //up
    {x:1,y:1},
    //bottom
    {x:-1,y:-1},
    //topleft
    {x:-1,y:0},
    //topright
    {x:0,y:-1},
    //bottomleft
    {x:1,y:-1},
    //bottomright
    {x:-1,y:1},
    //{x:0,y:0}
  ]
const gethits = (x,y) => {
  let hits = 0;
  let cond;
  if (part2) cond = 59;
  else cond = 1;

  directions.map(({x:ex,y:ey}) => {

let myx = x+ex;
let myy = y+ey
  let i = 0;
  while (i<cond) {
    if (data[myy]) {
      if (data[myy][myx] == "#") {
        hits++
        break;
      }
      else if (data[myy][myx] == "L") {
        break;
        }
    }
   myx += ex;
   myy += ey;
   i++;
  }
  })  
  return hits;
}

const parseinput = (cache="") => {
  let vacants = [];
  let occupants = [];
for (y in data) {
  for (x in data) {
    y = Number(y);
    x = Number(x);

    if (data[y][x] == "L") {
    let hits = gethits(x,y);
    if (!hits) occupants.push({x,y})
    } else if (data[y][x] == "#") {
    let hits = gethits(x,y);
    let tolerance = 4;
    if (part2) tolerance = 5;
    if (hits >= tolerance) vacants.push({x,y})
    }
  }
}
    occupants.forEach(e => {
      let string = [...data[e.y]]
      string[e.x] = "#"
        data[e.y] = string
    })
    vacants.forEach(e => {
      let string = [...data[e.y]]
      string[e.x] = "L";
      data[e.y] = string;
    })
if (cache == data.join(",")) logit()
else parseinput(data.join(","))
}
parseinput();

[Pukar Giri]

python solution for both part 1 and 2

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

[Derk-Jan Karrenbeld]

OOP in Ruby; I enjoyed writing this!

require 'benchmark'

class Seat
  def initialize(mark)
    self.mark = mark
    self.next_mark = mark
  end

  def valid?
    mark != 'X'
  end

  def empty?
    mark == 'L'
  end

  def occupied?
    mark == '#'
  end

  def floor?
    mark == '.'
  end

  def invalid?
    mark == 'X'
  end

  def seat?
    occupied? || empty?
  end

  def to_s
    mark
  end

  def prepare_to_dance!
    if occupied?
      self.next_mark = 'L'
    elsif empty?
      self.next_mark = '#'
    end

    self
  end

  def will_it_flip?
    self.next_mark != mark
  end

  def do_the_shuffle!
    self.mark = next_mark
  end

  private

  attr_accessor :mark, :next_mark
end

class SeatingGrid
  def self.from_lines(grid)
    height = grid.length
    width = grid[0].chomp.length

    gridline = grid.map(&:chomp).join('')
    SeatingGrid.new(gridline, width: width, height: height)
  end

  def initialize(gridline, width:, height:)
    self.seats = gridline.chars.map { |x| Seat.new(x) }
    self.width = width
    self.height = height

    self._adjacency = {}
    self._visually_adjacent = {}
    self._visually_at = {}
  end

  def at(x, y)
    return Seat.new('X') if x < 0 || x >= width || y < 0 || y >= height
    self[y * width + x]
  end

  def visual_at(x, y, direction:)
    memoized = _visually_at["#{x}.#{y}"]
    return memoized if memoized

    seat = at(x, y)
    if seat.seat? || seat.invalid?
      _visually_at["#{x}.#{y}"] = seat
      return seat
    end

    visual_at(
      x + direction.first,
      y + direction.last,
      direction: direction
    )
  end

  def [](i)
    seats[i]
  end

  def adjacent(x, y)
    memoized = _adjacency["#{x}.#{y}"]
    return memoized if memoized

    _adjacency["#{x}.#{y}"] = [
      at(x - 1, y - 1), # top left
      at(x    , y - 1), # top
      at(x + 1, y - 1), # top right

      at(x + 1, y    ), # right

      at(x + 1, y + 1), # bottom right
      at(x    , y + 1), # bottom
      at(x - 1, y + 1), # bottom left

      at(x - 1, y    ), # left
  ].select(&:seat?)
  end

  def visual_adjacent(x, y)
    memoized = _visually_adjacent["#{x}.#{y}"]
    return memoized if memoized

    _visually_adjacent["#{x}.#{y}"] = [
      visual_at(x - 1, y - 1, direction: [-1, -1]), # top left
      visual_at(x    , y - 1, direction: [ 0, -1]), # top
      visual_at(x + 1, y - 1, direction: [ 1, -1]), # top right

      visual_at(x + 1, y    , direction: [ 1,  0]), # right

      visual_at(x + 1, y + 1, direction: [ 1,  1]), # bottom right
      visual_at(x    , y + 1, direction: [ 0,  1]), # bottom
      visual_at(x - 1, y + 1, direction: [-1,  1]), # bottom left

      visual_at(x - 1, y    , direction: [-1,  0]), # left
    ].select(&:seat?)
  end

  def prepare_to_dance!(x, y)
    at(x, y).prepare_to_dance!
  end

  def each
    (0..width).each do |x|
      (0..height).each do |y|
        seat = at(x, y)
        yield x, y, seat if seat.seat?
      end
    end
  end

  def visualize
    gridline
      .chars
      .each_slice(width)
      .map(&:join)
      .join("\n")
  end

  def occupancy
    seats.count(&:occupied?)
  end

  def dance!
    seats.each(&:do_the_shuffle!)
  end

  private

  attr_accessor :seats, :width, :height
  attr_accessor :_adjacency, :_visually_adjacent, :_visually_at
end

def simulate(grid, adjacency:, packed_when:, verbose: false)
  rules = {}
  rules[-> (seat) { seat.empty? }]    = -> (adjacents) { !(adjacents.any? { |a| a.occupied? }) }
  rules[-> (seat) { seat.occupied? }] = -> (adjacents) { !(adjacents.count { |a| a.occupied? } < packed_when) }

  iteration = 0
  loop do
    changes = 0
    iteration += 1

    grid.each do |x, y, seat|
      next if seat.floor?

      rule = rules.find { |k, _| k.(seat) }
      next unless rule

      adjacents = adjacency.(grid, x, y)
      next unless rule.last.(adjacents)

      changed = grid.prepare_to_dance!(x, y).will_it_flip?
      changes += changed ? 1 : 0
    end

    grid.dance!

    if verbose
      puts "[#{iteration}] #{changes} changes"
      puts
      puts grid.visualize
      puts ""
      puts ""
    end

    if changes.zero?
      puts "==============================" if verbose
      puts "Seats taken: #{grid.occupancy}"
      break
    end
  end
end

source = 'input.txt'

Benchmark.bmbm do |x|
  x.report('part 1') do
    grid = SeatingGrid.from_lines(File.readlines(source))

    simulate(
      grid,
      adjacency: -> (grid, x, y) { grid.adjacent(x, y) },
      packed_when: 4,
    )
  end

  x.report('part 2') do
    grid = SeatingGrid.from_lines(File.readlines(source))

    simulate(
      grid,
      adjacency: -> (grid, x, y) { grid.visual_adjacent(x, y) },
      packed_when: 5
    )
  end
end

[readyready15728]

Ruby. Initially assumed a toroidal grid and wasted a huge amount of time in the process. Part 1:

$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

Part 2:

$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

[Benedict Gaster]

Well I had a little time while rewatching Buffy this evening with the kids and inspired by E. Choroba, I wrote a very (very) simple C++ program to generate an annimated GIF showing the process of set allocation. It uses the single header GIF library:

#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;
}

The input is a file which has the width and height on the first two lines, followed by the grid for each step. For example, the example given in the AOC description for today:

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#.##