HashcodeTest.scala

import scala.io.Source
import scala.concurrent.{Await, ExecutionContext, Future}
import scala.concurrent.duration._
import scala.collection.immutable.BitSet
import scala.util.Random
                                                    
object Main {

  sealed trait Ingredient
  case object Mushroom extends Ingredient
  case object Tomato extends Ingredient
  
  type Pizza = Array[Array[Ingredient]]
  type Row = Int
  type Col = Int

  final case class Input(rows: Int, cols: Int, minIngredient: Int, maxCells: Int, pizza: Pizza) 

  def isValidSlice(pizza: Pizza, rows: Int, cols: Int, startRow: Row, startCol: Col, l: Int, h: Int, taken: Map[Int, BitSet]): Boolean = {
    if (startRow + rows > pizza.length || startCol + cols > pizza(0).length)
      false
    else {
      val (tomatoes, mushrooms) = (startRow until startRow + rows).foldLeft((0, 0)) { case ((tomatoes, mushrooms), row) =>
        (startCol until startCol + cols).foldLeft((tomatoes, mushrooms)) { case ((tsCol, msCol), col) =>
          if (taken.get(row).map(_.apply(col)).getOrElse(false))
            (tsCol, msCol)
          else pizza(row)(col) match {
            case Tomato   => (tsCol + 1, msCol)
            case Mushroom => (tsCol, msCol + 1)
          }
        }
      }

      mushrooms >= l && tomatoes >= l && mushrooms + tomatoes <= h
    }
  }

  def updateTaken(row: Row, col: Col, taken: Map[Int, BitSet]): Map[Int, BitSet] = {
    taken.get(row) match {
      case Some(oldRow) => taken + (row -> (oldRow + col))
      case None         => taken + (row -> BitSet(col))
    }
  }
  
  def generateSlices(pizza: Pizza, row: Row, col: Col, l: Int, h: Int, taken: Map[Int, BitSet]): (List[(Int, Int)], Map[Int, BitSet]) = {
    (1 to h).foldLeft((List.empty[(Int, Int)], taken)) { case ((s0, t0), i) =>
      (1 to h).foldLeft((s0, t0)) { case ((s1, t1), j) =>
        if (i * j <= h && isValidSlice(pizza, i, j, row, col, l, h, t1))
          ((i, j) :: s1, updateTaken(i, j, t1))
        else
          (s1, t1)
      }
    }
  }
  
  def findSlices(pizza: Pizza, row: Row, col: Col, taken: Map[Int, BitSet], slices: (List[(Int, Int, Int, Int)], Int), l: Int, h: Int, level: Int, rand: Random)(implicit ec: ExecutionContext): Future[(List[(Int, Int, Int, Int)], Int)] = { 
    val (validSlices, updatedTaken) = generateSlices(pizza, row, col, l, h, taken)

    def nextSlices(rows: Int, cols: Int): Future[(List[(Int, Int, Int, Int)], Int)] = {
      val slicesUpdated = ((row, col, rows, cols) :: slices._1) -> ((rows * cols) + slices._2)

      for {
        x <- findSlices(pizza, row + rows, col, updatedTaken, slicesUpdated, l, h, level + 1, rand)
        y <- findSlices(pizza, row, col + cols, updatedTaken, slicesUpdated, l, h, level + 1, rand)
      } yield {
        if (x._2 > y._2) x
        else             y
      }
    }

    if (validSlices.isEmpty)
      Future.successful(slices)
    else {
      validSlices.foldLeft(Future.successful((List.empty[(Int, Int, Int, Int)], 0))) { case (aggF, (rows, cols)) =>
        if (level % 100 == 0 && rand.nextDouble() > 0.95) {
          println("parallelisation: " + level)
          val nextF = nextSlices(rows, cols)

          for {
            agg  <- aggF
            next <- nextF
          } yield {
            if (agg._2 < next._2) next
            else                  agg
          }
        }
        else {
          for {
            agg  <- aggF
            next <- nextSlices(rows, cols)
          } yield {
            if (agg._2 < next._2) next
            else                  agg
          }
        }
      }
    }
  }

  def readFile(filename: String): Iterator[String] =
    Source.fromFile(filename).getLines

  def parseInput(lines: List[String]): Input = {
    val Array(rows, cols, minIngredient, maxCells) = lines.head.split(" ").map(_.toInt)

    Input(
      rows,
      cols,
      minIngredient,
      maxCells,
      lines.tail.map { line =>
        val row: Array[Ingredient] = line.map {
          case 'T' => Tomato
          case 'M' => Mushroom
        }(collection.breakOut)

        row
      }(collection.breakOut)
    )
  }

  def main(args: Array[String]): Unit = {
    val filename = args(0)
    val input    = parseInput(readFile(filename).toList)
    val rand     = new Random

    import scala.concurrent.ExecutionContext.Implicits.global

    val t = System.currentTimeMillis()
    println(Await.result(findSlices(input.pizza, 0, 0, Map.empty, (Nil, 0), input.minIngredient, input.maxCells, 0, rand), 10.minutes))
    println("time: " + (System.currentTimeMillis() - t))
  }
}