Amsterdam.Scala - Scala Hackaton 26 Nov 2013 - Tiles Challenge

gistfile1.txt

This is the little challenge I proposed and worked on with Giorgio, Joost and two other people (names? :) )

You need to create a solver for the following problem.

Say you have squared Tiles. Each tile can be traversed with a Movement. If you come in from Left, you can go to the Top, Right, Bottom, or stay in the middle (Inner). Same if you come from the Top: possible directions are Left, Right, Bottom and Inner.

One Movement can also start from the middle, and go Left, Right, Top or Bottom.

Movements are here defined as Strings for simplicity.

  val LeftRight = "LeftRight"                 
  val InnerRight = "InnerRight"               
  val LeftInner = "LeftInner"                 
  val InnerLeft = "InnerLeft"                 
  val InnerBottom = "InnerBottom"             
  val InnerTop = "InnerTop"                   
  val BottomInner = "BottomInner"             
  val RightInner = "RightInner"               
  val TopInner = "TopInner"                   
  val LeftBottom = "LeftBottom"               
  val LeftTop = "LeftTop"                     
  val RightBottom = "RightBottom"             
  val RightTop = "RightTop"                   
  val BottomLeft = "BottomLeft"               
  val TopLeft = "TopLeft"                     
  val BottomRight = "BottomRight"             
  val TopRight = "TopRight"                   
  val RightLeft = "RightLeft"                 
  val TopBottom = "TopBottom"                 
  val BottomTop = "BottomTop"                 

The challenge is: given a group of tiles, in the form of a list (example: List(InnerLeft, RightBottom, TopBottom, RightInner, TopLeft)), find the longest sequence of tiles where you start and and in the middle. 

To solve this, we used the auxiliary function that gives you back a list of possible following tiles given one.

  def getLegalNextOnes(movement: String): List[String] = {
    movement match {
      case InnerRight | LeftRight | BottomRight | TopRight => List(LeftRight, LeftInner, LeftBottom, LeftTop)
      case InnerLeft | RightLeft | BottomLeft | TopLeft => List(RightLeft, RightInner, RightTop, RightBottom)
      case LeftBottom | RightBottom | TopBottom | InnerBottom => List(TopLeft, TopInner, TopRight, TopBottom)
      case LeftTop | RightTop | InnerTop | BottomTop => List(BottomLeft, BottomRight, BottomTop, BottomInner)
      case LeftInner | RightInner | TopInner | BottomInner => List()
    }
  }
  
How would you solve this?


------- Below, the work we'd further done on this, without reaching a solution yet.

  val expList = List(InnerRight, LeftTop, BottomInner)

  def isTileAllowed(previousTile: String, tile: String) =  getlegalNextOnes(previousTile).contains(tile)
  
  def getZeroList(tiles: List[String]): List[List[String]] = tiles.filter(tile => tile.startsWith("Inner")).map(x => List(x))

  def sortTiles(tiles: List[String]): List[List[String]] = {

    def placeTile(paths: List[List[String]], availableTiles: List[String]): List[List[String]] = {
      if (availableTiles == Nil) paths
			else if (paths == Nil) {
				val zeroList = getZeroList(availableTiles)
				placeTile(zeroList, availableTiles diff (zeroList.flatten))
			} else {
				val newPaths = paths.map(l => {
					if (isTileAllowed(l.head, availableTiles.head)) availableTiles.head :: l
					else l
				}  )
				placeTile(newPaths, availableTiles.tail)
			}
    }

    placeTile(Nil, tiles)
  }   
  
  
    def sortTiles2(tiles: List[String]): List[List[String]] = {

    def placeTile(subTiles: List[String], availableTiles: List[String]): List[List[String]] = {
      println("subtiles:" + subTiles + ", availableTiles: " + availableTiles)
      if (subTiles == Nil) {
        println("zero list: " + getZeroList(tiles))
        getZeroList(tiles)

      } else {
        val forResult =
          for {
            possibleTile <- availableTiles
            tilesComb <- placeTile(subTiles.tail, subTiles.head :: availableTiles)
            placedTile = tilesComb.head
            if (isTileAllowed(placedTile, possibleTile))
          } yield possibleTile :: tilesComb

        forResult
      }
    }

    placeTile(tiles.tail, List(tiles.head))
  }   
  
  

Can multiple tiles stack on one location? (I assume no)
Is the "board" unbounded? (I assume yes)