AoC 2015 Puzzle 3

2015 Puzzle 3: Perfectly Spherical Houses in a Vacuum

Puzzle, part 1

Santa is delivering presents to an infinite two-dimensional grid of houses.

He begins by delivering a present to the house at his starting location, and then an elf at the North Pole calls him via radio and tells him where to move next. Moves are always exactly one house to the north (^), south (v), east (>), or west (<). After each move, he delivers another present to the house at his new location.

However, the elf back at the north pole has had a little too much eggnog, and so his directions are a little off, and Santa ends up visiting some houses more than once. How many houses receive at least one present?

Solution, part 1

In order to solve this puzzle a unbounded 2 dimensional array is needed. This is something Java does not have. The way to get something like it is to create a class that encapsulate coordinates and then use that in a list.

This allows the introduction of Project Lombok which greatly simplifies the use of boilerplate code. Using Lombok it is no longer required to write getter and setter methods as well as toString(), equals and hashCode.

A simple class with 2 int fields can be used. Annotating it with @AllArgsConstructor will generate a constructor with both fields. The @ToString will create a toString method that prints both fields. The @EqualsAndHashCode annotation ensures that objects are compared on their contents and not on the object data, which means that the Position objects can be used in lists and maps and "it will just work".

@AllArgsConstructor
@ToString
@EqualsAndHashCode
class Position {
    int x, y;
}

The input for the puzzle is a series of steps. To process these steps performSteps will read each instruction and determine the new coordinates within the 2 dimensional array.

The new coordinate is retrieved from the existing coordinates, if it existed its value is increased, else it is set to 1. This allows the tracking of number of gifts.

The resulting 2 dimensional array is returned (a list with Position objects).

private Map<Position, Integer> performSteps(List<String> steps) {
    Map<Position, Integer> locations = new HashMap<>();

    int x = 0, y = 0;

    for (String step : steps) {
        switch (step) {
        case "<":
            --x;
            break;
        case ">":
            ++x;
            break;
        case "^":
            ++y;
            break;
        case "v":
            --y;
            break;
        }

        Position p = new Position(x, y);
        Integer currentValue = locations.get(p);
        locations.put(p, (currentValue == null ? 1 : currentValue++));
    }

    return locations;
}

To start the puzzle, the input is split, so that performSteps can take its input. A global location map is created, where the 1st position, the starting position, is added. Once performSteps returns, the values are added to this global locations map using putAll.

The answer is the size of the locations map.

@Override
public String part1(List<String> input) {
    List<String> tokens = new ArrayList<>(Arrays.asList(input.get(0).split("")));

    Map<Position, Integer> locations = new HashMap<>();
    locations.put(new Position(0, 0), 1);

    locations.putAll(performSteps(tokens));

    return String.valueOf(locations.size());
}

Puzzle, part 2

The next year, to speed up the process, Santa creates a robot version of himself, Robo-Santa, to deliver presents with him.

Santa and Robo-Santa start at the same location (delivering two presents to the same starting house), then take turns moving based on instructions from the elf, who is eggnoggedly reading from the same script as the previous year.

This year, how many houses receive at least one present?

Solution, part 2

The logic for part 2 remains the same. The performSteps method does not need to change, however we need to give it 2 sets of instructions, the one for Santa and the one for the robot.

A really neat lambda trick can be used to split the steps for both of them. First IntStream.range(0, tokens.size()) will generate a sequence of integers ranging from 0 to the size of the input tokens. Then filter(n -> n % 2 == 0) is used to only allow the even numbers to continue. Using the even numbers the call to mapToObj(tokens::get) transforms the integer value to the value from the tokens list, which is then transformed to a list using collect(Collectors.toList()).

For the robot instructions the only change is to only let the odd numbers pass through the filter function.

The result of both performSteps calls are added to the global locations map to return the answer to the puzzle.

@Override
public String part2(List<String> input) {
    List<String> tokens = new ArrayList<>(Arrays.asList(input.get(0).split("")));

    Map<Position, Integer> locations = new HashMap<>();
    locations.put(new Position(0, 0), 1);

    List<String> santaInstructions = IntStream.range(0, tokens.size())
        .filter(n -> n % 2 == 0)
        .mapToObj(tokens::get)
        .collect(Collectors.toList());

    List<String> roboInstructions = IntStream.range(0, tokens.size())
        .filter(n -> n % 2 != 0)
        .mapToObj(tokens::get)
        .collect(Collectors.toList());

    locations.putAll(performSteps(santaInstructions));
    locations.putAll(performSteps(roboInstructions));

    return String.valueOf(locations.size());
}

Conclusion

Today several very neat lambda tricks were used to solve the puzzle as well as the boilerplate-saving goodness of Project Lombok.

Puzzle 4 will be published Thursday the 9th of January.