DEV Community 👩‍💻👨‍💻

Cover image for Advent of Code 2019 Solution Megathread - Day 3: Crossed Wires
Jon Bristow
Jon Bristow

Posted on • Updated on

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

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?

Top comments (38)

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 • Edited on

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

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 • Edited on

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

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
 
smh30 profile image
Stephanie Hope
Collapse
 
fossheim profile image
Sarah • Edited on

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

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

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

All DEV content is created by the community!

Hey, if you're landing here for the first time, you should know that this website is a global community of folks who blog about their experiences to help folks like you out.

Sign up now if you're curious. It's free!