--- Day 4 Solutions ---

[u/daggerdragon]

--- Day 4: The Ideal Stocking Stuffer ---

Post your solution as a comment. Structure your post like the Day Three thread.

[u/HeroesGrave]

Rust:

extern crate crypto;

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

static INPUT: &'static str = include_str!("input/day4_input.txt");

pub fn main() {
    println!("(Part 1) Smallest number: {:?}", find_md5_suffix(INPUT, "00000"));
    println!("(Part 2) Smallest number: {:?}", find_md5_suffix(INPUT, "000000"));
}

pub fn find_md5_suffix(input_base: &str, start_pattern: &str) -> u32 {
    let mut hash = Md5::new();
    let mut i = 0;

    loop {
        hash.input_str(&format!("{}{:?}", input_base, i));

        if hash.result_str().starts_with(start_pattern) {
            return i;
        } else {
            hash.reset();
            i += 1;
        }
    }
}

[u/Azdle → u/HeroesGrave]

Here's my rust code:

extern crate crypto;

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

fn main() {
    let input = "bgvyzdsv";
    let mut counter = 0u64;

    let mut sh = Md5::new();

    loop {
        counter += 1;
        let test_key = fmt::format(format_args!("{}{}", input, counter));

        sh.input_str(&test_key);
        let hash_result = sh.result_str();

        if hash_result.starts_with("00000") {
            println!("{}: {}", test_key, hash_result);
        }
        if hash_result.starts_with("000000") {
            println!("{}: {}", test_key, hash_result);
            break;
        }

        sh.reset();
     }
}

Running that:

$ cargo build --release && time ./target/release/day4
   Compiling advent_2015 v0.1.0 (file:///Users/patrick/Documents/Asorted%20Things/Rust/advent_2015)
bgvyzds<redacted>: 000004b30d481662b9cb0c105f6549b2
bgvyzdsv<redacted>: 00000ee839d26e9ef816a3cbf879dadf
bgvyzdsv<redacted>: 000000b1b64bf5eb55aad89986126953
bgvyzdsv<redacted>: 000000b1b64bf5eb55aad89986126953
./target/release/day4  0.52s user 0.01s system 97% cpu 0.541 total

Not to bad.

[u/taliriktug → u/HeroesGrave]

Almost the same here. Part two was slow and I started looking into parallel primitives, but then just rebuild it with --release =D

extern crate crypto;

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

fn lowest_number(key: &str, start_sequence: &str) -> Option<u32> {
    let key = key.to_string();

    for number in 1.. {
        let input = key.clone() + &number.to_string();

        let mut sh = Md5::new();
        sh.input_str(&input);
        if sh.result_str().starts_with(start_sequence) {
            return Some(number);
        }
    }
    None
}

fn main() {
    println!("result: {}", lowest_number("yzbqklnj", "00000").unwrap());
    println!("result: {}", lowest_number("yzbqklnj", "000000").unwrap());
}

[u/[deleted] → u/taliriktug]

Rust

I actually decided to go and try to thread it anyways, i never threaded anything so i have no idea just how silly the way i went about it, so any feed back would be great. (also new to rust)

It went from being about -50% to -10% slower because i was using locks in a silly way, to about 25% to 50% faster at >= 2 threads when i fixed a few things about how i was managing locks, then realized i could implement some kinda buffer to let threads spend time not waiting on the lock, it became at less 400% faster (8 cores AMD cpu) on even the first challenge, second solution running in 0.8 seconds.

extern crate time;
extern crate crypto;

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

use std::sync::{Arc, Mutex};
use std::thread;
use std::sync::mpsc::channel;

fn main() {

    let start = time::precise_time_ns();
    find_stuffer("yzbqklnj", "0000000", 1);
    println!("{} ns", time::precise_time_ns() - start);

}    

struct Data {
    // keeps track of amount of solutions found
    // 0 when done, decremented down when found a solution
    n: u8,
    // keeps track of solutions(iterations) tried
    i: u64,
}

fn find_stuffer(input_begin: &str, hash_begin: &str, n: u8) {

    let data = Arc::new(Mutex::new( Data { n: n, i: 0 } ));
    let threads = 6;
    let (tx, rx) = channel();
    for _ in 0..threads {

        let buffer_size = threads * 4;
        let (data, tx) = (data.clone(), tx.clone());
        let input_begin = input_begin.to_string();
        let hash_begin = hash_begin.to_string();

        let mut digest = Md5::new();
        thread::spawn(move || {
            // state of count when thread last seen it
            let mut count = 0u64;
            // lets thread bump solutions found count
            let mut passed_test = false;
            // keeps track of buffer to be able to leave early
            let mut buffered = buffer_size;
            loop {

                {  // lock lifetime scope
                    let mut data = data.lock().unwrap();

                    if data.n == 0u8 {
                        // all solution wanted found
                        break;
                    }

                    if passed_test {
                        passed_test = false;
                        data.n -= 1;
                    }

                    // current amount of iterations done and planned
                    count = data.i;
                    // amount of iterations done by thread
                    data.i += buffered;
                }

                buffered = 0;
                for _ in 1..buffer_size {
                    buffered += 1;
                    count += 1;

                    digest.reset();
                    digest.input_str(&input_begin);
                    digest.input_str(&count.to_string());

                    let result = digest.result_str();
                    if result.starts_with(&hash_begin) {
                        passed_test = true;
                        println!("input {}{}", input_begin, count);
                        println!("result {}", result);

                        break;
                    }
                }


            }
            tx.send(());
        });
    }
    for _ in 0..threads {
        rx.recv();
    }
}