use md5;

type Hash = Vec<char>;

// Find first `char' appearing three time in a row in `h', if any
fn find_triple(h: &Hash) -> Option<char> {
    for i in 0..h.len() - 2 {
        if h[i] == h[i + 1] && h[i] == h[i + 2] {
            return Some(h[i]);
        }
    }
    None
}

// Does `h' contain `c' five times in a row?
fn has_quintuple(h: &Hash, c: char) -> bool {
    let mut qs: Vec<char> = Vec::new();

    for i in 0..h.len() - 4 {
        if h[i] == h[i + 1] && h[i] == h[i + 2] && h[i] == h[i + 3] && h[i] == h[i + 4] {
            qs.push(h[i])
        }
    }

    qs.contains(&c)
}

struct HashCache<'a> {
    salt: &'a str,
    reps: usize,
    vec: Vec<Hash>,
}

impl<'a> HashCache<'a> {
    fn new(salt: &'a str, reps: usize) -> Self {
        HashCache {
            salt,
            reps,
            vec: Vec::new(),
        }
    }

    // Generate hashes on demand, and always cache them for later use.
    // Can't write this as `impl Index<usize> for HashCache' because
    // the `Index' trait only allows an immutable borrow `&self'.
    fn at_index(&mut self, i: usize) -> &Hash {
        // If this hash is not in the cache yet...
        if i >= self.vec.len() {
            // ... calculate all hashes up to the requested one
            for j in self.vec.len()..i + 1 {
                let d = format!("{}{}", self.salt, j);
                let mut h = format!("{:x}", md5::compute(d));

                // Additional key stretching repetitions
                for _k in 0..self.reps {
                    h = format!("{:x}", md5::compute(h));
                }

                self.vec.push(h.chars().collect());
            }
        }

        &self.vec[i]
    }
}

fn solve_puzzle(salt: &str, reps: usize) -> usize {
    // The 64 valid indices we want to find
    let mut valid = Vec::new();

    let mut hc = HashCache::new(salt, reps);
    let mut i = 0;
    while valid.len() < 64 {
        // If `hc.at_index(i)' contains any `c' three times in a row
        if let Some(c) = find_triple(hc.at_index(i)) {
            for j in 1..1001 {
                if has_quintuple(hc.at_index(i + j), c) {
                    valid.push(i);
                    break;
                }
            }
        }

        i += 1;
    }

    *valid.last().unwrap()
}

fn main() {
    // My personal puzzle input
    let salt = "yjdafjpo";

    // Part 1 gives 25427 for me
    println!("Part 1 solution: {}", solve_puzzle(salt, 0));

    // Part 2 gives 22045 for me
    println!("Part 2 solution: {}", solve_puzzle(salt, 2016));
}

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

    #[test]
    fn part1_example1() {
        let salt = "abc";
        assert_eq!(solve_puzzle(salt, 0), 22728);
    }

    #[test]
    fn part2_example1() {
        let salt = "abc";
        assert_eq!(solve_puzzle(salt, 2016), 22551);
    }
}