Google Hash Code 2020 solution (total score 26 909 323)

HashCode2020.scala

import java.io._
import java.nio.file.{Files, StandardCopyOption}

import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer

object HashCode2020 extends App {

  case class Book(id: Int, score: Int)
  case class Lib(id: Int, signupDays: Int, scanPerDay: Int, books: mutable.TreeSet[Book])

  def listInFiles(prefix: String): Array[File] = new File("input").listFiles(new FilenameFilter {
    override def accept(dir: File, name: String): Boolean = {
      (prefix == "*" || name.startsWith(prefix)) && name.endsWith(".txt")
    }
  }).sortBy(_.getName)

  def saveSolution(fileName: String, libs: ArrayBuffer[Lib], orders: Array[ArrayBuffer[Int]]): Unit = {
    val tmp = new File(s"tmp$fileName.txt")
    tmp.delete()
    tmp.createNewFile()
    val out = new PrintWriter(new BufferedOutputStream(new FileOutputStream(tmp)))

    val cnt = orders.count(_.nonEmpty)

    out.println(cnt)
    for (lib <- libs) {
      val libId = lib.id
      if (orders(libId).nonEmpty) {
        out.println(s"$libId ${orders(libId).size}")
        out.println(orders(libId).mkString(" "))
      }
    }

    out.close()
    val tmpPath = tmp.toPath
    Files.move(tmpPath, tmpPath.resolveSibling(s"output/$fileName.out"), StandardCopyOption.REPLACE_EXISTING)
  }

  def solve(fileOption: Option[File]): Long = {

    val (fileName, in) = fileOption match {
      case Some(file) =>
        val name = file.getName
        println(name)
        name.take(name.lastIndexOf('.')) -> new java.io.FileInputStream("input/" + name)
      case None =>
        println("Enter input data:")
        "_console" -> System.in
    }

    val reader = new java.io.BufferedReader(new java.io.InputStreamReader(in))
    import reader._

    @inline def tokenizeLine = new java.util.StringTokenizer(readLine)
    def readInts(n: Int) = { val tl = tokenizeLine; Array.fill(n)(tl.nextToken.toInt) }

    val Array(bookCount, libCount, days) = readInts(3)
    val scores = readInts(bookCount)

    val libs = Array.tabulate(libCount) { id =>
      val Array(n, t, m) = readInts(3)
      val bookIds = readInts(n)
      val s = new mutable.TreeSet[Book]()(Ordering.by(b => (-b.score, b.id)))
      s ++= bookIds.map(id => Book(id, scores(id)))
      Lib(id, t, m, s)
    }

    var booksByScore = (0 until bookCount).map(id => Book(id, scores(id))).sortBy(-_.score).toArray
    val activeLibs = ArrayBuffer.empty[Lib]
    val orders = Array.fill(libCount) { ArrayBuffer.empty[Int] }

    var day = 0

    def potential(lib: Lib): Double = {
      var sum = 0L
      var canScan = (days.toLong - day - lib.signupDays) * lib.scanPerDay
      val it = lib.books.iterator
      while (it.hasNext && canScan > 0) {
        val book = it.next()
        //if (lib.books.contains(book)) {
          sum += book.score
          canScan -= 1
        //}
      }
      sum.toDouble / Math.pow(lib.signupDays, 0.9)
    }

    var remainingLibs = libs

    var nextSubscribeLib = remainingLibs.maxBy(potential)
    var nextSubscribeDay = nextSubscribeLib.signupDays

    var solutionScore = 0L
    val canScanToday = Array.ofDim[Int](libCount)
    val libsByBookId = Array.fill(bookCount)(ArrayBuffer.empty[Lib])

    while (day < days) {
      if (day == nextSubscribeDay) {
        activeLibs += nextSubscribeLib
        for (book <- nextSubscribeLib.books) libsByBookId(book.id) += nextSubscribeLib

        remainingLibs = remainingLibs.filterNot(_.id == nextSubscribeLib.id)

        if (remainingLibs.nonEmpty) {
          nextSubscribeLib = remainingLibs.maxBy(potential)
          nextSubscribeDay = day + nextSubscribeLib.signupDays
        }
      }

      for (lib <- activeLibs) {
        canScanToday(lib.id) = lib.scanPerDay
      }

      val scannedToday = mutable.Set.empty[Int]
      for (book <- booksByScore) {
        var libPos = 0
        val candidateLibs = libsByBookId(book.id)
        var bestLibId = -1
        var bestLibBookCount = Int.MaxValue
        while (libPos < candidateLibs.size) {

          if (canScanToday(candidateLibs(libPos).id) > 0) {
            if (candidateLibs(libPos).books.size < bestLibBookCount) {
              bestLibBookCount = candidateLibs(libPos).books.size
              bestLibId = libPos
            }
          }

          libPos += 1
        }

        if (bestLibId >= 0) {
          val takeFromLib = candidateLibs(bestLibId)
          for (lib <- libs) lib.books -= book
          orders(takeFromLib.id) += book.id
          canScanToday(takeFromLib.id) -= 1
          scannedToday += book.id
          solutionScore += book.score
          //???scores(book) = 0
        }
      }

      booksByScore = booksByScore.filterNot(b => scannedToday(b.id))
      //println(day, solutionScore, activeLibs.size, booksByScore.length)
      day += 1
    }

    saveSolution(fileName, activeLibs, orders)

    println("Score: " + solutionScore)

    solutionScore
  }

  if (args.length <= 0) solve(None) // console
  else {
    val scores = args.flatMap(listInFiles).map(f => solve(Some(f)))
    println(s"Total score: ${scores.sum} (${scores.mkString(" ")})")
  }
}