Posted at

貪欲ライフゲーム

More than 1 year has passed since last update.

lifegame.gif

(4x4の探索の様子)

長寿命パターンを探ろうのコーナーです

総当たりするのですが計算量が2^nになるので終わりが遠いです

subsequencesが全パターン列挙を担っています

それをevalが寿命を計算し、searchが寿命を比較してより長寿命のパターンを保持します

use std::time;

use std::thread;

type Cells = Vec<Vec<bool>>;

// コンウェイさんのルール
fn rule(c: bool, n: u8) -> bool {
match (c, n) {
(true, 2) => true,
(true, 3) => true,
(false, 3) => true,
_ => false
}
}

// 年齢を重ねる
fn next(cells: &Cells) -> Cells {
let mut new = cells.clone();
let sy = cells.len();
let sx = cells[0].len();

for y in 0 .. sy {
for x in 0 .. sx {
let c = cells[y][x];
let y = y as i32;
let x = x as i32;
let sy = sy as i32;
let sx = sx as i32;

// セル[y,x]の周辺のセルを数を数える
let mut n = 0;
for ay in y - 1 .. y + 2 {
for ax in x - 1 .. x + 2 {
if (ay != y || ax != x) && 0 <= ay && ay < sy && 0 <= ax && ax < sx {
if cells[ay as usize][ax as usize] {
n += 1;
}
}
}
}

new[y as usize][x as usize] = rule(c,n);
}
}

return new;
}

// 人に見易く
fn display(cells: &Cells) {
for y in cells {
for &c in y {
if c {
print!("O");
}
else {
print!(" ");
}
}
print!("\n");
}
}

// セル同士の比較
fn eq(c1: &Cells, c2: &Cells) -> bool {
if c1.len() == c2.len() {
for y in 0 .. c1.len() {
if c1[y].len() == c2[y].len() {
for x in 0 .. c1[y].len() {
if c1[y][x] != c2[y][x] {
return false;
}
}
}
else {
return false;
}
}

return true;

} else {
return false;
}
}

// 寿命を計算
fn eval(cells: &Cells) -> u32 {
let mut n = 0;

// 周期パターンを検知する用
let mut history = vec!(cells.clone());

loop {
n += 1;

// コンパイラに怒られ続けた結果、popしてすぐpush羽目に
// history[history.len() - 1]じゃダメらしい
let pre = history.pop().unwrap();
let new = next(&pre);
history.push(pre);

for h in &history {
if eq(&new, &h) {
return n;
}
}

history.push(new);

// 過去13件を保持
if history.len() >= 13 {
history.remove(0);
}
}
}

// 総当たり
// 正直、どう働いているのかよくわかってない
// xsがでかくなるとメモリを食いまくるし終わらないのでイテレーターとして使います
fn subsequences<F>(xs: &Vec<(usize,usize)>, mut f: F)
where F: FnMut(&Vec<(usize,usize)>) {

let max = (2 as u64).pow(xs.len() as u32);
for n in 1 .. max {
let mut ys = vec!();
for i in 0 .. xs.len() {
if (n & (1 << i)) != 0 {
ys.push(xs[i]);
}
}

println!("{}/{}", n, max);
f(&ys);
}
}

// 貪欲に探します
fn search(mut cells: Cells, start: (usize,usize), end: (usize,usize)) -> Cells {
let mut ls = vec!();
for y in start.0 .. end.0 + 1 {
for x in start.1 .. end.1 + 1 {
ls.push((y,x));
}
}

let mut search_cells = cells.clone();
let mut best_cells = cells.clone();
let mut best_score = eval(&best_cells);

print!("\x1B[1J");
subsequences(&ls, |ps| {
for &(y,x) in ps {
search_cells[y][x] = true;
}

// ansi escape code, カーソルを0,0に移動して画面クリア
print!("\x1B[0;0H\x1B[0J");

let score = eval(&search_cells);
println!("{}: {}", best_score, score);
display(&search_cells);

// 寿命が長い方を保持
// 寿命をスコアとか言っちゃうと殺伐とする
if score > best_score {
best_cells = search_cells.clone();
best_score = score;
}

search_cells = cells.clone();
});

return best_cells;
}

