Given a collection of line segments, we are looking for points in a 2-D space where at least two horizontal or vertical segments overlap.

```
Seg = ((ℕ × ℕ), (ℕ × ℕ))
to_set : Seg → Set ℕ²
```

We can extract the vertical or horizontal segments of a set by simply comparing coordinates:

```
vertical : Seg → Bool
vertical ((x₁, _), (x₂, _)) = x₁ == x₂
horizontal : Seg → Bool
horizontal ((_, y₁), (_, y₂)) = y₁ == y₂
```

Generating the set of points contained by a vertical or horizontal line segment is slightly convoluted, since the pairs describing the segment may not be ordered:

```
points : Seg → [(ℕ × ℕ)]
point p = if vertical p
then points_v p
else if horizontal p
then points_h p
else error "diagonal segment"
points_v ((x, y₁), (_, y₂)) =
let { maxy = max y₁ y₂ } in
unfold (λ y → y == maxy)
(λ y → (x, y))
(+ 1)
(min y₁ y₂)
```

Using Haskell-style list comprehensions, *points_v* can be written
more compactly as:

```
points_v ((x, y₁), (_, y₂)) =
[ (x, y) | y <- [min y₁ y₂ .. max y₁ y₂]]
```

*points_h* is analogous.

The overlapping points of two segments is then the intersection of the sets they denote. Given a list of segments, the set of all overlapping points is then the union of all such intersections.

```
overlaps : Set ℕ² → [Set ℕ²] → Set ℕ²
n
μ(overlaps s [t₁, …, tₙ]) = U (μ(s) ∩ μ(tᵢ))
i=1
all_overlaps : Set (Set ℕ²) → Set ℕ²
μ(all_overlaps ss) = U { μ(overlaps s ss) : s ∈ ss }
```

The value of *all_overlaps* on the given set of line segments is the
solution. Even taking into account the commutativity of intersection,
though, this is expensive to compute: Θ(n²) in the number of sets.
We can use arithmetic to quickly determine whether two segments
intersect, of course, but we still have to do the same number of
comparisons.

As is common with AoC, it seems that the author has an imperative solution in mind. In fact, the puzzle’s example is described in a way that suggests such an approach, namely drawing all the segments on a 2-D canvas large enough to include all of their points, then traversing the canvas to find the overlaps.

What is the meaning of this approach? We can see this algorithm as counting the number of points that occur more than once in the disjoint union of all of the segments. If S is this disjoint union, then the set T of overlap points is given by

```
T = { p : (p, s) ∈ S ∧ (p, t) ∈ S, s ≠ t }
```

The solution to the puzzle is then |T|. Given some function

```
occurs : (ℕ × ℕ) → ℕ
```

which gives the number of times a point occurs in the disjoint union
of all segments, we can also compute the answer by counting the number
of points *p* in the union of segments for which *occurs p* > 1. We
need not traverse the disjoint union each time we evaluate *occurs p*;
we can accumulate a point-to-number-of-occurrences dictionary in a
single traversal of the disjoint union. (Many fans of Perl-flavored
imperative programming will recognize their favorite Swiss Army
chainsaw in this approach.)

We can easily obtain a list of all points in a list of segments:

```
all_points : [Seg] → [(ℕ × ℕ)]
all_points = concat ∘ list points
```

From here, it’s easy to construct a dictionary. Many structural options will be available, but here’s an example using the brain-dead-simple association list:

```
make_dict : [(ℕ × ℕ)] → [((ℕ × ℕ), ℕ)]
make_dict = foldr (λ (x, y) ps →
case assoc (x, y) ps of
Nothing -> ((x, y), 1) ∷ ps
Just k -> update (x, y) (k + 1) ps)
[]
-- Standard alist operations.
assoc : α → [(α × β)] → Maybe β
update : α → β → [(α × β)] → [(α × β)]
point_dict : [Seg] → [((ℕ × ℕ), ℕ)]
point_dict =
make_dict ∘ all_points ∘ filter (vertical ∨ horizontal)
```

This is identical to part 1, except that we now handle diagonal segments. Fortunately, these are guaranteed to be “at exactly 45°”. Or, rather, at 45°, 135°, 225°, or 315°. (Recall that the Y axis increases downward.)

The point-set-generating function *points* has to be extended to
handle two classes of diagonal segments: those with symmetrically
increasing/decreasing X and Y coordinates (i.e. segments at 45° or at
225°), and those with inversely increasing/decreasing coordinates
(i.e. those at 135° or 315°).

```
points : Seg → [(ℕ × ℕ)]
point p = if vertical p
then points_v p
else if horizontal p
then points_h p
else points_d p
points_d : Seg → [(ℕ × ℕ)]
points_d ((x₁, y₁), (x₂, y₂)) =
if x₁ < x₂
if y₁ < y₂
then sym_inc ((x₁, y₁), (x₂, y₂)) -- 45°
else dec_y ((x₁, y₁), (x₂, y₂)) -- 315°
else
if y₁ < y₂
then dec_x ((x₁, y₁), (x₂, y₂)) -- 135°
else sym_inc ((x₂, y₂), (x₁, y₁)) -- 225°
```

The *sym_inc*, *dec_x*, and *dec_y* functions handle the various
coordinate cases. They’re straightforward list-building functions
similar to *points_v* above.