Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Advent of Code 2018 Day 7
import cats._
import cats.data.State
import cats.effect.{ExitCode, IO, IOApp}
import cats.implicits._
import scala.io.Source
// Tweet: https://twitter.com/francoaramburo/status/1081303164660473857
object Main extends IOApp {
override def run(args: List[String]): IO[ExitCode] =
for {
data <- loadData
graph <- parseGraph(data)
_ = println(">>> GRAPH OF STEPPES")
_ = graph.foreach(println)
_ = println(">>> PART 1: Simple")
(_, output1) = simpleAlgorithm[PureState, String]("").run(graph).value
_ = println(output1)
_ = println(">>> PART 2: Concurrent")
initTime = TimeGraph(0, graph.map { case (step, dependencies) =>
(step, Node(Work.fresh(step), dependencies))
})
(_, output2) = algorithmConcurrent("", Worker.listOf(5)).run(initTime).value
_ = println(output2)
} yield ExitCode.Success
def loadData: IO[List[String]] =
IO {
Source.fromResource("data.txt").getLines.toList
}
/** Quick dirty parser :P */
def parseGraph(lines: List[String]): IO[PureGraph] = {
val RegExp = """Step ([A-Z]) must be finished before step ([A-Z]) can begin\.""".r
for {
parsed <- lines.traverse[IO, (String, Set[String])] {
case RegExp(a, b) =>
// b "requires" a
IO.pure((b, Set(a)))
case _ =>
IO.raiseError(new RuntimeException("Input corrupted: \n" + lines.mkString("\n")))
}
allNodes = parsed.foldLeft(Set.empty[String]) {
case (set, (_, nSet)) => set.union(nSet)
}
graph1 = parsed.foldLeft[PureGraph](Map.empty) {
case (graph0, (a, setB)) =>
val old = graph0.getOrElse(a, Set.empty)
graph0 + (a -> old.union(setB))
}
graph = allNodes.foldLeft(graph1) {
case (graph0, node) =>
val old = graph0.getOrElse(node, Set.empty)
graph0 + (node -> old)
}
} yield graph
}
/* --------------------------- PART 1: SIMPLE ---------------------------------------------*/
/** This algorithm is in Finally Tagless form, a solution using pure structure (the state monad) is provided
* but an alternative instance of `DAGOps` can be provided to increase performance.
*
* The advantages of using first an implementation with the State Monad are:
* - Easy to reason
* - 1 to 1 mapping with pure mathematical expressions
* - Becomes an "oracle" to test other implementations against, by using property based testing
*/
def simpleAlgorithm[F[_] : Monad, N: Ordering](output: String)(implicit ops: DAGOps[F, N]): F[String] = {
for {
next <- ops.getNext
output <-
if (next.isEmpty) output.pure[F]
else for {
done <- ops.done(next.toList.min)
doneStr <- ops.show(done)
output0 = output ++ doneStr
output1 <- simpleAlgorithm[F, N](output0)
} yield output1
} yield output
}
/** A mapping from a step to it's dependencies */
type PureGraph = Map[String, Set[String]]
/** Monad that keeps the state of the graph */
type PureState[A] = State[PureGraph, A]
trait DAGOps[F[_], N] {
def show(node: N): F[String]
def getNext: F[Set[N]]
def done(node: N): F[N]
}
implicit def pureCorrectOps: DAGOps[PureState, String] =
new DAGOps[PureState, String] {
override def show(node: String): PureState[String] =
State.pure(node)
override def getNext: PureState[Set[String]] =
State.inspect { graph => graph.keySet.filter(graph(_).isEmpty) }
override def done(node: String): PureState[String] =
State.modify[PureGraph] {
_.mapValues(_.filter(_ != node)) - node
}.map(_ => node)
}
/* --------------------------- PART 2: CONCURRENT ---------------------------------------------*/
/** This implementation could also be translated to a Finally Tagless style, to provide better performance or truly
* concurrent semantics (by changing the implementation to something like the IO monad or Streams)
*
* In this implementation we model time as state to be kept in the same way we did with the graph on the simple
* algorithm, in a State Monad. This technique together with Finally Tagless is very good to model and test concurrent
* and distributed systems.
*
* An improvement could be to move the state of the workers inside the effect, and in this case the State Monad.
* Also this algorithm could be adapted to be a generalization of the previous one.
*/
def algorithmConcurrent(result: String, workers: List[Worker]): TimeState[String] =
for {
itIsDone <- isDone
res <-
if (itIsDone) result.pure[TimeState]
else for {
now <- getTime
_ = print(now + "\t\t")
workDone <- workers.traverse[TimeState, (Worker, String)](_.doWork(now))
res0 = workDone.map(_._2).sorted.mkString
_ <- moveTime
_ = print(result ++ res0 + "\n")
res1 <- algorithmConcurrent(result ++ res0, workDone.map(_._1))
} yield res1
} yield res
type TimeState[A] = State[TimeGraph, A]
def getTime: TimeState[Int] =
State.inspect(_.time)
def moveTime: TimeState[Unit] =
State.modify[TimeGraph](g => g.copy(time = g.time + 1))
def isDone: TimeState[Boolean] =
State.inspect(_.graph.isEmpty)
/** Steps which are ready are modeled as steps in the Map which have no more dependencies.
* If there are no ready steps, return no work, and if there is work to be done, take the next one alphabetically
* and lock it.
*/
def getNext: TimeState[Option[Work]] =
State[TimeGraph, Option[Work]] { g =>
val now = g.time
// Steps
val ready = g.graph.keySet.filter { key =>
val node = g.graph(key)
node.dependencies.isEmpty && !node.work.locked
}
if (ready.isEmpty) (g, None)
else g.lockNode(now, ready.toList.min)
}
/** Finishing a step means to remove it from the graph and from all the steppe's dependencies. */
def done(step: String): TimeState[Unit] = {
State.modify[TimeGraph] { _.done(step) }
}
case class Work(step: String, timeWhenInitiated: Int, locked: Boolean) {
def take(now: Int): Work =
copy(timeWhenInitiated = now, locked = true)
def isDone(now: Int): Boolean = {
val finishTime = timeWhenInitiated + duration
now >= finishTime
}
def duration: Int =
(step match {
case "A" => 1
case "B" => 2
case "C" => 3
case "D" => 4
case "E" => 5
case "F" => 6
case "G" => 7
case "H" => 8
case "I" => 9
case "J" => 10
case "K" => 11
case "L" => 12
case "M" => 13
case "N" => 14
case "O" => 15
case "P" => 16
case "Q" => 17
case "R" => 18
case "S" => 19
case "T" => 20
case "U" => 21
case "V" => 22
case "W" => 23
case "X" => 24
case "Y" => 25
case "Z" => 26
}) + 60
}
object Work {
def fresh(step: String): Work =
Work(step, -1, locked = false)
}
case class Worker(work: Option[Work]) {
def doWork(now: Int): TimeState[(Worker, String)] = {
print(work.fold(".")(_.step) + "\t\t")
work match {
case Some(work0) =>
if(work0.isDone(now))
for {
_ <- done(work0.step)
work <- getNext
} yield Worker(work) -> work0.step
else
State.pure(this -> "")
case None =>
getNext.map(work => Worker(work) -> "")
}
}
}
object Worker {
def listOf(n: Int): List[Worker] =
List.fill(n)(Worker(None))
}
case class Node(work: Work, dependencies: Set[String]) {
def done(step: String): Node =
copy(dependencies = dependencies.filter(_ != step))
}
case class TimeGraph(time: Int, graph: Map[String, Node]) {
def lockNode(now: Int, step: String): (TimeGraph, Option[Work]) = {
(for {
node <- graph.get(step)
_ <- if (node.work.locked) None else Some(())
newNode = Node(node.work.take(now), node.dependencies)
} yield graph.updated(step, newNode) -> newNode) match {
case None =>
(this, None)
case Some((newGraph, newNode)) =>
(copy(graph = newGraph), Some(newNode.work))
}
}
def done(step: String): TimeGraph = {
val newGraph = graph.mapValues { node =>
node.done(step)
} - step
copy(graph = newGraph)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.