Skip to content

Instantly share code, notes, and snippets.

@lbialy
Last active August 2, 2016 06:33
Show Gist options
  • Save lbialy/2a485cf6ae85c22ea4e70ebb360f2cb1 to your computer and use it in GitHub Desktop.
Save lbialy/2a485cf6ae85c22ea4e70ebb360f2cb1 to your computer and use it in GitHub Desktop.
Conway's Game of Life in functional Scala with lazy eval
type Position = (Int, Int)
type State = Set[Position]
def gameOfLife(state: State): Stream[State] =
if (state.isEmpty) Stream.empty
else state #:: gameOfLife(nextFrom(state))
def nextFrom(state: State) = {
for {
field <- getFieldsFromState(state)
result <- applyRules(field, state)
} yield result
}
def applyRules(pos: Position, state: State) = {
getNeighbourCount(pos, state) match {
case x if !state.contains(pos) && x == 3 => Some(pos) // dead field with 3 living neighbours
case x if state.contains(pos) && x == 2 || x == 3 => Some(pos) // live to see next iteration
case _ => None // too many or no neighbours or dead already
}
}
def getNeighbourCount(pos: Position, state: State) = (expand(pos) - pos).intersect(state).size
def getFieldsFromState(state: State) = state flatMap expand
//def expand(pos: Position) = (for {
// x <- pos._1 - 1 until pos._1 + 2
// y <- pos._2 - 1 until pos._2 + 2
//} yield (x, y)).toSet
def expand(p: Position) = Set(
(p._1 - 1, p._2 - 1), (p._1, p._2 - 1), (p._1 + 1, p._2 - 1),
(p._1 - 1, p._2), p, (p._1 + 1, p._2),
(p._1 - 1, p._2 + 1), (p._1, p._2 + 1), (p._1 + 1, p._2 + 1)
)
val glider = Set(
(-1, -1), (0, -1), (1, -1),
(-1, 0),
(0, 1)
)
val blinker = Set(
(0, -1),
(0, 0),
(0, 1)
)
val gol = gameOfLife(glider)
def draw(state: State) = {
val minx = state.foldLeft(Int.MaxValue)((acc, pos) => if (pos._1 < acc) pos._1 else acc)
val miny = state.foldLeft(Int.MaxValue)((acc, pos) => if (pos._2 < acc) pos._2 else acc)
val maxx = state.foldLeft(Int.MinValue)((acc, pos) => if (pos._1 > acc) pos._1 else acc)
val maxy = state.foldLeft(Int.MinValue)((acc, pos) => if (pos._2 > acc) pos._2 else acc)
(for {
y <- miny - 2 until maxy + 3
x <- minx - 2 until maxx + 3
} yield (x, y)).foreach(pos => {
if (state.contains(pos)) print("#")
else print(".")
if (pos._1 == maxx + 2) print("\n")
})
}
println("Starting position: glider")
val start = System.currentTimeMillis()
//gol.take(10000).foreach(draw)
val last = gol.take(10000).takeRight(1)
val time = System.currentTimeMillis() - start
draw(last.head)
println(s"Elapsed time: $time ms, per iteration: ${time.toFloat/10000} ms")
@MLaszczewski
Copy link

My C++ version: https://gist.github.com/MLaszczewski/30fae56a7c291e673cd8be822171d639
http://cpp.sh/72jbm
10000 Iterations in 49.917000 milliseconds - 0.004992 milliseconds per iteration.
Not optimized, but 10 times faster than scala :)

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