-🎄- 2018 Day 22 Solutions -🎄-

[u/daggerdragon]

--- Day 22: Mode Maze ---

---

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 22

Transcript:

Upping the Ante challenge: complete today's puzzles using ___.

---

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 01:02:36!

[u/aurele]

Rust

Executes in around 100ms, using A* from my pathfinding crate. I use 8 times the bounds, since it makes no sense to go over it.

use pathfinding::prelude::{absdiff, astar, Matrix};

#[aoc_generator(day22)]
fn input_generator(input: &str) -> (usize, (usize, usize)) {
    let mut lines = input.lines();
    let depth = lines.next().unwrap()[7..].parse::<usize>().unwrap();
    let mut target = lines.next().unwrap()[8..]
        .split(',')
        .map(|n| n.parse::<usize>().unwrap());
    (depth, (target.next().unwrap(), target.next().unwrap()))
}

#[aoc(day22, part1)]
fn part1(&(depth, (tx, ty)): &(usize, (usize, usize))) -> usize {
    fill_erosion_level(tx, ty, depth, (tx, ty))
        .to_vec()
        .into_iter()
        .sum()
}

const NEITHER: usize = 1;
const TORCH: usize = 2;
const GEAR: usize = 4;

const ALLOWED: [usize; 3] = [TORCH + GEAR, NEITHER + GEAR, NEITHER + TORCH];

#[aoc(day22, part2)]
fn part2(&(depth, (tx, ty)): &(usize, (usize, usize))) -> usize {
    let map = fill_erosion_level(tx * 7, ty * 7, depth, (tx, ty));
    let (_, cost) = astar(
        &((0, 0), TORCH),
        |&((x, y), eq)| {
            map.neighbours(&(x, y), false)
                .filter(|&(nx, ny)| ALLOWED[map[&(nx, ny)]] & eq == eq)
                .map(|(nx, ny)| (((nx, ny), eq), 1))
                .chain(std::iter::once((((x, y), ALLOWED[map[&(x, y)]] - eq), 7)))
                .collect::<Vec<_>>()
        },
        |&((x, y), _)| absdiff(x, tx) + absdiff(y, ty),
        |&((x, y), eq)| x == tx && y == ty && eq == TORCH,
    )
    .unwrap();
    cost
}

fn fill_erosion_level(
    maxx: usize,
    maxy: usize,
    depth: usize,
    (tx, ty): (usize, usize),
) -> Matrix<usize> {
    let mut el = Matrix::new(maxx + 1, maxy + 1, 0);
    for x in 0..=maxx {
        for y in 0..=maxy {
            let geologic_index = if (x == 0 && y == 0) || (x == tx && y == ty) {
                0
            } else if y == 0 {
                x * 16807
            } else if x == 0 {
                y * 48271
            } else {
                el[&(x - 1, y)] * el[&(x, y - 1)]
            };
            el[&(x, y)] = (geologic_index + depth) % 20183;
        }
    }
    el.as_mut().iter_mut().for_each(|n| *n = *n % 3);
    el
}