AoC Day 16

aoc16.scala

package advent

import cats.syntax.all._

object Sixteen extends Inputs:
  type Rule = Int => Boolean
  type Ticket = List[Int]
  type TicketPosition = List[Int -> Int]
  
  def parseRule: String => String \/ Rule = { s =>
    val ruleRe = """(\d+)-(\d+) or (\d+)-(\d+)""".r.unanchored
    s match 
      case ruleRe(min1, max1, min2, max2) => Right((i: Int) => (i >= min1.toInt && i <= max1.toInt) || (i >= min2.toInt && i <= max2.toInt))
      case _ => Left(s"$s can't be parsed")
  }
  
  
  def invalidFields: List[Rule] => Ticket => List[Int] = rules => ticket => 
    ticket.filter(i => !rules.exists(r => r(i)))
  
  def parseInput: String => String \/ (List[Rule], Ticket, List[Ticket]) = s => s.split("(?m)^\n") match {
    case Array(ruleS, myTicketS, nearbyTicketsS) => for {
      rules <- ruleS.linesIterator.toList.traverse(parseRule)
      ticket <- myTicketS.linesIterator.toList.last.split(",").toList.traverse(n => n.toIntOption.toRight(s"$n is not a number"))
      nearbyTickets <- nearbyTicketsS.linesIterator.drop(1).toList.traverse(
        _.split(",").toList.traverse(n => n.toIntOption.toRight(s"$n is not a number"))
      )
    } yield (rules, ticket, nearbyTickets)
    case _ => Left(s"$s cannot be split into things")
  }

  @main def m16 = {
    val dummy = """class: 1-3 or 5-7
                  |row: 6-11 or 33-44
                  |seat: 13-40 or 45-50
                  |
                  |your ticket:
                  |7,1,14
                  |
                  |nearby tickets:
                  |7,3,47
                  |40,4,50
                  |55,2,20
                  |38,6,12""".stripMargin

    val sum = for {
      (rules, myTicket, nearByTickets) <- parseInput(sixteen)
      invalids = nearByTickets.flatMap(invalidFields(rules))
    } yield invalids.sum

    println(sum)
  }
  
  object part2:
    type Label = String
    type Position = Int
    type LabelledRule = Label -> (Int => Boolean)
    
    def parseRule2: String => String \/ LabelledRule = { s =>
      val ruleRe = """([\w ]+): (\d+)-(\d+) or (\d+)-(\d+)""".r.unanchored
      s match
        case ruleRe(label, min1, max1, min2, max2) => Right(label -> {(i: Int) => (i >= min1.toInt && i <= max1.toInt) || (i >= min2.toInt && i <= max2.toInt) })
        case _ => Left(s"$s can't be parsed")
    }

    def validTicket: List[Rule] => Ticket => Boolean = rules => ticket =>
      ticket.forall(i => rules.exists(r => r(i)))

    def satisfiedRules: List[LabelledRule] => Int => Set[Label] = rules => i =>
      rules.collect{ case (l, r) if r(i) => l }.toSet

    def parseInput2: String => String \/ (List[LabelledRule], Ticket, List[Ticket]) = s => s.split("(?m)^\n") match {
      case Array(ruleS, myTicketS, nearbyTicketsS) => for {
        rules <- ruleS.linesIterator.toList.traverse(parseRule2)
        ticket <- myTicketS.linesIterator.toList.last.split(",").toList.traverse(n => n.toIntOption.toRight(s"$n is not a number"))
        nearbyTickets <- nearbyTicketsS.linesIterator.drop(1).toList.traverse(
          _.split(",").toList.traverse(n => n.toIntOption.toRight(s"$n is not a number"))
        )
      } yield (rules, ticket, nearbyTickets)
      case _ => Left(s"$s cannot be split into things")
    }
    
    def labelPosition: List[Ticket] => List[LabelledRule] => String \/ Map[Int, Label] = tickets => rules => {
      val ruleSet = rules.map(_._1).toSet
      val labelSets = tickets.foldLeft[List[Set[Label]]](List.fill(tickets.head.length)(ruleSet)) {
        case (satisfiers, ticket) => ticket.map(satisfiedRules(rules)).zip(satisfiers).map {
          case (current, acc) => current intersect acc
        }
      }
      
      object SingletonSet {
        def unapply[A](set: Set[A]): Option[A] = if (set.size == 1) Some(set.head) else None
      }

      def collapseSets(labelSets: List[Set[Label] -> Int], acc: Map[Int, Label]): String \/ Map[Int, Label] = labelSets match {
        case _ if acc.values.toSet == ruleSet => Right(acc)
        case (SingletonSet(label), pos) :: rest => 
          collapseSets(rest.map{ case (labels, i) => (labels - label) -> i }, acc + (pos -> label))
        case (s, pos) :: rest => Left(s"$s is too big. Remaining: $rest")
        case Nil => Left("empty list")
      }
      
      println(labelSets.zipWithIndex.sortBy(_._1.size))
      collapseSets(labelSets.zipWithIndex.sortBy(_._1.size), Map.empty)
    }

    @main def m16_2 = {
      val dummy = """class: 0-1 or 4-19
                    |row: 0-5 or 8-19
                    |seat: 0-13 or 16-19
                    |
                    |your ticket:
                    |11,12,13
                    |
                    |nearby tickets:
                    |3,9,18
                    |15,1,5
                    |5,14,9""".stripMargin

      val res = for {
        (rules, myTicket, nearByTickets) <- parseInput2(sixteen)
        validTickets = nearByTickets.filter(validTicket(rules.map(_._2)))
        labelPositions <- labelPosition(validTickets)(rules).map(_.toList.sortBy(_._1).map(_._2))
        labeledTicket = myTicket zip labelPositions
        departurePositions = labeledTicket.filter { 
          case (_, label) => label.startsWith("departure")
        }
      } yield labeledTicket -> departurePositions.map(_._1.toLong).product
      
      println(res)
  }