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

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

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

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

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

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

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

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

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

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

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

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

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

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()}")
}

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

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