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

• 120635-5c140b9a - provided by Linda Thompson

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?

Comments

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

[bretthancox]

Day 3 in two (convoluted) parts:

Day 3 part 1

Day 3 part 2

Both Clojure

[Thibaut Patel]

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

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

[Irene]

My ugly solution in C , after hours unfortunately :(

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

#define START_C 0
#define START_R 0

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

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

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

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


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



    dist_point_min min_dist = {100000000, START_C, START_R};

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

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

    int curr_row = START_R;
    int curr_col = START_C;

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

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

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

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

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

    }

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


}


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

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


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

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

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

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

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

[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

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

[fiddlerpianist]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[Neil Gall]

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

[Sarah]

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

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

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

    # Set the current position
    x = 0
    y = 0

    # Counter for each time the position moves
    step = 0

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

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

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

            step += 1

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

    return coordinates_all

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

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

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

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

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