anigame.rs

extern crate rand;

use rand::Rng;
use std::cmp;

use std::fs::File;
use std::io::prelude::*;
use std::io::BufReader;
use std::path::Path;
use std::fmt;
    
#[derive(Clone,Debug,PartialEq)]
enum Cell {
    Red,
    Blue,
    Green,
    Yellow,
    Brown,
    Bomb,
    Empty
}

impl fmt::Display for Cell {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{}", match *self {
            Cell::Red => "R",
            Cell::Blue => "B",
            Cell::Green => "G",
            Cell::Yellow => "Y",
            Cell::Brown => "W",
            Cell::Bomb => "*",
            Cell::Empty => "."
        })
    }
}

#[derive(Clone,Debug)]
struct Board {
    width: usize,
    height: usize,
    data: Vec<Vec<Cell>>
}

type Score = u64;
type Position = (usize, usize);
type Direction = (i64, i64);

const adjacents: [Direction; 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];

impl Board {
    fn new(data: Vec<Vec<Cell>>) -> Board {
        Board { width: data[0].len(), height: data.len(), data: data }
    }
    fn from_file<P: AsRef<Path>>(path: P) -> Board {
        let mut v = vec![];
        let f = match File::open(path) {
            Ok(file) => file,
            _ => panic!()
        };
        let reader = BufReader::new(f);
        for line in reader.lines().map(|l| l.unwrap()) {
            let mut vv = vec![];
            for c in line.split(" ") {
                vv.push(match c {
                    "R" => Cell::Red,
                    "B" => Cell::Blue,
                    "G" => Cell::Green,
                    "Y" => Cell::Yellow,
                    "W" => Cell::Brown,
                    "*" => Cell::Bomb,
                    _ => panic!()
                })
            }
            v.push(vv);
        }
        Board::new(v)
    }
    fn play(&mut self, row: usize, col: usize) -> Score {
        let target = self.data[row][col].clone();
        match target {
            Cell::Empty => {
                panic!();
            },
            Cell::Bomb => {
                0
            },
            _ => {
                let tbd = self.to_be_deleted(row, col);
                if tbd.len() <= 1 {
                    panic!();
                }
                self.delete(&tbd);
                (tbd.len() * tbd.len() * 5) as Score
            }
        }
    }
    fn outside(&self, row: i64, col: i64) -> bool {
        row < 0 || col < 0 || row >= self.height as i64 || col >= self.width as i64
    }
    fn _dfs(row: usize, col: usize, state: &mut Board) -> Vec<Position> {

        if state.outside(row as i64, col as i64) {
            return vec![]
        }
        
        let cell = state.data[row][col].clone();
        let mut res = vec![(row, col)];

        state.data[row][col] = Cell::Empty;
        
        for d in adjacents.iter() {

            let next_row = row as i64 + d.0;
            let next_col = col as i64 + d.1;

            if state.outside(next_row, next_col) {
                continue;
            }
            if state.data[next_row as usize][next_col as usize] != cell {
                continue;
            }

            res.extend(Board::_dfs(next_row as usize, next_col as usize, state));
        }

        res
    }
    fn clickable(&self, row: usize, col: usize) -> bool {
        // skip bomb
        if self.outside(row as i64, col as i64) || self.data[row][col] == Cell::Empty || self.data[row][col] == Cell::Bomb {
            return false
        }
        adjacents.iter().any(|d| !self.outside(row as i64 + d.0, col as i64 + d.1) &&
                             self.data[row][col] == self.data[(row as i64 + d.0) as usize][(col as i64 + d.1) as usize])
    }
    fn clickable_list(&self) -> Vec<Position> {
        let mut res = vec![];
        for r in 0..self.height {
            for c in 0..self.width {
                if !self.clickable(r, c) {
                    continue;
                }
                let mut l = self.to_be_deleted(r, c);
                if l.len() <= 1 {
                    continue;
                }
                l.sort();
                res.push(l[0]);
            }
        }
        res.sort();
        res.dedup();
        res
    }
    fn over(&self) -> bool {
        self.clickable_list().len() == 0
    }
    fn to_be_deleted(&self, row: usize, col: usize) -> Vec<Position> {
        let mut state = self.clone();
        Board::_dfs(row, col, &mut state)
    }
    fn delete(&mut self, target: &Vec<Position>) {

        for p in target {
            self.data[p.0][p.1] = Cell::Empty;
        }
        
        for r in (1..self.height).rev() {
            for c in 0..self.width {
                if self.data[r][c] == Cell::Empty {
                    let mut top = -1;
                    for rr in (0..r).rev() {
                        if self.data[rr][c] != Cell::Empty {
                            top = rr as i64;
                            break;
                        }
                    }
                    if top == -1 {
                        continue;
                    }
                    let diff = r - top as usize;
                    self.data[r][c] = self.data[r - diff][c].clone();
                    self.data[r - diff][c] = Cell::Empty;
                }
            }
        }
        for c in (1..self.width).rev() {
            // let remain = !(0..self.height).map(|r| self.data[r][c] == Cell::Empty).fold(true, |a, c| a && c);
            if self.data[self.height - 1][c] == Cell::Empty {
                let mut left = -1;
                for cc in (0..c).rev() {
                    if self.data[self.height - 1][cc] != Cell::Empty {
                        left = cc as i64;
                        break;
                    }
                }
                if left == -1 {
                    continue;
                }
                let diff = c - left as usize;
                for r in 0..self.height {
                    self.data[r][c] = self.data[r][c - diff].clone();
                    self.data[r][c - diff] = Cell::Empty;
                }
            }
        }
    }
}

