Day 3: Crossed Wires

defmodule Day3 do
  def solution_part1(filename) do
    get_wire_intersections(filename)
    |> Enum.map(fn {a, _} -> a end)
    |> Enum.min_by(&manhattan/1)
    |> manhattan
  end

  def solution_part2(filename) do
    get_wire_intersections(filename)
    |> Enum.min_by(&combined_steps/1)
    |> combined_steps
  end

  defp get_wire_intersections(filename) do
    wire1 =
      parse_input(filename, 0)
      |> navigate()

    wire2 =
      parse_input(filename, 1)
      |> navigate()

    intersection_recurser(wire1, wire2, []) |> tl
  end

  defp navigate(route) do
    Enum.reduce(route, [{0, 0, 0}], fn command, acc_route ->
      move(acc_route, command)
    end)
    |> List.keysort(1)
    |> List.keysort(0)
  end

  defp move(route, {direction, movement}) do
    case direction do
      "U" ->
        step(route, movement, 0, 1)

      "D" ->
        step(route, movement, 0, -1)

      "L" ->
        step(route, movement, -1, 0)

      "R" ->
        step(route, movement, 1, 0)
    end
  end

  defp parse_input(filename, n) do
    File.read!(filename)
    |> String.trim()
    |> String.split("\n")
    |> Enum.at(n)
    |> String.split(",")
    |> Enum.map(
      &{String.first(&1),
       String.slice(&1, 1..-1)
       |> String.to_integer()}
    )
  end

  defp intersection_recurser(wire1, wire2, result)
       when wire1 == [] or wire2 == [] do
    result
  end

  defp intersection_recurser(wire1, wire2, result) do
    case compare_duple(hd(wire1), hd(wire2)) do
      :equal ->
        intersection_recurser(
          tl(wire1),
          tl(wire2),
          [{hd(wire1), hd(wire2)} | result]
        )

      :smaller ->
        intersection_recurser(tl(wire1), wire2, result)

      :greater ->
        intersection_recurser(wire1, tl(wire2), result)
    end
  end

  defp compare_duple({x1, x2, _}, {y1, y2, _}) do
    if x1 == y1 do
      if x2 == y2 do
        :equal
      else
        if x2 < y2 do
          :smaller
        else
          :greater
        end
      end
    else
      if x1 < y1 do
        :smaller
      else
        :greater
      end
    end
  end

  defp step(route, steps, x, y) do
    Enum.reduce(1..steps, route, fn _, route_new ->
      {last_x, last_y, count} = List.first(route_new)
      {new_x, new_y} = {last_x + x, last_y + y}
      [{new_x, new_y, count + 1} | route_new]
    end)
  end

  defp manhattan({x, y, _}) do
    abs(x) + abs(y)
  end

  defp combined_steps({{_, _, steps1}, {_, _, steps2}}) do
    steps1 + steps2
  end
end

#from tabulate import tabulate

with open('input','r') as f:
    data = f.read().splitlines()

for i in range(len(data)):#overdone to do it like this. But this way it isn't hardcoded to only dealing with two lines. Although the rest of the code is.. *shrug*
    data[i] = data[i].split(',')

print(data)

#make big array that has everything in it 20000x20000 should be big enough...
LinesArray = [['.' for i in range(20000)] for i in range(20000)]#Normally 2000

'''
Key:
5 = starting position
1 = part of line 1
2 = part of line 2
3 = intersection of both lines
blank = nothing here
'''
LinesArray[10000][10000] = 5#start point. Normally 1000

Position = [10000,10000]#y,x. Normally 1000,1000
PositionOriginal = Position#Store this for later...

