Advent of Code 2019

Problem 1

Problem link

Part 1

Fuel required is floor(mass / 3) - 2.

def calcRequiredFuel(mass: Long): Long =
  (mass.toDouble / 3d).floor.toLong - 2

input1.map(calcRequiredFuel).sum
// res0: Long = 3305041L

Part 2

Recursively calculate the required fuel for each module, then calculate the fuel required to carry that fuel recursively. Negative fuel is treated as 0.

import scala.annotation.tailrec

def calcTotalFuel(origMass: Long): Long = {
  @tailrec
  def iter(mass: Long, totalFuel: Long): Long = {
    val fuel = calcRequiredFuel(mass).max(0)
    if (fuel == 0) totalFuel
    else iter(fuel, totalFuel + fuel)
  }
  iter(origMass, 0)
}

input1.map(calcTotalFuel).sum
// res1: Long = 4954710L

Problem 2

Problem link

Part 1

import scala.annotation.tailrec

@tailrec
final def run(program: Vector[Int], pointer: Int): Vector[Int] = {
  program.slice(pointer, pointer + 4).toList match {
    case 99 :: _ => program
    case 1 :: address1 :: address2 :: updateAddress :: _ =>
      run(
        program.updated(updateAddress, program(address1) + program(address2)),
        pointer + 4)
    case 2 :: address1 :: address2 :: updateAddress :: _ =>
      run(
        program.updated(updateAddress, program(address1) * program(address2)),
        pointer + 4)
    case instruction =>
      throw new IllegalStateException(s"Unexpected instruction supplied ${instruction.mkString(",")} ($pointer)")
  }
}

run(input2.updated(1, 12).updated(2, 2), 0)(0)
// res3: Int = 3931283

Part 2

def runProgram(program: Vector[Int], noun: Int, verb: Int): Int = {
  run(program.updated(1, noun).updated(2, verb), 0)(0)
}

Calculate all possible noun and verb combinations.

val results = for {
  noun <- (1 to 99)
  verb <- (1 to 99)
  result = runProgram(input2, noun, verb)
} yield (noun, verb, result)

Get the first noun and verb combination that gives the correct result.

results
  .collectFirst { case (noun, verb, 19690720) => 100 * noun + verb }
  .get
// res4: Int = 6979

Problem 3

Problem link

Part 1

Coerce the strings into the required data. Keep track of the starting position of each path segment.

sealed trait PathSegment {
  def x: Int
  def y: Int
}
final case class Horizontal(x: Int, y: Int, dx: Int) extends PathSegment
final case class Vertical(x: Int, y: Int, dy: Int) extends PathSegment

object PathSegment {

  private val commandPattern = """([URDL])(\d+)""".r
  def unsafeFromString(s: String, x: Int, y: Int): PathSegment = {
    s match {
      case commandPattern("U", delta) => Vertical(x, y, delta.toInt)
      case commandPattern("R", delta) => Horizontal(x, y, delta.toInt)
      case commandPattern("D", delta) => Vertical(x, y, -delta.toInt)
      case commandPattern("L", delta) => Horizontal(x, y, -delta.toInt)
      case unknown => throw new IllegalArgumentException(s"Unexpected command string $unknown")
    }
  }
}

type Path = List[PathSegment]
object Path {
  def unsafeFromString(s: String): (Path, Path) = {
    val (line1, line2) = s.span(_ != '\n')
    (parsePathLine(line1), parsePathLine(line2.trim))
  }

  private def parsePathLine(s: String): Path = s
    .split(",")
    .toList
    .foldLeft((List.empty[PathSegment], 0, 0)) { case ((acc, x, y), segmentS) =>
      val segment = PathSegment.unsafeFromString(segmentS, x, y)
      segment match {
        case horizontal: Horizontal =>
          (horizontal :: acc, x + horizontal.dx, y)
        case vertical: Vertical =>
          (vertical :: acc, x, y + vertical.dy)
      }
    }
    ._1
    .reverse
}

For the problem the distinction between horizontal and vertical doesn't matter. However it's much easier to visualize.

def findIntersectPoints(path1: Path, path2: Path) =
  for {
    segment1 <- path1
    segment2 <- path2
    point <- (segment1, segment2) match {
      case (_: Horizontal, _: Horizontal) => None
      case (_: Vertical, _: Vertical) => None
      case (horizontal: Horizontal, vertical: Vertical) =>
        findIntersectPoint(horizontal, vertical)
      case (vertical: Vertical, horizontal: Horizontal) =>
        findIntersectPoint(horizontal, vertical)
    }
  } yield point

