1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

//! # Day 5: How About a Nice Game of Chess?
//!
//! You are faced with a security door designed by Easter Bunny engineers that seem to have acquired
//! most of their security knowledge by watching [hacking movies].
//!
//! The **eight-character password** for the door is generated one character at a time by finding
//! the [MD5] hash of some Door ID (your puzzle input) and an increasing integer index (starting
//! with `0`).
//!
//! A hash indicates the **next character** in the password if its [hexadecimal] representation
//! starts with **five zeroes**. If it does, the sixth character in the hash is the next character
//! of the password.
//!
//! For example, if the Door ID is `abc`:
//!
//! - The first index which produces a hash that starts with five zeroes is `3231929`, which we find
//!   by hashing `abc3231929`; the sixth character of the hash, and thus the first character of the
//!   password, is `1`.
//! - `5017308` produces the next interesting hash, which starts with `000008f82...`, so the second
//!   character of the password is `8`.
//! - The third time a hash starts with five zeroes is for `abc5278568`, discovering the character
//!   `f`.
//!
//! In this example, after continuing this search a total of eight times, the password is
//! `18f47a30`.
//!
//! Given the actual Door ID, **what is the password**?
//!
//! [hacking movies]: https://en.wikipedia.org/wiki/Hackers_(film)
//! [MD5]: https://en.wikipedia.org/wiki/MD5
//! [hexadecimal]: https://en.wikipedia.org/wiki/Hexadecimal
//!
//! ## Part Two
//!
//! As the door slides open, you are presented with a second door that uses a slightly more inspired
//! security mechanism. Clearly unimpressed by the last version (in what movie is the password
//! decrypted **in order**?!), the Easter Bunny engineers have worked out [a better solution].
//!
//! Instead of simply filling in the password from left to right, the hash now also indicates the
//! **position** within the password to fill. You still look for hashes that begin with five zeroes;
//! however, now, the **sixth** character represents the **position** (`0`-`7`), and the **seventh**
//! character is the character to put in that position.
//!
//! A hash result of `000001f` means that `f` is the **second** character in the password. Use only
//! the **first result** for each position, and ignore invalid positions.
//!
//! For example, if the Door ID is `abc`:
//!
//! - The first interesting hash is from `abc3231929`, which produces `0000015...`; so, `5` goes in
//!   position `1`: `_5______`.
//! - In the previous method, `5017308` produced an interesting hash; however, it is ignored,
//!   because it specifies an invalid position (`8`).
//! - The second interesting hash is at index `5357525`, which produces `000004e...`; so, `e` goes
//!   in position `4`: `_5__e___`.
//!
//! You almost choke on your popcorn as the final character falls into place, producing the password
//! `05ace8e3`.
//!
//! Given the actual Door ID and this new method, **what is the password**? Be extra proud of your
//! solution if it uses a cinematic "decrypting" animation.
//!
//! [a better solution]: https://www.youtube.com/watch?v=NHWjlCaIrQo&t=25

use anyhow::{bail, Context, Result};
use md5::{Digest, Md5};
use rayon::prelude::*;

pub const INPUT: &str = include_str!("d05.txt");

pub fn solve_part_one(input: &str) -> Result<String> {
    let door_id = parse_input(input)?;

    Ok((0..u32::MAX)
        .filter_map(|counter| {
            let mut hasher = Md5::default();
            hasher.update(door_id.as_bytes());
            hasher.update(&counter.to_string());

            hasher
                .finalize()
                .strip_prefix(&[0, 0])
                .and_then(|h| h.first())
                .copied()
                .filter(|b| b & 0xF0 == 0)
                .and_then(|b| char::from_digit(b as u32, 16))
        })
        .take(8)
        .collect())
}

pub fn solve_part_two(input: &str) -> Result<String> {
    let door_id = parse_input(input)?;
    let mut password = [' '; 8];

    let hashes = (0..u32::MAX).filter_map(|counter| {
        let mut hasher = Md5::default();
        hasher.update(door_id.as_bytes());
        hasher.update(&counter.to_string());

        hasher
            .finalize()
            .strip_prefix(&[0, 0])
            .and_then(|h| h.first().copied().zip(h.get(1).copied()))
            .filter(|(pos, _)| *pos < 8)
            .and_then(|(pos, val)| {
                char::from_digit((val >> 4) as u32, 16).map(|val| (pos as usize, val))
            })
    });

    for (position, value) in hashes {
        if password[position] != ' ' {
            continue;
        }

        password[position] = value;

        if password.iter().all(|&c| c != ' ') {
            return Ok(password.iter().collect());
        }
    }

    bail!("no password found for the given door ID")
}

fn parse_input(input: &str) -> Result<&str> {
    input.lines().next().context("input is empty")
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn part_one() {
        assert_eq!("18f47a30", solve_part_one("abc").unwrap());
    }

    #[test]
    fn part_two() {
        assert_eq!("05ace8e3", solve_part_two("abc").unwrap());
    }
}