Skip to content

Instantly share code, notes, and snippets.

@kamiyaowl

kamiyaowl/LifegameGenetic.scala

Last active August 29, 2015 13:57
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kamiyaowl/9407281 to your computer and use it in GitHub Desktop.
Save kamiyaowl/9407281 to your computer and use it in GitHub Desktop.
Download ZIP
LifeGameの初期配置を遺伝的アルゴリズムで求める
Raw
_after
=== load from after ===
_____________________
# ##
# #
######
# # #
# # #
### # ##
## #
# ## #
### # #
# #
# # ##
# # ## ## ##
# # # ## ## ##
# # # #
# # ## ##
# ### # # #
## # ## # ##
# ###
##
#
+++ world end 207 +++
_____________________
#
# #
## # #
# # #
#
##
##
##
# #
##
Raw
_before
=== load from before ===
_____________________
### ## #
### # # # #
# ### #
## # ## # #
## # # # #
# ## ### # ##
# # #
### # # #
# ## # # # # # #
## # # ## #
# ## # #
## # # # ## # ##
##
### # #
## ## ##
# ## # #
## ## ## # #
# # # # # #
# # #
# # # # ## # ##
+++ world end 120 +++
_____________________
##
##
##
# #
##
##
##
##
##
Raw
_Lifegame.scala
import scala.language.postfixOps
import scala.util.Random
import scala.io.Source
object Lifegame {
implicit class RichList[T](self:List[T]){
def shuffle() = (new Random).shuffle(self)
}
implicit class Field(self:Map[(Int,Int),Boolean]) {
def around(p:(Int,Int), d:Int = 1) = self filter(x => Tools.aroundPoint(p,d).contains(x._1))
def isLive(p:(Int,Int)) = {
val lives = around(p) filter(_._2)
//born
if(!self(p)) {
if(lives.size == 3) true else false
} else { //live or death
lives.size match {
case 2 => true
case 3 => true
case _ => false
}
}
}
def next() = self map(x => (x._1._1, x._1._2) -> isLive(x._1))
def show(implicit size:(Int,Int)) = {
println("_" * size._1)
for(j <- 0 until size._2) {
for(i <- 0 until size._1) {
self((i,j)) match {
case true => print("#")
case false => print(" ")
}
}
println("")
}
}
def future() : Stream[Map[(Int,Int),Boolean]] = {
Stream.cons(self, self.next.future)
}
}
object Tools {
def field(implicit size:(Int,Int)) = (for(j <- 0 until size._2 ; i <- 0 until size._1) yield ((i,j) -> false)).toMap
def aroundPoint(x:(Int,Int), d:Int = 1) = List((x._1 - d, x._2 - d), (x._1 - d, x._2 + d), (x._1 + d, x._2 - d), (x._1 + d, x._2 + d), (x._1 - d, x._2), (x._1 + d, x._2), (x._1, x._2 - d), (x._1, x._2 + d))
def create(implicit size:(Int,Int)) = {
val f = field
val t = f.toList.shuffle.take((new Random).nextInt(f.size)) map(x => {((x._1._1,x._1._2) -> true)})
f ++ t
}
def worldEnd(futures:Stream[Map[(Int,Int),Boolean]],current:Int = 0)(threash:Int = 3) : (Map[(Int,Int),Boolean],Int) = {
if(futures.take(threash).tail.filter(futures.head.equals).length != 0) (futures.head, current)
else worldEnd(futures.tail,current + 1)(threash)
}
}
def main(args:Array[String]) = {
var start:Map[(Int,Int),Boolean] = Map.empty
implicit var size:(Int,Int) = (0,0)
var gen = 0
var x = 0
var y = 0
val s = Source.fromFile(args(0))
for(line <- s.getLines){
x = 0
for(c <- line){
start += (x,y) -> (c == '#')
x += 1
if(size._1 < x) size = (x,size._2)
}
y += 1
if(size._2 < y) size = (size._1, y)
}
size = (size._1 + 1, size._2 + 1)
start = Tools.field ++ start
println("=== load from " + args(0) + " ===")
start.show
val result = Tools.worldEnd(start.future,0)(3)
println("+++ world end " + result._2 + " +++")
result._1.show
/*for(g <- start.future){
println("++++++++++" + gen + "+++++++++")
g.show
gen += 1
}*/
}
}
Raw
LifegameGenetic.scala
import scala.language.postfixOps
import scala.util.Random
import scala.reflect._
object LifegameGenetic {
abstract class Cell[T] {
var self:T
def show()
def make()
def eval():Int
def +(target:T) : (Cell[T],Cell[T])
def mutation()
def copy() : Cell[T]
}
class World extends Cell[Map[(Int,Int),Boolean]] {
var self:Map[(Int,Int),Boolean] = Map()
var size:(Int,Int) = (10,10)//default
var evalGen = 10
override def show() = {
self.show(size)
}
override def make() = {
self = Tools.richCreate(evalGen)(size)
}
override def eval() = {
val e = self.future.take(evalGen).reverse.head.filter(_._2).size
println(",eval = " + e)
e
}
override def +(target:Map[(Int,Int),Boolean]) = {
val r = new Random
val pivotX = r.nextInt(size._1)
val pivotY = r.nextInt(size._2)
val pivot = pivotX * pivotY
val selfA = self filter(x => (x._1._1 * x._1._2 < pivot))
val selfB = self filter(x => (x._1._1 * x._1._2 >= pivot))
val targetA = target filter(x => (x._1._1 * x._1._2 < pivot))
val targetB = target filter(x => (x._1._1 * x._1._2 >= pivot))
val child1 = copy
val child2 = copy
child1.self = selfA ++ targetB
child2.self = selfB ++ targetA
(child1,child2)
}
def mutation() = {
val m = self.toList.shuffle.head
println(",,mutation = " + m)
self += m._1 -> !m._2
}
def copy() = {
val c = new World
c.self = self
c.size = size
c
}
}
class WorldTool(evalGen:Int,size:(Int,Int))
{
def makeFirst() : Stream[World] = {
val n = new World
n.size = size
n.evalGen = evalGen
n.make
Stream.cons(n, makeFirst)
}
def crossing[T](evaled:Stream[World]) : Stream[World] = {
if(evaled.length < 2) Stream.empty
else {
val crossed = evaled(0) + evaled(1).self
Stream.cons(crossed._1, Stream.cons(crossed._2, crossing(evaled.tail.tail)))
}
}
def nextGen(current:Stream[World]) : Stream[World] = {
val ranked = current zip (current map(_.eval)) sortWith((a,b) => a._2 > b._2) filter(_._2 != 0)
val next = ranked map(_._1)
if((new Random).nextFloat < 0.01 * next.length) next.toList.shuffle.head.mutation
else Map()
crossing(next)
}
def autoGen(current:Stream[World]) : Stream[Stream[World]] = {
Stream.cons(current,autoGen(nextGen(current)))
}
}
implicit class RichList[T](self:List[T]){
def shuffle() = (new Random).shuffle(self)
}
implicit class Field(self:Map[(Int,Int),Boolean]) {
def around(p:(Int,Int), d:Int = 1) = self filter(x => Tools.aroundPoint(p,d).contains(x._1))
def isLive(p:(Int,Int)) = {
val lives = around(p) filter(_._2)
//born
if(!self(p)) {
if(lives.size == 3) true else false
} else { //live or death
lives.size match {
case 2 => true
case 3 => true
case _ => false
}
}
}
def next() = self map(x => (x._1._1, x._1._2) -> isLive(x._1))
def show(implicit size:(Int,Int)) = {
println("_" * size._1)
for(j <- 0 until size._2) {
for(i <- 0 until size._1) {
self((i,j)) match {
case true => print("#")
case false => print(" ")
}
}
println("")
}
}
def future() : Stream[Map[(Int,Int),Boolean]] = {
Stream.cons(self, self.next.future)
}
}
object Tools {
def field(implicit size:(Int,Int)) = (for(j <- 0 until size._2 ; i <- 0 until size._1) yield ((i,j) -> false)).toMap
def aroundPoint(x:(Int,Int), d:Int = 1) = List((x._1 - d, x._2 - d), (x._1 - d, x._2 + d), (x._1 + d, x._2 - d), (x._1 + d, x._2 + d), (x._1 - d, x._2), (x._1 + d, x._2), (x._1, x._2 - d), (x._1, x._2 + d))
def create(implicit size:(Int,Int)) = {
val f = field
val t = f.toList.shuffle.take((new Random).nextInt(f.size)) map(x => {((x._1._1,x._1._2) -> true)})
f ++ t
}
def richCreate(saveGen:Int)(implicit size:(Int,Int)) = {
println(",,,,richCreate gen = " + saveGen)
var n = create(size)
while(n.future.take(saveGen).reverse.head.filter(_._2).size == 0){
println(",,,,retry")
n = create(size)
}
n
}
}
def main(args:Array[String]) = {
val size = (20,20)
val evalGen = 15
val t = new WorldTool(evalGen,size)
val first = t.makeFirst take 30
val processed = t.autoGen(first) take 30
var genCount = 0
for(p <- processed){
genCount += 1
println("========== " + genCount + " ==========")
println("worlds_count = " + p.length)
println("default lives = " + p(0).self.filter(_._2).size)
val p_future = p(0).self.future.take(evalGen).reverse.head
println("after lives = " + p_future.filter(_._2).size)
println("\n\n++++++++++ seed world ++++++++++")
p(0).show
println("\n\n********** after world **********")
p_future.show(size)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment