Day 11: Corporate Policy

link to problem

The Problem

Santa's previous password expired, and he needs help choosing a new one.

To help him remember his new password after the old one expires, Santa has devised a method of coming up with a password based on the previous one. Corporate policy dictates that passwords must be exactly eight lowercase letters (for security reasons), so he finds his new password by incrementing his old password string repeatedly until it is valid.

Incrementing is just like counting with numbers: xx, xy, xz, ya, yb, and so on. Increase the rightmost letter one step; if it was z, it wraps around to a, and repeat with the next letter to the left until one doesn't wrap around.

Unfortunately for Santa, a new Security-Elf recently started, and he has imposed some additional password requirements:

Passwords must include one increasing straight of at least three letters, like abc, bcd, cde, and so on, up to xyz. They cannot skip letters; abd doesn't count.

Passwords may not contain the letters i, o, or l, as these letters can be mistaken for other characters and are therefore confusing.

Passwords must contain at least two different, non-overlapping pairs of letters, like aa, bb, or zz.

For example:

hijklmmn meets the first requirement (because it contains the straight hij) but fails the second requirement requirement (because it contains i and l).

abbceffg meets the third requirement (because it repeats bb and ff) but fails the first requirement.

abbcegjk fails the third requirement, because it only has one double letter (bb).

The next password after abcdefgh is abcdffaa.

The next password after ghijklmn is ghjaabcc, because you eventually skip all the passwords that start with ghi..., since i is not allowed.

Given Santa's current password (your puzzle input), what should his next password be?

Your puzzle input is hxbxwxba.

Thoughts

The password being a fixed size great help. 8 characters is small enough that I can create a function for each one of these checks and not care how long it will take to process.

For no reason in particular, I am thinking about fancy stuff like a validate function that takes a list of functions and a string as input. The string will then get tested against all the functions in the list and if any of the function return false, it will return false.

The reason I can do this is because all the validation checks have the same function signature, which is that they take in a string reference and return a boolean.

The harder part of this question might be the incrementing of strings. I'm silly. I have been sitting here struggling to think of ways to interate over the charaters while skipping i, o, and l, like that is actually a requirement. I will use the numbers 0 - 25 and i will convert them back and forth between characters as needed. I'm thinking a struct that holds an internal list of numbers. It has an increment method that cycles up and another method that returns the string representation of the array so that I can pass it to the validate function.

I could take time to think about the other parts of the problem, but I'm pretty tired. So lets write this up and go to bed.

Solution

This took a lot longer to write than I thought it would and, with regard to speed of the code, this is, by far, the slowest thing I have written so far.

use std::collections::HashMap;
use std::io;

struct Password {
    internal: Vec<usize>,
    number_map: HashMap<usize, String>,
    letter_map: HashMap<String, usize>,
}

impl Password {
    fn new(
        data: &str,
        number_map: HashMap<usize, String>,
        letter_map: HashMap<String, usize>,
    ) -> Self {
        let internal: Vec<usize> = data
            .chars()
            .map(|x| x.to_string())
            .map(|y| letter_map.get(&y).unwrap().clone())
            .collect();
        Self {
            internal,
            number_map,
            letter_map,
        }
    }

    fn to_string(&self) -> String {
        self.internal
            .iter()
            .map(|x| self.number_map.get(x).unwrap())
            .map(|y| y.clone())
            .collect()
    }

    fn increment(&mut self) {
        let mut index = self.internal.len() - 1;

        loop {
            match self.internal[index] {
                25 => {
                    self.internal[index] = 0;
                    if index == 0 {
                        break;
                    } else {
                        index -= 1;
                    }
                }
                _ => {
                    self.internal[index] += 1;
                    break;
                }
            }
        }
    }
}

fn validate(funcs: Vec<fn(&str) -> bool>, input: String) -> bool {
    let mut result = true;

    for func in funcs.iter() {
        match func(&input) {
            false => {
                result = false;
                break;
            }
            true => {}
        }
    }
    result
}

