Home
Log in
Avatar for fasterthanlime fasterthanlime
Dec 10, 2022 clock icon 32 min #rust · #advent-of-code · #egui · #wasm · #interactive

Day 9 (Advent of Code 2022)

From the series Advent of Code 2022
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

đź‘‹ This page was last updated ~2 years ago. Just so you know.

The Advent of Code is not a sprint: it's a marathon: sometimes you've got to stop and smell the roses.

Bear

I... what? That's not.. have you done a marathon before?

No, and I haven't taken any creative writing classes either, I think you can tell. Anyway: Day 8 was a bit aggravating for me. In 2020 I gave up AoC after Day 14 I think, and then I skipped a year. It doesn't help that it overlaps some holidays and stuff, but!

My point is! Day 9 sounds like it could be annoying as well (if we get unlucky), unless we have a little fun with it.

The problem statement

So, we have a rope, it has a head (H) that moves, and a tail (T) that follows. They lie on a grid (no fractional coordinates), and must always be touching (overlapping counts, and they can touch diagonally):

....
.TH.
....

....
.H..
..T.
....

...
.H. (H covers T)
...

When the head moves, the tail follows, in the simple case:

.....    .....    .....
.TH.. -> .T.H. -> ..TH.
.....    .....    .....

...    ...    ...
.T.    .T.    ...
.H. -> ... -> .T.
...    .H.    .H.
...    ...    ...

And for the slightly more complicated cases: "if the head and tail aren't touching and aren't in the same row or column, the tail always moves one step diagonally to keep up":

.....    .....    .....
.....    ..H..    ..H..
..H.. -> ..... -> ..T..
.T...    .T...    .....
.....    .....    .....

.....    .....    .....
.....    .....    .....
..H.. -> ...H. -> ..TH.
.T...    .T...    .....
.....    .....    .....

We're given the motions of the head (U = up, D = down, L = left, R = right, numbers mean the number of cells traveled), like:

R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2

We "simply" have to record how many unique positions the tail's been at, and that's our answer! Delightful way to come up with a number, but probably hell to debug.

But first, parsing

Before we get to the fun stuff, let's parse first.

Rust code
// in `src/main.rs`
mod parse;

fn main() {
    // etc.
}
Shell session
$ cargo add nom@7
(cut)

Because I have no idea if the motions are going to bring us on the negative side of (0, 0), this time we'll use a signed integer type, so we can deal with negative coordinates if needed:

Rust code
// in `src/parse.rs`

use nom::{
    branch::alt,
    bytes::complete::tag,
    character::complete::space1,
    combinator::{map, value},
    sequence::{preceded, tuple},
    IResult,
};
use std::fmt;

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub(crate) struct GridPos {
    pub(crate) x: i32,
    pub(crate) y: i32,
}

impl fmt::Debug for GridPos {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "({}, {})", self.x, self.y)
    }
}

impl std::ops::Add for GridPos {
    type Output = GridPos;

    fn add(self, other: GridPos) -> GridPos {
        GridPos {
            x: self.x + other.x,
            y: self.y + other.y,
        }
    }
}

impl std::ops::AddAssign for GridPos {
    fn add_assign(&mut self, other: GridPos) {
        *self = GridPos {
            x: self.x + other.x,
            y: self.y + other.y,
        };
    }
}

impl std::ops::Sub for GridPos {
    type Output = GridPos;

    fn sub(self, other: GridPos) -> GridPos {
        GridPos {
            x: self.x - other.x,
            y: self.y - other.y,
        }
    }
}

#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
pub(crate) enum Direction {
    Up,
    Down,
    Left,
    Right,
}

impl Direction {
    pub(crate) fn parse(i: &str) -> IResult<&str, Self> {
        alt((
            value(Direction::Up, tag("U")),
            value(Direction::Down, tag("D")),
            value(Direction::Left, tag("L")),
            value(Direction::Right, tag("R")),
        ))(i)
    }

    pub(crate) fn delta(self) -> GridPos {
        match self {
            Direction::Up => GridPos { x: 0, y: -1 },
            Direction::Down => GridPos { x: 0, y: 1 },
            Direction::Left => GridPos { x: -1, y: 0 },
            Direction::Right => GridPos { x: 1, y: 0 },
        }
    }
}

#[derive(Debug, Clone, Copy)]
pub(crate) struct Instruction {
    pub(crate) dir: Direction,
    pub(crate) dist: u32,
}

