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

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

   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

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

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

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

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

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

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