def findIntersectPoint(
  horizontal: Horizontal,
  vertical: Vertical
): Option[(Int, Int)] = (horizontal, vertical) match {
  case (Horizontal(x1, y1, dx), Vertical(x2, y2, dy)) =>
    if (y1 < y2.max(y2 + dy) && y1 > y2.min(y2 + dy) &&
        x2 < x1.max(x1 + dx) && x2 > x1.min(x1 + dx)) {
      Some(x2 -> y1)
    } else None
}

def runPart1(s: String): Int = {
  val (path1, path2) = Path.unsafeFromString(s)
  findIntersectPoints(path1, path2)
    .map { case (x, y) => x.abs + y.abs }
    .min
}

Run the examples.

runPart1("""R75,D30,R83,U83,L12,D49,R71,U7,L72
U62,R66,U55,R34,D71,R55,D58,R83""")
// res6: Int = 159
runPart1("""R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
U98,R91,D20,R16,D67,R40,U7,R15,U6,R7""")
// res7: Int = 135

Success!

runPart1(input3)
// res8: Int = 489

Part 2

Modify the function in part 1 to return the segments which intersect, making it easy to find the segments leading up to intersection.

final case class Intersect(
  segment1: PathSegment, segment2: PathSegment,
  x: Int, y: Int)

def findIntersects(path1: Path, path2: Path): List[Intersect] =
  for {
    segment1 <- path1
    segment2 <- path2
    intersect <- (segment1, segment2) match {
      case (_: Horizontal, _: Horizontal) => None
      case (_: Vertical, _: Vertical) => None
      case (horizontal: Horizontal, vertical: Vertical) =>
        findIntersectPoint(horizontal, vertical).map { case (x, y) =>
          Intersect(horizontal, vertical, x, y)
        }
      case (vertical: Vertical, horizontal: Horizontal) =>
        findIntersectPoint(horizontal, vertical).map { case (x, y) =>
          Intersect(vertical, horizontal, x, y)
        }
    }
  } yield intersect

Count the steps to the intersection, and add the distance to the intersection point.

def runPart2(s: String) = {
  val (path1, path2) = Path.unsafeFromString(s)
  val intersects = findIntersects(path1, path2)
  val stepCounts = intersects.map { case Intersect(segment1, segment2, x, y) =>
    val stepCount1 = countSteps(path1.takeWhile(_ != segment1)) +
      ((segment1.x - x).abs + (segment1.y - y).abs)
    val stepCount2 = countSteps(path2.takeWhile(_ != segment2)) +
      ((segment2.x - x).abs + (segment2.y - y).abs)
    stepCount1 + stepCount2
  }
  stepCounts.min
}

def countSteps(path: Path) = {
  path.foldLeft(0) {
    case (count, Horizontal(_, _, dx)) => count + dx.abs
    case (count, Vertical(_, _, dy)) => count + dy.abs
  }
}

Examples.

runPart2("""R75,D30,R83,U83,L12,D49,R71,U7,L72
U62,R66,U55,R34,D71,R55,D58,R83""")
// res9: Int = 610
runPart2("""R98,U47,R26,D63,R33,U87,L62,D20,R33,U53,R51
U98,R91,D20,R16,D67,R40,U7,R15,U6,R7""")
// res10: Int = 410

runPart2(input3)
// res11: Int = 93654

Problem 4

Problem link

Part 1

Apply the rule.

import cats.implicits._

def isDescending(digits: List[Int]): Boolean =
  digits.foldM(0) {
    case (prev, curr) if curr < prev => None
    case (prev, curr) if curr >= prev => Some(curr)
  }.isDefined

def hasDoubleDigit(digits: List[Int]): Boolean =
  digits.foldM(0) {
    case (prev, curr) if prev == curr => None
    case (prev, curr) => Some(curr)
  }.isEmpty

def rule(digits: List[Int]): Boolean =
  isDescending(digits) && hasDoubleDigit(digits)

Test the examples.

import scala.annotation.tailrec

def digits(i: Int): List[Int] = {
  @tailrec
  def loop(n: Int, acc: List[Int]): List[Int] = {
    if (n == 0) acc
    else {
      val x = (n / 10) * 10
      loop(x / 10, n - x :: acc)
    }
  }
  loop(i, List.empty)
}

// get digits and put in list
digits(12345678)
// res13: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8)

assert(rule(digits(111111)) == true)
assert(rule(digits(223450)) == false)
assert(rule(digits(123789)) == false)

Let's try brute forcing.

(145852 to 616942).count(i => rule(digits(i)))
// res17: Int = 1767

Looks like it completes in a sensible amount of time!

Part 2

def hasOnlyDoubleDigit(digits: List[Int]): Boolean =
  digits
    .foldM((1, 0)) {
      case ((combo, prev), curr) if prev == curr => Some((combo + 1, curr))
      case ((2, prev), curr) if prev != curr => None
      case ((_, prev), curr) if prev != curr => Some((1, curr))
    }
    .map {
      case (2, _) => true
      case _ => false
    }
    .getOrElse(true)

def newRule(digits: List[Int]): Boolean =
  isDescending(digits) && hasOnlyDoubleDigit(digits)

Examples.

assert(newRule(digits(112233)) == true)
assert(newRule(digits(123444)) == false)
assert(newRule(digits(111122)) == true)
assert(newRule(digits(111111)) == false)

(145852 to 616942).count(i => newRule(digits(i)))
// res22: Int = 1192

Problem 5

Problem link

Part 1

Simplify the interpreter by using Instruction ADT.

import cats.implicits._
import scala.annotation.tailrec

sealed trait ParamMode

object ParamMode {
  case object Position extends ParamMode
  case object Immediate extends ParamMode

  def unapply(i: Int): Option[ParamMode] = i match {
    case 0 => Position.some
    case 1 => Immediate.some
    case _ => None
  }
}

final case class Params(
  opCode: Int,
  param1: ParamMode, param2: ParamMode, param3: ParamMode)

object Params {

  def fromInt(i: Int): Option[Params] = {
    digits(i).reverse match {
      case d :: e :: ParamMode(c) :: ParamMode(b) :: ParamMode(a) :: Nil =>
        Params(d + e * 10, c, b, a).some
      case d :: e :: ParamMode(c) :: ParamMode(b) :: Nil =>
        Params(d + e * 10, c, b, ParamMode.Position).some
      case d :: e :: ParamMode(c) :: Nil =>
        Params(d + e * 10, c, ParamMode.Position, ParamMode.Position).some
      case d :: e :: Nil =>
        Params(d + e * 10, ParamMode.Position, ParamMode.Position, ParamMode.Position).some
      case d :: Nil =>
        Params(d, ParamMode.Position, ParamMode.Position, ParamMode.Position).some
      case _ => None
    }
  }

  private def digits(i: Int): List[Int] = {
    @tailrec
    def loop(n: Int, acc: List[Int]): List[Int] = {
      if (n == 0) acc
      else {
        val x = (n / 10) * 10
        loop(x / 10, n - x :: acc)
      }
    }
    loop(i, List.empty)
  }
}

sealed trait Instruction
case object Halt extends Instruction
final case class Add(arg1: Int, param1: ParamMode, arg2: Int, param2: ParamMode, address: Int) extends Instruction
final case class Mult(arg1: Int, param1: ParamMode, arg2: Int, param2: ParamMode, address: Int) extends Instruction
final case class In(address: Int) extends Instruction
final case class Out(arg1: Int, param1: ParamMode) extends Instruction
final case class JumpIfTrue(arg1: Int, param1: ParamMode, pointer: Int, param2: ParamMode) extends Instruction
final case class JumpIfFalse(arg1: Int, param1: ParamMode, pointer: Int, param2: ParamMode) extends Instruction
final case class LessThan(arg1: Int, param1: ParamMode, arg2: Int, param2: ParamMode, address: Int) extends Instruction
final case class Equals(arg1: Int, param1: ParamMode, arg2: Int, param2: ParamMode, address: Int) extends Instruction

object Instruction {
  def fromList(l: List[Int]): Option[Instruction] =
    (l.headOption.flatMap(Params.fromInt), l.tail) match {
      case (Some(Params(99, _, _, _)),  _) => Halt.some
      case (Some(Params(1, param1, param2, _)), arg1 :: arg2 :: arg3 :: Nil) =>
        Add(arg1, param1, arg2, param2, arg3).some
      case (Some(Params(2, param1, param2, _)), arg1 :: arg2 :: arg3 :: Nil) =>
        Mult(arg1, param1, arg2, param2, arg3).some
      case (Some(Params(3, _, _, _)), arg1 :: _) => In(arg1).some
      case (Some(Params(4, param1, _, _)), arg1 :: _) => Out(arg1, param1).some
      case (Some(Params(5, param1, param2, _)), arg1 :: arg2 :: _) =>
        JumpIfTrue(arg1, param1, arg2, param2).some
      case (Some(Params(6, param1, param2, _)), arg1 :: arg2 :: _) =>
        JumpIfFalse(arg1, param1, arg2, param2).some
      case (Some(Params(7, param1, param2, _)), arg1 :: arg2 :: arg3 :: _) =>
        LessThan(arg1, param1, arg2, param2, arg3).some
      case (Some(Params(8, param1, param2, _)), arg1 :: arg2 :: arg3 :: _) =>
        Equals(arg1, param1, arg2, param2, arg3).some
      case _ => None
    }
}

Write a program interpreter.

@tailrec
def runLoop(
  memory: Vector[Int],
  pointer: Int,
  inputs: List[Int],
  outputs: List[Int]
): List[Int] = {
  val instructionList = memory.slice(pointer, pointer + 4).toList
  Instruction.fromList(instructionList) match {
    case Some(Halt) => outputs
    case Some(Add(arg1, param1, arg2, param2, address)) =>
      val newMemory = memory.updated(address, resolveArg(memory, arg1, param1) + resolveArg(memory, arg2, param2))
      runLoop(newMemory, pointer + 4, inputs, outputs)
    case Some(Mult(arg1, param1, arg2, param2, address)) =>
      val newMemory = memory.updated(address, resolveArg(memory, arg1, param1) * resolveArg(memory, arg2, param2))
      runLoop(newMemory, pointer + 4, inputs, outputs)
    case Some(In(address)) =>
      val newMemory = memory.updated(address, inputs.head)
      runLoop(newMemory, pointer + 2, inputs.tail, outputs)
    case Some(Out(arg, param)) =>
      runLoop(memory, pointer + 2, inputs, resolveArg(memory, arg, param) :: outputs)
    case Some(JumpIfTrue(arg1, param1, newPointer, param2)) if resolveArg(memory, arg1, param1) != 0 =>
      runLoop(memory, resolveArg(memory, newPointer, param2), inputs, outputs)
    case Some(JumpIfTrue(arg, param, _, _)) if resolveArg(memory, arg, param) == 0 =>
      runLoop(memory, pointer + 3, inputs, outputs)
    case Some(JumpIfFalse(arg1, param1, newPointer, param2)) if resolveArg(memory, arg1, param1) == 0 =>
      runLoop(memory, resolveArg(memory, newPointer, param2), inputs, outputs)
    case Some(JumpIfFalse(arg, param, _, _)) if resolveArg(memory, arg, param) != 0 =>
      runLoop(memory, pointer + 3, inputs, outputs)
    case Some(LessThan(arg1, param1, arg2, param2, address)) =>
      val newMemory = memory.updated(
        address,
        if (resolveArg(memory, arg1, param1) < resolveArg(memory, arg2, param2)) 1 else 0
      )
      runLoop(newMemory, pointer + 4, inputs, outputs)
    case Some(Equals(arg1, param1, arg2, param2, address)) =>
      val newMemory = memory.updated(
        address,
        if (resolveArg(memory, arg1, param1) == resolveArg(memory, arg2, param2)) 1 else 0
      )
      runLoop(newMemory, pointer + 4, inputs, outputs)
    case _ =>
      throw new IllegalStateException(s"Unexpected instruction supplied ${instructionList.mkString(",")} ($pointer)")
  }
}

def resolveArg(memory: Vector[Int], arg: Int, paramMode: ParamMode): Int =
  paramMode match {
    case ParamMode.Position => memory(arg)
    case ParamMode.Immediate => arg
  }

def run(program: Vector[Int], inputs: List[Int]): List[Int] =
  runLoop(program, 0, inputs, List.empty)

Run the program with 1 input.

run(input5, List(1))
// res24: List[Int] = List(13294380, 0, 0, 0, 0, 0, 0, 0, 0, 0)

Part 2

Examples.

val exampleInput = "3,21,1008,21,8,20,1005,20,22,107,8,21,20,1006,20,31,1106,0,36,98,0,0,1002,21,125,20,4,20,1105,1,46,104,999,1105,1,46,1101,1000,1,20,4,20,1105,1,46,98,99"
  .split(",")
  .map(_.toInt)
  .toVector

