DEV Community


Posted on

Advent of code 2021 - day 5

This challenge gives us a list of start & end co-ordinates and asks us to count the intersections. Looking at the input, it seems that all the co-ordinates are less than 1000. For part 1, we are ignoring co-ordinates which aren't horizontal or vertical.

My strategy is to map each start & end co-ordinate into a set of points. So (1,1) -> (1,3) gets transformed into list containing (1,1), (1,2), (1,3). I will then map that list of list of co-ordinates into a Map of co-ordinates and a count. In type signatures:

type Coord = [number, number]
type Line = [Coord, Coord]

toCoords:: Line -> List Coord
countIntersections:: List Coord -> Map (Coord, number)
Enter fullscreen mode Exit fullscreen mode

Edit: I spent a lot of time trying to write a range function and went down a generator function rabbithole. I also goofed up trying to make the countIntersection function work with a Set instead of realising later that what i really needed was a Map.

Edit 2: So exploding out each line into an array of Coords is not good for the computer. Even though the above approach works for the example, the input is simply too large. My next approach is to fold over the input array so that the JS GC can get rid the exploded array for each line.

Edit 3: I suspect that the export declare const upsertAt: <K>(E: Eq<K>) => <A>(k: K, a: A) => (m: Map<K, A>) => Map<K, A>
function is causing a bit of grief with performance. I think that the process of making this a pure function involves taking in a map, making an edit and then recreating the entire map which is causing a severe slow down.

Edit 4: I give up using a non-standard key requiring an Eq instance to figure out the difference between the keys. I'm going to stringify the coord and use that as the key.

-- Part 2
Part 2 asks us to take into account lines which aren't horizontal or vertical. This is a fairly easy addition.

Latest comments (0)