Advent of code 2021: Day 5
 3 minutes read  512 wordsFollowing from my efforts on Day 4 of Advent of Code 2021 I was encouraged to try writing up more of my attempts to teach myself Haskell while having fun trying to solve puzzles.
The problem
The exercise was concerned with drawing lines on a grid and finding intersections:
 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.
The aim was to count the number of points where lines overlap. More on the problem here
Initial thought
So my first thought on how to solve this was going to be
 make a grid
 find the points of each line (only vertical and horizontal lines to start with)
 mark them on the grid
 check the grid to find intersections
I encountered the same issue as the day before: This sounds like a mutable data structure. And if there’s one thing that Haskell doesn’t like (feel free to correct me  I’m only a beginner)  it’s mutability.
Brainwave
Rather than creating a grid, I only really needed to find out the points that get created by each line and then to filter out all the points that only occur a single time.
If I represent each line as a tuple (start, end) of tuples (x, y):


then I can use the following function to create all the horizontal and vertical lines:


so I can create all points on a line:


then finding duplicates becomes easy (assuming coords
is a list of all the lines):


Unpacking this a little bit:
map genline coords
creates a list of list of pointsconcat
merges this into a single long listgroup $ sort points
groups all the same values into listsmap length
then turns this into a list of the lengthsfilter (>1) summary
filters out all elements of the list that are not greater than one (i.e. all the points with no intersections)length
gives me the number of elements  i.e. the number of intersections.
Rest of the solution on GitHub
Conclusion
I found that the solution that I arrived at felt more elegant than creating a grid and trying
to fill it in. Like the day before, the trick here was to step back and think about the problem
before charging in. Incidentally, part two of the puzzle (which introduced 45 degree diagonals)
was easy to solve with this approach as I just needed to change the genline
function to also
create a list of points for diagonals.
If you'd like to find more of my writing, why not follow me on Twitter or Mastodon?