DEV Community

Advent of Code 2019 Solution Megathread - Day 3: Crossed Wires

Jon Bristow on December 03, 2019

It's day 3, and we've gone from code interpreters to spatial mapping. Day 3 - The Problem Looks like someone wasn't very organized when...

Read full post

Sarah • Dec 3 '19 • Edited

Not sure if it's the most efficient way of doing it, but this is how I solved it

# Get all the directions from the input
from input import moving_input_1, moving_input_2

# Create an object with coordinates for each step
def populate_grid(moving_input):
    coordinates_all = {}

    # Set the current position
    x = 0
    y = 0

    # Counter for each time the position moves
    step = 0

    # Loop through all the directions given by the file
    for move in moving_input:
        direction = move[0]
        distance = int(move[1:])

        # Pick in which direction to move
        move_x = move_y = 0
        if direction == "L":
            move_x = -1
        if direction == "R":
            move_x = 1
        if direction == "D":
            move_y = -1
        if direction == "U":
            move_y = 1

        # Do the actual movement
        for _ in range(0, distance):
            x += move_x
            y += move_y

            step += 1

            if (x,y) not in coordinates_all:
                coordinates_all[(x,y)] = step

    return coordinates_all

# Get the coordinate grids for each line
line_1 = populate_grid(moving_input_1)
line_2 = populate_grid(moving_input_2)

# Get the intersections for both lines
intersections = list(set(line_1.keys()) & set(line_2.keys()))

# Get the shortest distance
def get_shortest():
    distances = []
    for intersection in intersections:
        dist = abs(intersection[0]) + abs(intersection[1])
        distances.append(dist)
    return min(distances)

# Get the fewest steps
def get_fewest():
    combined_steps = [line_1[i] + line_2[i] for i in intersections]
    return min(combined_steps)

print("SOLUTION", get_shortest(), get_fewest())

Paweł Świątkowski • Dec 3 '19

So, I see everyone did it like I did - recording all visited nodes on the grid and checking for intersections. Now, without considering part 2, is there a smarter way? I'm pretty sure there has to be.

Avalander • Dec 3 '19

You can generate segments with only the start and end points and check where they intersect, which would require less memory. But the math is more complicated and I'm not sure it's faster, since you can't use a hash table to find the intersections.

Mustafa Haddara • Dec 3 '19

This is how did it (I assumed the memory requirement of enumerating all of the visited nodes in the grid would be too much).

buuut the code got really messy and I don't know if there's a cleaner way to do it.

It's so long I don't want to reproduce it here 😱 github.com/MustafaHaddara/advent-o...

Jon Bristow • Dec 3 '19 • Edited

The only thing I can see right off the bat is that you’re checking for vertical/horizontal via start/end points, but you could have kept that information (UDLR) alongside the line segment definition. Other than that it makes sense, and other than being too deeply nested for my compulsive refactoring instinct, it doesn’t look much longer than my full-point enumerator.

(If you use a linked list, it doesn’t take more than 30 seconds or so for part b)

Mustafa Haddara • Dec 4 '19

you could have kept that information (UDLR) alongside the line segment definition

d'oh that would have made things much more readable.

I was complaining to a coworker that I've done collision detection for 2d games before, and this felt similar, but is sort of like "hard mode" because I didn't necessarily know which endpoint of each line was on the left/right or top/bottom. Keeping that info would have made things more straightforward!

Jon Bristow • Dec 4 '19

It’s why I love working with people who know the same codebase as me! When you PR or rubber duck, you often get some perspective that makes the “ugly” bits fall into place that you were too close to see!

Jon Bristow • Dec 3 '19 • Edited

I think I have a way it wouldn’t be ridiculous, but you have to process the list with both solutions in mind so you only have to do one Cartesian join.

First precalculate all the start/end points of each instruction in each wire.

Then, for each piece of wire a, go looking for all pieces of wire b that intersect. You should do this while keeping track of how far you’ve come on wire a. Likewise, while looping through wire b, you should keep track of your distance so it can be recorded in the data structure that captures the intersection point. Anyway, flatmap this all into one list.

Once you have them all, then you can do two different minBy type lookups to find answers a and b.

It seems more space and memory efficient. The processor efficiency seems like it’s a wash though.

I think my solution has a similar big O: 3n+n² (aka n² ), but the size of n in this pseudo code is the number of instructions, not points. In my input, the number of points is several orders of magnitude higher than the number of instructions and intersection points. Additionally, the code for calculating the “bend positions” of the wire is also way less complicated since you’re not appending lists to lists.

Ali Spittel • Dec 3 '19

This is how I did it last night! Ended up being way slower and the code was much uglier.

Avalander • Dec 3 '19

That's what I suspected would happen. I think the best optimization is to calculate the list of points for both paths and then convert one of them to a hash table and iterate over the other one and filter out the elements that are not in the hash table. This is complexity O(n) because iterating over one list is O(n) and checking whether a random element exists in a hash table is still O(1). I don't think any smart trick with segments can get a better complexity.

Stephanie Hope • Dec 3 '19

PHP, because I'm having to learn it at my internship at the moment. Something isn't right here, because it takes several minutes to run, but at least the solution appears eventually.

<?php

$input = file("input3.txt");

$wire1 = explode(",", substr($input[0], 0, strlen($input[0]) - 1));
$wire2 = explode(",", $input[1]);

$wire1_posn = trace_wire($wire1);
$wire2_posn = trace_wire($wire2);

[$distance, $time] = find_intersections($wire1_posn, $wire2_posn);
echo "\n min distance = $distance, min time = $time";

function find_intersections($wire1, $wire2)
{
    $distances = array();
    $times = array();
    foreach ($wire1 as $posn) {
        if (in_array($posn, $wire2)) {
            [$x, $y] = explode(",", $posn);
            $distances[] = abs($x) + abs($y);

            $time1 = array_search($posn, $wire1);
            $time2 = array_search($posn, $wire2);

            $times[] = $time1 + $time2 +2;
        }
        echo ".\n";
    }
    return array(min($distances), min($times));
}

function trace_wire($wire)
{
    $x = 0;
    $y = 0;

    foreach ($wire as $path) {
        $direction = $path[0];
        $distance = substr($path, 1);
        if ($direction == "U") {
            for ($i = 0; $i < $distance; $i++) {
                $y--;
                $wire_posn[] = "$x, $y";
            }
        }
        if ($direction == "D") {
            for ($i = 0; $i < $distance; $i++) {
                $y++;
                $wire_posn[] = "$x, $y";
            }
        }
        if ($direction == "L") {
            for ($i = 0; $i < $distance; $i++) {
                $x--;
                $wire_posn[] = "$x, $y";
            }
        }
        if ($direction == "R") {
            for ($i = 0; $i < $distance; $i++) {
                $x++;
                $wire_posn[] = "$x, $y";
            }
        }
    }
    return $wire_posn;
}

Jon Bristow • Dec 3 '19

If you’re enumerating every point you’re operating with two lists of hundreds of thousands of items. Worse, I don’t think there’s a way around a cartesian join of the two sets (potentially squaring your already hideous number of data).

Running into performance problems is expected, driving the solution into minutes if you’re not careful (I crashed my jvm and lost a few minutes manually killing it and my ide as they consumed as much processor and memory power as they could)

Stephanie Hope • Dec 4 '19

I was able to improve the speed hugely with just a little tweaking, from over 7 minutes to around 0.1 seconds!

Ryan Palo • Dec 4 '19

Took me an extra day to clean it up so I wasn't disgusted with it. I definitely followed the Advent of Code "Brute Force until proven otherwise" approach. I considered doing it by only considering each leg of wire as two endpoints and calculating the intersections, but this was easier and more straightforward.

I also tried out Rust's type aliases to make things read a bit easier, which I'm really happy with.

