Solves 538's riddler class for Jun 19, 2020

538_splitting_spheres.scala

// All of the ways that a subset of xs can sum to target
def sumTo(xs: List[Long], target: Long, acc: Set[Long]): LazyList[Set[Long]] = {
  if (target == 0) {
    LazyList(acc)
  } else if (target < 0) {
    LazyList.empty
  } else xs match {
    case head :: rest => {
      sumTo(rest, target - head, acc + head) ++ sumTo(rest, target, acc)
    }
    case Nil => LazyList.empty
  }
}

// All of the ways that a subset of xs can sum to target, with the optimization of always including the "first" element
def sumToIncludingFirst(xs: Set[Long], target: Long): LazyList[Set[Long]] = {
  val head :: rest = xs.toList
  sumTo(rest, target - head, Set(head))
}

// All of the ways to evenly split the set among n groups
def splitN(xs: Set[Long], n: Int): LazyList[List[Set[Long]]] = {
  if (n == 1) {
    LazyList(List(xs))
  } else {
    val sum = xs.sum
    if (sum % n != 0) {
      LazyList.empty
    } else {
      val target = sum / n
      for {
        group1 <- sumToIncludingFirst(xs, target)
        remaining = xs.diff(group1)
        otherGroups <- splitN(remaining, n - 1)
      } yield group1 :: otherGroups
    }
  }
}

// The number of spheres (and corresponding split) required with n children
def firstWorkingSplit(n: Int): (Int, List[Set[Long]]) = {
  LazyList.from(1).flatMap(max => {
    val cubes = (1L to max).map(x => x * x * x).toSet
    splitN(cubes, n).map(ans => (max, ans))
  }).head
}

for (n <- 2 to 6) {
  val (a, split) = firstWorkingSplit(n)
  println(s"with $n children, requires $a spheres, split like $split")
}