Advent of Code 2019 Day 3 in Scala, or “How I am not a smart programmer, and the importance of taking breaks.” I spent probably 6+ hours on this, when it probably should’ve taken only an hour or two. Also, don’t go look at the subreddit for it, because it’ll make you feel super stupid.
One Over-complicated Solution
Okay, I started working on this, and somehow, turned it into a nightmare of complexity that was painfully slow, and did not work well at all. First of all, let me share you the Wire class I came up with to encapsulate my concept of a Wire.
The Wire Class and Point Class
I tried to use types to describe my problem. My first solution was implemented very poorly. But first, here’s a couple foundational classes I used to “help” me describe the problem. Turns out I overthought it, and made it worse. I had a concept of a Wire, and if it is Horizontal or Vertical. The wire had a List of Points in it. I added a bit of logic to go from a Tuple of Ints to a Point, which was handy.
package is.kow.adventofcode._2019
case class Point(x: Int, y: Int)
object Point {
def apply(pair: (Int, Int)): Point = {
Point(pair._1, pair._2)
}
}
case class Wire(start: Point, end: Point) {
val isVertical: Boolean = start.x == end.x
val isHorizontal: Boolean = start.y == end.y
//BLECH I feel like this is super wrong and lame
val points: List[(Int, Int)] = {
if (isHorizontal) {
val range = if (start.x < end.x) {
(start.x to end.x)
} else {
end.x to start.x
}
val path = range.map(x =>
(x, start.y)
)
val items = if (start.x < end.x) {
path
} else {
path.reverse
}
items.toList
} else {
val range = if (start.y < end.y) {
start.y to end.y
} else {
end.y to start.y
}
val pre = range.map(y =>
(start.x, y))
val finished = if (start.y < end.y) {
pre
} else {
pre.reverse
}
finished.toList
}
}
def intersects2(other: Wire): Option[Point] = {
val intersection = this.points.intersect(other.points)
if (intersection.isEmpty) {
Option.empty
} else {
Option(Point(intersection.head))
}
}
}
There are some hella code smells in there. I hated that points value. Something about that was super wrong. I had been at it for a couple hours by this point, and I was determined to forge onward. Hello sunk cost fallacy. I did have passing tests, using all the sample data, including for part 2. My scala code at this point follows.
Puzzle 3 Try 1
package is.kow.adventofcode._2019
import scala.annotation.tailrec
import scala.io.Source
import scala.util.matching.Regex
class Puzzle3 {
def distance(resource: String): Int = {
//load from resource
val source = Source.fromResource(resource)
try {
//Two lines
val lines = source.getLines().toList
val wire1String = lines.head
val wire2String = lines.tail.head
val wire1Path = wirePath(wire1String.split(",").toList).reverse
val wire2Path = wirePath(wire2String.split(",").toList).reverse
//Find all the intersections
val points: List[Point] = wire1Path.iterator.flatMap { wire1 =>
//See if it intersects with any wire, and get that point
wire2Path.map { wire2 =>
wire1.intersects2(wire2)
}.filter(_.isDefined)
.map(_.get)
}.toList
//Don't count 0,0
val intersections = points.drop(1)
val distances = intersections.map(manhattanDistance(Point(0, 0), _))
val smallest = distances.foldLeft(distances.head) { (acc, v) =>
if (v < acc) {
v
} else {
acc
}
}
smallest
} finally {
source.close()
}
}
def cheapestRoute(resource: String): Int = {
//load from resource
val source = Source.fromResource(resource)
try {
//Two lines
val lines = source.getLines().toList
val wire1String = lines.head
val wire2String = lines.tail.head
val wire1Path = wirePath(wire1String.split(",").toList).reverse
val wire2Path = wirePath(wire2String.split(",").toList).reverse
//Find all the intersections
val points: List[Point] = wire1Path.iterator.flatMap { wire1 =>
//See if it intersects with any wire, and get that point
wire2Path.map { wire2 =>
wire1.intersects2(wire2)
}.filter(_.isDefined)
.map(_.get)
}.toList
//Don't count 0,0
val intersections = points.drop(1)
val distances = intersections.map { point =>
pointPath(wire1Path, point) + pointPath(wire2Path, point)
}
val smallest = distances.foldLeft(distances.head) { (acc, v) =>
if (v < acc) {
v
} else {
acc
}
}
smallest
}
finally {
source.close()
}
}
private def pointPath(wire: List[Wire], dest: Point): Int = {
//Get all points
val path = wire.flatMap(_.points).distinct.map(Point(_)).takeWhile(_ != dest)
path.length
}
private def manhattanDistance(p: Point, q: Point): Int = {
Math.abs(p.x - q.x) + Math.abs(p.y - q.y)
}
private def wirePath(ins: List[String]): List[Wire] = {
val up: Regex = raw"U([0-9]+)".r
val down = raw"D([0-9]+)".r
val left = raw"L([0-9]+)".r
val right = raw"R([0-9]+)".r
@tailrec def mapPath(acc: List[Wire], startPoint: Point, ops: List[String]): List[Wire] = {
if (ops.isEmpty) {
acc
} else {
val wire = ops.head match {
case up(dist) =>
Wire(startPoint, startPoint.copy(y = startPoint.y + dist.toInt))
case down(dist) =>
Wire(startPoint, startPoint.copy(y = startPoint.y - dist.toInt))
case left(dist) =>
Wire(startPoint, startPoint.copy(x = startPoint.x - dist.toInt))
case right(dist) =>
Wire(startPoint, startPoint.copy(x = startPoint.x + dist.toInt))
}
//Got a wire, accumulate it, and get point
mapPath(wire :: acc, wire.end, ops.tail)
}
}
mapPath(List.empty, Point(0, 0), ins)
}
}
This is *very* complicated code. It did pass all the tests, but it failed the final result for part 2 🙁 I knew I had to start all over. I was super disappointed when the tests passed, but the answer was wrong! A good example of where TDD sorta failed me for a huge problem set. It proved to me that my solution was not very good. It worked for a small subset of data, when my problem set could have infinite data.
A clear head, and attempt 2
My second try at this I pounded out in about 30 minutes. I copied over a few of the known good things, like the manhattan distance, and used the Point case class to make it easier to type out Points. I also consumed the same loading logic, but put it into a function that I could use. This code is far easier to read, much shorter, and an order of magnitude faster.
package is.kow.adventofcode._2019
class Puzzle3Try2 {
def distanceFromCenter(wire1: String, wire2: String): Int = {
val wire1Points = wireStringToPoints(wire1)
val wire2Points = wireStringToPoints(wire2)
val intersections = wire1Points.intersect(wire2Points)
intersections.foldLeft(Int.MaxValue) { (acc, point) =>
val dist = manhattanDistance(Point(0, 0), point)
if (dist < acc) {
dist
} else {
acc
}
}
}
private def manhattanDistance(p: Point, q: Point): Int = {
Math.abs(p.x - q.x) + Math.abs(p.y - q.y)
}
def shortestPath(wire1: String, wire2: String): Int = {
val wire1Points = wireStringToPoints(wire1)
val wire2Points = wireStringToPoints(wire2)
val intersections = wire1Points.intersect(wire2Points)
intersections.foldLeft(Int.MaxValue) { (acc, point) =>
val dist = wire1Points.indexOf(point) + wire2Points.indexOf(point) + 2
if (dist < acc) dist else acc
}
}
private def wireStringToPoints(wire: String): List[Point] = {
val up = raw"U([0-9]+)".r
val down = raw"D([0-9]+)".r
val left = raw"L([0-9]+)".r
val right = raw"R([0-9]+)".r
wire.split(",").foldLeft(List.empty[Point]) { (acc, op) =>
val lastPoint = if (acc.isEmpty) {
Point(0, 0)
} else {
acc.last
}
val newLine = op match {
case up(dist) => (1 to dist.toInt).map(y => lastPoint.copy(y = lastPoint.y + y))
case down(dist) => (1 to dist.toInt).map(y => lastPoint.copy(y = lastPoint.y - y))
case right(dist) => (1 to dist.toInt).map(x => lastPoint.copy(x = lastPoint.x + x))
case left(dist) => (1 to dist.toInt).map(x => lastPoint.copy(x = lastPoint.x - x))
}
acc ++ newLine
}
}
}
That is so much better. Far less lines, easier to read, substantially faster. It also passed all the tests, and got me the correct value. A night of sleep was what I needed to clear my head of all the concepts I had built up over the previous code, and start all over again. The second iteration took barely 2 seconds, and the first attempt took almost 20. My output, and timings from the executions follows.
Failed Attempt 1:
DISTANCE: 258
Cheapest path: 12301
Attempt 2:
Distance: 258 -- Cheapest: 12304
Original: 18
new: 2
My lesson from this: Take breaks. Go do something completely unrelated to the problem, so you can let your subconscious grind on the problem. Do something else to clear out the blinders you’ve built up by looking at a problem only one way.
