Introduction

I don't know if the problems are getting harder, or my brain just struggled with the structure of this one, but it feels like I have double the functions necessary to achieve the goal.

Nevertheless, Day 3 is finished! This second part highlighted some brittleness in my approach to part 1. My approach for the individual sub-lines (producing [x-start x-end y] or [y-start y-end x]) meant that I couldn't work with the outputs of later functions in the chain. I had to go back to the coordinate-producing function.
Given more time, this feels like a refactoring candidate, but time waits for no Santa!

Day 3.2

Challenge is to work out the intersection point closest to origin as determined by the sum of the distance it occurs from origin when following each of the two input lines. Instead of working out relative position on the grid (Manhattan distance), now it's about following the directions for the lines and counting the steps taken for each, summing the two distances.

After doing some reading, I found that if you know the coordinates of a single point (i.e. an intersection point), you can use the cross product formula to check if that point is on the same plane: Cross product on Wikipedia

Essentially, if the cross product for a sub-line and an intersection point is 0, then the point exists on that line.

Sub-line:    a-----------------------b

Coordinates: a (xa, ya)   b (xb, yb)   i (xi, yi)   Where i is the intersection point

Cross product: |((yi - ya)(xb - xa)) - ((xi - xa)(yb - ya))|

What does that do for us?
If you have an input line with the following coordinates [[0 0] [9 0] [9 3] [5 3]] and an intersection point of [9 2], then to determine distance you're not measuring the length of the entire line. The line to measure instead ends at the intersection point: [[0 0] [9 0] [9 2]]
The distance in this simple, one line example is thus 9 + 2 = 11
Cross product tells us between which two points the intersection occurs. If cross product is 0, the point of intersection is on that sub-line.

With that in mind I started with a cross product function:

(defn crossproduct
  "I determine if an intersection point is on the line defined by point1 and point2"
  [point1 point2 testpoint]
  (let [part1 (- (second testpoint) (second point1))
        part2 (- (first point2) (first point1))
        part3 (- (first testpoint) (first point1))
        part4 (- (second point2) (second point1))
        crossprd (- (* part1 part2) (* part3 part4))]
    (if (= crossprd 0)
      true
      false)))

Next, a function that takes in a single intersect point and the coordinate set for a single line, producing a shorter coordinate set that terminates in the point of intersection. Using crossproduct, if the point of intersection occurs on a sub-line, use the intersect coordinate as the end of that particular sub-line, thus going from [xa xb] or [ya yb] to [xa xi] or [ya yi]

(defn day3_2_crossproduct_output
  [intersection line_coordinates]
  (loop [line_coordinates line_coordinates
         line_start (first line_coordinates)
         line_end (second line_coordinates)
         coordinates_to_intersect [line_start]
         is_intersected (crossproduct line_start line_end intersection)]
    (if (true? is_intersected)
      (conj coordinates_to_intersect intersection)
      (recur 
       (rest line_coordinates) 
       line_end
       (second (rest line_coordinates)) 
       (conj coordinates_to_intersect line_end)
       (crossproduct line_end (second (rest line_coordinates)) intersection)))))

Then, before the command and control function, I know that the distance is the combined distance from input line 1 and input line 2, so a summing function will be needed:

(defn sum_the_distance 
  [coords_to_intersect]
(loop [coords_to_intersect coords_to_intersect
       point1 (first coords_to_intersect)
       point2 (second coords_to_intersect)
       total 0]
  (if (= (count coords_to_intersect) 1)
    total
    (recur 
     (rest coords_to_intersect)
     point2
     (second (rest coords_to_intersect))
     (+ total (reduce + (map #(Math/abs %) (map - point2 point1))))))))

The input is the coordinates generated by crossproduct_output - i.e. a coordinate set terminating in a point of intersection.
The last line looks complicated, but is just doing the following:

Subtract both values in point1 from point2. Using map allows a function to apply to all contents of collections, so this step would work like so: [8 5] - [4 2] == [4 3]. This is not possible with a simple -
Next, map that result to Math/abs ensuring all values are positive. Even negative coordinate changes add to the distance traveled.
Reduce the resulting positive pair using + to produce the length of the sub-line. Using the earlier example (reduce + [4 3]) == 7
Add that to the total distance for the next loop.

Finally, the command and control. This function takes in the input lines, produces the coordinates for each, finds the points of intersection, and builds a vector of distances.
On each loop, the function takes the next point of intersection and the coordinates of the two input lines, and uses the functions discussed above to produce a total distance for each input line. Lastly, it adds the total distance for each line, producing the combined distance, before adding that value to the distances vector.
Once all points of intersection have been iterated over, the return value is the first value of the sorted vector of distances. The default sort behavior on integers is to sort them in ascending order, making the first value the smallest:

(defn day3_2_loop_intersects
  [line1 line2]
  (let [line1_coords (day3_1_coordinate_builder line1)
        line2_coords (day3_1_coordinate_builder line2)
        intersections (day3_1_all_intersections_for_both_lines line1 line2)
        distances []]
    (loop [intersections intersections
           line1_intersection_coords (day3_2_crossproduct_output (first intersections) line1_coords)
           line2_intersection_coords (day3_2_crossproduct_output (first intersections) line2_coords)
           distances distances]
      (println (count intersections) (count distances))
      (if (= 1 (count intersections))
        (first (sort distances))
        (recur 
         (rest intersections)
         (day3_2_crossproduct_output (first (rest intersections)) line1_coords)
         (day3_2_crossproduct_output (first (rest intersections)) line2_coords)
         (conj distances (+ (sum_the_distance line1_intersection_coords) (sum_the_distance line2_intersection_coords))))))))

(defn -main
  "I call the functions for the Advent of Code on the basis of which day(s) are added as arguments to the command line call"
  [& days]
  (loop [days days
         day (first days)]
    (if (empty? days)
      nil
      (do
        (cond (= day "1") (do
                            (println "Day 1.1 - Module masses only:" (day1_1 day1_masses))
                            (println "Day 1.2 - Fuel for the fuel:" (reduce + (map day1_2 day1_masses))))
              (= day "2") (do 
                            (println "Day 2.1 - Intcode output: " (day2_1 (day2_prep day2_intcode 12 2)))
                            (println "Day 2.2 - Noun/verb:" (day2_2_result (day2_2_nounverb day2_intcode 99 19690720))))
              (= day "3") (do 
                            (println "Day 3.1 - Manhattan distance:" (day3_1_manhattan_distance day3_line1 day3_line2))
                            (println "Day 3.2 - Shortest route to intersect:" (day3_2_loop_intersects day3_line1 day3_line2)))
              :else (println "Day not completed yet"))
        (recur (rest days) (first (rest days))))))
        )

And with a quick lein run 3 I have my day 3 results, earning two more gold stars!

Testing

Testing was simpler in part 2, mainly because I found a less convoluted way to achieve the goal than in part 1. Only note for next round of testing is to use def to define the inputs, rather than writing (into [] (map #(name %...*snip* every time I needed an input. Readability would be a lot better.

(deftest day3_2_crossproduct_test
  (testing "Finding the set of coordinates that terminate in an intersection"
  (is (= (day3_2_crossproduct_output 
          (second 
           (day3_1_all_intersections_for_both_lines 
            (into [] (map #(name %) '[R8,U5,L5,D3]))
            (into [] (map #(name %) '[U7,R6,D4,L4]))))
          (day3_1_coordinate_builder (into [] (map #(name %) '[R8,U5,L5,D3]))))
         [[0 0] [8 0] [8 5] [6 5]]
         ))))

(deftest sum_the_distance_test
  (testing "Summing the distance"
    (is (= (sum_the_distance [[0 0] [8 0] [8 5] [6 5]]) 15))
    (is (= (sum_the_distance [[0 0] [0 7] [6 7] [6 5]]) 15))))

(deftest day3_2_loop_intersects_test
  (testing "day3_2_loop_intersects"
    (is (= (day3_2_loop_intersects
            (into [] (map #(name %) '[R75,D30,R83,U83,L12,D49,R71,U7,L72]))
            (into [] (map #(name %) '[U62,R66,U55,R34,D71,R55,D58,R83])))
           610)
        (= (day3_2_loop_intersects
            (into [] (map #(name %) '[R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51]))
            (into [] (map #(name %) '[U98,R91,D20,R16,D67,R40,U7,R15,U6,R7])))
           410))))

Blog

Advent of Code 2019 - Day 3, Part 2

bretthancox

Introduction

Day 3.2

Testing

Join Our Newsletter. No Spam, Only the good stuff.

Related