## Saturday, 16 August 2014

### Snail Algo in Scala

A friend of mine just had an interview for a job at Amazon... and he had a funny algorithm to work on. Something that I would describe as a 'snail algorithm' for a matrix. A bit like this: So, I was wondering how to implement this .. and I wrote this in Scala.. seems to work - although not entirely tested ;-) Some type def
```  val numRows = 4
val numCols = 3
val matrixSize = numRows * numCols

type Coord = (Int, Int)
type Operand = (Int, Int)
type Path = List[Coord]

val incs = List((0, 1), (1, 0), (0, -1), (-1, 0))
```
incs defines directions: go right, go down, go left, go up, etc. In order to continuously iterate through those values, I used Stream.continually():
```  val incsIt = (for(x <- Stream.continually(); y <- incs) yield y).iterator
def nxtOp = incsIt.next
```
Then a small recursive function to snail-walk the matrix:
```  def walk(coord: Coord = (0, 0), op: Operand = nxtOp, path: Path = List()): Path = {
if (path.size == matrixSize) path else {
val nrc = (coord._1+op._1, coord._2+op._2)
if (nrc._1 < 0 || nrc._1 >= numRows || nrc._2 < 0 || nrc._2 >= numCols || (path contains nrc))
walk(coord, nxtOp, path)
else
walk(nrc, op, if (path.size == matrixSize-2) path :+ coord :+ nrc else path :+ coord)
}
}
```
The result for (4, 3) shows:
```  val p1 = walk()

//> p1  : org.jts.z.Snail.Path =
// List((0,0), (0,1), (0,2), (1,2), (2,2), (3,2), (3,1), (3,0), (2,0), (1,0), (1,1), (2,1))
```
I really have the feeling it can be done in a better way. Have not found how yet.