AoC 2015 Puzzle 6

2015 Puzzle 6: Probably a Fire Hazard

Part 1

Because your neighbors keep defeating you in the holiday house decorating contest year after year, you've decided to deploy one million lights in a 1000x1000 grid.

Furthermore, because you've been especially nice this year, Santa has mailed you instructions on how to display the ideal lighting configuration.

Lights in your grid are numbered from 0 to 999 in each direction; the lights at each corner are at 0,0, 0,999, 999,999, and 999,0. The instructions include whether to turn on, turn off, or toggle various inclusive ranges given as coordinate pairs. Each coordinate pair represents opposite corners of a rectangle, inclusive; a coordinate pair like 0,0 through 2,2 therefore refers to 9 lights in a 3x3 square. The lights all start turned off.

To defeat your neighbors this year, all you have to do is set up your lights by doing the instructions Santa sent you in order.

Solution

From the description it is clear an 2 dimensional array is required to layout the field of lights. Each light will be changed by running a set of instructions over it.

The instructions will be can be processed in a variety of ways. For this puzzle a class is created to encapsulate the instruction. It will take the written string and turn it into a class that can be applied to the grid.

The first thing to do is to encapsulate our actual instructions in an Enum. With this we can reference the enum value instead of relying on strings. Using this technique the code is shielded from typo problems once the instruction is parsed.

enum OPERATION {
    TOGGLE, TURN_ON, TURN_OFF
}

The next step is to write the class that will encapsulate the instruction. This is a simple POJO annotated with the Project Lombok @ToString annotation. This will make it possible to print out the objects in a readable way.

The only special functions take the string representation of the coordinates and parses them into integers.

@ToString
class Instruction {
    OPERATION op;
    int startX;
    int startY;
    int endX;
    int endY;

    void setStart(String[] pos) {
        startX = Integer.valueOf(pos[0]);
        startY = Integer.valueOf(pos[1]);
    }

    void setEnd(String[] pos) {
        endX = Integer.valueOf(pos[0]);
        endY = Integer.valueOf(pos[1]);
    }

}

Now that the Instruction class is written the code to create one from the input string is next. The function parseInstruction() is passed a single line from our input file. The line is split on a space, breaking it up into individual pieces.

If the string starts with the term turn it is skipped over. Instead of looking for the instructions turn on, turn off and toggle, the code can look for on, off and toggle. Skipping over the turn word allows the code to be uniform for all 3 cases.

Instruction parseInstruction(String instruction) {
    Instruction step = new Instruction();
    String[] parts = instruction.split(" ");

    int pos = 0;
    if (parts[pos].equals("turn"))
        pos++;

The uniformity allows for a switch statement on the part of the string that holds the actual instruction. As switch statements can be performed on strings the enum value will be applied to the operation in the Instruction object.

switch (parts[pos]) {
case "on":
    step.op = OPERATION.TURN_ON;
    break;
case "off":
    step.op = OPERATION.TURN_OFF;
    break;
case "toggle":
    step.op = OPERATION.TOGGLE;
    break;
}

The only thing left to do in parsing the instruction is to set the coordinates. The pairs are connected with a ,, so another split is required to set them.

    pos++;

    String[] start = parts[pos].split(",");
    step.setStart(start);
    pos += 2;

    String[] end = parts[pos].split(",");
    step.setEnd(end);

    return step;
}

At this point the Instruction is parsed from the input file and a grid is populated with lights. Combining them will modify the grid based on the instruction.

By looping from the Instruction value of startX to endX, so each step on the horizontal axis (the x-axis), the first dimension of the lights array is visited. Within that loop startY to endY ensures each vertical point is visited as well. At each point in the rectangle the operation is evaluated in a switch.

If the operation is on, the value in the grid is set to 1. If it is off it will be set to 0. In order to toggle a tertiary comparison is done on the current value of point. If it is 1, it becomes 0, and vice versa.

void applyInstruction(Instruction step, int[][] grid) {
    for (int x = step.startX; x <= step.endX; x++) {
        for (int y = step.startY; y <= step.endY; y++) {
            switch (step.op) {
            case TOGGLE:
                grid[x][y] = (grid[x][y] == 1 ? 0 : 1);
                break;
            case TURN_ON:
                grid[x][y] = 1;
                break;
            case TURN_OFF:
                grid[x][y] = 0;
                break;
            }
        }
    }
}

Once all the Instructions are followed the puzzle calls for the number of lights that are on to be counted. This can be done by simply summing the value of the grid by looping over the x and y positions and adding the value of the point.

int sumLights(int[][] grid) {
    int on = 0;
    for (int x = 0; x < grid.length; x++) {
        for (int y = 0; y < grid[x].length; y++) {
            on += grid[x][y];
        }
    }
    return on;
}

The main driver of part 1 constructs a grid of 1000 by 1000 int values. For every string in the input list it is passed to parseInstruction() which is immediately passed into applyInstruction() to modify the grid. The result of sumLights is passed as the answer to the puzzle.

@Override
public String part1(List<String> input) {

    int[][] grid = new int[1000][1000];

    for (String s : input) {
        applyInstruction(parseInstruction(s), grid);
    }

    return String.valueOf(sumLights(grid));
}

Part 2

You just finish implementing your winning light pattern when you realize you mistranslated Santa's message from Ancient Nordic Elvish.

The light grid you bought actually has individual brightness controls; each light can have a brightness of zero or more. The lights all start at zero.

The phrase turn on actually means that you should increase the brightness of those lights by 1.

The phrase turn off actually means that you should decrease the brightness of those lights by 1, to a minimum of zero.

The phrase toggle actually means that you should increase the brightness of those lights by 2.

What is the total brightness of all lights combined after following Santa's instructions?

Solution

The solution for part 1 does not allow for the inclusion of this new brightness criteria. So a copy of applyInstruction() is needed to implement the new conditions.

The same logic applies as in part 1, but now the brightness is increased when toggle is encountered. on will increase the value and off will decrease, but no further then 0.

void applyInstructionPart2(Instruction step, int[][] grid) {
    for (int x = step.startX; x <= step.endX; x++) {
        for (int y = step.startY; y <= step.endY; y++) {
            switch (step.op) {
            case TOGGLE:
                grid[x][y] += 2;
                break;
            case TURN_ON:
                grid[x][y]++;
                break;
            case TURN_OFF:
                grid[x][y]--;
                if (grid[x][y] < 0)
                    grid[x][y] = 0;
                break;
            }
        }
    }
}

The actual driver for part 2 does not change in comparison to part 1, with the exception of the applyInstructionPart2() call instead of its part 1 counterpart.

@Override
public String part2(List<String> input) {
    int[][] grid = new int[1000][1000];

    for (String s : input) {
        applyInstructionPart2(parseInstruction(s), grid);
    }

    return String.valueOf(sumLights(grid));
}