advent-of-code-2019

3.scala

import scala.io.Source
import scala.collection.mutable.ListBuffer
import scala.math.{min,max,abs}

class Point(var x: Int, var y: Int) {

  override def toString = "x: " + x + ", y: " + y
  override def equals(o: Any) = o match {
    case that: Point => that.x == this.x && that.y == this.y
    case _ => false
  }
  override def hashCode = x.hashCode + ":".hashCode + y.hashCode

  def add(that: Point): Point = new Point(x + that.x, y + that.y)
}

def direction(sign: Char, length: Int): Point = sign match {
  case 'U' => new Point(0, length)
  case 'D' => new Point(0, length * -1)
  case 'L' => new Point(length * -1, 0)
  case 'R' => new Point(length, 0)
}

// use slope to determine orientation
// taken from my reference book on 3d mathmatics
def orientation(p: Point, q: Point, r: Point): Int = {
  val cal: Int = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y) // use cross-product to determine difference in angle

  if (cal == 0) return 0; // CO-LINEAR
  if (cal > 0) {
    1
  } else {
    2
  }
}

def pathToPointList(p: Vector[String]): List[Point] = {
  val path = new ListBuffer[Point]()
  path += new Point(0, 0)

  for (vec <- p) {
    val len :+ dir = vec.reverse.toVector

    val nextPoint = path.last.add(direction(dir, len.reverse.mkString.toInt))

    path += nextPoint
  }

  path.toList
}

class LineSegment(val startPoint: Point, val endPoint: Point) {
  var path = ListBuffer[Point](startPoint, endPoint)

  def isPointColinear(p: Point): Boolean = {
    // NOTE: Assumes the path is co-linear; incorrect results otherwise
    if (orientation(path.head, path.last, p) == 0) return true

    false
  }

  override def toString = "Start: (" + path.head + ") End: (" + path.last + ")"

  def addPoint(p: Point): Unit = path += p
  def getLastPoint(): Point = path.last
  def getOrderedContinuity(): Array[Point] = {
    // Each line segment is assumed to have a slope of 0. Populate a set of points along the segment's primary axis
    val x = Array.range(min(path.head.x, path.last.x), max(path.last.x, path.head.x))
    val y = Array.range(min(path.head.y, path.last.y), max(path.last.y, path.head.y))
    if (x.size > 1) {
      x.map(new Point(_, path.head.y))
    } else {
      y.map(new Point(path.head.x, _))
    }
  }
  def intersects(that: LineSegment): Array[Point] = {
    getOrderedContinuity.intersect(that.getOrderedContinuity)
  }
}

class ColinearLineSegmentBuilder(val startPoint: Point, val endPoint: Point) {
  var segments = ListBuffer[LineSegment](new LineSegment(startPoint, endPoint))

  def addPoint(point: Point): Unit = {
    val curSeg = segments.last

    if (curSeg.isPointColinear(point)) {
      curSeg.addPoint(point)
    } else {
      segments += new LineSegment(curSeg.getLastPoint, point)
    }
  }

  def getLineSegments(): List[LineSegment] = segments.toList
}

class LineSegmentShape(val segments: List[LineSegment]) {
  def intersections(that: LineSegmentShape): List[Point] = {
    val i = ListBuffer[Point]()

    for (l <- segments) {
      for (o <- that.segments) {
        val p = l.intersects(o).toList

        i ++= p
      }
    }

    i.toList
  }

  def distanceToPoint(p: Point): Int = {
    var steps = 0
    for (l <- segments) {
      val s = l.getOrderedContinuity
      val i = s.indexOf(p)

      if (i != -1) {
        steps += i

        return steps
      } else {
        steps += s.size
      }
    }

    0
  }
}

def getManhattanDistance(origin: Point, target: Point): Int = {
  abs(origin.x - target.x) + abs(origin.y - target.y)
}

val input = Source.fromFile("input.txt").getLines()
val wireA = input.next.split(",").toVector
val wireB = input.next.split(",").toVector

val wireAPath = pathToPointList(wireA)
val wireBPath = pathToPointList(wireB)

val lba = new ColinearLineSegmentBuilder(wireAPath.take(2).head, wireAPath.take(2).last)
val lbb = new ColinearLineSegmentBuilder(wireBPath.take(2).head, wireBPath.take(2).last)
wireAPath.drop(2).map(lba.addPoint(_)) // This is bad (implicit state mutation), but it's late and I just want to go home
wireBPath.drop(2).map(lbb.addPoint(_))

val shapeA = new LineSegmentShape(lba.getLineSegments)
val shapeB = new LineSegmentShape(lbb.getLineSegments)
val intersections = shapeA.intersections(shapeB)
val shapeADistances = intersections.map(i => shapeA.distanceToPoint(i))
val shapeBDistances = intersections.map(i => shapeB.distanceToPoint(i))

val distances = intersections.map(getManhattanDistance(new Point(0,0), _))
println("Distances: " + distances + "; min: " + distances.min)
println("Thus, answer to part 1 is: " + distances.min)

val stepCombinations = (shapeADistances.drop(1) zip shapeBDistances.drop(1)).map(t => t._1 + t._2)
println("Part 2 answer is least of: " + stepCombinations)
println("Thus, part 2 answer is: " + stepCombinations.min)