day06.c

#include <ctype.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>
#include <time.h>

#include "switching.h"

#define MAX_LINE_LENGTH 80
#define MAX_COMMANDS    500
#define GRID_SIZE       1000

typedef enum {TURN_ON, TURN_OFF, TOGGLE} Opcode;

typedef struct Command
{
    uint8_t opcode;
    union {
        uint16_t coordinates[4];
        struct {
            uint16_t x1, y1, x2, y2;
        };
    };
    struct Command *next;
} Command;

typedef struct
{
    uint16_t length;
    Command items[MAX_COMMANDS];
} Commands;

typedef struct
{
    uint16_t length;
    Command *items[MAX_COMMANDS];
} ActiveCommands;

#ifdef DEBUG
static const char *opcode2command[] = {"turn on", "turn off", "toggle"};
#endif

static Commands commands;
static Command *row2commands_to_start[GRID_SIZE];
static _Bool row2commands_change[GRID_SIZE + 1];
static _Bool row2just_remove_commands[GRID_SIZE];
static ActiveCommands active_commands;
uint16_t row[GRID_SIZE];

/* ------------------------------------------------------------------------ */

char* parse_int(char *string, uint16_t *result)
{
    uint16_t value;

    while (*string && !isdigit(*string)) ++string;
    if (!isdigit(*string)) return NULL;

    value = 0;
    while (isdigit(*string)) {
        value = value * 10 + (*string - '0');
        ++string;
    }
    *result = value;
    return string;
}

_Bool parse_line(char *line, Command *result)
{
    uint8_t i;

    if (strncmp(line, "turn o", 6) == 0) {
        if (line[6] == 'n' && line[7] == ' ') {
            result->opcode = TURN_ON;
        } else if (line[6] == 'f' && line[7] == 'f' && line[8] == ' ') {
            result->opcode = TURN_OFF;
        } else {
            return false;
        }
    } else if (strncmp(line, "toggle ", 7) == 0) {
        result->opcode = TOGGLE;
    } else {
        return false;
    }
    line += 7;

    for (i = 0; i < 4; ++i) {
        line = parse_int(line, &result->coordinates[i]);
        if (!line) return false;
    }

    result->next = NULL;

    return true;
}

_Bool parse_file(FILE *file)
{
    char line[MAX_LINE_LENGTH + 1];

    commands.length = 0;
    while (fgets(line, MAX_LINE_LENGTH, file)) {
        if (!parse_line(line, &commands.items[commands.length])) return false;
        ++commands.length;
    }

    return true;
}

#ifdef DEBUG
void debug_dump_commands(void)
{
    uint16_t i;
    Command *command;

    for (i = 0; i < commands.length; ++i) {
        command = &commands.items[i];
        printf(
            "%s %u,%u through %u,%u\n",
            opcode2command[command->opcode],
            command->x1,
            command->y1,
            command->x2,
            command->y2
        );
    }
}
#endif

void init_row_lookup_tables(void)
{
    int16_t i;
    uint16_t j;
    Command *command;

    memset(row2commands_to_start, 0, sizeof(row2commands_to_start));
    memset(row2commands_change, false, sizeof(row2commands_change));
    memset(row2just_remove_commands, false, sizeof(row2just_remove_commands));
    for (i = commands.length - 1; i > 0; --i) {
        command = &commands.items[i];
        command->next = row2commands_to_start[command->y1];
        row2commands_to_start[command->y1] = command;
        row2commands_change[command->y1] = true;
        row2just_remove_commands[command->y2] = true;
        row2commands_change[command->y2 + 1] = true;
    }
    for (j = 0; j < GRID_SIZE; ++j) {
        row2just_remove_commands[j] = (
            row2just_remove_commands[j] && ! row2commands_change[j]
        );
    }
}

/* ------------------------------------------------------------------------ */

void ActiveCommands_init(void)
{
    active_commands.length = 0;
    memset(active_commands.items, 0, sizeof(active_commands.items));
}

void ActiveCommands_extend(uint16_t row_index)
{
    Command *command;
    uint16_t i;

    command = row2commands_to_start[row_index];
    while (command) {
        i = active_commands.length;
        while (i && active_commands.items[i - 1] > command) {
            active_commands.items[i] = active_commands.items[i - 1];
            --i;
        }
        active_commands.items[i] = command;
        ++active_commands.length;
        command = command->next;
    }
}

/* ------------------------------------------------------------------------ */

#ifndef __CC65__

void turn_on(uint16_t i, uint16_t j)
{
    for (; i <= j; ++i) row[i] = 1;
}

void turn_off(uint16_t i, uint16_t j)
{
    for (; i <= j; ++i) row[i] = 0;
}

void toggle(uint16_t i, uint16_t j)
{
    for (; i <= j; ++i) row[i] = row[i] ^ 1;
}

void turn_up(uint16_t i, uint16_t j)
{
    for (; i <= j; ++i) row[i] += 1;
}

void turn_double_up(uint16_t i, uint16_t j)
{
    for (; i <= j; ++i) row[i] += 2;
}

void turn_down(uint16_t i, uint16_t j)
{
    for (; i <= j; ++i) {
        if (row[i]) row[i] -= 1;
    }
}

#endif

uint32_t count_lights(CommandFunction *command_functions)
{
    uint16_t row_index, row_result, i, j;
    uint32_t result;
    Command *command;

    result = row_result = 0;
    ActiveCommands_init();
    for (row_index = 0; row_index < GRID_SIZE; ++row_index) {
        #ifdef __CC65__
            printf("%u\n%c", row_index, 145);
        #endif

        if (row2commands_change[row_index]) {
            ActiveCommands_extend(row_index);
            memset(row, 0, sizeof(row));
            for (i = 0, j = 0; i < active_commands.length; ++i) {
                command = active_commands.items[i];
                command_functions[command->opcode](command->x1, command->x2);
                active_commands.items[j] = command;
                if (command->y2 != row_index) {
                    ++j;
                }
            }
            active_commands.length -= i - j;

            row_result = 0;
            for (i = 0; i < GRID_SIZE; ++i) {
                row_result += row[i];
            }
        } else if (row2just_remove_commands[row_index]) {
            for (i = 0, j = 0; i < active_commands.length; ++i) {
                command = active_commands.items[i];
                active_commands.items[j] = command;
                if (command->y2 != row_index) {
                    ++j;
                }
            }
            active_commands.length -= i - j;
        }
        result += row_result;
    }

    return result;
}

int main(void)
{
    clock_t start_time, end_time;
    uint8_t i;
    _Bool ok;
    FILE *file;
    CommandFunction command_functions[][3] = {
        {turn_on, turn_off, toggle},
        {turn_up, turn_down, turn_double_up}
    };

    puts("Reading input...");
    start_time = clock();
    file = fopen("input.txt", "r");
    ok = parse_file(file);
    fclose(file);
    init_row_lookup_tables();
    end_time = clock();
    printf(
        "Parsing took %ld seconds.\n", (end_time - start_time) / CLOCKS_PER_SEC
    );
    if (ok) {
        #ifdef DEBUG
        debug_dump_commands();
        #endif
        for (
            i = 0;
            i < (sizeof(command_functions) / sizeof(command_functions[0]));
            ++i
        ) {
            printf("Counting %u...\n", i);
            start_time = end_time;
            printf("\n%lu\n", count_lights(command_functions[i]));
            end_time = clock();
            printf("(%ld seconds)\n", (end_time - start_time) / CLOCKS_PER_SEC);
        }
    } else {
        printf("Parsing error in line %u.\n", commands.length + 1);
    }

    return !ok;
}