Day 5 - Just a string

We have a bunch of seemingly random strings, separated by a new line. We need to find which strings are valid, according to a bunch of arbitrary rules. Let’s make sure that we can reuse our file reading and parsing methods from before:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "futils.h"
#include "parser.h"

#define FILE_INPUT "./data/day5.txt"

int main(){
    char* fcontent = freadall(FILE_INPUT);
    str_list_t* strings = parse_strings(fcontent, '\n');
    printf("Number of strings: %d", strings->n);

    exit(0);
}

Now make day5 compiles everything I need, and I get 1001 strings. There are 1000 in my input file, plus an empty string at the end. Everything is looking good so far.

First attempt

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "futils.h"
#include "parser.h"

#define FILE_INPUT "./data/day5.txt"

bool is_vowel(char c){
    return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}

bool is_repeat(char a, char b){
    return a==b;
}

bool is_forbidden(char a, char b){
    return (a=='a' && b=='b') ||
           (a=='c' && b=='d') ||
           (a=='p' && b=='q') ||
           (a=='x' && b=='y');
}

bool is_valid(char* str){
    int n_vowels = 0;
    bool repeat = false;
    
    for( int i=0; i < strlen(str)-1; i++ ){
        if (is_forbidden(str[i], str[i+1]))
            return false;
        if (is_vowel(str[i]))
            n_vowels++;
        if (is_repeat(str[i], str[i+1]))
            repeat = true;
    }
    if (is_vowel(str[strlen(str)]))
        n_vowels++;

    return repeat && (n_vowels>=3);
}

int count_valids(str_list_t* strings){
    int n = 0;
    for (int i=0; i < strings->n; i++){
        if (strlen(strings->str_list[i]) == 0)
            continue;
        if (is_valid(strings->str_list[i]))
            n++;
    }
    return n;
}

int main(){
    char* fcontent = freadall(FILE_INPUT);
    str_list_t* strings = parse_strings(fcontent, '\n');
    printf("Number of strings: %d\n", strings->n);
    int valid = count_valids(strings);
    printf("Number of valid strings: %d\n", valid);

    exit(0);
}

I get a result which is apparently too low, so I’ve made a mistake somewhere. Time to actually do some tests (which I should really have done before, to be honest, but this looked simple enough…)

Bug hunt

Anyway. I wanted to make my testing process a bit better. In my test_coords.c file I had made a helper “assert” function to make the output of the tests a bit easier to generate (and read), so let’s extract that to a testutils.c file.

#include <stdio.h>
#include <stdbool.h>

void assert(bool result, char* msg){
    if (result)
        printf("[OK] %s\n");
    else
        printf("[FAIL] %s\n");
}

With a corresponding .h file which I can include in day5.c, and start writing my tests.

bool test_is_vowel(){
    return (is_vowel('a') && is_vowel('e') && is_vowel('i') && 
            is_vowel('o') && is_vowel('u') && !is_vowel('b'));
}

void run_tests(){
    assert(test_is_vowel(), "Test is_vowel");
}

int main(){
    run_tests();
    // ...
}

bool test_is_repeat(){
    return (is_repeat('a', 'a') && 
            is_repeat('x', 'x') && 
            !is_repeat('x', 'y'));
}

bool test_is_forbidden(){
    return (is_forbidden('a', 'b') && 
           is_forbidden('c', 'd') && 
           is_forbidden('p', 'q') && 
           is_forbidden('x', 'y') && 
           !is_forbidden('y', 'x'));
}

Still fine. Let’s use the test strings given by Eric in the puzzle to check the combination of the functions.

bool test_is_valid(){
    return (is_valid("ugknbfddgicrmopn") &&
            is_valid("aaa") && 
            !is_valid("jchzalrnumimnmhp") && 
            !is_valid("haegwjzuvuyypxyu") && 
            !is_valid("dvszwmarrgswjxmb"));
}

FAIL. Good, if it passed it would mean something really weird is going on. Adding some debugging: ugknbfddgicrmopn is valid, but not aaa.

if (is_vowel(str[strlen(str)]))
    n_vowels++;

if (is_vowel(str[strlen(str)-1]))
    n_vowels++;

Off-by-one errors, always nice. Fixed, all test pass, and we get the star for part one.

Part two - new rules

The rules are a bit more annoying this time, as they should be. A valid string is defined as:

The second rule is easy, I just need a two-characters offset in my is_repeat call. But for the first one, I think I need a representation of a pair of letters. I’m thinking about:

First a char_pair_t type with a create and destroy function, and an equality test:

typedef struct {
    char first;
    char second;
} char_pair_t;

char_pair_t* char_pair_create(char first, char second){
    char_pair_t* pair = malloc(sizeof(char_pair_t));
    pair->first = first;
    pair->second = second;
    return pair;
}

void char_pair_destroy(char_pair_t* pair){
    free(pair);
}

bool char_pair_is_equal(char_pair_t* a, char_pair_t* b){
    return (a->first == b->first && a->second == b->second);
}

bool test_char_pairs(){
    char_pair_t* a = char_pair_create('a', 'b');
    char_pair_t* b = char_pair_create('a', 'b');
    char_pair_t* c = char_pair_create('b', 'a');

    assert(char_pair_is_equal(a, b), "a, b == a, b");
    assert(!char_pair_is_equal(a, c), "a, b != b, a");

    char_pair_destroy(a);
    char_pair_destroy(b);
    char_pair_destroy(c);
}