Part 2 almost got me with a sneaky "Off by Two" error. I forgot to count the step off of the origin on both wires, leading me to be short by 2 on my final answer. A quick test case based on the examples provided showed I landed at 608 instead of 610 and I got suspicious.

Altogether much happier with this than I was last night. :)

/// Day 3: Crossed Wires
/// 
/// Figure out which directions wires go and where they cross

use std::collections::HashSet;
use std::iter::FromIterator;
use std::fs;
use std::ops::Add;

/// A coordinate is a 2D location (or Vector change!) with X and Y components
#[derive(Debug, PartialEq, Eq, Hash, Copy, Clone)]
struct Coordinate {
    x: isize,
    y: isize,
}

/// You can Add Coordinates together with + to get a new one
impl Add for Coordinate {
    type Output = Self;

    fn add(self, other: Self) -> Self {
        Self {
            x: self.x + other.x,
            y: self.y + other.y,
        }
    }
}

impl Coordinate {
    pub fn new(x: isize, y: isize) -> Self {
        Self {x, y}
    }
}

/// A Wire is a chain of coordinates that are electrically connected
type Wire = Vec<Coordinate>;

/// Moves are an ordered list of delta moves to make to form a wire
type Moves = Vec<Coordinate>;

/// Expects two lines of comma separated move strings, one for each wire.
/// The move strings are of the pattern [UDLR][0-9]+
///     [UDLR]: Specifies whether the wire is going up, down, left or right
///     [0-9]+: Specifies how many spaces that leg of the wire covers
/// 
/// Returns both processed wires
fn parse_input() -> (Wire, Wire) {
    let text = fs::read_to_string("data/day3.txt").unwrap();
    let lines: Vec<&str> = text.split("\n").collect();
    let mut wires = lines.into_iter().map(build_moves).map(make_wire);
    (wires.next().unwrap(), wires.next().unwrap())
}

/// Builds a list of Moves out of an input comma separated string as described
/// above.
fn build_moves(text_moves: &str) -> Moves {
    let mut results: Vec<Coordinate> = Vec::new();


    for step in text_moves.split(",") {
        let (direction, count_text) = step.split_at(1);
        let count: usize = count_text.parse().unwrap();
        let move_coord = if direction == "U" {
            Coordinate::new(0, 1)
        } else if direction == "D" {
            Coordinate::new(0, -1)
        } else if direction == "L" {
            Coordinate::new(-1, 0)
        } else if direction == "R" {
            Coordinate::new(1, 0)
        } else {
            panic!("Weird step {}", direction);
        };

        for _ in 0..count {
            results.push(move_coord);
        }
    }

    results
}


/// Build a Wire out of relative Moves
fn make_wire(moves: Moves) -> Wire {
    let mut current = Coordinate { x: 0, y: 0 };
    let mut results: Wire = Vec::new();

    for step in moves {
        current = step + current;
        results.push(current);
    }

    results
}

/// Calculate a Coordinate's absolute distance from the origin
fn origin_manhattan_distance(coord: &Coordinate) -> usize {
    (coord.x.abs() + coord.y.abs()) as usize
}

/// Given two Wires, find the location where they cross that is closest to the
/// origin (which is where both wires start, and doesn't count as a cross)
fn find_closest_cross(a: &Wire, b: &Wire) -> Coordinate {
    let a_set: HashSet<&Coordinate> = HashSet::from_iter(a.iter());
    let b_set: HashSet<&Coordinate> = HashSet::from_iter(b.iter());
    **a_set.intersection(&b_set).min_by_key(|c| origin_manhattan_distance(c)).unwrap()
}

/// Find the first occurrence of a Coordinate in a Wire (index-wise, but 1-based)
fn find_in_wire(wire: &Wire, target: &Coordinate) -> usize {
    wire.iter().position(|e| e == target).unwrap() + 1
}

/// Find the shortest distance you can travel on each wire (summed) before you
/// hit a cross.
fn shortest_cross_distance(a: &Wire, b: &Wire) -> usize {
    let a_set: HashSet<&Coordinate> = HashSet::from_iter(a.iter());
    let b_set: HashSet<&Coordinate> = HashSet::from_iter(b.iter());
    a_set.intersection(&b_set).map(|c| find_in_wire(a, c) + find_in_wire(b, c)).min().unwrap()
}

/// Main Day 3 logic to solve the puzzles
pub fn run() {
    let (a, b) = parse_input();
    let closest_cross = find_closest_cross(&a, &b);
    println!("Closest cross distance is {}", origin_manhattan_distance(&closest_cross));
    println!("Fewest combined steps: {}", shortest_cross_distance(&a, &b));
}

Neil Gall • Dec 3 '19

Had to reach for Haskell again. This may happen on the hard ones! Solved it using correct line segment intersections rather than enumerating every single coordinate.

Scratched my head on part 2 for a bit then realised each segment could store the accumulated length, then it was a simple shortening calculation for each line at the intersections.

