Advent of Code 2019 - Day 3, Part 1
bretthancox
Posted on December 9, 2019
Introduction
Day 3 (posting on day 9...better get ready for day 4 on day 19...) exposed the amount of time since I did math in a meaningful way. My solution is painful, probably because I don't know some fundamental mathematical approach to the problem, but it is what it is. Behold, day 3!
Day 3.1
Day 3 requires that some directions and distances be taken in and processed to produce points of intersection. The input defines two lines that will have 1 or more intersection points. The lines comprise only vertical or horizontal changes in direction.
I handle the input as strings in Clojure. To avoid having to wrap every single part of the input in double-quotes, I wrote the input as follows:
(def day3_line1 (into [] (map #(name %) '[R1001,D890,R317,U322,L481,D597, ;;*snip*
By doing this, I can use the text as provided in the problem and Clojure handles putting the symbols (as it interprets them) into a new vector as strings.
The single apostrophe in front of the symbol vector tells Clojure not to evaluate the content of the vector, just use it. Allowing Clojure to evaluate it will give you some nice long Java errors.
With the input defined, the "logic" needs to be built. Given my approach, I struggle to write "logic" without quoting it.
(ns advent.core
(:gen-class)
(:require [advent.inputs :refer :all]
[clojure.string :as str]))
(defn day3_1_coordinate_vec_builder_x
"I construct the coordinates for horizontal lines"
[operator coordinates next_str]
(vector (operator (get coordinates 0) ;; X
(Integer/parseInt (subs next_str 1)))
(get coordinates 1))) ;; Y
(defn day3_1_coordinate_vec_builder_y
"I construct the coordinates for vertical lines"
[operator coordinates next_str]
(vector (get coordinates 0) ;; X
(operator (get coordinates 1) ;; Y
(Integer/parseInt (subs next_str 1)))))
(defn day3_1_coordinate_builder
"I turn the direction set for each line into coordinates that represent each point the line changes direction"
[strings]
(loop [next_str (first strings)
rest_strings (rest strings)
coordinates [0 0]
vec_of_coords [coordinates]]
(if (= (+ 1 (count strings)) (count vec_of_coords))
vec_of_coords
(cond (str/starts-with? next_str "U") (recur (first rest_strings)
(rest rest_strings)
(day3_1_coordinate_vec_builder_y + coordinates next_str)
(conj vec_of_coords (day3_1_coordinate_vec_builder_y + coordinates next_str)))
(str/starts-with? next_str "D") (recur (first rest_strings)
(rest rest_strings)
(day3_1_coordinate_vec_builder_y - coordinates next_str)
(conj vec_of_coords (day3_1_coordinate_vec_builder_y - coordinates next_str)))
(str/starts-with? next_str "R") (recur (first rest_strings)
(rest rest_strings)
(day3_1_coordinate_vec_builder_x + coordinates next_str)
(conj vec_of_coords (day3_1_coordinate_vec_builder_x + coordinates next_str)))
(str/starts-with? next_str "L") (recur (first rest_strings)
(rest rest_strings)
(day3_1_coordinate_vec_builder_x - coordinates next_str)
(conj vec_of_coords (day3_1_coordinate_vec_builder_x - coordinates next_str)))))))
To avoid writing extra :refer entries for every new input, I switched to :refer :all, thus pulling all inputs in at once.
day3_1_coordinate_builder uses the vector of instructions to build a coordinate set for each line passed to it. U or D indicate a change in the y value of the coordinate and are sent to day3_1_coordinate_vec_builder_y, while R or L indicates a change in x and are sent to day3_1_coordinate_vec_builder_x. The operator changes based on whether the axis being changed is increasing or decreasing. A D decreases y, while a U increases it.
The output is a vector of vectors. The inner vectors are the [x y] coordinates for each direction change, including origin [0 0].
Next, I use a command and control for the majority of the intersection-identifying process:
(defn day3_1_all_intersections_for_both_lines
"I am basically command and control. I walk through each function, passing the result to the next.
Finally merge the intersection points into one vector."
[line_1 line_2]
(let [line_1_coordinates (day3_1_coordinate_builder line_1)
line_2_coordinates (day3_1_coordinate_builder line_2)
line_1_horizontals (day3_1_get_horizontals line_1_coordinates)
line_1_verticals (day3_1_get_verticals line_1_coordinates)
line_2_horizontals (day3_1_get_horizontals line_2_coordinates)
line_2_verticals (day3_1_get_verticals line_2_coordinates)
l1v_intersect_l2h (day3_1_find_intersection_points line_1_verticals line_2_horizontals)
l2v_intersect_l1h (day3_1_find_intersection_points line_2_verticals line_1_horizontals)]
(loop [intersect_main l1v_intersect_l2h
intersect_source l2v_intersect_l1h]
(if (empty? intersect_source)
intersect_main
(recur (into intersect_main intersect_source) (rest intersect_source))))))
This function is basically taking in a number of other function outputs. Since most of my functions work on only half of the data set, this function was necessary to consolidate the results.
The reason for half each time is because I broke each line into sub-lines: horizontal and vertical. This allowed for comparison of line 1 horizontal sub-lines to the line 2 vertical sub-lines and vice versa. Since intersection could only occur between vertical and horizontal sub-lines, this seemed simple.
First, for each line, I extract the key values for each sub-line. Looking at horizontal sub-lines, the y doesn't change for the entire length, so each sub-line is defined by three values x-start, x-end, and y.
Thus each of these functions returns a vector of sub-vectors. Each sub-vector defines a sub-line as: [start end constant].
(defn day3_1_get_horizontals
"I extract the horizontal lines from the coordinate vector. It then produces a three number set for each: [x1 x2 y].
x1 is the start of the line. x2 is the end of the line. y is the constant y-plane. "
[coordinates]
(loop [start (first coordinates)
rest_coords (rest coordinates)
horizontals []]
(if (<= (count rest_coords) 0)
horizontals
(if
(not=
(- (first start) (first (first rest_coords))) 0)
(recur (first rest_coords) (rest rest_coords) (conj horizontals [(first start) (first (first rest_coords)) (second start)]))
(recur (first rest_coords) (rest rest_coords) horizontals)
))))
(defn day3_1_get_verticals
"I extract the vertical lines from the coordinate vector. It then produces a three number set for each: [y1 y2 x].
y1 is the start of the line. y2 is the end of the line. x is the constant x-plane. "
[coordinates]
(loop [start (first coordinates)
rest_coords (rest coordinates)
verticals []]
(if (<= (count rest_coords) 0)
verticals
(if
(not=
(- (second start) (second (first rest_coords))) 0)
(recur (first rest_coords) (rest rest_coords) (conj verticals [(second start) (second (first rest_coords)) (first start)]))
(recur (first rest_coords) (rest rest_coords) verticals)))))
Then, for the two lines, use all vertical sub-lines and check if they intersect with the horizontal sub-lines:
(defn day3_1_find_intersection_points
"For each of the initial lines, I compare the horizontal sub-lines from line A to the vertical sub-lines from line B.
Run again with vertical sub-lines from line A and horizontal sub-lines from line B to get all intersects."
[vert_lines horiz_lines]
(loop [vert_loop vert_lines
horiz_loop horiz_lines ;; bind to a different name so that...
intersections []]
(if (empty? vert_loop)
intersections
(if (empty? horiz_loop) ;; ...we can reuse the original vector as passed to the function even if we empty out the copy
(recur (rest vert_loop) horiz_lines intersections)
(let [vert_coords (first vert_loop)
horiz_coords (first horiz_loop)
vert_x_axis (nth vert_coords 2)
horiz_y_axis (nth horiz_coords 2)
;; A little cheat. The end of a line can have a smaller number than the start
;; and catching this situation with code is painful. So I guarantee that the smallest
;; x or y value is x1 or y1 and the largest is x2 or y2, simplifying subsequent math.
;; Since the direction of the line is irrelevant to determining intersects, this is not a problem.
vert_y1 (if (> (nth vert_coords 0) (nth vert_coords 1)) (nth vert_coords 1) (nth vert_coords 0))
vert_y2 (if (> (nth vert_coords 0) (nth vert_coords 1)) (nth vert_coords 0) (nth vert_coords 1))
horiz_x1 (if (> (nth horiz_coords 0) (nth horiz_coords 1)) (nth horiz_coords 1) (nth horiz_coords 0))
horiz_x2 (if (> (nth horiz_coords 0) (nth horiz_coords 1)) (nth horiz_coords 0) (nth horiz_coords 1))]
(if
(and
(and (> horiz_y_axis vert_y1) (< horiz_y_axis vert_y2)) ;; If horizontal y axis is within the y range of the vertical line being assessed
(and (> vert_x_axis horiz_x1) (< vert_x_axis horiz_x2))) ;; and vertical x axis is within the x range of the horizontal line being assessed
(recur vert_loop (rest horiz_loop) (conj intersections [vert_x_axis horiz_y_axis])) ;; then the lines intersect and we add it to the vector of intersections.
(recur vert_loop (rest horiz_loop) intersections))))))) ;; Otherwise, don't update the intersections and move on.
The key to this is that an intersect means that the x value for a vertical sub-line is within the x range of a horizontal and the y axis for that horizontal sub-line is within the y range of the vertical. If that isn't true, they don't intersect.
To make things somewhat simpler, I also disregard the direction of any sub-line as it doesn't change the intersect. This approach means my > and < checks at the end don't need to be conditional as I'll always be comparing against the largest and smallest values, in that order.
Then back to the day3_1_all_intersections_for_both_lines function, as shown earlier, to do the main command and control and pull the intersection set together for the complete lines.
Lastly, the actual Manhattan distance calculation and invoking it.
Manhattan distance is defined as |(x-origin - x-intersect) + (y-origin - y-intersect)|. Using that calculation, I iterate over the points of intersection and store or replace the smallest resulting value until, at the end, it is returned.
(defn day3_1_manhattan_distance
"I take the vector of intersection points and calculate the Manhattan distance. I then compare
that distance to the last recorded distance and, if smaller, store that distance instead. I return the smallest distance."
[line_1 line_2]
(loop [intersection_points (day3_1_all_intersections_for_both_lines line_1 line_2)
intersect (first intersection_points)
smallest_distance (+ (Math/abs (- 0 (first intersect))) (Math/abs (- 0 (second intersect))))]
(if (empty? intersection_points)
smallest_distance
(recur (rest intersection_points)
(first intersection_points)
(if (< smallest_distance
(+ (Math/abs (- 0 (first intersect))) (Math/abs (- 0 (second intersect)))))
smallest_distance
(+ (Math/abs (- 0 (first intersect))) (Math/abs (- 0 (second intersect)))))))))
(defn -main
(println "Day 3.1 - Manhattan distance:" (day3_1_manhattan_distance day3_line1 day3_line2)))
Testing
I definitely do not do test-driven development. I tried for Day 3.2, but these are my tests for Day 3.1.
I didn't plan on writing this many, but my code was so troublesome that it needed a lot more attention than I had planned.
(deftest day3_1_coord_builder
(testing "Day 3.1 Building coordinates"
(is (= (day3_1_coordinate_builder ["R8","U5","L5","D3"]) [[0 0] [8 0] [8 5] [3 5] [3 2]]))
(is (= (day3_1_coordinate_builder ["U7","R6","D4","L4"]) [[0 0] [0 7] [6 7] [6 3] [2 3]]))
(is (= (day3_1_coordinate_builder ["U7","R6","D4","L4","L5","D4"]) [[0 0] [0 7] [6 7] [6 3] [2 3] [-3 3] [-3 -1]]))
))
(deftest day3_1_horizontal_lines
(testing "Day 3.1 Horizontal line definitions [Xstart Xend Y]"
(is (= (day3_1_get_horizontals [[0 0] [8 0] [8 5] [3 5] [3 2]]) [[0 8 0] [8 3 5]]))
(is (= (day3_1_get_horizontals [[0 0] [0 7] [6 7] [6 3] [2 3]]) [[0 6 7] [6 2 3]]))
(is (= (day3_1_get_horizontals [[0 0] [0 7] [6 7] [6 3] [2 3] [-3 3] [-3 -1]]) [[0 6 7] [6 2 3] [2 -3 3]]))
))
(deftest day3_1_vertical_lines
(testing "Day 3.1 Vertical line definitions [Ystart Yend X]"
(is (= (day3_1_get_verticals [[0 0] [8 0] [8 5] [3 5] [3 2]]) [[0 5 8] [5 2 3]]))
(is (= (day3_1_get_verticals [[0 0] [0 7] [6 7] [6 3] [2 3]]) [[0 7 0] [7 3 6]]))
(is (= (day3_1_get_verticals [[0 0] [0 7] [6 7] [6 3] [2 3] [-3 3] [-3 -1]]) [[0 7 0] [7 3 6] [3 -1 -3]]))))
(deftest day3_1_intersections
(testing "Day 3.1 find the intersection coordinates"
(is (= (day3_1_find_intersection_points [[0 7 0] [7 3 6]] [[0 8 0] [8 3 5]]) [[6 5]]))
(is (= (day3_1_find_intersection_points [[0 5 8] [5 2 3]] [[0 6 7] [6 2 3]]) [[3 3]]))
))
(deftest day3_1_manhattan_test
(testing "Day 3.1 Manhattan distance"
(is (= (day3_1_manhattan_distance
(into [] (map #(name %) '[R75,D30,R83,U83,L12,D49,R71,U7,L72]))
(into [] (map #(name %) '[U62,R66,U55,R34,D71,R55,D58,R83])))
159))
(is (= (day3_1_manhattan_distance
(into [] (map #(name %) '[R8,U5,L5,D3]))
(into [] (map #(name %) '[U7,R6,D4,L4])))
6))
))
Extra
I was getting a little fed up with constantly running all preceding days when running day 3. As such, I updated my main function to take command line arguments and run the days specified by the user:
(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:" (day3_2_loop_intersects day3_line1 day3_line2)))
:else (println "Day not completed yet"))
(recur (rest days) (first (rest days)))))))
Now, typing lein run 1 3 will result in only the code for Day 1 and Day 3 running.
Posted on December 9, 2019
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