impl Instruction {
    pub(crate) fn parse(i: &str) -> IResult<&str, Self> {
        map(
            tuple((
                Direction::parse,
                preceded(space1, nom::character::complete::u32),
            )),
            |(dir, dist)| Self { dir, dist },
        )(i)
    }
}

Whew! Look at all that code. Fells good to get all that out of my system.

But look, I even used value and space1, and nom's own number parsers, like my readers said. Are you proud of me?

Bear

Yes, sure. Good job! Moving on.

Let's make sure we're parsing it right:

Rust code
// in `src/main.rs`
use nom::{combinator::all_consuming, Finish};
use parse::Instruction;

mod parse;

fn main() {
    let instructions = include_str!("sample-input.txt")
        .lines()
        .map(|l| all_consuming(Instruction::parse)(l).finish().unwrap().1);

    for ins in instructions {
        println!("{ins:?}");
    }
}
Shell session
$ cargo run -q # short form of --quiet
(cut)
Instruction { dir: Right, dist: 4 }
Instruction { dir: Up, dist: 4 }
Instruction { dir: Left, dist: 3 }
Instruction { dir: Down, dist: 1 }
Instruction { dir: Right, dist: 4 }
Instruction { dir: Down, dist: 1 }
Instruction { dir: Left, dist: 5 }
Instruction { dir: Right, dist: 2 }

Alright! That matches up with our src/sample-input.txt file:

R 4
U 4
L 3
D 1
R 4
D 1
L 5
R 2

Now for the fun stuff!

Drawing stuff with egui

I've always wanted to do this. In fact, I've already done this, in a series I've just never published. Do you know how much unpublished stuff I have? You don't want to know.

Anyhoo:

Shell session
$ cargo add egui@0.20 eframe@0.20
(cut)

I've had to switch from my usual Linux VM to Windows because I didn't want to deal with X11 forwarding over SSH / having an X server on Windows. This is all works flawlessly with WSL2, but I'm not using it right now for reasons I don't want to get into (yes, you can use it, it's fine, don't @ me).

Our src/main.rs becomes:

Rust code
use nom::{combinator::all_consuming, Finish};
use parse::{Direction, Instruction};

mod parse;

use eframe::egui;

fn main() {
    let instructions = include_str!("sample-input.txt")
        .lines()
        .map(|l| all_consuming(Instruction::parse)(l).finish().unwrap().1)
        .collect::<Vec<_>>();

    let options = eframe::NativeOptions {
        initial_window_size: Some(egui::vec2(800.0, 600.0)),
        ..Default::default()
    };
    eframe::run_native(
        "AoC 2022 — Day 9",
        options,
        Box::new(|_cc| Box::new(MyApp { instructions })),
    );
}

struct MyApp {
    instructions: Vec<Instruction>,
}

impl eframe::App for MyApp {
    fn update(&mut self, ctx: &egui::Context, _frame: &mut eframe::Frame) {
        egui::CentralPanel::default().show(ctx, |ui| {
            ui.heading("Instructions:");
            for ins in &self.instructions {
                let arrow = match ins.dir {
                    Direction::Up => "⬆",
                    Direction::Down => "⬇",
                    Direction::Right => "➡",
                    Direction::Left => "⬅",
                };
                ui.label(arrow.repeat(ins.dist as _));
            }
        });
    }
}

And looks like this:

Screnshot showing VS Code with the code we mentioned, and an eframe/egui window showing an Instructions header, and some arrows as the instructions

Well that was easy! We'll need a grid, and we'll need to be able to show the position of the tail and the head (they both start at (0, 0)).

In the problem statement, (0, 0) is depicted at the bottom-left. egui has (0, 0) conceptually in the top-left. Neither of these work for us, since, in my puzzle input, the first thing it does is move left, which would be immediately off-screen.

So let's paint the center at the center (and also the head and the tail):

Rust code
struct MyApp {
    instructions: Vec<Instruction>,
    head: GridPos,
    tail: GridPos,
}

