loading...
Cover image for Advent of Code 2019 Solution Megathread - Day 3: Crossed Wires

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

jbristow profile image Jon Bristow Updated on ・2 min read

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 doing the wiring for our fuel management system! While we have the time, let's get in there and untangle the shorting out wires and replace it with its more ideal version.

Part 1 was fairly straightforward, but since I didn't know how to convert this into nice intersecting systems of equation, my brute force solution ran into a heapspace problem.

Part 2 was a bit hairy, because I had to back out one of my optimizations for part 1, which revealed (eventually) an issue with how I was calculating the points it passed through.

Overall I would rate this a fairly difficult day 3!

Ongoing Meta

Dev.to List of Leaderboards

If you were part of Ryan Palo's leaderboard last year, you're still a member of that!

If you want me to add your leaderboard code to this page, reply to one of these posts and/or send me a DM containing your code and any theming or notes you’d like me to add. (You can find your private leaderboard code on your "Private Leaderboard" page.)

I'll edit in any leaderboards that people want to post, along with any description for the kinds of people you want to have on it. (My leaderboard is being used as my office's leaderboard.) And if I get something wrong, please call me out or message me and I’ll fix it ASAP.

There's no limit to the number of leaderboards you can join, so there's no problem belonging to a "Beginner" and a language specific one if you want.

Neat Statistics

I'm planning on adding some statistics, but other than "what languages did we see yesterday" does anyone have any ideas?

Discussion

pic
Editor guide
Collapse
fossheim profile image
Sarah

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())
Collapse
katafrakt profile image
Paweł Świątkowski

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.

Collapse
avalander profile image
Avalander

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.

Collapse
mustafahaddara profile image
Mustafa Haddara

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

Thread Thread
jbristow profile image
Jon Bristow Author

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)

Thread Thread
mustafahaddara profile image
Mustafa Haddara

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!

Thread Thread
jbristow profile image
Jon Bristow Author

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!

Collapse
jbristow profile image
Jon Bristow Author

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+n2 (aka n2 ), 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.

Collapse
aspittel profile image
Ali Spittel

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

Thread Thread
avalander profile image
Avalander

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.

Collapse
smh30 profile image
Stephanie Hope

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;
}

Collapse
jbristow profile image
Jon Bristow Author

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)

Collapse
Collapse
ballpointcarrot profile image
Christopher Kruse

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

Collapse
neilgall profile image
Neil Gall

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)
Collapse
neilgall profile image
Neil Gall

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

Collapse
rpalo profile image
Ryan Palo

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));
}
Collapse
yordiverkroost profile image
Yordi Verkroost

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

Collapse
esbanarango profile image
Esteban Arango Medina

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;
}
Collapse
jorgee97 profile image
Jorge Gomez

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

Collapse
aspittel profile image
Ali Spittel

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)))
Collapse
mellen profile image
Matt Ellen

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;
}
Collapse
204070 profile image
Akinwunmi Oluwaseun

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 };
Collapse
rizzu26 profile image
Rizwan

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: ","));

Collapse
jbristow profile image
Jon Bristow Author

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()}")
}
Collapse
jbristow profile image
Jon Bristow Author

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.

Collapse
avalander profile image
Avalander

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
      }
    }
  }
}
Collapse
rtran profile image
Ray Tran ☁️

Today was a challenging Day 3! I was definitely overthinking this problem, and I also ended up accidentally deleting my Part 1 implementation before moving on to Part 2...it's one of those days 🙃. Here's what I got:

def get_path(wire):
    i = j = 0
    step = 1
    path = {}
    for visit in wire:
        dir, position = visit[0], int(visit[1:])
        x = y = 0
        if dir == 'U':
            x = -1
        elif dir == 'D':
            x = 1
        elif dir == 'L':
            y = -1
        elif dir == 'R':
            y = 1
        else:
            raise Exception('Unexpected direction')

        for _ in range(position):
            i += x
            j += y
            path[(i, j)] = step
            step += 1

    return path

def dist(p, q):
    return abs(p[0] - q[0]) + abs(p[1] - q[1])

def calculate_min_distance(intersections):
    return min(dist(point, (0, 0)) for point in intersections)

def calculate_min_steps(intersections, steps_a, steps_b):
    min_steps = float('inf')
    for point in intersections:
        if point not in steps_a or point not in steps_b:
            raise Exception('Not an shared path intersection.')
        min_steps = min(min_steps, steps_a[point] + steps_b[point])
    return min_steps

data = open('input.txt', 'r').readlines()
wire1, wire2 = data[0].strip().split(','), data[1].strip().split(',')
path_wire1, path_wire2 = get_path(wire1), get_path(wire2)
intersections  = list(set(path_wire1.keys()) & set(path_wire2.keys()))

# part 1
print(calculate_min_distance(intersections))

# part 2
print(calculate_min_steps(intersections, path_wire1, path_wire2))
Collapse
lindakatcodes profile image
Linda Thompson

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}`);
Collapse
thibpat profile image
Thibaut Patel

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

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

Collapse
fiddlerpianist profile image
fiddlerpianist

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))
Collapse
ninfadora profile image
Irene

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;
    }
}
Collapse
bretthancox profile image
bretthancox

Day 3 in two (convoluted) parts:

Day 3 part 1

Day 3 part 2

Both Clojure

Collapse
salokristian profile image
salokristian

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)))
Collapse
simonced profile image
simonced

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

Collapse
askeroff profile image
Javid Askerov

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?

Collapse
jbristow profile image
Jon Bristow Author

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)

Collapse
askeroff profile image
Javid Askerov

Oh, ok. Thank you!