day19a.c

#include "common.h"
#include "stringview.h"

enum TokenType {
    TOKEN_CHAR,
    TOKEN_NUMBER,
    TOKEN_BAR,
};

struct Token {
    enum TokenType type;
    union {
        char character;
        int number;
    };
};

enum MatchType {
    MATCH_CHAR,
    MATCH_REF
};

struct Match {
    enum MatchType type;
    union {
        char character;
        int rule_id;
    };
};

struct MatchList {
    size_t n_matches;
    struct Match matches [];
};

struct Rule {
    size_t n_options;
    struct MatchList * lists [];
};

struct Rule * rules [256] = {};

size_t matchesRule (int rule_id, StringView_t const * str) {
    struct Rule * rule = rules[rule_id];
    for (size_t i = 0; i < rule->n_options; ++i) {
        struct MatchList * list = rule->lists[i];
        _Bool matches_all = 1;
        size_t n_matched = 0;
        StringView_t s = *str;
        for (size_t j = 0; j < list->n_matches; ++j) {
            ASSERT(!sv_is_empty(&s));
            struct Match * match = &(list->matches[j]);
            if (match->type == MATCH_CHAR) {
                if (s.start[0] == match->character) {
                    n_matched += 1;
                    sv_eat_char(&s);
                } else {
                    matches_all = 0;
                    break;
                }
            } else {
                ASSERT(match->type == MATCH_REF);
                size_t n = matchesRule(match->rule_id, &s);
                if (n) {
                    n_matched += n;
                    s.start += n;
                } else {
                    matches_all = 0;
                    break;
                }
            }
        }
        if (matches_all) {
            return n_matched;
        }
    }
    return 0;
}

int main (int argc, char ** argv) {
    do {
        char buf [BUFSIZ];
        char * s = fgets(&(buf[0]), sizeof(buf), stdin);
        ASSERT(s);

        StringView_t line = sv_view_c_string(&(buf[0]));
        sv_eat_spaces(&line);
        if (sv_is_empty(&line)) {
            break;
        }

        size_t tokens_count = 0;
        struct Token tokens [256];

        StringView_t id_str = sv_eat_until(&line, ':');
        ASSERT(*line.start == ':');
        sv_eat_char(&line);
        sv_eat_spaces(&line);
        while (!sv_is_empty(&line)) {
            StringView_t token_str = sv_eat_until_space(&line);
            struct Token tok;
            if (sv_equals(&token_str, "|")) {
                tok.type = TOKEN_BAR;
            } else if (isdigit(*token_str.start)) {
                tok.type = TOKEN_NUMBER;
                tok.number = strtol(token_str.start, NULL, 10);
            } else if (token_str.start[0] == '"') {
                ASSERT(sv_length(&token_str) == 3 && token_str.start[2] == '"');
                tok.type = TOKEN_CHAR;
                tok.character = token_str.start[1];
            }
            ASSERT(tokens_count < ARRAYCOUNT(tokens));
            tokens[tokens_count++] = tok;
            sv_eat_spaces(&line);
        }

        size_t n_options = 1;
        for (size_t i = 0; i < tokens_count; ++i) {
            if (tokens[i].type == TOKEN_BAR) {
                n_options += 1;
            }
        }

        struct Rule * rule = malloc(sizeof(struct Rule) + sizeof(struct MatchList *)*n_options);

        size_t i_start = 0;
        for (size_t i = 0; i < tokens_count; ++i) {
            if (tokens[i].type == TOKEN_BAR) {
                size_t n_matches = i - i_start;
                struct MatchList * list = malloc(sizeof(struct MatchList) + sizeof(struct Match)*n_matches);
                list->n_matches = n_matches;
                for (size_t j = 0; j < n_matches; ++j) {
                    struct Match match;
                    switch (tokens[i_start+j].type) {
                        case TOKEN_NUMBER: {
                            match.type = MATCH_REF;
                            match.rule_id = tokens[i_start+j].number;
                        } break;
                        case TOKEN_CHAR: {
                            match.type = MATCH_CHAR;
                            match.character = tokens[i_start+j].character;
                        } break;
                        default: {
                            ASSERT(0);
                        }
                    }
                    list->matches[j] = match;
                }
                rule->lists[rule->n_options++] = list;
                i_start = i+1;
            }
        }
        {
            size_t n_matches = tokens_count - i_start;
            struct MatchList * list = malloc(sizeof(struct MatchList) + sizeof(struct Match)*n_matches);
            list->n_matches = n_matches;
            for (size_t j = 0; j < n_matches; ++j) {
                struct Match match;
                switch (tokens[i_start+j].type) {
                    case TOKEN_NUMBER: {
                        match.type = MATCH_REF;
                        match.rule_id = tokens[i_start+j].number;
                    } break;
                    case TOKEN_CHAR: {
                        match.type = MATCH_CHAR;
                        match.character = tokens[i_start+j].character;
                    } break;
                    default: {
                        ASSERT(0);
                    }
                }
                list->matches[j] = match;
            }
            rule->lists[rule->n_options++] = list;
        }

        unsigned long id = strtoul(id_str.start, NULL, 10);
        ASSERT(id < ARRAYCOUNT(rules));
        rules[id] = rule;
    } while (1);

    size_t n_matching = 0;
    do {
        char buf [BUFSIZ];
        char * s = fgets(&(buf[0]), sizeof(buf), stdin);
        if (!s) {
            break;
        }

        StringView_t line = sv_view_c_string(&(buf[0]));
        sv_eat_spaces(&line);
        if (sv_is_empty(&line)) {
            break;
        }
        line = sv_eat_until_space(&line);

        size_t n = matchesRule(0, &line);
        if (n == sv_length(&line)) {
            n_matching += 1;
        }
    } while (1);
    DISP(n_matching);
}