# Advent of Code 2022 - Day 17

By Eric Burden | December 18, 2022

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Rust. I’ll post my solutions and code to GitHub as well. After finishing last year (and 2015-2019) in Julia, I needed to spend some time with Rust again! If you haven’t given AoC a try, I encourage you to do so along with me!

# Day 17 - Pyroclastic Flow

Find the problem description HERE.

## The Input - Left, Left, Left Right Left

You know what’s the easy part of today’s puzzle? Parsing a string of two kinds of characters into Left/Right directions. You know what’s the fun part of today’s input? Making that list of characters into an infinite iterator! Yeah, my idea of fun may be a bit different than most. Ah well, more for me!


/// Represents a gust from the jets of gas, either to the left or right.
#[derive(Debug, Clone, Copy)]
enum Gust {
Left,
Right,
}

/// An iterator that produces gusts of gas in an repeating cycle
#[derive(Debug, Clone)]
struct GasJetIter {
iter: Vec<Gust>,
pub idx: usize,
}

/// Iterator implementation for GasJetIter. Just returns the values contained
/// in a repeating cycle.
impl Iterator for GasJetIter {
type Item = Gust;

fn next(&mut self) -> Option<Self::Item> {
let result = Some(self.iter[self.idx]);
self.idx = (self.idx + 1) % self.iter.len();
result
}
}

/// Convert a list of Gusts into a GasJetIter
impl From<Vec<Gust>> for GasJetIter {
fn from(iter: Vec<Gust>) -> Self {
GasJetIter {
iter,
idx: Default::default(),
}
}
}

/// Module to wrap the parsing functions for today's puzzle
mod parser {
use super::*;
use anyhow::{anyhow, Result};
use nom::{
branch::alt,
character::complete::char,
combinator::{map, value},
multi::many1,
Finish, IResult,
};

/// Nom parser for '<' -> Gust::Left
fn push_left(s: &str) -> IResult<&str, Gust> {
value(Gust::Left, char('<'))(s)
}

/// Nom parser for '>' -> Gust::Right
fn push_right(s: &str) -> IResult<&str, Gust> {
value(Gust::Right, char('>'))(s)
}

/// Nom parser for a Gust in either direction
fn push(s: &str) -> IResult<&str, Gust> {
alt((push_left, push_right))(s)
}

/// Nom parser for a list of Gusts
fn pushes(s: &str) -> IResult<&str, Vec<Gust>> {
many1(push)(s)
}

/// Nom parser to map a GasJetIter to a list of Gusts
fn gas_jet_iter(s: &str) -> IResult<&str, GasJetIter> {
map(pushes, GasJetIter::from)(s)
}

/// Main parsing function, attempts to parse the input into a GasJetIter and
/// return it.
pub fn parse(s: &str) -> Result<GasJetIter> {
let (_, result) = gas_jet_iter(s).finish().map_err(|e| anyhow!("{e}"))?;
Ok(result)
}
}

const INPUT: &str = include_str!("../../input/17/input.txt");

/// Parse that input!
parser::parse(INPUT).unwrap()
}


The neat thing here is that we can pass one mutable reference to that iterator around and always get the next Gust in the sequence. That’s going to come in handy for…

## Part One - Drop It Like It’s Rock

Now, look, I’m as big a fan of Tetris as anyone. I’m not a super big fan of needing to prove my competence as a programmer to a gosh darn elephant! Especially given that they were there when we did that mapping through the steam valves. Well, time to prove that elephant wrong! For part one, we need to model what happens when 2022 oddly predictably shaped rocks fall into this tall cave chamber. I know how to make this make more sense: rocks as bits!

/// Solve Day 17, Part 1
fn solve(input: &GasJetIter) -> u32 {
// We need an owned copy of the iterator so we can use it in both parts
let mut gas_jets = input.to_owned();
let total_rocks = 2022;

// Since the maximum height of any rock is 4, a chamber than can hold
// up to rocks * 4 levels will be plenty big enough.
let mut chamber = Chamber::with_capacity(total_rocks * 4);

// Produce rocks of the appropriate shape in a cycle, up to total_rocks
// times.
for rock in Rock::all().iter().cycle().take(total_rocks) {
}

// Repor the total height of the rocks in the chamber
chamber.height() as u32
}

// You'll note that we're storing rocks as u32 integers. This makes collision
// checking much easier, as well as adding rocks to the chamber. It does, however
// make _reading_ the code a bit more difficult. These are the 32-bit integers
// that represent the column just to the left of the left wall and the column
// just to the right of the right wall. If any part of our rock overlaps one of
// those spaces and the wind tries to push it in the corresponding direction,
// it won't move over.
const LEFT_WALL: u32 = 0x40404040;
const RIGHT_WALL: u32 = 0x01010101;

