Schedule for Posting the solutions to the website 2024 #571
Replies: 22 comments 15 replies
-
|
Cool! I volunteer for Fri 13 and Sat 21 🥳 |
Beta Was this translation helpful? Give feedback.
-
|
It seems there are already 2 PRs for the two first days from @spamegg1: #554 and #566. |
Beta Was this translation helpful? Give feedback.
-
|
I volunteer for Fri 6 :) |
Beta Was this translation helpful? Give feedback.
-
|
I volunteer for Mon 9 |
Beta Was this translation helpful? Give feedback.
-
|
I'll take day 7 (I added myself) |
Beta Was this translation helpful? Give feedback.
-
|
Count me in for Sat 14 |
Beta Was this translation helpful? Give feedback.
-
|
I’ll do 16 and 17 (I’ll be in a long-haul flight on the 17th so have to have something to do…) |
Beta Was this translation helpful? Give feedback.
-
|
I can do Wed 4th, Wed 11th |
Beta Was this translation helpful? Give feedback.
-
|
I can do tomorrow, Tue 3rd. |
Beta Was this translation helpful? Give feedback.
-
|
I can do 8th, 15th. |
Beta Was this translation helpful? Give feedback.
-
|
@merlinorg |
Beta Was this translation helpful? Give feedback.
-
|
I'll do day 12 |
Beta Was this translation helpful? Give feedback.
-
|
I'll volunteer for day 22 as well. |
Beta Was this translation helpful? Give feedback.
-
|
I would like to do day 18 as well. |
Beta Was this translation helpful? Give feedback.
-
|
I would like to volunteer for day 19 |
Beta Was this translation helpful? Give feedback.
-
|
I'd like to volunteer for day 20 |
Beta Was this translation helpful? Give feedback.
-
|
status update: finished solving, will write tomorrow |
Beta Was this translation helpful? Give feedback.
-
|
@shardulc I accidentally wrote up day 16 instead of day 15 (small numbers are hard), care to trade or have you already written it up? |
Beta Was this translation helpful? Give feedback.
-
|
I can do Day 15, no worries
Le lun. 16 déc. 2024 à 18:04, Merlin Hughes ***@***.***(mailto:Le lun. 16 déc. 2024 à 18:04, Merlin Hughes <<a href=)> a écrit :
… ***@***.***(https://github.com./shardulc) I accidentally wrote up day 16 instead of day 15 (small numbers are hard), care to trade or have you already written it up?
—
Reply to this email directly, [view it on GitHub](#571 (comment)), or [unsubscribe](https://github.com./notifications/unsubscribe-auth/ACO6YODOFUGXCWUNAZAJRG32F4BZFAVCNFSM6AAAAABS3RP7HWVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTCNJYGM3DIMQ).
You are receiving this because you were mentioned.Message ID: ***@***.***>
|
Beta Was this translation helpful? Give feedback.
-
|
any brave souls want to volunteer for the Dec 23 & 25 articles? it's not an absolute commitment. you should be fairly confident you can do it, but you don't need to be 100% confident |
Beta Was this translation helpful? Give feedback.
-
|
could try Day 23, but only as a candidate |
Beta Was this translation helpful? Give feedback.
-
|
@rayrobdod do you still intend to submit an article for day 19? |
Beta Was this translation helpful? Give feedback.
-
|
Yes |
Beta Was this translation helpful? Give feedback.
-
|
@rayrobdod I noticed that you still intend to write the article for day 19. However, we also have a submission from @AvaPL (#819) that I believe is worth merging. Thank you for your understanding! |
Beta Was this translation helpful? Give feedback.
-
|
Sorry for stealing that one! 😨 I didn't notice there was any reservation list and was convinced that after AoC is finished we can freely fill in the gaps. Hope that wasn't a problem. |
Beta Was this translation helpful? Give feedback.
-
|
not a problem! |
Beta Was this translation helpful? Give feedback.
-
|
I can do Day 25. |
Beta Was this translation helpful? Give feedback.
-
|
Looks like @merlinorg already wrote an article. |
Beta Was this translation helpful? Give feedback.
-
|
@Philippus I'm more than happy to decline mine if you want it. |
Beta Was this translation helpful? Give feedback.
-
|
Yours is fine. Happy holidays! |
Beta Was this translation helpful? Give feedback.
-
|
Interesting, thank you! |
Beta Was this translation helpful? Give feedback.
-
|
@hamzaremmal do you still intend to do day 24? @merlinorg do you still intend to submit articles for day 20 and day 23? (one of them had been incorrectly marked as "done" above) note that days 20 and 23 already have links to writeups by @TheDrawingCoder-Gamer , so one possibility would to be promote those writeups to become the blessed writeups |
Beta Was this translation helpful? Give feedback.
-
|
@SethTisue I actually already implemented it a while ago, I just haven't the find time yet to write the blog post (end of the semester deadline and exams ahead of us now). Here is the implementation of 24 (part I and part II). import scala.language.experimental.modularity
import scala.language.experimental.namedTuples
import scala.annotation.targetName
import scala.collection.mutable
/** Representation of a Wire in the [[System]] */
opaque type Wire = (name: String, value: Boolean)
/** Representation of a Gate in the [[System]] */
opaque type Gate = (lhs: String, rhs: String, op: Operation, res: String)
/** Representation of a normalised [[Gate]] */
opaque type NormalisedGate <: Gate = Gate
/** Representation of the System */
opaque type System = (wires: Seq[Wire], gates: Set[Gate])
/** Representation of a Simulated [[System]] */
opaque type SimulatedSystem <: System = System
/** Representation of a normalised [[System]] */
opaque type NormalisedSystem <: System = (wires: Seq[Wire], gates: Set[NormalisedGate])
/** Representation of a rewriting of a [[System]] */
opaque type WireRewrites = Map.WithDefault[String, String]
object Wire:
def from(name: String, value: Boolean = false): Wire =
(name = name, value = value)
end Wire
object Gate:
def and(lhs: String, rhs: String, out: String): Gate =
(lhs = lhs, rhs = rhs, op = Operation.AND, res = out)
def or(lhs: String, rhs: String, out: String): Gate =
(lhs = lhs, rhs = rhs, op = Operation.OR, res = out)
def xor(lhs: String, rhs: String, out: String): Gate =
(lhs = lhs, rhs = rhs, op = Operation.XOR, res = out)
end Gate
object System:
def from(wires: Seq[Wire], gates: Set[Gate]): System =
(wires = wires, gates = gates)
/** Return an adder that take as input two wires of [[nbits]] and outputs to a wire of [[nbits + 1]]*/
def adder(nbits: Int): System =
val wires = mutable.ListBuffer.empty[Wire]
val gates = mutable.Set.empty[Gate]
// Create the Set of Input Wires; default to '0'
for i <- 0 until nbits do wires += Wire.from(name = f"x$i%02d")
for i <- 0 until nbits do wires += Wire.from(name = f"y$i%02d")
// Build the first Half-Adder of the System
gates += Gate.xor(lhs = "x00", rhs = "y00", out = "z00")
gates += Gate.and(lhs = "x00", rhs = "y00", out = "c01")
// Build the remaining Full-Adder of the System
for i <- 1 until nbits do
val (xi, yi, zi, ci) = (f"x$i%02d", f"y$i%02d", f"z$i%02d", f"c$i%02d")
val (t1, t2, t3) = (s"t1_$i", s"t2_$i", s"t3_$i")
val cNext = if i + 1 == nbits then f"z$nbits%02d" else f"c${i+1}%02d"
gates += Gate.xor(lhs = xi, rhs = yi, out = t1)
gates += Gate.xor(lhs = t1, rhs = ci, out = zi)
gates += Gate.and(lhs = xi, rhs = yi, out = t2)
gates += Gate.and(lhs = ci, rhs = t1, out = t3)
gates += Gate.or(lhs = t2, rhs = t3, out = cNext)
end for
System.from(wires.toSeq, gates.toSet)
end adder
end System
object SimulatedSystem:
def from(wires: Seq[Wire], gates: Set[Gate]): SimulatedSystem =
(wires = wires, gates = gates)
/** Representation of a [[Gate]]'s operation */
enum Operation(fn: (Boolean, Boolean) => Boolean):
case AND extends Operation(_ & _)
case XOR extends Operation(_ ^ _)
case OR extends Operation(_ | _)
def apply(lhs: Boolean, rhs: Boolean): Boolean = fn(lhs, rhs)
end Operation
extension (wire: Wire)
def name: String = wire.name
def value: Boolean = wire.value
end extension
extension (gate: Gate)
/** What is the output [[Wire]] of the [[Gate]] */
def output: String = gate.res
/** What are the input [[Wire]]s of the [[Gate]] */
def inputs: Set[String] = Set(gate.lhs, gate.rhs)
def lhs = gate.lhs
def rhs = gate.rhs
def op = gate.op
def rewrite(dict: WireRewrites): Gate =
(lhs = dict(gate.lhs), rhs = dict(gate.rhs), op = gate.op, res = dict(gate.res))
/** Similar to [[rewrite]] but it will only try to rewrite the output */
def swap(dict: WireRewrites): Gate =
(lhs = gate.lhs, rhs = gate.rhs, op = gate.op, res = dict(gate.res))
inline def normalise: NormalisedGate =
val (lhs, rhs, op, res) = gate
if lhs > rhs then (rhs, lhs, op, res) else gate
end extension
extension (system: System)
/** The left-hand side (or x) of the addition done by the [[System]] */
def x: BigInt =
interpret(system.wires.filter(_.name.matches("x\\d\\d")).asInstanceOf)
/** The right-hand side (or y) of the addition done by the [[System]] */
def y: BigInt =
interpret(system.wires.filter(_.name.matches("y\\d\\d")).asInstanceOf)
/** ??? */
def wires: Seq[Wire] = system.wires
def gates: Set[Gate] = system.gates
def normalise: NormalisedSystem =
(system.wires, system.gates.map(_.normalise))
def rewrite(dict: WireRewrites): System =
(system.wires, system.gates.map(_.rewrite(dict)))
def swap(dict: WireRewrites): System =
(system.wires, system.gates.map(_.swap(dict)))
end extension
extension (system: NormalisedSystem)
@targetName("normalisedGate") def gates1: Set[NormalisedGate] = system.gates
end extension
extension (system: SimulatedSystem)
/** The result (or z) of the addition done by the [[System]] */
def z: BigInt =
interpret(system.wires.filter(_.name.matches("z\\d\\d")))
end extension
extension (rewrites: WireRewrites)
def apply(wire: String): String = rewrites(wire)
def toMutable: collection.mutable.Map[String, String] =
collection.mutable.Map(rewrites.toSeq*)
def union(rhs: WireRewrites): WireRewrites =
WireRewrites.from(rewrites.toMutable.addAll(rhs).toMap)
def containsSource(wire: String): Boolean =
rewrites.contains(wire)
def containsTarget(wire: String): Boolean =
rewrites.values.toSeq.contains(wire)
end extension
object WireRewrites:
def empty: WireRewrites =
Map.empty.withDefault(identity).asInstanceOf
def from(map: Map[String, String]): WireRewrites =
map.toMap.withDefault(identity).asInstanceOf
end WireRewrites
given Ordering[Wire]:
type Self = Wire
override def compare(x: Wire, y: Wire): Int =
x.name.compareTo(y.name)
end given//> using scala 3.6.2
//> using options -experimental
//> using file package.scala
import scala.language.experimental.namedTuples
import scala.collection.mutable
import scala.io.Source
import scala.util.boundary
// ================================================================================================
// ============================================ PART I ============================================
// ================================================================================================
/** Build a [[System]] from a given File */
def parse(filename: String): System =
val lines = Source.fromFile(filename)
.getLines()
.map(_.trim)
.filter(_.nonEmpty)
.toList
val wires = mutable.ListBuffer.empty[Wire]
val gates = mutable.ListBuffer.empty[Gate]
for line <- lines do line match
case s"$name: 1" => wires.addOne(Wire.from(name = name, value = true))
case s"$name: 0" => wires.addOne(Wire.from(name = name, value = false))
case s"$lhs AND $rhs -> $out" =>
gates.addOne(Gate.and(lhs = lhs, rhs = rhs, out = out))
case s"$lhs XOR $rhs -> $out" =>
gates.addOne(Gate.xor(lhs = lhs, rhs = rhs, out = out))
case s"$lhs OR $rhs -> $out" =>
gates.addOne(Gate.or(lhs = lhs, rhs = rhs, out = out))
case _ => println(s"Ignoring line '$line': Doesn't match the specified format")
end for
System.from(wires.toSeq, gates.toSet)
end parse
/** Perform topological sort of the set of [[Gate]]s */
private def sort(gates: Set[Gate]): Seq[Gate] =
val result = mutable.ListBuffer.empty[Gate]
val producerOf = gates.map(g => g.output -> g).toMap
val adjacency = mutable.Map.empty[Gate, Set[Gate]].withDefaultValue(Set.empty)
val inDegree = mutable.Map.empty[Gate, Int].withDefaultValue(0)
for gate <- gates
wire <- gate.inputs
producer <- producerOf.get(wire)
do
adjacency(producer) += gate
inDegree(gate) += 1
end for
val queue = mutable.Queue[Gate]()
queue.enqueueAll(gates.filter(gate => inDegree(gate) == 0))
while queue.nonEmpty do
val current = queue.dequeue()
result += current
for dependentGate <- adjacency(current) do
inDegree(dependentGate) -= 1
if inDegree(dependentGate) == 0 then
queue.enqueue(dependentGate)
end for
end while
result.toSeq
end sort
/** Simulate a given [[System]] */
def simulate(system: System): SimulatedSystem =
val ctx = mutable.Map.empty[String, Wire]
for case wire @ (name, _) <- system.wires do ctx(name) = wire.asInstanceOf
for gate <- sort(system.gates) do
ctx(gate.output) = Wire.from(name = gate.output, value = gate.op(ctx(gate.lhs).value, ctx(gate.rhs).value))
SimulatedSystem.from(wires = ctx.values.toSeq, gates = system.gates)
end simulate
/** Interpret the result of the simulation of the [[System]] as a [[BigInt]]*/
def interpret(wires: Seq[Wire]): BigInt =
val bits = wires.sorted
.map(wire => if wire.value then "1" else "0")
.reverse
.mkString
BigInt(bits, 2)
end interpret
/** Entrypoint to execute the code for part I */
@main def part1(input: String) =
val system = parse(input)
val simulation = simulate(system)
println(simulation.z)
end part1
// ================================================================================================
// =========================================== PART II ============================================
// ================================================================================================
// The system to fix is s1 and the system fixed is s2
// We should return a swap sugestion if unification failed or a WireRewrite if the unification was successful
def unify(system: System, expected: System, n: Int): (WireRewrites, NormalisedSystem, NormalisedSystem) =
var dict = WireRewrites.from(map(n))
var ss1 = system.normalise
var ss2 = expected.normalise
for _ <- 0 to 400 do
val (ndict, swaps, nss1, nss2) = level1(ss1.gates1, ss2.gates1, dict)
dict = dict.union(ndict)
ss1 = System.from(wires = ss1.wires, gates = nss1.map(_.asInstanceOf)).swap(swaps).normalise
ss2 = System.from(wires = ss2.wires, gates = nss2.map(_.asInstanceOf)).normalise
end for
(dict, System.from(ss1.wires, ss1.gates).normalise, System.from(ss2.wires, ss2.gates).normalise)
end unify
def level1(gates1: Set[NormalisedGate], gates2: Set[NormalisedGate], rewrites: WireRewrites): (WireRewrites, WireRewrites, Set[NormalisedGate], Set[NormalisedGate]) =
val dict = mutable.Map.empty[String, String]
val swaps = mutable.Map.empty[String, String]
val g1u = mutable.Set.empty[NormalisedGate]
val g2u = mutable.Set.empty[NormalisedGate]
boundary:
for gate <- gates1 do
val g1r = gate.rewrite(rewrites).normalise
gates2.find(level1(g1 = g1r, _)) match
case Some(g2) if ((!rewrites.containsSource(gate.output) && !rewrites.containsTarget(g2.output)) || g1r.output == g2.output) =>
dict(gate.output) = g2.output
g1u.add(gate)
g2u.add(g2)
boundary.break()
// We found an inaccuracy, we move on
case Some(g2) =>
swaps.addOne(gate.output -> g2.output)
swaps.addOne(g2.output -> gate.output)
println(s"Found an inaccuraccy. Expected: ${g2.output} but was ${gate.output} (${g1r.output})")
boundary.break()
case _ => ()
(WireRewrites.from(dict.toMap), WireRewrites.from(swaps.toMap), gates1.removedAll(g1u), gates2.removedAll(g2u))
end level1
def map(n: Int): Map[String, String] =
val wires = mutable.Map.empty[String, String]
for i <- 0 until n do
wires += f"x$i%02d" -> f"x$i%02d"
wires += f"y$i%02d" -> f"y$i%02d"
wires += f"z$i%02d" -> f"z$i%02d"
wires += f"z$n%02d" -> f"z$n%02d"
wires.toMap
// From this rule, we can either validate the output, or find an inaccurary
def level1(g1: NormalisedGate, g2: NormalisedGate): Boolean =
g1.lhs == g2.lhs && g1.rhs == g2.rhs && g1.op == g2.op
/** Entrypoint to execute the code for part II */
@main def part2(input: String) =
val system = parse(input)
val adder = System.adder(45)
val unification = unify(system, adder, 45)
println(f"Gates before unification: ${system.gates.size}%03d - ${adder.gates.size}%03d")
println(f"Gates after unification : ${unification._2.gates.size}%03d - ${unification._3.gates.size}%03d")
println(unification._1.toMutable.mkString("===== DICT =====\n", "\n", "\n========"))
println(unification._2.gates.mkString("===== ORIG =====\n", "\n", "\n========"))
println(unification._3.gates.mkString("===== ADDR =====\n", "\n", "\n========"))
end part2 |
Beta Was this translation helpful? Give feedback.
-
|
@SethTisue Btw, this implementation highlighted a couple of issues in the compiler itself (as I attempted to use named tuples for it), and I already minimised two issues this morning (as I had some time for it) scala/scala3#22324 and scala/scala3#22320. I still need to minimise the problems where I use |
Beta Was this translation helpful? Give feedback.
-
|
@SethTisue and part II is not fully automated, it's half-automated as the algorithm is not complete and we have to verify and compare between the little remaining gates to flag some swaps. In the case of my specific input, I only have to detect one of the four swaps manually, for the rest, they were all detected automatically. |
Beta Was this translation helpful? Give feedback.
-
|
@SethTisue sorry, i kept rewiting the articles in 70% state, will open PR soon |
Beta Was this translation helpful? Give feedback.
-
|
@hamzaremmal I think those sorts of technical details (named tuples, compiler bugs, and such) will actually be interesting to many readers 👍 @scarf005 ok cool, no worries! |
Beta Was this translation helpful? Give feedback.
-
Here is a separate post for scheduling the solutions for Scala Advent of Code.
It would be great for people to volunteer for specific days and we can update the schedule here.
Responsibility
You should write a description of the solution, and provide the code in the main body of the article, as in these examples:
day 1 2023
day 2 2023
Please make sure that you do both part 1 and part 2 of the challenge before you write the article
the solution should only use what is available in the Scala 3 standard library, with the following two entry points:
Please avoid File I/O, and assume that the input is already read from file/text input. We will compile your solutions with Scala.js so that they can be run in the browser.
it is not necessary to add the "Solve it in the browser section" as that requires a bit more manual work that we can handle if necessary.
Schedule
Beta Was this translation helpful? Give feedback.
All reactions