justahero.de

Here is the challenge of day 3 of Advent Of Code. Today's challenge deals with loading all of the rucksacks with supplies for a journey.

Part 1

Unfortunately some packed items need to be rearranged in the rucksacks. Each rucksack has two large compartments, all items are distributed evenly to both compartments. The elves made a list of all items currently in each rucksack but they need to help to figure out which item appears in both compartments.

Given the following sample input:

vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw

each line contains the content of one rucksack, e.g. vJrwpWtwJgWrhcsFMMfFFhFp. Each character a to z and A to Z represents an item. The first half is put into one compartment, the second half in the other compartment.

all: vJrwpWtwJgWrhcsFMMfFFhFp
1st: vJrwpWtwJgWr
         ^
2nd:             hcsFMMfFFhFp
                            ^

The item "p" is the entry that appears in both compartments. The goal is to prioritize the item arrangement, every item can be converted to a priority value.

lower case items a..=z have priorities of 1..=26
upper case items A..=Z have priorities of 27..=52

The task is to find all duplicate items in all rucksacks and to calculate the sum of all priorities of these items.

We setup the project as before (see Day 1's setup). We also add the itertools crate to have some useful iterator methods at hand. Let's put the current sample data into a test into out src/main.rs file.

fn part1(rucksacks: &[(&str, &str)]) -> u32 {
    todo!()
}

fn parse(input: &str) -> Vec<(&str, &str)> {
    todo!()
}

fn main() {
    let input = parse(include_str!("input.txt"));
    println!("Part 1: {}", part1(&input));
}

#[cfg(test)]
mod tests {
    use crate::*;

    const INPUT: &str = r#"
        vJrwpWtwJgWrhcsFMMfFFhFp
        jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
        PmmdzqPrVvPwwTWBwg
        wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
        ttgJtRGJQctTZtZT
        CrZsJsPPZsGzwwsLwLmpwMDw
    "#;

    #[test]
    fn check_part1() {
        assert_eq!(157, part1(&parse(INPUT)));
    }
}

This code is the basic outline for now, with the current information we have. This may change later (& it does) for the 2nd part.

First we need to parse the input text again, each line represents the content of a single rucksack. Each rucksack has two compartments of same size, therefore we can split the content into tuples of two which represent the compartments.

Let's implement parse first:

fn parse(input: &str) -> Vec<(&str, &str)> {
    input
        .lines()
        .map(str::trim)
        .filter(|&line| !line.is_empty())
        .map(|line| line.split_at(line.len() / 2))
        .collect_vec()
}

As before we str::trim each line and filter all empty ones to make the test variable INPUT work. Each line is split into a tuple of (&str, &str). There are multiple options to represent the parsed rucksack type for example as a New Type.

struct Rucksack(String);

impl Rucksack {
    pub fn compartments(&self) -> (&str, &str) {
        self.0.split_at(self.0.len() / 2)
    }
}

This way some of the logic can be added to the Rucksack type, e.g. to find the duplicate item (char) of both compartments. We stick with the tuple (&str, &str) as a representation.

Let's implement the part1 function.

// Gets the list of all rucksacks, a tuple represents both compartments
fn part1(rucksacks: &[(&str, &str)]) -> u32 {
    rucksacks
        .iter()
        .map(|(left, right)| {
            todo!()
        })
        .map(|v| get_priority(v))
        .sum()
}

The todo!() call is a placeholder to make the compiler happy at this point, the function itself will panic when called. What we would like to do here is to find the duplicate item (char) inside the first map closure. Then map the item to its value by passing it to get_priority to calculate the priority.

As usual there are multiple ways to find the duplicate entry in two &str. The std lib in Rust has the type [HashSet] to calculate the intersection between two collections. Its method intersection is appropriate for this use case.

Note there exist other crates that do something similar and might be even easier to use than the HashSet type, for example the im crate is a good choice.

To make HashSet work for our use case, both &str have to be converted appropriately to HashSet. We know that both compartments have a single item in common, we can ignore the case that a single compartment itself might contain items multiple times. Let's replace the todo! the missing part of the part1 function.

fn get_priority(c: char) -> u32 {
    todo!()
}

fn part1(rucksacks: &[(&str, &str)]) -> u32 {
    rucksacks
        .iter()
        .map(|(left, right)| {
            let left = left.chars().collect::<HashSet<_>>();
            let right = right.chars().collect::<HashSet<_>>();
            left.intersection(&right).next().unwrap().clone()
        })
        .map(get_priority)
        .sum()
}

We also added the function get_priority to complete the part1 block. map accepts a function as closure as well & if the passed in type matches there is no need to declare a closure with ||. Inside the map closure both compartments are converted into HashSets. The method str::chars returns an iterator over char, the type we want to have in the HashSet. The collect method transforms an iterator into a collection.

Let's have a brief look on why collect is quite useful. It takes an iterator & transforms it into a collection.

fn main() {
    let chars = ['a', 'a', 'b', 'c'];
    let vec = chars.iter().collect::<Vec<_>>();
    let hashet = chars.iter().collect::<HashSet<_>>();
    let string = chars.iter().collect::<String>();
}

Given the chars array there are multiple ways to collect them into.

['a', 'a', 'b', 'c'] in Vec
{'a', 'c', 'b'} in HashSet
"aabc" in String

Back to our example. The call left.intersection(&right).next().unwrap().clone() takes the first (& only) duplicate items that appear in both HashSet, ignoring any error handling. The result is cloned here to allow the function get_priority to take a char as parameter.

The missing logic is function get_priority. The range of lower case characters and upper case characters can be represented by 7-bit codes. Ignoring most of the history, it's possible to get the integer values for all lower and upper case alphabets from an ASCII table. Given the character codes it's possible now to map a char to its priority value.

fn get_pririty(c: char) -> u32 {
    match c {
        'a'..='z' => c as u32 - 96,
        'A'..='Z' => c as u32 - 38,
        _ => panic!("Unknown char found"),
    }
}

The get_priority function panics for all unsupported chars, otherwise the ranges are mapped to their priority values. The interesting part here is match statement allow a range of chars for its cases, which is very helpful. It's part of the Pattern Matching logic in Rust, where the given character c is matched against the range of 'a'..='z'.

With all this in place we can now calculate the first solution.

Part 2

The elves come with another issue, for safety elves are divided into groups of three. Every elf carries a badge that identifies their group. Thankfully the input list already resembles this, every set of three lines or chunk (hint, hint) represents a single group. The rucksacks from the first group are:

vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg

Unfortunately the elves don't know which particular item is their badge, the task is to find each group's badge by finding the single item that appears in all rucksacks of a group. In the example above that would be item Z that appears in all rucksacks. The priorities are now calculated as a sum over all found badges, the logic is the same as in part 1.

Instead of dealing with compartments, we have a similar requirement to find the shared item in a group of three rucksacks. This is a good indicator that we can reuse some of the logic. First let's refactor the current code to accomodate both parts.

use std::collections::HashSet;
use itertools::Itertools;

fn parse(input: &str) -> Vec<&str> {
    input
        .lines()
        .map(str::trim)
        .filter(|&line| !line.is_empty())
        .collect_vec()
}

fn get_priority(c: char) -> u32 {
    match c {
        'a'..='z' => c as u32 - 96,
        'A'..='Z' => c as u32 - 38,
        _ => panic!("Unknown char found"),
    }
}

fn part1(rucksacks: &[&str]) -> u32 {
    rucksacks
        .iter()
        .map(|line| line.split_at(line.len() / 2))
        .map(|(left, right)| {
            let left = left.chars().collect::<HashSet<_>>();
            let right = right.chars().collect::<HashSet<_>>();
            left.intersection(&right).next().unwrap().clone()
        })
        .map(get_priority)
        .sum()
}

fn part2(rucksacks: &[&str]) -> u32 {
    todo!()
}

fn main() {
    let input = parse(include_str!("input.txt"));
    println!("Part 1: {}", part1(&input));
    println!("Part 2: {}", part2(&input));
}

#[cfg(test)]
mod tests {
    use crate::*;

    const INPUT: &str = r#"
        vJrwpWtwJgWrhcsFMMfFFhFp
        jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
        PmmdzqPrVvPwwTWBwg
        wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
        ttgJtRGJQctTZtZT
        CrZsJsPPZsGzwwsLwLmpwMDw
    "#;

    #[test]
    fn check_part1() {
        assert_eq!(157, part1(&parse(INPUT)));
    }

    #[test]
    fn check_part2() {
        assert_eq!(70, part2(&parse(INPUT)));
    }
}

This code should compile, but fails the test check_part2. The function parameters changed now, the parse function now returns a Vec<&str> instead of a tuple, which can be passed to the functions part1 and part2. Checking the itertools crate there are two methods that help here, one is chunks. A method by the same name is available on slices in std Rust too, which could have been used as a slice &[..] is given as function argument.

First we should convert each &str into a HashSet, then group them by chunks of three. Then we need to determine for each group what the common item is. In the first part the intersection on HashSet was called, that seems like a good choice to re-use here as well. Again there are multiple ways to implement this logic. One possible option might be to see if fold is a good choice, but it requires to provide an initial accumulator that needs to be filled accordingly to make sense. It could be filled with all possible items, then in each iteration using intersection all items are eliminated that are not shared.

A better choice is to use reduce which works similar to fold but instead of initialising a new type, the first item of the iterator is the initial value for the accumulator. To give an example let's calculate the sum of all entries in an iterator using reduce.

let list = [1, 2, 3, 4];
let x = list.into_iter().reduce(|sum, item| sum + item).expect("Failed to reduce");
// x => 10

Applying this to our use case we can complete the logic of function part2.

fn part2(rucksacks: &[&str]) -> u32 {
    rucksacks
        .iter()
        .map(|&s| s.chars().collect::<HashSet<_>>())
        .chunks(3)
        .into_iter()
        .map(|group| {
            group
                .reduce(|result: HashSet<char>, rhs| result.intersection(&rhs).cloned().collect())
                .unwrap()
                .iter()
                .next()
                .unwrap()
                .clone()
        })
        .map(get_priority)
        .sum()
}

This looks slightly scary, the difference here is the inner map closure over chunks of three HashSets. Instead of using unwrap the expect method could have been used or alternatively collect and propagate errors to the caller. The call group.reduce(|_, _| ...) returns an Option<HashSet<char>>. The remaining iterator calls .ìter().next().unwrap().clone() does the following. The iter call returns an iterator from HashSet<char> over char. As it's expected the HashSet contains exactly one item calling next on it should return Some(char). This is then unwrapped and then cloned to pass the char to get_priority.

Once everything is in place the program now should calculate the 2nd solution.