Day 6 - Lights out

Advent of Code 2015

Adrien Foucart

2026-03-05

[Back to index]

Puzzle: https://adventofcode.com/2015/day/6

My solution: https://codeberg.org/adfoucart/aocode15/src/branch/main/src/day6.c

A 2D problem again. I usually like these, let’s see how it goes.

We have a grid of 1000x1000 lights. And we have a set of instructions to turn on, off, or toggle rectangles within this grid. The instructions shown as example are:

turn on 0,0 through 999,999
toggle 0,0 through 999,0
turn off 499,499 through 500,500

Which would do:

Let’s make that our first test, before we really start.

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

#define TEST_INPUT "turn on 0,0 through 999,999\ntoggle 0,0 through 999,0\nturn off 499,499 through 500,500\n"

int compute_number_of_lights(char* instructions){
    return 0;
}

void run_test(){
    assert(compute_number_of_lights(TEST_INPUT)==998996, "test input works");
}

int main(){
    run_test();
}

Update the makefile, run. Everything compiles, the test fails, we can get started.

Data structure

We’ll probably need a “rectangle” type. This may be useful later, so we’ll put it directly in our coords module. It will use a pair of coord_t for the top-left and bottom-right corners.

// coords.h
typedef struct {
    coord_t* tl;
    coord_t* br;
} rectangle_t;

rectangle_t* rectangle_create(int x0, int y0, int x1, int y1);
void rectangle_destroy(rectangle_t* rec);

And:

// coords.c
rectangle_t* rectangle_create(int x0, int y0, int x1, int y1){
    rectangle_t* rec = malloc(sizeof(rectangle_t));

    rec->tl = coord_create(x0, y0);
    rec->br = coord_create(x1, y1);

    return rec;
}

void rectangle_destroy(rectangle_t* rec){
    coord_destroy(rec->tl);
    coord_destroy(rec->br);

    free(rec);
}

Add a test in test_coords.c:

bool test_rectangle_create(){
    rectangle_t* rec = rectangle_create(1, 2, 3, 4);
    bool success = (rec->tl != NULL && rec->br != NULL && 
                    rec->tl->x == 1 && rec->tl->y == 2 &&
                    rec->br->x == 3 && rec->br->y == 4);
    rectangle_destroy(rec);

    return success;
}

It passes, we’re good. Now what can we do with it?

Naïve approach

I often find that, with Advent of Code puzzles, using a naïve approach for the first part is useful. It often works, and you often notice the limitations of the naïve approach while you’re implementing it, which helps better understand the problem. So what would the naïve approach be:

Grid set-up

We need a grid, and a method for setting the value of an element in grid:

typedef struct {
    int cols;
    int rows;
    bool** grid;
} grid_t;

grid_t* grid_create(int cols, int rows){
    grid_t* g = malloc(sizeof(grid_t));
    g->cols = cols;
    g->rows = rows;
    g->grid = malloc(sizeof(bool*)*g->rows);

    for (int i=0; i < g->rows; i++){
        g->grid[i] = malloc(sizeof(bool)*g->cols);
        for (int j=0; j < g->cols; j++){
            g->grid[i][j] = false;
        }
    }
    return g;
}

void grid_destroy(grid_t* grid){
    for (int i=0; i < grid->rows; i++){
        free(grid->grid[i]);
    }
    free(grid->grid);
    free(grid);
}

bool grid_set(grid_t* grid, coord_t* coord, bool value){
    if (coord->x < 0 || coord->x >= grid->cols || coord->y < 0 || coord->y >= grid->rows)
        return false;
    
    grid->grid[coord->y][coord->x] = value;
    return true;
}

Make tests:

bool test_grid_create(){
    grid_t* grid = grid_create(10, 20);

    bool success = (grid->rows == 20 && grid->cols == 10);

    grid_destroy(grid);
    return success;
}

bool test_grid_set(){
    grid_t* grid = grid_create(10, 20);
    if (!grid_set(grid, coord_create(3, 5), true))
        return false;
    
    if (grid_set(grid, coord_create(-1, 10), true))
        return false;

    if (grid_set(grid, coord_create(10, 5), true))
        return false;

    bool success = (grid->grid[5][3] && !grid->grid[0][0]);

    grid_destroy(grid);
    return success;
}

Both pass. Now we make the turn_on, turn_off and toggle methods:

bool grid_turn_on_cell(grid_t* grid, coord_t* coord){
    return grid_set(grid, coord, true);
}

bool grid_turn_off_cell(grid_t* grid, coord_t* coord){
    return grid_set(grid, coord, false);
}

bool grid_toggle_cell(grid_t* grid, coord_t* coord){
    if (coord->x < 0 || coord->x >= grid->cols || coord->y < 0 || coord->y >= grid->rows)
        return false;
    
    grid->grid[coord->y][coord->x] = !grid->grid[coord->y][coord->x];

    return true;
}

And the test, which passes:

bool test_grid_methods(){
    grid_t* grid = grid_create(10, 20);
    
    if (!grid_turn_on_cell(grid, coord_create(3, 5)))
        return false;
    
    if (!grid->grid[5][3])
        return false;

    if (!grid_turn_off_cell(grid, coord_create(3, 5)))
        return false;
    
    if (grid->grid[5][3])
        return false;

    if (!grid_toggle_cell(grid, coord_create(3, 5)))
        return false;

    if (!grid->grid[5][3])
        return false;
    
    grid_destroy(grid);
    return true;
}

I will put the grid definition and grid_set methods into their own grid.c file, they may be useful later. And the related tests in a test_grid.c file of course. The turn_on, turn_off and toggle methods seem more puzzle-specific, so I’ll leave them here.

Parsing the instructions

Here is our day6.c file so far:

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

#define TEST_INPUT "turn on 0,0 through 999,999\ntoggle 0,0 through 999,0\nturn off 499,499 through 500,500\n"

bool grid_turn_on_cell(grid_t* grid, coord_t* coord){
    return grid_set(grid, coord, true);
}

bool grid_turn_off_cell(grid_t* grid, coord_t* coord){
    return grid_set(grid, coord, false);
}

bool grid_toggle_cell(grid_t* grid, coord_t* coord){
    if (coord->x < 0 || coord->x >= grid->cols || coord->y < 0 || coord->y >= grid->rows)
        return false;
    
    grid->grid[coord->y][coord->x] = !grid->grid[coord->y][coord->x];

    return true;
}

int compute_number_of_lights(char* instructions){
    return 0;
}

bool test_grid_methods(){
    grid_t* grid = grid_create(10, 20);
    
    if (!grid_turn_on_cell(grid, coord_create(3, 5)))
        return false;
    
    if (!grid->grid[5][3])
        return false;

    if (!grid_turn_off_cell(grid, coord_create(3, 5)))
        return false;
    
    if (grid->grid[5][3])
        return false;

    if (!grid_toggle_cell(grid, coord_create(3, 5)))
        return false;

    if (!grid->grid[5][3])
        return false;
    
    grid_destroy(grid);
    return true;
}

void run_test(){
    assert(test_grid_methods(), "grid toggle, turn on and turn off are working");
    assert(compute_number_of_lights(TEST_INPUT)==998996, "test input works");
}

int main(){
    run_test();
}

We still havent touched the inputs. We need to:

From each line in the input, I would like to get an instruction, which contains the method to use, and the rectangle with the coordinates.

Something like this:

#define TURN_OFF 0
#define TURN_ON 1
#define TOGGLE 2

typedef struct {
    int method // TURN_OFF, TURN_ON or TOGGLE;
    rectangle_t* rectangle;
} instruction_t;

Now we start parsing the instructions, using our test input first:

int compute_number_of_lights(char* instructions){
    str_list_t* instr_list = parse_strings(instructions, '\n');
    printf("Number of instructions: %d\n", instr_list->n);
    for (int i=0; i < instr_list->n; i++){
        printf("%s\n", instr_list->str_list[i]);
    }
    return 0;
}
// ...
int main(){
    int lights = compute_number_of_lights(TEST_INPUT);
    printf("%d lights are on.\n");
}

It crashes in parse_strings? I thought that part was working well… I usually run it on input read from a file, does that make a difference that I’m not aware of?

int main(){
    char *instructions = freadall(INPUT_FILE);
    int lights = compute_number_of_lights(instructions);
    printf("%d lights are on.\n");
}

Yes, that works. I guess the #define doesn’t give me a null-terminated string. Let’s add an intermediary step:

char instructions[] = TEST_INPUT;
int lights = compute_number_of_lights(instructions);

And change it as well in the test:

char instructions[] = TEST_INPUT;
assert(compute_number_of_lights(instructions)==998996, "test input works");

Good, now it runs.

Number of instructions: 4
turn on 0,0 through 999,999
toggle 0,0 through 999,0
turn off 499,499 through 500,500

Four instructions, one of which is the empty line. We can use strstr to find the method names:

int get_method(char* str){
    char* turn_on = strstr(str, "turn on");
    if (turn_on != NULL)
        return TURN_ON;

    char* turn_off = strstr(str, "turn off");
    if (turn_off != NULL)
        return TURN_OFF;

    char* toggle = strstr(str, "toggle");
    if (toggle != NULL)
        return TOGGLE;

    return -1;
}

instruction_t* parse_instruction(char* str){
    instruction_t* instruction = malloc(sizeof(instruction_t));
    instruction->method = get_method(str);

    if (instruction->method == -1)
        return NULL;
    
    return instruction;
}

And in compute_number_of_lights:

// ...
for (int i=0; i < instr_list->n; i++){
    instruction_t* instruction = parse_instruction(instr_list->str_list[i]);
    if (instruction == NULL)
        continue;
    printf("Method: %d\n", instruction->method);
}

Works fine. Now how do we get the coordinates? This is a bit more tricky, but I think this should work:

After a bit of fiddling with the offsets, I get:

instruction_t* parse_instruction(char* str){
    // ...
    char *first_coord_start = str + offset;
    char *first_coord_end = strstr(str, " through");
    size_t first_coord_str_size = sizeof(char)*(first_coord_end-first_coord_start+1);
    char *first_coords_str = malloc(first_coord_str_size);
    memcpy(first_coords_str, first_coord_start, first_coord_str_size-1);
    first_coords_str[first_coord_str_size-1] = '\0';
    
    char *second_coord_start = first_coord_end + strlen(" through ");
    char *second_coord_end = str + strlen(str);
    size_t second_coord_str_size = sizeof(char)*(second_coord_end-second_coord_start+1);
    char *second_coords_str = malloc(second_coord_str_size);
    memcpy(second_coords_str, second_coord_start, second_coord_str_size-1);
    second_coords_str[second_coord_str_size-1] = '\0';

    printf("Coords: %s -> %s\n", first_coords_str, second_coords_str);
    // ...
}

Which gives me the right string segments, which I’ll still need to convert to a rectangle_t. First parsing into a int_list_t, since we have that handy in our parser:

    // ...
    int_list_t* int_list_first = parse_ints(first_coords_str, ',');
    int_list_t* int_list_second = parse_ints(second_coords_str, ',');
    // ...

Then we can create the rectangle, free the intermediate variable that we no longer need, and return the completed instruction.

instruction_t* parse_instruction(char* str){
    // ...
    instruction->rectangle = rectangle_create(int_list_first->int_list[0], 
                                              int_list_first->int_list[1], 
                                              int_list_second->int_list[0], 
                                              int_list_second->int_list[1]);
    
    free(first_coords_str);
    free(second_coords_str);
    free(int_list_first);
    free(int_list_second);

    return instruction;
}

Quick check in compute_number_of_lights: I get everything I need in the instructions. Now we just need a way to apply an instruction to the grid.

First attempt: create a coord_t, move it around the rectangle, and apply the method to each cell along the way.

void apply_instruction(grid_t* grid, instruction_t* instruction){
    coord_t* cell = coord_create(-1, -1);
    for (cell->y=instruction->rectangle->tl->y; cell->y <= instruction->rectangle->br->y; cell->y++){
        for (cell->x=instruction->rectangle->tl->x; cell->x <= instruction->rectangle->br->x; cell->x++){
            if (instruction->method == TURN_ON)
                grid_turn_on_cell(grid, cell);
            else if (instruction->method == TURN_OFF)
                grid_turn_off_cell(grid, cell);
            else
                grid_toggle_cell(grid, cell);
        }
    }
    coord_destroy(cell);
}

Complete the compute_number_of_lights method to use it.

int compute_number_of_lights(char* instructions){
    grid_t* grid = grid_create(1000, 1000);
    str_list_t* instr_list = parse_strings(instructions, '\n');
    printf("Number of instructions: %d\n", instr_list->n);
    for (int i=0; i < instr_list->n; i++){
        printf("%s\n", instr_list->str_list[i]);
        instruction_t* instruction = parse_instruction(instr_list->str_list[i]);
        if (instruction == NULL)
            continue;
        apply_instruction(grid, instruction);
    }
    int n = grid_count(grid);
    grid_destroy(grid);
    return n;
}

We had to add a grid_count method as well along the way in grid.c, to get the number of lights at the end.

int grid_count(grid_t* grid){
    int n = 0;
    for (int i=0; i < grid->rows; i++){
        for (int j=0; j < grid->cols; j++){
            if (grid->grid[i][j])
                n++;
        }
    }
    return n;
}

Running the code on the test input works! Now we try on the real input.

int main(){
    char *instructions = freadall(INPUT_FILE);
    int lights = compute_number_of_lights(instructions);
    printf("%d lights are on.\n", lights);
}

Roll drums… it works! Another star for me! ⭐

I think that’s enough for today. Part two will be for another time.