Instantly share code, notes, and snippets.

# agleyzer/TetrisShapes.scala Created Mar 8, 2013

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") } }