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