diff options
| -rw-r--r-- | src/main.rs | 24 | ||||
| -rw-r--r-- | src/position.rs | 4 | ||||
| -rw-r--r-- | src/solve.rs | 14 |
3 files changed, 24 insertions, 18 deletions
diff --git a/src/main.rs b/src/main.rs index f7b6a6e..e77ce2b 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,6 +1,6 @@ use std::io; use std::io::prelude::*; -use std::collections::HashMap; +use std::time::{Instant,Duration}; pub mod position; pub mod solve; @@ -10,6 +10,9 @@ use solve::solve; fn main() { + let mut total_time = Duration::new(0, 0); + let mut total_solve = 0; + for result in io::stdin().lock().lines() { let line = result.unwrap(); let fields: Vec<&str> = line.split_ascii_whitespace().collect(); @@ -26,20 +29,17 @@ fn main() { }; match fields[0].parse::<Position>() { Ok(pos) => { - // println!("{:?}", pos); - let mut cache = HashMap::with_capacity(30000); - println!("score: {:3} {:3}", solve(pos, -10000, 10000, &mut cache), expected_score); + print!("{:?}", pos); + let begin = Instant::now(); + let score = solve(pos); + let elapsed = begin.elapsed(); + total_time += elapsed; + total_solve += 1; + println!("score: {:3} {:3}, time: {:?}\n", score, expected_score, elapsed); } Err(msg) => eprintln!("wrong score format {:?}: {}", fields[1], msg), } } - - // let mut p = "7422341735647741166133573473242566".parse::<Position>().unwrap(); - // p = p.play(2); - // p = p.play(2); - // p = p.play(1); - // p = p.play(5); - // println!("{:?}", p); - // println!("{}", solve(p.clone(), -10000, 100000)); + println!("mean time {:?}", total_time / total_solve); } diff --git a/src/position.rs b/src/position.rs index 953881c..9ed617d 100644 --- a/src/position.rs +++ b/src/position.rs @@ -156,8 +156,8 @@ use std::fmt; impl fmt::Debug for Position { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { use Cell::*; - write!(f, "play_count: {}\n", self.play_count)?; - write!(f, "{:10}{:10}{:10}\n", "position", "mask", "player")?; + writeln!(f, "play_count: {}", self.play_count)?; + writeln!(f, "{:10}{:10}{:10}", "position", "mask", "player")?; for y in (0..FULL_HEIGHT).rev() { for x in 0..WIDTH { match self.at(y, x) { diff --git a/src/solve.rs b/src/solve.rs index e9c8c04..b950ab6 100644 --- a/src/solve.rs +++ b/src/solve.rs @@ -2,8 +2,14 @@ use std::collections::HashMap; use crate::position::{Position, WIDTH, HEIGHT}; +const COLUMNS_ORDER: [u64; 7] = [3, 2, 4, 1, 5, 0, 6]; -pub fn solve(p: Position, a: i32, b: i32, cache: &mut HashMap<u64, i32>) -> i32 { +pub fn solve(p: Position) -> i32 { + let mut cache = HashMap::with_capacity(30000); + solve_rec(p, -100000, 100000, &mut cache) +} + +fn solve_rec(p: Position, a: i32, b: i32, cache: &mut HashMap<u64, i32>) -> i32 { if let Some(score) = cache.get(&p.key()) { return *score; } @@ -28,12 +34,13 @@ pub fn solve(p: Position, a: i32, b: i32, cache: &mut HashMap<u64, i32>) -> i32 } } - for x in 0..WIDTH { + for x_unordered in 0..(WIDTH as usize) { + let x = COLUMNS_ORDER[x_unordered]; if !p.is_valid_play(x) { continue } - let score = -solve(p.play(x), -beta, -alpha, cache); + let score = -solve_rec(p.play(x), -beta, -alpha, cache); if score >= beta { return score; @@ -47,4 +54,3 @@ pub fn solve(p: Position, a: i32, b: i32, cache: &mut HashMap<u64, i32>) -> i32 return alpha; } - |