fn contains_unwanted_letters(data: &str) -> bool {
    let mut result = true;

    for letter in data.chars() {
        match letter {
            'o' | 'i' | 'l' => {
                result = false;
                break;
            }
            _ => {}
        }
    }
    result
}

fn contains_two_pairs(data: &str) -> bool {
    let mut pairs = Vec::new();

    let list: Vec<char> = data.chars().collect();

    let mut index = 1;
    while index < list.len() {
        let prev_char = list[index - 1];
        let curr_char = list[index];

        match prev_char.eq(&curr_char) {
            true => {
                if !pairs.contains(&format!("{prev_char}{curr_char}")) {
                    pairs.push(format!("{prev_char}{curr_char}"));
                    index += 1;
                }
            }
            false => {}
        }

        index += 1;
    }

    pairs.len() >= 2
}

fn contains_seq_letters(data: &str) -> bool {
    let letter_map: HashMap<String, usize> = "abcdefghijklmnopqrstuvwxyz"
        .chars()
        .map(|x| x.to_string())
        .enumerate()
        .map(|(num, letter)| (letter, num))
        .collect();

    let mut result = false;

    let list: Vec<String> = data.chars().map(|x| x.to_string()).collect();
    let mut index = 2;

    while index < list.len() {
        let num_1 = letter_map.get(&list[index - 2]).unwrap();
        let num_2 = letter_map.get(&list[index - 1]).unwrap();
        let num_3 = letter_map.get(&list[index]).unwrap();

        //println!("{}, {}, {}", num_1, num_2, num_3);

        if num_1 + 1 == *num_2 && num_2 + 1 == *num_3 {
            result = true;
            break;
        }
        index += 1;
    }
    //println!("seq: {result}");
    result
}

fn main() {
    let mut letter_to_number = HashMap::new();
    let mut number_to_letter = HashMap::new();

    for (index, letter) in "abcdefghijklmnopqrstuvwxyz".chars().enumerate() {
        letter_to_number.insert(index.clone(), letter.to_string());
        number_to_letter.insert(letter.to_string(), index);
    }

    for line in io::stdin().lines() {
        let data = line.unwrap();

        let mut password = Password::new(
            &data.to_string(),
            letter_to_number.clone(),
            number_to_letter.clone(),
        );

        let mut result = password.to_string();
        let checks = vec![
            contains_seq_letters,
            contains_unwanted_letters,
            contains_two_pairs,
        ];

        while !validate(checks.clone(), result.clone()) {
            password.increment();
            result = password.to_string();
            //println!("{result}");
        }

        println!("{result}");
    }
}

I did everything I said I was going to do. I created a struct called Password that has a increment method and a to_string method. Internally, it manipulates and Vec of numbbers, which makes the implementation for the increment method manageable.

I have a validate function that takes a list of functions with the signature of fn (&str) -> bool and it also has a parameter called input which is a String. The validate function iterates over the functions in the list, it passes a reference to input to those functions and makes sure they all return true.

I then wrote out each of the requirements as functions.

Architectually, I really like this code because everything is broken down into small components. Maintaining this code would a breeze. That said, the reason the code is slow to solve the problem is because I separated everything out.

The next password after ghijklmn is ghjaabcc, because you eventually skip all the passwords that start with ghi..., since i is not allowed.

My code increments that password one unit at a time, which means that I have to go through every ghi.... combination before getting to the correct answer. For this test input, the code took so long to complete that I was positive that I had an infinite loop somewhere. It wasn't until I killed the program and added print statements that realized that the program is fine, its just slow. That said, it was really cool to see the password increment up super fast.

The Problem Part 2

After I found the password in part 1, they wanted me to find the next password. So the code stays the same, but I did manually increment part 1's password by one to that it would be invalid. Otherwise the code returns the input because the input is a valid password.