Advent of Code 2015 Day 3: Perfectly Spherical Houses in a Vacuum

Input is a series of characters which tell Santa which way to move (one position each time). After each move, Santa delivers a present.

Part 1

The first question is how to map out the world in which Santa moves. Since he can only move one unit at a time, this can be represented by a Cartesian coordinate system, i.e. a pair of numbers (x, y). The starting point will be (0, 0), and as Santa can move in any direction, either or both coordinates can be negative.

First of all, we need a data structure which represents a pair of coordinates:

typedef struct coordinates {
    int x;
    int y;
} coordinates_t;

Conveniently, we can use this structure to represent both fixed coordinates and a delta / offset for existing coordinates.

Converting each character to a coordinates delta can be accomplished with an enum and switch statement:

enum move_symbol {
    NORTH = '^',
    EAST = '>',
    SOUTH = 'v',
    WEST = '<'
};

coordinates_t *parse_delta(const enum move_symbol symbol) {
    coordinates_t *delta = calloc(1, sizeof(coordinates_t));

    switch (symbol) {
        case NORTH:
            delta->y = 1;
            break;
        case EAST:
            delta->x = 1;
            break;
        case SOUTH:
            delta->y = -1;
            break;
        case WEST:
            delta->x = -1;
            break;
    }

    return delta;
}

Applying a delta involves adding it to coordinates:

coordinates_t *apply_delta(const coordinates_t * const start, const coordinates_t * const delta) {
    coordinates_t *end = calloc(1, sizeof(coordinates_t));
    end->x = start->x + delta->x;
    end->y = start->y + delta->y;

    return end;
}

Now we have to consider how we keep track of the unique coordinates Santa has visited. There are at least three ways we could do this.

Hash map. Using the coordinates as the key and the number of visits as the value. If the key does not exist, add it and set the visits to 1, otherwise increment the number of visits by 1. This effectively consolidates multiple visits to the same coordinates as we parse the data. However, we would need to implement a hash map in C.

Array. Index as the move number and value is the coordinates. The array would need to be allocated on the heap because its value would not be known at compile time, but we know that the number of elements is equal to the number of characters in the input - plus 1 for the starting position.

Grid. We could build a grid (two dimensional array) to represent the entire space in which Santa can move, and increment the visit count each time Santa moves to those coordinates. However, we don’t know the initial size of the grid, and negative indexes also pose a challenge.

Perhaps the simplest solution is to use dynamic arrays, appending an element each time we visit a new set of coordinates.

aoc_slice_t *all_visits(const char * const input) {
    size_t input_length = strlen(input);
    aoc_slice_t *visits = aoc_slice_new(input_length);

    coordinates_t *start = calloc(1, sizeof(coordinates_t));
    start->x = 0;
    start->y = 0;

    // We always visit the starting coordinates
    aoc_slice_append(visits, start);

    coordinates_t *current_position = start;

    for (size_t i = 0; i < input_length; i++) {
        current_position = apply_delta(current_position, parse_delta(input[i]));
        aoc_slice_append(visits, current_position);
    }

    return visits;
}

This gets us all the visits, however we only want the unique visits. To achieve this, we can create a ‘unique’ slice from the ‘all visits’ slice, only copying coordinates that do not already exist. For this we need a function to compare coordinates for equality, and one to create a ‘unique’ slice.

bool coordinates_equal(const coordinates_t * const a, const coordinates_t * const b) {
    return a->x == b->x && a->y == b->y;
}

aoc_slice_t *unique_visits(aoc_slice_t *all_visits) {
    // Unique visits will be at most the same size as all visits,
    // so we can allocate capacity in advance
    aoc_slice_t *unique = aoc_slice_new(all_visits->capacity);

    for (size_t av = 0; av < all_visits->length; av++) {
        bool is_unique = true;

        for (size_t uv = 0; uv < unique->length && is_unique; uv++) {
            if (coordinates_equal(all_visits->data[av], unique->data[uv])) {
                is_unique = false;
            }
        }

        if (is_unique) {
            aoc_slice_append(unique, all_visits->data[av]);
        }
    }

    return unique;
}

Finally, we get the unique visits for a given input and return the length.

size_t santa_house_visits(const char * const input) {
    aoc_slice_t *unique = unique_visits(all_visits(input));

    return unique->length;
}

Part 2

This is straightforward, as we are now alternating our steps through the input, but still using the same mechanism to keep track of visited coordinates. All we have to do this:

1. Split the input in two, based on every alternating character.
2. Calculate all visits for each input.
3. Concatenate the visits into a single slice.
4. Filter the combined slice to get unique visits.
5. Return the length of the unique combined slice.

This is slightly more code than part 1, but not by much.

size_t santa_robot_house_visits(const char * const input) {
    // Split the input in two, alternating characters
    size_t input_length = strlen(input);
    size_t sub_input_length = input_length / 2;
    char *santa_input = calloc(sub_input_length, sizeof(char));
    char *robot_input = calloc(sub_input_length, sizeof(char));

    for (
        size_t input_index = 0, output_index = 0;
        input_index < input_length;
        input_index += 2, output_index++
    ) {
        santa_input[output_index] = input[input_index];
        robot_input[output_index] = input[input_index + 1];
    }

    // Technically don't need the NUL terminator since we used calloc
    santa_input[sub_input_length] = '\0';
    robot_input[sub_input_length] = '\0';

    aoc_slice_t *unique_combined_visits = unique_visits(
        aoc_slice_concat(
            all_visits(santa_input),
            all_visits(robot_input)
        )
    );

    return unique_combined_visits->length;
}