/// Represents one of the rocks.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Rock(u32);

impl Rock {
/// Produce a list of all five rock shapes, in order. This is what they look
/// like in octal. Printed out in binary one byte at a time, with each byte
/// on a new line, they look like this (using . instead of 0 to make it easier
/// to see):
///
/// ...1111.  ....1...  .....1..  ...1....  ...11...
/// ........  ...111..  .....1..  ...1....  ...11...
/// ........  ....1...  ...111..  ...1....  ........
/// ........  ........  ........  ...1....  ........
const fn all() -> [Self; 5] {
[
Self(0x0000001E), // -
Self(0x00081C08), // +
Self(0x0004041C), // L
Self(0x10101010), // |
Self(0x00001818), // #
]
}

/// Try to move a rock over to the left or right from a gas jet
/// within the chamber.
fn shove(&mut self, push: Gust, levels: u32) {
// Get a copy of the rock bits
let mut pushed = self.0;

match push {
// If pushed to the left and not against the wall, move the rock
// to the left.
Gust::Left => {
if self.0 & LEFT_WALL == 0 {
pushed = self.0 << 1
}
}

// If pushed to the right and not against the wall, move the rock
// to the right.
Gust::Right => {
if self.0 & RIGHT_WALL == 0 {
pushed = self.0 >> 1
}
}
}

// If the pushed rock isn't colliding with anything in the same levels
// as it in the chamber, then update the rock's horizontal position.
if pushed & levels == 0 {
self.0 = pushed
}
}

/// Check to see if this rock collides with another object.
fn collides(&self, other: u32) -> bool {
self.0 & other > 0
}

/// Produce the bytes of the rock in order, skipping the empty bytes
fn bytes(&self) -> impl Iterator<Item = u8> {
self.0.to_le_bytes().into_iter().take_while(|b| *b > 0)
}
}

/// Represents the chamber where the rocks are being dropped
#[derive(Debug, Default, Clone)]
struct Chamber(Vec<u8>);

impl Chamber {
/// Create a new chamber with a set capacity
fn with_capacity(n: usize) -> Self {
Self(Vec::with_capacity(n))
}

/// Report the height of the rocks in the chamber
fn height(&self) -> usize {
self.0.len()
}

/// Add a new level (byte) to the chamber
fn push(&mut self, level: u8) {
self.0.push(level)
}

/// Get a 4-wide chunk of bytes from the chamber, starting at level.
fn get_level_chunk(&self, level: usize) -> u32 {
if level >= self.0.len() {
return 0;
}

// Starting at level, take up to four bytes from the chamber, reverse
// the production (so that the chunk is right-side up) of bytes, then
// convert the four bytes into a single u32 by shifting existing bits
// left and adding each new byte to the first 8 bits after the shift.
self.0
.iter()
.skip(level)
.take(4)
.rev()
.fold(0, |acc, byte| (acc << 8) | *byte as u32)
}

/// Add a rock to the top of the chamber and allow it to fall until it
/// comes to rest on another rock or the floor.
fn add_rock(&mut self, gas_jets: &mut GasJetIter, mut rock: Rock) {

// Start the rock out three levels above the top of chamber, which is
// the top level with any rock parts.
let mut level = self.height() + 3;

// Until the rock comes to rest...
loop {
// Get the chunk of chamber levels starting at level
let levels = self.get_level_chunk(level);

// Get the next gust from the gas jets
let jet = gas_jets.next().unwrap();

// Attempt to shove the rock over
rock.shove(jet, levels);

// If the current level is above the highest level with a rock in it
// in the chamber, drop the level and shove the rock again.
if level > self.height() {
level -= 1;
continue;
}

// Now get the chunk of the chamber starting one level below where
// we started. This simulates the rock dropping down one level.
let levels = self.get_level_chunk(level.saturating_sub(1));

// Check to see if the rock would collide with anything if it moved down.
let collision = rock.collides(levels);

// If we reached the floor or would collide with another rock...
if level == 0 || collision {

// Add the rock to the chamber, layer by layer. Where there's a
// chamber level already there for the layer of rock we're adding,
// just add the layer of rock to the level. Otherwise, push the
// layer to the top of the chamber's bytes.
for byte in rock.bytes() {
if level < self.height() {
self.0[level] |= byte;
} else {
self.push(byte);
}
level += 1;
}
break;
}

// If the rock doesn't need to stop due to the floor or collision, keep
// going, dropping the rock another level and going again.
level -= 1;
}
}
}


