The challenge

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.


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.


To avoid the most dangerous areas, you need to determine the number of points where at least two lines overlap. […]

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

You can read the challenge more in depth, here.

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.


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

Full solution

auto input = stdin.byLineCopy()
    .map!`a.splitter(" -> ").map!"a.splitter(',').map!(to!long).array".array`.array;
auto xy!(l => [max(l[0][0], l[1][0]), max(l[0][1],l[1][1])])!maxElement.array;
size_t[][] a = new size_t[(xy[0]+1)*(xy[1]+1)].evenChunks(xy[1]+1).array;
foreach(p; input) {
    if(p[0][0] == p[1][0])
        if(p[0][1] > p[1][1]) foreach(e; p[1][1]..p[0][1]+1) ++a[e][p[0][0]];
        else foreach(e; p[0][1]..p[1][1]+1) ++a[e][p[0][0]];
    else if(p[0][1] == p[1][1])
        if(p[1][0] > p[0][0]) foreach(e; p[0][0]..p[1][0]+1) ++a[p[0][1]][e];
        else foreach(e; p[1][0]..p[0][0]+1) ++a[p[0][1]][e];
    else if(1) // change this value to 0 for first part
        auto x1 = p[0][0], x2 = p[1][0], y1 = p[0][1], y2 = p[1][1];
        if(x1 > x2) { swap(x1,x2); swap(y1, y2); }
        foreach(e; x1..x2+1)
            if(y2>y1) ++a[y1+(e-x1)][e];
            else ++a[y1-(e-x1)][e];
// construct the map
//!(l =>!`!string == "0" ? "." :!string`.join).each!writeln;
a.join.filter!"a > 1".count.writeln;