Day 3: Rucksack Reorganization

[simonw]

https://adventofcode.com/2022/day/3

The list of items for each rucksack is given as characters all on a single line. A given rucksack always has the same number of items in each of its two compartments, so the first half of the characters represent items in the first compartment, while the second half of the characters represent items in the second compartment.

vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg
wMqvLMZHhHMvwLHjbvcjnnSBnvTQFn
ttgJtRGJQctTZtZT
CrZsJsPPZsGzwwsLwLmpwMDw

Need to look for common types - items in both the front and back half.

• Lowercase item types a through z have priorities 1 through 26.
• Uppercase item types A through Z have priorities 27 through 52.

Find the item type that appears in both compartments of each rucksack. What is the sum of the priorities of those item types?

[simonw]

Had a long conversation with ChatGPT about this. I asked:

Given two strings in Rust, identify the character that appears in both strings

The first code example it gave me was;

use std::collections::HashSet;

fn main() {
    let string1 = "hello";
    let string2 = "world";

    // Convert the strings to HashSets
    let set1: HashSet<char> = string1.chars().collect();
    let set2: HashSet<char> = string2.chars().collect();

    // Use the intersection method to find the common characters
    let common_chars: HashSet<char> = set1.intersection(&set2).collect();

    // Print the common characters
    for c in common_chars {
        println!("{}", c);
    }
}

I said:

Can you do this without a HashSet?

fn main() {
    let string1 = "hello";
    let string2 = "world";

    // Create Vecs of characters for each string
    let chars1: Vec<char> = string1.chars().collect();
    let chars2: Vec<char> = string2.chars().collect();

    // Iterate over the elements of one Vec and check if they appear in the other
    for c1 in chars1 {
        if chars2.contains(&c1) {
            println!("{}", c1);
        }
    }
}

Then:

Given two strings in Rust, identify the character that appears in both strings - but without using any other modules

fn main() {
let string1 = "hello";
let string2 = "world";

// Iterate over the elements of one string and check if they appear in the other
for c1 in string1.chars() {
    if string2.contains(c1) {
        println!("{}", c1);
    }
}

}

It added:
> Note that this approach is not as efficient as using a HashSet or a BTreeSet, since it requires iterating over all the elements of one of the strings and checking each element against the other string. This can become slow if the strings are long and have many common characters. In contrast, the intersection method on HashSet or BTreeSet can find the common elements in constant or logarithmic time, without having to iterate over all the elements.

[simonw]

Finally I said:

Turn that into a function I can call

fn find_common_chars(string1: &str, string2: &str) {
    // Iterate over the elements of one string and check if they appear in the other
    for c1 in string1.chars() {
        if string2.contains(c1) {
            println!("{}", c1);
        }
    }
}

fn main() {
    let string1 = "hello";
    let string2 = "world";

    find_common_chars(string1, string2);
}

[simonw]

Got Copilot to write this:

And this with a comment prompt:

        // Split the line exactly in half into two strings
        let (left, right) = line.split_at(line.len() / 2);

[simonw]

But when I ran that code I got a warning:

03 % just
rustc rucksack.rs
warning: `...` range patterns are deprecated
  --> rucksack.rs:33:16
   |
33 |             'a'...'z' => duplicate as u8 - 'a' as u8 + 1,
   |                ^^^ help: use `..=` for an inclusive range
   |
   = note: `#[warn(ellipsis_inclusive_range_patterns)]` on by default
   = warning: this is accepted in the current edition (Rust 2015) but is a hard error in Rust 2021!
   = note: for more information, see <https://doc.rust-lang.org/nightly/edition-guide/rust-2021/warnings-promoted-to-error.html>

warning: `...` range patterns are deprecated
  --> rucksack.rs:34:16
   |
34 |             'A'...'Z' => duplicate as u8 - 'A' as u8 + 27,
   |                ^^^ help: use `..=` for an inclusive range
   |
   = warning: this is accepted in the current edition (Rust 2015) but is a hard error in Rust 2021!
   = note: for more information, see <https://doc.rust-lang.org/nightly/edition-guide/rust-2021/warnings-promoted-to-error.html>

warning: 2 warnings emitted

./rucksack
thread 'main' panicked at 'attempt to add with overflow', rucksack.rs:37:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
error: Recipe `run` failed on line 2 with exit code 101
03 % 

[simonw]

Fed my code and that error to ChatGPT:

fn main() -> io::Result<()> {
    let file = fs::File::open("input.txt")?;
    let reader = io::BufReader::new(file);
    let mut score = 0;

    for line in reader.lines() {
        let line = line?;
        // Split the line exactly in half into two strings
        let (left, right) = line.split_at(line.len() / 2);

        let duplicate = find_duplicate_character(left, right).unwrap();

        /*
        Lowercase item types a through z have priorities 1 through 26.
        Uppercase item types A through Z have priorities 27 through 52.
        */
        let priority = match duplicate {
            'a'...'z' => duplicate as u8 - 'a' as u8 + 1,
            'A'...'Z' => duplicate as u8 - 'A' as u8 + 27,
            _ => 0,
        };
        score += priority;
    }
    println!("{}", score);
    Ok(())
}

03 % just
rustc rucksack.rs
warning: `...` range patterns are deprecated
  --> rucksack.rs:33:16
   |
33 |             'a'...'z' => duplicate as u8 - 'a' as u8 + 1,
   |                ^^^ help: use `..=` for an inclusive range
   |
   = note: `#[warn(ellipsis_inclusive_range_patterns)]` on by default
   = warning: this is accepted in the current edition (Rust 2015) but is a hard error in Rust 2021!
   = note: for more information, see <https://doc.rust-lang.org/nightly/edition-guide/rust-2021/warnings-promoted-to-error.html>

warning: `...` range patterns are deprecated
  --> rucksack.rs:34:16
   |
34 |             'A'...'Z' => duplicate as u8 - 'A' as u8 + 27,
   |                ^^^ help: use `..=` for an inclusive range
   |
   = warning: this is accepted in the current edition (Rust 2015) but is a hard error in Rust 2021!
   = note: for more information, see <https://doc.rust-lang.org/nightly/edition-guide/rust-2021/warnings-promoted-to-error.html>

warning: 2 warnings emitted

./rucksack
thread 'main' panicked at 'attempt to add with overflow', rucksack.rs:37:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
error: Recipe `run` failed on line 2 with exit code 101
03 % 

It replied:

It looks like you're trying to compile and run a Rust program, but you're encountering some errors. The first error is a warning that says that ... range patterns are deprecated, which means that they are no longer recommended to use in new code. Instead, you should use the ..= syntax for inclusive ranges.

Here's how you can fix this error:

let priority = match duplicate {
    'a'..='z' => duplicate as u8 - 'a' as u8 + 1,
    'A'..='Z' => duplicate as u8 - 'A' as u8 + 27,
    _ => 0,
};

The second error is a panic, which is an unrecoverable error that causes the program to crash. In this case, the panic occurs on line 37, which is the line with the score += priority expression. This means that there's an issue with the priority value, which is causing an arithmetic overflow when it's added to the score variable.

To fix this error, you can use the checked_add() method to add priority to score in a way that won't cause an overflow. Here's an example of how you could do this:

score = score.checked_add(priority).unwrap_or(0);

This will add priority to score if it doesn't cause an overflow, and if it does, it will return None instead of panicking. In that case, the unwrap_or() method will return 0 instead of None, which will prevent the panic.

[simonw]

I added a print debug line and saw this:

GGVGlqWFgVfFqqVZGFlblJPMsDbbMrDMpDsJRn: 12
LwzHtwdLHHwDrzPZzzsJbJ: 26
wdLTBvSvHvZVGCjhfN: 22
HsSSnZVHjjssZnJpSJjBHHWgQGcgqqQLQdQFqNgWgqGNDg: 49
rmmRwrtfThtTrbCrGGGcLBDTqDBNQLdL: 46
mwPrrbzPfwvbzhwMMnnjHnBjZlnzMM: 26
gjjdMBgdqdTpJpBcjgRRRlqnvrqfnZtrtZDw: 17
zHShWLhCszCWHVbVzQWCPtQvNZRwtfftfNnrnftlfR: 43
PzPSssHbVhCLFMJFcMFJJMjdJw: 32
thread 'main' panicked at 'attempt to add with overflow', rucksack.rs:38:9

[simonw]

I still don't understand that overflow error. My score is a i32 which should have a max value of 2.1bn (according to a conversation with ChatGPT about it).

[simonw]

Hunch: maybe the problem is the type of the variable that came back from this block of code?

        let priority = match duplicate {
            'a'...'z' => duplicate as u8 - 'a' as u8 + 1,
            'A'...'Z' => duplicate as u8 - 'A' as u8 + 27,
            _ => 0,
        };

Tip from https://fasterthanli.me/series/advent-of-code-2022/part-1 - I'm going to install https://rust-analyzer.github.io/

[simonw]

In VS Code it says:

Maybe because I'm not using Cargo yet?

[simonw]

[simonw]

That advice helped! I closed my VS Code window and opened a new one just on a folder with a single Cargo.toml file and now the extension works.

[simonw]

And that new extension shows me the problem - I have a u8 type here:

[simonw]

Got the right answer for part 1!

https://github.com/simonw/advent-of-code-2022-in-rust/blob/d3acbd41bbc4290ab86899096b0ff4b90d4e917e/03/src/main.rs#L1-L43

[simonw]

I'm switching from Just to cargo run at this point.

[simonw]

New naming convention, because of this:

advent-of-code-2022-in-rust % cargo new 03_part2
error: the name `03_part2` cannot be used as a package name, the name cannot start with a digit
If you need a package name to not match the directory name, consider using --name flag.
If you need a binary with the name "03_part2", use a valid package name, and set the binary name to be different from the package. This can be done by setting the binary filename to `src/bin/03_part2.rs` or change the name in Cargo.toml with:

    [[bin]]
    name = "03_part2"
    path = "src/main.rs"

advent-of-code-2022-in-rust % cargo new day_03_part_2
     Created binary (application) `day_03_part_2` package

So I'm calling things day_03 and day_03_part_2 from now on.

[simonw]

Look at sets of three lines:

vJrwpWtwJgWrhcsFMMfFFhFp
jqHRNqRjqzjGDLGLrsFMfFZSrLrFZsSL
PmmdzqPrVvPwwTWBwg

First find the badges - those are the characters present in all three.

Then calculate "What is the sum of the priorities of those item types?".

[simonw]

Trying this:

[simonw]

Now trying this:

use std::fs;
use std::io;
use std::io::BufRead;

fn find_duplicate_character(s1: &str, s2: &str) -> Option<char> {
    for c1 in s1.chars() {
        for c2 in s2.chars() {
            if c1 == c2 {
                return Some(c1);
            }
        }
    }
    None
}

fn main() -> io::Result<()> {
    let file = fs::File::open("input.txt")?;
    let reader = io::BufReader::new(file);
    let mut score: i32 = 0;

    // Read the file three lines at a time
    let mut lines = reader.lines();
    let mut c1;

    while let Some(Ok(line1)) = lines.next() {
        if let Some(Ok(line2)) = lines.next() {
            if let Some(Ok(line3)) = lines.next() {
                // What character is present in all three lines?
                // Do not use find_duplicate_character() here
                // because it is too slow.
                let mut found = false;
                for c1 in line1.chars() {
                    for c2 in line2.chars() {
                        for c3 in line3.chars() {
                            if c1 == c2 && c2 == c3 {
                                found = true;
                                break;
                            }
                        }
                        if found {
                            break;
                        }
                    }
                    if found {
                        break;
                    }
                }
                if found {
                    let priority = match c1 {
                        'a'..='z' => c1 as u8 - 'a' as u8 + 1,
                        'A'..='Z' => c1 as u8 - 'A' as u8 + 27,
                        _ => 0,
                    } as i32;
                    score += priority;
                } else {
                    // Quit with error
                    panic!("No character found that was in all 3 lines");
                }
            }
        }
    }
    println!("{}", score);
    Ok(())
}

Getting this error:

day_03_part_2 % cargo run
   Compiling day_03_part_2 v0.1.0 (/Users/simon/Dropbox/Development/advent-of-code-2022-in-rust/day_03_part_2)
error[E0381]: use of possibly-uninitialized variable: `c1`
  --> src/main.rs:49:42
   |
49 |                     let priority = match c1 {
   |                                          ^^ use of possibly-uninitialized `c1`

For more information about this error, try `rustc --explain E0381`.
error: could not compile `day_03_part_2` due to previous error

[simonw]

Ran rustc --explain E0381 and got:

It is not allowed to use or capture an uninitialized variable.

Erroneous code example:

fn main() {
    let x: i32;
    let y = x; // error, use of possibly-uninitialized variable
}

To fix this, ensure that any declared variables are initialized before being used. Example:

fn main() {
    let x: i32 = 0;
    let y = x; // ok!

[simonw]

I had to muck around with variable scope a little bit but I got there:

https://github.com/simonw/advent-of-code-2022-in-rust/blob/f37b6b80b78aa53206c5f7a11dfefab337ed3e11/day_03_part_2/src/main.rs#L6-L52

[simonw]

I pasted the first few lines into ChatGPT to ask about that ?:

[simonw]

OK this is cool, ChatGPT suggested an improvement (and I didn't even ask it to):

while let Some(line1) = try!(lines.next()) {
    let line2 = try!(lines.next());
    let line3 = try!(lines.next());

    // Do something with the three lines of input.
}

[simonw]

Tried that and got a warning:

day_03_part_2 % cargo run
   Compiling day_03_part_2 v0.1.0 (/Users/simon/Dropbox/Development/advent-of-code-2022-in-rust/day_03_part_2)
error: use of deprecated `try` macro
  --> src/main.rs:15:29
   |
15 |     while let Some(line1) = try!(lines.next()) {
   |                             ^^^^^^^^^^^^^^^^^^
   |
   = note: in the 2018 edition `try` is a reserved keyword, and the `try!()` macro is deprecated
help: you can use the `?` operator instead
   |
15 -     while let Some(line1) = try!(lines.next()) {
15 +     while let Some(line1) = lines.next()? {
   | 
help: alternatively, you can still access the deprecated `try!()` macro using the "raw identifier" syntax
   |
15 |     while let Some(line1) = r#try!(lines.next()) {
   |                             ++

Pasting that back into ChatGPT.

[simonw]

New error:

day_03_part_2 % cargo run
   Compiling day_03_part_2 v0.1.0 (/Users/simon/Dropbox/Development/advent-of-code-2022-in-rust/day_03_part_2)
error[E0277]: the `?` operator can only be used on `Result`s, not `Option`s, in a function that returns `Result`
  --> src/main.rs:15:41
   |
6  | / fn main() -> io::Result<()> {
7  | |     let file = fs::File::open("input.txt")?;
8  | |     let reader = io::BufReader::new(file);
9  | |     let mut score: i32 = 0;
...  |
15 | |     while let Some(line1) = lines.next()? {
   | |                                         ^ use `.ok_or(...)?` to provide an error compatible with `Result<(), std::io::Error>`
...  |
50 | |     Ok(())
51 | | }
   | |_- this function returns a `Result`
   |
   = help: the trait `FromResidual<Option<Infallible>>` is not implemented for `Result<(), std::io::Error>`
   = help: the following other types implement trait `FromResidual<R>`:
             <Result<T, F> as FromResidual<Result<Infallible, E>>>
             <Result<T, F> as FromResidual<Yeet<E>>>

error[E0308]: mismatched types

Pasted that into ChatGPT, got back a bit of a tangle. Decided to try solving this myself.

[simonw]

Tried this:

    while let line1 = lines.next().unwrap()? {
        let line2 = lines.next().unwrap()?;
        let line3 = lines.next().unwrap()?;

        // What character is present in all three lines?
        let mut found = false;
        for c1 in line1.chars() {
            for c2 in line2.chars() {
                for c3 in line3.chars() {

Warning:

day_03_part_2 % cargo run
   Compiling day_03_part_2 v0.1.0 (/Users/simon/Dropbox/Development/advent-of-code-2022-in-rust/day_03_part_2)
warning: irrefutable `while let` pattern
  --> src/main.rs:15:11
   |
15 |     while let line1 = lines.next().unwrap()? {
   |           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: `#[warn(irrefutable_let_patterns)]` on by default
   = note: this pattern will always match, so the loop will never exit
   = help: consider instead using a `loop { ... }` with a `let` inside it

[simonw]

Solved it like this:

[simonw]

[simonw]

Wow https://fasterthanli.me/series/advent-of-code-2022/part-3 has a VERY different solution to this.

fn main() -> color_eyre::Result<()> {
    let rucksacks = include_str!("input.txt").lines().map(|line| {
        line.bytes()
            .map(Item::try_from)
            .collect::<Result<HashSet<_>, _>>()
    });

    let sum = itertools::process_results(rucksacks, |rs| {
        rs.tuples()
            .map(|(a, b, c)| {
                a.iter()
                    .copied()
                    .find(|i| b.contains(i) && c.contains(i))
                    .map(|i| dbg!(i.score()))
                    .unwrap_or_default()
            })
            .sum::<usize>()
    })?;
    dbg!(sum);

    Ok(())
}

I used Copilot to help me create this list of questions, then pasted the whole lot into ChatGPT:

fn main() -> color_eyre::Result<()> {
    let rucksacks = include_str!("input.txt").lines().map(|line| {
        line.bytes()
            .map(Item::try_from)
            .collect::<Result<HashSet<_>, _>>()
    });
    let sum = itertools::process_results(rucksacks, |rs| {
        rs.tuples()
            .map(|(a, b, c)| {
                a.iter()
                    .copied()
                    .find(|i| b.contains(i) && c.contains(i))
                    .map(|i| dbg!(i.score()))
                    .unwrap_or_default()
            })
            .sum::<usize>()
    })?;
    dbg!(sum);
    Ok(())
}

Questions about this code:
- What does include_tsr! do?
- What does .map(Item::try_from) do?
- What exactly is going on with .collect::<Result<HashSet<_>, _>>()?
- What does itertools::process_results do?
- What does .tuples() do? Why does the next thing take (a, b, c)?
- What does .copied() do?
- What does .unwrap_or_default() do?
- What does .sum::<usize>() do?