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;

We also need to represent a house. Technically we could implement this as part of the coordinates_t struct, because every pair of coordinates contains a house (presumably), however we will stick as closely to the puzzle text as possible as this makes reasoning about it easier. All we need to know for a house in part 1 is its coordinates and the number of visits.

typedef struct house {
    coordinates_t coordinates;
    int visits;
}

Now we have to consider how we keep track of where Santa has visited. There are at least four 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