From 7a15bcbeb8a86f3202ae55ca610384991806e443 Mon Sep 17 00:00:00 2001
From: Tom Smeding <tom.smeding@gmail.com>
Date: Wed, 12 Dec 2018 11:58:50 +0100
Subject: Day 12

---
 2018/input/12.txt |  34 ++++++++++++++
 2018/src/day12.rs | 136 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2018/src/main.rs  |   4 +-
 3 files changed, 173 insertions(+), 1 deletion(-)
 create mode 100644 2018/input/12.txt
 create mode 100644 2018/src/day12.rs

diff --git a/2018/input/12.txt b/2018/input/12.txt
new file mode 100644
index 0000000..588d9dc
--- /dev/null
+++ b/2018/input/12.txt
@@ -0,0 +1,34 @@
+initial state: ###.#..#..##.##.###.#.....#.#.###.#.####....#.##..#.#.#..#....##..#.##...#.###.#.#..#..####.#.##.#
+
+#.... => .
+#.##. => #
+..#.. => .
+#.#.# => .
+.#.## => #
+...## => #
+##... => #
+###.. => #
+#..## => .
+.###. => .
+###.# => #
+..... => .
+#..#. => .
+.#.#. => #
+##..# => #
+.##.. => .
+...#. => .
+#.### => .
+..### => .
+####. => .
+#.#.. => #
+.##.# => #
+.#... => #
+##.#. => #
+....# => .
+..#.# => #
+#...# => #
+..##. => .
+.#..# => #
+.#### => .
+##### => #
+##.## => #
diff --git a/2018/src/day12.rs b/2018/src/day12.rs
new file mode 100644
index 0000000..6ec0772
--- /dev/null
+++ b/2018/src/day12.rs
@@ -0,0 +1,136 @@
+use std::io;
+use std::io::BufRead;
+use std::cmp::min;
+use std::mem::swap;
+
+fn bits_to_u8(bits: &[u8]) -> u8 {
+    (0..min(bits.len(), 8)).map(|i| if bits[i] == '#' as u8 { 1 << i } else { 0 }).sum()
+}
+
+fn getbit(bits: &[u8], idx: usize) -> u8 {
+    (bits[idx / 8] & 1 << idx % 8) >> idx % 8
+}
+
+fn evolve(board: &[u8], out: &mut [u8], patdict: &[u8; 1 << 5]) {
+    assert!(board.len() == out.len());
+
+    let mut pat = board[0] & 0x1f;
+    for i in 2..8*out.len()-2 {
+        let bit = patdict[pat as usize];
+
+        // for i in 0..5 { print!("{}", if (pat & 1 << i) != 0 { '#' } else { '.' }); }
+        // println!(" {}", bit);
+
+        out[i / 8] = out[i / 8] & !(1 << i % 8) | bit << i % 8;
+
+        if i == 8 * out.len() - 3 { break; }
+        pat = pat >> 1 | getbit(board, i + 3) << 4;
+    }
+}
+
+#[allow(dead_code)]
+fn print_board(board: &[u8]) {
+    for i in 0..8*board.len() {
+        let bit = board[i / 8] & (1 << (i % 8));
+        print!("{}", if bit != 0 { '#' } else { '.' });
+    }
+
+    println!("");
+}
+
+fn board_sum(board: &[u8], zeroidx: i64) -> i64 {
+    let mut numsum = 0;
+    for i in 0..8*board.len() {
+        if (board[i / 8] & 1 << i % 8) != 0 {
+            numsum += i as i64 - 8 * zeroidx as i64;
+        }
+    }
+    numsum
+}
+
+fn make_board(init_str: &str, niters: usize) -> (Vec<u8>, usize) {
+    let slack = 2 * niters + 2;
+
+    let zeroidx = (slack + 7) / 8;
+    let mut board = vec![0; zeroidx + (init_str.len() + slack + 7) / 8];
+
+    for i in 0..(init_str.len() + 7) / 8 {
+        board[zeroidx + i] = bits_to_u8(&init_str.as_bytes()[8*i..min(8*i+8, init_str.len())]);
+    }
+
+    (board, zeroidx)
+}
+
+struct Repetition {
+    generation: usize,
+    score: i64,
+    increment: i64,
+}
+
+fn findrep(init_str: &str, patdict: &[u8; 1 << 5]) -> Repetition {
+    let niters = 1000;
+
+    let (mut board, zeroidx) = make_board(init_str, niters);
+    let mut board2 = vec![0; board.len()];
+
+    let mut prevscore = 0;
+    let mut previncr = 0;
+    let mut streak = 0;
+
+    for generation in 1..niters+1 {
+        evolve(&board, &mut board2, &patdict);
+        swap(&mut board, &mut board2);
+
+        let score = board_sum(&board, zeroidx as i64);
+        let increment = score - prevscore;
+        if increment == previncr {
+            streak += 1;
+            if streak > 10 {
+                return Repetition { generation, score, increment };
+            }
+        } else {
+            streak = 0;
+        }
+
+        prevscore = score;
+        previncr = increment;
+    }
+
+    unreachable!();
+}
+
+fn simulate(init_str: &str, niters: usize, patdict: &[u8; 1 << 5]) -> i64 {
+    let (mut board, zeroidx) = make_board(init_str, niters);
+    let mut board2 = vec![0; board.len()];
+
+    for _ in 0..niters {
+        evolve(&board, &mut board2, &patdict);
+        swap(&mut board, &mut board2);
+    }
+
+    board_sum(&board, zeroidx as i64)
+}
+
+pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> {
+    let mut lines_iter = reader.lines();
+    let init_str = &lines_iter.next().unwrap().unwrap().clone()[15..];
+
+    let patdict = {
+        let mut patdict = [0; 1 << 5];
+        lines_iter.next();
+        for line in lines_iter {
+            let line = line.unwrap();
+            let pat = bits_to_u8(&line.as_bytes()[0..5]);
+            let res = bits_to_u8(&line.as_bytes()[9..10]);
+            patdict[pat as usize] = res;
+        }
+        patdict
+    };
+
+    let part1 = simulate(&init_str, 20, &patdict).to_string();
+
+    let rep = findrep(&init_str, &patdict);
+    let part2 = (rep.score + (50000000000 - rep.generation as i64) * rep.increment).to_string();
+
+    Ok((part1, part2))
+}
diff --git a/2018/src/main.rs b/2018/src/main.rs
index e3622a3..daafaa4 100644
--- a/2018/src/main.rs
+++ b/2018/src/main.rs
@@ -16,8 +16,9 @@ mod day8;
 mod day9;
 mod day10;
 mod day11;
+mod day12;
 
-static NUM_DAYS: i32 = 11;
+static NUM_DAYS: i32 = 12;
 
 fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
     match day {
@@ -32,6 +33,7 @@ fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> {
         9 => day9::main(reader),
         10 => day10::main(reader),
         11 => day11::main(reader),
+        12 => day12::main(reader),
         _ => Err(Error::new(ErrorKind::Other, "Invalid day"))
     }
 }
-- 
cgit v1.2.3-54-g00ecf