From f41b593e8d1169a6e67f689f0e9115c6afa8c3e8 Mon Sep 17 00:00:00 2001 From: Greg Burri Date: Mon, 5 Dec 2022 12:09:19 +0100 Subject: [PATCH] Day 5 --- data/day05.input | 513 +++++++++++++++++++++++++++++++++++++++++++++++ src/day05.rs | 111 ++++++++++ src/main.rs | 10 + 3 files changed, 634 insertions(+) create mode 100644 data/day05.input create mode 100644 src/day05.rs diff --git a/data/day05.input b/data/day05.input new file mode 100644 index 0000000..a572b71 --- /dev/null +++ b/data/day05.input @@ -0,0 +1,513 @@ +[G] [D] [R] +[W] [V] [C] [T] [M] +[L] [P] [Z] [Q] [F] [V] +[J] [S] [D] [J] [M] [T] [V] +[B] [M] [H] [L] [Z] [J] [B] [S] +[R] [C] [T] [C] [T] [R] [D] [R] [D] +[T] [W] [Z] [T] [P] [B] [B] [H] [P] +[D] [S] [R] [D] [G] [F] [S] [L] [Q] + 1 2 3 4 5 6 7 8 9 + +move 1 from 3 to 5 +move 5 from 5 to 4 +move 6 from 7 to 3 +move 6 from 1 to 3 +move 1 from 1 to 9 +move 1 from 1 to 4 +move 3 from 6 to 9 +move 2 from 7 to 5 +move 1 from 5 to 7 +move 1 from 7 to 2 +move 2 from 2 to 5 +move 2 from 6 to 3 +move 6 from 8 to 9 +move 7 from 3 to 9 +move 1 from 8 to 7 +move 8 from 9 to 7 +move 5 from 4 to 8 +move 1 from 6 to 2 +move 2 from 8 to 4 +move 9 from 9 to 1 +move 2 from 8 to 5 +move 1 from 8 to 5 +move 5 from 9 to 2 +move 1 from 6 to 8 +move 5 from 1 to 7 +move 1 from 8 to 2 +move 2 from 1 to 7 +move 1 from 2 to 6 +move 4 from 5 to 4 +move 2 from 1 to 4 +move 13 from 7 to 8 +move 3 from 8 to 6 +move 2 from 6 to 8 +move 10 from 3 to 5 +move 2 from 7 to 6 +move 3 from 5 to 6 +move 10 from 8 to 1 +move 1 from 8 to 6 +move 6 from 2 to 4 +move 1 from 5 to 8 +move 5 from 6 to 3 +move 2 from 8 to 6 +move 1 from 7 to 9 +move 2 from 2 to 7 +move 3 from 5 to 1 +move 2 from 7 to 2 +move 6 from 6 to 3 +move 7 from 5 to 6 +move 5 from 3 to 2 +move 10 from 1 to 8 +move 2 from 1 to 3 +move 8 from 3 to 7 +move 9 from 4 to 8 +move 1 from 9 to 2 +move 2 from 7 to 8 +move 4 from 6 to 9 +move 1 from 4 to 9 +move 5 from 7 to 4 +move 3 from 6 to 5 +move 1 from 1 to 5 +move 14 from 4 to 8 +move 3 from 9 to 7 +move 4 from 5 to 9 +move 2 from 4 to 1 +move 27 from 8 to 6 +move 2 from 7 to 2 +move 2 from 7 to 4 +move 4 from 2 to 9 +move 7 from 8 to 4 +move 10 from 4 to 1 +move 18 from 6 to 5 +move 6 from 9 to 2 +move 1 from 9 to 5 +move 11 from 2 to 6 +move 2 from 5 to 4 +move 1 from 2 to 8 +move 2 from 4 to 9 +move 2 from 8 to 3 +move 1 from 6 to 8 +move 4 from 9 to 7 +move 4 from 7 to 8 +move 7 from 5 to 1 +move 4 from 6 to 3 +move 2 from 3 to 7 +move 6 from 5 to 3 +move 2 from 8 to 2 +move 14 from 6 to 2 +move 3 from 8 to 1 +move 15 from 2 to 3 +move 1 from 6 to 1 +move 14 from 3 to 2 +move 2 from 2 to 5 +move 1 from 9 to 3 +move 13 from 1 to 3 +move 4 from 2 to 6 +move 10 from 1 to 3 +move 2 from 6 to 9 +move 6 from 2 to 9 +move 6 from 5 to 2 +move 2 from 6 to 8 +move 7 from 9 to 5 +move 1 from 5 to 8 +move 2 from 7 to 6 +move 34 from 3 to 6 +move 19 from 6 to 2 +move 12 from 6 to 9 +move 3 from 6 to 3 +move 2 from 3 to 2 +move 1 from 6 to 5 +move 17 from 2 to 8 +move 2 from 3 to 2 +move 8 from 9 to 4 +move 7 from 5 to 2 +move 5 from 4 to 1 +move 4 from 1 to 6 +move 1 from 1 to 6 +move 6 from 6 to 8 +move 2 from 8 to 4 +move 17 from 8 to 6 +move 2 from 4 to 5 +move 17 from 6 to 9 +move 22 from 9 to 7 +move 1 from 5 to 2 +move 20 from 2 to 7 +move 29 from 7 to 9 +move 1 from 4 to 7 +move 3 from 8 to 3 +move 1 from 8 to 5 +move 3 from 8 to 2 +move 2 from 2 to 4 +move 27 from 9 to 7 +move 2 from 3 to 2 +move 1 from 5 to 2 +move 18 from 7 to 5 +move 1 from 3 to 2 +move 1 from 5 to 6 +move 18 from 5 to 3 +move 1 from 6 to 3 +move 2 from 9 to 5 +move 10 from 3 to 5 +move 4 from 3 to 6 +move 1 from 7 to 1 +move 1 from 5 to 1 +move 6 from 7 to 6 +move 1 from 6 to 2 +move 4 from 4 to 8 +move 5 from 5 to 4 +move 1 from 3 to 8 +move 2 from 1 to 8 +move 2 from 2 to 5 +move 3 from 3 to 8 +move 6 from 8 to 2 +move 1 from 3 to 9 +move 1 from 6 to 3 +move 6 from 2 to 8 +move 7 from 8 to 4 +move 8 from 5 to 2 +move 5 from 4 to 6 +move 2 from 8 to 3 +move 2 from 3 to 9 +move 1 from 3 to 9 +move 2 from 7 to 1 +move 2 from 1 to 2 +move 12 from 2 to 4 +move 1 from 9 to 7 +move 1 from 6 to 2 +move 9 from 7 to 9 +move 1 from 8 to 2 +move 9 from 9 to 8 +move 6 from 7 to 8 +move 4 from 4 to 1 +move 6 from 2 to 5 +move 1 from 4 to 9 +move 3 from 1 to 9 +move 6 from 4 to 5 +move 5 from 8 to 9 +move 8 from 4 to 6 +move 3 from 9 to 8 +move 1 from 9 to 3 +move 3 from 8 to 3 +move 5 from 9 to 2 +move 3 from 2 to 6 +move 3 from 6 to 9 +move 3 from 6 to 2 +move 4 from 2 to 6 +move 6 from 9 to 7 +move 1 from 1 to 8 +move 8 from 8 to 5 +move 20 from 5 to 3 +move 2 from 2 to 8 +move 6 from 7 to 1 +move 10 from 6 to 3 +move 4 from 6 to 7 +move 4 from 1 to 9 +move 2 from 1 to 2 +move 3 from 6 to 9 +move 5 from 8 to 3 +move 3 from 7 to 9 +move 17 from 3 to 2 +move 1 from 6 to 2 +move 2 from 6 to 9 +move 1 from 6 to 4 +move 12 from 9 to 2 +move 1 from 4 to 7 +move 8 from 3 to 8 +move 8 from 8 to 9 +move 7 from 9 to 2 +move 1 from 9 to 7 +move 18 from 2 to 9 +move 1 from 7 to 2 +move 2 from 7 to 1 +move 1 from 1 to 2 +move 4 from 2 to 7 +move 15 from 9 to 3 +move 1 from 9 to 1 +move 2 from 1 to 8 +move 6 from 2 to 4 +move 8 from 2 to 1 +move 2 from 8 to 5 +move 2 from 9 to 3 +move 4 from 4 to 1 +move 2 from 5 to 8 +move 2 from 8 to 9 +move 14 from 3 to 1 +move 2 from 9 to 7 +move 2 from 4 to 3 +move 1 from 2 to 9 +move 5 from 7 to 9 +move 21 from 1 to 9 +move 2 from 1 to 6 +move 3 from 2 to 4 +move 1 from 7 to 3 +move 19 from 9 to 5 +move 1 from 2 to 7 +move 1 from 7 to 2 +move 3 from 4 to 2 +move 19 from 5 to 7 +move 2 from 2 to 5 +move 1 from 5 to 3 +move 1 from 3 to 4 +move 8 from 9 to 4 +move 1 from 6 to 3 +move 1 from 2 to 6 +move 1 from 2 to 1 +move 8 from 7 to 3 +move 5 from 4 to 7 +move 2 from 6 to 4 +move 1 from 5 to 9 +move 1 from 1 to 6 +move 1 from 1 to 2 +move 2 from 4 to 7 +move 1 from 4 to 2 +move 2 from 4 to 9 +move 1 from 6 to 8 +move 1 from 1 to 5 +move 1 from 8 to 6 +move 1 from 1 to 4 +move 25 from 3 to 1 +move 1 from 4 to 2 +move 2 from 3 to 6 +move 3 from 1 to 9 +move 6 from 9 to 8 +move 1 from 6 to 3 +move 1 from 2 to 9 +move 15 from 7 to 6 +move 2 from 2 to 6 +move 1 from 3 to 8 +move 1 from 1 to 4 +move 6 from 8 to 4 +move 1 from 3 to 8 +move 1 from 8 to 5 +move 2 from 5 to 2 +move 8 from 6 to 7 +move 1 from 8 to 7 +move 1 from 9 to 4 +move 9 from 4 to 5 +move 19 from 1 to 3 +move 9 from 3 to 5 +move 6 from 7 to 2 +move 2 from 1 to 7 +move 7 from 2 to 4 +move 7 from 5 to 6 +move 5 from 4 to 3 +move 3 from 5 to 8 +move 1 from 2 to 4 +move 2 from 4 to 8 +move 14 from 6 to 1 +move 6 from 5 to 6 +move 1 from 5 to 2 +move 7 from 1 to 6 +move 1 from 2 to 4 +move 4 from 6 to 4 +move 1 from 5 to 4 +move 2 from 1 to 9 +move 2 from 9 to 4 +move 2 from 1 to 8 +move 9 from 3 to 6 +move 3 from 7 to 4 +move 4 from 8 to 6 +move 3 from 7 to 6 +move 1 from 7 to 2 +move 1 from 7 to 5 +move 3 from 8 to 4 +move 26 from 6 to 1 +move 8 from 1 to 2 +move 1 from 6 to 4 +move 5 from 2 to 7 +move 2 from 2 to 4 +move 10 from 4 to 7 +move 1 from 6 to 1 +move 22 from 1 to 2 +move 1 from 6 to 1 +move 6 from 4 to 7 +move 1 from 5 to 1 +move 1 from 1 to 2 +move 21 from 7 to 2 +move 38 from 2 to 3 +move 8 from 2 to 6 +move 2 from 4 to 8 +move 2 from 8 to 2 +move 1 from 1 to 3 +move 1 from 2 to 8 +move 1 from 2 to 5 +move 6 from 6 to 4 +move 2 from 4 to 2 +move 2 from 2 to 6 +move 1 from 8 to 2 +move 28 from 3 to 1 +move 11 from 1 to 2 +move 8 from 1 to 7 +move 4 from 6 to 4 +move 8 from 3 to 1 +move 8 from 2 to 5 +move 6 from 5 to 4 +move 2 from 5 to 4 +move 8 from 3 to 4 +move 22 from 4 to 1 +move 2 from 3 to 5 +move 33 from 1 to 5 +move 26 from 5 to 6 +move 4 from 5 to 7 +move 2 from 2 to 7 +move 2 from 7 to 2 +move 2 from 7 to 8 +move 2 from 8 to 3 +move 6 from 1 to 3 +move 5 from 5 to 1 +move 1 from 5 to 7 +move 7 from 7 to 5 +move 4 from 5 to 6 +move 5 from 1 to 8 +move 4 from 2 to 4 +move 2 from 7 to 4 +move 2 from 7 to 3 +move 5 from 4 to 6 +move 1 from 8 to 2 +move 1 from 2 to 4 +move 10 from 3 to 6 +move 44 from 6 to 9 +move 2 from 5 to 7 +move 1 from 5 to 8 +move 41 from 9 to 1 +move 1 from 6 to 4 +move 2 from 8 to 1 +move 1 from 7 to 3 +move 1 from 3 to 8 +move 2 from 9 to 8 +move 29 from 1 to 9 +move 2 from 1 to 5 +move 2 from 8 to 3 +move 1 from 3 to 5 +move 2 from 5 to 9 +move 1 from 5 to 7 +move 25 from 9 to 2 +move 10 from 2 to 1 +move 1 from 7 to 8 +move 2 from 4 to 1 +move 2 from 8 to 9 +move 1 from 8 to 6 +move 4 from 2 to 4 +move 4 from 2 to 5 +move 1 from 6 to 5 +move 1 from 2 to 7 +move 2 from 4 to 1 +move 18 from 1 to 3 +move 8 from 9 to 4 +move 15 from 3 to 9 +move 3 from 4 to 8 +move 4 from 5 to 8 +move 4 from 2 to 4 +move 10 from 9 to 4 +move 4 from 8 to 5 +move 2 from 7 to 2 +move 11 from 4 to 9 +move 12 from 4 to 9 +move 2 from 5 to 7 +move 4 from 2 to 4 +move 5 from 8 to 1 +move 1 from 5 to 6 +move 1 from 4 to 6 +move 1 from 3 to 9 +move 1 from 5 to 7 +move 4 from 1 to 6 +move 6 from 1 to 5 +move 6 from 5 to 9 +move 3 from 7 to 6 +move 9 from 6 to 5 +move 8 from 5 to 2 +move 7 from 2 to 3 +move 1 from 3 to 1 +move 7 from 3 to 5 +move 2 from 4 to 1 +move 1 from 2 to 6 +move 2 from 1 to 3 +move 8 from 5 to 9 +move 3 from 1 to 3 +move 1 from 6 to 1 +move 2 from 4 to 1 +move 1 from 5 to 2 +move 2 from 1 to 6 +move 2 from 6 to 3 +move 2 from 3 to 2 +move 2 from 2 to 4 +move 1 from 2 to 6 +move 3 from 3 to 9 +move 2 from 4 to 8 +move 3 from 3 to 1 +move 4 from 1 to 7 +move 2 from 8 to 4 +move 7 from 9 to 6 +move 1 from 1 to 4 +move 11 from 9 to 7 +move 3 from 9 to 3 +move 14 from 9 to 5 +move 6 from 6 to 5 +move 4 from 5 to 9 +move 10 from 7 to 6 +move 1 from 3 to 7 +move 2 from 4 to 1 +move 4 from 7 to 9 +move 9 from 6 to 1 +move 3 from 6 to 5 +move 15 from 9 to 1 +move 1 from 4 to 7 +move 4 from 9 to 7 +move 12 from 5 to 1 +move 3 from 7 to 3 +move 4 from 7 to 2 +move 1 from 9 to 3 +move 22 from 1 to 2 +move 21 from 2 to 6 +move 3 from 1 to 9 +move 1 from 3 to 7 +move 1 from 7 to 3 +move 1 from 3 to 2 +move 8 from 1 to 4 +move 1 from 9 to 2 +move 7 from 4 to 8 +move 3 from 3 to 9 +move 3 from 3 to 5 +move 4 from 2 to 3 +move 1 from 1 to 3 +move 4 from 8 to 5 +move 2 from 8 to 3 +move 5 from 3 to 2 +move 6 from 5 to 3 +move 2 from 5 to 8 +move 2 from 1 to 7 +move 2 from 7 to 4 +move 15 from 6 to 9 +move 8 from 3 to 1 +move 3 from 5 to 9 +move 2 from 4 to 9 +move 8 from 1 to 3 +move 8 from 9 to 8 +move 1 from 1 to 4 +move 3 from 5 to 9 +move 4 from 8 to 1 +move 1 from 3 to 9 +move 2 from 4 to 3 +move 2 from 8 to 6 +move 3 from 8 to 7 +move 8 from 2 to 5 +move 3 from 5 to 2 +move 4 from 3 to 4 +move 3 from 6 to 1 +move 2 from 5 to 9 +move 4 from 4 to 1 +move 2 from 5 to 6 +move 1 from 5 to 4 +move 2 from 2 to 1 +move 4 from 3 to 9 +move 1 from 7 to 3 +move 2 from 7 to 4 +move 2 from 4 to 7 +move 1 from 6 to 7 +move 1 from 2 to 8 +move 2 from 3 to 9 +move 14 from 1 to 8 +move 1 from 6 to 2 +move 2 from 7 to 1 +move 3 from 8 to 3 +move 6 from 8 to 5 diff --git a/src/day05.rs b/src/day05.rs new file mode 100644 index 0000000..3a0f1bc --- /dev/null +++ b/src/day05.rs @@ -0,0 +1,111 @@ +use std::collections::VecDeque; + +use regex::Regex; + +type Stacks = Vec>; + +pub struct Move { + n: usize, + from: usize, + to: usize, +} + +pub fn parse(s: &str) -> (Stacks, Vec) { + let mut stacks = Vec::new(); + let mut lines = s.lines(); + while let Some(line) = lines.next() { + let chars: Vec = line.trim_end().chars().collect(); + if chars[1] == '1' { + break; + } + let n = (chars.len() + 1) / 4; + for _ in stacks.len()..n { + stacks.push(VecDeque::new()); + } + + for i in 0..n { + let pos_char = i * 4 + 1; + if chars[pos_char] != ' ' { + stacks[i].push_front(chars[pos_char]); + } + } + } + + lines.next(); // Drop the empty line. + + let r = Regex::new(r"move (\d+) from (\d+) to (\d+)").unwrap(); + let mut moves = Vec::new(); + while let Some(line) = lines.next() { + let cap = r.captures(line).unwrap(); + moves.push(Move { n: cap[1].parse().unwrap(), from: cap[2].parse::().unwrap() - 1, to: cap[3].parse::().unwrap() - 1 }); + } + + (stacks, moves) +} + +pub fn apply_moves_by_crate_mover_9000(stacks: &mut Stacks, moves: &[Move]) { + for m in moves { + for _ in 0..m.n { + if let Some(c) = stacks[m.from].pop_back() { + stacks[m.to].push_back(c); + } else { + break; + } + } + } +} + +pub fn apply_moves_by_crate_mover_9001(stacks: &mut Stacks, moves: &[Move]) { + for m in moves { + let from = stacks.get_mut(m.from).unwrap(); + let mut to_move = from.split_off(from.len() - m.n); + stacks[m.to].append(&mut to_move); + } +} + +pub fn get_top_as_string(stacks: &Stacks) -> String { + let mut result = String::new(); + for stack in stacks { + if let Some(c) = stack.back() { + result.push(*c); + } + } + result +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn part1() { + let stacks_and_moves =" [D] +[N] [C] +[Z] [M] [P] + 1 2 3 + +move 1 from 2 to 1 +move 3 from 1 to 3 +move 2 from 2 to 1 +move 1 from 1 to 2"; + let (mut stacks, moves) = parse(stacks_and_moves); + apply_moves_by_crate_mover_9000(&mut stacks, &moves); + assert_eq!(get_top_as_string(&stacks), "CMZ"); + } + + #[test] + fn part2() { + let stacks_and_moves =" [D] +[N] [C] +[Z] [M] [P] + 1 2 3 + +move 1 from 2 to 1 +move 3 from 1 to 3 +move 2 from 2 to 1 +move 1 from 1 to 2"; + let (mut stacks, moves) = parse(stacks_and_moves); + apply_moves_by_crate_mover_9001(&mut stacks, &moves); + assert_eq!(get_top_as_string(&stacks), "MCD"); + } +} \ No newline at end of file diff --git a/src/main.rs b/src/main.rs index 014c31d..8fbe072 100644 --- a/src/main.rs +++ b/src/main.rs @@ -5,6 +5,7 @@ mod day01; mod day02; mod day03; mod day04; +mod day05; fn day01() -> String { let f = fs::File::open("data/day01.input").unwrap(); @@ -30,6 +31,14 @@ fn day04() -> String { format!("part1: {}, part2: {}", day04::number_fully_contain(&pairs), day04::number_overlaps(&pairs)) } +fn day05() -> String { + let (mut stacks, moves) = day05::parse(&fs::read_to_string("data/day05.input").unwrap()); + let mut stacks2 = stacks.clone(); + day05::apply_moves_by_crate_mover_9000(&mut stacks, &moves); + day05::apply_moves_by_crate_mover_9001(&mut stacks2, &moves); + format!("part1: {}, part2: {}", day05::get_top_as_string(&stacks), day05::get_top_as_string(&stacks2)) +} + fn format_micros(t: u128) -> String { if t < 10_000 { format!("{} μs", t) @@ -53,6 +62,7 @@ fn main() { day02, day03, day04, + day05, ); let args: Vec = env::args().skip(1).collect(); -- 2.45.2