Last active
April 30, 2025 00:34
-
-
Save horothesun/5482a076bc2351e81ea02903bce2b033 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //> using scala 3.6.4 | |
| //> using jvm temurin:21 | |
| // | |
| //> using dep org.typelevel::cats-core:2.13.0 | |
| //> using dep org.typelevel::cats-effect:3.6.1 | |
| //> using dep io.github.timwspence::cats-stm:0.13.5 | |
| // | |
| import cats.data.NonEmptySet | |
| import cats.effect.{IO, IOApp} | |
| import cats.effect.std.Random | |
| import cats.kernel.Order | |
| import cats.syntax.all.* | |
| import io.github.timwspence.cats.stm.* | |
| import scala.concurrent.duration.* | |
| val TOTAL_NUMBER_OF_REINDEERS: Int = 9 | |
| val TOTAL_NUMBER_OF_ELVES: Int = 10 | |
| val MAX_NUMBER_OF_ELVES_WITH_ISSUES: Int = 3 | |
| val GLOBAL_SPEED_UP_FACTOR: Double = 2.0 | |
| val MIN_DELIVERY_MILLIS: Int = 5_000 | |
| val MAX_DELIVERY_MILLIS: Int = 10_000 | |
| val MIN_SHOP_TO_HUT_MILLIS: Int = 1_000 | |
| val MAX_SHOP_TO_HUT_MILLIS: Int = 4_000 | |
| val MIN_SHOP_TO_FACTORY_MILLIS: Int = 1_000 | |
| val MAX_SHOP_TO_FACTORY_MILLIS: Int = 4_000 | |
| val MIN_VACATION_MILLIS: Int = 30_000 | |
| val MAX_VACATION_MILLIS: Int = 60_000 | |
| val MIN_ISSUE_FIXING_MILLIS: Int = 10_000 | |
| val MAX_ISSUE_FIXING_MILLIS: Int = 20_000 | |
| val MIN_TIME_TO_ISSUE_MULTIPLIER: Int = 8 | |
| val MAX_TIME_TO_ISSUE_MULTIPLIER: Int = 15 | |
| val BASE_TIME_TO_ISSUE_MILLIS: Int = 10_000 | |
| object Main extends IOApp.Simple: | |
| override def run: IO[Unit] = STM.runtime[IO].flatMap(run) | |
| def run(stm: STM[IO]): IO[Unit] = | |
| import stm.* | |
| extension [A](txn: Txn[A]) def atomically: IO[A] = stm.commit(txn) | |
| case class Santa(shop: TVar[Shop], doorstep: TVar[Doorstep], hut: TVar[Hut], factory: TVar[Factory]): | |
| def kickoffAllActivities: IO[Unit] = (sendAllReindeersOnVacation, sendAllElvesBackToWork).parTupled.void | |
| def sendAllReindeersOnVacation: IO[Unit] = waitForAllReindeersInHut | |
| .flatMap(_.occupants.toList.parTraverseVoid(_.goOnVacation(hut, shop, doorstep, santa = this))) | |
| def sendAllElvesBackToWork: IO[Unit] = | |
| factory.get.atomically.flatMap( | |
| _.occupants.toList.parTraverseVoid(_.resumeWork(factory, shop, doorstep, santa = this)) | |
| ) | |
| /* Santa needs to be responsible for sending the last reindeer back to the hut after waking up, because if he | |
| gets woken up by an elf while the reindeer is there too, the reindeer will never reach Santa at the hut. */ | |
| def wakeUp: IO[Unit] = | |
| doorstep.get.atomically.flatMap { | |
| case Doorstep.Empty => IO.println("Santa was woken up but nobody's at the door!") | |
| case Doorstep.JustElves(_) => goFromShopToFactory | |
| case Doorstep.JustReindeer(r) => goFromShopToHutAndSendReindeerToo(r) | |
| case Doorstep.ReindeerAndElves(r, _) => goFromShopToHutAndSendReindeerToo(r) | |
| } | |
| def goFromShopToHutAndSendReindeerToo(r: Reindeer): IO[Unit] = | |
| (goFromShopToHut, r.goFromShopToHut(shop, doorstep, hut)).parTupled.void | |
| def goFromShopToHut: IO[Unit] = | |
| for { | |
| _ <- IO.println("Santa left his shop to reach the hut") | |
| _ <- travelFromShopToHut | |
| _ <- IO.println("Santa arrived at the hut from his shop") | |
| _ <- waitForAllReindeersInHut | |
| _ <- IO.println("Santa found all reindeers in the hut: ready for delivery!") | |
| _ <- deliverPresents | |
| _ <- ( | |
| sendAllReindeersOnVacation, | |
| for { | |
| _ <- IO.println("Santa left the hut to reach his shop") | |
| _ <- travelFromHutToShop | |
| _ <- IO.println("Santa arrived at his shop from the hut") | |
| _ <- backToSleep | |
| } yield () | |
| ).parTupled | |
| } yield () | |
| def goFromShopToFactory: IO[Unit] = | |
| for { | |
| _ <- IO.println("Santa left his shop to reach the factory") | |
| _ <- travelFromShopToFactory | |
| _ <- IO.println("Santa arrived at the factory from his shop" + "\nSanta started fixing the issues") | |
| issueFixingTime <- Random[IO] | |
| .betweenInt(minInclusive = MIN_ISSUE_FIXING_MILLIS, maxExclusive = 1 + MAX_ISSUE_FIXING_MILLIS) | |
| .map(t => (t / GLOBAL_SPEED_UP_FACTOR).millis) | |
| _ <- IO.sleep(issueFixingTime) | |
| _ <- IO.println("Santa fixed all the issues!") | |
| _ <- goFromFactoryToShop | |
| } yield () | |
| def goFromFactoryToShop: IO[Unit] = | |
| for { | |
| _ <- IO.println("Santa left the factory to reach his shop") | |
| _ <- travelFromFactoryToShop | |
| _ <- IO.println("Santa arrived at his shop from the factory") | |
| elvesReadyToGoBack <- tellElvesAsReadyToGoBack | |
| _ <- backToSleep | |
| _ <- elvesReadyToGoBack.toList.parTraverseVoid(_.goFromShopToFactory(santa = this, shop, doorstep, factory)) | |
| } yield () | |
| def tellElvesAsReadyToGoBack: IO[Set[Elf]] = | |
| for { | |
| elvesReadyToGoBack <- (for { | |
| _ <- doorstep.modify(_.markedElvesAsReadyToGoBack) | |
| es <- doorstep.get.map(_.elves) | |
| } yield es).atomically | |
| elvesReadyToGoBackText = elvesReadyToGoBack.toList.sorted.map(e => s"#${e.id}").mkString("{ ", ", ", " }") | |
| _ <- IO.println(s"Santa told all elves at his doorstep to go back: $elvesReadyToGoBackText") | |
| } yield elvesReadyToGoBack | |
| def waitForAllReindeersInHut: IO[Hut] = hut.get.flatTap(h => stm.check(h.isFull)).atomically | |
| def deliverPresents: IO[Unit] = | |
| for { | |
| _ <- hut.modify(_ => Hut.empty).atomically | |
| _ <- IO.println("Delivery started!") | |
| deliveryTime <- Random[IO] | |
| .betweenInt(minInclusive = MIN_DELIVERY_MILLIS, maxExclusive = 1 + MAX_DELIVERY_MILLIS) | |
| .map(t => (t / GLOBAL_SPEED_UP_FACTOR).millis) | |
| _ <- IO.sleep(deliveryTime) | |
| _ <- IO.println("Delivery completed!") | |
| _ <- hut.modify(_ => Hut.full).atomically | |
| } yield () | |
| def backToSleep: IO[Unit] = | |
| shop.modify(_.addedSanta).atomically *> IO.println("Santa went back to sleep") | |
| extension (reindeer: Reindeer) | |
| def goOnVacation(hut: TVar[Hut], shop: TVar[Shop], doorstep: TVar[Doorstep], santa: Santa): IO[Unit] = | |
| for { | |
| _ <- hut.modify(_.removed(reindeer)).atomically | |
| _ <- IO.println(s"Reindeer #${reindeer.id} gone on vacation") | |
| vacationTime <- Random[IO] | |
| .betweenInt(minInclusive = MIN_VACATION_MILLIS, maxExclusive = 1 + MAX_VACATION_MILLIS) | |
| .map(t => (t / GLOBAL_SPEED_UP_FACTOR).millis) | |
| _ <- IO.sleep(vacationTime) | |
| _ <- comeBackFromVacation(hut, shop, doorstep, santa) | |
| } yield () | |
| def comeBackFromVacation(hut: TVar[Hut], shop: TVar[Shop], doorstep: TVar[Doorstep], santa: Santa): IO[Unit] = | |
| for { | |
| (isLastToComeBack, newHut) <- (for { | |
| isLast <- hut.get.map(h => h.size == h.maxSize - 1) | |
| _ <- if (isLast) doorstep.modify(_.added(reindeer)) else hut.modify(_.added(reindeer)) | |
| h <- hut.get | |
| } yield (isLast, h)).atomically | |
| _ <- IO.println(s"Reindeer #${reindeer.id} came back${if (isLastToComeBack) " (LAST ONE)" else ""}") | |
| _ <- | |
| if (isLastToComeBack) | |
| for { | |
| _ <- IO.println(s"Reindeer #${reindeer.id} left the hut to reach Santa's shop") | |
| _ <- travelFromHutToShop | |
| _ <- IO.println(s"Reindeer #${reindeer.id} arrived at Santa's shop from the hut") | |
| _ <- wakeUpSanta(santa, shop, message = s"Reindeer #${reindeer.id} is waking up Santa") | |
| } yield () | |
| else IO.unit | |
| } yield () | |
| def goFromShopToHut(shop: TVar[Shop], doorstep: TVar[Doorstep], hut: TVar[Hut]): IO[Unit] = | |
| for { | |
| _ <- IO.println(s"Reindeer #${reindeer.id} left Santa's shop to reach the hut") | |
| _ <- travelFromShopToHut | |
| newHut <- (for { | |
| (_, newDoorstep) <- doorstep.get.map(_.removedReindeer) | |
| _ <- doorstep.set(newDoorstep) | |
| _ <- hut.modify(_.added(reindeer)) | |
| h <- hut.get | |
| } yield h).atomically | |
| _ <- IO.println(s"Reindeer #${reindeer.id} arrived at the hut from Santa's shop") | |
| } yield () | |
| extension (elf: Elf) | |
| def resumeWork(factory: TVar[Factory], shop: TVar[Shop], doorstep: TVar[Doorstep], santa: Santa): IO[Unit] = | |
| for { | |
| _ <- IO.println(s"Elf #${elf.id} is back at work") | |
| _ <- workUntilIssueOccurs | |
| _ <- IO.println(s"Elf #${elf.id} encountered an issue!") | |
| _ <- goFromFactoryToShop(factory, shop, doorstep, santa) | |
| } yield () | |
| def workUntilIssueOccurs: IO[Unit] = | |
| for { | |
| variableMillis <- Random[IO].betweenInt(minInclusive = 1, maxExclusive = 1 + BASE_TIME_TO_ISSUE_MILLIS) | |
| timeToIssue <- Random[IO] | |
| .betweenInt(minInclusive = MIN_TIME_TO_ISSUE_MULTIPLIER, maxExclusive = 1 + MAX_TIME_TO_ISSUE_MULTIPLIER) | |
| .map(m => ((variableMillis + m * BASE_TIME_TO_ISSUE_MILLIS) / GLOBAL_SPEED_UP_FACTOR).millis) | |
| _ <- IO.sleep(timeToIssue) | |
| } yield () | |
| def goFromFactoryToShop( | |
| factory: TVar[Factory], | |
| shop: TVar[Shop], | |
| doorstep: TVar[Doorstep], | |
| santa: Santa | |
| ): IO[Unit] = | |
| for { | |
| _ <- factory.modify(_.removed(elf)).atomically | |
| _ <- IO.println(s"Elf #${elf.id} left the factory to reach Santa's shop") | |
| _ <- travelFromFactoryToShop | |
| (doesCompleteWaitingGroup, newDoorstep) <- (for { | |
| oldDoorstep <- doorstep.get | |
| _ <- stm.check(oldDoorstep.areNewElvesAllowed) | |
| _ <- doorstep.modify(_.added(elf)) | |
| isLast = oldDoorstep.numberOfElves == MAX_NUMBER_OF_ELVES_WITH_ISSUES - 1 | |
| newDoorstep <- doorstep.get | |
| } yield (isLast && oldDoorstep.areAllElvesWaiting, newDoorstep)).atomically | |
| elvesWaitingAtDoorstep = s"${newDoorstep.numberOfElves} / $MAX_NUMBER_OF_ELVES_WITH_ISSUES" | |
| _ <- | |
| if (doesCompleteWaitingGroup) | |
| IO.println(s"Elf #${elf.id} completed the waiting group at the doorstep ($elvesWaitingAtDoorstep)") *> | |
| wakeUpSanta(santa, shop, message = s"Elf #${elf.id} is waking up Santa") | |
| else IO.println(s"Elf #${elf.id} joined the others at the doorstep ($elvesWaitingAtDoorstep)") | |
| } yield () | |
| def goFromShopToFactory( | |
| santa: Santa, | |
| shop: TVar[Shop], | |
| doorstep: TVar[Doorstep], | |
| factory: TVar[Factory] | |
| ): IO[Unit] = | |
| for { | |
| _ <- doorstep.modify(_.removedElf(elf)).atomically | |
| _ <- IO.println(s"Elf #${elf.id} left Santa's shop to reach the factory") | |
| _ <- travelFromShopToFactory | |
| _ <- factory.modify(_.added(elf)).atomically | |
| _ <- IO.println(s"Elf #${elf.id} arrived at the factory") | |
| _ <- resumeWork(factory, shop, doorstep, santa) | |
| } yield () | |
| def wakeUpSanta(santa: Santa, shop: TVar[Shop], message: String): IO[Unit] = | |
| for { | |
| _ <- (for { | |
| isSantaAsleep <- shop.get.map(_.isSantaAsleep) | |
| _ <- stm.check(isSantaAsleep) | |
| _ <- shop.modify(_.removedSanta) | |
| } yield ()).atomically | |
| _ <- IO.println(message) | |
| _ <- santa.wakeUp | |
| } yield () | |
| // Main | |
| ( | |
| TVar.of(Shop.SleepingSanta).atomically, | |
| TVar.of(Doorstep.Empty).atomically, | |
| TVar.of(Hut.full).atomically, | |
| TVar.of(Factory.full).atomically | |
| ).parFlatMapN { (shop, doorstep, hut, factory) => | |
| IO.println(s"START! | $TOTAL_NUMBER_OF_REINDEERS reindeers | $TOTAL_NUMBER_OF_ELVES elves") *> | |
| Santa(shop, doorstep, hut, factory).kickoffAllActivities | |
| } | |
| // Utils | |
| def travelFromHutToShop: IO[Unit] = travelFromShopToHut | |
| def travelFromShopToHut: IO[Unit] = Random[IO] | |
| .betweenInt(minInclusive = MIN_SHOP_TO_HUT_MILLIS, maxExclusive = 1 + MAX_SHOP_TO_HUT_MILLIS) | |
| .flatMap(t => IO.sleep((t * GLOBAL_SPEED_UP_FACTOR).millis)) | |
| def travelFromFactoryToShop: IO[Unit] = travelFromShopToFactory | |
| def travelFromShopToFactory: IO[Unit] = Random[IO] | |
| .betweenInt(minInclusive = MIN_SHOP_TO_FACTORY_MILLIS, maxExclusive = 1 + MAX_SHOP_TO_FACTORY_MILLIS) | |
| .flatMap(t => IO.sleep((t * GLOBAL_SPEED_UP_FACTOR).millis)) | |
| // Models | |
| trait IDed: | |
| val id: Int | |
| case class Reindeer(id: Int) extends IDed | |
| object Reindeer: | |
| given Ordering[Reindeer] = Ordering.by(_.id) | |
| case class Elf(id: Int) extends IDed | |
| object Elf: | |
| given Order[Elf] = Order.fromOrdering[Elf] | |
| given Ordering[Elf] = Ordering.by(_.id) | |
| enum Shop: | |
| case Empty, SleepingSanta | |
| def isSantaAsleep: Boolean = this match | |
| case Empty => false | |
| case SleepingSanta => true | |
| def addedSanta: Shop = this match | |
| case Empty => SleepingSanta | |
| case SleepingSanta => this | |
| def removedSanta: Shop = this match | |
| case Empty => this | |
| case SleepingSanta => Empty | |
| enum ElfStatus: | |
| case Waiting, ReadyToGoBack | |
| object ElfStatus: | |
| given Order[ElfStatus] = Order.by(_.ordinal) | |
| enum Doorstep: | |
| case Empty | |
| case JustReindeer(r: Reindeer) | |
| case JustElves(es: NonEmptySet[(Elf, ElfStatus)]) | |
| case ReindeerAndElves(r: Reindeer, es: NonEmptySet[(Elf, ElfStatus)]) | |
| def numberOfElves: Int = this match | |
| case Empty | JustReindeer(_) => 0 | |
| case JustElves(es) => es.size.toInt | |
| case ReindeerAndElves(_, es) => es.size.toInt | |
| def elves: Set[Elf] = | |
| def aux(es: NonEmptySet[(Elf, ElfStatus)]): Set[Elf] = es.map(_._1).toSortedSet.toSet | |
| this match | |
| case Empty | JustReindeer(_) => Set.empty | |
| case JustElves(es) => aux(es) | |
| case ReindeerAndElves(r, es) => aux(es) | |
| def areAllElvesWaiting: Boolean = | |
| def aux(es: NonEmptySet[(Elf, ElfStatus)]): Boolean = es.map(_._2).forall(_ == ElfStatus.Waiting) | |
| this match | |
| case Empty | JustReindeer(_) => false | |
| case JustElves(es) => aux(es) | |
| case ReindeerAndElves(_, es) => aux(es) | |
| def removedElf(elf: Elf): Doorstep = this match | |
| case Empty | JustReindeer(_) => this | |
| case JustElves(es) => | |
| val found = es.find { case (e, s) => e == elf } | |
| found match | |
| case None => this | |
| case Some(v) => | |
| val newElves = es.toSortedSet - v | |
| newElves.toNes.fold(ifEmpty = Empty)(nes => JustElves(nes)) | |
| case ReindeerAndElves(r, es) => | |
| val found = es.find { case (e, s) => e == elf } | |
| found match | |
| case None => this | |
| case Some(v) => | |
| val newElves = es.toSortedSet - v | |
| newElves.toNes.fold(ifEmpty = JustReindeer(r))(nes => ReindeerAndElves(r, nes)) | |
| def areNewElvesAllowed: Boolean = | |
| def aux(es: NonEmptySet[(Elf, ElfStatus)]): Boolean = es.size < MAX_NUMBER_OF_ELVES_WITH_ISSUES | |
| this match | |
| case Empty | JustReindeer(_) => true | |
| case JustElves(es) => aux(es) | |
| case ReindeerAndElves(_, es) => aux(es) | |
| def added(r: Reindeer): Doorstep = this match | |
| case Empty => JustReindeer(r) | |
| case JustReindeer(_) | ReindeerAndElves(_, _) => this | |
| case JustElves(es) => ReindeerAndElves(r, es) | |
| def added(e: Elf): Doorstep = this match | |
| case Empty => JustElves(NonEmptySet.one((e, ElfStatus.Waiting))) | |
| case JustReindeer(r) => ReindeerAndElves(r, NonEmptySet.of((e, ElfStatus.Waiting))) | |
| case JustElves(es) => JustElves(es.add((e, ElfStatus.Waiting))) | |
| case ReindeerAndElves(r, es) => ReindeerAndElves(r, es.add((e, ElfStatus.Waiting))) | |
| def removedReindeer: (Option[Reindeer], Doorstep) = this match | |
| case Empty | JustElves(_) => (None, this) | |
| case JustReindeer(r) => (Some(r), Empty) | |
| case ReindeerAndElves(r, es) => (Some(r), JustElves(es)) | |
| def markedElvesAsReadyToGoBack: Doorstep = | |
| def aux(es: NonEmptySet[(Elf, ElfStatus)]): NonEmptySet[(Elf, ElfStatus)] = | |
| es.map((e, _) => (e, ElfStatus.ReadyToGoBack)) | |
| this match | |
| case Empty | JustReindeer(_) => this | |
| case JustElves(es) => JustElves(aux(es)) | |
| case ReindeerAndElves(r, es) => ReindeerAndElves(r, aux(es)) | |
| case class Building[A <: IDed](maxSize: Int, occupants: Set[A])(using Ordering[A]): | |
| val size: Int = occupants.size | |
| val isFull: Boolean = occupants.size == maxSize | |
| def added(a: A): Building[A] = Building(maxSize, occupants + a) | |
| def removed(a: A): Building[A] = Building(maxSize, occupants - a) | |
| override def toString: String = occupants.toList.sorted.map(o => s"#${o.id}").mkString("{ ", ", ", " }") | |
| type Hut = Building[Reindeer] | |
| object Hut: | |
| def full: Hut = Building( | |
| maxSize = TOTAL_NUMBER_OF_REINDEERS, | |
| occupants = Range.inclusive(1, TOTAL_NUMBER_OF_REINDEERS).map(Reindeer(_)).toSet | |
| ) | |
| def empty: Hut = Building(maxSize = TOTAL_NUMBER_OF_REINDEERS, occupants = Set.empty) | |
| type Factory = Building[Elf] | |
| object Factory: | |
| def full: Factory = Building( | |
| maxSize = TOTAL_NUMBER_OF_ELVES, | |
| occupants = Range.inclusive(1, TOTAL_NUMBER_OF_ELVES).map(Elf(_)).toSet | |
| ) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment