Advent of Code 2022, Day 3 -- Rucksack Reorganization

Dec 3rd, 2022

6 min read

Advent Of Code

Rust solutions to Advent of Code 2022, day 3.

I thought that yesterday's Advent of Code had a lot of string manipulation, but day 3 has so much more!

Today's challenge involves splitting the puzzle input into individual lines, then individual characters, then finding duplicate characters in multiple sets of strings.

Full code for Day 3 can be found on Github.

The Day 3 problem can be found at adventofcode.com/2022/day/3

use std::fs;
use std::str::SplitTerminator;
use std::collections::{HashMap, HashSet};

fn main() {
    let contents = fs::read_to_string("input.txt").unwrap();
    let arr = contents.split_terminator("\n");
    let priority_sum = sum_priorities(
        find_dupes(
            rucksack_compartments(arr.clone())
        )
    );
    println!("{:?}", priority_sum);
    let group_sum = sum_priorities(
        find_badge(
            groups(arr.collect::<Vec<&str>>())
        )
    );
    println!("{:?}", group_sum);
}

/*
Divide rucksack into two compartments.
 */
fn rucksack_compartments<'a>(sacks: SplitTerminator<'a, &'a str>) -> Vec<(&'a str, &'a str)> {
    sacks.map(|sack| {
        let half = sack.len() / 2;
        return (&sack[..half], &sack[half..]);
    }).collect::<Vec<(&str, &str)>>()
}

/*
Find the duplicate item in the two compartments.
Creates a hash set from the first compartment
and checks the items in the second compartment against the set.
 */
fn find_dupes(sacks: Vec<(&str, &str)>) -> Vec<char> {
    sacks.iter().map(|sack| {
        let mut set = HashSet::new();
        let first_compartment = sack.0.chars();
        for item in first_compartment {
            set.insert(item);
        }
        let second_compartment = sack.1.chars();
        for item in second_compartment {
            if set.contains(&item) {
                return item;
            }
        }
        return ' ';
    }).collect::<Vec<char>>()
}

/*
Find the sum of the item priorities.
 */
fn sum_priorities(dupes: Vec<char>) -> usize {
    let values: [char; 52] = ['a', 'b', 'c', 'd', 'e', 'f', 'g',
    'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
    't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E',
    'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q',
    'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];

    dupes.iter().map(|item| {
        return values
            .iter()
            .position(|val| val == item)
            .unwrap() + 1;
    }).sum()
}

/*
Partition the list into groups of three.
 */
fn groups(sacks: Vec<&str>) -> Vec<Vec<&str>> {
    sacks.chunks(3).map(|chunk| {
        return chunk.to_vec();
    }).collect::<Vec<Vec<&str>>>()
}

/*
Find the badge common to the group.
Creates a hashmap, removes duplicates,
and checks for the only character that appears thrice.
 */
fn find_badge(groups: Vec<Vec<&str>>) -> Vec<char> {
    groups.iter().map(|group| {
        let mut badge_map: HashMap<char, i32> = HashMap::new();
        for items in group {
            let mut dedup = items.chars().collect::<Vec<char>>();
            dedup.sort();
            dedup.dedup();
            for item in dedup {
                *badge_map.entry(item).or_insert(0) += 1;
            }
        }
        let common_char = badge_map.iter().find_map(|(key, &val)| {
            if val == 3 {
                Some(key)
            } else {
                None
            }
        });
        return *common_char.unwrap();
    }).collect::<Vec<char>>()
}

Part 1

In part 1, we need to split each line into two equal halves, then find the only character in each half that is duplicated. I already have the puzzle input split by newlines, with .split_terminator(), and I pass that into a function that will return a tuple containing each half of the original string.

fn rucksack_compartments<'a>(sacks: SplitTerminator<'a, &'a str>) -> Vec<(&'a str, &'a str)> {
    sacks.map(|sack| {
        let half = sack.len() / 2;
        return (&sack[..half], &sack[half..]);
    }).collect::<Vec<(&str, &str)>>()
}

You'll notice the use of 'a in the function definition. Running the function without 'a causes this error message:

error[E0106]: missing lifetime specifiers
  --> src/main.rs:25:64
   |