{-# LANGUAGE OverloadedStrings #-}

import Data.Ord (comparing)
import Data.Foldable (minimumBy)
import Data.Maybe (maybeToList)
import qualified Data.Text as T
import Test.Hspec

data Direction = U | D | L | R 
  deriving (Eq, Show)

data Move = Move Direction Int
  deriving (Eq, Show)

data Point = Point Int Int
  deriving (Eq, Show)

-- A Segment is the distance to its end and the start and end points
data Segment = Segment Int Point Point
  deriving (Eq, Show)

-- An Intersection is the crossing point and the distance along each wire to that point
data Intersection = Intersection Point Int Int
  deriving (Show)

type Wire = [Segment]

manhattan :: Point -> Int
manhattan (Point x y) = (abs x) + (abs y)

centralPort :: Point
centralPort = Point 0 0

expandWire :: [Move] -> Wire
expandWire segs = tail segments
  where
    follow (Segment len _ (Point x y)) (Move U n) = Segment (len+n) (Point x (y+1)) (Point x (y+n))
    follow (Segment len _ (Point x y)) (Move D n) = Segment (len+n) (Point x (y-1)) (Point x (y-n))
    follow (Segment len _ (Point x y)) (Move L n) = Segment (len+n) (Point (x-1) y) (Point (x-n) y)
    follow (Segment len _ (Point x y)) (Move R n) = Segment (len+n) (Point (x+1) y) (Point (x+n) y)
    segments = scanl follow (Segment 0 centralPort centralPort) segs

load :: String -> [Wire]
load = map expandWire . map wire . T.splitOn "\n" . T.strip . T.pack
  where
    wire = map (segment . T.unpack . T.strip) . T.splitOn ","
    segment (d:len) = Move (dir d) (read len)
    dir 'U' = U
    dir 'D' = D
    dir 'L' = L
    dir 'R' = R 

vertical :: Segment -> Bool
vertical (Segment _ (Point x1 _) (Point x2 _)) = x1 == x2

horizontal :: Segment -> Bool
horizontal (Segment _ (Point _ y1) (Point _ y2)) = y1 == y2

wireIntersections :: Wire -> Wire -> [Intersection]
wireIntersections [] _ = []
wireIntersections _ [] = []
wireIntersections (x:xs) (y:ys) =
  maybeToList (intersection x y) ++ wireIntersections [x] ys ++ wireIntersections xs ys

crosses :: Int -> Int -> Int -> Bool
crosses a b c = (min a b) < c && c < (max a b)

intersection :: Segment -> Segment -> Maybe Intersection
intersection s1@(Segment l1 (Point x1 y1) (Point x2 y2)) s2@(Segment l2 (Point x3 y3) (Point x4 y4)) =
  if vertical s1 && horizontal s2 && crosses y1 y2 y3 && crosses x3 x4 x1 then
    Just $ Intersection (Point x1 y3) (l1-abs(y2-y3)) (l2-abs(x4-x1))
  else
  if horizontal s1 && vertical s2 && crosses x1 x2 x3 && crosses y3 y4 y1 then
    Just $ Intersection (Point x3 y1) (l1-abs(x2-x3)) (l2-abs(y4-y1))
  else
    Nothing

intersections :: [Wire] -> [Intersection]
intersections [] = []
intersections (w:ws) = (intersections' w ws) ++ (intersections ws)
  where
    intersections' w ws = concat $ map (wireIntersections w) ws

intersectionManhattan :: Intersection -> Int
intersectionManhattan (Intersection p _ _) = manhattan p

intersectionDistance :: Intersection -> Int
intersectionDistance (Intersection _ a b) = a + b

bestIntersectionBy :: (Intersection -> Int) -> [Intersection] -> Maybe Intersection
bestIntersectionBy _   [] = Nothing
bestIntersectionBy cmp is = Just $ minimumBy (comparing cmp) is

part1 :: [Wire] -> Maybe Int
part1 = fmap intersectionManhattan . bestIntersectionBy intersectionManhattan . intersections

part2 :: [Wire] -> Maybe Int
part2 = fmap intersectionDistance . bestIntersectionBy intersectionDistance . intersections

testCase1 = load "R8,U5,L5,D3\nU7,R6,D4,L4"
testCase2 = load "R75,D30,R83,U83,L12,D49,R71,U7,L72\nU62,R66,U55,R34,D71,R55,D58,R83"
testCase3 = load "R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51\nU98,R91,D20,R16,D67,R40,U7,R15,U6,R7"

main = do
  part1 testCase1 `shouldBe` Just 6
  part1 testCase2 `shouldBe` Just 159
  part1 testCase3 `shouldBe` Just 135

  part2 testCase1 `shouldBe` Just 30
  part2 testCase2 `shouldBe` Just 610
  part2 testCase3 `shouldBe` Just 410

  input <- fmap load $ readFile "input.txt"
  putStrLn $ show (part1 input)
  putStrLn $ show (part2 input)

Neil Gall • Dec 3 '19

I'm not proud of that intersection function. 12 variables in scope. The horror!

Yordi Verkroost • Dec 4 '19

I still have nightmares from previous year's assignment based on coordinates, but luckily this wasn't as bad. Here's my solution for part two in Elixir:

defmodule Aoc19.Day3b do
  @moduledoc false

  alias Aoc19.Utils.Common

  def start(input_location) do
    [line1, line2] =
      input_location
      |> read()
      |> paths()

    line1_coordinates = coordinates(line1)
    line2_coordinates = coordinates(line2)

    line1_coordinates
    |> MapSet.intersection(line2_coordinates)
    |> Enum.map(&distance(&1, line1, line2))
    |> Enum.min()
  end

  defp coordinates(line) do
    line
    |> Enum.map(&remove_distance/1)
    |> MapSet.new()
  end

  defp remove_distance({x, y, _d}), do: {x, y}

  defp distance({x, y}, line1, line2) do
    {_, _, d1} = Enum.find(line1, fn {x1, y1, _} -> x == x1 && y == y1 end)
    {_, _, d2} = Enum.find(line2, fn {x2, y2, _} -> x == x2 && y == y2 end)
    d1 + d2
  end

  defp paths(instructions) do
    instructions
    |> Enum.map(&path/1)
  end

  defp path(instructions) do
    {_, full_path} =
      Enum.reduce(instructions, {{0, 0, 0}, []}, fn instruction,
                                                    {coordinate, path} ->
        walk(coordinate, path, instruction)
      end)

    full_path
  end

  defp walk({x, y, d}, path, {"R", steps}) do
    coordinates =
      for n <- 1..steps do
        {x + n, y, d + n}
      end

    {{x + steps, y, d + steps}, Enum.concat(path, coordinates)}
  end

  defp walk({x, y, d}, path, {"L", steps}) do
    coordinates =
      for n <- 1..steps do
        {x - n, y, d + n}
      end

    {{x - steps, y, d + steps}, Enum.concat(path, coordinates)}
  end

  defp walk({x, y, d}, path, {"U", steps}) do
    coordinates =
      for n <- 1..steps do
        {x, y + n, d + n}
      end

    {{x, y + steps, d + steps}, Enum.concat(path, coordinates)}
  end

  defp walk({x, y, d}, path, {"D", steps}) do
    coordinates =
      for n <- 1..steps do
        {x, y - n, d + n}
      end

    {{x, y - steps, d + steps}, Enum.concat(path, coordinates)}
  end

  defp walk(_, _, _), do: {nil, nil}

  defp read(input_location) do
    input_location
    |> Common.read_lines()
    |> Enum.map(&String.split(&1, ","))
    |> Enum.map(&instructions/1)
  end

  defp instructions(line) do
    Enum.map(line, &instruction/1)
  end

  defp instruction(<<direction::binary-size(1)>> <> number) do
    {direction, String.to_integer(number)}
  end
end

Check part one here

Christopher Kruse • Dec 3 '19

Woo! Day 3 is in the bag. :D

I'm hosting my solutions on repl.it, and this one they don't let me finish calculating - I'm gonna have to look for some better optimization in order to let it finish within the resource boundary they set.

Anyway, I was able to handle the calculation locally and got the answers. I used the instructions to create sets of visited points, and then used set intersection to find the crossings. From there, it was finding either the minimum distance from the origin, or finding the minimum walk distance.

(ns aoc2019.day3
  (:require [clojure.string :as st]
            [clojure.set :refer [intersection]]))

(defn next-step
  [last-pos direction]
  (let [[x y] last-pos]
    (condp = direction
      \U [x (inc y)]
      \D [x (dec y)]
      \R [(inc x) y]
      \L [(dec x) y])))

(defn walk
  "Provide the list of coords passed when moving a direction"
  [current-path step]
  (let [direction (first step)
        distance (inc (Integer/parseInt (st/join (rest step))))
        start-from (last current-path)]
    (apply conj current-path (rest (take distance (iterate #(next-step % direction) start-from))))))

(defn all-wire-coords
  [steps]
  (loop [path [[0 0]]
         steps steps]
    (if (empty? steps)
      (rest path) ; remove initial [0 0] coordinate
      (recur (walk path (first steps)) (rest steps)))))

(defn p2019-03-part1
  [input]
  (let [lines (st/split-lines input)
        wires (map #(all-wire-coords (st/split % #",")) lines)
        crosses (apply intersection (map #(into #{} %) wires))]
    (->> crosses
         (map (fn [[x y]] (+ (Math/abs x) (Math/abs y))))
         (apply min))))

(defn walk-distance
  [wires coord]
  (let [first-wire (first wires)
        second-wire (last wires)]
    (+ (inc (.indexOf first-wire coord))
       (inc (.indexOf second-wire coord)))))

(defn p2019-03-part2
  [input]
  (let [lines (st/split-lines input)
        wires (map #(all-wire-coords (st/split % #",")) lines)
        crosses (apply intersection (map #(into #{} %) wires))]
    (->> crosses
         (map (fn [coord] (walk-distance wires coord)))
         (apply min))))

Esteban • Dec 3 '19

C++

Part 1

int main(){
  freopen("in.in", "r", stdin);
  map<pair<int, int>, bool> visitedPath;
  string wirePath;
  int minDistance = INT_MAX;
  // Read path
  while(getline (cin,wirePath)) {
    map<pair<int, int>, bool> currentPath;
    stringstream ss(wirePath);
    string move;
    pair<int, int> pos = {0,0};
    // Read moves
    while (getline(ss, move, ',')) {
      char direction = move.front();
      move.erase(move.begin());
      int distance = stoi(move);
      while(distance--){
        switch (direction) {
        case 'U': pos.first++; break;
        case 'D': pos.first--; break;
        case 'R': pos.second++; break;
        case 'L': pos.second--; break;
        }
        if(visitedPath[pos] && !currentPath[pos]){
          minDistance = min(minDistance, abs(pos.first) + abs(pos.second));
        }
        currentPath[pos] = true;
        visitedPath[pos] =  true;
      }
    }
  }
  cout<<minDistance<<endl;
  return 0;
}

Part 2

int main(){
  freopen("in.in", "r", stdin);
  map<pair<int, int>, int> visitedPath;
  string wirePath;
  int minDistance = INT_MAX;
  // Read path
  while(getline (cin,wirePath)) {
    map<pair<int, int>, bool> currentPath;
    stringstream ss(wirePath);
    string move;
    pair<int, int> pos = {0,0};
    int totalDistance = 0;
    // Read moves
    while (getline(ss, move, ',')) {
      char direction = move.front();
      move.erase(move.begin());
      int distance = stoi(move);
      while(distance--){
        totalDistance++;
        switch (direction) {
        case 'U': pos.first++; break;
        case 'D': pos.first--; break;
        case 'R': pos.second++; break;
        case 'L': pos.second--; break;
        }
        if(visitedPath[pos] != 0 && !currentPath[pos]){
          minDistance = min(minDistance, totalDistance + visitedPath[pos]);
        }
        currentPath[pos] = true;
        visitedPath[pos] = totalDistance;
      }
    }
  }
  cout<<minDistance<<endl;
  return 0;
}

Jorge Gomez • Dec 5 '19

Beautiful code Sr. Really straight forward and easy to read and understand.

Ali Spittel • Dec 3 '19

I way over thought this last night, and had a solution that worked but it was gnarly. Refactored this morning:

def format_coords(coords):
    return [(val[0], int(val[1:])) for val in coords.split(",")]

DIRECTIONS = {"R": (1, 0), "L": (-1, 0), "U": (0, 1), "D": (0, -1)}

def find_points(paths):
    points = {}

    x = 0
    y = 0
    steps = 0

    for direction, distance in paths:
        for point in range(distance):
            x_change, y_change = DIRECTIONS[direction]
            x += x_change
            y += y_change
            steps += 1
            points[(x, y)] = steps

    return points


def get_intersections(points1, points2):
    return set(points1.keys()).intersection(set(points2.keys()))


def get_manhattan_distances(points):
    return [abs(x) + abs(y) for x, y in points]


def get_least_steps(intersections, points1, points2):
    return [points1[point] + points2[point] for point in intersections]


with open("input.txt") as _file:
    paths1 = format_coords(_file.readline())
    points1 = find_points(paths1)

    paths2 = format_coords(_file.readline())
    points2 = find_points(paths2)

    intersections = get_intersections(points1, points2)

    # Part 1
    print(min(get_manhattan_distances(intersections)))

    # Part 2
    print(min(get_least_steps(intersections, points1, points2)))

Matt Ellen-Tsivintzeli • Dec 3 '19

More browser antics. I think I can refactor this, and possibly make it faster, but it's fast enough.

function crosswires()
{
    let pretext = document.getElementsByTagName('pre')[0].innerHTML;
    let wires = pretext.split('\n').filter(w => w !== '').map(w => w.split(','));
    let points = [[{x:0, y:0}],[{x:0, y:0}]];
    let crosspoints = {};

    let bestpoint = {x:Number.MAX_SAFE_INTEGER, y:Number.MAX_SAFE_INTEGER};

    for(let stepi = 0; stepi < wires[0].length; stepi++)
    {
    let wire0step = wires[0][stepi];
    let wire1step = wires[1][stepi];

    let wire0points = stepToPoints(points[0][points[0].length-1], wire0step);

    for(let p0 of wire0points)
    {
        if(p0.x in crosspoints)
        {
        if(p0.y in crosspoints[p0.x])
        {
            crosspoints[p0.x][p0.y][0] = true;
        }
        else
        {
            crosspoints[p0.x][p0.y] = {0:true, 1: false};
        }

        }
        else
        {
        let obj = {};
        obj[p0.y] = {0:true, 1:false};
        crosspoints[p0.x] = obj;
        }
    }

    points[0] = points[0].concat(wire0points);

    let wire1points = stepToPoints(points[1][points[1].length-1], wire1step);

    for(let p1 of wire1points)
    {
        if(p1.x in crosspoints)
        {
        if(p1.y in crosspoints[p1.x])
        {
            crosspoints[p1.x][p1.y][1] = true;
        }
        else
        {
            crosspoints[p1.x][p1.y] = {0: false, 1: true};
        }

        }
        else
        {
        let obj = {};
        obj[p1.y] = {0:false, 1:true};
        crosspoints[p1.x] = obj;
        }
    }

    points[1] = points[1].concat(wire1points);

    }

    for(let x in crosspoints)
    {
    for(let y in crosspoints[x])
    {
        if(crosspoints[x][y][0] && crosspoints[x][y][1])
        {
        if(Math.abs(x) + Math.abs(y) < Math.abs(bestpoint.x) + Math.abs(bestpoint.y))
        {
            bestpoint = {x:x, y:y};
        }
        }
    }
    }

    return bestpoint;
}


function crosswires2()
{
    let pretext = document.getElementsByTagName('pre')[0].innerHTML;
    let wires = pretext.split('\n').filter(w => w !== '').map(w => w.split(','));
    let points = [[{x:0, y:0}],[{x:0, y:0}]];
    let steps = [0, 0]
    let crosspoints = {};

    let beststeps = Number.MAX_SAFE_INTEGER;

    for(let stepi = 0; stepi < wires[0].length; stepi++)
    {
    let wire0step = wires[0][stepi];
    let wire1step = wires[1][stepi];

    let wire0points = stepToPoints(points[0][points[0].length-1], wire0step);

    for(let p0 of wire0points)
    {
        steps[0]++;
        if(p0.x in crosspoints)
        {
        if(p0.y in crosspoints[p0.x])
        {
            if(crosspoints[p0.x][p0.y][0] == -1)
            {
            crosspoints[p0.x][p0.y][0] = steps[0];
            }
        }
        else
        {
            crosspoints[p0.x][p0.y] = {0:steps[0], 1: -1};
        }

        }
        else
        {
        let obj = {};
        obj[p0.y] = {0:steps[0], 1:-1};
        crosspoints[p0.x] = obj;
        }
    }

    points[0] = points[0].concat(wire0points);

    let wire1points = stepToPoints(points[1][points[1].length-1], wire1step);

    for(let p1 of wire1points)
    {
        steps[1]++;
        if(p1.x in crosspoints)
        {
        if(p1.y in crosspoints[p1.x])
        {
            if(crosspoints[p1.x][p1.y][1] == -1)
            {
            crosspoints[p1.x][p1.y][1] = steps[1];
            }
        }
        else
        {
            crosspoints[p1.x][p1.y] = {0: -1, 1: steps[1]};
        }

        }
        else
        {
        let obj = {};
        obj[p1.y] = {0:-1, 1:steps[1]};
        crosspoints[p1.x] = obj;
        }
    }

    points[1] = points[1].concat(wire1points);

    }

    for(let x in crosspoints)
    {
    for(let y in crosspoints[x])
    {
        if(crosspoints[x][y][0] > -1 && crosspoints[x][y][1] > -1)
        {
        let steps = crosspoints[x][y][0] + crosspoints[x][y][1];
        if(steps < beststeps)
        {
            beststeps = steps;
        }
        }
    }
    }

    return beststeps;
}


function stepToPoints(curPoint, step)
{
    let dist = parseInt(step.slice(1));
    let points = [];
    for(let i = 1; i <= dist; i++)
    {
    let nextPoint = {x:curPoint.x, y:curPoint.y};
    switch(step[0])
    {
        case 'U':
        nextPoint.y += i;
        break;
        case 'D':
        nextPoint.y -= i;
        break;
        case 'L':
        nextPoint.x += i;
        break
        case 'R':
        nextPoint.x -= i;
        break;
    }
    points.push(nextPoint);
    }

    return points;
}

Akinwunmi Oluwaseun • Dec 15 '19

My brute force JS code. Still looking into a more optimized solution

const closestIntersectionToOrigin = (wirePath1, wirePath2) => {
    const trace1 = traceWire(wirePath1);
    const trace2 = traceWire(wirePath2);

    // find intersection of traces
    const intersects = trace1.filter(x => trace2.includes(x));
    const distanceArr = intersects
        .slice(1)
        .map(x => manhattanDistance([0, 0], x.split(',').map(Number)));
    return Math.min(...distanceArr);
};

const leastStepsIntersection = (wirePath1, wirePath2) => {
    const trace1 = traceWire(wirePath1);
    const trace2 = traceWire(wirePath2);

    // find intersection of traces
    const intersects = trace1.filter(x => trace2.includes(x));
    const distanceArr = intersects.slice(1).map(x => {
        const totalSteps = trace2.findIndex(y => y == x) + trace1.findIndex(y => y == x);
        return totalSteps;
    });
    return Math.min(...distanceArr);
};

const traceWire = (wirePath, acc = ['0,0']) => {
    for (let i = 0; i < wirePath.length; i++) {
        const move = wirePath[i];
        const direction = move[0];
        const steps = Number(move.slice(1));

        const start = acc[acc.length - 1].split(',').map(Number);
        let [x, y] = start;

        const stepMap = {
            R: () => `${x},${++y}`,
            L: () => `${x},${--y}`,
            U: () => `${++x},${y}`,
            D: () => `${--x},${y}`
        };

        for (let j = 0; j < steps; j++) {
            acc.push(stepMap[direction]());
        }
    }
    return acc;
};

const manhattanDistance = (pos1, pos2) => Math.abs(pos2[0] - pos1[0]) + Math.abs(pos2[1] - pos1[1]);

if (!module.parent) {
    const wire1 = ['R75', 'D30', 'R83', 'U83', 'L12', 'D49', 'R71', 'U7', 'L72'];
    const wire2 = ['U62', 'R66', 'U55', 'R34', 'D71', 'R55', 'D58', 'R83'];

    console.log(leastStepsIntersection(wire1, wire2));
}
module.exports = { closestIntersectionToOrigin, leastStepsIntersection };

Rizwan • Dec 3 '19

Solution with Swift. Took a long route and first tried with Int Array and failed. Went with Set second time and seems working. But its very slow even on my MacBook Pro. :(

Definitely looking forward to improve my solution by getting inspiration from others code :)

import Cocoa
/// --- Day 3: Crossed Wires ---


func grid(_ path: [String], _ path2: [String]) {
    struct Point: CustomStringConvertible, Equatable, Hashable {
        var x: Int
        var y: Int

        var description: String {
            get {
                return "X: \(self.x) Y: \(self.y)"
            }
        }

        mutating func move(in direction: Character?) {
            switch direction {
            case "L": x -= 1
            case "R": x += 1
            case "U": y -= 1
            case "D": y += 1
            default:
                fatalError()
            }
        }
    }

    func fillPath(_ path: [String]) -> Set<Point> {
        var visted:Set<Point> = []
        var center = Point.init(x: 0, y: 0)

        for aPath in path {
            let direction = aPath.first
            let end = Int(aPath.dropFirst()) ?? 1
            (1 ... end).forEach {_ in
                center.move(in: direction)
                visted.insert(center)
            }
        }
        return visted
    }


    func fillPath2(_ path: [String]) -> Dictionary<Point, Int> {
        var vistedDict: Dictionary<Point, Int> = Dictionary<Point, Int>()
        var center = Point.init(x: 0, y: 0)
        var steps: Int = 0
        for aPath in path {
            let direction = aPath.first
            let end = Int(aPath.dropFirst()) ?? 1
            (1 ... end).forEach {_ in
                steps = steps + 1
                center.move(in: direction)
                if vistedDict[center] == nil {
                    vistedDict[center] = steps
                }
            }
        }
        return vistedDict
    }


    func partTwo() {
        let firstVisited = fillPath2(path)
        let secondVisited = fillPath2(path2)
        let crossPoint = firstVisited.keys.filter(secondVisited.keys.contains)
        let distance = crossPoint.map{ firstVisited[$0]! + secondVisited[$0]!}.min()
        print(distance)
    }

    func partOne() {
        let firstVisited = fillPath(path)
        let secondVisited = fillPath(path2)
        let crossPoints = firstVisited.intersection(secondVisited)

        //    let crossPoints = firstVisited.filter(secondVisited.contains)
        //
        let center = Point.init(x: 0, y: 0)
        var distances:[Int] = []
        for (_,aPoint) in crossPoints.enumerated() {
            let distance = abs(center.x - aPoint.x) + abs(center.y - aPoint.y)
            distances.append(distance)
        }

        dump(crossPoints)
        print(distances)
        print(distances.min())
    }
    partOne()
    partTwo()
}

let path = """
R1003,U756,L776,U308,R718,D577,R902,D776,R760,U638,R289,D70,L885,U161,R807,D842,R175,D955,R643,U380,R329,U573,L944,D2,L807,D886,L549,U592,R152,D884,L761,D915,L726,D677,L417,D651,L108,D377,L699,D938,R555,D222,L689,D196,L454,U309,L470,D234,R198,U689,L996,U117,R208,D310,R572,D562,L207,U244,L769,U186,R153,D756,R97,D625,R686,U244,R348,U586,L385,D466,R483,U718,L892,D39,R692,U756,L724,U148,R70,U224,L837,D370,L309,U235,R382,D579,R404,D146,R6,U584,L840,D863,R942,U646,R146,D618,L12,U210,R126,U163,R931,D661,L710,D883,L686,D688,L148,D19,R703,U530,R889,U186,R779,D503,R417,U272,R541,U21,L562,D10,L349,U998,R69,D65,R560,D585,L949,D372,L110,D865,R212,U56,L936,U957,L88,U612,R927,U642,R416,U348,L541,D416,L808,D759,R449,D6,L517,D4,R494,D143,L536,U341,R394,U179,L22,D680,L138,U249,L285,U879,L717,U756,L313,U222,R823,D208,L134,U984,R282,U635,R207,D63,L416,U511,L179,D582,L651,U932,R646,U378,R263,U138,L920,U523,L859,D556,L277,D518,R489,U561,L457,D297,R72,U920,L583,U23,L395,D844,R776,D552,L55,D500,R111,U409,R685,D427,R275,U739,R181,U333,L215,U808,R341,D537,R336,U230,R247,U748,R846,U404,R850,D493,R891,U176,L744,U585,L987,D849,R271,D848,L555,U801,R316,U753,L390,U97,L128,U45,R706,U35,L928,U913,R537,D512,R152,D410,R76,D209,R183,U941,R289,U632,L923,D190,R488,D934,R442,D303,R178,D250,R204,U247,R707,U77,R428,D701,R386,U110,R641,U925,R703,D387,L946,U415,R461,D123,L214,U236,L959,U517,R957,D524,R812,D668,R369,U340,L606,D503,R755,U390,R142,D921,L976,D36,L965,D450,L722,D224,L303,U705,L584
"""
let path2 = """
L993,U810,L931,D139,R114,D77,L75,U715,R540,D994,L866,U461,R340,D179,R314,D423,R629,D8,L692,U446,L88,D132,L128,U934,L465,D58,L696,D883,L955,D565,R424,U286,R403,U57,L627,D930,R887,D941,L306,D951,R918,U587,R939,U821,L65,D18,L987,D707,L360,D54,L932,U366,R625,U609,R173,D637,R661,U888,L68,U962,R270,U369,R780,U845,L813,U481,R66,D182,R420,U605,R880,D276,L6,D529,R883,U189,R380,D472,R30,U35,L510,D844,L146,U875,R152,U545,R274,U920,R432,U814,R583,D559,L820,U135,L353,U975,L103,U615,R401,U692,L676,D781,R551,D985,L317,U836,R115,D216,L967,U286,R681,U144,L354,U678,L893,D487,R664,D185,R787,D909,L582,D283,L519,D893,L56,U768,L345,D992,L248,U439,R573,D98,L390,D43,L470,D435,R176,U468,R688,U388,L377,U800,R187,U641,L268,U857,L716,D179,R212,U196,L342,U731,R261,D92,R183,D623,L589,D215,L966,U878,L784,U740,R823,D99,L167,D992,R414,U22,L27,U390,R286,D744,L360,U554,L756,U715,R939,D806,R279,U292,L960,U633,L428,U949,R90,D321,R749,U395,L392,U348,L33,D757,R289,D367,L562,D668,L79,D193,L991,D705,L562,U25,R146,D34,R325,U203,R403,D714,R607,U72,L444,D76,R267,U924,R289,U962,L159,U726,L57,D540,R299,U343,R936,U90,L311,U243,L415,D426,L936,D570,L539,D731,R367,D374,L56,D251,L265,U65,L14,D882,L956,U88,R688,D34,R866,U777,R342,D270,L344,D953,L438,D855,L587,U320,L953,D945,L473,U559,L487,D602,R255,U871,L854,U45,R705,D247,R955,U885,R657,D664,L360,D764,L549,D676,R85,U189,L951,D922,R511,D429,R37,U11,R821,U984,R825,U874,R753,D524,L537,U618,L919,D597,L364,D231,L258,U818,R406,D208,R214,U530,R261
"""
grid(path.components(separatedBy: ","),path2.components(separatedBy: ","));

Jon Bristow • Dec 3 '19

Kotlin Solution! No monads today, sadly, but I pulled in Java's LinkedList implementation for memory efficiency.

import java.nio.file.Files
import java.nio.file.Paths
import java.util.*
import kotlin.math.abs


typealias Point = Pair<Int, Int>

val Point.x: Int get() = first
val Point.y: Int get() = second

object Day03 {

    data class Instruction(val direction: String, val count: Int)

    data class Wire(val lastLoc: Point, val locations: LinkedList<Point>)

    private fun String.makeInstruction(): Instruction = Instruction(take(1), drop(1).toInt())

    private const val FILENAME = "src/main/resources/day03.txt"

    private fun String.processLine(): List<Instruction> = split(",").map { it.makeInstruction() }

    private fun List<String>.toWires(): List<Wire> {
        return map { line ->
            line.processLine()
                .fold(Wire(0 to 0, LinkedList())) { wire, instr ->
                    val newLocs = when (instr.direction) {
                        "U" -> (wire.lastLoc.y + 1..wire.lastLoc.y + instr.count).map { (wire.lastLoc.x to it) }
                        "D" -> (wire.lastLoc.y - instr.count until wire.lastLoc.y).reversed().map { (wire.lastLoc.x to it) }
                        "R" -> (wire.lastLoc.x + 1..wire.lastLoc.x + instr.count).map { (it to wire.lastLoc.y) }
                        "L" -> (wire.lastLoc.x - instr.count until wire.lastLoc.x).reversed().map { (it to wire.lastLoc.y) }
                        else -> throw Error("bad instruction $instr")
                    }
                    wire.locations.addAll(newLocs)
                    Wire(newLocs.last(), wire.locations)
                }
        }
    }

    private val wires =
        Files.readAllLines(Paths.get(FILENAME)).toWires().map { it.locations }

    private val wiresAsSet = wires.map { it.toSet() }


    private fun List<Set<Point>>.overlaps(): Set<Point> {
        return this[0].intersect(this[1].toSet())
    }

    private fun Set<Point>.calculateShortest(wires0: LinkedList<Point>, wires1: LinkedList<Point>): String {
        return map { match ->
            wires0.takeWhile { p -> p != match } to wires1.takeWhile { p -> p != match }
        }.minBy { it.first.size + it.second.size }!!
            .let {
                it.first.size + it.second.size + 2
            }.toString()
    }

    fun part1() =
        wiresAsSet.overlaps().map { abs(it.x.toDouble()) + abs(it.y.toDouble()) }.min()!!.toInt().toString()

    fun part2() = wiresAsSet.overlaps()
        .calculateShortest(wires[0], wires[1])

}


fun main() {
    println("Part 1: ${Day03.part1()}")
    println("Part 2: ${Day03.part2()}")
}

Jon Bristow • Dec 3 '19

I tried to draw the full layout represented by my input as ascii, but it turned out to be a 200MB file. Imagemagick filled my hard drive trying to parse it.

Avalander • Dec 3 '19

Scala! I'm slowly falling in love with this language.

object Wires {
  case class Point(x: Int, y: Int)

  def closestInDistance (a: Seq[String], b: Seq[String]): Int = {
    val pathA = makePath(a, Point(0, 0))
    val pathB = makePath(b, Point(0, 0))

    val distances = pathA.intersect(pathB).tail map {
      case Point(x, y) => math.abs(x) + math.abs(y)
    }

    distances.min
  }

  def closestInSteps (a: Seq[String], b: Seq[String]): Int = {
    val pathA = makePath(a, Point(0, 0))
    val pathB = makePath(b, Point(0, 0))

    val steps = pathA.intersect(pathB).tail map {
      point => pathA.indexOf(point) + pathB.indexOf(point)
    }

    steps.min
  }

  private def makePath (xs: Seq[String], start: Point): Seq[Point] = {
    val vectors = for {
      x <- xs
      (dir :: rest) = x.toList
      length = rest.mkString.toInt
      i <- (1 to length)
    } yield dir match {
      case 'R' => Point(1, 0)
      case 'L' => Point(-1, 0)
      case 'U' => Point(0, 1)
      case 'D' => Point(0, -1)
    }

    vectors.foldLeft(Vector(start)) {
      case (result, Point(x2, y2)) => {
        val Point(x, y) = result.last
        val next = Point(x + x2, y + y2)
        result :+ next
      }
    }
  }
}

Linda Thompson • Dec 5 '19

Woooooo, finally got this one! Took me 2 days, but dangit I solved it on my own and I feel super pleased and relieved. lol

What's lame is I basically had the right idea yesterday, but wasn't adding the absolute value of the coordinates, so was getting the wrong values back and thought my whole solution was wrong. 😒 So I rage deleted everything last night, and rewrote it all today and got it working! 😊

Got to use a set for the first real time, which worked out nicely! I figured I could plot out each coordinate visited by the first wire, and store those in a set (since where a wire crosses itself doesn't matter). Then, for the second wire, I go through and just check to see if the set contains that coordinate already, and if so, store that in it's own array to check over at the end. Ran pretty quickly, though I'm sure I could factor the code to be a bit more function-oriented than I did. Just wanted it to work! lol

Thankfully, part 2 didn't take me all that long...just refactoring my first path run to count the steps taken so far and figure out how/where to store them, then adding it as an extra value onto the end of my crossed points array. Easy! (Ending up reading my coords and counter as a string, so that comparisons were easier to do.)

JavaScript:

let wire1 = input[0].split(',');
let wire2 = input[1].split(','); 

let path1 = new Set();
let path1c = [];
let crosses = [];

let h = 0; 
let v = 0;
let counter = 0;

for (let i = 0; i < wire1.length; i++) {
  let split = [wire1[i].slice(0, 1), wire1[i].slice(1)];
  let dir = split[0];
  let steps = split[1];

  do {
    switch (dir) {
      case 'U':
        v++;
        steps--;
        break;
      case 'D':
        v--;
        steps--;
        break;
      case 'R':
        h++;
        steps--;
        break;
      case 'L':
        h--;
        steps--;
        break;
      }
      counter++;

    if (!path1.has(`${h},${v}`)) {
      path1.add(`${h},${v}`);  
      path1c.push(counter);
    }
  } while  (steps > 0);
}

let setarr = [...path1];

// console.log(path1);

h = 0; 
v = 0;
counter = 0;

for (let i = 0; i < wire2.length; i++) {
  let split = [wire2[i].slice(0, 1), wire2[i].slice(1)];
  let dir = split[0];
  let steps = split[1];

  do {
    switch (dir) {
      case 'U':
        v++;
        steps--;
        break;
      case 'D':
        v--;
        steps--;
        break;
      case 'R':
        h++;
        steps--;
        break;
      case 'L':
        h--;
        steps--;
        break;
      }
      counter++;

    if (path1.has(`${h},${v}`)) {
      let path1pos = setarr.indexOf(`${h},${v}`);
      let path1count = path1c[path1pos];
      let sumsteps = path1count + counter;
      crosses.push(`${h},${v},${sumsteps}`);
    }  
  } while  (steps > 0);
}

// console.log(crosses);

let closest;
let lowest;

crosses.forEach(val => {
  let breakup = val.split(',');
  let valh = breakup[0];
  let valv = breakup[1];
  let valc = breakup[2];

  let distance = Math.abs(valh) + Math.abs(valv);

  if (!closest) {
    closest = distance;
  } else {
    if (distance < closest) {
      closest = distance;
    }
  }

  if (!lowest) {
    lowest = valc;
  } else {
    if (valc < lowest) {
      lowest = valc;
    }
  }
})

console.log(`Part 1: ${closest}`);
console.log(`Part 2: ${lowest}`);

fiddlerpianist • Dec 4 '19

I'm using AoC this year to learn Python. Last year I used it to learn nodejs.

Day 3 was a doozy for me, partly because I started it at 11pm (I'm on American Central Time), but partly because I overthought the problem and thought I would map the whole thing as a 2D array. After screwing my head on a little bit more, I went with simply tracking the path of the wire with x/y tuples, then finding the intersections between the two wires. Manhattan distance was baked into each tuple (just add the absolute values of x and y together and voila).

For my first crack at Part One, I originally used sets. When I discovered Part Two, I just had to change the sets to lists and then I got path distance for free.

def move(direction, coord, path):
    x = coord['x']
    y = coord['y']
    # remove any \n if it exists
    dir = direction.rstrip()
    amt = int(dir[1:len(dir)])

    if dir.startswith("R"):
        for i in range(x+1, x+amt+1):
            path.append((i,y))
        coord['x'] += amt
    elif dir.startswith("L"):
        for i in range(x-1, x-amt-1, -1):
            path.append((i,y))
        coord['x'] -= amt
    elif dir.startswith("U"):
        for i in range(y+1, y+amt+1):
            path.append((x,i))
        coord['y'] += amt
    elif dir.startswith("D"):
        for i in range(y-1, y-amt-1, -1):
            path.append((x,i))
        coord['y'] -= amt
    else:
        # Fortunately we don't have any of these
        print ("Error! Wasn't expecting that!")    
    return path

def findDistancesToCommonPoints(path, intersections):
    positions = {}
    previousCoord = (0,0)
    cumulativeDistance = 0
    for i in range(0, len(path)):
        cumulativeDistance += calculateDistance(previousCoord, path[i])
        if path[i] in intersections and path[i] not in positions:
            positions[path[i]] = cumulativeDistance
        # make the current coord the previous one for the next iteration
        previousCoord = path[i]
    return positions

def calculateDistance(point1, point2):
    return abs(point1[0]-point2[0]) + abs(point1[1]-point2[1])

# Initialize: open file, put both wire directions into lists
with open('day03.txt') as f:
    wireOneDirections = f.readline().split(",")
    wireTwoDirections = f.readline().split(",")

# Setup: get the paths that the wires take, put the coordinate points into a trackable list
wireCoord = { 'x': 0, 'y': 0}
firstpath = []
for i in range(0, len(wireOneDirections)):
    move(wireOneDirections[i], wireCoord, firstpath)

wireCoord = { 'x': 0, 'y': 0}
secondpath = []
for i in range(0, len(wireTwoDirections)):
    move(wireTwoDirections[i], wireCoord, secondpath)

# Part One: find the intersection point closest to the central port (which is at (0, 0))
intersections = set(firstpath).intersection(set(secondpath))
# (Initialize with large number...one that will be larger than any of the numbers we might encounter)
least = 1000000
for tup in intersections:
    sum = abs(tup[0]) + abs(tup[1])
    if sum < least:
        least = sum

print ("Part One: %i" % least)

# Part Two: find the fewest combined steps the wires must take to reach an intersection
distancesOne = findDistancesToCommonPoints(firstpath, intersections)
distancesTwo = findDistancesToCommonPoints(secondpath, intersections)
combinedDistances = []
for key in distancesOne:
    combinedDistances.append(distancesOne[key]+distancesTwo[key])

print ("Part Two: %i" % min(combinedDistances))

Irene • Dec 7 '19 • Edited

My ugly solution in C , after hours unfortunately :(

#include <stdio.h>
#include <stdlib.h>

#define START_C 0
#define START_R 0

typedef struct _dist_point_min{
    int dist_min;
    int row_min;
    int col_min;
}dist_point_min;

void calc_dist(int row, int col, dist_point_min *str);

int main(int argc, char *argv[]){
    FILE* fd;
    int i;
    char buf;
    int pos;

    fd = fopen("input.txt","r");


    if (fd == NULL){
        perror("Errore apertura file");
        exit(1);
    }
    i = 0;
    while((fscanf(fd, "%c,", &buf)) > 0 && buf != '\n' ){
    }
    while(fscanf(fd, "%c,", &buf) > 0 && fscanf(fd, "%d,", &pos) > 0){
        //printf("p: %d\n", pos);
        i++;
    }
    //printf("i: %d\n",i);
    int NUM_ELEM = i+1;



    dist_point_min min_dist = {100000000, START_C, START_R};

    int x[NUM_ELEM];
    x[0] = START_R;
    int y[NUM_ELEM];
    y[0] = START_C;

    int x1[NUM_ELEM];
    x1[0] = START_R;
    int y1[NUM_ELEM];
    y1[0] = START_C;

    int curr_row = START_R;
    int curr_col = START_C;

    fd = fopen("input.txt","r");

    if (fd == NULL){
        perror("Errore apertura file");
        exit(1);
    }
    i = 1;
    while((fscanf(fd, "%c,", &buf)) > 0 && buf != '\n' ){
        switch(buf){
            case 'R':
                fscanf(fd, "%d,", &pos);
                x[i] = curr_row;
                y[i] = curr_col + pos;
                printf("R r: %d, c: %d \n", x[i], y[i]);
                curr_col += pos;
                break;
            case 'L':
                fscanf(fd, "%d,", &pos);
                x[i] = curr_row;
                y[i] = curr_col - pos;
                printf("L r: %d, c: %d \n", x[i], y[i]);
                curr_col -= pos;
                break;
            case 'U':
                fscanf(fd, "%d,", &pos);
                x[i] = curr_row - pos;
                y[i] = curr_col;
                printf("U r: %d, c: %d \n", x[i], y[i]);
                curr_row -= pos;
                break;
            case 'D':
                fscanf(fd, "%d,", &pos);
                x[i] = curr_row + pos;
                y[i] = curr_col;
                printf("D r: %d, c: %d \n", x[i], y[i]);
                curr_row += pos;
                break;  
        }
        i++;

    }
    /*for(int c = 0; c < 5; c++){
        printf("r: %d, c: %d \n",x[c],y[c]);
    }*/

    curr_row = START_R;
    curr_col = START_C;
    i = 1;

    printf("\n");
    while((fscanf(fd, "%c,", &buf)) > 0){   
        switch(buf){
            case 'R':
                fscanf(fd, "%d,", &pos);
                x1[i] = curr_row;
                y1[i] = curr_col + pos;
                for(int r = 1; r <= NUM_ELEM; r++){
                //  printf("\n y[r]: %d, y1[i-1]: %d, y1[i]: %d\n",y[r],y1[i-1],y1[i]);
                    if(x1[i] <= x[r-1] && x1[i] >= x[r] || x1[i] >= x[r-1] && x1[i] <= x[r]){
                //      printf("S4\n");
                        if(y1[i-1] <= y[r] && y1[i] >= y[r] || y1[i-1] >= y[r] && y1[i] <= y[r]){
                    //      printf("S4_2\n");
                //          printf("\nVEDI: x: %d, y1: %d\n\n",x1[i],y[r]);
                            calc_dist(x1[i],y[r],&min_dist);
                        }
                    }
                }
                printf("R r: %d, c: %d \n", x1[i], y1[i]);
                curr_col += pos;
                break;
            case 'L': //*
                fscanf(fd, "%d,", &pos);
                x1[i] = curr_row;
                y1[i] = curr_col - pos;
                for(int r = 1; r <= NUM_ELEM; r++){
            //      printf("\n y[r]: %d, y1[i-1]: %d, y1[i]: %d\n",y[r],y1[i-1],y1[i]);
                    if(x1[i] <= x[r-1] && x1[i] >= x[r] || x1[i] >= x[r-1] && x1[i] <= x[r]){
            //          printf("S4\n");
                        if(y1[i-1] <= y[r] && y1[i] >= y[r] || y1[i-1] >= y[r] && y1[i] <= y[r]){
                //          printf("S4_2\n");
                    //      printf("\nVEDI: x: %d, y1: %d\n\n",x1[i],y[r]);
                            calc_dist(x1[i],y[r],&min_dist);
                        }
                    }
                }
                printf("L r: %d, c: %d \n", x1[i], y1[i]);
                curr_col -= pos;
                break;
            case 'U':
                fscanf(fd, "%d,", &pos);
                x1[i] = curr_row - pos;
                y1[i] = curr_col;
                for(int r = 1; r <= NUM_ELEM; r++){
            //      printf("\n y[r-1]: %d, y[r]: %d, y1[i]: %d\n",y[r-1],y[r],y1[i]);
                    if(y1[i] <= y[r-1] && y1[i] >= y[r] || y1[i] >= y[r-1] && y1[i] <= y[r]){
                //      printf("S4\n");
                        if(x1[i-1] <= x[r] && x1[i] >= x[r] || x1[i-1] >= x[r] && x1[i] <= x[r]){
                //          printf("S4_2\n");
                //          printf("\nVEDI: x1: %d, y: %d\n\n",x[r],y1[i]);
                            calc_dist(x[r],y1[i],&min_dist);
                        }
                    }
                }
                printf("U r: %d, c: %d \n", x1[i], y1[i]);
                curr_row -= pos;
                break;
            case 'D': //*
                fscanf(fd, "%d,", &pos);
                x1[i] = curr_row + pos;
                y1[i] = curr_col;
                for(int r = 1; r <= NUM_ELEM; r++){
            //      printf("\n y[r-1]: %d, y[r]: %d, y1[i]: %d\n",y[r-1],y[r],y1[i]);
                    if(y1[i] <= y[r-1] && y1[i] >= y[r] || y1[i] >= y[r-1] && y1[i] <= y[r]){
                        //printf("S4\n");
                        if(x1[i-1] <= x[r] && x1[i] >= x[r] || x1[i-1] >= x[r] && x1[i] <= x[r]){
                    //      printf("S4_2\n");
                            printf("\nVEDI: x1: %d, y: %d, pos %d\n\n",x[r],x1[i-1],curr_row+pos);
                            calc_dist(x[r],y1[i],&min_dist);
                        }
                    }
                }
                printf("D r: %d, c: %d \n", x1[i], y1[i]);
                curr_row += pos;
                break;  
        }
        i++;

    }

    printf("%d\n", min_dist.dist_min);


}


void calc_dist(int row, int col, dist_point_min *min){
    if(row == START_R && col == START_C)
        return;
    printf("-r: %d,c: %d\n\n", row,col);
    int d_col = 0;
    int d_row = 0;

    if(col > START_C)
        d_col = col - START_C;
    else
        d_col = START_C - col;


    if(row > START_R)
        d_row = row - START_R;
    else
        d_row = START_R - row;

        printf("+c: %d, r: %d\n",d_col,d_row);

    int dist = d_row + d_col;
    printf("dist %d\n",dist);

    if(min -> dist_min > dist){
        min -> dist_min = dist;
        min -> row_min = row;
        min -> col_min = col;
    }
}

bretthancox • Dec 12 '19 • Edited

Day 3 in two (convoluted) parts:

Day 3 part 1

Day 3 part 2

Both Clojure

Thibaut Patel • Dec 9 '19

It took me quite a bit of time to solve both problems, but I believe I've implemented a relatively optimized solution:

Parse the input into a list of segments
Detect the overlap between the two wires, segment by segment (only when one wire is vertical and the other is horizontal)

salokristian • Dec 3 '19

Here's my solution with Clojure. It is generating all the points in the lines, which seems a bit brute-force, but at least on my machine it works swiftly;)

I'm also posting my solutions to github.

(defn parse-wire [s]
  (->> (str/split s #",")
       (map (fn [s]
              {:dir   (subs s 0 1)
               :steps (edn/read-string (subs s 1))}))))

(defn line-points [start-point line]
  (let [step-line (case (:dir line)
                    "U" #(update start-point :y + %)
                    "D" #(update start-point :y - %)
                    "R" #(update start-point :x + %)
                    "L" #(update start-point :x - %))]
    (->> (:steps line)
         inc
         (range 1)
         (map step-line))))

(defn create-grid [wire]
  (reduce (fn [grid line]
            (into grid (line-points (last grid) line)))
          [{:x 0 :y 0}]
          wire))

(def wires (common/parse-file parse-wire "day_3.txt"))
(def grid-1 (create-grid (first wires)))
(def grid-2 (create-grid (second wires)))
(def intersect-points (clj-set/intersection (set grid-1) (set grid-2)))

(defn part-1 []
  (->> intersect-points
       (map #(+ (Math/abs (:x %)) (Math/abs (:y %))))
       (filter #(not (zero? %)))
       (apply min)))

(defn part-2 []
  (->> intersect-points
       (map #(+ (.indexOf grid-1 %) (.indexOf grid-2 %)))
       (filter #(not (zero? %)))
       (apply min)))

simonced • Dec 12 '19

Wow, your solution is so compact!
Mine is very verbose, and I am not done with part 2 yet! (will try tonight, but it's hard when working 11h a day...).

Maybe you could have a look on my solution and give me some pointers on how I could get better at Clojure?

gitlab.com/simonced/advent-of-code...

I am just beginning and I enjoy the language very much :).

Javid Asgarov • Dec 3 '19

Can somebody help with undesrstanding the premise.
I am a little bit confused from the description of part 1. What should be considered the central port?

Jon Bristow • Dec 3 '19

Well, technically it can be anything you want!

However, since the answer is the distance from the "center port", you might as well make things easier on yourself by declaring that it is (0,0)

Javid Asgarov • Dec 3 '19

Oh, ok. Thank you!