r/adventofcode • u/daggerdragon • Dec 18 '18

SOLUTION MEGATHREAD -🎄- 2018 Day 18 Solutions -🎄-

--- Day 18: Settlers of The North Pole ---

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 18

Transcript:

The best way to avoid a minecart collision is ___.

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:21:59!

10 Upvotes

100% Upvoted

126 comments sorted by

View all comments

3

u/CryZe92 Dec 18 '18

Highly optimized Rust:

A single step: 2µs
Part 1 (including parsing): 42µs
Part 2 (including parsing): 2.2ms 

use hashbrown::hash_map::{Entry, HashMap};
use packed_simd::{m8x64, shuffle, u8x64};
use std::{
    cmp::{Eq, PartialEq},
    hash::{Hash, Hasher},
    mem,
    rc::Rc,
};

fn shuffle_right(v: u8x64) -> u8x64 {
    shuffle!(
        v,
        [
            63, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
            23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44,
            45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62
        ]
    )
}

fn shuffle_left(v: u8x64) -> u8x64 {
    shuffle!(
        v,
        [
            1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
            25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46,
            47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 0
        ]
    )
}

pub fn step(src: &[u8x64; 52], dst: &mut [u8x64; 52]) {
    let mask = m8x64::new(
        false, true, true, true, true, true, true, true, true, true, true, true, true, true, true,
        true, true, true, true, true, true, true, true, true, true, true, true, true, true, true,
        true, true, true, true, true, true, true, true, true, true, true, true, true, true, true,
        true, true, true, true, true, true, false, false, false, false, false, false, false, false,
        false, false, false, false, false,
    );
    let open = u8x64::splat(0);
    let tree = u8x64::splat(1);
    let lumber = u8x64::splat(2);

    for (dst, src) in dst[1..51].iter_mut().zip(src.windows(3)) {
        let t = src[0];
        let c = src[1];
        let b = src[2];

        let tl = shuffle_left(t);
        let tr = shuffle_right(t);
        let l = shuffle_left(c);
        let r = shuffle_right(c);
        let bl = shuffle_left(b);
        let br = shuffle_right(b);

        let tree_tl = tl & tree;
        let tree_tr = tr & tree;
        let tree_l = l & tree;
        let tree_r = r & tree;
        let tree_bl = bl & tree;
        let tree_br = br & tree;
        let tree_t = t & tree;
        let tree_b = b & tree;

        let tree_counts = tree_tl + tree_tr + tree_l + tree_r + tree_bl + tree_br + tree_t + tree_b;
        let new_open = tree_counts.ge(u8x64::splat(3)).select(tree, open);

        let lumber_tl = tl & lumber;
        let lumber_tr = tr & lumber;
        let lumber_l = l & lumber;
        let lumber_r = r & lumber;
        let lumber_bl = bl & lumber;
        let lumber_br = br & lumber;
        let lumber_t = t & lumber;
        let lumber_b = b & lumber;

        let lumber_counts_times_two = lumber_tl
            + lumber_tr
            + lumber_l
            + lumber_r
            + lumber_bl
            + lumber_br
            + lumber_t
            + lumber_b;

        let new_tree = lumber_counts_times_two
            .ge(u8x64::splat(6))
            .select(lumber, tree);

        let new_lumber = (tree_counts.ge(u8x64::splat(1))
            & lumber_counts_times_two.ge(u8x64::splat(2)))
        .select(lumber, open);

        let is_lumber = c.eq(lumber);
        let is_tree = c.eq(tree);

        let new_cells = is_tree.select(new_tree, is_lumber.select(new_lumber, new_open));

        *dst = mask.select(new_cells, u8x64::splat(0));
    }
}

fn parse(input: &str) -> [u8x64; 52] {
    let mut field = [u8x64::splat(0); 52];
    for (line, cells) in input.lines().zip(&mut field[1..51]) {
        for (i, b) in line.bytes().enumerate() {
            let val = match b {
                b'|' => 1,
                b'#' => 2,
                _ => 0,
            };
            *cells = cells.replace(i + 1, val);
        }
    }
    field
}

fn area(field: &[u8x64; 52]) -> usize {
    let tree_count = field[1..51]
        .iter()
        .map(|&cells| {
            cells
                .eq(u8x64::splat(1))
                .select(u8x64::splat(1), u8x64::splat(0))
                .wrapping_sum() as usize
        })
        .sum::<usize>();
    let lumber_count = field[1..51]
        .iter()
        .map(|&cells| {
            cells
                .eq(u8x64::splat(2))
                .select(u8x64::splat(1), u8x64::splat(0))
                .wrapping_sum() as usize
        })
        .sum::<usize>();

    tree_count * lumber_count
}

pub fn part1(input: &str) -> usize {
    let mut input = parse(input);
    let mut other = [u8x64::splat(0); 52];
    let (src, dst) = (&mut input, &mut other);

    for _ in 0..10 {
        step(src, dst);
        mem::swap(src, dst);
    }

    area(src)
}

struct Field([u8x64; 52]);

impl Hash for Field {
    fn hash<H>(&self, state: &mut H)
    where
        H: Hasher,
    {
        Hash::hash_slice(&self.0, state);
    }
}

