Day 22: Sand

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

  • cvttsd2si
    2·
    11 months ago

    Scala3

    Not much to say about this, very straightforward implementation that was still fast enough

    case class Pos3(x: Int, y: Int, z: Int)
case class Brick(blocks: List[Pos3]):
    def dropBy(z: Int) = Brick(blocks.map(b => b.copy(z = b.z - z)))
    def isSupportedBy(other: Brick) = ???

def parseBrick(a: String): Brick = a match
    case s"$x1,$y1,$z1~$x2,$y2,$z2" => Brick((for x <- x1.toInt to x2.toInt; y <- y1.toInt to y2.toInt; z <- z1.toInt to z2.toInt yield Pos3(x, y, z)).toList)

def dropOn(bricks: List[Brick], brick: Brick): (List[Brick], List[Brick]) =
    val occupied = bricks.flatMap(d => d.blocks.map(_ -> d)).toMap

    @tailrec def go(d: Int): (Int, List[Brick]) =
        val dropped = brick.dropBy(d).blocks.toSet
        if dropped.intersect(occupied.keySet).isEmpty && !dropped.exists(_.z <= 0) then
            go(d + 1)
        else
            (d - 1, occupied.filter((p, b) => dropped.contains(p)).map(_._2).toSet.toList)
    
    val (d, supp) = go(0)
    (brick.dropBy(d) :: bricks, supp)

def buildSupportGraph(bricks: List[Brick]): Graph[Brick, DiEdge[Brick]] =
    val (bs, edges) = bricks.foldLeft((List[Brick](), List[DiEdge[Brick]]()))((l, b) => 
        val (bs, supp) = dropOn(l._1, b)
        (bs, supp.map(_ ~> bs.head) ++ l._2)
    )
    Graph() ++ (bs, edges)

def parseSupportGraph(a: List[String]): Graph[Brick, DiEdge[Brick]] =
    buildSupportGraph(a.map(parseBrick).sortBy(_.blocks.map(_.z).min))

def wouldDrop(g: Graph[Brick, DiEdge[Brick]], b: g.NodeT): Long =
    @tailrec def go(shaking: List[g.NodeT], falling: Set[g.NodeT]): List[g.NodeT] = 
        shaking match
            case h :: t => 
                if h.diPredecessors.forall(falling.contains(_)) then
                    go(h.diSuccessors.toList ++ t, falling + h)
                else
                    go(t, falling)
            case _ => falling.toList
    
    go(b.diSuccessors.toList, Set(b)).size

def task1(a: List[String]): Long = parseSupportGraph(a).nodes.filter(n => n.diSuccessors.forall(_.inDegree > 1)).size
def task2(a: List[String]): Long = 
    val graph = parseSupportGraph(a)
    graph.nodes.toList.map(wouldDrop(graph, _) - 1).sum