Passes. Now a list of pairs. This time I’ll make it capable of growing if needed, so it will have a capacity as well as a size. With a create and destroy first.

typedef struct {
    char_pair_t** list;
    int n;
    int capacity;
} list_char_pair_t;

list_char_pair_t* list_char_pair_create(int capacity){
    list_char_pair_t* list = malloc(sizeof(list_char_pair_t));
    list->n = 0;
    list->capacity = capacity;
    list->list = malloc(sizeof(char_pair_t*)*list->capacity);
}

void list_char_pair_destroy(list_char_pair_t* list){
    for (int i=0; i < list->n; i++)
        char_pair_destroy(list->list[i]);
    free(list->list);
    free(list);
}

Then we need a contains and a add, which will reallocate memory if we are over the capacity:

bool list_char_pair_contains(list_char_pair_t* list, char_pair_t* pair){
    for (int i=0; i < list->n; i++) {
        if (char_pair_is_equal(list->list[i], pair))
            return true;
    }
    return false;
}

void list_char_pair_add(list_char_pair_t* list, char_pair_t* pair){
    if (list->capacity == list->n){
        list->capacity = list->capacity*2;
        list->list = realloc(list, sizeof(char_pair_t*)*list->capacity);
    }
    list->list[list->n++] = pair;
}

bool test_list_char_pair(){
    list_char_pair_t* list = list_char_pair_create(2);
    assert(list->n == 0, "list created with 0 elements");
    assert(list->capacity == 2, "list created with capacity of 2");
    list_char_pair_add(list, char_pair_create('a', 'b'));
    list_char_pair_add(list, char_pair_create('b', 'c'));
    list_char_pair_add(list, char_pair_create('c', 'd')); // should grow the list

    assert(list->n == 3, "list has correct size");
    assert(list->capacity == 4, "list has grown its capacity");

    assert(list_char_pair_contains(list, char_pair_create('a', 'b')), "list contains a,b");
    assert(!list_char_pair_contains(list, char_pair_create('e', 'f')), "list doesn't contains e,f");
    list_char_pair_destroy(list);
}

Crashes in list_char_pair_add. Commenting out the third add and the tests (obviously) fail but without crashing, so it must be the growing mechanism.

Ah yes, I was reallocating list and not list->list. Fixed, and all test pass. I should have everything I need now.

Let’s try something. I realize that it would be useful to have also a function to get the last item in the list:

char_pair_t* list_char_pair_last(list_char_pair_t* list){
    return list->list[list->n-1];
}

bool is_valid_part_2(char* str){
    if (strlen(str) < 2)
        return false;

    bool pair_valid = false;
    bool repeated = false;

    list_char_pair_t* list = list_char_pair_create(16);
    list_char_pair_add(list, char_pair_create(str[0], str[1]));

    for (int i=1; i < strlen(str)-1; i++){
        char_pair_t* pair = char_pair_create(str[i], str[i+1]);
        if (list_char_pair_contains(list, pair) && 
            !char_pair_is_equal(list_char_pair_last(list), pair))
            pair_valid = true;
        if (is_repeat(str[i-1], str[i+1]))
            repeated = true;
    }

    list_char_pair_destroy(list);
    return (pair_valid && repeated);
}

void test_valid_part_two(){
    assert(is_valid_part_2("qjhvhtzxzqqjkmpb"), "qjhvhtzxzqqjkmpb");
    assert(is_valid_part_2("xxyxx"), "xxyxx");
    assert(!is_valid_part_2("uurcxstgmygtbstg"), "uurcxstgmygtbstg");
    assert(!is_valid_part_2("ieodomkazucvgmuy"), "ieodomkazucvgmuy");
}

Fail: the two valid strings are not valid. That’s probably because I forgot to add the pair to the list after checking if it’s already there… Fixed, and we pass the tests. Now run on the whole sequence…

…and we don’t have the right number. I had a feeling that would happen, because there’s at least one edge case I haven’t considered yet. What if we have something like aaaa.

That’s because I thought I didn’t need to do a set here, but in fact that should solve my issue. Only add the pair to the list if it’s not there yet.

//...
bool contains = list_char_pair_contains(list, pair);
if ( contains && 
    !char_pair_is_equal(list_char_pair_last(list), pair))
    pair_valid = true;
if (!contains)
    list_char_pair_add(list, pair);

assert(is_valid_part_2("aaaa"), "aaaa");

Still fails? Of course. Even though I didn’t add the second aa, the last element of the list is still the first aa so it will still be counted as an overlap. I need to add a dummy pair to make it work. Not the cleanest, but it’ll do:

if (!contains)
    list_char_pair_add(list, pair);
else
    list_char_pair_add(list, char_pair_create('0', '0'));

Test passes, and I get the right answer on the puzzle input. We’re done with star number ten.

I don’t think it’s worth refactoring my pairs and lists here, they are a bit too ad-hoc for this particular puzzle. But it’s nice to have a template for a “list that can grow indefinitely”, which I may need later.

I’m getting a bit better at making tests earlier in my process, which made me find bugs sooner than I would have otherwise, which is nice. Much better experience for day 5 than for day 4. Let’s see what’s next.