#now to plot the lines
for i in range(len(data)):#Do once for each line. If len(data) is not 2, this will break.
    Position = [10000,10000]#y,x. Normally 1000,1000
    if i == 0:
        CurrentLine = 1
    elif i == 1:
        CurrentLine = 2
    else:
        print('More lines are not supported!!')
        break
    for j in range(len(data[i])):
        Direction = data[i][j][:1]
        Amount = data[i][j][1:]
        #print(Direction, Amount)
        #print(Position)
        if Direction == 'U':
            for k in range(int(Amount)):
                #print(k)
                if LinesArray[Position[0] - k - 1][Position[1]] == CurrentLine - 1 or LinesArray[Position[0] - k - 1][Position[1]] == 3:#neverhappens on first run. does on second
                    LinesArray[Position[0] - k - 1][Position[1]] = 3
                else:
                    LinesArray[Position[0] - k - 1][Position[1]] = CurrentLine
            Position[0] = Position[0] - k - 1
            #print(Position)
            #LinesArray[Position[0]][1] = 2
            #print(tabulate(LinesArray))
        elif Direction == 'D':
            for k in range(int(Amount)):
                #print(k)
                if LinesArray[Position[0] + k + 1][Position[1]] == CurrentLine - 1 or LinesArray[Position[0] + k + 1][Position[1]] == 3:
                    LinesArray[Position[0] + k + 1][Position[1]] = 3
                else:
                    LinesArray[Position[0] + k + 1][Position[1]] = CurrentLine
            Position[0] = Position[0] + k + 1
            #print(Position)
            #LinesArray[Position[0]][1] = 2
            #print(tabulate(LinesArray))
        elif Direction == 'L':
            for k in range(int(Amount)):
                #print(k)
                if LinesArray[Position[0]][Position[1] - k - 1] == CurrentLine - 1 or LinesArray[Position[0] - k - 1][Position[1]] == 3:
                    LinesArray[Position[0]][Position[1] - k - 1] = 3
                else:
                    LinesArray[Position[0]][Position[1] - k - 1] = CurrentLine
            Position[1] = Position[1] - k - 1
            #print(Position)
            #LinesArray[Position[0]][1] = 2
            #print(tabulate(LinesArray))
        elif Direction == 'R':
            for k in range(int(Amount)):
                #print(k)
                if LinesArray[Position[0]][Position[1] + k + 1] == CurrentLine -1 or LinesArray[Position[0]][Position[1] + k + 1] == 3:
                    LinesArray[Position[0]][Position[1] + k + 1] = 3
                else:
                    LinesArray[Position[0]][Position[1] + k + 1] = CurrentLine
            Position[1] = Position[1] + k + 1
            #print(Position)
            #LinesArray[Position[0]][1] = 2
            #print(tabulate(LinesArray))
        else:
            print('There is an issue')
            break

#print('---------------')
#Now do the manhattan distance thing to find the closest point...
ListOfIntersections = []
for i in range(len(LinesArray)):
    for j in range(len(LinesArray[i])):
        if LinesArray[i][j] == 3:#i is down from top, j is from left going right
            SubList = []
            SubList.append(i)
            SubList.append(j)
            ListOfIntersections.append(SubList)
            #print(ListOfIntersections)
            


#print(ListOfIntersections)

#Now find the one that is the closest...
ShortestDistance = -1
for i in range(len(ListOfIntersections)):
    XDistance = ListOfIntersections[i][1] - PositionOriginal[1]
    YDistance = ListOfIntersections[i][0] - PositionOriginal[0]
    if XDistance < 0:
        XDistance = XDistance * -1
    if YDistance < 0:
        YDistance = YDistance * -1
    ManhattanDistance = XDistance + YDistance
    #print('pos orig', PositionOriginal)
    #print(ListOfIntersections[i][1], PositionOriginal[1], XDistance)
    #print(ListOfIntersections[i][0], PositionOriginal[0], YDistance)
    #print(ManhattanDistance)
    if ManhattanDistance < ShortestDistance or ShortestDistance == -1:
        ShortestDistance = ManhattanDistance

print('Answer: ',ShortestDistance)

This is horrible. I used an absolutely massive two dimensional array to visualise the wires. When it runs it uses about 3.2GB's of ram and takes a minute or so to get the result.

I used tabulate to visualise the grid when it was small (10x10) for testing. I took this out for the final, massive array.

I kept on having to increase the size of the array, because the wires kept on going outside of it and causing errors. It worked at 20,000 by 20,000. (very big).

Also I kept on having weird issues where I would set an array to be equal to another array, and then if I changed the first array, the second one would also change. I fixed that by using some jank. For attempt 2 I learned when you say array = array2, they are both the same object, so you need to say array = array2[:] to make them separate.

So perhaps visualisation is not so great when dealing with very big things.

I thought that this was so bad that I should really give it another crack. But I think attempt 2 is arguably worse.

with open('input','r') as f:
    data = f.read().splitlines()

for i in range(len(data)):#overdone to do it like this. But this way it isn't hardcoded to only dealing with two lines. Although the rest of the code is.. *shrug*
    data[i] = data[i].split(',')

History = []#Always clear your history. Well... not this one.
StartPos = [0,0]#x,y (the middle of our 'cartesian plane' if we want to visualise)
CurrentPos = StartPos[:]#[:] so that it makes a new object
#print(CurrentPos)
#print(StartPos)
for i in range(len(data[0])):#first line
    print(len(data[0]), i)
    Direction = data[0][i][:1]
    Amount = int(data[0][i][1:])
    if Direction == 'U':
        for j in range(Amount):
            #print(CurrentPos)
            CurrentPos[1] = CurrentPos[1] + 1
            #if not CurrentPos in History:#this should save some time. Or perhaps its more checks so it takes longer??
            #    History.append(CurrentPos[:])
            History.append(CurrentPos[:])
    elif Direction == 'D':
        for j in range(Amount):
            #print(CurrentPos)
            CurrentPos[1] = CurrentPos[1] - 1
            #if not CurrentPos in History:#this should save some time. Or perhaps its more checks so it takes longer??
            #    History.append(CurrentPos[:])
            History.append(CurrentPos[:])
    elif Direction == 'L':
        for j in range(Amount):
            #print(CurrentPos)
            CurrentPos[0] = CurrentPos[0] - 1
            #if not CurrentPos in History:#this should save some time. Or perhaps its more checks so it takes longer??
            #    History.append(CurrentPos[:])
            History.append(CurrentPos[:])
    elif Direction == 'R':
        for j in range(Amount):
            #print(CurrentPos)
            CurrentPos[0] = CurrentPos[0] + 1
            #if not CurrentPos in History:#this should save some time. Or perhaps its more checks so it takes longer??
            #    History.append(CurrentPos[:])
            History.append(CurrentPos[:])
    else:
        print('Something has probably just caught fire...')
        break
#print(History)

CurrentPos = StartPos[:]
IntersectionList = []

for i in range(len(data[1])):#second line!
    print(len(data[1]), i)
    Direction = data[1][i][:1]
    Amount = int(data[1][i][1:])
    if Direction == 'U':
        for j in range(Amount):
            #print(CurrentPos)
            CurrentPos[1] = CurrentPos[1] + 1
            if CurrentPos in History:
                IntersectionList.append(CurrentPos[:])
    elif Direction == 'D':
        for j in range(Amount):
            #print(CurrentPos)
            CurrentPos[1] = CurrentPos[1] - 1
            if CurrentPos in History:
                IntersectionList.append(CurrentPos[:])
    elif Direction == 'L':
        for j in range(Amount):
            #print(CurrentPos)
            CurrentPos[0] = CurrentPos[0] - 1
            if CurrentPos in History:
                IntersectionList.append(CurrentPos[:])
    elif Direction == 'R':
        for j in range(Amount):
            #print(CurrentPos)
            CurrentPos[0] = CurrentPos[0] + 1
            if CurrentPos in History:
                IntersectionList.append(CurrentPos[:])
    else:
        print('Something has probably just caught fire... But in a different spot!')
        break

#print(IntersectionList)

#All the stuff down here is pretty similar to attempt 1
#Now find the one that is the closest...
ShortestDistance = -1
for i in range(len(IntersectionList)):
    XDistance = IntersectionList[i][0] - StartPos[0]
    YDistance = IntersectionList[i][1] - StartPos[1]
    if XDistance < 0:
        XDistance = XDistance * -1
    if YDistance < 0:
        YDistance = YDistance * -1
    ManhattanDistance = XDistance + YDistance
    #print('pos orig', StartPos)
    #print(IntersectionList[i][0], StartPos[0], XDistance)
    #print(IntersectionList[i][1], StartPos[1], YDistance)
    #print(ManhattanDistance)
    if ManhattanDistance < ShortestDistance or ShortestDistance == -1:
        ShortestDistance = ManhattanDistance

print('Answer: ',ShortestDistance)

So I thought, rather than make a massive array, why don't we just record every single place that the first line goes (a different, massive array), and then when figuring out the second line, check each place to see if it's in a spot that the first line has also been. If it is, then record those coordinates. Then do the same figuring out to find the closest one.

The good: This uses significantly less memory than the previous attempt (I didn't measure it but gotop didn't show any massive climbs like attempt 1 did)

The bad: This is very slow. Slower than slow. It took 8 minutes to get the correct answer. The guy who completed this challenge first did it in 2 minutes and 38 seconds. They could program this whole thing ~3x faster than I could run mine.

I tried reducing this time by checking if something has already been added to the "history" of the first line and then not adding it a second time (or perhaps more), reducing the size of the array and therefore hopefully making the comparisons quicker. But this made more checks have to be done, so it actually slowed it down. The modified code takes 11 minutes and 40 seconds to run. Ooops! I left that check code in but commented out.

I noticed that when it was being slow, it was getting slow in the "for j in range(Amount):" loops.

When the loops do an "if not CurrentPos in History:" check (for the first line, this is the thing I added to try speed it up that actually slowed it) they go slow. When they check is not present, the first part of the code completes very quickly.

Of course the "if CurrentPos in History:" checks are pretty necessary on the second line because how else would I check if the lines intersect. So this part is still slow.

Perhaps I could speed it up by just storing the end points of each line segment (eg 200,200 and 200,220 could be one segment) and then checking if the proposed spot falls within that range. I'm not sure if this will be faster though and I'm too tired at the moment to try it. Perhaps another time.

Please don't make me feel too bad about what I've just done.

use std::fs;
use std::vec::Vec;

struct Line {
    horizontal: bool,
    x: isize,
    y: isize,
    length: isize,
}

impl Line {
    fn new (line: &str, x: &mut isize, y: &mut isize) -> Line {
        let (dir, length) = line.split_at(1);
        let length = length.parse().unwrap();

        let ret;
        match dir {
            "R" => {
                ret = Line {horizontal : true, x : *x, y : *y, length : length};
                *x += length;
            }
            "D" => {
                ret = Line {horizontal : false, x : *x, y : *y, length : -1 * length};
                *y -= length;
            }
            "L" => {
                ret = Line {horizontal : true, x : *x, y : *y, length : -1 * length};
                *x -= length;
            }
            "U" => {
                ret = Line {horizontal : false, x : *x, y : *y, length : length};
                *y += length;
            }
            _ => {panic!("Cannot parse line: {}", line);}
        }

        ret
    }

    /* Returns the point at which the lines cross (if they do cross)
     * Only used for part 1
     */
    fn cross_point(&self, other: &Line) -> Option<(isize, isize)> {
        match (self.horizontal, other.horizontal) {
            (true, false) => {
                let (self_lower, self_upper) = order(self.x, self.x + self.length);
                let (other_lower, other_upper) = order(other.y, other.y + other.length);
                if self_lower < other.x
                    && self_upper > other.x
                    && other_lower < self.y
                    && other_upper > self.y {
                        return Some((other.x, self.y))
                    }
            }
            (false, true) => {
                let (self_lower, self_upper) = order(self.y, self.y + self.length);
                let (other_lower, other_upper) = order(other.x, other.x + other.length);
                if self_lower < other.y
                    && self_upper > other.y
                    && other_lower < self.x
                    && other_upper > self.x {
                        return Some((self.x, other.y))
                    }
            }
            _ => {}
        }

        None
    }

