fifteen.rs

use std::str::FromStr;
use std::fmt::Debug;
use std::io::stdin;
use std::io::stdout;
use std::io::Write;
use std::fmt::Formatter;

trait Game : Clone {
    type Move : Copy + FromStr + PartialEq + Debug;
    fn start() -> Self;
    fn moves(&self) -> Vec<Self::Move>;
    fn apply_move(&self, Self::Move) -> Self;
    fn score_finished_game(&self) -> f64;  // returns >0 if last move won the game.
}


// === How to play a game, if you're a computer

fn max<T, I>(mut iter: I) -> T
    where I: Iterator<Item=T>, T: PartialOrd
{
    let first = iter.next().expect("max: empty iterator");
    iter.fold(first, |a, b| if a > b { a } else { b })
}

fn max_by<T, I, F, M>(mut iter: I, score: F) -> T
  where
    I: Iterator<Item=T>,
    F: Fn(&T) -> M,
    M: PartialOrd
{
    let init_value = iter.next().expect("max_by: empty iterator");
    let init_score = score(&init_value);
    let (max_value, _) = iter.fold((init_value, init_score), |(v1, s1), v2| {
        let s2 = score(&v2);
        if s2 > s1 { (v2, s2) } else { (v1, s1) }
    });
    max_value
}

fn best_move<G: Game>(game: &G) -> G::Move {
    *max_by(game.moves().iter(), |m| score_move(game, **m))
}

fn score_move<G: Game>(game: &G, m: G::Move) -> f64 {
    score_game(&game.apply_move(m))
}

fn score_game<G: Game>(game: &G) -> f64 {
    let moves = game.moves();
    if moves.len() == 0 {
        game.score_finished_game()
    } else {
        -max(moves.iter().map(|m| score_move(game, *m)))
    }
}


// === A layer of paint

fn input_one_of<G: Game>(options: &Vec<G::Move>, prompt: &str) -> std::io::Result<Option<G::Move>>
{
    loop {
        try!(stdout().write(prompt.as_bytes()));
        try!(stdout().flush());
        let mut line_buf = String::new();
        try!(stdin().read_line(&mut line_buf));
        if line_buf.len() == 0 {
            return Ok(None);  // user typed the EOF key, treat it like "q"
        }
        let line_str : &str = line_buf.as_ref();
        let line = line_str.trim();

        if line == "q" {
            return Ok(None);
        }
        if line == "?" {
            println!("options: {:?}", options);
            continue;
        }
        match G::Move::from_str(&line) {
            Err(_) => {
                println!("i didn't understand that");
                continue;
            }
            Ok(m) => {
                if options.contains(&m) {
                    return Ok(Some(m));
                } else {
                    println!("{:?} is not an option (enter ? to show all options)", m);
                }
            }
        }
    }
}

fn play_human_vs_computer<G: Game + Debug, F>(select_move: F, start: G)
  where
    G::Move: PartialEq + Debug + FromStr,
    F: Fn(&G) -> G::Move
{
    println!("{:?}", start);

    let mut board = start;

    loop {
        let options = board.moves();
        if options.len() == 0 {
            println!("game over");
            let s = board.score_finished_game();
            println!("{}",
                if s == 0.0 {
                    "it's a tie"
                } else if s > 0.0 {
                    "i win"
                } else {
                    "you win"
                });
            return;
        }
        let your_move = match input_one_of::<G>(&options, "your turn> ").unwrap() {
            None => {
                return; // user typed "q" to quit
            },
            Some(m) => m
        };

        board = board.apply_move(your_move);
        println!("{:?}", board);
        let move_vec = board.moves();
        if move_vec.len() == 0 {
            println!("game over");
            let s = board.score_finished_game();
            println!("{}",
                if s == 0.0 {
                    "it's a tie"
                } else if s > 0.0 {
                    "you win"
                } else {
                    "i win"
                });
            return;
        }

        // computer's turn
        let my_move = select_move(&board);
        println!("my move: {:?}", my_move);
        board = board.apply_move(my_move);
        println!("{:?}", board);
    }
}


// === The game of Pennies

#[derive(Debug, Clone, Copy)]
struct Pennies(i32);

impl Game for Pennies {
    type Move = i32;

    fn start() -> Pennies {
        Pennies(14)
    }
    fn moves(&self) -> Vec<i32> {
        let Pennies(n) = *self;
        (1..4).filter(|x| n - x >= 0).collect::<Vec<i32>>()
    }
    fn apply_move(&self, m: i32) -> Pennies {
        let Pennies(n) = *self;
        Pennies(n - m)
    }
    fn score_finished_game(&self) -> f64 {
        1.0
    }
}


// === The game of Fifteen

#[derive(Clone, Copy)]
struct BitSet16(u16);

impl BitSet16 {
    fn has(&self, i: i32) -> bool {
        let BitSet16(bits) = *self;
        0 <= i && i < 16 && (1u16 << i) & bits != 0
    }

    fn with(&self, i: i32) -> BitSet16 {
        let BitSet16(bits) = *self;
        BitSet16(bits | (1u16 << i))
    }

    fn wins(&self) -> bool {
        // A bitset is a winner if it contains three distinct numbers
        // that add up to 15.
        (1 .. 8).any(|i| self.has(i) &&
            (i + 1 .. 9).any(|j| self.has(j) && {
                let k = 15 - (i + j);
                k > j && k <= 9 && self.has(k)
            }))
    }
}

impl Debug for BitSet16 {
    fn fmt(&self, f: &mut Formatter) -> Result<(), std::fmt::Error> {
        (0..16).filter(|i| self.has(*i)).collect::<Vec<i32>>().fmt(f)
    }
}

#[derive(Debug, Clone, Copy)]
struct Fifteen {
    red: BitSet16,
    blue: BitSet16
}

impl Game for Fifteen {
    type Move = i32;
    fn start() -> Fifteen {
        Fifteen { red: BitSet16(0), blue: BitSet16(0) }
    }
    fn moves(&self) -> Vec<i32> {
        if self.blue.wins() {
            Vec::new()
        } else {
            let Fifteen { red: BitSet16(r), blue: BitSet16(b) } = *self;
            let used = r | b;
            (1..10).filter(|i| (1u16 << i) & used == 0).collect::<Vec<i32>>()
        }
    }
    fn apply_move(&self, m: i32) -> Fifteen {
        Fifteen { red: self.blue, blue: self.red.with(m) }
    }
    fn score_finished_game(&self) -> f64 {
        if self.blue.wins() { 1.0 } else { 0.0 }
    }
}

fn main() {
    play_human_vs_computer(best_move::<Fifteen>, Fifteen::start());
}