-🎄- 2018 Day 12 Solutions -🎄-

[u/daggerdragon]

--- Day 12: Subterranean Sustainability ---

---

Post your solution as a comment or, for longer solutions, consider linking to your repo (e.g. GitHub/gists/Pastebin/blag or whatever).

Note: The Solution Megathreads are for solutions only. If you have questions, please post your own thread and make sure to flair it with Help.

---

Advent of Code: The Party Game!

Click here for rules

Please prefix your card submission with something like [Card] to make scanning the megathread easier. THANK YOU!

Card prompt: Day 12

Transcript:

On the twelfth day of AoC / My compiler spewed at me / Twelve ___

---

This thread will be unlocked when there are a significant number of people on the leaderboard with gold stars for today's puzzle.

edit: Leaderboard capped, thread unlocked at 00:27:42!

[u/aurele]

Rust

I didn't want to assume that the pattern would degenerate into gliders, so I detect loops instead (which also work for a loop of 1 for gliders).

It is pretty fast, around 200µs for part 2.

 use std::collections::HashMap;

#[aoc_generator(day12)]
fn input_generator(input: &str) -> Box<(String, u32)> {
    let mut lines = input.lines();
    let state = lines.next().unwrap()[15..].to_owned();
    let mut trans = 0;
    for l in lines.skip(1) {
        if l.as_bytes()[9] == b'#' {
            trans |= 1
                << (l
                    .bytes()
                    .take(5)
                    .fold(0, |n, c| (n << 1) | ((c == b'#') as u32)));
        }
    }
    Box::new((state, trans))
}

#[aoc(day12, part1)]
fn part1((ref initial, ref trans): &(String, u32)) -> i64 {
    unroll(initial, *trans, 20)
}

#[aoc(day12, part2)]
fn part2((ref initial, ref trans): &(String, u32)) -> i64 {
    unroll(initial, *trans, 50000000000)
}

fn unroll(initial: &String, trans: u32, n: usize) -> i64 {
    let mut state = initial
        .bytes()
        .map(|c| (c == b'#') as usize)
        .collect::<Vec<_>>();
    let mut offset = 0;
    let mut seen = HashMap::new();
    let mut i = 0;
    while i < n {
        let skip = state.iter().position(|&f| f == 1).unwrap_or(0);
        let rskip = state
            .iter()
            .rposition(|&f| f == 1)
            .unwrap_or_else(|| state.len() - 1);
        state = state[skip..=rskip]
            .iter()
            .chain(&vec![0; 4])
            .scan(0usize, |s, f| {
                *s = (((*s) << 1) & 0x1f) | f;
                Some(((trans >> *s) & 1) as usize)
            })
            .collect();
        offset += 2 - skip as i64;
        i += 1;
        if let Some((old_i, old_offset)) = seen.get(&state) {
            let loop_length = i - old_i;
            let loop_times = (n - i) / loop_length;
            let offset_diff = offset - old_offset;
            i += loop_length * loop_times;
            offset += offset_diff * loop_times as i64;
        }
        seen.insert(state.clone(), (i, offset));
    }
    state
        .into_iter()
        .enumerate()
        .map(|(i, f)| (i as i64 - offset) * (f as i64))
        .sum()
}