Day24.scala

object Day24 extends App {
  val test = List(1,2,3,4,5,7,8,9,10,11).mkString("\n")

  val input =
    """
      |1
      |3
      |5
      |11
      |13
      |17
      |19
      |23
      |29
      |31
      |37
      |41
      |43
      |47
      |53
      |59
      |67
      |71
      |73
      |79
      |83
      |89
      |97
      |101
      |103
      |107
      |109
      |113
    """.stripMargin.trim

  solve(input, 3)

  def solve(input: String = test, partitions: Long = 3): Unit = {
    val list = input.split("\n").map(_.toLong).toList
    val target = list.sum / partitions
    val stream = pieces(list, Nil, Nil, target).sortBy { case (piece, _) => piece.length }
    val validStream = stream.filter { case (piece, rest) => validPieces(rest, partitions - 1, target)}
    val minLength = validStream.head._1.length

    println(
      validStream.takeWhile { case (piece, rest) =>
        piece.length == minLength
      }
      .map(_._1.product)
      .min
    )
  }

  def validPieces(list: List[Long], count: Long, target: Long): Boolean = {
    if (count == 1) {
      pieces(list, Nil, Nil, target).nonEmpty
    } else {
      pieces(list, Nil, Nil, target).exists { case (_, rest) =>
        validPieces(rest, count - 1, target)
      }
    }
  }

  def pieces(list: List[Long], acc: List[Long], rest: List[Long], target: Long): Stream[(List[Long],List[Long])] = {
    val sum = acc.sum
    if (sum == target) {
      Stream((acc, rest))
    } else if (sum > target || list.isEmpty) {
      Stream.empty
    } else {
      pieces(list.tail, acc, list.head :: rest, target) #::: pieces(list.tail, list.head :: acc, rest, target)
    }
  }
}