// セルを初期化
fn new_cells(sy: u32, sx: u32) -> Cells {
let mut cs = vec!();
for _ in 0 .. sy + 1{
cs.push(vec!());
let i = cs.len() - 1;
for _ in 0 .. sx + 1 {
cs[i].push(false);
}
}

return cs;
}

fn main() {
let mut cells = new_cells(50, 200);
// wikipediaに乗ってるドングリがこのサイズ
cells = search(cells,(20,100),(22,106));

loop {
display(&cells);
cells = next(cells);
thread::sleep(time::Duration::from_secs(1));
}
}


終わり

rustで書いて見たのですがコンパイラにボッコボコにされましてつらぽよです

それゆえに多々変なコードになってると思います

最初haskellで書いたのですが、それと比べかなり早いので辛い思いしたかいあったなと

もうrust書きたくないと思っても、またやろうと思える魅力ある言語です


おまけ

最初に書いたhaskell版

もうちょい速度が欲しかったのでrustで書き直した次第です

すごい簡潔で良いのですがね

{-# LANGUAGE Strict #-}

import System.Console.ANSI
import Control.Monad
import Control.Concurrent
import Data.Array
import Data.List

type Cells = Array (Int,Int) Bool

rule :: Bool -> Int -> Bool
rule True 2 = True
rule True 3 = True
rule False 3 = True
rule _ _ = False

next :: Cells -> Cells
next cs = array bs $ map (\i -> (i, go i)) $ range bs
where
bs = bounds cs
go i@(y,x) = rule (cs ! i)
$ length
$ filter (cs !)
$ filter (inRange bs)
$ [(y-1,x-1),(y-1,x),(y-1,x+1),
(y,x-1),(y,x+1),
(y+1,x-1),(y+1,x),(y+1,x+1)]

eval :: Int -> Cells -> Int
eval n cs = go 0 $ iterate next cs
where
go n' (c1:c2:c3:c4:c5:c6:c7:c8:c9:css) =
if n < n' || (elem c1 [c2,c3,c4,c5,c6,c7,c8,c9]) then
n'
else
go (n' + 1) (c2:c3:c4:c5:c6:c7:c8:c9:css)

display :: Cells -> IO ()
display cs = do
let ix@(_,(_,maxX)) = bounds cs
putStrLn
$ concat
$ flip map (range ix)
$ \i@(y,x) -> (if cs ! i then 'O' else ' ') : (if x == maxX then "\n" else "")

bruteforce :: (Int,Int) -> (Int,Int) -> Int -> IO Cells
bruteforce size@(sy,sx) rng@(ry,rx) life = do
let
field = listArray ((1,1),size) $ repeat False
css = subsequences
[((y,x),True) |
y <- [sy`div`2-ry`div`2..sy`div`2+ry`div`2],
x <- [sx`div`2-rx`div`2..sx`div`2+rx`div`2]]
patterns = 2 ^ rangeSize ((1,1),rng)

loop n score cells [] = pure cells
loop n score cells (c:cs) = do
let
cells' = field // c
score' = eval life cells'

setCursorPosition 0 0
clearScreen
print (patterns, n)
print (score,score')
display cells'

when (score > life) $ do
writeFile ("lifegame-best-cells-" ++ show n ++ ".hs") $ show cells'

if score < score' then do
loop (n + 1) score' cells' cs
else
loop (n + 1) score cells cs
loop 0 0 field css

main = do
hideCursor
best <- bruteforce (50,200) (2,6) 10000
writeFile "lifegame-best-cells.hs" $ show best
let max = eval (100^2) best
forM_ (zip [1..(max + 3)] $ iterate next best) $ \(n,cs) -> do
setCursorPosition 0 0
clearScreen
putStrLn $ show n ++ "/" ++ show max
display cs
threadDelay $ 10 ^ 5 * 1