Malerwerkst.at

Rust - Advent of Code 2015 - Tag 4 / Teil 1+2

Introduction

R.


Rust AoC-2015

Rust - Advent of Code 2015 - Tag 4 / Teil 1+2

Posted by R. on .
Featured

Rust AoC-2015

Rust - Advent of Code 2015 - Tag 4 / Teil 1+2

Posted by R. on .

Heute fangen wir mal direkt mit der Aufgabenstellung an.

Aufgabenstellung

Santa needs help mining some AdventCoins (very similar to bitcoins) to use as gifts for all the economically forward-thinking little girls and boys.

To do this, he needs to find MD5 hashes which, in hexadecimal, start with at least five zeroes. The input to the MD5 hash is some secret key (your puzzle input, given below) followed by a number in decimal. To mine AdventCoins, you must find Santa the lowest positive number (no leading zeroes: 1, 2, 3, ...) that produces such a hash.

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....

Zusammengefasst sollen wir also einen vorgegebenen Inputstring solange um eine Ziffernfolge erweitern, bis der daraus errechnete MD5-Hash mit fünf Nullen (00000...) beginnt. An sich eine weitere (simple) Brute-Force Aufgabe.

Zu deren Lösung muss man aber erstmal schauen, wie MD5-Hashes in Rust berechnet werden können. Anders als beispielsweise Python oder Ruby, die die entsprechenden Funktionalitäten von Haus aus (in ihren Standardbibliotheken) mitbringen, muss man sich bei Rust externer Bibliotheken bzw. Module bedienen.

Erste Anlaufstelle hierfür sind Crates.io - das Package Repository - und Cargo, der Rust eigene Packagemanager, der sowieso bereits installiert sein sollte. Wenn nicht, wird es spätestens jetzt Zeit, dies nachzuholen (und den Cargo-Guide durchzugehen)!

Hat man das erledigt, kann man sich auf die Suche nach dem passenden Modul für die Berechnung von MD5-Hashes begeben. Im folgenden Lösungsbeispiel habe ich mich für das "rust-crypto"-crate entschieden.

Im Sourcecode wird die Funktionalität des rust-crypto-crates mittels

extern crate crypto;  
use crypto::digest::Digest;  
use crypto::md5::Md5;  

eingebunden.

Damit Cargo, unser Packagemanager, aber auch weiß, dass wir ein externes Modul benötigen, müssen wir ihm diese "Abhängigkeit" in der Projekt-Konfigurationsdatei Cargo.toml im Abschnitt "Dependencies" mitteilen:

[dependencies]
rust-crypto = "0.2.36"  

Um den Rest (Herunterladen und Kompilieren der benötigten Pakete) kümmert sich Cargo dann beim nächsten Build-Aufruf selbstständig.

Nun aber genug der ganzen Vorrede. Wird Zeit, dass wir zum eigentlichen Code-Beispiel kommen:

Code

extern crate crypto;

use crypto::digest::Digest;  
use crypto::md5::Md5;

fn main() {  
    let input="yzbqklnj";
    let mut skip=false;
    let mut hash = Md5::new();

    for i in 1.. {
        let test=format!("{}{}",input,i);
        hash.reset();
        hash.input_str(&test);

        if !skip {
            if hash.result_str().starts_with("00000") {
                println!("Part 1: {} ---> {}",i,hash.result_str());
                skip=true;
            } else {
                continue;
            }
        }
        if hash.result_str().starts_with("000000") {
            println!("Part 2: {} ---> {}",i,hash.result_str());
            break;
        }
    }
}

R.

View Comments...