The Ideal Stocking Stuffer

AoC 2015 with Rust - Day 4

Jul 29 23 • 5 min read

Link to problem

Source of the final solution

Other posts in the series

Part 1

Santa is mining coins. He is trying to find MD5 hashes that start with 5 zeroes. An input of a secret key followed by a number that produces such a hash is valid, and Santa needs to find the lowest possible number of such hashes.

For example,

• If your secret key is abcdef, the answer is 609043, because the MD5 hash of abcdef609043 starts with five zeroes (000001dbbfa...), and it is the lowest such number to do so.
• If your secret key is pqrstuv, the lowest number it combines with to make an MD5 hash starting with five zeroes is 1048970; that is, the MD5 hash of pqrstuv1048970 looks like 000006136ef....

The idea is to make a loop with a counter starting from 0, add the value of this counter to the secret key (input), and hash the concatenated string. If the hash starts with five zeroes, break the loop and check the counter to get the result.

I don’t want to implement MD5 myself, so I added a crate by running cargo add md5.

[dependencies]
md5 = "0.7.0"

I put together something like this as the solution for the part 1 but it kept running for so long.

use md5;

fn main() {
    let base_input = "iwrupvqb";
    let mut counter = 0;

    let result = loop {
        let hash = md5::compute(format!("{}{}", base_input, counter));

        if hash.starts_with(b"00000") {
            break counter;
        }

        counter = counter + 1;
    };

    println!("{:?}", result);
}

Given that AoC about page has the following statement, I know that I am not on the right track.

You don’t need a computer science background to participate - just a little programming knowledge and some problem solving skills will get you pretty far. Nor do you need a fancy computer; every problem has a solution that completes in at most 15 seconds on ten-year-old hardware.

I was expecting this to be a lot faster because when I printed out the counter on each iteration, I could see that it was going through numbers really fast.

I went about debugging the code by printing hash and b"00000", and could see that the two was not producing exactly the same data. Since the break condition never met, the loop went on running forever.

Instead, I decided to format the hash as a string, which produced a healthier comparison.

use md5;

fn main() {
    let base_input = "iwrupvqb";
    let mut counter = 0;

    let result = loop {
        let hash = md5::compute(format!("{}{}", base_input, counter));

        if format!("{:?}", hash).starts_with("00000") {
            break counter;
        }

        counter = counter + 1;
    };

    println!("{:?}", result);
}

And this worked a lot quicker and the first part of the puzzle is done.

Part 2

For part two, we need to do the same thing but with six zeroes. Simply changing .starts_with("00000") part with .starts_with("000000") with works, although a bit slower. But, we can do a minor improvement and use some sort of repeating pattern to change the number of zeroes, and put the logic in some sort of function.

use md5;

fn produce_hash(base_input: &str, target_prefix: String) -> i32 {
    let mut counter = 0;

    return loop {
        let hash = md5::compute(format!("{}{}", base_input, counter));

        if format!("{:?}", hash).starts_with(&target_prefix) {
            break counter;
        }

        counter = counter + 1;
    };
}

fn main() {
    let base_input = "iwrupvqb";

    println!("{:?}", produce_hash(base_input, "0".repeat(5)));
    println!("{:?}", produce_hash(base_input, "0".repeat(6)));
}