As I'm particularly busy these days, I was able to solve the problems of day 5, 6 and 7 but I'm able to write up solutions and considerations only today. Let's start with the day 5!

Problem — Part 1

You come across a field of hydrothermal vents on the ocean floor! These vents constantly produce large, opaque clouds, so it would be best to avoid them if possible.

They tend to form in lines; the submarine helpfully produces a list of nearby lines of vents (your puzzle input) for you to review. For example:

0,9 -> 5,9
8,0 -> 0,8
9,4 -> 3,4
2,2 -> 2,1
7,0 -> 7,4
6,4 -> 2,0
0,9 -> 2,9
3,4 -> 1,4
0,0 -> 8,8
5,5 -> 8,2

Each line of vents is given as a line segment in the format x1,y1 -> x2,y2 where x1,y1 are the coordinates of one end the line segment and x2,y2 are the coordinates of the other end. These line segments include the points at both ends. In other words:

• An entry like 1,1 -> 1,3 covers points 1,1, 1,2, and 1,3.

• An entry like 9,7 -> 7,7 covers points 9,7, 8,7, and 7,7.

For now, only consider horizontal and vertical lines: lines where either x1 = x2 or y1 = y2.

So, the horizontal and vertical lines from the above list would produce the following diagram:

.......1..
..1....1..
..1....1..
.......1..
.112111211
..........
..........
..........
..........
222111....

In this diagram, the top left corner is 0,0 and the bottom right corner is 9,9. Each position is shown as the number of lines which cover that point or . if no line covers that point. The top-left pair of 1s, for example, comes from 2,2 -> 2,1; the very bottom row is formed by the overlapping lines 0,9 -> 5,9 and 0,9 -> 2,9.

To avoid the most dangerous areas, you need to determine the number of points where at least two lines overlap. In the above example, this is anywhere in the diagram with a 2 or larger - a total of 5 points.

Consider only horizontal and vertical lines. At how many points do at least two lines overlap?

Your puzzle answer was 5608.

Solution — Part 1

The first thing we want to do for sure, is to parse correctly the coordinates of the starting and ending lines of the vents. To do so we can:

// Parse the vent positions from the input
const pairs = lines.map((line) => {
  const [a, b] = line.split("->").map((s) => s.trim());
  const [x1, y1] = a.split(",").map((s) => parseInt(s));
  const [x2, y2] = b.split(",").map((s) => parseInt(s));
  return [x1, y1, x2, y2];
});

Now, we have all the information stored in an array in the [x1, y1, x2, y2] form. Since we have (for now) the constraint of the orthogonality, we need a function to filter out only those that have both the x value and the y value different from each other in the pair.

/**
 * Filter out the pairs not orthogonal to each other
 * @param {array} pairs Array of [x1, y1, x2, y2]
 * @returns {array} Only the orthogonal pairs
 */
function filterOrthogonal(pairs) {
  const [x1, y1, x2, y2] = pairs;
  return x1 === x2 || y1 === y2;
}

Now, we can glue the things together in the main() function

function main() {
  const orthogonal = pairs.filter(filterOrthogonal);
  // 1000? Magic number
  const mat = Matrix.fromDimensions(1000, 1000, 0);

  for (const ventLines of orthogonal) {
    const [x1, y1, x2, y2] = ventLines;
    if (x1 === x2) {
      for (let i = Math.min(y1, y2); i <= Math.max(y1, y2); i++) {
        mat.set(x1, i, mat.get(x1, i) + 1);
      }
    } else if (y1 === y2) {
      for (let i = Math.min(x1, x2); i <= Math.max(x1, x2); i++) {
        mat.set(i, y1, mat.get(i, y1) + 1);
      }
    }
  }

  return mat.toArray().filter((cell) => cell >= 2).length;
}
console.log(main());

For every couple remaining (and therefore orthogonal), I loop on the x or y axis and add a +1 to the value of the cell in the matrix. When I have inserted all the vent lines information, I can filter out the cells with value >=2 and count how many of them are there.

Possible (space) optimization

An optimization for that problem I think could be using a dictionary instead of the matrix. This is because in JavaScript I can anyway allocate dynamically allocate space, so it's not required to create a 1000x1000 matrix which could be half or even more empty.

With a dictionary I would create something like:

const dict = {
	"0,2": 2,
// ...
}

And store only the positions that have actual values. Once done with that, I would iterate over the dictionary keys to find the fields with value >=2. This would not benefit the time complexity, but just the space one.

Problem — Part 2

Unfortunately, considering only horizontal and vertical lines doesn't give you the full picture; you need to also consider diagonal lines.

Because of the limits of the hydrothermal vent mapping system, the lines in your list will only ever be horizontal, vertical, or a diagonal line at exactly 45 degrees. In other words:

• An entry like 1,1 -> 3,3 covers points 1,1, 2,2, and 3,3.

• An entry like 9,7 -> 7,9 covers points 9,7, 8,8, and 7,9.

Considering all lines from the above example would now produce the following diagram:

1.1....11.
.111...2..
..2.1.111.
...1.2.2..
.112313211
...1.2....
..1...1...
.1.....1..
1.......1.
222111....

You still need to determine the number of points where at least two lines overlap. In the above example, this is still anywhere in the diagram with a 2 or larger - now a total of 12 points.

Consider all of the lines. At how many points do at least two lines overlap?

Your puzzle answer was 20299.

Solution — Part 2

The only thing that actually change with respect to the first part, is the requirement of the orthogonality which is not there anymore. We can actually remove the function that filtered out the pairs and add a new condition in the loop to consider only the 45 degrees points.

To know if it is at 45 degrees, we can check if the cell distance is the same from both the x axis and the y axis. The code would look like this

function main() {
  const mat = Matrix.fromDimensions(1000, 1000, 0);

  for (const ventLines of pairs) {
    const [x1, y1, x2, y2] = ventLines;
    if (x1 === x2) {
      for (let i = Math.min(y1, y2); i <= Math.max(y1, y2); i++) {
        mat.set(x1, i, mat.get(x1, i) + 1);
      }
    } else if (y1 === y2) {
      for (let i = Math.min(x1, x2); i <= Math.max(x1, x2); i++) {
        mat.set(i, y1, mat.get(i, y1) + 1);
      }
    } else {
      for (let i = Math.min(x1, x2); i <= Math.max(x1, x2); i++) {
        for (let j = Math.min(y1, y2); j <= Math.max(y1, y2); j++) {
          if (Math.abs(i - x1) === Math.abs(j - y1)) {
            mat.set(i, j, mat.get(i, j) + 1);
          }
        }
      }
    }
  }
  return mat.toArray().filter((cell) => cell >= 2).length;
}

console.log(main());

After finishing this part as well, I worked more on the utility function and the Matrix class in particular in order to make it more useful for the problems.