impl eframe::App for MyApp {
    fn update(&mut self, ctx: &egui::Context, _frame: &mut eframe::Frame) {
        egui::SidePanel::left("side_panel").show(ctx, |ui| {
            ui.heading("Instructions");
            egui::ScrollArea::new([false, true]).show(ui, |ui| {
                // (cut: showing the arrows)
            })
        });
        egui::CentralPanel::default().show(ctx, |ui| {
            let painter_size = egui::vec2(500.0, 500.0);
            let (res, painter) = ui.allocate_painter(painter_size, Sense::hover());
            let center = res.rect.center().to_vec2();

            const SIDE: f32 = 16.0;
            let to_panel_pos = |pos: GridPos| {
                (egui::vec2(pos.x as f32 * SIDE, pos.y as f32 * SIDE) + center).to_pos2()
            };

            for x in -30..30 {
                for y in -20..20 {
                    let dot = GridPos { x, y };
                    let is_zero = dot.x == 0 && dot.y == 0;

                    let color = if is_zero {
                        Color32::DARK_RED
                    } else {
                        Color32::LIGHT_GRAY
                    };
                    painter.circle_stroke(to_panel_pos(dot), 1.0, Stroke::new(1.0, color));
                }
            }

            // paint the head
            let head_pos = to_panel_pos(self.head);
            painter.circle_stroke(head_pos, 6.0, Stroke::new(2.0, Color32::GREEN));

            // paint the tail
            let tail_pos = to_panel_pos(self.tail);
            painter.circle_stroke(tail_pos, 3.0, Stroke::new(2.0, Color32::YELLOW));

            // paint an arrow from head to tail
            painter.arrow(
                tail_pos,
                head_pos - tail_pos,
                Stroke::new(2.0, Color32::YELLOW),
            )
        });
        ctx.request_repaint();
    }
}

Note that the app_creator argument now becomes:

Rust code
    // in `fn main()`
    eframe::run_native(
        "AoC 2022 — Day 9",
        options,
        Box::new(|_cc| {
            Box::new(MyApp {
                instructions,
                head: GridPos { x: 0, y: 0 },
                tail: GridPos { x: 1, y: 1 },
            })
        }),
    );

And we now get a pretty thing, like this:

Same kind of screenshot as before, but now the instructions are in a side panel, and the central panel shows a map. Every position has a small light gray dot. The head is a large green circle. The head is a smaller yellow circle, and there's an arrow pointing from the tail to the head

Now, let's start implementing the rules!

So, the first thing we need to do is to move the head. We'll do that in a loop, popping instructions off as we go.

Because the GUI code needs to be updated too, I'll just reproduce the whole main.rs file again, with some comments:

Rust code
use std::{collections::VecDeque, time::Duration};

use egui::{Color32, Sense, Stroke};
use nom::{combinator::all_consuming, Finish};
use parse::{Direction, GridPos, Instruction};

mod parse;

use eframe::{egui, epaint::ahash::HashSet};

fn main() {
    let options = eframe::NativeOptions {
        initial_window_size: Some(egui::vec2(1280.0, 720.0)),
        ..Default::default()
    };
    eframe::run_native(
        "AoC 2022 — Day 9",
        options,
        // we have a constructor now! 👇
        Box::new(|_cc| Box::new(MyApp::new())),
    );
}

struct MyApp {
    // for pop_front 👇
    instructions: VecDeque<Instruction>,
    head: GridPos,
    tail: GridPos,
    tail_visited: HashSet<GridPos>,
}

impl MyApp {
    fn new() -> Self {
        let instructions = include_str!("input.txt")
            .lines()
            .map(|l| all_consuming(Instruction::parse)(l).finish().unwrap().1)
            .collect();

        Self {
            instructions,
            head: GridPos { x: 0, y: 0 },
            tail: GridPos { x: 0, y: 0 },
            tail_visited: Default::default(),
        }
    }

    fn update_state(&mut self) {
        // I'd use "let-else" but it breaks rustfmt for now
        let instruction = match self.instructions.front_mut() {
            Some(instruction) => instruction,
            None => return,
        };
        self.head += instruction.dir.delta();

        let diff = self.head - self.tail;
        // there - I keep seeing Haskell solutions that use pattern matching.
        // well, WE CAN HAVE SOME TOO:
        let (dx, dy) = match (diff.x, diff.y) {
            // overlapping
            (0, 0) => (0, 0),
            // touching up/left/down/right
            (0, 1) | (1, 0) | (0, -1) | (-1, 0) => (0, 0),
            // touching diagonally
            (1, 1) | (1, -1) | (-1, 1) | (-1, -1) => (0, 0),
            // need to move up/left/down/right
            (0, 2) => (0, 1),
            (0, -2) => (0, -1),
            (2, 0) => (1, 0),
            (-2, 0) => (-1, 0),
            // need to move to the right diagonally
            (2, 1) => (1, 1),
            (2, -1) => (1, -1),
            // need to move to the left diagonally
            (-2, 1) => (-1, 1),
            (-2, -1) => (-1, -1),
            // need to move up/down diagonally
            (1, 2) => (1, 1),
            (-1, 2) => (-1, 1),
            (1, -2) => (1, -1),
            (-1, -2) => (-1, -1),
            _ => panic!("unhandled case: tail - head = {diff:?}"),
        };
        self.tail.x += dx;
        self.tail.y += dy;
        self.tail_visited.insert(self.tail);

        instruction.dist -= 1;
        if instruction.dist == 0 {
            self.instructions.pop_front();
        }
    }
}

