TileSolver

TileSolver.scala

package tilesolver

sealed trait Direction {
  def opposite: Direction
}
case object North extends Direction {
  val opposite = South
}
case object South extends Direction {
  val opposite = North
}
case object West extends Direction {
  val opposite = East
}
case object East extends Direction {
  val opposite = West
}
case object Center extends Direction {
  def opposite = throw new AssertionError()
}

case class Tile(in: Direction, out: Direction) {
  assert(in != out)
}

case object Tiles {

  val southEast = Tile(South, East)
  val westEast = Tile(West, East)
  val northCenter = Tile(North, Center)
  val centerEast = Tile(Center, East)
  val southWest = Tile(South, West)
  val northEast = Tile(North, East)
  val northSouth = Tile(North, South)
  val westCenter = Tile(West, Center)
  val westSouth = Tile(West, South)
}

case object TileSolver {
  case class Step(tilesLeft: Set[Tile], path: List[Tile])

  def findEnd(step: Step): Set[List[Tile]] = {
    val ends = step.tilesLeft.filter {
      case Tile(_, Center) => true
      case _ => false
    }

    ends.flatMap { end =>
      prependElement(Step(step.tilesLeft - end, List(end)))
    }
  }

  def prependElement(step: Step): Set[List[Tile]] = {
    val possibleTiles = step.tilesLeft.filter(tile => tile.out != Center && tile.out == step.path.head.in.opposite)
    possibleTiles.flatMap { tile =>
      if (tile.in == Center) {
        List(tile :: step.path)
      } else {
        prependElement(Step(step.tilesLeft - tile, tile :: step.path))
      }
    }
  }


  def solve(tiles: Set[Tile]): Set[List[Tile]] = {

    val allTiles = findEnd(Step(tiles, Nil))

    allTiles.foldLeft(Set.empty[List[Tile]]) { (elements, step) =>
      val currentLength = elements.headOption.map(_.length).getOrElse(0)
      val maxLength = Math.max(currentLength, step.length)

      (elements + step).filter(_.length == maxLength)
    }
  }
}