codetrotter_aoc_2019_solutions 0.9.0

/*
 * Copyright (c) 2019, 2020 Erik Nordstrøm <erik@nordstroem.no>
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

solution_printer!(3, print_solution, input_generator, INPUT, solve_part_1, solve_part_2);

pub const INPUT: &str = include_str!("../input/2019/day3.txt");

/// ### Day 3: Crossed Wires
///
/// [https://adventofcode.com/2019/day/3](https://adventofcode.com/2019/day/3)
///
/// The gravity assist was successful, and you're well on your way to the Venus
/// refuelling station.  During the rush back on Earth, the fuel management
/// system wasn't completely installed, so that's next on the priority list.
///
/// Opening the front panel reveals a jumble of wires. Specifically, *two wires*
/// are connected to a central port and extend outward on a grid.  You trace the
/// path each wire takes as it leaves the central port, one wire per line of
/// text (your puzzle input).
///
/// The wires twist and turn, but the two wires occasionally cross paths. To
/// fix the circuit, you need to *find the intersection point closest to the
/// central port*. Because the wires are on a grid, use the [Manhattan distance](https://en.wikipedia.org/wiki/Taxicab_geometry)
/// for this measurement. While the wires do technically cross right at the
/// central port where they both start, this point does not count, nor does a
/// wire count as crossing with itself.
///
/// For example, if the first wire's path is `R8,U5,L5,D3`, then starting from
/// the central port (`o`), it goes right `8`, up `5`, left `5`, and finally down `3`:
///
/// ```text
/// ...........
/// ...........
/// ...........
/// ....+----+.
/// ....|....|.
/// ....|....|.
/// ....|....|.
/// .........|.
/// .o-------+.
/// ...........
/// ```
///
/// Then, if the second wire's path is `U7,R6,D4,L4`, it goes up `7`, right `6`, down
/// `4`, and left `4`:
///
/// ```text
/// ...........
/// .+-----+...
/// .|.....|...
/// .|..+--X-+.
/// .|..|..|.|.
/// .|.-X--+.|.
/// .|..|....|.
/// .|.......|.
/// .o-------+.
/// ...........
/// ```
///
/// These wires cross at two locations (marked `X`), but the lower-left one is
/// closer to the central port: its distance is `3 + 3 = 6`.
///
/// Here are a few more examples:
///
///   - ```text
///     R75,D30,R83,U83,L12,D49,R71,U7,L72
///     U62,R66,U55,R34,D71,R55,D58,R83
///     ```
///     = distance `159`
///   - ```text
///     R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
///     U98,R91,D20,R16,D67,R40,U7,R15,U6,R7
///     ```
///     = distance `135`
///
/// *What is the Manhattan distance* from the central port to the closest
/// intersection?
///
/// ### Examples
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_03::{input_generator, solve_part_1};
/// const EX1INPUT: &str =
///   "R8,U5,L5,D3\n\
///    U7,R6,D4,L4";
/// assert_eq!(solve_part_1(&mut input_generator(EX1INPUT)), 6);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_03::{input_generator, solve_part_1};
/// const EX2INPUT: &str =
///   "R75,D30,R83,U83,L12,D49,R71,U7,L72\n\
///    U62,R66,U55,R34,D71,R55,D58,R83";
/// assert_eq!(solve_part_1(&mut input_generator(EX2INPUT)), 159);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_03::{input_generator, solve_part_1};
/// const EX3INPUT: &str =
///   "R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51\n\
///    U98,R91,D20,R16,D67,R40,U7,R15,U6,R7";
/// assert_eq!(solve_part_1(&mut input_generator(EX3INPUT)), 135);
/// ```
///
/// ### Solution
///
/// ⚠️ SPOILER ALERT ⚠️
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_03::{INPUT, input_generator, solve_part_1};
/// assert_eq!(solve_part_1(&mut input_generator(INPUT)), 1064);
/// ```
pub fn solve_part_1 (input_wire_pair: &(Vec<WireSegment>, Vec<WireSegment>)) -> u16
{
  let mut min_manhattan_distance = std::u16::MAX;

  for (horizontal_segment, vertical_segment) in WireSegmentIntersectionFinder::new(&input_wire_pair.0, &input_wire_pair.1)
  {
    let x_distance = if vertical_segment.x0   >= 0 { vertical_segment.x0   } else { -vertical_segment.x0   };
    let y_distance = if horizontal_segment.y0 >= 0 { horizontal_segment.y0 } else { -horizontal_segment.y0 };

    let manhattan_distance = (x_distance + y_distance) as u16;

    if manhattan_distance < min_manhattan_distance
    {
      min_manhattan_distance = manhattan_distance;
    }
  }

  min_manhattan_distance
}

#[derive(PartialEq)]
pub enum Orientation { Vertical, Horizontal }

#[derive(PartialEq)]
pub enum Direction   { Up, Right, Down, Left }

pub struct WireSegment
{
  orientation: Orientation,
  direction: Direction,
  distance_walked: i32,
  x0: i32,
  y0: i32,
  x1: i32,
  y1: i32,
}

impl WireSegment
{
  fn new (orientation: Orientation, direction: Direction, distance_walked: i32, x_prev: i32, y_prev: i32, x_end: i32, y_end: i32) -> Self
  {
    let (x0, x1) = if x_prev <= x_end { (x_prev, x_end) } else { (x_end, x_prev) };
    let (y0, y1) = if y_prev <= y_end { (y_prev, y_end) } else { (y_end, y_prev) };

    Self { orientation, direction, distance_walked, x0, y0, x1, y1, }
  }
}

fn wire_from_single_line_str (single_line: &str) -> Vec<WireSegment>
{
  let mut wire_segments = vec![];

  let mut x_prev = 0;
  let mut y_prev = 0;
  let mut distance_walked = 0;

  for wire_segment_str in single_line.split(',')
  {
    let mut x_end = x_prev;
    let mut y_end = y_prev;

    let wire_segment_length = &wire_segment_str[1..].parse::<i32>().unwrap();

    let (orientation, direction) = match &wire_segment_str.chars().next().unwrap()
    {
      'U' => { y_end += wire_segment_length; (Orientation::Vertical,   Direction::Up   ) },
      'R' => { x_end += wire_segment_length; (Orientation::Horizontal, Direction::Right) },
      'D' => { y_end -= wire_segment_length; (Orientation::Vertical,   Direction::Down ) },
      'L' => { x_end -= wire_segment_length; (Orientation::Horizontal, Direction::Left ) },
      _ => panic!("Bad wire segment format."),
    };

    wire_segments.push(WireSegment::new(orientation, direction, distance_walked, x_prev, y_prev, x_end, y_end));

    x_prev = x_end;
    y_prev = y_end;
    distance_walked += wire_segment_length;
  }

  wire_segments
}

pub fn input_generator (input: &str) -> (Vec<WireSegment>, Vec<WireSegment>)
{
  let mut str_lines = input.lines();

  let wire1 = wire_from_single_line_str(str_lines.next().unwrap());
  let wire2 = wire_from_single_line_str(str_lines.next().unwrap());

  (wire1, wire2)
}

struct WireSegmentIntersectionFinder<'a>
{
  segments_a: &'a Vec<WireSegment>,
  index_a: usize,
  vertical_segments_b: Vec<&'a WireSegment>,
  index_vb: usize,
  horizontal_segments_b: Vec<&'a WireSegment>,
  index_hb: usize,
}

impl<'a> WireSegmentIntersectionFinder<'a>
{
  fn new (wire_segments_a: &'a Vec<WireSegment>, wire_segments_b: &'a Vec<WireSegment>) -> Self
  {
    let mut vertical_segments_b   = vec![];
    let mut horizontal_segments_b = vec![];

    for segment in wire_segments_b
    {
      if segment.orientation  == Orientation::Vertical { vertical_segments_b.push(segment); }
      else                                             { horizontal_segments_b.push(segment); }
    }

    Self
    {
      segments_a: wire_segments_a,
      index_a: 0,
      vertical_segments_b,
      index_vb: 0,
      horizontal_segments_b,
      index_hb: 0,
    }
  }
}

fn segments_intersect (horizontal_segment: &WireSegment, vertical_segment: &WireSegment) -> bool
{
  horizontal_segment.x0 < vertical_segment.x0 && horizontal_segment.x1 > vertical_segment.x1
    && vertical_segment.y0 < horizontal_segment.y0 && vertical_segment.y1 > horizontal_segment.y1
}

impl<'a> Iterator for WireSegmentIntersectionFinder<'a>
{
  type Item = (&'a WireSegment, &'a WireSegment);

  fn next (&mut self) -> Option<Self::Item>
  {
    for segment_a in &self.segments_a[self.index_a..]
    {
      if segment_a.orientation == Orientation::Horizontal
      {
        let horizontal_segment = segment_a;
        for vertical_segment in &self.vertical_segments_b[self.index_vb..]
        {
          self.index_vb += 1;
          if segments_intersect(horizontal_segment, vertical_segment)
            { return Some((horizontal_segment, vertical_segment)); }
        }
        self.index_vb = 0;
      }
      else
      {
        let vertical_segment = segment_a;
        for horizontal_segment in &self.horizontal_segments_b[self.index_hb..]
        {
          self.index_hb += 1;
          if segments_intersect(horizontal_segment, vertical_segment)
            { return Some((horizontal_segment, vertical_segment)); }
        }
        self.index_hb = 0;
      }

      self.index_a += 1;
    }

    None
  }
}

/// ### Day 3, Part Two
///
/// [https://adventofcode.com/2019/day/3#part2](https://adventofcode.com/2019/day/3#part2)
///
/// It turns out that this circuit is very timing-sensitive; you actually need
/// to *minimize the signal delay*.
///
/// To do this, calculate the *number of steps* each wire takes to reach each
/// intersection; choose the intersection where the *sum of both wires' steps* is
/// lowest. If a wire visits a position on the grid multiple times, use the
/// steps value from the *first* time it visits that position when calculating
/// the total value of a specific intersection.
///
/// The number of steps a wire takes is the total number of grid squares the
/// wire has entered to get to that location, including the intersection being
/// considered. Again consider the example from above:
///
/// ```text
/// ...........
/// .+-----+...
/// .|.....|...
/// .|..+--X-+.
/// .|..|..|.|.
/// .|.-X--+.|.
/// .|..|....|.
/// .|.......|.
/// .o-------+.
/// ...........
/// ```
///
/// In the above example, the intersection closest to the central port is
/// reached after `8+5+5+2 = 20` steps by the first wire and `7+6+4+3 = 20` steps
/// by the second wire for a total of `20+20 = 40` steps.
///
/// However, the top-right intersection is better: the first wire takes only
/// `8+5+2 = 15` and the second wire takes only `7+6+2 = 15`, a total of `15+15 = 30`
/// steps.
///
/// Here are the best steps for the extra examples from above:
///
///   - ```text
///     R75,D30,R83,U83,L12,D49,R71,U7,L72
///     U62,R66,U55,R34,D71,R55,D58,R83
///     ```
///     = `610` steps
///   - ```text
///     R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
///     U98,R91,D20,R16,D67,R40,U7,R15,U6,R7
///     ```
///     = `410` steps
///
/// *What is the fewest combined steps the wires must take to reach an
/// intersection?*
///
/// ### Examples
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_03::{input_generator, solve_part_2};
/// const EX1INPUT: &str =
///   "R8,U5,L5,D3\n\
///    U7,R6,D4,L4";
/// assert_eq!(solve_part_2(&mut input_generator(EX1INPUT)), 30);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_03::{input_generator, solve_part_2};
/// const EX2INPUT: &str =
///   "R75,D30,R83,U83,L12,D49,R71,U7,L72\n\
///    U62,R66,U55,R34,D71,R55,D58,R83";
/// assert_eq!(solve_part_2(&mut input_generator(EX2INPUT)), 610);
/// ```
///
/// ```
/// # use codetrotter_aoc_2019_solutions::day_03::{input_generator, solve_part_2};
/// const EX3INPUT: &str =
///   "R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51\n\
///    U98,R91,D20,R16,D67,R40,U7,R15,U6,R7";
/// assert_eq!(solve_part_2(&mut input_generator(EX3INPUT)), 410);
/// ```
///
/// ### Solution
///
/// ⚠️ SPOILER ALERT ⚠️
///
/// ```
/// use codetrotter_aoc_2019_solutions::day_03::{INPUT, input_generator, solve_part_2};
/// assert_eq!(solve_part_2(&mut input_generator(INPUT)), 25676);
/// ```
pub fn solve_part_2 (input_wire_pair: &(Vec<WireSegment>, Vec<WireSegment>)) -> u32
{
  let mut min_walking_distance = std::u32::MAX;

  for (horizontal_segment, vertical_segment) in WireSegmentIntersectionFinder::new(&input_wire_pair.0, &input_wire_pair.1)
  {
    let horizontal_walking_distance_remaining =
      if horizontal_segment.direction == Direction::Right { vertical_segment.x0   - horizontal_segment.x0 }
      else                                                { horizontal_segment.x1 - vertical_segment.x0   };

    let vertical_walking_distance_remaining =
      if vertical_segment.direction == Direction::Up { horizontal_segment.y0 - vertical_segment.y0   }
      else                                           { vertical_segment.y1   - horizontal_segment.y0 };

    let walking_distance =
      (horizontal_segment.distance_walked + vertical_segment.distance_walked +
       horizontal_walking_distance_remaining + vertical_walking_distance_remaining) as u32;

    if walking_distance < min_walking_distance
      { min_walking_distance = walking_distance; }
  }

  min_walking_distance
}