samedi 13 mars 2021

Improve Conway's Game Of Life implementation

Cell.scala

case class Cell(status: Status)
sealed trait Status
case object Alive extends Status
case object Dead extends Status

Grid.scala

case class Coordinates(x: Int, y: Int)

case class Grid(width:Int, height: Int, board: List[Cell]){

  val neighboursHelper = List((-1, -1),(-1, 0),(-1, 1),( 0, -1),( 0, 1),( 1, -1),(+1, 0),( 1, 1))

  def updatedGeneration(neighboursMap: Map[Int, List[Int]]): Grid = {
    val result = board.zipWithIndex.map(x => Rules.evolveCell(x._2, neighboursMap, this))
    Grid(width, height, result)
  }

  def getCoordinates(i: Int): Coordinates = {
    Coordinates(i % width, i / width)
  }

  def getIndex(value: Coordinates): Int = {
    value.y * width + value.x
  }

  def generateNeighbours(current: Int): List[Int] ={
    val Coordinates(x, y) = getCoordinates(current)
    neighboursHelper
      .map   { case (row, column) => (row+x, column+y) }
      .filter{ case (row, column) => isValidPosition(row,column) }
      .map   { case (row, column) => getIndex(Coordinates(row, column)) }
  }
  private def isValidPosition(row: Int, column: Int): Boolean = {
    row >= 0 &&
      row < width &&
      column >= 0 &&
      column < height
  }

  def countAliveNeighbours(list: List[Int]):Int = list.count(i => board(i) == Cell(Alive))
}

Rules.scala

object Rules{
  def evolveCell(currentIndex: Int, neighboursMap: Map[Int, List[Int]], grid: Grid): Cell = {
    val Some(currentNeighbours) = neighboursMap.get(currentIndex)
    val alive = grid.countAliveNeighbours(currentNeighbours)
    grid.board(currentIndex) match {
      case Cell(Alive) =>  alive match {
        case n if n < 2 => Cell(Dead)
        case n if n <= 3 => Cell(Alive)
        case n if n > 3 => Cell(Dead)
      }
      case Cell(Dead) => alive match {
        case n if n == 3 => Cell(Alive)
        case _ => Cell(Dead)
      }
    }
  }

}

FileParser.scala

import scala.io.Source

object FileParser extends App {

  def readFile(filename: String): Grid = {
    // Reads the contents of the file
    var lines = Source.fromFile(filename).getLines()
    // Converts it into a List of Cells
    val result = lines.flatMap(x => x.stripLineEnd).map(y => if(y == '*') Cell(Alive) else Cell(Dead))
    val h = Source.fromFile(filename).getLines().length
    val w = Source.fromFile(filename).bufferedReader.readLine.length
    Grid(w, h, result.toList)
  }
}

Game.scala

object Game extends App {

  var game = FileParser.readFile("inputs1.txt")
  val neighboursMap: Map[Int, List[Int]] = game.board.zipWithIndex.map(x => x._2 -> game.generateNeighbours(x._2)).toMap
  val t1 = System.nanoTime
  for(i <- 1 to 1000){
    game = game.updatedGeneration(neighboursMap)
    if (i % 10 == 0) println(i)
  }

  val duration = (System.nanoTime - t1) / 1e9d

  var count = 0
  for (i <- game.board.indices){
      if(count == 100){
        println()
        count = 0
      }
      print(game.board(i))
      count+=1
    }

  println(duration)
}

Here is my implementation of a Scala version of Game of Life, in the Game.scala I want to get the output of 1000 in about 5 minutes, but my version takes approximately 17 minutes. I wanted to improve this version to reduce the running time as low as possible. Any suggestions on how to improve or what to change will really be appertained
Also here is a input file in case someone tries to run it.
https://drive.google.com/file/d/1xER3RWv_-dNQsU7XNvW9tXaTgKNNIi2b/view?usp=sharing

Aucun commentaire:

Enregistrer un commentaire