פיתרון Advent Of Code יום 19 בסקאלה
25/06/2024
אני כבר לא זוכר כמה זמן עבר מאז חידת ה Advent Of Code הקודמת שפתרתי כאן בסקאלה, אבל יצא שתוכניות השתנו היום וסוף סוף היה לי זמן להמשיך לפרק הבא. למי שעוקב אנחנו בחידה 19 מתוך 25 מה שאומר שיש סיכוי לא רע שעד סוף השנה אצליח לסיים את כל ה 25 חידות של שנה שעברה.
1. האתגר
היום סקאלה עבדה נגדי או שאולי פשוט השתמשתי בה לא נכון. הקלט שלנו נראה כך:
px{a<2006:qkq,m>2090:A,rfg}
pv{a>1716:R,A}
lnx{m>1548:A,A}
rfg{s<537:gd,x>2440:R,A}
qs{s>3448:A,lnx}
qkq{x<1416:A,crn}
crn{x>2662:A,R}
in{s<1351:px,qqz}
qqz{s>2770:qs,m<1801:hdj,R}
gd{a>3333:R,R}
hdj{m>838:A,pv}
{x=787,m=2655,a=1222,s=2876}
{x=1679,m=44,a=2067,s=496}
{x=2036,m=264,a=79,s=2244}
{x=2461,m=1339,a=466,s=291}
{x=2127,m=1623,a=2188,s=1013}
והוא מחולק לשני בלוקים. בבלוק התחתון יש רשימה של פריטים, לכל פריט יש 4 מאפיינים המסומנים באותיות x, m, a, s. הבלוק השני הוא "תוכנית" שמתחילה בשורה שמתחילה ב in וכוללת רשימת תנאים ותוצאות. כשיש לך פריט שמתאים לתנאי ממשיכים לתוצאה שלידו. התוצאה A אומרת שהפריט "התקבל" והתוצאה R אומרת שהפריט לא התקבל. אלה כמה דוגמאות לזרימה של פריטים בתוך תוכניות:
{x=787,m=2655,a=1222,s=2876}: in -> qqz -> qs -> lnx -> A
{x=1679,m=44,a=2067,s=496}: in -> px -> rfg -> gd -> R
{x=2036,m=264,a=79,s=2244}: in -> qqz -> hdj -> pv -> A
{x=2461,m=1339,a=466,s=291}: in -> px -> qkq -> crn -> R
{x=2127,m=1623,a=2188,s=1013}: in -> px -> rfg -> A
אז אנחנו רואים לדוגמה בפריט הראשון שהוא מתחיל ב in, ה s שלו גדול מ 1351 ולכן לא ממשיך ל px אלא ל qqz. שם ה s שלו גדול מ 2770 ולכן ממשיך ל lnx ובגלל שה m שלו גדול מ 1548 הוא מגיע ל A ופה מסיימים.
השאלה הראשונה היא לגלות איזה פריטים מגיעים ל A ולחבר את כל ה a, x, m ו s-ים שלהם.
בשאלה השנייה עלינו לדמיין שכל מאפיין יכול לקבל ערכים בין 1 ל 4000, ולגלות כמה פריטים תיאורטית סך הכל (בלי קשר לרשימה שהם נתנו) יכולים להגיע ל A.
2. פיתרון חלק ראשון
הגדרתי המון טיפוסים בסקאלה כדי שיעזרו לי להתמודד עם כל הטקסט של החידה:
import scala.io.Source
import scala.util.matching.Regex
object aoc2023day19 {
val MAX_VALUE = 4000
case class Item(x: Long, m: Long, a: Long, s: Long)
case class CompressedConditions(minX: Long, maxX: Long,
minM: Long, maxM: Long,
minA: Long, maxA: Long,
minS: Long, maxS: Long)
case class Condition(first: String, comparator: String, second: Long)
case class Rule(condition: Condition, destination: String)
type Workflow = List[Rule]
type Workflows = Map[String, Workflow]
val demoWorkflowLine: String = "ex{x>10:one,m<20:two,a>30:R,A}"
val demoWorkflow: String = """px{a<2006:qkq,m>2090:A,rfg}
|pv{a>1716:R,A}
|lnx{m>1548:A,A}
|rfg{s<537:gd,x>2440:R,A}
|qs{s>3448:A,lnx}
|qkq{x<1416:A,crn}
|crn{x>2662:A,R}
|in{s<1351:px,qqz}
|qqz{s>2770:qs,m<1801:hdj,R}
|gd{a>3333:R,R}
|hdj{m>838:A,pv}
|
|{x=787,m=2655,a=1222,s=2876}
|{x=1679,m=44,a=2067,s=496}
|{x=2036,m=264,a=79,s=2244}
|{x=2461,m=1339,a=466,s=291}
|{x=2127,m=1623,a=2188,s=1013}""".stripMargin
ואז המשכתי לכתוב את כל הפונקציות שמפענחות את הקלט:
// condition - x>10
def parseCondition(condition: String): Condition =
val pattern: Regex = "([xmas])([<>])(\\d+)".r
condition match
case "" => Condition("x", "<=", MAX_VALUE)
case pattern(a, b, c) => Condition(a, b, c.toLong)
// rule - x>10:one
def parseRule(rule: String): Rule =
rule.split(":") match
case Array(destination) => Rule(parseCondition(""), destination)
case Array(condition, destination) => Rule(parseCondition(condition), destination)
// workflow - ex{x>10:one,m<20:two,a>30:R,A}
def parseWorkflow(line: String): (String, Workflow) =
val List(name, workflow) = """(\w+)\{(.*)}""".r.findFirstMatchIn(line).get.subgroups
val rules = workflow.split(",").map(parseRule).toList
(name, rules)
def parseItem(line: String): Item =
val pattern = """\{x=(\d+),m=(\d+),a=(\d+),s=(\d+)}""".r
val List(x, m, a, s) = pattern.findFirstMatchIn(line).get.subgroups
Item(x.toLong,
m.toLong,
a.toLong,
s.toLong)
def parse(source: Source): (Workflows, List[Item]) =
val lines = source.getLines().toList
val workflows = lines
.takeWhile(_.nonEmpty)
.map(parseWorkflow)
.foldLeft(Map[String, Workflow]()) {(workflow, map) =>
val (name, data) = map
workflow ++ Map(name -> data)
}
val items = lines
.dropWhile(_.nonEmpty)
.drop(1)
.map(parseItem)
(workflows, items)
הפונקציה המעניינת הבאה מקבלת פריט ותנאי ובודקת אם הפריט מתאים לתנאי:
def checkCondition(condition: Condition, item: Item): Boolean =
val op1 = condition.first match
case "x" => item.x
case "m" => item.m
case "a" => item.a
case "s" => item.s
condition.comparator match
case "<" => op1 < condition.second
case "<=" => op1 <= condition.second
case ">" => op1 > condition.second
case ">=" => op1 >= condition.second
ואחריה אפשר היה לכתוב פונקציית המשך רקורביסית שבודקת אם הפריט מסתיים ב A או ב R:
def process(workflows: Workflows, current: Workflow, item: Item): Boolean =
current.find(r => checkCondition(r.condition, item)) match
case Some(rule) =>
rule.destination match
case "A" => true
case "R" => false
case next => process(workflows, workflows(next), item)
זה מספיק בשביל החלק הראשון:
def day19part1(): Unit =
val (workflows, items) = parse(Source.fromResource("day19.txt"))
val start = workflows("in")
println(items.filter {
item => process(workflows, start, item)
}.map { item =>
item.x + item.m + item.a + item.s
}.sum)
הרעיון המרכזי של החלק השני הוא הפונקציה הבאה:
def count(workflows: Workflows,
name: String,
ruleNumber: Int = 0,
constraints: List[Condition] = List()): Long =
if (name == "R") {
0L
} else if (name == "A") {
sizeOf(compress(constraints))
} else {
val rules = workflows(name)
val rule = rules(ruleNumber)
if (rule.condition.second < MAX_VALUE) {
count(workflows, rule.destination, 0, constraints :+ rule.condition) +
count(workflows, name, ruleNumber + 1, constraints :+ inverseCondition(rule.condition))
} else {
count(workflows, rule.destination, 0, constraints :+ rule.condition)
}
}
זו פונקציה רקורסיבית שעוברת על כל המסלולים שמגיעים ל A ו"אוספת" את כל התנאים שמגיעים לשם - לדוגמה אם היה תנאי x<50 אז נאסוף אותו כדי לדעת שבמסלול מסוים אנחנו יכולים להתקדם רק אם התנאי הזה מתקיים. כל "כלל" בתוכנית מייצר שתי אפשרויות, אפשרות אחת אם הכלל הזה אמיתי ואפשרות שניה אם הוא שקרי. אז לדוגמה אם יש לנו את השורה:
crn{x>2662:A,R}
אז אני יודע לחלק אותו לשני מסלולים - במסלול אחד x באמת קטן מ 2662 ואז נגיע ל A, ובמסלול שני x גדול או שווה ל 2662 ואז מגיעים ל R. זה הסיפור של החיבור הרקורסיבי שמופיע בפונקציה.
וכן בשביל שהפונקציה תעבוד היא צריכה את המימושים של פונקציות העזר:
def sizeOf(condition: CompressedConditions): Long =
(condition.maxX - condition.minX + 1) *
(condition.maxS - condition.minS + 1) *
(condition.maxA - condition.minA + 1) *
(condition.maxM - condition.minM + 1)
def compress(conditions: List[Condition]): CompressedConditions =
conditions.foldLeft(CompressedConditions(1, 4000, 1, 4000, 1, 4000, 1, 4000)) { (compressed, cond) =>
cond.first match
case "x" =>
cond.comparator match
case "<" if cond.second < compressed.maxX => compressed.copy(maxX=cond.second - 1)
case "<=" if cond.second < compressed.maxX => compressed.copy(maxX=cond.second)
case ">" if cond.second > compressed.minX => compressed.copy(minX=cond.second + 1)
case ">=" if cond.second > compressed.minX => compressed.copy(minX=cond.second)
case _ => compressed
case "m" =>
cond.comparator match
case "<" if cond.second < compressed.maxM => compressed.copy(maxM=cond.second - 1)
case "<=" if cond.second < compressed.maxM => compressed.copy(maxM=cond.second)
case ">" if cond.second > compressed.minM => compressed.copy(minM=cond.second + 1)
case ">=" if cond.second > compressed.minM => compressed.copy(minM=cond.second)
case _ => compressed
case "a" =>
cond.comparator match
case "<" if cond.second < compressed.maxA => compressed.copy(maxA=cond.second - 1)
case "<=" if cond.second < compressed.maxA => compressed.copy(maxA=cond.second)
case ">" if cond.second > compressed.minA => compressed.copy(minA=cond.second + 1)
case ">=" if cond.second > compressed.minA => compressed.copy(minA=cond.second)
case _ => compressed
case "s" =>
cond.comparator match
case "<" if cond.second < compressed.maxS => compressed.copy(maxS = cond.second - 1)
case "<=" if cond.second < compressed.maxS => compressed.copy(maxS = cond.second)
case ">" if cond.second > compressed.minS => compressed.copy(minS = cond.second + 1)
case ">=" if cond.second > compressed.minS => compressed.copy(minS = cond.second)
case _ => compressed
}
def inverseCondition(condition: Condition): Condition =
condition.comparator match
case "<" => condition.copy(comparator=">=")
case "<=" => condition.copy(comparator=">")
case ">" => condition.copy(comparator="<=")
case ">=" => condition.copy(comparator = "<")
וכל התנאים האלה הם מה שהתכוונתי כשכתבתי שסקאלה עבדה לרעתי.
סך הכל קוד הפיתרון המלא בסקאלה הוא:
import scala.io.Source
import scala.util.matching.Regex
object aoc2023day19 {
val MAX_VALUE = 4000
case class Item(x: Long, m: Long, a: Long, s: Long)
case class CompressedConditions(minX: Long, maxX: Long,
minM: Long, maxM: Long,
minA: Long, maxA: Long,
minS: Long, maxS: Long)
case class Condition(first: String, comparator: String, second: Long)
case class Rule(condition: Condition, destination: String)
type Workflow = List[Rule]
type Workflows = Map[String, Workflow]
val demoWorkflowLine: String = "ex{x>10:one,m<20:two,a>30:R,A}"
val demoWorkflow: String = """px{a<2006:qkq,m>2090:A,rfg}
|pv{a>1716:R,A}
|lnx{m>1548:A,A}
|rfg{s<537:gd,x>2440:R,A}
|qs{s>3448:A,lnx}
|qkq{x<1416:A,crn}
|crn{x>2662:A,R}
|in{s<1351:px,qqz}
|qqz{s>2770:qs,m<1801:hdj,R}
|gd{a>3333:R,R}
|hdj{m>838:A,pv}
|
|{x=787,m=2655,a=1222,s=2876}
|{x=1679,m=44,a=2067,s=496}
|{x=2036,m=264,a=79,s=2244}
|{x=2461,m=1339,a=466,s=291}
|{x=2127,m=1623,a=2188,s=1013}""".stripMargin
// condition - x>10
def parseCondition(condition: String): Condition =
val pattern: Regex = "([xmas])([<>])(\\d+)".r
condition match
case "" => Condition("x", "<=", MAX_VALUE)
case pattern(a, b, c) => Condition(a, b, c.toLong)
// rule - x>10:one
def parseRule(rule: String): Rule =
rule.split(":") match
case Array(destination) => Rule(parseCondition(""), destination)
case Array(condition, destination) => Rule(parseCondition(condition), destination)
// workflow - ex{x>10:one,m<20:two,a>30:R,A}
def parseWorkflow(line: String): (String, Workflow) =
val List(name, workflow) = """(\w+)\{(.*)}""".r.findFirstMatchIn(line).get.subgroups
val rules = workflow.split(",").map(parseRule).toList
(name, rules)
def parseItem(line: String): Item =
val pattern = """\{x=(\d+),m=(\d+),a=(\d+),s=(\d+)}""".r
val List(x, m, a, s) = pattern.findFirstMatchIn(line).get.subgroups
Item(x.toLong,
m.toLong,
a.toLong,
s.toLong)
def parse(source: Source): (Workflows, List[Item]) =
val lines = source.getLines().toList
val workflows = lines
.takeWhile(_.nonEmpty)
.map(parseWorkflow)
.foldLeft(Map[String, Workflow]()) {(workflow, map) =>
val (name, data) = map
workflow ++ Map(name -> data)
}
val items = lines
.dropWhile(_.nonEmpty)
.drop(1)
.map(parseItem)
(workflows, items)
def checkCondition(condition: Condition, item: Item): Boolean =
val op1 = condition.first match
case "x" => item.x
case "m" => item.m
case "a" => item.a
case "s" => item.s
condition.comparator match
case "<" => op1 < condition.second
case "<=" => op1 <= condition.second
case ">" => op1 > condition.second
case ">=" => op1 >= condition.second
def inverseCondition(condition: Condition): Condition =
condition.comparator match
case "<" => condition.copy(comparator=">=")
case "<=" => condition.copy(comparator=">")
case ">" => condition.copy(comparator="<=")
case ">=" => condition.copy(comparator = "<")
def process(workflows: Workflows, current: Workflow, item: Item): Boolean =
current.find(r => checkCondition(r.condition, item)) match
case Some(rule) =>
rule.destination match
case "A" => true
case "R" => false
case next => process(workflows, workflows(next), item)
def sizeOf(condition: CompressedConditions): Long =
(condition.maxX - condition.minX + 1) *
(condition.maxS - condition.minS + 1) *
(condition.maxA - condition.minA + 1) *
(condition.maxM - condition.minM + 1)
def compress(conditions: List[Condition]): CompressedConditions =
conditions.foldLeft(CompressedConditions(1, 4000, 1, 4000, 1, 4000, 1, 4000)) { (compressed, cond) =>
cond.first match
case "x" =>
cond.comparator match
case "<" if cond.second < compressed.maxX => compressed.copy(maxX=cond.second - 1)
case "<=" if cond.second < compressed.maxX => compressed.copy(maxX=cond.second)
case ">" if cond.second > compressed.minX => compressed.copy(minX=cond.second + 1)
case ">=" if cond.second > compressed.minX => compressed.copy(minX=cond.second)
case _ => compressed
case "m" =>
cond.comparator match
case "<" if cond.second < compressed.maxM => compressed.copy(maxM=cond.second - 1)
case "<=" if cond.second < compressed.maxM => compressed.copy(maxM=cond.second)
case ">" if cond.second > compressed.minM => compressed.copy(minM=cond.second + 1)
case ">=" if cond.second > compressed.minM => compressed.copy(minM=cond.second)
case _ => compressed
case "a" =>
cond.comparator match
case "<" if cond.second < compressed.maxA => compressed.copy(maxA=cond.second - 1)
case "<=" if cond.second < compressed.maxA => compressed.copy(maxA=cond.second)
case ">" if cond.second > compressed.minA => compressed.copy(minA=cond.second + 1)
case ">=" if cond.second > compressed.minA => compressed.copy(minA=cond.second)
case _ => compressed
case "s" =>
cond.comparator match
case "<" if cond.second < compressed.maxS => compressed.copy(maxS = cond.second - 1)
case "<=" if cond.second < compressed.maxS => compressed.copy(maxS = cond.second)
case ">" if cond.second > compressed.minS => compressed.copy(minS = cond.second + 1)
case ">=" if cond.second > compressed.minS => compressed.copy(minS = cond.second)
case _ => compressed
}
@main
def day19part1(): Unit =
val (workflows, items) = parse(Source.fromString(demoWorkflow))
val start = workflows("in")
println(items.filter {
item => process(workflows, start, item)
}.map { item =>
item.x + item.m + item.a + item.s
}.sum)
def count(workflows: Workflows,
name: String,
ruleNumber: Int = 0,
constraints: List[Condition] = List()): Long =
if (name == "R") {
0L
} else if (name == "A") {
sizeOf(compress(constraints))
} else {
val rules = workflows(name)
val rule = rules(ruleNumber)
if (rule.condition.second < MAX_VALUE) {
count(workflows, rule.destination, 0, constraints :+ rule.condition) +
count(workflows, name, ruleNumber + 1, constraints :+ inverseCondition(rule.condition))
} else {
count(workflows, rule.destination, 0, constraints :+ rule.condition)
}
}
@main
def day19part2(): Unit =
val (workflows, items) = parse(Source.fromString(demoWorkflow))
println(count(workflows, "in"))
}
אם יש לכם רעיונות איך לכתוב את זה בסקאלה עם פחות חזרתיות אל תתביישו לשתף בתגובות או בטלגרם.