Advent of Code 2015 Day 5: Doesn’t He Have Intern-Elves For This?

Input is a list of strings, one per line.

Part 1

A string is considered ‘nice’ if it fulfils all the following criteria:

We need an ‘is string nice’ function, which can be decomposed into three smaller functions to make testing easier.

Count vowels: This goes through the string one character at a time and increments the counter using a switch statement if the character matches any vowels, with a delibate fall through since they all have the same action.

size_t count_vowels(const char * const str) {
    size_t length = strlen(str);
    size_t count = 0;

    for (size_t c = 0; c < length; c++) {
        switch (str[c]) {
            case 'a':
            case 'e':
            case 'i':
            case 'o':
            case 'u':
                count++;
                break;
        }
    }

    return count;
}

We could optimise this function to stop as soon as it finds three vowels, but the criteria may change in part 2 (which we can’t see until we solve part 1) so we will leave it to return the full count. If we were processing very large strings we might want to pass in a max_count parameter, which would stop the counting at that point.

Contains double letter: Similar to counting the vowels, we step through the string one character at a time. This time we compare the current character to the next character - taking care not to read beyond the end of the string - and if they match we return true immediately. We also return false immediately if the string is empty. We could have implemented this differently by using our aoc_sub_string function to get a specific number of characters ahead and check if they were all the same, however we take the risk that this may be required in part 2.

bool contains_double_letter(const char * const str) {
    size_t length = strlen(str);

    // Edge case: Empty string can never contain double letter
    if (length == 0) {
        return false;
    }

    for (size_t c = 0; c < length - 1; c++) {
        if (str[c] == str[c + 1]) {
            return true;
        }
    }

    return false;
}

Does not contain: This is the most complicated function. We invert the logic so we are looking for ‘does the string contain any of these strings’, which means we need a haystack (the string we are checking for niceness), an array of needles (the substrings to look for) and, because an array of array of characters (an array of strings) is implemented as a double pointer, we also need a count of the needles so that we do not read beyond the end of the memory block in which they reside. We can return immediately if we find a substring, because we only want to know if the haystack contains any of the needles - we don’t care which ones or how many.

bool contains_any(const char * const haystack, const char ** const needles, size_t needles_count) {
    // Edge case: No needles makes no sense so is always false
    if (needles_count == 0) {
        return false;
    }

    size_t haystack_length = strlen(haystack);

    // Edge case: Empty string never contains needles
    if (haystack_length == 0) {
        return false;
    }

    // Check if each needle is in the string
    for (size_t n = 0; n < needles_count; n++) {
        if (aoc_prefix_substring(haystack, needles[n]) != haystack_length) {
            return true;
        }
    }

    return false;
}

Our is string nice? function is then just a combination of the above:

bool is_nice_original(const char * const str) {
    const char * needles[] = {
        "ab",
        "cd",
        "pq",
        "xy",
    };

    size_t vowels = count_vowels(str);
    bool double_letters = contains_double_letter(str);
    bool contains_needles = contains_any(str, needles, 4);

    return vowels >= 3 && double_letters && !contains_needles;
}

We have hardcoded the needles but could have passed them as a parameter. If we were dealing with a much larger data set, we could decide to bail out early on the first failed niceness check. We could also re-order the checks so that we either ran the least expensive ones first, or the ones most likely to fail first.

Our complete solution is then to call this function, which will count the number of nice strings in our input:

size_t count_nice_original(const char * const input) {
    size_t count = 0;
    aoc_explode_result_t input_lines = aoc_explode("\n", input);

    for (size_t i = 0; i < input_lines.size; i++) {
        if (is_nice_original(input_lines.data[i])) {
            count++;
        }
    }

    return count;
}

Part 2

Part 2 is very similar, except the rules for niceness are now that the string must:

As with part 1, we can make each criteria its own function, then combine them at the end.

Pair twice without overlapping: The simplest way to achieve this is to iterate over every consecutive pair of characters and see if they appear in the rest of the string, i.e. everything from after the end of the pair. Instead of treating the string as an array, let’s also try pointer arithmetic to iterate over the characters, remembering that our termination point should be two characters before the end of the string, because if we don’t have two characters left (excluding the \0 terminator), we can’t have another instance of the pair. There is already a standard library function, strstr, which searches a haystack for a needle. We can stop checking as soon as we find one other instance of the pair, because we only care that there are at least two.

bool contains_pair_no_overlap(const char * const str) {
    const char * const start = str;
    const char * const end = strchr(str, '\0');
    char * const pair = calloc(3, sizeof(char));
    const char * haystack;

    for (const char *position = start; position < end - 2; position++) {
        // Get next pair
        pair[0] = *position;
        pair[1] = *(position + 1);

        // Check if this pair appears again
        haystack = position + 2;

        if (strstr(haystack, pair) != NULL) {
            return true;
        }
    }

    return false;
}

One repeated letter separated by one letter: This is similar to our previous ‘consecutive repeated letter’ check, we just move forward two spaces instead of one. We also return false immediately if the string has less than 3 characters, because it cannot possibly meet the criteria we have set.

bool contains_repeated_letter_separated(const char * const str) {
    size_t length = strlen(str);

    // Strings less than 3 characters cannot contain a repeat and separation
    if (length < 3) {
        return false;
    }

    for (size_t c = 0; c < length - 2; c++) {
        if (str[c] == str[c + 2]) {
            return true;
        }
    }

    return false;
}

Our new ‘is nice’ function chains the two together:

bool is_nice_modified(const char * const str) {
    return contains_pair_no_overlap(str) && contains_repeated_letter_separated(str);
}

Finally, we have a function to split the input by lines and count the number of nice strings:

size_t count_nice_modified(const char * const input) {
    size_t count = 0;
    aoc_explode_result_t input_lines = aoc_explode("\n", input);

    for (size_t i = 0; i < input_lines.size; i++) {
        if (is_nice_modified(input_lines.data[i])) {
            count++;
        }
    }

    return count;
}