    /* Returns the length of wire, until the lines cross, for each line (if they do cross)
     * Only used for part 2
     */
    fn cross_length(&self, other: &Line) -> Option<(isize, isize)> {
        match (self.horizontal, other.horizontal) {
            (true, false) => {
                let (self_lower, self_upper) = order(self.x, self.x + self.length);
                let (other_lower, other_upper) = order(other.y, other.y + other.length);
                if self_lower < other.x
                    && self_upper > other.x
                    && other_lower < self.y
                    && other_upper > self.y {
                        return Some(((other.x - self.x).abs(), (self.y - other.y).abs()))
                    }
            }
            (false, true) => {
                let (self_lower, self_upper) = order(self.y, self.y + self.length);
                let (other_lower, other_upper) = order(other.x, other.x + other.length);
                if self_lower < other.y
                    && self_upper > other.y
                    && other_lower < self.x
                    && other_upper > self.x {
                        return Some(((self.x - other.x).abs(), (other.y - self.y).abs()))
                    }
            }
            _ => {}
        }

        None
    }

}

fn main() {
    let paths = fs::read_to_string("input").unwrap();
    let paths: Vec<&str> = paths.split('\n').collect();
    let mut x = 0;
    let mut y = 0;
    let path_1: Vec<Line> = paths[0].split(',').map(|line| {Line::new(line.trim(), &mut x, &mut y)}).collect();
    x = 0;
    y = 0;
    let path_2: Vec<Line> = paths[1].split(',').map(|line| {Line::new(line.trim(), &mut x, &mut y)}).collect();

    println!("The closest point by Manhattan distance (Part 1): {}", manhattan_distance_of_closest_point(&path_1, &path_2));
    println!("The closest point by wire distance (Part 2): {}", wire_distance_of_closest_point(&path_1, &path_2));
}

/* Finds the closest point by Manhattan distance, and returns that distance.
 * Only used for part 1
 */
fn manhattan_distance_of_closest_point(path_1: &Vec<Line>, path_2: &Vec<Line>) -> isize {
    let mut closest_point: isize = isize::max_value();
    for line_1 in path_1 {
        for line_2 in path_2 {
            match line_1.cross_point(line_2) {
                Some((x, y)) => {
                    if x.abs() + y.abs() < closest_point {
                        closest_point = x.abs() + y.abs();
                    }
                }
                None => {}
            }
        }
    }

    closest_point
}

/* Finds the closest point by cumulative wire length, and returns that distance.
 * Only used for part 2
 */
fn wire_distance_of_closest_point(path_1: &Vec<Line>, path_2: &Vec<Line>) -> isize {
    let mut closest_point: isize = isize::max_value();
    let mut line_1_length = 0;
    for line_1 in path_1 {
        let mut line_2_length = 0;
        for line_2 in path_2 {
            match line_1.cross_length(line_2) {
                Some((line_1_cross_dist, line_2_cross_dist)) => {
                    if line_1_length + line_1_cross_dist + line_2_length + line_2_cross_dist < closest_point {
                        closest_point = line_1_length + line_1_cross_dist + line_2_length + line_2_cross_dist;
                    }
                }
                None => {}
            }
            line_2_length += line_2.length.abs();
        }
        line_1_length += line_1.length.abs();
    }

    closest_point
}

#[inline]
fn order(n: isize, m: isize) -> (isize, isize) {
    if n < m {
        return (n, m);
    }
    (m, n)
}

#!/usr/bin/awk -f
{
    split($0, path, ",")
    wire += 1
    x = 0
    y = 0

    for (i = 1; i <= length(path); ++i) {
        c = substr(path[i], 1, 1)
        j = int(substr(path[i], 2))
        for (k = 0; k < j; ++k) {
            if (c == "U")
                y += 1
            else if (c == "D")
                y -= 1
            else if (c == "L")
                x -= 1
            else if (c == "R")
                x += 1

            if (grid[x","y] == wire-1)
                grid[x","y] = wire
        }
    }
}

END {
    nearest = 0
    for (i in grid) {
        if (grid[i] == 2) {
            split(i, coordinates, ",")
            for (j = 1; j <= 2; ++j)
                sub(/^-/, "", coordinates[j])

            distance = int(coordinates[1]) + int(coordinates[2])
            if (distance < nearest || nearest == 0)
                nearest = distance
        }
    }

    print nearest
}

#!/usr/bin/awk -f
{
    split($0, path, ",")
    wire += 1
    step = 0
    x = 0
    y = 0

    for (i = 1; i <= length(path); ++i) {
        c = substr(path[i], 1, 1)
        j = int(substr(path[i], 2))
        for (k = 0; k < j; ++k) {
            step += 1
            if (c == "U")
                y += 1
            else if (c == "D")
                y -= 1
            else if (c == "L")
                x -= 1
            else if (c == "R")
                x += 1

            if (grid[x","y] == wire-1) {
                grid[x","y] = wire
                steps[x","y] += step
            }
        }
    }
}

END {
    nearest = 0
    for (i in grid)
        if (grid[i] == 2)
            if (steps[i] < nearest || nearest == 0)
                nearest = steps[i]

    print nearest
}

def read_paths(file_name):

    with open(file_name, 'r') as fid:
        path_1 = fid.readline().strip().split(',')
        path_2 = fid.readline().strip().split(',')

    return path_1, path_2

# TODO: Make another version that finds the locations again and then use that to
# the number of steps needed
def find_corners(path):

    corners = [[0, 0]]

    for move in path:

        num_moves = int(move[1:])
        initial_pos = corners[-1]

        if move[0] == 'R':

            new_pos = [initial_pos[0] + num_moves, initial_pos[1]]
            corners.append(new_pos)

        elif move[0] == 'L':

            new_pos = [initial_pos[0] - num_moves, initial_pos[1]]
            corners.append(new_pos)

        elif move[0] == 'D':

            new_pos = [initial_pos[0], initial_pos[1] - num_moves]
            corners.append(new_pos)

        elif move[0] == 'U':

            new_pos = [initial_pos[0], initial_pos[1] + num_moves]
            corners.append(new_pos)

        else:
            raise ValueError("Invalid direction letter!")

    return corners

def find_intersections(corners_1, path_1, corners_2, path_2):
    intersections = []
    step_idx = []
    for idx in range(len(path_1)):
        for jdx in range(len(path_2)):
            move_1 = path_1[idx]
            move_2 = path_2[jdx]

            # Check cases that could intersect
            if move_1[0] == 'R' and move_2[0] == 'U':
                if (corners_1[idx][0] < corners_2[jdx][0] and
                    corners_1[idx+1][0] > corners_2[jdx][0] and
                    corners_1[idx][1] > corners_2[jdx][1] and
                    corners_1[idx][1] < corners_2[jdx+1][1]):
                    intersections.append([corners_2[jdx][0], corners_1[idx][1]])
                    step_idx.append([idx, jdx])
            elif move_1[0] == 'R' and move_2[0] == 'D':
                if (corners_1[idx][0] < corners_2[jdx][0] and
                    corners_1[idx+1][0] > corners_2[jdx][0] and
                    corners_1[idx][1] < corners_2[jdx][1] and
                    corners_1[idx][1] > corners_2[jdx+1][1]):
                    intersections.append([corners_2[jdx][0], corners_1[idx][1]])
                    step_idx.append([idx, jdx])
            elif move_1[0] == 'L' and move_2[0] == 'U':
                if (corners_1[idx][0] > corners_2[jdx][0] and
                    corners_1[idx+1][0] < corners_2[jdx][0] and
                    corners_1[idx][1] > corners_2[jdx][1] and
                    corners_1[idx][1] < corners_2[jdx+1][1]):
                    intersections.append([corners_2[jdx][0], corners_1[idx][1]])
                    step_idx.append([idx, jdx])
            elif move_1[0] == 'L' and move_2[0] == 'D':
                if (corners_1[idx][0] > corners_2[jdx][0] and
                    corners_1[idx+1][0] < corners_2[jdx][0] and
                    corners_1[idx][1] < corners_2[jdx][1] and
                    corners_1[idx][1] > corners_2[jdx+1][1]):
                    intersections.append([corners_2[jdx][0], corners_1[idx][1]])
                    step_idx.append([idx, jdx])
            elif move_1[0] == 'U' and move_2[0] == 'R':
                if (corners_1[idx][1] < corners_2[jdx][1] and
                    corners_1[idx+1][1] > corners_2[jdx][1] and
                    corners_1[idx][0] > corners_2[jdx][0] and
                    corners_1[idx][0] < corners_2[jdx+1][0]):
                    intersections.append([corners_1[idx][0], corners_2[jdx][1]])
                    step_idx.append([idx, jdx])
            elif move_1[0] == 'U' and move_2[0] == 'L':
                if (corners_1[idx][1] < corners_2[jdx][1] and
                    corners_1[idx+1][1] > corners_2[jdx][1] and
                    corners_1[idx][0] < corners_2[jdx][0] and
                    corners_1[idx][0] > corners_2[jdx+1][0]):
                    intersections.append([corners_1[idx][0], corners_2[jdx][1]])
                    step_idx.append([idx, jdx])
            elif move_1[0] == 'D' and move_2[0] == 'R':
                if (corners_1[idx][1] > corners_2[jdx][1] and
                    corners_1[idx+1][1] < corners_2[jdx][1] and
                    corners_1[idx][0] > corners_2[jdx][0] and
                    corners_1[idx][0] < corners_2[jdx+1][0]):
                    intersections.append([corners_1[idx][0], corners_2[jdx][1]])
                    step_idx.append([idx, jdx])
            elif move_1[0] == 'D' and move_2[0] == 'L':
                if (corners_1[idx][1] > corners_2[jdx][1] and
                    corners_1[idx+1][1] < corners_2[jdx][1] and
                    corners_1[idx][0] < corners_2[jdx][0] and
                    corners_1[idx][0] > corners_2[jdx+1][0]):
                    intersections.append([corners_1[idx][0], corners_2[jdx][1]])
                    step_idx.append([idx, jdx])


    return intersections, step_idx

