summaryrefslogtreecommitdiff
path: root/2018
diff options
context:
space:
mode:
authorTom Smeding <tom.smeding@gmail.com>2018-12-12 11:58:50 +0100
committerTom Smeding <tom.smeding@gmail.com>2018-12-12 11:58:50 +0100
commit7a15bcbeb8a86f3202ae55ca610384991806e443 (patch)
tree318ef84b6c2196952a49f89d4fc497369d31142b /2018
parent46640ec717810091d4fa1d74167c01793c48c059 (diff)
Day 12
Diffstat (limited to '2018')
-rw-r--r--2018/input/12.txt34
-rw-r--r--2018/src/day12.rs136
-rw-r--r--2018/src/main.rs4
3 files changed, 173 insertions, 1 deletions
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"))
}
}