Mostly code

# Advent of Code 2019: Day 3

04 Dec 2019 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

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 `h`ead and `t`ail 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

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.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

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.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!