run(exampleInput, List(1))
// res25: List[Int] = List(999)
run(exampleInput, List(8))
// res26: List[Int] = List(1000)
run(exampleInput, List(9))
// res27: List[Int] = List(1001)

Actual output.

run(input5, List(5))
// res28: List[Int] = List(11460760)

Problem 6

Problem link

Part 1

Example data:

val exampleInput = """COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L"""

Model a tree and coerce the result into it.

sealed trait Tree
final case class Node(id: String, edges: List[Tree]) extends Tree
final case class Leaf(id: String) extends Tree

object Tree {
  private val orbitRegex = """([^\)]+)\)([^\)]+)""".r

  def parseOrbits(s: String): Tree =
    fromList(s.trim
      .split("\n").flatMap(_.split(","))
      .map { case orbitRegex(left, right) => (left, right) }
      .toList, "COM")

  def fromList(list: List[(String, String)], rootKey: String) =
    fromMap(list.groupMap(_._1)(_._2), rootKey)

  def fromMap(objectMap: Map[String, List[String]], key: String): Tree =
    objectMap.get(key) match {
      case None => Leaf(key)
      case Some(nextEdges) => Node(key, nextEdges.map(fromMap(objectMap, _)))
    }
}

val orbitMap = Tree.parseOrbits(exampleInput)
// orbitMap: Tree = Node(
//   id = "COM",
//   edges = List(
//     Node(
//       id = "B",
//       edges = List(
//         Node(
//           id = "C",
//           edges = List(
//             Node(
//               id = "D",
//               edges = List(
//                 Node(
//                   id = "E",
//                   edges = List(
//                     Leaf(id = "F"),
//                     Node(
//                       id = "J",
//                       edges = List(Node(id = "K", edges = List(Leaf(id = "L"))))
//                     )
//                   )
//                 ),
//                 Leaf(id = "I")
//               )
//             )
//           )
//         ),
//         Node(id = "G", edges = List(Leaf(id = "H")))
//       )
//     )
//   )
// )

Count each nodes edge, and add the depth.

def countOrbits(tree: Tree, depth: Int = 0): Int = tree match {
  case Node(_, edges) =>
    val newDepth = depth + 1
    edges.foldLeft(0) { case (count, edge) =>
      count + newDepth + countOrbits(edge, newDepth)
    }
  case Leaf(id) => 0
}

countOrbits(orbitMap)
// res30: Int = 42

countOrbits(Tree.parseOrbits(input6))
// res31: Int = 224901

Part 2

Parse the example orbit map.

val orbitMap2 = Tree.parseOrbits("""COM)B
B)C
C)D
D)E
E)F
B)G
G)H
D)I
E)J
J)K
K)L
K)YOU
I)SAN""")

Build a path from the root of the tree to the id of the node.

import cats.implicits._

def pathToRoot(tree: Tree, dest: String, path: List[String] = List.empty): Option[List[String]] = {
  tree match {
    case Node(`dest`, _) | Leaf(`dest`) => Some(dest :: path)
    case Node(id, edges) =>
      edges.collectFirstSome(pathToRoot(_, dest, id :: path))
    case Leaf(_) => None
  }
}

Path from santa to me, can be determined by finding a common ancestor from the paths to the root of the object map, which is COM.

val santaPath = pathToRoot(orbitMap2, "SAN").get
// santaPath: List[String] = List("SAN", "I", "D", "C", "B", "COM")
val myPath = pathToRoot(orbitMap2, "YOU").get
// myPath: List[String] = List("YOU", "K", "J", "E", "D", "C", "B", "COM")
santaPath.diff(myPath)
// res32: List[String] = List("SAN", "I")
myPath.diff(santaPath)
// res33: List[String] = List("YOU", "K", "J", "E")

def path(tree: Tree, from: String, to: String) = for {
  path1 <- pathToRoot(tree, from)
  path2 <- pathToRoot(tree, to)
} yield path1.diff(path2) ::: path2.diff(path1).reverse

path(orbitMap2, "YOU", "SAN")
// res34: Option[List[String]] = Some(
//   value = List("YOU", "K", "J", "E", "I", "SAN")
// )

Now try with the input...

val pathToSanta = path(Tree.parseOrbits(input6), "YOU", "SAN")
  .getOrElse(throw new IllegalStateException("Cannot find path to santa!!!"))

pathToSanta.size - 2
// res35: Int = 334