貪欲ライフゲーム

（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