פיתרון Advent Of Code 2023 יום 20 בסקאלה
יום עשרים של Advent Of Code הוא אחד התרגילים עם הרבה יותר מדי טקסט, הרבה יותר מדי קוד והרבה יותר מדי עבודה ידנית. בקיצור לא תרגיל שאוכל אי פעם להשתמש בו בקורסים ולא תרגיל שנהניתי ממנו במיוחד. אבל יש גם כאלה בחיים. בואו נראה את המשימה והפיתרון בקצרה. לינק לתרגיל: https://adventofcode.com/2023/day/20
1. מה צריך למצוא
נתון קלט שנראה כמו תרשים חומרה:
broadcaster -> a, b, c
%a -> b
%b -> c
%c -> inv
&inv -> a
הקלט מתאר רכיבים ולכל רכיב יש את הלוגיקה שלו. הרכיב שנקרא broadcaster מעביר את האות שהוא מקבל לכל אלה שהוא מחובר אליהם, רכיבים שמתחילים באחוז נקראים Flip Flop ויש להם לוגיקה פנימית ורכיבים שמתחילים באמפרסנד נקראים Conjunction וגם להם יש לוגיקה פנימית שלהם.
רכיב Flip Flop מחזיק מצב פנימי שמתחיל False. הוא יכול לקבל אות "חזק" או "חלש". אם הוא מקבל אות חלש הוא הופך את המצב הפנימי שלו וגם שולח אות חדש. אם הוא התחיל כבוי הוא ישלח אות חזק לכל אלה שהוא מחובר אליהם, ואם הוא התחיל דלוק הוא ישלח אות חלש.
רכיב Conjunction זוכר את האות האחרון שהוא קיבל מכל הרכיבים שנכנסים אליו (אם לא התקבל אות הוא זוכר זרם "חלש"). כשמקבל אות הוא מעדכן את הזיכרון ואז בודק אם כל הקלטים שלו הם זרם "חזק" הוא ישלח זרם חלש, אחרת הוא ישלח זרם חזק.
אה ויש עוד רכיב שנקרא button. הוא מחובר ל broadcaster, לא מופיע בציור וכשלוחצים עליו שולח זרם "חלש" ל broadcaster.
אם הלכתם לאיבוד עד פה אתם לא לבד. לי לקח כמה פעמים לקרוא את ההוראות עד שהבנתי וגם בזמן כתיבת הפיתרון המשכתי לחזור להוראות האלה. נקודה אחרונה היא שצריך לטפל באותו בסדר בו הם נשלחים, לכן אם a שולח אות ל b ול c ואז b שולח אות חדש ל c, אז קודם צריך לטפל בשני האותות ש a שלח ורק אז להמשיך לאות ש b שלח ל c.
בשאלה הראשונה לוחצים על הכפתור אלף פעמים וצריך למצוא כמה אותות חזקים וכמה אותות חלשים נשלחו. בחלק השני צריך למצוא כמה פעמים צריך ללחוץ על הכפתור עד שמודול בשם rx יקבל אות חלש.
2. פיתרון חלק ראשון בסקאלה
בחלק הראשון רוב העבודה היא לקודד את ההוראות לסקאלה (או לכל שפה אחרת שבחרתם). האתגר היחיד כאן היה הטיפול באותו לפי הסדר, ובשביל זה הגדרתי מחלקה בשם Runner שמגדירה תור הודעות. כל פעם שמישהו שולח אות האות מצטרף לתור ויש פונקציה שמוציאה את כל האותות של סיבוב מסוים מהתור ומטפלת בהם לפי הסדר.
מבחינת מחלקות אלה המחלקות שמחזיקות את המידע על המודולים:
sealed trait CommunicationModule {
def name: String
}
case class FlipFlop(name: String, state: Boolean) extends CommunicationModule
case class Conjunction(name: String, state: Map[String, Int]) extends CommunicationModule
case class Broadcaster(name: String) extends CommunicationModule
case class UntypedModule(name: String) extends CommunicationModule
וזאת הפונקציה שנקראת כשמודול מקבל אות:
def receive(sender: String, target: CommunicationModule, signal: Int, runner: Runner): CommunicationModule =
target match
case cm @ FlipFlop(name, state) if signal == LOW_PULSE && state =>
runner.sendSignal(LOW_PULSE, name)
cm.copy(state = false)
case cm @ FlipFlop(name, state) if signal == LOW_PULSE && !state =>
runner.sendSignal(HIGH_PULSE, name)
cm.copy(state = true)
case cm @ Conjunction(name, state) =>
val updatedState = runner.inputs(name).map {
case i if i == sender => Map(sender -> signal)
case i if state.contains(i) => Map(i -> state(i))
case i => Map(i -> LOW_PULSE)
}.foldLeft(Map[String, Int]())(_ ++ _)
if (updatedState.values.forall(_ == HIGH_PULSE)) {
runner.sendSignal(LOW_PULSE, name)
} else {
runner.sendSignal(HIGH_PULSE, name)
}
cm.copy(state = updatedState)
case cm @ Broadcaster(name) =>
runner.sendSignal(signal, name)
cm
case _ => target
אפשר לראות שמקודדת פה כל הלוגיקה של כל המודולים. באופן כללי אחרי שכתבתי את הפונקציה חשבתי שאולי היה עדיף לבנות את הקוד בגישת Object Oriented ולבנות לוגיקה של כל מודול בתוך המחלקה שלו.
המחלקה Runner היא זאת שמנהלת את תור ההודעות וזה הקוד שלה:
class Runner(val inputs: Map[String, List[String]], val outputs: Map[String, List[String]]) {
val pendingSignals: mutable.Queue[(String, String, Int)] = mutable.Queue()
var lowCount = 0
var highCount = 0
var buttonPresses = 0
def pressButton(): Unit =
buttonPresses += 1
this.sendSignal(LOW_PULSE, "button")
def sendSignal(signal: Int, from: String): Unit =
val to = outputs(from)
if (signal == LOW_PULSE) {
lowCount += to.size
} else if (signal == HIGH_PULSE) {
highCount += to.size
}
to.foreach { to =>
// if (to == "xf" && signal == LOW_PULSE) {
// throw new Exception(s"xf ${this.buttonPresses}")
// }
this.pendingSignals.enqueue((from, to, signal))
}
def handleSignals(modules: Map[String, CommunicationModule]): Map[String, CommunicationModule] =
this.pendingSignals.dequeueAll((item) => true).foldLeft(modules) { (modules, message) =>
val (from, to, signal) = message
println(s"${from} - ${if (signal == -1) "low" else "high"} - ${to}")
modules.updatedWith(to) {
case Some(cm) =>
Some(receive(from, cm, signal, this))
case _ =>
println(s"Tried to send signal to untyped module: ${to}")
None
}
}
def helper(modules: Map[String, CommunicationModule]): Map[String, CommunicationModule] =
this.pressButton()
process(modules)
def findCycleSize(modules: Map[String, CommunicationModule], end: String): Long =
val relevantModules = influencedBy(modules, inputs, Set(end))
val data = LazyList.iterate(modules)(helper).map { modules =>
modules.view.filterKeys(relevantModules.contains).toMap
}
findCycleIndex(data)
@tailrec
final def process(modules: Map[String, CommunicationModule]): Map[String, CommunicationModule] =
if (this.pendingSignals.nonEmpty) {
val updatedModules = handleSignals(modules)
this.process(updatedModules)
} else {
modules
}
}
חלק מהקוד כאן רלוונטי רק לחלק השני של התרגיל, בגדול מבחינת החלק הראשון הפונקציה הכי חשובה היא sendSignal שמקבלת סיגנל ומודול ושולחת את הסיגנל לכל המודולים שמחוברים לאותו שולח. הפונקציה handleSignals מושכת מהתור את כל הסיגנלים ומטפלת בהם והפונקציה process קוראת ל handleSignals בלולאה כל עוד סיגנלים חדשים מצטרפים לתור. הפונקציה helper מתארת איטרציה אחת של עבודה עם המכונה - היא לוחצת על הכפתור ואז מטפלת בכל הסיגנלים שוב ושוב עד שהתור מתרוקן.
החלק המסובך השני של התרגיל היה לפענח את הקלט. בשביל החלק השני של התרגיל רציתי להחזיק אינדקס כפול גם לשמור את החוטים שיוצאים מכל מודול וגם את החוטים שנכנסים אליו. סך הכל בניתי 3 מפות:
המפה modules מחזיקה לכל אות את המודול שמתאים לה, עם הסטייט הפנימי שלו, השם שלו והסוג שלו.
המפה outputs מחזיקה לכל אות את האותיות שאליהן היא שולחת סיגנלים.
המפה inputs מחזיקה לכל אות את האותיות ששולחות אליה סיגנלים.
הפונקציה הזו בסקאלה בונה את שלושת המפות:
def parseInput(input: Source): (Map[String, CommunicationModule], Map[String, List[String]], Map[String, List[String]]) =
input
.getLines()
.concat(List("button -> broadcaster"))
.map { line => line.split(" -> ") }
.collect { case Array(name, outputs) =>
val outputModules = outputs.split(", ").toList
val module = name match
case "broadcaster" => Broadcaster(name)
case s"%${name}" => FlipFlop(name, false)
case s"&${name}" => Conjunction(name, Map[String, Int]())
case s"${name}" => UntypedModule(name)
(module, outputModules)
}.foldLeft((
Map[String, CommunicationModule](),
Map[String, List[String]](),
Map[String, List[String]]())) { (a, v) =>
val (modules, inputs, outputs) = a
val (newModule, itsOutputs) = v
val newName = newModule.name
val updatedInputs = itsOutputs.foldLeft(inputs) { (inputs, output) =>
inputs.updatedWith(output) {
case Some(existingInputs) => Some(existingInputs :+ newName)
case None => Some(List(newName))
}
}
val updatedOutputs = outputs.updatedWith(newName) {
case Some(existingOutputs) => Some(existingOutputs ++ itsOutputs) // unreachable, because there's only one line per module
case None => Some(itsOutputs)
}
val updatedModules = modules.updated(newName, newModule)
(updatedModules, updatedInputs, updatedOutputs)
}
בשביל החלק הראשון צריך רק ללחוץ על הכפתור אלף פעמים ולראות כמה סיגנלים חזקים וכמה חלשים נשלחו:
@main
def day20part1(): Unit =
val (modules, inputs, outputs) = parseInput(Source.fromResource("day20.txt"))
println(modules)
println(inputs)
println(outputs)
val runner = Runner(inputs, outputs)
var round = 0L
var modules_i = modules
1.to(1000).foreach { i =>
runner.pressButton()
modules_i = runner.process(modules_i)
}
println(runner.lowCount)
println(runner.highCount)
println(runner.lowCount * runner.highCount)
3. פיתרון חלק שני
החלק השני היה יותר מורכב ודרש עבודה ידנית. אלה השורות הרלוונטיות מתוך הקלט הספציפי שאני קיבלתי:
&zr -> rx
&gc -> zr
&sz -> zr
&cm -> zr
&xf -> zr
אני רואה ש rx מושפע מ zr, ו zr מושפע מ 4 מודולים אחרים. עכשיו התחילה עבודת החיפוש: בשביל ש rx יקבל אות חלש zr צריך לשלוח לו אות חלש. zr הוא מודול חיבור והוא שולח אות חלש רק כשכל המודולים שמחוברים אליו שולחים אות חזק. עכשיו אנחנו רק צריכים לבדוק מתי gc, sz, cm ו xf מקבלים אות חזק יחד כדי לענות על השאלה.
בשביל להבין מתי מישהו מקבל אות חזק הוספתי את ה Exception הבא לפונקציה sendSignal:
def sendSignal(signal: Int, from: String): Unit =
val to = outputs(from)
if (signal == LOW_PULSE) {
lowCount += to.size
} else if (signal == HIGH_PULSE) {
highCount += to.size
}
to.foreach { to =>
if (to == "gc" && signal == HIGH_PULSE) {
throw new Exception(s"gc ${this.buttonPresses}")
}
this.pendingSignals.enqueue((from, to, signal))
}
אחרי חיפושים גיליתי שכל ה-4 מקבלים אות חזק ממש בלחיצה הראשונה. השאלה הבאה היא מתי בפעם הבאה הם יקבלו אות חזק, כלומר כל כמה לחיצות המצב שלהם מתאפס. את זה כבר היה יותר מסובך לחשב - הטריק היה לזהות מי המודולים שמשפיעים על מודול מסוים בעזרת הפונקציה הבאה:
@tailrec
def influencedBy(modules: Map[String, CommunicationModule],
inputs: Map[String, List[String]],
searching: Set[String] = Set(),
found: Set[String] = Set()): Set[String] =
if (searching.isEmpty) {
found
} else {
val nextModule = searching.head
val nextSearching = searching ++ inputs.getOrElse(nextModule, List()) - nextModule -- found
val nextFound = found + nextModule
influencedBy(modules,
inputs,
nextSearching,
nextFound)
}
לאחר מכן לבנות תת-מפה רק של המודולים האלה ולבנות רשימה של כל המצבים שלהם לאורך הלחיצות, כלומר לבנות רשימה שבמקום הראשון שלה יהיה המצב של המודולים הרלוונטים אחרי לחיצה אחת, במקום השני אחרי שתי לחיצות וכך הלאה:
def findCycleSize(modules: Map[String, CommunicationModule], end: String): Long =
val relevantModules = influencedBy(modules, inputs, Set(end))
val data = LazyList.iterate(modules)(helper).map { modules =>
modules.view.filterKeys(relevantModules.contains).toMap
}
findCycleIndex(data)
אחרי שיש לנו את הרשימה (data) אפשר למצוא מה האינדקס של האיבר הראשון בה שחוזר על עצמו, וזה גודל המעגל שלהם. אחרי שמצאתי את ארבעת המעגלים היה צריך רק לכפול את 4 המספרים כדי למצוא מתי כל ה-4 יסתנכרנו עם אות חזק מה שיגרום ל zr להוציא אות חלש ויסיים את השאלה.
זה קוד הפיתרון המלא בסקאלה:
import org.neo4j.driver.internal.messaging.request.CommitMessage
import scala.annotation.tailrec
import scala.collection.mutable
import scala.io.Source
import scala.util.chaining._
object aoc2023day20 {
val HIGH_PULSE = 1
val LOW_PULSE = -1
val demoInput: String = """broadcaster -> a, b, c
|%a -> b
|%b -> c
|%c -> inv
|&inv -> a""".stripMargin
val demoInput2: String = """broadcaster -> a
|%a -> inv, con
|&inv -> b
|%b -> con
|&con -> output""".stripMargin
def receive(sender: String, target: CommunicationModule, signal: Int, runner: Runner): CommunicationModule =
target match
case cm @ FlipFlop(name, state) if signal == LOW_PULSE && state =>
runner.sendSignal(LOW_PULSE, name)
cm.copy(state = false)
case cm @ FlipFlop(name, state) if signal == LOW_PULSE && !state =>
runner.sendSignal(HIGH_PULSE, name)
cm.copy(state = true)
case cm @ Conjunction(name, state) =>
val updatedState = runner.inputs(name).map {
case i if i == sender => Map(sender -> signal)
case i if state.contains(i) => Map(i -> state(i))
case i => Map(i -> LOW_PULSE)
}.foldLeft(Map[String, Int]())(_ ++ _)
if (updatedState.values.forall(_ == HIGH_PULSE)) {
runner.sendSignal(LOW_PULSE, name)
} else {
runner.sendSignal(HIGH_PULSE, name)
}
cm.copy(state = updatedState)
case cm @ Broadcaster(name) =>
runner.sendSignal(signal, name)
cm
case _ => target
@tailrec
def influencedBy(modules: Map[String, CommunicationModule],
inputs: Map[String, List[String]],
searching: Set[String] = Set(),
found: Set[String] = Set()): Set[String] =
if (searching.isEmpty) {
found
} else {
val nextModule = searching.head
val nextSearching = searching ++ inputs.getOrElse(nextModule, List()) - nextModule -- found
val nextFound = found + nextModule
influencedBy(modules,
inputs,
nextSearching,
nextFound)
}
def findCycleIndex[T](data: Seq[T]): Long =
data
.scanLeft(Some(Set()): Option[Set[T]]) {
case (Some(seen), newItem) if seen.contains(newItem) => None
case (Some(seen), newItem) => Some(seen + newItem)
case (None, newItem) => None
}.zipWithIndex
.find { (item, index) => item.isEmpty }.get._2 - 1
class Runner(val inputs: Map[String, List[String]], val outputs: Map[String, List[String]]) {
val pendingSignals: mutable.Queue[(String, String, Int)] = mutable.Queue()
var lowCount = 0
var highCount = 0
var buttonPresses = 0
def pressButton(): Unit =
buttonPresses += 1
this.sendSignal(LOW_PULSE, "button")
def sendSignal(signal: Int, from: String): Unit =
val to = outputs(from)
if (signal == LOW_PULSE) {
lowCount += to.size
} else if (signal == HIGH_PULSE) {
highCount += to.size
}
to.foreach { to =>
if (to == "gc" && signal == HIGH_PULSE) {
throw new Exception(s"gc ${this.buttonPresses}")
}
this.pendingSignals.enqueue((from, to, signal))
}
def handleSignals(modules: Map[String, CommunicationModule]): Map[String, CommunicationModule] =
this.pendingSignals.dequeueAll((item) => true).foldLeft(modules) { (modules, message) =>
val (from, to, signal) = message
println(s"${from} - ${if (signal == -1) "low" else "high"} - ${to}")
modules.updatedWith(to) {
case Some(cm) =>
Some(receive(from, cm, signal, this))
case _ =>
println(s"Tried to send signal to untyped module: ${to}")
None
}
}
def helper(modules: Map[String, CommunicationModule]): Map[String, CommunicationModule] =
this.pressButton()
process(modules)
def findCycleSize(modules: Map[String, CommunicationModule], end: String): Long =
val relevantModules = influencedBy(modules, inputs, Set(end))
val data = LazyList.iterate(modules)(helper).map { modules =>
modules.view.filterKeys(relevantModules.contains).toMap
}
findCycleIndex(data)
@tailrec
final def process(modules: Map[String, CommunicationModule]): Map[String, CommunicationModule] =
if (this.pendingSignals.nonEmpty) {
val updatedModules = handleSignals(modules)
this.process(updatedModules)
} else {
modules
}
}
sealed trait CommunicationModule {
def name: String
}
case class FlipFlop(name: String, state: Boolean) extends CommunicationModule
case class Conjunction(name: String, state: Map[String, Int]) extends CommunicationModule
case class Broadcaster(name: String) extends CommunicationModule
case class UntypedModule(name: String) extends CommunicationModule
def parseInput(input: Source): (Map[String, CommunicationModule], Map[String, List[String]], Map[String, List[String]]) =
input
.getLines()
.concat(List("button -> broadcaster"))
.map { line => line.split(" -> ") }
.collect { case Array(name, outputs) =>
val outputModules = outputs.split(", ").toList
val module = name match
case "broadcaster" => Broadcaster(name)
case s"%${name}" => FlipFlop(name, false)
case s"&${name}" => Conjunction(name, Map[String, Int]())
case s"${name}" => UntypedModule(name)
(module, outputModules)
}.foldLeft((
Map[String, CommunicationModule](),
Map[String, List[String]](),
Map[String, List[String]]())) { (a, v) =>
val (modules, inputs, outputs) = a
val (newModule, itsOutputs) = v
val newName = newModule.name
val updatedInputs = itsOutputs.foldLeft(inputs) { (inputs, output) =>
inputs.updatedWith(output) {
case Some(existingInputs) => Some(existingInputs :+ newName)
case None => Some(List(newName))
}
}
val updatedOutputs = outputs.updatedWith(newName) {
case Some(existingOutputs) => Some(existingOutputs ++ itsOutputs) // unreachable, because there's only one line per module
case None => Some(itsOutputs)
}
val updatedModules = modules.updated(newName, newModule)
(updatedModules, updatedInputs, updatedOutputs)
}
@main
def day20part1(): Unit =
val (modules, inputs, outputs) = parseInput(Source.fromResource("day20.txt"))
println(modules)
println(inputs)
println(outputs)
val runner = Runner(inputs, outputs)
var round = 0L
var modules_i = modules
1.to(1000).foreach { i =>
runner.pressButton()
modules_i = runner.process(modules_i)
}
println(runner.lowCount)
println(runner.highCount)
println(runner.lowCount * runner.highCount)
@main
def day20part2(): Unit =
val (modules, inputs, outputs) = parseInput(Source.fromResource("day20.txt"))
println(influencedBy(modules, inputs, Set("output")))
val runner = Runner(inputs, outputs)
var m = modules
while (true) {
m = runner.helper(m)
}
// println(runner.findCycleSize(modules, "xf"))
}
סך הכל זה היה אחד התרגילים המעייפים של הסידרה הזו, אבל אולי זה חלק מהעניין עם התרגילים במספרים הגבוהים. הנחמה היחידה היא שאנחנו לקראת הסוף.