Skip to content

Instantly share code, notes, and snippets.

@reitzig
Created November 20, 2020 17:49
Show Gist options
  • Save reitzig/07d70b0c1e1fafea507c764cea57022d to your computer and use it in GitHub Desktop.
Save reitzig/07d70b0c1e1fafea507c764cea57022d to your computer and use it in GitHub Desktop.
Determine how to fill a wall with shelves of certain widths
fun maximalSplits(pieces: List<Int>, width: Int): List<Pair<Map<Int, Int>, Int>> {
fun maximalSplits(partial: List<Int>): List<List<Int>> {
val longerSplits = pieces
.filter { partial.sum() + it < width }
.map { (partial + it).sorted() }
.flatMap { maximalSplits(it) }
.distinct()
if (longerSplits.isEmpty()) {
return listOf(partial)
} else {
return longerSplits
}
}
return maximalSplits(emptyList())
.map { Pair(it.groupBy { it }.mapValues { it.value.count() }, it.sum()) }
}
val pieces = args[0].split(",").map(String::toInt)
val width = args[1].toInt()
val splits = maximalSplits(pieces, width)
println(splits)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment