Day 1 of 100: AoC 1

My first day of 100. 99 to go.

Day 1 of 100: AoC 1
Play this article

TL;DR

Today I learned a few from the first-day challenge of Advent of Code 2022. Summary:

  • File I/O in Rust

  • String Manipulation

  • Parsing a.k.a. Explicit Casting

  • Some Iterators.

The Challenge

Canonical URL: Challenge Day 1

There are 2 challenges, the latter builds up on the previous. Though, the challenge might throw you here & there, the brief is

  1. Find the max of the sum of calories carried by each elf.

  2. Find the sum of the first 3 max calories


1) The Max of Sum

The input seems to be in the format:

1000
2000
3000

4000

5000
6000

7000
8000
9000

10000

The Max is of sum, we need the sum first. So the input reduces to...

Now, just get the max: 24000 . Hope you got it. So the plan is to...

  1. Get the sum from the input

  2. Find the max.


Parsing The Input

However, the input is not in the way we needed. AoC2022 provides the input in the input.txt file, and it's up to us how we proceed. First, let's just get the file in the disk to the memory, so we can work with it.

Few Google searches, we arrive at the official documentation. The core concept of Rust File IO is this.

use std::io::prelude::*;
use std::fs::File;

// --snippet--
let filename = "filename.ext";
let mut buf = String::new();
let file = File::open(filename);
file.read_to_string(&mut buf);
// now buff has contents of `filename.ext`

But the documentation suggests that we use a BufReader to handle the reading efficiently. So, why not?

use std::io::prelude::*;
use std::fs::File;
use std::io::BufReader;

// --snippet--
let filename = "input.txt";
let mut content = String::new();
let file = File::open(filename).unwrap();

// a proxy-like buffer and read from it
let mut buffer = BufReader::new(file);
buffer.read_to_string(&mut content).unwrap();

For further, please read the official documentation.

We don't have to manually close the file, the descriptor is automatically dropped when the variable is out of scope. Thanks, Rust ownership model.

What do we have? What do we want?

We have...

1000\n2000\n3000\n\n4000\n5000\n6000\n...

We want...

max([1000+2000+3000, 4000+5000+6000,...])

One clear thing is we need to parse String to u32 (because calories are always positive). And the group seems to be delimited by \n\n in the input text. So, let's try to split the monogamous input string to \n\n delimited Vec<String>. This is quite easy in Rust, as Rust's String is encoding-ware.

Spliting the String is as breeze as...

let sub_arr: Vec<&str> = content.split("\n\n").collect();

We need to annotate sub_arr with : Vec<&str> so that .collect() can infer the type, or you will get an error. You can omit the annotation and provide it in the turbo-fish format as .collect::<Vec<&str>>().

Note: If you print the value of sub_arr to the stdout we can see that the last element is an empty string. This has to do with the way .split(pattern) works. Refer to this documentation for further peculiar behaviors!

-- from this
1000\n2000\n3000\n\n4000\n5000\n6000\n...
-- to this
["1000\n2000\n3000", "4000\n5000\n6000", ...]

Now let's find the sum. We can do this the imperative way, but I love the functional approach whenever I can. So, let's do this...

let max = match sub_arr
        .iter()
        .map(|s| {
            s.split("\n")
                .map(|c| match c.parse::<u32>() {
                    Ok(i) => i,
                    Err(_)=> 0
                })
            .sum::<u32>()
        })
        .max() {
    Some(m) => m,
    None => 0
};

Quite a lot of daisy chains, eh? Let me break it up for you.

  1. First, let's iterate over the sub_arr and split each element by \n.

     sub_arr.iter()
             .map(|s| {
                 // before: 1000\n2000\n3000
                 s.split("\n")
                 // after: ["1000", "2000", "3000"] (quite like)
              })
    
  2. Once split, let's parse each value. Since .split() returns Iterator, we can .map() again. Parsing in Rust is rather simple, just obj.parse::<targetType>(). For further clarification, refer to this.

     // before: ["1000", "2000", "3000"] (quite like)
     s.split("\n")
      .map(|c| match c.parse::<u32>() {
           Ok(i) => i,
     // this is to prevent error due to last empty string
           Err(_)=> 0 
      })
     // after: [1000,2000,3000] (quite like)
     // note, the elements are no longer strings.
    

    The essence of this step is c.parse::<u32>(). The rest are generic stuff.

  1. Once parsed, we need to sum them up, this is fairly easy as Iterator implements .sum() utility. But since this is deeply nested we might have to specify what the return value should be. Thus specify it by the turbo-fish syntax

     // --snip--
     ...
     .sum::<u32>()
    

    I am using u32 instead of i32 because calories are always positive and I trust the input.txt. Don't do this in prod. Always sanitize your input, first.

  2. Now that we got the sums of how much each one is carrying, we can utilize the .max() of Iterator trait. .max() returns Option ( Some(_) usually, None if iter is empty). Refer to this document for more.

     match sub_arr.iter()
             .map(|s| {})
             .max() {
         Some(m) => m, // the maximum
         None => 0 // to exhaust the arms, not neccesary logically.
     }
    
  3. The return of the expression is the answer for the first part. So, the complete script(binary crate) would be

     fn main() -> std::io::Result<()> {
         let file = File::open("input.txt")?;
         let mut buf = BufReader::new(file);
         let mut content = String::new();
    
         buf.read_to_string(&mut content)?;
         let sub_arr: Vec<&str> = content.split("\n\n").collect();
    
         let max = match sub_arr
             .iter()
             .map(|s| {
                 s.split("\n")
                     .map(|c| match c.parse::<u32>() {
                         Ok(i) => i,
                         Err(_)=> 0
                     })
                 .sum::<u32>()
             })
             .max() {
             Some(m) => m,
             None => 0
     };
         println!("the max is {}", max);
         Ok(())
     }
    

2) The Sum of 3 Maxs

Instead of finding the max, the abstraction is the task extends by finding the sum of the first 3 maximums. We could however do this like before, but with a little bit of refactoring, we can reduce some boilerplates.

Instead of getting the max right away, we can store the intermediate Vec of sums of each carriage. So the let max = match sub_arr... becomes like this:-

// annotation is neccessary!
let arr: Vec<u32> = sub_arr
        .iter()
        .map(|s| {
            s.split("\n")
                .map(|c| match c.parse::<u32>() {
                    Ok(i) => i,
                    Err(_)=> 0
                })
            .sum::<u32>()
        })
    // instead of .max() let's create a Vec<u32>
    .collect();
// getting the max
let max = match arr.iter().max() {
    Some(m) => m ,
    None => &0 // because .iter() creates a ref than a clone
};

Back to the point.

We need the first 3 maxs. So, we need to sort the Vec<u32>. We can use the .sort() of Vec. But, there is a better performant but unstable which can sort in O(n * log(n)). This also mutates the Vec. So we have to change the let arr = ... to let mut arr. And then, it is as...

arr.sort_unstable()

Now the first 3 maxs are of the last (pun indented) 3 elements, as the .sort_unstable() sorts in ascending order. They can be retrieved as arr[arr.len()-3..]. So the needed sum would be then appended .iter().sum(). The final expression might look like

arr.sort_unstable();
let sum_max = arr[(arr.len() - 3)..].iter().sum::<u32>();
println!("sum of 3 maxs is {}", sum_max);

EOF for Day 1

That's it for today. I learned a lot today about Rust's built-in utilities and the patience to read the official docs. I can't wait to experience what the upcoming 99 days hold. See you tomorrow.


This is meTheBE signing off, Sayanora.