impl fmt::Display for Board {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        for r in 0..self.height {
            for c in 0..self.width {
                write!(f, "{}", self.data[r][c])?
            }
            write!(f, "{}", "\n")?
        }
        Result::Ok(())
    }
}

struct MonteCarlo {
}

// 14 x 9

impl MonteCarlo {
    fn choice(&self, board: &Board) -> Position {
        let available = board.clickable_list();
        // println!("available {:?}", available);
        let mut res = (0, 0);
        let mut max_score = 0;
        for c in available {
            // println!("playout for {:?}", c);
            let mut b = board.clone();
            let s = b.play(c.0, c.1);
            let mut _s = 0;
            for i in 0..1000 {
                // if i % 50 == 0 {
                //     println!("{}...", i);
                // }
                let mut _b = b.clone();
                _s = cmp::max(_s, self.playout(&mut _b));
            }
            if max_score < s + _s {
                res = c;
                max_score = s + _s;
            }
        }
        println!("max score of this choice: {}", max_score);
        res
    }
    fn playout(&self, board: &mut Board) -> Score {

        let mut rng = rand::thread_rng();
        let mut score = 0;
        
        loop {
            let available = board.clickable_list();
            // println!("available {:?}", available);
            if available.len() == 0 {
                break;
            }
            let i = rand::sample(&mut rng, 0..available.len(), 1)[0];
            score += board.play(available[i].0, available[i].1);
        }

        let mut remain = 0;
        for r in 0..board.height {
            for c in 0..board.width {
                if board.data[r][c] != Cell::Empty {
                    remain += 1;
                }
            }
        }

        let ratio = (remain as f64 / (board.height * board.width) as f64).floor() as i64;
        if ratio < 15 {
            let mut bonus = 25;
            for _ in 0..(15 - ratio) {
                score += bonus;
                bonus += 50;
            }
        }

        score
    }
    fn playout2(&self, board: &mut Board) -> (Score, Vec<Position>) {

        let mut rng = rand::thread_rng();
        let mut score = 0;
        let mut res = vec![];
        
        loop {
            let available = board.clickable_list();
            // println!("available {:?}", available);
            if available.len() == 0 {
                break;
            }
            let i = rand::sample(&mut rng, 0..available.len(), 1)[0];
            score += board.play(available[i].0, available[i].1);
            res.push(available[i]);
        }

        let mut remain = 0;
        for r in 0..board.height {
            for c in 0..board.width {
                if board.data[r][c] != Cell::Empty {
                    remain += 1;
                }
            }
        }

        let ratio = (100.0 * remain as f64 / (board.height * board.width) as f64).floor() as i64;
        // println!("{:?}", ratio);
        if ratio < 15 {
            let mut bonus = 25;
            for _ in 0..(15 - ratio) {
                score += bonus;
                bonus += 50;
            }
        }

        (score, res)
    }
    fn play(&self, board: &mut Board) -> Vec<Position> {
        let mut score = 0;
        let mut res = vec![];
        while !board.over() {
            let c = self.choice(board);
            println!("{:?}", c);
            println!("{}", board);
            res.push(c);
            score = score + board.play(c.0, c.1);
        }
        println!("score={}", score);
        res
    }
    fn play2(&self, board: &mut Board) -> Vec<Position> {
        let mut max_score = 0;
        let mut res = vec![];
        for _ in 0..1000 {
            let mut b = board.clone();
            let (score, seq) = self.playout2(&mut b);
            if score > max_score {
                println!("update score {} => {}", max_score, score);
                max_score = score;
                res = seq;
            }
        }
        
        println!("best answer: {:?}", res);
        for p in &res {
            board.play(p.0, p.1);
            println!("{}", board);
        }
        
        res
    }
}

fn main() {

    let mut b = Board::from_file("board.txt");

    // let d = vec![vec![Cell::Empty, Cell::Brown, Cell::Red], vec![Cell::Brown, Cell::Red, Cell::Red]];
    // let mut b = Board::new(d);
    
    // println!("{:?}", b);

    // b.play(1, 2);

    // println!("{:?}", b);

    // b.play(1, 2);

    // println!("{:?}", b);

    let monte = MonteCarlo{};

    // let score = monte.playout(&mut b);

    // println!("score={} {:?}", score, b);

    let seq = monte.play(&mut b);
    println!("{:?}", seq);
}