A friend and I are trying to figure out the optimal way to generate the full set of all possible Android shape passwords. This is my attempt -- permutations, recursions; fairly functional.

AndroidPasswordGenerator.scala

import scala.math.abs

object AndroidPasswordGenerator{

  def main(args: Array[String]) {
    val grid = NodeGrid.generateGrid
    val paths = findPath(grid, new EmptyPath)
    paths.foreach{println}
  }

  def findPath(nodes: List[AndroidNode], path: AndroidPath): List[AndroidPath] = {
    nodes.flatMap{ node =>
      val newPath = path.addToPath(node)
      val remainingNodes = nodes.filter{
        node => !newPath.contains(node)
      }
      if (newPath.length >= 9) List(newPath)
      else if (newPath.length >= 4) findPath(remainingNodes, newPath) ++ List(newPath)
      else findPath(remainingNodes, newPath)
    }
  }
}

case class AndroidNode(x: Int, y: Int) {

  lazy val neighbors = getAdjacentNodes

  override def toString(): String = "<" + this.x + "," + this.y + ">"

  def - (other: AndroidNode): AndroidNode = {
    new AndroidNode(diff(this.x, other.x), diff(this.y, other.y))
  }

  def diff(a: Int, b: Int): Int = {
    if (a == b) a else abs(a - b)
  }

  def getAdjacentNodes(): List[AndroidNode]= {
    def inRange(param: Int): Boolean = { (param > 0 && param < 4) }
    (-1 to 1)
      .toList
      .flatMap{
      xMod => (-1 to 1)
        .toList
        .map{
        yMod => AndroidNode(this.x + xMod, this.y + yMod)
      }
    }
      .filter{ node => (inRange(node.x) && inRange(node.y)) && node != this }
  }

}

// Grid Generator
object NodeGrid {
  def generateGrid(): List[AndroidNode] = {
    (1 to 3).toList.flatMap{ x => (1 to 3).toList.map{y => AndroidNode(x, y)}}
  }

}

// Base Path Class
abstract class AndroidPath {

  val path: List[AndroidNode]
  def isEmpty(): Boolean
  def length(): Int
  def contains(node: AndroidNode): Boolean
  def addToPath(
    candidateNode: AndroidNode): AndroidPath
  def toString(): String

}

class EmptyPath extends AndroidPath {

  val path: List[AndroidNode] = List()
  def isEmpty() = true
  def length(): Int = 0
  def contains(node: AndroidNode): Boolean = false
  def addToPath(
    candidateNode: AndroidNode): AndroidPath =
    new Path(List(candidateNode))
  override def toString(): String = "<Empty Path>"

}

class Path(val path: List[AndroidNode]) extends AndroidPath {

  def length(): Int = this.path.length

  def isEmpty(): Boolean = false

  def contains(node: AndroidNode): Boolean = this.path.contains(node)

  def addToPath(
    candidateNode: AndroidNode): Path = {

    if (this.path.head.neighbors.contains(candidateNode))
      new Path(candidateNode +: this.path)
    else {
      val interstitial = getInterstitialNode(candidateNode)
      if (this.path.contains(interstitial))
        new Path(candidateNode +: this.path)
      else
        new Path(candidateNode +: interstitial +: this.path)
    }
  }

  def getInterstitialNode(candidateNode: AndroidNode): AndroidNode = {
    this.path.head - candidateNode
  }

  override def toString(): String = {
    this.path.reverse.mkString("->")
  }

}