Granted, the whole bitwise thing is probably a bit of a questionable choice, but, as we have established, I have a bit of a strange sense of fun, and that includes operating on bits to speed up execution times. In this case, it meant sub-millisecond run times for this part. Actually, spoiler alert, this approach manages to parse the input and run both parts in around half a millisecond. Speedy!

## Part Two - Never Enough! Never, Never!

Ok, these elephants are really starting to grind my gears! I mean, I could calculate how tall this theoretical rock tower will be after ONE TRILLION rocks fall through the chamber. Or I could just leave the elephants in the cave and let them figure it out. Good thing for them I like coding puzzles.

use std::collections::HashMap;

/// Solve Day 17, Part 2
fn solve(input: &GasJetIter) -> u32 {
// We need an owned copy of the iterator so we can use it in both parts
let mut gas_jets = input.to_owned();
let total_rocks = 1_000_000_000_000; // That's a _lot_ of rocks...
let mut rocks_added = 0; // Number of rocks added to the chamber

// Keep up with the states we've seen of the chamber before. The state includes
// the top 8 levels of the chamber, the shape of the last rock added to the
// chamber, and the current internal index of the gas_jets.
let mut seen = HashMap::with_capacity(2048);

// Why use 2048 as the capacity now? It's larger than the repeat length of the
// chamber. What repeat length? Well, as it turns out, typically when Advent of
// Code asks you what the state of some data structure will be one bazillion
// iterations later, there's probably a cycle in the state of the data structure
// somewhere that can be used to calculate the final state without needing to
// simulate each step. In my case, the state of the top layers of the chamber
// repeated every 1700 rocks dropped or so.
let mut chamber = Chamber::with_capacity(2048);

// How much height has been accumulated so far?
let mut accumulated_height = 0;

// An iterator to produce rocks of the appropriate shape in a cycle.
let mut rock_types = Rock::all().into_iter().cycle();

// Until we've added all gajillion rocks...

// Get the next rock, add it to the chamber, account for it, and if the
// chamber has fewer than 8 levels, do it again. We're checking the state
// based on the top 8 levels, so no checking until we have at least 8 levels.
let rock = rock_types.next().unwrap();
if chamber.height() < 8 {
continue;
}

// Check to see if we've seen this state of the top 8 levels of the chamber
// before. If so, time to use that cycle!
let state = (chamber.skyline(), rock, gas_jets.idx);
if let Some((prev_rocks_added, prev_height)) = seen.get(&state) {
// The number of rocks added in each repeating cycle.

// The number of repeats left before we add the final rock.
let repeats: usize = (total_rocks - rocks_added) / repeat_len;

// Add all the rocks in all the repeating cycles between here and the end.

// Add the chamber height of the cycle to the accumulated height
accumulated_height += repeats * (chamber.height() - prev_height);

// Clear the map of seen states. We don't want to do everything inside
// this if block again on the next iteration, after all.
seen.clear();
continue;
}

// If we haven't seen this state before, add it to the map and keep going.
}

// Report the current height of the chamber and the accumulated height from all
// the cycles. The chamber will contain all the rocks dropped up to the start
// of the second repetition of the cycle, then all the rocks that would be
// dropped after the last full cycle ended.
(chamber.height() as u64 + accumulated_height as u64).into()
}

impl Chamber {
/// Get the 'skyline' of the top of the chamber. Really, it's just a u64 with
/// bits representing the top 8 levels of the chamber.
fn skyline(&self) -> Option<u64> {

// If the chamber is less than 8 levels tall, we can't take a skyline
if self.height() < 8 {
return None;
}

// Take the top 8 levels of the chamber and fold them into a 64-bit integer.
let result = self
.0
.iter()
.rev()
.take(8)
.fold(0u64, |acc, byte| (acc << 8) | *byte as u64);
Some(result)
}
}


Pro Tip: Anytime Advent of Code tells you to do a thing a ridiculous number of times, there’s probably some cycle in there that you can exploit. Today’s puzzle is no different! Since the pattern of dropping rocks repeats, you just need to know the height of the tower before the pattern, the height added by each repeat of the pattern, the number of repeats, and the height added after the last full repeat of the pattern. Then, math!

## Wrap Up

This was my favorite puzzle so far! We had a lot of interesting “bits” today (see what I did there?). Infinite iterators, bitwise operations, stacking bytes, and infeasibly large numbers. What’s not to love? This is a good level of difficulty for this part of the year, and while it took me a while to work out the strategy for leveraging bits as rocks, once I started going down the path of using boolean arrays, I knew it was just one short step to bits! I’m still a bit behind on my blog posts, so I can tell you now that Day 18 is also interesting, so come on back for that one!