Calculates all possible Tetris-like shapes for a given number of squares.

TetrisShapes.scala

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