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.

Note about the problem

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 Points (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 Points, 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 Locations.
  3. Extract the Points from the Locations, since the Direction isn't important once the moves are complete.
  4. Create conceptual lines by creating pairs of individual Points.
  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.[0] |> 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.

But what about testing?

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.

See you next time!