Day 11 - Password

We have to find the next (in the alphabetical sense) valid password from a seed, using a set of arbitrary rules:

This feels like something that’s human-solvable, but I did a few attempts on my puzzle input and couldn’t get it right, so I must be missing something. I’m not feeling smart right now so I’m going to brute force it unless I get a better idea, or it takes too long. Let’s put the scaffolding first:

bool check(char* s){
    
}

void find_next(char *s){
    
}

int main(){
    printf("==Day 11==\n\n");

    char s[] = TEST_INPUT;
    find_next(s);
    printf("Part 1: %s\n", s);
    
    exit(0);
}

My test case will be the example given in the puzzle: ghijklmn, which must give me ghjaabcc. I want to have a find_next function that will start incrementing the s string’s character, testing them with check until it finds one that is valid.

Let’s first test (and write) the check function, using the examples given. First the test:

bool test_check(){
    if (check("hijklmmn"))
        printf("ERROR: hijklmmn should be invalid\n");
    if (check("abbceffg"))
        printf("ERROR: abbceffg should be invalid\n");
    if (check("abbcegjk"))
        printf("ERROR: abbcegjk should be invalid\n");
    if (!check("abcdffaa"))
        printf("ERROR: abcdffaa should be valid\n");
    if (!check("ghjaabcc"))
        printf("ERROR: ghjaabcc should be valid\n");
}

It obviously fails. Now writing the check function. In order to be a little bit smarter than originally announced, I’ll start by checking for the forbidden characters, which I think will be the fastest. Then for the pairs and threes, I’ll always start by checking if the condition is already met, as we don’t need the extra checks in that case. I think that’s going to be a little bit more efficient.

To check if the pairs are distinct, I use a boolean table: if the pair was already found, it doesn’t count.

bool check(char* s){
    bool has_three = FALSE;
    bool has_pair_set[26];
    int n_pairs = 0;
    for (int i = 0; i < 26; i++)
        has_pair_set[i] = FALSE; 

    // check forbidden first, it's fast
    for (int i=0; i < 8; i++){
        if (s[i] == 'i' || s[i] == 'o' || s[i] == 'l') 
            return false;
    }

    // pairs and threes
    for (int i=0; i < 7; i++){
        if (n_pairs < 2 && s[i] == s[i+1] && !has_pair_set[s[i]-'a']){
            has_pair_set[s[i]-'a'] = TRUE;
            n_pairs++;
        }
        if (!has_three && i < 6 && s[i] == s[i+1]-1 && s[i+1] == s[i+2]-1){
            has_three = TRUE;
        }
    }

    return has_three && n_pairs >= 2;
}

My very robust tests now pass. Moving on to the “increment all letters” part, hoping it doesn’t take forever to compute.

I’ll use a do... while, which is something I almost never do but it seems appropriate here. We start from the last letter, increment it, and if we get to z we move back one letter and carry over. Whenever we have finished the carry-over process, we check if we have found a valid string.

char* find_next(char *s){
    do {
        int p = 7;
        while (p >= 0){
            s[p] = s[p]+1;
            if (s[p] > 'z'){
                s[p--] = 'a';
            } else{
                break;
            }
        } 
    } while (!check(s));

    return s;
}

I should also check that we haven’t wrapped up all the way to aaaaaaaa, but I’ll assume for the moment that we eventually get to a valid string. On to the main:

int main(){
    printf("==Day 11==\n\n");

    char input[] = INPUT;
    char* next = find_next(input);
    printf("Part 1: %s\n", next);
    
    exit(0);
}

On the test input, I get the right answer. On the real input as well, and I should have been able to find it manually as there was no particular trick. Some brain fog going on tonight, but I got the code right, so it seems that my computer can do the thinking for me, without resorting to a stochastic bullshit generator. Good.

next = find_next(next);
printf("Part 2: %s\n", next);

Which works as well, unsurprisingly. I realize now that, since I’m changing s in-place in find_next, I don’t need the next variable:

int main(){
    printf("==Day 11==\n\n");

    char input[] = INPUT;
    find_next(input);
    printf("Part 1: %s\n", input);
    find_next(input);
    printf("Part 2: %s\n", input);
    
    exit(0);
}

Another quick two stars. Two easy puzzles in a row, I fear that I’m getting lured in a false sense of confidence. We’ll see.