impl eframe::App for MyApp {
    fn update(&mut self, ctx: &egui::Context, _frame: &mut eframe::Frame) {
        self.update_state();

        egui::SidePanel::left("side_panel").show(ctx, |ui| {
            ui.label(format!("{} instructions left", self.instructions.len()));
            ui.label(format!("{} places visited", self.tail_visited.len()));
            egui::ScrollArea::new([false, true]).show(ui, |ui| {
                for ins in &self.instructions {
                    let arrow = match ins.dir {
                        Direction::Up => "⬆",
                        Direction::Down => "⬇",
                        Direction::Right => "➡",
                        Direction::Left => "⬅",
                    };
                    ui.label(arrow.repeat(ins.dist as _));
                }
            })
        });
        egui::CentralPanel::default().show(ctx, |ui| {
            const CANVAS_WIDTH: f32 = 900.0;
            const CANVAS_HEIGHT: f32 = 700.0;
            const SIDE: f32 = 5.0;

            let painter_size = egui::vec2(CANVAS_WIDTH, CANVAS_HEIGHT);
            let (res, painter) = ui.allocate_painter(painter_size, Sense::hover());
            let center = res.rect.center().to_vec2();

            let to_panel_pos = |pos: GridPos| {
                (egui::vec2(pos.x as f32 * SIDE, pos.y as f32 * SIDE) + center).to_pos2()
            };

            let half_width = (CANVAS_WIDTH / SIDE).floor() as i32;
            let half_height = (CANVAS_HEIGHT / SIDE).floor() as i32;

            for x in -half_width..half_width {
                for y in -half_height..half_height {
                    let dot = GridPos { x, y };
                    if !self.tail_visited.contains(&dot) {
                        continue;
                    }
                    let color = Color32::DARK_RED;

                    let dot_pos = to_panel_pos(dot);
                    painter.circle_stroke(dot_pos, 1.0, Stroke::new(2.0, color));
                }
            }

            // paint the head
            let head_pos = to_panel_pos(self.head);
            painter.circle_stroke(head_pos, 2.0, Stroke::new(2.0, Color32::GREEN));

            // paint the tail
            let tail_pos = to_panel_pos(self.tail);
            painter.circle_stroke(tail_pos, 2.0, Stroke::new(2.0, Color32::YELLOW));

            // paint an arrow from head to tail
            painter.arrow(
                tail_pos,
                head_pos - tail_pos,
                Stroke::new(1.0, Color32::YELLOW),
            )
        });

        ctx.request_repaint_after(Duration::from_millis(25));
    }
}

You can adjust the request_repaint_after to request_repaint (without _after) to run "as fast as possible", and you can also set vsync to false (in NativeOptions) to really run as fast as possible.

If that's still not good enough, you can do.. say 10x speed, by calling self.update_state() 10 times in a row! (The instructions do get pretty long after a while).

I'm happy to report that my code seems correct! (Yes, I waited for it to go through the whole output at 1x speed).

Compiling that solution to wasm

I didn't pick egui at random. Not only did they recently gain support for screen readers via AccessKit, they've also supported WASM as a target forever.

And hey, this is a web page!

eframe folks provide a template but I have an existing project, so, let's try to wing it.

They recommend trunk to build it as wasm, so let's get it:

Shell session
$ cargo install trunk
(cut)

The trunk docs say to create an index.html. Using my time-travelling power, I can tell I want it to look like this:

HTML
<!DOCTYPE html>
<html>

<head>
	<link data-trunk rel="rust" data-wasm-opt="2" />

	<style>
		html {
			/* Remove touch delay: */
			touch-action: manipulation;
		}

		html,
		body {
			overflow: hidden;
			margin: 0 !important;
			padding: 0 !important;
			height: 100%;
			width: 100%;
		}

		canvas {
			margin-right: auto;
			margin-left: auto;
			display: block;
			position: absolute;
			top: 0%;
			left: 50%;
			transform: translate(-50%, 0%);
		}
	</style>
</head>

