tictactoe

main.rs

/*
    Question: https://jrms-random-blog.blogspot.com/2021/03/a-google-interview-question.html
    Shor: building a tic tac toe winning algo

    Solutions

        map: 4x4
        3  O O O O             8
        2  O O O O             8
        1  O O O O             8
        0  O O O O             8
        yx 0 1 2 3

    Save map as u32

    Save map as Vector:vec!

        let map: Vec<Vec<u8>> = vec![vec![0, 0, 0]]; // map as vec
        println!("pos: ({},{})", map[0][0], map[0][0]);

    Save map as array

        let arr_map: [[u8; 3]; 3] = [[0; 3]; 3]; // map as array
        println!("{:#?}", arr_map);

    Save turns without map

        let mut pos: [Vec<(u8, u8)>; 2] = [vec![], vec![]];
        pos[0].push((0, 0));
        pos[0].push((0, 1));
        println!("{:#?}", pos);

        states: None=00,X=01(1),O=10(2)
        2-bits

        | = OR -> set
        & = AND -> unset
        ^ = XOR -> toggle


        todo:
            - add rules
                - free to set rule
                - on top of it
            - use automated tests
            - use as lib
            - use enums and traits for multiple impl
            - use magic square: https://fowlie.github.io/2018/08/24/winning-algorithm-for-tic-tac-toe-using-a-3x3-magic-square/


        possible win positions

        {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, //horizontal wins
        {0, 3, 6}, {1, 4, 7}, {2, 5, 8}, //virticle wins
        {0, 4, 8}, {2, 4, 6}             // diagonal wins


*/

use std::fmt;

pub struct TicTacToe {
    map: u32,
}

const MAP_SIZE: u8 = 6; //6 = 3x3, 8 = 4x4
const CALC: u8 = MAP_SIZE / 2;
const X: u8 = 0b01;
const O: u8 = 0b10;
const WINS: [[u32; 8]; 2] = [
    [
        0b00000000000000000001000001000001,
        0b00000000000000000100000100000100,
        0b00000000000000010000010000010000,
        0b00000000000000000000000000010101,
        0b00000000000000000000010101000000,
        0b00000000000000010101000000000000,
        0b00000000000000010000000100000001,
        0b00000000000000010000000100000001,
    ],
    [
        0b00000000000000000010000010000010,
        0b00000000000000001000001000001000,
        0b00000000000000100000100000100000,
        0b00000000000000000000000000101010,
        0b00000000000000000000101010000000,
        0b00000000000000101010000000000000,
        0b00000000000000100000001000000010,
        0b00000000000000100000001000000010,
    ],
];

impl TicTacToe {
    pub fn new() -> TicTacToe {
        TicTacToe { map: 0 }
    }
    pub fn reset(&mut self) {
        self.map = 0;
    }

    fn set(&mut self, pos: (u8, u8), v: u8) {
        // if self.get(pos) != 0 {}
        let n: u32 = v as u32;
        self.map |= n << (pos.0 * 2) << (pos.1 * MAP_SIZE)
    }

    pub fn set_x(&mut self, pos: (u8, u8)) {
        self.set(pos, X);
    }
    pub fn set_o(&mut self, pos: (u8, u8)) {
        self.set(pos, O);
    }

    pub fn check_x(&self, pos: (u8, u8)) -> bool {
        self.get(pos) == X
    }

    pub fn check_o(&self, pos: (u8, u8)) -> bool {
        self.get(pos) == O
    }

    pub fn get(&self, pos: (u8, u8)) -> u8 {
        (((0b11 << (pos.0 * 2) << (pos.1 * MAP_SIZE)) & self.map)
            >> (pos.1 * MAP_SIZE)
            >> (pos.0 * 2))
            .to_be_bytes()[3]
    }

    pub fn winhash(self) -> u8 {
        for i in WINS[0].iter() {
            if self.map & i == *i {
                return X;
            }
        }
        for i in WINS[1].iter() {
            if self.map & i == *i {
                return O;
            }
        }
        0
    }

    pub fn win(self) -> u8 {
        let mut n: u8 = 0;
        let winner = |n: u8| {
            if n == CALC {
                X
            } else if n == (CALC * 2) {
                O
            } else {
                0
            }
        };

        // calc horizontal
        for x in 0..CALC {
            for y in 0..CALC {
                let p = self.get((y, x));
                if p == 0 {
                    n = 0;
                    break;
                }
                n += p;
            }
            n = winner(n);
            if n > 0 {
                return n;
            };
        }

        // calc vertical
        for x in 0..CALC {
            for y in 0..CALC {
                let p = self.get((x, y));
                if p == 0 {
                    n = 0;
                    break;
                }
                n += p;
            }
            n = winner(n);
            if n > 0 {
                return n;
            };
        }

        // calc diagonal
        for x in 0..CALC {
            let p = self.get((x, x));
            if p == 0 {
                n = 0;
                break;
            }
            n += p;
        }
        n = winner(n);
        return n;
    }
}

impl fmt::Display for TicTacToe {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, " {}\n\n", "---".repeat(5))?;
        for y in (0..(MAP_SIZE / 2)).rev() {
            write!(f, "{}", "|")?;
            for x in 0..(MAP_SIZE / 2) {
                if self.check_x((x, y)) {
                    write!(f, "{}", " X |")?;
                } else if self.check_o((x, y)) {
                    write!(f, "{}", " O |")?;
                } else {
                    write!(f, "{}", "   |")?;
                }
            }
            write!(f, "\n")?;
        }

        write!(f, "\n {}", "---".repeat(5))?;
        write!(f, "\nBitmap: 0b{:032b}", self.map)?;
        Ok(())
    }
}

fn main() {
    let mut t3: TicTacToe = TicTacToe::new();

    // diagonal win
    //t3.set_o((3, 3));
    t3.set_x((0, 0));
    t3.set_x((1, 1));
    t3.set_x((2, 2));

    //t3.set_o((1, 0));
    //t3.set_o((2, 0));

    // horizontal win
    // t3.set_x((0, 1));
    // t3.set_x((1, 1));
    // t3.set_x((2, 1));

    // vertical win
    // t3.set_o((2, 0));
    // t3.set_o((2, 1));
    // t3.set_o((2, 2));

    /*possible wins*/
    // t3.set_o((0, 2));
    // t3.set_o((1, 2));
    // t3.set_o((2, 2));

    println!("{}", t3);

    //let w = t3.win();
    let w = t3.winhash();

    println!(
        "winner is: {}",
        if w == X {
            "x"
        } else if w == O {
            "O"
        } else {
            "nobody"
        }
    );
    let u: u32 = 100;
    let a: [[u8; 4]; 4] = [[8, 8, 8, 8], [8, 8, 8, 8], [8, 8, 8, 8], [8, 8, 8, 8]];
    let v: Vec<Vec<u8>> = vec![
        vec![8, 8, 1, 8],
        vec![7, 8, 8, 5],
        vec![8, 8, 1, 8],
        vec![8, 2, 8, 8],
    ];
    println!("u32 occupies {} bytes", std::mem::size_of_val(&u));
    println!("array occupies {} bytes", std::mem::size_of_val(&a));
    println!("vec occupies {} bytes", std::mem::size_of_val(&v));
}