Advent of Code 2020
Problem 1
Part 1
Calculate the difference between 2020 and the candidate number, lookup that value in the input. If we see the number in the input, it means we have a pair.
import cats.implicits._
def find2Addends(numbers: List[Long], target: Long): Option[(Long, Long)] = {
val numSet = numbers.toSet
numbers.collectFirstSome { x =>
val y = target - x
if (numSet(y)) Some((x, y))
else None
}
}
val (x, y) = find2Addends(input1, 2020L).get
// x: Long = 462L
// y: Long = 1558L
x * y
// res0: Long = 719796L
Part 2
Use recursion to find n addends which sum to a target value.
def findNAddends(numbers: List[Long], target: Long, n: Long): Option[List[Long]] = {
n match {
case 2 => find2Addends(numbers, target).map { case (x, y) => List(x, y) }
case _ =>
def loop(l: List[Long]): Option[List[Long]] = {
l match {
case x :: rest =>
findNAddends(rest, target - x, n - 1) match {
case None => loop(rest)
case Some(addends) => Some(x :: addends)
}
case Nil => None
}
}
loop(numbers)
}
}
val addends = findNAddends(input1, 2020L, 3).get
// addends: List[Long] = List(277L, 1359L, 384L)
addends.foldLeft(1L)(_ * _)
// res1: Long = 144554112L
Problem 2
Part 1
Let's define the interesting bits we want from the input.
case class Rule(num1: Int, num2: Int, char: Char)
case class Line(rule: Rule, password: String)
Now use cats-parse to parse the input.
// here's the first few lines
println(input2.split("\n").take(5).mkString("\n"))
// 1-8 n: dpwpmhknmnlglhjtrbpx
// 11-12 n: frpknnndpntnncnnnnn
// 4-8 t: tmttdtnttkr
// 12-18 v: vvvvvvvqvvvvvqvvgf
// 3-4 c: cccc
import cats.parse.{Parser => P, _}
val parser = {
val digits = Numbers.digits.map(_.toInt)
val alphaLower = P.charIn('a' to 'z')
val rule = (digits ~ (P.char('-') *> digits) ~ (P.char(' ') *> alphaLower))
.map { case ((num1, num2), char) => Rule(num1, num2, char) }
val line = (rule ~ (P.string(": ") *> alphaLower.rep.string))
.map { case (rule, password) =>
Line(rule, password)
}
(line <* P.char('\n').orElse(P.end)).rep
}
val lines = parser.parseAll(input2)
// lines: Either[cats.parse.Parser.Error, cats.data.NonEmptyList[Line]] = Right(
// value = NonEmptyList(
// head = Line(
// rule = Rule(num1 = 1, num2 = 8, char = 'n'),
// password = "dpwpmhknmnlglhjtrbpx"
// ),
// tail = List(
// Line(
// rule = Rule(num1 = 11, num2 = 12, char = 'n'),
// password = "frpknnndpntnncnnnnn"
// ),
// Line(
// rule = Rule(num1 = 4, num2 = 8, char = 't'),
// password = "tmttdtnttkr"
// ),
// Line(
// rule = Rule(num1 = 12, num2 = 18, char = 'v'),
// password = "vvvvvvvqvvvvvqvvgf"
// ),
// Line(rule = Rule(num1 = 3, num2 = 4, char = 'c'), password = "cccc"),
// Line(
// rule = Rule(num1 = 17, num2 = 18, char = 'z'),
// password = "zzzzzzzzdzzzzzzgzr"
// ),
// Line(rule = Rule(num1 = 5, num2 = 6, char = 'l'), password = "llltzl"),
// Line(rule = Rule(num1 = 4, num2 = 5, char = 'g'), password = "fzfng"),
// Line(rule = Rule(num1 = 3, num2 = 6, char = 'b'), password = "bjsbbxbb"),
// Line(rule = Rule(num1 = 4, num2 = 5, char = 'b'), password = "dbbbl"),
// Line(rule = Rule(num1 = 1, num2 = 4, char = 't'), password = "tttcrt"),
// Line(
// rule = Rule(num1 = 8, num2 = 11, char = 't'),
// password = "tttwtttwttn"
// ),
// Line(
// rule = Rule(num1 = 16, num2 = 17, char = 'm'),
// password = "mmmmmmmmmmmmmmmbp"
// ),
// Line(
// rule = Rule(num1 = 8, num2 = 11, char = 'f'),
// password = "fffffffqfmzfff"
// ),
// Line(
// rule = Rule(num1 = 10, num2 = 12, char = 'n'),
// password = "nnnnnnnnnncvnnnf"
// ),
// Line(
// rule = Rule(num1 = 5, num2 = 15, char = 'b'),
// password = "ztmcfqsrbvbbbqbxw"
// ),
// ...
Now apply the rule to the passwords.
lines.map(_.count { case Line(rule, password) =>
val count = password.count(_ === rule.char)
(rule.num1 to rule.num2).contains(count)
})
// res3: Either[cats.parse.Parser.Error, Long] = Right(value = 445L)
Part 2
Apply the new rule.
lines.map(_.count { case Line(rule, password) =>
val first = password.lift(rule.num1 - 1).contains_(rule.char)
val second = password.lift(rule.num2 - 1).contains_(rule.char)
(first, second) match {
case (true, true) => false
case (true, false) => true
case (false, true) => true
case (false, false) => false
}
})
// res4: Either[cats.parse.Parser.Error, Long] = Right(value = 491L)
Problem 3
Part 1
Describe the grid, with open and tree cells.
sealed trait Cell
case object Open extends Cell
case object Tree extends Cell
type Grid[A] = Array[Array[A]]
Let's parse the input:
def parseGrid(s: String): Grid[Cell] = {
s.split("\n").map { line =>
line.map {
case '.' => Open
case '#' => Tree
}.toArray[Cell]
}.toArray
}
val s = """..##.......
#...#...#..
.#....#..#.
..#.#...#.#
.#...##..#.
..#.##.....
.#.#.#....#
.#........#
#.##...#...
#...##....#
.#..#...#.#"""
val grid = parseGrid(s)
// grid: Grid[Cell] = Array(
// Array(Open, Open, Tree, Tree, Open, Open, Open, Open, Open, Open, Open),
// Array(Tree, Open, Open, Open, Tree, Open, Open, Open, Tree, Open, Open),
// Array(Open, Tree, Open, Open, Open, Open, Tree, Open, Open, Tree, Open),
// Array(Open, Open, Tree, Open, Tree, Open, Open, Open, Tree, Open, Tree),
// Array(Open, Tree, Open, Open, Open, Tree, Tree, Open, Open, Tree, Open),
// Array(Open, Open, Tree, Open, Tree, Tree, Open, Open, Open, Open, Open),
// Array(Open, Tree, Open, Tree, Open, Tree, Open, Open, Open, Open, Tree),
// Array(Open, Tree, Open, Open, Open, Open, Open, Open, Open, Open, Tree),
// Array(Tree, Open, Tree, Tree, Open, Open, Open, Tree, Open, Open, Open),
// Array(Tree, Open, Open, Open, Tree, Tree, Open, Open, Open, Open, Tree),
// Array(Open, Tree, Open, Open, Tree, Open, Open, Open, Tree, Open, Tree)
// )
Now let's render the grid to help debug.
import $ivy.`org.typelevel::cats-core:2.3.0`
import cats.implicits._
import cats.Show
object Cell {
implicit def showCell[A <: Cell]: Show[A] = {
case Open => "."
case Tree => "#"
}
}
def showGrid[A : Show](grid: Grid[A]) =
grid.toList
.map(line => line.toList.mkString_(""))
.mkString_("\n")
println(showGrid(grid))
// ..##.......
// #...#...#..
// .#....#..#.
// ..#.#...#.#
// .#...##..#.
// ..#.##.....
// .#.#.#....#
// .#........#
// #.##...#...
// #...##....#
// .#..#...#.#
A function to produce a path down the slope.
import scala.annotation.tailrec
def downTheSlope(grid: Grid[Cell], xDelta: Int, yDelta: Int): List[(Int, Int, Cell)] = {
val width = grid(0).size
val height = grid.size
@tailrec
def loop(prevX: Int, prevY: Int, visited: List[(Int, Int, Cell)]): List[(Int, Int, Cell)] = {
val x = (prevX + xDelta) % width
val y = prevY + yDelta
if (y >= height) visited
else {
val cell = grid(y)(x)
loop(x, y, (x, y, cell) :: visited)
}
}
loop(0, 0, Nil)
}
Overlay the path on the grid, with an overlay of visited cells, . as open, # as a tree.
def overlayPath(grid: Grid[Cell], path: List[(Int, Int, Cell)]): Grid[String] = {
val coord2cell = path.map { case (x, y, cell) => ((x, y), cell) }.toMap
grid.zipWithIndex.map { case (line, j) =>
line.zipWithIndex.map { case (cell, i) =>
(coord2cell.get((i, j)), cell) match {
case (Some(Open), _) => "O"
case (Some(Tree), _) => "X"
case (None, Open) => "."
case (None, Tree) => "#"
}
}
}
}
println(showGrid(overlayPath(grid, downTheSlope(grid, 3, 1))))
// ..##.......
// #..O#...#..
// .#....X..#.
// ..#.#...#O#
// .X...##..#.
// ..#.X#.....
// .#.#.#.O..#
// .#........X
// #.X#...#...
// #...#X....#
// .#..#...X.#
This looks correct, now let's do it for the actual input.
downTheSlope(parseGrid(input3), 3, 1).count(_._3 == Tree)
// res7: Int = 207
Part 2
Same again, for different trajectories, timesing by all the count of trees.
val slopes = List((1, 1), (3, 1), (5, 1), (7, 1), (1, 2))
// slopes: List[(Int, Int)] = List((1, 1), (3, 1), (5, 1), (7, 1), (1, 2))
slopes
.map { case (xDelta, yDelta) =>
downTheSlope(parseGrid(input3), xDelta, yDelta).count(_._3 == Tree).toLong
}
.foldLeft(1L)(_ * _)
// res8: Long = 2655892800L
Problem 4
Part 1
Define the things we want to parse:
import cats.data.NonEmptyList
sealed trait Field
object Field {
case class BirthYear(value: String) extends Field
case class IssueYear(value: String) extends Field
case class ExpirationYear(value: String) extends Field
case class Height(value: String) extends Field
case class HairColor(value: String) extends Field
case class EyeColor(value: String) extends Field
case class PassportID(value: String) extends Field
case class CountryID(value: String) extends Field
}
case class Passport(fields: NonEmptyList[Field])
Write a parser.
object Parser {
val whitespace = P.charIn(Array(' ', '\n'))
def field[A <: Field](field: String, builder: String => A): P[A] =
P.string(field + ":") *> P.until(whitespace).map(builder)
def fields = P.oneOf[Field](List(
field("byr", Field.BirthYear),
field("iyr", Field.IssueYear),
field("eyr", Field.ExpirationYear),
field("hgt", Field.Height),
field("hcl", Field.HairColor),
field("ecl", Field.EyeColor),
field("pid", Field.PassportID),
field("cid", Field.CountryID),
))
val passport = P.repSep(fields, 1, whitespace).map(Passport)
val batch = P.repSep(passport, 1, P.string("\n\n"))
}
Test the parser out on the test input.
Parser.batch.parseAll(passportInput)
// res9: Either[cats.parse.Parser.Error, NonEmptyList[Passport]] = Right(
// value = NonEmptyList(
// head = Passport(
// fields = NonEmptyList(
// head = EyeColor(value = "gry"),
// tail = List(
// PassportID(value = "860033327"),
// ExpirationYear(value = "2020"),
// HairColor(value = "#fffffd"),
// BirthYear(value = "1937"),
// IssueYear(value = "2017"),
// CountryID(value = "147"),
// Height(value = "183cm")
// )
// )
// ),
// tail = List(
// Passport(
// fields = NonEmptyList(
// head = IssueYear(value = "2013"),
// tail = List(
// EyeColor(value = "amb"),
// CountryID(value = "350"),
// ExpirationYear(value = "2023"),
// PassportID(value = "028048884"),
// HairColor(value = "#cfa07d"),
// BirthYear(value = "1929")
// )
// )
// ),
// Passport(
// fields = NonEmptyList(
// head = HairColor(value = "#ae17e1"),
// tail = List(
// IssueYear(value = "2013"),
// ExpirationYear(value = "2024"),
// EyeColor(value = "brn"),
// PassportID(value = "760753108"),
// BirthYear(value = "1931"),
// Height(value = "179cm")
// )
// )
// ),
// Passport(
// fields = NonEmptyList(
// head = HairColor(value = "#cfa07d"),
// tail = List(
// ExpirationYear(value = "2025"),
// PassportID(value = "166559648"),
// ...
Now let's validate the passports:
val requiredFields = Set[Class[_]](
classOf[Field.BirthYear],
classOf[Field.IssueYear],
classOf[Field.ExpirationYear],
classOf[Field.Height],
classOf[Field.HairColor],
classOf[Field.EyeColor],
classOf[Field.PassportID]
)
def validatePassport1(passport: Passport): Boolean =
(requiredFields -- passport.fields.map(_.getClass).toList).isEmpty
val batch = Parser.batch.parseAll(input4).getOrElse(???)
batch.count(validatePassport1)
// res10: Long = 245L
Part 2
Add additional validation of the fields.
import scala.util.Try
def validateField(field: Field): Boolean = field match {
case Field.BirthYear(value) =>
Try(value.toInt).map { year =>
1920 <= year && year <= 2002
}.getOrElse(false)
case Field.IssueYear(value) =>
Try(value.toInt).map { year =>
2010 <= year && year <= 2020
}.getOrElse(false)
case Field.ExpirationYear(value) =>
Try(value.toInt).map { year =>
2020 <= year && year <= 2030
}.getOrElse(false)
case Field.Height(value) =>
Try(value.dropRight(2).toInt).map { height =>
if (value.endsWith("cm"))
150 <= height && height <= 193
else if (value.endsWith("in"))
59 <= height && height <= 76
else false
}.getOrElse(false)
case Field.HairColor(value) =>
value.matches("#[0-9a-f]{6}")
case Field.EyeColor("amb" | "blu" | "brn" | "gry" | "grn" | "hzl" | "oth") =>
true
case Field.EyeColor(_) => false
case Field.PassportID(value) =>
value.matches("[0-9]{9}")
case Field.CountryID(_) => true
}
def validatePassport2(passport: Passport): Boolean = {
val hasRequired = (requiredFields -- passport.fields.map(_.getClass).toList).isEmpty
hasRequired && passport.fields.toList.forall(validateField)
}
Recount the valid passports.
batch.count(validatePassport2)
// res11: Long = 133L
Problem 5
Part 1
Split the string into row and column parts:
val (encodedRow, encodedCol) = "FBFBBFFRLR".splitAt(7)
// encodedRow: String = "FBFBBFF"
// encodedCol: String = "RLR"
Subdividing can be achieved using foldLeft:
def decodeRow(encoded: String) =
encoded.foldLeft((0, 127)) {
case ((low, high), 'F') =>
(low, (low + high) / 2)
case ((low, high), 'B') =>
((low + high + 1) / 2, high)
case (_, _) => ???
}
decodeRow(encodedRow)
// res12: (Int, Int) = (44, 44)
Now the same for the column.
def decodeCol(encoded: String) =
encoded.foldLeft((0, 7)) {
case ((low, high), 'L') =>
(low, (low + high) / 2)
case ((low, high), 'R') =>
((low + high + 1) / 2, high)
case (_, _) => ???
}
decodeCol(encodedCol)
// res13: (Int, Int) = (5, 5)
Now put them all together, row * 8 + col = seat.
def decodeSeat(encoded: String) = {
val (encodedRow, encodedCol) = encoded.splitAt(7)
decodeRow(encodedRow)._1 * 8 + decodeCol(encodedCol)._1
}
Test it against the examples.
decodeSeat("BFFFBBFRRR")
// res14: Int = 567
decodeSeat("FFFBBBFRRR")
// res15: Int = 119
decodeSeat("BBFFBBFRLL")
// res16: Int = 820
We want to decode each row of the input, and then get the maximum value.
input5.split("\n").map(decodeSeat).max
// res17: Int = 818
Part 2
Now look for a discontinuity in the seats. This can be done by sorting the seat ids, calc the difference between sequential elements. If the difference isn't 1, we've found the discontinuity.
val seatIds = input5.split("\n").map(decodeSeat).sorted.toList
seatIds.sliding(2).collectFirst {
case x :: y :: Nil if (y - x) != 1 => (x, y)
}
// res18: Option[(Int, Int)] = Some(value = (558, 560))
So our seat is between 558 and 560, must be 559!
Problem 6
Part 1
Split into groups, convert the group of strings into sets of characters. Need to remember to remove the newlines.
val customs = """abc
a
b
c
ab
ac
a
a
a
a
b"""
val group2correct = customs.split("\n\n").map(_.toSet - '\n')
// group2correct: Array[Set[Char]] = Array(
// Set('a', 'b', 'c'),
// Set('a', 'b', 'c'),
// Set('a', 'b', 'c'),
// Set('a'),
// Set('b')
// )
The size of the set will be the number of correct answers per group. Add them all together
group2correct.map(_.size).foldLeft(0)(_ + _)
// res19: Int = 11
Put it all together for the real input.
input6
.split("\n\n")
.map(_.toSet - '\n')
.map(_.size)
.foldLeft(0)(_ + _)
// res20: Int = 6259
Part 2
Now we need to find the intersection of all the correct answers for a group.
val groupAnswers = customs.split("\n\n").map { group =>
group.split("\n").map(_.toSet).toList
}
// groupAnswers: Array[List[Set[Char]]] = Array(
// List(Set('a', 'b', 'c')),
// List(Set('a'), Set('b'), Set('c')),
// List(Set('a', 'b'), Set('a', 'c')),
// List(Set('a'), Set('a'), Set('a'), Set('a')),
// List(Set('b'))
// )
val allYesForGroup = groupAnswers.map { answers =>
answers.tail
.foldLeft(answers.head)(_.intersect(_))
}
// allYesForGroup: Array[Set[Char]] = Array(
// Set('a', 'b', 'c'),
// Set(),
// Set('a'),
// Set('a'),
// Set('b')
// )
allYesForGroup.map(_.size).foldLeft(0)(_ + _)
// res21: Int = 6
Now for realz:
input6
.split("\n\n")
.map { group =>
val answers = group.split("\n").map(_.toSet).toList
answers.tail.foldLeft(answers.head)(_.intersect(_))
}
.map(_.size).foldLeft(0)(_ + _)
// res22: Int = 3178
Problem 7
Part 1
Define the stuff we want.
case class Requirement(color: String, quantity: Int)
case class Rule(color: String, requirements: List[Requirement])
Let's parse the input.
import cats.parse.{Parser => P, _}
import cats.implicits._
object Parser {
val space = P.char(' ')
val alpha = P.charIn('a' to 'z')
val color = (alpha.rep ~ space ~ alpha.rep).string
val requirement = (((Numbers.digits <* space) ~ color) <* P.string(" bag") <* P.char('s').?)
.map { case (num, color) => Requirement(color, num.toInt) }
val requirements = P.string("no other bags").as(Nil)
.orElse(P.repSep(requirement, 1, P.string(", ")).map(_.toList))
val rule = ((color <* P.string(" bags contain ")) ~ (requirements <* P.char('.')))
.map { case (color, reqs) => Rule(color, reqs) }
val rules = P.repSep(rule, 1, P.char('\n'))
}
val rules = Parser.rules.parseAll(input7).getOrElse(???)
// rules: cats.data.NonEmptyList[Rule] = NonEmptyList(
// head = Rule(
// color = "dark olive",
// requirements = List(
// Requirement(color = "muted brown", quantity = 2),
// Requirement(color = "mirrored tomato", quantity = 1),
// Requirement(color = "bright black", quantity = 4)
// )
// ),
// tail = List(
// Rule(
// color = "faded coral",
// requirements = List(
// Requirement(color = "drab cyan", quantity = 3),
// Requirement(color = "light aqua", quantity = 1)
// )
// ),
// Rule(
// color = "plaid plum",
// requirements = List(Requirement(color = "mirrored cyan", quantity = 2))
// ),
// Rule(
// color = "clear maroon",
// requirements = List(
// Requirement(color = "dotted turquoise", quantity = 1),
// Requirement(color = "dim lavender", quantity = 3)
// )
// ),
// Rule(
// color = "plaid coral",
// requirements = List(
// Requirement(color = "posh fuchsia", quantity = 3),
// Requirement(color = "dotted beige", quantity = 3),
// Requirement(color = "wavy turquoise", quantity = 2)
// )
// ),
// Rule(
// color = "mirrored indigo",
// requirements = List(
// Requirement(color = "pale orange", quantity = 5),
// Requirement(color = "striped aqua", quantity = 5),
// Requirement(color = "dotted cyan", quantity = 1),
// Requirement(color = "muted coral", quantity = 4)
// )
// ),
// Rule(
// color = "striped brown",
// requirements = List(
// Requirement(color = "faded green", quantity = 4),
// ...
Use recursion to find out whether a bag contains a "shiny gold" bag.
type Color2Reqs = Map[String, List[Requirement]]
def containsGold(color2reqs: Color2Reqs, color: String): Boolean = {
color2reqs(color).exists { req =>
req.color === "shiny gold" || containsGold(color2reqs, req.color)
}
}
val color2reqs = rules
.map(rule => (rule.color, rule.requirements))
.toList.toMap
// color2reqs: Map[String, List[Requirement]] = HashMap(
// "posh fuchsia" -> List(Requirement(color = "dotted fuchsia", quantity = 2)),
// "dull salmon" -> List(Requirement(color = "dark gold", quantity = 3)),
// "vibrant beige" -> List(
// Requirement(color = "shiny red", quantity = 2),
// Requirement(color = "clear tan", quantity = 2)
// ),
// "faded gray" -> List(
// Requirement(color = "bright yellow", quantity = 5),
// Requirement(color = "light silver", quantity = 4)
// ),
// "wavy gray" -> List(
// Requirement(color = "shiny green", quantity = 4),
// Requirement(color = "shiny red", quantity = 5)
// ),
// "dull blue" -> List(
// Requirement(color = "bright gold", quantity = 1),
// Requirement(color = "dim olive", quantity = 2),
// Requirement(color = "muted chartreuse", quantity = 4),
// Requirement(color = "striped salmon", quantity = 2)
// ),
// "plaid bronze" -> List(
// Requirement(color = "plaid chartreuse", quantity = 5),
// Requirement(color = "mirrored turquoise", quantity = 3),
// Requirement(color = "light salmon", quantity = 3)
// ),
// "mirrored gray" -> List(
// Requirement(color = "dotted orange", quantity = 3),
// Requirement(color = "mirrored tomato", quantity = 4),
// Requirement(color = "plaid lime", quantity = 4)
// ),
// "clear indigo" -> List(
// Requirement(color = "dotted magenta", quantity = 2),
// Requirement(color = "bright silver", quantity = 4),
// Requirement(color = "muted aqua", quantity = 4)
// ),
// "shiny cyan" -> List(
// Requirement(color = "clear gold", quantity = 5),
// Requirement(color = "shiny lime", quantity = 2),
// Requirement(color = "wavy magenta", quantity = 4),
// Requirement(color = "wavy lavender", quantity = 2)
// ),
// "dull violet" -> List(
// Requirement(color = "bright yellow", quantity = 4),
// Requirement(color = "posh magenta", quantity = 2),
// Requirement(color = "shiny red", quantity = 5)
// ),
// "mirrored red" -> List(
// Requirement(color = "pale lime", quantity = 3),
// ...
rules.count(rule => containsGold(color2reqs, rule.color))
// res24: Long = 246L
Wohoo!
Part 2
Now recursively count the bags.
def countBags(color2reqs: Color2Reqs, color: String): Long = {
color2reqs(color) match {
case Nil => 1L
case reqs => reqs
.map { req =>
req.quantity * countBags(color2reqs, req.color)
}
.foldLeft(1L)(_ + _)
}
}
countBags(color2reqs, "shiny gold")
// res25: Long = 2977L
One thing which caught me out, is to remember to -1. As you don't want to count the "shiny gold" bag.
Problem 8
Part 1
Parse the instructions.
import cats.parse.{Parser => P, _}
sealed trait Op
case class Acc(value: Int) extends Op
case class Jmp(value: Int) extends Op
case class Nop(value: Int) extends Op
object Parser {
def op[A <: Op](name: String, builder: Int => Op) = (P.string(name + " ") *> (P.charIn("-+") ~ Numbers.digits).string).map { num => builder(num.toInt) }
val ops = P.repSep(
P.oneOf(List(
op("acc", Acc),
op("jmp", Jmp),
op("nop", Nop)
)), 1, P.char('\n'))
}
Parser.ops.parseAll("""nop +0
acc +1
jmp +4
acc +3
jmp -3
acc -99
acc +1
jmp -4
acc +6""")
// res27: Either[cats.parse.Parser.Error, cats.data.NonEmptyList[Op]] = Right(
// value = NonEmptyList(
// head = Nop(value = 0),
// tail = List(
// Acc(value = 1),
// Jmp(value = 4),
// Acc(value = 3),
// Jmp(value = -3),
// Acc(value = -99),
// Acc(value = 1),
// Jmp(value = -4),
// Acc(value = 6)
// )
// )
// )
Write an interpreter, the return type is a bit funky due to part 2.
If the program enters an infinite loop return left which is a tuple of the accumulator and the seen instructions.
If the program completes return right which is just the accumulator.
import scala.annotation.tailrec
import cats.implicits._
def run(instructions: List[Op]): Either[(Int, List[Int]), Int] = {
val max = instructions.size - 1
@tailrec
def loop(i: Int, acc: Int, seen: List[Int]): Either[(Int, List[Int]), Int] = {
if (seen.contains_(i)) Left((acc, seen))
else if (i >= max) Right(acc)
else instructions(i) match {
case Acc(value) =>
loop(i + 1, acc + value, i :: seen)
case Jmp(value) =>
loop(i + value, acc, i :: seen)
case Nop(_) =>
loop(i + 1, acc, i :: seen)
}
}
loop(0, 0, Nil)
}
Run for the program input.
val instructions = Parser.ops.parseAll(input8)
.getOrElse(???)
.toList
val Left((acc, seen)) = run(instructions)
acc
// res28: Int = 1709
👌
Part 2
Thanks to the limitation of only replacing a single operation in the instructions, the "bad" op has to be one of the ones which was processed before entering an infinite loop. Fortunately we kept track of these seen ops in part 1.
Let's brute force this by replacing a single op one by one, until the program terminates (returns right).
seen.collectFirstSome { i =>
instructions(i) match {
case _: Acc => None
case Jmp(value) =>
val newInstructions = instructions.updated(i, Nop(value))
run(newInstructions).toOption
case Nop(value) =>
val newInstructions = instructions.updated(i, Nop(value))
run(newInstructions).toOption
}
}
// res29: Option[Int] = Some(value = 1976)
That's the answer!
Problem 9
Part 1
Reuse the find2Addends function from problem 1.
def find2Addends(numbers: List[Long], target: Long): Option[(Long, Long)] = {
val numSet = numbers.toSet
numbers.collectFirstSome { x =>
val y = target - x
if (numSet(y)) Some((x, y))
else None
}
}
Parsing the input, you know the drill:
val nums = """35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576"""
.split("\n")
.map(_.toLong)
.toList
I'm a fan of sliding windows for these kinds of problems, basically you want a row of each number you want to test as well as the preceding 5 numbers. So a sliding window of 6 works perfectly.
nums
// keep the number we want to test + previous 5
.sliding(6)
// reverse the sliding window, making pattern matching easier
// head will be the number you want to test
.map(_.reverse)
.toList
.tail // don't process the preamble
.collectFirstSome {
case head :: xs if (find2Addends(xs, head).isEmpty) =>
Some(head)
case _ => None
}
// res30: Option[Long] = Some(value = 127L)
Awesome, let's go ahead and run on the input with a sliding window of 1 + 25:
input9
.sliding(26)
.map(_.reverse)
.toList
.tail // don't process the preamble
.collectFirstSome {
case head :: xs if (find2Addends(xs, head).isEmpty) =>
Some(head)
case _ => None
}
// res31: Option[Long] = Some(value = 36845998L)
Part 2
Let's just go ahead and brute force this. The possible size of subsets of the input will be
2 to the size of the input. Incrementally increase the size of the sliding windows on the input
until one of the windows sums up to the result of the previous answer 36845998.
val Some(list) = (2 to input9.size).toList.collectFirstSome { lSize =>
input9.sliding(lSize).toList.collectFirstSome { list =>
if (list.sum === 36845998L) Some(list)
else None
}
}
// list: List[Long] = List(
// 1443202L,
// 1886894L,
// 1622596L,
// 1628710L,
// 1683212L,
// 2054839L,
// 1793533L,
// 1848035L,
// 1955257L,
// 2517933L,
// 2031865L,
// 2948974L,
// 2101735L,
// 2946745L,
// 2455659L,
// 2539785L,
// 3387024L
// )
Now add the min and max of the list.
list.min + list.max
// res32: Long = 4830226L
🎉
Problem 10
Part 1
Parse the example as a set, with an additional entry which is the max of the example + 3 jolts.
val exampleAdapters = """28
33
18
42
31
14
46
20
48
47
24
23
49
45
19
38
39
11
1
32
25
35
8
17
7
9
4
2
34
10
3"""
.split("\n")
.map(_.toInt)
.toSet
val adapters = exampleAdapters + (exampleAdapters.max + 3)
Lookup the joltages in the set, preferring the lowest joltage increment. Recursively incrementing the joltage, till it reaches the maxJoltage of the adapters.
def countDifferences(adapters: Set[Int]): List[Int] = {
val maxJoltage = adapters.max
@tailrec
def loop(joltage: Int, acc: List[Int]): List[Int] = {
if (joltage === maxJoltage) acc
else if (adapters(joltage + 1)) loop(joltage + 1, 1 :: acc)
else if (adapters(joltage + 2)) loop(joltage + 2, 2 :: acc)
else if (adapters(joltage + 3)) loop(joltage + 3, 3 :: acc)
else ???
}
loop(0, Nil)
}
countDifferences(adapters)
// res33: List[Int] = List(
// 3,
// 1,
// 1,
// 1,
// 1,
// 3,
// 3,
// 1,
// 3,
// 1,
// 1,
// 1,
// 1,
// 3,
// 3,
// 1,
// 1,
// 3,
// 1,
// 1,
// 1,
// 3,
// 3,
// 1,
// 1,
// 1,
// 1,
// 3,
// 1,
// 1,
// 1,
// 1
// )
Count the number of joltage steps for each joltage increment.
countDifferences(adapters)
.groupBy(identity) // group by the joltage step
.view.mapValues(_.size) // count the number of joltage steps
// res34: collection.MapView[Int, Int] = MapView((1, 22), (3, 10))
So we have 22 of 1 joltage steps, and 10 of 3 joltage steps. Which matches what was specified for the example. Now for the real input, we'll ignore the extra max + 3 joltage adapter this time, and just remember to count an extra 3 joltage step at the end.
countDifferences(input10)
.groupBy(identity)
.view.mapValues(_.size)
// res35: collection.MapView[Int, Int] = MapView((1, 71), (3, 26))
So 71 of 1 joltages steps, and 26 of the 3 joltage steps (remember to add 1 for the adapter we choose to miss out).
Times them together for the correct answer.
71 * 27
// res36: Int = 1917
Cool, we have the correct answer.
A simpler solution is available by sorting the array, and counting the difference between each step.
input10.toList.sorted
.sliding(2)
.collect { case prev :: next :: Nil => next - prev }
.toList
.groupBy(identity)
.view.mapValues(_.size)
// res37: collection.MapView[Int, Int] = MapView((1, 70), (3, 26))
Part 2
For part 2, we need to count the total number of unique paths from 0 to the maximum joltage.
One way to solve this is to count the paths from 0 to a each adapter joltage.
def countPaths(adapters: List[Int]): Long = {
val counts = adapters.foldLeft(Map[Int, Long](0 -> 1L)) {
case (acc, joltage) =>
val count = acc.getOrElse(joltage - 1, 0L) +
acc.getOrElse(joltage - 2, 0L) +
acc.getOrElse(joltage - 3, 0L)
acc + (joltage -> count)
}
counts(adapters.last)
}
The adapters need to be sorted lowest to highest, so that the path counting happens for the lowest voltage first. We don't need to worry about the max + 3 joltage adapter, as there is only one joltage step that can be taken to it.
countPaths(input10.toList.sorted)
// res38: Long = 113387824750592L
⚡⚡️⚡️