<body>
	<canvas id="canvas"></canvas>
</body>

</html>

Their example had a path/to/index.scss, but we have no CSS for now, so I didn't add it in.

Building with trunk build results in a bunch of errors like:

error[E0463]: can't find crate for `core`
   --> C:\Users\amos\.cargo\registry\src\github.com-1ecc6299db9ec823\ttf-parser-0.17.1\src\aat.rs:531:13
    |
531 |             core::cmp::Ordering::Greater
    |             ^^^^ can't find crate
    |
    = note: the `wasm32-unknown-unknown` target may not be installed
    = help: consider downloading the target with `rustup target add wasm32-unknown-unknown`

(They go by real fast). So I stopped the build and tried:

Shell session
$ rustup target add wasm32-unknown-unknown
info: downloading component 'rust-std' for 'wasm32-unknown-unknown'
info: installing component 'rust-std' for 'wasm32-unknown-unknown'

Weird that trunk didn't do it by itself, but ah well. Maybe it's Just Windows Things?

Amos

Future amos here: I just checked on Linux too: it's not just Windows.

Finally I got the error I expected:

Shell session
$ trunk build
(cut)
   Compiling day9 v0.1.0 (C:\Users\amos\bearcove\aoc2022\day9)
error[E0422]: cannot find struct, variant or union type `NativeOptions` in crate `eframe`
  --> src\main.rs:12:27
   |