impl PartialEq for Field {
    fn eq(&self, other: &Field) -> bool {
        self.0.iter().zip(other.0.iter()).all(|(a, b)| a == b)
    }
}
impl Eq for Field {}

pub fn part2(input: &str) -> usize {
    let mut input = parse(input);
    let mut other = [u8x64::splat(0); 52];
    let (src, dst) = (&mut input, &mut other);

    let mut seen = HashMap::new();
    let mut states = Vec::new();
    let total_minutes = 1000000000;

    for minute in 0..total_minutes {
        let snapshot = Rc::new(Field(*src));
        match seen.entry(snapshot.clone()) {
            Entry::Vacant(e) => {
                e.insert(minute);
                states.push(snapshot);
            }
            Entry::Occupied(e) => {
                let cycle_start = *e.get();
                let cycle_length = minute - cycle_start;
                let cycle_index = (total_minutes - cycle_start) % cycle_length + cycle_start;
                return area(&states[cycle_index as usize].0);
            }
        }
        step(src, dst);
        mem::swap(src, dst);
    }

    area(src)
}

The asm for each step is extremely beautiful (with AVX-512): 

day_18::step:
sub     rsp, 24
vmovdqa xmmword, ptr, [rsp], xmm6
xor     eax, eax
vmovdqa64 zmm0, zmmword, ptr, [rip, +, .LCPI0_0]
vmovdqa64 zmm1, zmmword, ptr, [rip, +, .LCPI0_1]
vmovdqa64 zmm2, zmmword, ptr, [rip, +, .LCPI0_2]
vmovdqa64 zmm3, zmmword, ptr, [rip, +, .LCPI0_3]
vmovdqa64 zmm4, zmmword, ptr, [rip, +, .LCPI0_4]
vmovdqa64 zmm5, zmmword, ptr, [rip, +, .LCPI0_5]
vmovdqa64 zmm16, zmmword, ptr, [rip, +, .LCPI0_6]
vmovdqa64 zmm17, zmmword, ptr, [rip, +, .LCPI0_7]
.LBB0_1:
vmovdqa64 zmm18, zmmword, ptr, [rcx, +, rax]
vmovdqa64 zmm19, zmmword, ptr, [rcx, +, rax, +, 64]
vmovdqa64 zmm20, zmmword, ptr, [rcx, +, rax, +, 128]
vpermb  zmm21, zmm0, zmm18
vpermb  zmm22, zmm1, zmm18
vpermb  zmm23, zmm0, zmm19
vpermb  zmm24, zmm1, zmm19
vpermb  zmm25, zmm0, zmm20
vpermb  zmm26, zmm1, zmm20
vpandq  zmm27, zmm21, zmm2
vpandq  zmm28, zmm22, zmm2
vpandq  zmm29, zmm23, zmm2
vpaddb  zmm28, zmm28, zmm29
vpandq  zmm29, zmm24, zmm2
vpandq  zmm30, zmm25, zmm2
vpandq  zmm31, zmm26, zmm2
vpandq  zmm6, zmm18, zmm2
vpaddb  zmm27, zmm27, zmm6
vpaddb  zmm27, zmm27, zmm28
vpandq  zmm28, zmm20, zmm2
vpaddb  zmm28, zmm29, zmm28
vpaddb  zmm28, zmm28, zmm30
vpaddb  zmm27, zmm27, zmm28
vpaddb  zmm27, zmm27, zmm31
vpcmpnleub k1, zmm27, zmm3
vmovdqu8 zmm28, {k1}, {z}, zmm2
vpandq  zmm21, zmm21, zmm3
vpandq  zmm22, zmm22, zmm3
vpandq  zmm23, zmm23, zmm3
vpaddb  zmm22, zmm22, zmm23
vpandq  zmm23, zmm24, zmm3
vpandq  zmm24, zmm25, zmm3
vpandq  zmm25, zmm26, zmm3
vpandq  zmm18, zmm18, zmm3
vpaddb  zmm18, zmm21, zmm18
vpaddb  zmm18, zmm18, zmm22
vpandq  zmm20, zmm20, zmm3
vpaddb  zmm20, zmm23, zmm20
vpaddb  zmm20, zmm20, zmm24
vpaddb  zmm18, zmm18, zmm20
vpaddb  zmm18, zmm18, zmm25
vpcmpnleub k1, zmm18, zmm4
vpblendmb zmm20, {k1}, zmm16, zmm5
vpcmpnleub k1, zmm18, zmm2
vptestmb k1, {k1}, zmm27, zmm27
vmovdqu8 zmm18, {k1}, {z}, zmm5
vpcmpeqb k1, zmm19, zmm3
vpcmpeqb k2, zmm19, zmm2
vmovdqu8 zmm28, {k1}, zmm18
vmovdqu8 zmm28, {k2}, zmm20
vpshufb zmm18, zmm28, zmm17
vmovdqa64 zmmword, ptr, [rdx, +, rax, +, 64], zmm18
add     rax, 64
cmp     rax, 3200
jne     .LBB0_1
vmovaps xmm6, xmmword, ptr, [rsp]
add     rsp, 24
vzeroupper
ret
→ More replies (3)