25 | fn rucksack_compartments(sacks: SplitTerminator<&str>) -> Vec<(&str, &str)> {
   |                                 ---------------------          ^     ^ expected named lifetime parameter
   |                                                                |
   |                                                                expected named lifetime parameter
   |
   = help: this function's return type contains a borrowed value, but the signature does not say which one of `sacks`'s 2 lifetimes it is borrowed from
help: consider introducing a named lifetime parameter
   |
25 | fn rucksack_compartments<'a>(sacks: SplitTerminator<'a, &'a str>) -> Vec<(&'a str, &'a str)> {
   |                         ++++                        +++  ++                ++       ++

After reading up on lifetime parameters, it seems that the problem is that splitting the &str in the "sacks" parameter into a tuple confuses the borrow checker. If I understand it correctly, this annotation tells the borrow checker that both &str in the returned tuple will come from the "sacks" parameter.

Luckily, Rust's error handling very nicely tells you exactly what to do to fix this problem.

After splitting the string into a tuple of two strings, I needed to come up with a way to find the character that appears in both strings. I decided to use a HashSet to store each character without duplicates from the first string, and then iterate over the characters in the second string, checking to see if the set contains the character.

fn find_dupes(sacks: Vec<(&str, &str)>) -> Vec<char> {
    sacks.iter().map(|sack| {
        let mut set = HashSet::new();
        let first_compartment = sack.0.chars();
        for item in first_compartment {
            set.insert(item);
        }
        let second_compartment = sack.1.chars();
        for item in second_compartment {
            if set.contains(&item) {
                return item;
            }
        }
        return ' ';
    }).collect::<Vec<char>>()
}

Finally, once I have a vector of chars, I can calculate the value of each character, and sum them.

fn sum_priorities(dupes: Vec<char>) -> usize {
    let values: [char; 52] = ['a', 'b', 'c', 'd', 'e', 'f', 'g',
    'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
    't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E',
    'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q',
    'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];

    dupes.iter().map(|item| {
        return values
            .iter()
            .position(|val| val == item)
            .unwrap() + 1;
    }).sum()
}

Originally I had thought to use the decimal values of the characters to calculate the priority value, but it would've involved identifying if the character was uppercase or lowercase, and then subtracting an amount. I felt like that would be too convoluted. I also didn't want to type out a HashMap with characters and values. So, I decided to create an array of characters, find the index of the character in the array, and add 1.

Part 2

For part 2, the puzzle input needs to be grouped into three lines each. I initially tried to iterate over the vector, adding each line to a second vector, and when the index % 3 == 0, push the vector of three lines to another vector, creating a two-dimensional vector. Then, I learned about .chunks().

fn groups(sacks: Vec<&str>) -> Vec<Vec<&str>> {
    sacks.chunks(3).map(|chunk| {
        return chunk.to_vec();
    }).collect::<Vec<Vec<&str>>>()
}

With chunks, the vector will be sliced into chunks of a specified size. Then, I was able to convert the chunk to a vector, and collect into a two-dimensional vector. So much less verbose than my original plan!

Finding the "badge" (character), that was common to all three strings in a group was the most difficult part of this challenge. I decided to make a HashMap to count the occurances of characters in each string, but I also had to make sure that each string only contained unique characters. So, I learned about .dedup().

Now, .dedup() only works on "consecutive repeated elements in the vector", so I needed to sort the vector of characters first. Luckily, the order of the characters makes no difference in this case. After creating the vector of chars, sorting, and deduping I could add the character and update its count in the HashMap.

fn find_badge(groups: Vec<Vec<&str>>) -> Vec<char> {
    groups.iter().map(|group| {
        let mut badge_map: HashMap<char, i32> = HashMap::new();
        for items in group {
            let mut dedup = items.chars().collect::<Vec<char>>();
            dedup.sort();
            dedup.dedup();
            for item in dedup {
                *badge_map.entry(item).or_insert(0) += 1;
            }
        }
        let common_char = badge_map.iter().find_map(|(key, &val)| {
            if val == 3 {
                Some(key)
            } else {
                None
            }
        });
        return *common_char.unwrap();
    }).collect::<Vec<char>>()
}

Once I've iterated over all the strings, I can use .find_map() to iterate over the HashMap and find the key that has a value of 3. If there was more than one it would only return the first key, but there should only be one common character between the three strings.

Finally, to find the values and sum the priorities of the returned characters, the sum_priorities function can be reused without any changes.

What I learned

Lifetime parameters - Helps the borrow checker understand the lifetimes of references.
HashSet - Creates a set of unique values.
.chunks() - Slices a vector into pieces of a specified size.
.dedup() - Removes duplicate consecutive values. Will reliably remove all duplicates only if the vector is sorted.
.find_map() - Maps through the iterator until finding a value that evaluates to true, and returns that value, otherwise returns None.

mary.codes