Day 9 (Advent of Code 2022)
đź‘‹ 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.
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.
// in `src/main.rs` mod parse; fn main() { // etc. }
$ 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:
// 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?
Yes, sure. Good job! Moving on.
Let's make sure we're parsing it right:
// 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:?}"); } }
$ 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:
$ 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:
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:
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):
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:
// 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:
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:
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:
$ 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:
<!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:
$ 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?
Future amos here: I just checked on Linux too: it's not just Windows.
Finally I got the error I expected:
$ 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:
#[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:
$ 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
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?
Have you tried --release
?
Mhh..
$ 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
:
[profile.release] opt-level = 's' lto = true
Which shaves off even more:
$ 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:
<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:
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:
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:
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:
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:
// 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!
Thanks to my sponsors: Aleksandre Khokhiashvili, Lena Schönburg, aureliomarcoag, Jarek Samic, Jake Demarest-Mays, Paul Marques Mota, Tyler Bloom, Ryan, Http 418, L0r3m1p5um, Scott Sanderson, belzael, Ben Wishovich, Christian Bourjau, Jorge Giménez Pérez, Justin Ossevoort, Matt Heise, C J Silverio, Timothée Gerber, Xavier Groleau and 235 more
If you liked what you saw, please support my work!
Here's another article just for you:
Writing Rust is pretty neat. But you know what's even neater? Continuously testing Rust, releasing Rust, and eventually, shipping Rust to production. And for that, we want more than plug-in for a code editor.
We want... a workflow.
Why I specifically care about this
This gets pretty long, so if all you want is the advice, feel free to directly.