Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Amsterdam.Scala - Scala Hackaton 26 Nov 2013 - Tiles Challenge
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 = => {
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))
} else {
val forResult =
for {
possibleTile <- availableTiles
tilesComb <- placeTile(subTiles.tail, subTiles.head :: availableTiles)
placedTile = tilesComb.head
if (isTileAllowed(placedTile, possibleTile))
} yield possibleTile :: tilesComb
placeTile(tiles.tail, List(tiles.head))

This comment has been minimized.

Show comment
Hide comment

martijnhoekstra Nov 27, 2013

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

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment