Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Calculates all possible Tetris-like shapes for a given number of squares.
// Calculates all possible Tetris-like shapes for a given number of
// squares.
object TetrisShapes extends App {
type Point = (Int, Int) // x, y
type Shape = Set[Point]
// returns a list of neighbors for a point
def neighbors(p: Point) = {
val (x, y) = p
List(
(x, y - 1), // up
(x, y + 1), // down
(x - 1, y), // left
(x + 1, y) // right
)
}
// returns a string version of the shape
def mkString(shape: Shape): String = {
val (xs, ys) = shape.unzip
val rows = for (y <- ys.min to ys.max) yield {
val row = for (x <- xs.min to xs.max) yield if (shape(x, y)) '#' else ' '
row.mkString
}
rows.mkString("\n")
}
// returns a list of all permutations
def allShapes(n: Int): List[Shape] = {
require(n > 0, "number of pieces must be positive")
def step(remaining: Int, curr: Point, shape: Shape): List[Shape] = {
if (remaining == 0) {
List(shape)
} else {
val vacant = neighbors(curr).filterNot(shape)
vacant.flatMap(p => step(remaining - 1, p, shape + p))
}
}
step(n - 1, (0, 0), Set((0, 0)))
}
// prints all shapes
for (s <- allShapes(args.head.toInt)) {
println(mkString(s) + "\n")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.