Cracking Challenges: Strategies for Advent of Code 2022 and Hackerrank

Cracking Challenges: Strategies for Advent of Code 2022 and Hackerrank

Discover the prowess of Rust as we dive into challenges. Uncover the magic of Rust's regex engine for time conversion and master matrix calculations

Play this article

Prologue

Embarking on the #100DaysOfCodeChallenge has been an incredible experience so far. Every day brings new learning opportunities, and I'm thrilled to share my journey with you. Today, I'll be diving into days 2-17 of my challenge, where I tackled the Advent of Code 2022 day 2 puzzle and ventured into the world of hackerrank. I will break the post into two parts, so jump to whatever section interests you:-

  1. Advent of Code 2022 Day 02

  2. Hackerranks

Hope you enjoy the read, let's gooooo.


AoC 2022: 02

You can find the advent puzzle here:-

The puzzle for day 02

The summary is very simple. You have a list of tuples--each with 2 elements-- to indicate what an opponent would take for Rock-Paper-Scissors(RPS) and the other, yup we don't what the other thing is in the first half. So we assume it is what we should take. Now, the task is to find the sum of scores if nothing goes south.

the core algorithm

So, first, we see that we need scores for each Y and the outcome encoded into our program. Thank god, rust's Enums are powerful. For more information, please have a look at this video.

From the task, we can get the score details for the play:

enum Points {
    Rock = 1,
    Paper = 2,
    Scissors = 3,
}

Now, for each tuple, we could...

Points::Paper + outcome_value

but wait, rustc is not happy, it seems like, it couldn't figure out how to add i32 with Points. But rustc being rustc, the error message just tells us what to do.

impl std::ops::Add<i32> for Points {
    type Output = i32;

    fn add(self, other: i32) -> i32 {
        self as i32 + other
    }
}

We could encode the outcome_value, but since I am just learning the rust, I decided not to as this would overcomplicate the codebase. That would be too much because I encoded other magic values into the Rust's type system.

// this is to see what the first column of the tuple is,
// i.e. what the opponent will take.
enum Opponent {
    Rock,
    Paper,
    Scissors,
}

// this is same as Opponent above, but for me, the second column.
enum Me {
    Rock,
    Paper,
    Scissors,
}

Note that I could have done this with a single enum Play but the duo of columns contain different presentations for the values, so encoding would be harder.

Let's also create 2 helper functions to convert our input A|Y into our internal representation Opponent::Rock|Me::Paper.

fn parse_opp(h: &str) -> Option<Opponent> {
    match h {
        "A" => Some(Opponent::Rock),
        "B" => Some(Opponent::Paper),
        "C" => Some(Opponent::Scissors),
        _ => None,
    }
}

fn parse_me(h: &str) -> Option<Me> {
    match h {
        "X" => Some(Me::Rock),
        "Y" => Some(Me::Paper),
        "Z" => Some(Me::Scissors),
        _ => None,
    }
}

I decided to return an Option<Opponent|Me> as the input contains a blank line at the EOF. I discovered a solution lately to eliminate a bunch of boilerplate from the codebase, so stick around till the end.

Now all we have to do is to

  • iterate over the tuples,

  • determine the scores,

  • sum up,

  • then, finally sum up the whole rounds.

let sum = vec_with_each_line.iter()
    .map(|l| {
    let split: Vec<&str> = l.split(" ").collect();
    if split.len() > 1 {
      match parse_opp(split[0]) {
           Some(Opponent::Rock) => match parse_me(split[1]) {
           Some(Me::Rock) => Points::Rock + 3,
           Some(Me::Paper) => Points::Paper + 6,
           Some(Me::Scissors) => Points::Scissors + 0,
           _ => 0,
        }
        // --snip-- for brevity
        }
    }else {
        // because of that EOF line.
        0
    }
    }).sum::<i32>();

The essence is match parse_opp(split[0]) and the parse_me(). Then as trivial, I check what I have and then return the appropriate score. The tricky part is to think when we win or lose and it is a draw. Wrap your brain around and patiently figure it out.

Keep in mind, that we cannot just consider what the Opponent would take, as winning every round might raise suspicion!

Well in the next half, it turns out the second column is how that round should end. This may sound like we need to rewrite the program, but we only have to change the match statements.

Since this is just like the above, here is the code. Have a look at it.

    let second_sum: i32 = rounds
        .iter()
        .map(|s| {
            let split: Vec<&str> = s.split(" ").collect();
            if split.len() > 1 {
                match parse_opp(split[0]) {
                    Some(Opponent::Rock) => match parse_outcome(split[1]) {
                        Some(Outcome::Lose) => Points::Scissors + 0,
                        Some(Outcome::Draw) => Points::Rock + 3,
                        Some(Outcome::Win) => Points::Paper + 6,
                        _ => 0,
                    },
                    Some(Opponent::Paper) => match parse_outcome(split[1]) {
                        Some(Outcome::Lose) => Points::Rock + 0,
                        Some(Outcome::Draw) => Points::Paper + 3,
                        Some(Outcome::Win) => Points::Scissors + 6,
                        _ => 0,
                    },
                    Some(Opponent::Scissors) => match parse_outcome(split[1]) {
                        Some(Outcome::Lose) => Points::Paper + 0,
                        Some(Outcome::Draw) => Points::Scissors + 3,
                        Some(Outcome::Win) => Points::Rock + 6,
                        _ => 0,
                    },
                    _ => 0,
                }
            } else {
                0
            }
        })
        .sum();

That's it for AoC 2022 Day 02. See you with another one.


Hackerrank

Meanwhile, I also checked out the hackerrank warmup challenges. For a beginner, I recommend these. These challenges helped me figure out a much in the rust std library. Here are some challenges, I think are worth going for.

Diagonal Difference

Please check this link for the challenge. The task is to find the absolute difference of sums of diagonals of a square matrix. With a little bit of math background, we can achieve this as...

let n = arr.len();
let (x,y) = (0..n)
             .fold((0,0), |(x,y), i| {
                  (x + arr[i][i], y + arr[i][n-1-i])
             });
(x-y).abs() // the answer

The trick up the sleeve is, arr[i][i] gives the ith primary diagonal value in a square matrix. And the arr[i][n-(i+1)] gives the ith secondary diagonal value of a square matrix.

The code above achieves this algorithm by-

  1. creating a range from 0 to array length, n : (0..n) (note that this is exclusive of n)

  2. using the fold iterator. Starting from (0,0) each representing each sum of diagonals.

  3. Then after, indexing the correct value in the 2D array (the square matrix), closure given to fold updates the folding values using (x + arr[i][i], y + arr[i][n-1-i]), here x is the sum of the primary and y is the sum of secondary diagonals.

  4. When all is done, returned value due to folding is then extracted as x and y using pattern matching.

  5. Finally, the absolute value is calculated using, (x-y).abs().

Even though there are many challenges in the warmup sequence, I decided to write about this one, because it took me a great deal of time to properly get the sums of the diagonals. I then asked ChatGPT to give me a solution. After a few trials of asking it to reduce the loops, we both arrived at this handy-dainty trick.

I don't know where ChatGPT trained this technique, but a salute to whoever posted it online first.

Time Conversion

This one also stays in my heart, as this was my first encounter of the regex in Rust. I could have only used the String methods, but I decided to give regex a go because Rust is known for its state-of-art SIMD regular expression engine.

According to the challenge statement, I decided this...

Regex::new(
    r"(\d{2}):(\d{2}):(\d{2})([AP])"
).unwrap();

...expression would capture what I need. If you want to know more about regex or are a beginner to it, please check out my comprehensive regex post.

One can easily spot out, I used capture groups. Since of this, I can easily reuse the input string and also determine what to do. Apart from the expression and the captured groups indexing; nothing special going on. All else is trivial clock logic we learned in primary schools.

fn timeConversion(s: &str) -> String {
    let r = Regex::new(
        r"(\d{2}):(\d{2}):(\d{2})([AP])M"
    ).unwrap();
    let c = r.captures_iter(s).next().unwrap();

    match &c[4] {
        "A" => match &c[1] {
            "12" => format!("{}:{}:{}", "00", &c[2], &c[3]),
            _ => format!("{}:{}:{}", &c[1], &c[2], &c[3])
        },
        "P" => match &c[1] {
            "12" => format!("{}:{}:{}", &c[1], &c[2], &c[3]),
            _ => format!("{}:{}:{}", (12 + atoi(&c[1])), &c[2], &c[3])
        },
        _ => panic!("invalid string passed in")
    }
}

That's all I have got. See you in another one.


Wrap up

Hope you enjoyed the time being. Catch you up on the next report. Wish it wouldn't be much later as after 17 days next time. Till then this is meTheBE signing off, bye.