Advent of Code 2015 - Day 6 - Probably a Fire Hazard

On the sixth day of Advent of Code 2015 we are tasked with trying to win the holiday house decorating contest - by designing the best light sequence 💡.

Part 1

We are first told that the lights are configured in a 1000x1000 grid and that based on instructions that Santa has provided we should operate each light in different ways. Like before, we start off by parsing the provided instructions (actions and grid position ranges) into a form we can enact on going forward.

type Light = { row: number; col: number };
type Range = { from: Light; to: Light };
enum Action {
  On,
  Off,
  Toggle,
}
type Instruction = [Action, Range];

const parseInstructions = (input: string): Instruction[] =>
  input.split('\n').map(line => {
    const [, action, fr, fc, tr, tc] = line.match(
      /(.+) (\d+),(\d+) through (\d+),(\d+)/
    );
    return [
      action === 'turn on'
        ? Action.On
        : action === 'turn off'
        ? Action.Off
        : Action.Toggle,
      {
        from: { row: toInt(fr), col: toInt(fc) },
        to: { row: toInt(tr), col: toInt(tc) },
      },
    ];
  });

We initially define a couple of types to help map the domain problem into our code solution. Using a Regular Expression we are able to translate every instruction line into the given action and grid position range (from, to). I have opted for using a ternary operator in such a way that it can provide three choices, I would usually shy away from doing this in professional code due to readability and possible errors.

With the instructions now parsed we can look into solving the first part of today’s problem. For this, we will be using a two-dimensional array of which I have decided to define a generic function to use for creation in both parts. Providing the size and default value allows us to build a type-safe array which the client can then use.

const create2DArray = <T>(rows: number, cols: number, defaultValue: T): T[][] =>
  Array.from(Array(rows), () => Array(cols).fill(defaultValue));

Based on the three actions (On, Off and Toggle), we are required to iterate through the instructions and manipulate the specified lights (based on a given range) using a double for loop like so:

const part1 = (input: string): number => {
  const lights = create2DArray(1000, 1000, false);

  for (const [action, { from, to }] of parseInstructions(input)) {
    for (let row = from.row; row <= to.row; row++) {
      for (let col = from.col; col <= to.col; col++) {
        lights[row][col] =
          action === Action.On
            ? true
            : action === Action.Off
            ? false
            : !lights[row][col];
      }
    }
  }

  return lights.flat().filter(Boolean).length;
};

Once we have followed the instructions we can flatten the two-dimensional array into a single-dimension and tally up all the lights that are still lit to reach the desired answer 🌟.

Alternatively, we could replace the two-dimensional array with a more performant UInt8Array one-dimensional array. In doing so we lose the the ability to express the light state as a Boolean now and instead map these states to 1 or 0 accordingly.

const part1 = (input: string): number => {
  const lights = new Uint8Array(1000 * 1000);

  for (const [action, { from, to }] of parseInstructions(input)) {
    for (let row = from.row; row <= to.row; row++) {
      for (let col = from.col; col <= to.col; col++) {
        lights[1000 * row + col] =
          action === Action.On
            ? 1
            : action === Action.Off
            ? 0
            : 1 - lights[1000 * row + col];
      }
    }
  }

  return lights.reduce(sum);
};

Accessing the desired row and column is now achieved using a small formula 1000 * row + col. To toggle the light state we use the 1 - n trick to flip the state between 1 and 0. Finally, we can sum up all the lights that are on with a single reduction, thanks to the values we are now storing (integers) and being a one-dimensional array.

Part 2

In the case of part two we are required to again iterate through the provided instructions, but instead of just turning the light on or off we now control their brightness. As such, we now wish to store integer values in our two-dimensional array - thanks to the help of Generics and the supplied default value this is made type-safe.

const part2 = (input: string): number => {
  const lights = create2DArray(1000, 1000, 0);

  for (const [action, { from, to }] of parseInstructions(input)) {
    for (let row = from.row; row <= to.row; row++) {
      for (let col = from.col; col <= to.col; col++) {
        lights[row][col] = Math.max(
          0,
          lights[row][col] +
            (action === Action.On ? 1 : action === Action.Off ? -1 : 2)
        );
      }
    }
  }

  return lights.flat().reduce(sum);
};

Following a very similiar form as to part one the only code that has really changed is the action we wish to enact based on the given instructions light range. Having iterated through the provided instructions we can again flatten the grid and return the light brightness sum to reach our desired answer 🌟.

Following suite with part one’s alternative implementation, we can again opt to use a Uint8Array instead and use a small math formula to locate a given row and column.

const part2 = (input: string): number => {
  const lights = new Uint8Array(1000 * 1000);

  for (const [action, { from, to }] of parseInstructions(input)) {
    for (let row = from.row; row <= to.row; row++) {
      for (let col = from.col; col <= to.col; col++) {
        lights[1000 * row + col] = Math.max(
          0,
          lights[1000 * row + col] +
            (action === Action.On ? 1 : action === Action.Off ? -1 : 2)
        );
      }
    }
  }

  return lights.reduce(sum);
};

The benefits to using this approach are for performance as the interpreter is able to know of what type and size the array should be allocated up-front. In the case of the two-dimensional array, we produce this array somewhat dynamically; and the engine is not able to be sure of what exact type we will be storing throughout its lifetime (as JavaScript arrays are heterogeneous).

Upon review, due to how similiar both part one and two were, we could have possibly distilled down the logic for iterating through an instruction set and applying a given action into a more generalised higher-ordered function. In doing so it could have abstracted away how we stored the lighting grid and how we produced the desired resulting sum. As the callee we could then just supply different actions (possibly of the type (Light) => Light) to form the bases of each parts concrete solution.