Enumerating polyominos

polyominos.scala

case class Point(x: Int, y: Int) {
  lazy val neighbours = Set(Point(x-1,y), Point(x+1,y), Point(x,y-1), Point(x,y+1))
}

case class Polyomino(squares: Set[Point]) {
  def op(f: Point => Point) = copy(squares = squares.map(f))
  
  val order = squares.size

  lazy val mx = if (squares.isEmpty) 0 else squares.map(_.x).max
  lazy val my = if (squares.isEmpty) 0 else squares.map(_.y).max

  lazy val horizontal = op { s => Point(mx-s.x, s.y) }
  lazy val vertical   = op { s => Point(s.x, my-s.y) }
  lazy val diagonal   = op { s => Point(s.y, s.x) }
  
  lazy val family = Set(
    this, 
    horizontal, 
    vertical, 
    horizontal.vertical,
    diagonal,
    diagonal.horizontal,
    diagonal.vertical,
    diagonal.horizontal.vertical
  )
  
  lazy val right = op { s => Point(s.x+1, s.y) }
  lazy val down  = op { s => Point(s.x, s.y+1) }
  
  lazy val extensions = squares.flatMap(_.neighbours).filterNot(squares.contains)
  
  def add(s: Point) =
    if (s.neighbours.exists(squares.contains)) 
      if (s.x<0) copy(squares = squares+s).right
      else if (s.y<0) copy(squares = squares+s).down
      else copy(squares = squares+s)
    else throw new UnsupportedOperationException("square not connected")
  
  override def toString = {
    val s = for (y <- 0 to my; x <- 0 to mx) yield (if (squares.contains(Point(x,y))) 'O' else '.')
    s.grouped(mx+1).map(_.mkString).mkString("\n")
  }
}

val mono = Polyomino(Set(Point(0,0)))

def find(p: Polyomino, ps: Set[Polyomino], maxo: Int): Set[Polyomino] =
  if (p.order>=maxo) ps
  else p.extensions.map(p.add).foldLeft(ps) { 
    case (nps,np) if np.family.exists(nps.contains) => nps
    case (nps,np) => find(np, nps+np, maxo)
  }

val frees = find(mono, Set(mono), 10)

val counts = frees.groupBy(_.order).map(p => (p._1, p._2.size))

//println(frees.toList.sortBy(_.order).mkString("\n---\n"))
//println("\n---\n")
println(counts.toList.sortBy(_._1).mkString("\n"))