I think this puzzle was about as frustrating as actually untangling a mess of wires, so that’s fun!
Now that I’m caught up, I want to try to provide some more details on how I came to my solution.
Puzzle 1
Given 2 wires, find the collision point closest to the origin.
Right off the bat, I set off parsing the input. Wires are set up as a list of
movements, where U is up, D is down, L is left, and R is right. A string
such as "R75,D30,R83,U83,L12,D49,R71,U7,L72" will become a list of points:
[
{145, 11},
{217, 11},
{217, 4},
{146, 4},
{146, 53},
{158, 53},
{158, -30},
{75, -30},
{75, 0},
{0, 0}
]
Note that the wire is built backwards. This is simply due to it being easier in Elixir to prepend to lists than append. The code is below.
defmodule AdventOfCode.Y2019.Wire do
def build(wire, coords \\ [{0, 0}])
def build([], coords), do: coords
def build([h | t], coords) do
coords = find_coord(h, coords)
build(t, coords)
end
defp find_coord("U" <> u, [{x, y} | _] = coords) do
u = String.to_integer(u)
[{x, y + u} | coords]
end
defp find_coord("D" <> d, [{x, y} | _] = coords) do
d = String.to_integer(d)
[{x, y - d} | coords]
end
defp find_coord("L" <> l, [{x, y} | _] = coords) do
l = String.to_integer(l)
[{x - l, y} | coords]
end
defp find_coord("R" <> r, [{x, y} | _] = coords) do
r = String.to_integer(r)
[{x + r, y} | coords]
end
end
It’s not often I am able to pattern match with string concatenation, but I was
able to here. This is another recursive implementation, which has coords as an
accumulator, building up the list of points as we go. [h | t] in Elixir
pattern matches on the first element of a list, and the rest (the head and
tail of the list). build takes the list of coordinates so far and the next step
in the list, and passes it off to find_coord, which matches on the direction
of the step and the last point in the list. Then, find_coord will add the
right amount to the last point to the new point (if the step is Up, add the
amount to the y axis, and so on), prepending it to the list with that same
[h | t] style. This builds up the wire, but backwards!
Now that I have a wire’s list of points, I need to take two and find any
collision points. Ugh, I remember a collision point problem from last year that
was just so annoying. First, I need to create a list of lines out of my
wires. Enum.chunk_every is handy here. It takes a list, the number of items in
each chunk, and the number of steps in each chunk. :discard will discard the
final chunk if there isn’t the full number of items in the final chunk.
Enum.chunk_every(wire, 2, 1, :discard)
Now, my wire is a list of pairs of points:
[
[{145, 11}, {217, 11}],
[{217, 11}, {217, 4}],
[{217, 4}, {146, 4}],
[{146, 4}, {146, 53}],
[{146, 53}, {158, 53}],
[{158, 53}, {158, -30}],
[{158, -30}, {75, -30}],
[{75, -30}, {75, 0}],
[{75, 0}, {0, 0}]
]
Because these wires are straight lines in either the x- or y-direction,
collision computing isn’t quite as scary. Given 2 lines, check if one’s x
or y point is within the other:
defp collide?([{x1_min, y1_min}, {x1_max, y1_max}], [{x2_min, y2_min}, {x2_max, y2_max}]) do
x =
if x1_min == x1_max do
x1_min >= min(x2_min, x2_max) and x1_min <= max(x2_min, x2_max)
else
x2_min >= min(x1_min, x1_max) and x2_min <= max(x1_min, x1_max)
end
y =
if y1_min == y1_max do
y1_min >= min(y2_min, y2_max) and y1_min <= max(y2_min, y2_max)
else
y2_min >= min(y1_min, y1_max) and y2_min <= max(y1_min, y1_max)
end
x and y
end
These points aren’t ordered, so I have to make sure that I’m comparing against the smallest and largest points. It only took me, oh, 30 minutes after I initially wrote my short quick version (taken from last year) to realize that.
Once I know two lines collide, I can find the point they collide. It’s a small
extension on the above, returning the actual x and y that are between the
others. I think I could combine the two and eliminate a step here, but it was
getting pretty late when I was working on this, and no one writes good code
tired.
defp collision_points([{x1_min, y1_min}, {x1_max, y1_max}], [{x2_min, y2_min}, {x2_max, y2_max}]) do
x =
if x1_min == x1_max and x1_min >= min(x2_min, x2_max) and x1_min <= max(x2_min, x2_max) do
x1_min
else
x2_min
end
y =
if y1_min == y1_max and y1_min >= min(y2_min, y2_max) and y1_min <= max(y2_min, y2_max) do
y1_min
else
y2_min
end
{x, y}
end
After that, the rest is easy! Take the list of collision points, and find the one with the smallest Manhattan distance.
import AdventOfCode
alias AdventOfCode.Y2019.Wire
aoc 2019, 3 do
def p1() do
input_stream()
|> Stream.map(&String.split(&1, ","))
|> Stream.map(&Wire.build/1)
|> Enum.to_list()
|> find_collisions()
|> Enum.filter(fn p -> p != {0, 0} end)
|> Enum.map(fn {x, y} -> abs(x) + abs(y) end)
|> Enum.min()
end
defp find_collisions([w1, w2]) do
w1 = Enum.chunk_every(w1, 2, 1, :discard)
w2 = Enum.chunk_every(w2, 2, 1, :discard)
Enum.reduce(w1, [], fn l1, l ->
collisions =
Enum.filter(w2, fn l2 ->
collide?(l1, l2)
end)
case collisions do
[] -> l
c -> collision_points(l1, c) |> Enum.concat(l)
end
end)
end
defp collide?([{x1_min, y1_min}, {x1_max, y1_max}], [{x2_min, y2_min}, {x2_max, y2_max}]) do
x =
if x1_min == x1_max do
x1_min >= min(x2_min, x2_max) and x1_min <= max(x2_min, x2_max)
else
x2_min >= min(x1_min, x1_max) and x2_min <= max(x1_min, x1_max)
end
y =
if y1_min == y1_max do
y1_min >= min(y2_min, y2_max) and y1_min <= max(y2_min, y2_max)
else
y2_min >= min(y1_min, y1_max) and y2_min <= max(y1_min, y1_max)
end
x and y
end
defp collision_points([{x1_min, y1_min}, {x1_max, y1_max}], c) do
Enum.map(c, fn [{x2_min, y2_min}, {x2_max, y2_max}] ->
x =
if x1_min == x1_max and x1_min >= min(x2_min, x2_max) and x1_min <= max(x2_min, x2_max) do
x1_min
else
x2_min
end
y =
if y1_min == y1_max and y1_min >= min(y2_min, y2_max) and y1_min <= max(y2_min, y2_max) do
y1_min
else
y2_min
end
{x, y}
end)
end
end
Because the origin point {0, 0} is a collision point, it has to be filtered
out, but then I just map the points to their distance and find the minimum.
for me!
Puzzle 2
Puzzle 2, thankfully, only changed the computation about which point to pick. Once I have my list of points, I need to calculate how many “steps” it takes to reach my point:
defp calculate_steps({x, y}, wire) do
wire
|> Enum.reverse()
|> Enum.chunk_every(2, 1, :discard)
|> Enum.reduce_while(0, fn [{x1, y1}, {x2, y2}], s ->
cond do
x == x1 and x == x2 and y >= min(y1, y2) and y <= max(y1, y2) ->
{:halt, s + abs(y1 - y)}
y == y1 and y == y2 and x >= min(x1, x2) and x <= max(x1, x2) ->
{:halt, s + abs(x1 - x)}
x2 == x1 ->
{:cont, s + abs(y2 - y1)}
true ->
{:cont, s + abs(x2 - x1)}
end
end)
end
Remember my wires are backwards! Step 0 is to reverse it so I start from the origin. Step 2 is to generate my chunks. Step 3 is to figure out if the point is on the current line. If it isn’t, add the number of steps to my total and continue. If it is, add the number of steps along the line to it and stop.
The final solution is very similar to puzzle 1, only changing how I map at the
end to get my minimum. Only the added code is shown.
import AdventOfCode
alias AdventOfCode.Y2019.Wire
aoc 2019, 3 do
def p2() do
find_steps_along_wire =
input_stream()
|> Stream.map(&String.split(&1, ","))
|> Stream.map(&Wire.build/1)
|> Enum.to_list()
|> min_steps()
input_stream()
|> p()
|> Stream.map(&String.split(&1, ","))
|> Stream.map(&Wire.build/1)
|> Enum.to_list()
|> find_collisions()
|> Enum.filter(fn p -> p != {0, 0} end)
|> Enum.map(find_steps_along_wire)
|> Enum.min()
end
defp min_steps([w1, w2]) do
fn p ->
calculate_steps(p, w1) + calculate_steps(p, w2)
end
end
defp calculate_steps({x, y}, wire) do
wire
|> Enum.reverse()
|> Enum.chunk_every(2, 1, :discard)
|> Enum.reduce_while(0, fn [{x1, y1}, {x2, y2}], s ->
cond do
x == x1 and x == x2 and y >= min(y1, y2) and y <= max(y1, y2) ->
{:halt, s + abs(y1 - y)}
y == y1 and y == y2 and x >= min(x1, x2) and x <= max(x1, x2) ->
{:halt, s + abs(x1 - x)}
x2 == x1 ->
{:cont, s + abs(y2 - y1)}
true ->
{:cont, s + abs(x2 - x1)}
end
end)
end
end
Conclusion
Start these earlier in the day! I finished this at 11:30 PM, and the quality of my code definitely shows it. I’ll be linking to the final versions of things now instead of embedding them here.
Tests here were extremely helpful in finding my missteps, which were assumptions about order, assumptions about positivity, and forgetting to take the difference of the points when calculating the steps.
How did you do? Are you enjoying this series? @ me below!