def determine_closest(intersections):

    distances = []


    for intersection in intersections:
        distances.append(abs(intersection[0]) + abs(intersection[1]))

    return min(distances)

def least_steps(intersections, corners_1, corners_2, path_1, path_2, moves):

    total_steps = []

    for idx in range(len(intersections)):

        steps_1 = 0
        steps_2 = 0

        for jdx in range(moves[idx][0]):
            steps_1 += int(path_1[jdx][1:])

        for jdx in range(moves[idx][1]):
            steps_2 += int(path_2[jdx][1:])

        steps_1 += (abs(intersections[idx][0] - corners_1[moves[idx][0]][0])
                    + abs(intersections[idx][1] - corners_1[moves[idx][0]][1]))
        steps_2 += (abs(intersections[idx][0] - corners_2[moves[idx][1]][0])
                    + abs(intersections[idx][1] - corners_2[moves[idx][1]][1]))

        total_steps.append(steps_1 + steps_2)

    return min(total_steps)

def closest_intersection_dist(data_file):
    path_1, path_2 = read_paths(data_file)

    corners_1 = find_corners(path_1)
    corners_2 = find_corners(path_2)

    intersections, steps = find_intersections(corners_1, path_1, corners_2, path_2)

    return determine_closest(intersections)

def least_steps_intersection(data_file):

    path_1, path_2 = read_paths(data_file)

    corners_1 = find_corners(path_1)
    corners_2 = find_corners(path_2)

    intersections, moves = find_intersections(corners_1, path_1, corners_2, path_2)

    return least_steps(intersections, corners_1, corners_2, path_1, path_2, moves)

test_files = ["Test1.txt", "Test2.txt"]
test_results_1 = [159, 135]
test_results_2 = [610, 410]
input_file = "PathInput.txt"


# Run our tests!
print("Running tests")
for idx in range(len(test_files)):

    distance = closest_intersection_dist(test_files[idx])

    assert distance  == test_results_1[idx]

print("Tests passed!")

print("Running problem data...")

distance = closest_intersection_dist(input_file)

print("The closest distance found is {}".format(distance))

print("Running tests")

for idx in range(len(test_files)):

    num_steps = least_steps_intersection(test_files[idx])

    assert num_steps == test_results_2[idx]

print("Tests passed!")

print("Running problem data...")

num_steps = least_steps_intersection(input_file)

print("The least steps instersection takes {} steps.".format(num_steps))