12 |     let options = eframe::NativeOptions {
   |                           ^^^^^^^^^^^^^ not found in `eframe`
error: could not compile `day9` due to 2 previous errors
2022-12-10T18:51:57.579392Z ERROR ❌ error
error from HTML pipeline

Caused by:
    0: error from asset pipeline
    1: error during cargo build execution
    2: cargo call returned a bad status
Error: error from HTML pipeline

Caused by:
    0: error from asset pipeline
    1: error during cargo build execution
    2: cargo call returned a bad status

eframe supports both "native" and "web" targets, but we have to set up some conditional compilation. The template uses a couple crates which I think are neat:

$ cargo add console_error_panic_hook@0.1
(cut)
$ cargo add tracing-wasm@0.2
(cut)
$ cargo add wasm-bindgen-futures@0.4
(cut)

And the top of our src/main.rs file now looks like this:

Rust code
#[cfg(target_arch = "wasm32")]
fn main() {
    // Make sure panics are logged using `console.error`.
    console_error_panic_hook::set_once();

    // Redirect tracing to console.log and friends:
    tracing_wasm::set_as_global_default();

    let web_options = eframe::WebOptions::default();

    wasm_bindgen_futures::spawn_local(async {
        eframe::start_web(
            // this is the id of the `<canvas>` element we have
            // in our `index.html`
            "canvas",
            web_options,
            Box::new(|_cc| Box::new(MyApp::new())),
        )
        .await
        .expect("failed to start eframe");
    });
}

#[cfg(not(target_arch = "wasm32"))]
fn main() {
    let options = eframe::NativeOptions {
        initial_window_size: Some(egui::vec2(1280.0, 720.0)),
        ..Default::default()
    };
    eframe::run_native(
        "AoC 2022 — Day 9",
        options,
        Box::new(|_cc| Box::new(MyApp::new())),
    );
}

And... the result is... a 7.1MB wasm blob:

Shell session
$ ls -lhA dist
.rwxrwx--- OREO\amos OREO\amos  55 KB Sat Dec 10 20:35:11 2022 day9-e96d7bdc8524e3a2.js
.rwxrwx--- OREO\amos OREO\amos 7.1 MB Sat Dec 10 20:35:11 2022 day9-e96d7bdc8524e3a2_bg.wasm
.rwxrwx--- OREO\amos OREO\amos 595 B  Sat Dec 10 20:35:11 2022 index.html
Cool bear's hot tip

If you're following this project as-is, and you're using Git to keep track of changes, this is a good time to add /dist to your .gitignore file.

Also, if you're curious, that's the output from lsd.

We can probably do a little bit better than that?

Bear

Have you tried --release?

Mhh..

Shell session
$ trunk build --release
(cut)
$ ls -lhA dist/*.wasm
.rwxrwx--- OREO\amos OREO\amos 2.5 MB Sat Dec 10 20:41:47 2022 day9-c78d4a0e0468b6f6_bg.wasm

Well, that's better!

We can also try adding this to Cargo.toml:

TOML markup
[profile.release]
opt-level = 's'
lto = true

Which shaves off even more:

Shell session
$ ls -lhA dist/*.wasm
.rwxrwx--- OREO\amos OREO\amos 2.1 MB Sat Dec 10 20:47:47 2022 dist\day9-d329af3d19161b6f_bg.wasm

I was previously binaryen's wasm-opt program myself, but it turns out trunk can do this, that's what this line was about:

HTML
	<link data-trunk rel="rust" data-wasm-opt="2" />

Part 1 solution, in your browser

And finally, (after replacing / with ./ manually in the output of trunk because... apparently it really wants an absolute URL?), and adding better controls, I give you:

(You should see an interactive version of my Part 1 solution above. If not, use the "Feedback" button next to the search bar. If yes, use the blue "Play" button in the sidebar to start the simulation).

Here's the final code:

Rust code
use std::{collections::VecDeque, time::Duration};

use egui::{Color32, Sense, Slider, Stroke};
use nom::{combinator::all_consuming, Finish};
use parse::{Direction, GridPos, Instruction};

mod parse;

use eframe::{egui, epaint::ahash::HashSet};

#[cfg(target_arch = "wasm32")]
fn main() {
    // Make sure panics are logged using `console.error`.
    console_error_panic_hook::set_once();

    // Redirect tracing to console.log and friends:
    tracing_wasm::set_as_global_default();

    let web_options = eframe::WebOptions::default();

    wasm_bindgen_futures::spawn_local(async {
        eframe::start_web(
            "canvas",
            web_options,
            Box::new(|_cc| Box::new(MyApp::new())),
        )
        .await
        .expect("failed to start eframe");
    });
}

#[cfg(not(target_arch = "wasm32"))]
fn main() {
    let options = eframe::NativeOptions {
        initial_window_size: Some(egui::vec2(1280.0, 720.0)),
        ..Default::default()
    };
    eframe::run_native(
        "AoC 2022 — Day 9",
        options,
        Box::new(|_cc| Box::new(MyApp::new())),
    );
}

struct MyApp {
    instructions: VecDeque<Instruction>,
    head: GridPos,
    tail: GridPos,
    tail_visited: HashSet<GridPos>,
    speed: usize,
    paused: bool,
    show_sidebar: bool,
    step: bool,
}

impl MyApp {
    fn new() -> Self {
        let instructions = include_str!("input.txt")
            .lines()
            .map(|l| all_consuming(Instruction::parse)(l).finish().unwrap().1)
            .collect();

        Self {
            instructions,
            head: GridPos { x: 0, y: 0 },
            tail: GridPos { x: 0, y: 0 },
            tail_visited: Default::default(),
            speed: 1,
            paused: true,
            show_sidebar: true,
            step: false,
        }
    }

    fn update_state(&mut self) {
        // I'd use "let-else" but it breaks rustfmt for now
        let instruction = match self.instructions.front_mut() {
            Some(instruction) => instruction,
            None => return,
        };
        self.head += instruction.dir.delta();

        let diff = self.head - self.tail;
        let (dx, dy) = match (diff.x, diff.y) {
            // overlapping
            (0, 0) => (0, 0),
            // touching up/left/down/right
            (0, 1) | (1, 0) | (0, -1) | (-1, 0) => (0, 0),
            // touching diagonally
            (1, 1) | (1, -1) | (-1, 1) | (-1, -1) => (0, 0),
            // need to move up/left/down/right
            (0, 2) => (0, 1),
            (0, -2) => (0, -1),
            (2, 0) => (1, 0),
            (-2, 0) => (-1, 0),
            // need to move to the right diagonally
            (2, 1) => (1, 1),
            (2, -1) => (1, -1),
            // need to move to the left diagonally
            (-2, 1) => (-1, 1),
            (-2, -1) => (-1, -1),
            // need to move up/down diagonally
            (1, 2) => (1, 1),
            (-1, 2) => (-1, 1),
            (1, -2) => (1, -1),
            (-1, -2) => (-1, -1),
            _ => panic!("unhandled case: tail - head = {diff:?}"),
        };
        self.tail.x += dx;
        self.tail.y += dy;
        self.tail_visited.insert(self.tail);

        instruction.dist -= 1;
        if instruction.dist == 0 {
            self.instructions.pop_front();
        }
    }
}

impl eframe::App for MyApp {
    fn update(&mut self, ctx: &egui::Context, _frame: &mut eframe::Frame) {
        egui::TopBottomPanel::top("top_panel").show(ctx, |ui| {
            ui.horizontal(|ui| {
                ui.style_mut().spacing.interact_size.y *= 1.4;
                ui.style_mut()
                    .text_styles
                    .get_mut(&egui::TextStyle::Button)
                    .unwrap()
                    .size *= 1.4;

                if ui.button("Reset").clicked() {
                    *self = Self::new();
                }
                if ui.button("Step").clicked() {
                    self.step = true;
                }

                let paused = self.paused;
                ui.toggle_value(&mut self.paused, if paused { "▶" } else { "⏸" });

                ui.toggle_value(&mut self.show_sidebar, "Sidebar");
            });

            ui.horizontal(|ui| {
                ui.label("Speed: ");
                ui.add(Slider::new(&mut self.speed, 1..=20).prefix("x"));
            });
        });

        if self.step {
            self.update_state();
            self.step = false;
        } else if !self.paused {
            for _ in 0..self.speed {
                self.update_state();
            }
            ctx.request_repaint_after(Duration::from_millis(25));
        }

        if self.show_sidebar {
            egui::SidePanel::right("side_panel").show(ctx, |ui| {
                ui.label(format!("{} places visited", self.tail_visited.len()));
                egui::ScrollArea::new([false, true]).show(ui, |ui| {
                    let mut it = self.instructions.iter();
                    for (i, ins) in it.by_ref().enumerate() {
                        if i >= 20 {
                            break;
                        }

                        let arrow = match ins.dir {
                            Direction::Up => "⬆",
                            Direction::Down => "⬇",
                            Direction::Right => "➡",
                            Direction::Left => "⬅",
                        };
                        let dist = ins.dist as usize;
                        if dist > 5 {
                            ui.label(format!("{}+{}", arrow.repeat(5), dist - 5));
                        } else {
                            ui.label(arrow.repeat(dist));
                        }
                    }
                    let remaining = it.count();

                    if remaining > 0 {
                        ui.label(format!("(+ {remaining} more)"));
                    }
                })
            });
        }
        egui::CentralPanel::default().show(ctx, |ui| {
            let mut painter_size = ui.available_size_before_wrap();
            if !painter_size.is_finite() {
                painter_size = egui::vec2(500.0, 500.0);
            }

            const SIDE: f32 = 5.0;

            let (res, painter) = ui.allocate_painter(painter_size, Sense::hover());
            let center = res.rect.center().to_vec2();

            let to_panel_pos = |pos: GridPos| {
                (egui::vec2(pos.x as f32 * SIDE, pos.y as f32 * SIDE) + center).to_pos2()
            };

            let half_width = (painter_size.x / SIDE).floor() as i32;
            let half_height = (painter_size.y / SIDE).floor() as i32;

            for x in -half_width..half_width {
                for y in -half_height..half_height {
                    let dot = GridPos { x, y };
                    let color = if dot.x == 0 && dot.y == 0 {
                        Color32::WHITE
                    } else if self.tail_visited.contains(&dot) {
                        Color32::DARK_RED
                    } else {
                        continue;
                    };

                    let dot_pos = to_panel_pos(dot);
                    painter.circle_stroke(dot_pos, 1.0, Stroke::new(2.0, color));
                }
            }

            // paint the head
            let head_pos = to_panel_pos(self.head);
            painter.circle_stroke(head_pos, 2.0, Stroke::new(2.0, Color32::GREEN));

            // paint the tail
            let tail_pos = to_panel_pos(self.tail);
            painter.circle_stroke(tail_pos, 2.0, Stroke::new(2.0, Color32::YELLOW));

            // paint an arrow from head to tail
            painter.arrow(
                tail_pos,
                head_pos - tail_pos,
                Stroke::new(1.0, Color32::YELLOW),
            )
        });
    }
}

Part 2

In the second part of the day 9 puzzle, the rope is now made up of ten knots! So we can think of it as an array of 10 positions: the head is at index 0, and the tail is at index 9. Index 1 follows 0, 2 follows 1, 3 follows 2, and so on.

Our MyApp struct becomes:

Rust code
struct MyApp {
    instructions: VecDeque<Instruction>,
    knots: [GridPos; 10],
    tail_visited: HashSet<GridPos>,
    speed: usize,
    paused: bool,
    show_sidebar: bool,
    step: bool,
}

The constructor becomes this:

Rust code
impl MyApp {
    fn new() -> Self {
        let instructions = include_str!("input.txt")
            .lines()
            .map(|l| all_consuming(Instruction::parse)(l).finish().unwrap().1)
            .collect();

        Self {
            instructions,
            knots: [GridPos { x: 0, y: 0 }; 10],
            tail_visited: Default::default(),
            speed: 1,
            paused: true,
            show_sidebar: true,
            step: false,
        }
    }

    // etc.
}

And update_state, this:

Rust code
    fn update_state(&mut self) {
        // I'd use "let-else" but it breaks rustfmt for now
        let instruction = match self.instructions.front_mut() {
            Some(instruction) => instruction,
            None => return,
        };
        self.knots[0] += instruction.dir.delta();

        for i in 1..self.knots.len() {
            let diff = self.knots[i - 1] - self.knots[i];
            let (dx, dy) = match (diff.x, diff.y) {
                // overlapping
                (0, 0) => (0, 0),
                // touching up/left/down/right
                (0, 1) | (1, 0) | (0, -1) | (-1, 0) => (0, 0),
                // touching diagonally
                (1, 1) | (1, -1) | (-1, 1) | (-1, -1) => (0, 0),
                // need to move up/left/down/right
                (0, 2) => (0, 1),
                (0, -2) => (0, -1),
                (2, 0) => (1, 0),
                (-2, 0) => (-1, 0),
                // need to move to the right diagonally
                (2, 1) => (1, 1),
                (2, -1) => (1, -1),
                // need to move to the left diagonally
                (-2, 1) => (-1, 1),
                (-2, -1) => (-1, -1),
                // need to move up/down diagonally
                (1, 2) => (1, 1),
                (-1, 2) => (-1, 1),
                (1, -2) => (1, -1),
                (-1, -2) => (-1, -1),
                // 🆕 need to move diagonally
                (-2, -2) => (-1, -1),
                (-2, 2) => (-1, 1),
                (2, -2) => (1, -1),
                (2, 2) => (1, 1),
                _ => panic!("unhandled case: tail - head = {diff:?}"),
            };
            self.knots[i].x += dx;
            self.knots[i].y += dy;

            if i == self.knots.len() - 1 {
                self.tail_visited.insert(self.knots[i]);
            }
        }

        instruction.dist -= 1;
        if instruction.dist == 0 {
            self.instructions.pop_front();
        }
    }

Then we need to paint each knot, and we can do something pretty:

Rust code
            // paint each knot
            let num_knots = self.knots.len();

            for (i, knot_pos) in self.knots.iter().copied().enumerate() {
                let knot_pos = to_panel_pos(knot_pos);
                if i > 0 {
                    // paint an arrow from the previous knot to this one
                    let prev_pos = to_panel_pos(self.knots[i - 1]);
                    painter.arrow(
                        prev_pos,
                        knot_pos - prev_pos,
                        Stroke::new(1.0, Color32::YELLOW),
                    )
                }
            }

            for (i, knot_pos) in self.knots.iter().copied().enumerate() {
                let knot_pos = to_panel_pos(knot_pos);
                painter.circle_filled(
                    knot_pos,
                    2.0,
                    Color32::from_rgb(
                        20,
                        60 + ((255.0 - 60.0) * (num_knots as f32 - i as f32) / num_knots as f32)
                            as u8,
                        20,
                    ),
                );
            }

And what do you know, it gives the correct answer!

Part 2 solution, in your browser

Here's the embed for my part 2 solution, so you can witness it in its full glory:

And with that, I must bid you adieu! I realize I'm one day late and cannot seem to catch up with advent of code, but, at least we had fun today :) Look at that rope go!

You're reading the Advent of Code 2022 series.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Reddit logo Comment on /r/fasterthanlime

If you liked what you saw, please support my work!

Github logo Donate on GitHub Patreon logo Donate on Patreon

Here's another article just for you:

Futures Nostalgia
Apr 03, 2022
clock icon 1 hour 4 min #rust · #async · #futures · #tower · #hyper

Up until recently, hyper was my favorite Rust HTTP framework. It's low-level, but that gives you a lot of control over what happens.

Here's what a sample hyper application would look like:

Shell session
$ cargo new nostalgia
     Created binary (application) `nostalgia` package
Shell session
$ cd nostalgia
$ cargo add hyper@0.14 --features "http1 tcp server"
    Updating 'https://github.com/rust-lang/crates.io-index' index
      Adding hyper v0.14 to dependencies with features: ["http1", "tcp", "server"]
$ cargo add tokio@1 --features "full"
    Updating 'https://github.com/rust-lang/crates.io-index' index
      Adding tokio v1 to dependencies with features: ["full"]
Read more