ZNProjects

Software is beautiful again!

AOC 2016 - Day 1, Part 2

If you just want to jump into the code, the code for Day 1 is on GitHub.

The problem

Part 2 adds a small twist to the problem. Instead of just finding an end-point, you have to find the first block that you visit twice.

This is not as simple as checking against the end points of each move. Rather each intermediate block that you visit is a candidate for being the final answer.

If you have not finished Day 1, Part 1 yet, the AOC website will not show you the Part 2 text. If you need to do Day 1, Part 1, please see my post on that subject.

Do the lines intersect?

There are a few ways to solve this problem.

1. Keep a list of all `Point`s (as sets of 2D Cartesian coordinates). Then, every time you move, check if you are passing over an already visited block.
2. Store the lines that represent the moves you have made so far, in order. Then, when making a new move, check whether the new 'line of movement' intersects with any of the previous lines. If there is an intersection, find the point of intersection.

I first thought of implementing solution #1, but found solution #2 more interesting because I do not currently know how to calculate whether two lines intersect or what that intersection point is.

So, I started out by reading about lines and intersections. I started with various "game" / graphical algorithms because I assumed that this is a problem that game developers encounter often. Like most people (I imagine), I first ended up at Wikipedia. This is a great article that is heavy on theory and light on implementation details. A lot of the information, not only on Wikipedia but on various sites, involves knowing the equation of the line. I had the end-points, but did not readily have the slope-intercept form of the lines. After quite a bit of searching, I ended up on Martin Thoma's article, How to check if two line segments intersect.

I highly recommend reading this article if you haven't seen it before. He has an excellent explanation of line-line intersection. I actually implemented most of Martin's code (in F#) and it is quite solid. But then, I started reading Gregory Stein's comment on the same page regarding cross products of vectors. I really liked Gregory's idea, mainly due to the succinctness of the code. So, I also translated Gregory's code to F#. In the end, I went with Gregory's algorithm.

Here is what Gregory's code came out as:

``let doLinesIntersect2 l1 l2 =  let A = fst l1  let B = snd l1  let O = fst l2  let M = snd l2  let v1 = {x = A.x - O.x; y = A.y - O.y}  let v2 = {x = B.x - O.x; y = B.y - O.y}  let v3 = {x = M.x - O.x; y = M.y - O.y}  let v4 = {x = A.x - M.x; y = A.y - M.y}  let v5 = {x = B.x - M.x; y = B.y - M.y}  let v4 = {x = v4.x + v5.x; y = v4.y + v5.y}  let v5 = {x = v1.x + v2.x; y = v1.y + v2.y}  let dotProduct = v4.x * v5.x + v4.y * v5.y  if dotProduct > 0 then false  else (    let crossV1V3 = v1.x*v3.y - v1.y*v3.x    let crossV3V2 = v3.x*v2.y - v3.y*v2.x    (crossV1V3 < 0) = (crossV3V2 < 0)  )``

I can safely confirm that this code does work. This function has signature `Point * Point -> Point * Point -> bool`. Recall from Day 1 that a `Point` and a `Location` are defined as:

``type Point = {  x : int  y : int}type Location = {  dir : Direction  pt : Point}``

Initially, my x-y coordinates were saved directly in the `Location` record. However, once I decided on a solution for Part 2, I actually went back, changed the data types, and refactored the Part 1 code so that it would continue working.

Where do they intersect?

Once I knew that two lines intersect, the next job was to find the intersection point. I looked at a number of sites and ended up adapting the code from Intersection of lines in 2D.

``let intersectionPoint l1 l2 =  let x1 = (fst l1).x  let y1 = (fst l1).y  let x2 = (snd l1).x  let y2 = (snd l1).y  let x3 = (fst l2).x  let y3 = (fst l2).y  let x4 = (snd l2).x  let y4 = (snd l2).y  let denom = (x1-x2)*(y3-y4)-(y1-y2)*(x3-x4)  {x = ((x1*y2-y1*x2)*(x3-x4)-(x1-x2)*(x3*y4-y3*x4))/denom;  y = ((x1*y2-y1*x2)*(y3-y4)-(y1-y2)*(x3*y4-y3*x4))/denom}``

This function's signature is `Point * Point -> Point * Point -> Point`. It takes 2 lines, each represented as a pair of `Point`s, and returns the intersection `Point`.

Putting it all together

I wanted to re-use, as much as possible, the code I had already written for Day 1, Part 1. Specifically, I wanted to re-use the `move` mechanic. To achieve this goal, I wrote my final function per the following spec:

1. Parse the instructions
2. Perform the moves while preserving all intermediate `Location`s.
3. Extract the `Point`s from the `Location`s, since the `Direction` isn't important once the moves are complete.
4. Create conceptual lines by creating pairs of individual `Point`s.
5. Iterate over the list of Lines (which are really just `Point` tuples) to find an intersection, but with a built-in short-circuit. Once we find an intersection point, we don't want to update it again in the future.
6. Finally, pull out the intersection point (if any) and calculate the distance from the `startPt` (which is at `(0,0)`).

The things I love about F# is that I was able to translate this spec almost line-for-line into code. I called this function `dupFinder` because I figured that we are trying to find the first `Point` that is a duplicate in the route we have traveled thus far:

``let dupFinder strList =  Regex.Matches (strList, @"[LR]\d+")  |> Seq.cast  |> Seq.scan    (fun oldloc (instr : System.Text.RegularExpressions.Match) ->      move        (instr.Value. |> toTurn)        (instr.Value.Substring 1 |> int)        oldloc    )    startLoc  |> Seq.map (fun x -> x.pt)  // Define lines  |> Seq.pairwise  |> Seq.fold    (fun accum elt ->      if snd accum = None then        let s = fst accum        if Seq.exists (doLinesIntersect2 elt) s then          let ip = Seq.find (doLinesIntersect2 elt) s          s, intersectionPoint ip elt |> Some        else s @ [elt], None      else accum    )    ([], None)  |> snd  |> fun x ->    match x with    | None -> failwith "No intersection"    | Some y -> y  |> distance startPt``

And this is it. I invoked the `dupFinder` function with the input string (same string as Part 1) and got the correct answer.

The answer you get with this code is `141`, which is, in fact, correct.

If you want to see the code for Day 1 (both parts), please head over to GitHub.

As you may have noticed, I barely have any testing in my code. In the beginning, I debugged by code using a combination of code reading (gotta love static typing!) and the `tee` function to print debugging information during execution.
If you are not aware of `tee`, I highly recommend reading Extending F# Pipelines With A Tee Function and Scott Wlaschin's Railway oriented programming.
Here is the code for `tee`:
``let tee f x =  f x |> ignore  x``
This handy little function allows you to inject arbitrary commands (such as `printfn` or `logger.Log`) into the middle of a pipe chain without disturbing the rest of the code. It takes a function and an argument, executes the function, ignores the result (if any), and passes the original argument forward. Obviously, this wouldn't work so well if the function somehow mutated the argument. Luckily, F# makes it at least a little annoying to write functions that mutate values, and I almost always only use `tee` to do mid-pipe log entries / debug output.