algorithmicProblemSolving_1_1.scala

case class Size(width: Int, height: Int)
case class State(rects: Map[Size, Int])

def allChildren(size: Size): Set[Size] =
  (for (x <- 1 to size.width; y <- 1 to size.height) yield Size(x, y)).toSet

def solve(allCases: Set[Size], remains: Set[Size], current: Size, acc: State): State =
  def appended(acc: State, rect: Size, newRects: Size): State = {
    if allCases.contains(newRects) && acc.rects.keys.toSet.contains(rect) then
      val nextCount = acc.rects(rect) + acc.rects(current) + 1
      acc.copy(rects = acc.rects.updated(newRects, acc.rects.getOrElse(newRects, Int.MaxValue) min nextCount))
    else
      acc
  }

  if remains.isEmpty then
    acc
  else
    val nextAcc = acc.rects.keys.foldLeft(acc) { case (acc, rect) =>
      val widthAppendedAcc = if rect.width == current.width then
        val newRects = Size(rect.width, rect.height + current.height)
        appended(acc, rect, newRects)
      else
        acc
      if rect.height == current.height then
        val newRects = Size(rect.width + current.width, rect.height)
        appended(widthAppendedAcc, rect, newRects)
      else
        widthAppendedAcc
    }
    remains.find(nextAcc.rects.contains) match
      case Some(next) =>
        solve(allCases, remains - current, next, nextAcc)


@main def solve1_1(): Unit =
  val fullSize = Size(4, 3)
  val children = allChildren(fullSize)
  val result = solve(children, children, Size(1, 1), State(Map(Size(1, 1) -> 0)))
  println(result.rects(fullSize))
  // (Size(1,1),0), (Size(2,1),1), (Size(1,2),1), (Size(1,3),2), (Size(3,1),2), (Size(2,2),3), (Size(4,1),3), (Size(3,2),5), (Size(2,3),5), (Size(4,2),7), (Size(3,3),8), (Size(4,3),11)