diff options
Diffstat (limited to '2020-overdrive/vroomba-analysis')
| -rw-r--r-- | 2020-overdrive/vroomba-analysis/Cargo.lock | 378 | ||||
| -rw-r--r-- | 2020-overdrive/vroomba-analysis/Cargo.toml | 11 | ||||
| -rw-r--r-- | 2020-overdrive/vroomba-analysis/src/main.rs | 182 |
3 files changed, 571 insertions, 0 deletions
diff --git a/2020-overdrive/vroomba-analysis/Cargo.lock b/2020-overdrive/vroomba-analysis/Cargo.lock new file mode 100644 index 0000000..9ac35c7 --- /dev/null +++ b/2020-overdrive/vroomba-analysis/Cargo.lock @@ -0,0 +1,378 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +[[package]] +name = "ansi_term" +version = "0.11.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ee49baf6cb617b853aa8d93bf420db2383fab46d314482ca2803b40d5fde979b" +dependencies = [ + "winapi", +] + +[[package]] +name = "anyhow" +version = "1.0.28" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d9a60d744a80c30fcb657dfe2c1b22bcb3e814c1a1e3674f32bf5820b570fbff" + +[[package]] +name = "atty" +version = "0.2.14" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d9b39be18770d11421cdb1b9947a45dd3f37e93092cbf377614828a319d5fee8" +dependencies = [ + "hermit-abi", + "libc", + "winapi", +] + +[[package]] +name = "autocfg" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f8aac770f1885fd7e387acedd76065302551364496e46b3dd00860b2f8359b9d" + +[[package]] +name = "bitflags" +version = "1.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693" + +[[package]] +name = "clap" +version = "2.33.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5067f5bb2d80ef5d68b4c87db81601f0b75bca627bc2ef76b141d7b846a3c6d9" +dependencies = [ + "ansi_term", + "atty", + "bitflags", + "strsim", + "textwrap", + "unicode-width", + "vec_map", +] + +[[package]] +name = "colored" +version = "1.9.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f4ffc801dacf156c5854b9df4f425a626539c3a6ef7893cc0c5084a23f0b6c59" +dependencies = [ + "atty", + "lazy_static", + "winapi", +] + +[[package]] +name = "either" +version = "1.5.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bb1f6b1ce1c140482ea30ddd3335fc0024ac7ee112895426e0a629a6c20adfe3" + +[[package]] +name = "fixedbitset" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "37ab347416e802de484e4d03c7316c48f1ecb56574dfd4a46a80f173ce1de04d" + +[[package]] +name = "heck" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "20564e78d53d2bb135c343b3f47714a56af2061f1c928fdb541dc7b9fdd94205" +dependencies = [ + "unicode-segmentation", +] + +[[package]] +name = "hermit-abi" +version = "0.1.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8a0d737e0f947a1864e93d33fdef4af8445a00d1ed8dc0c8ddb73139ea6abf15" +dependencies = [ + "libc", +] + +[[package]] +name = "indexmap" +version = "1.3.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "076f042c5b7b98f31d205f1249267e12a6518c1481e9dae9764af19b707d2292" +dependencies = [ + "autocfg", +] + +[[package]] +name = "itertools" +version = "0.8.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f56a2d0bc861f9165be4eb3442afd3c236d8a98afd426f65d92324ae1091a484" +dependencies = [ + "either", +] + +[[package]] +name = "itoa" +version = "0.4.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b8b7a7c0c47db5545ed3fef7468ee7bb5b74691498139e4b3f6a20685dc6dd8e" + +[[package]] +name = "lazy_static" +version = "1.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646" + +[[package]] +name = "libc" +version = "0.2.69" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "99e85c08494b21a9054e7fe1374a732aeadaff3980b6990b94bfd3a70f690005" + +[[package]] +name = "num-traits" +version = "0.2.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c62be47e61d1842b9170f0fdeec8eba98e60e90e5446449a0545e5152acd7096" +dependencies = [ + "autocfg", +] + +[[package]] +name = "pathfinding" +version = "2.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "86f4d8cc85ca67860ef4324faf86973a39e4e1c78338987eda29a8e6b6ec0c0e" +dependencies = [ + "fixedbitset", + "indexmap", + "itertools", + "num-traits", +] + +[[package]] +name = "proc-macro-error" +version = "1.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "98e9e4b82e0ef281812565ea4751049f1bdcdfccda7d3f459f2e138a40c08678" +dependencies = [ + "proc-macro-error-attr", + "proc-macro2", + "quote", + "syn", + "version_check", +] + +[[package]] +name = "proc-macro-error-attr" +version = "1.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4f5444ead4e9935abd7f27dc51f7e852a0569ac888096d5ec2499470794e2e53" +dependencies = [ + "proc-macro2", + "quote", + "syn", + "syn-mid", + "version_check", +] + +[[package]] +name = "proc-macro2" +version = "1.0.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "df246d292ff63439fea9bc8c0a270bed0e390d5ebd4db4ba15aba81111b5abe3" +dependencies = [ + "unicode-xid", +] + +[[package]] +name = "quote" +version = "1.0.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2bdc6c187c65bca4260c9011c9e3132efe4909da44726bad24cf7572ae338d7f" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "ryu" +version = "1.0.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "535622e6be132bccd223f4bb2b8ac8d53cda3c7a6394944d3b2b33fb974f9d76" + +[[package]] +name = "serde" +version = "1.0.106" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "36df6ac6412072f67cf767ebbde4133a5b2e88e76dc6187fa7104cd16f783399" +dependencies = [ + "serde_derive", +] + +[[package]] +name = "serde_derive" +version = "1.0.106" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9e549e3abf4fb8621bd1609f11dfc9f5e50320802273b12f3811a67e6716ea6c" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "serde_json" +version = "1.0.51" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "da07b57ee2623368351e9a0488bb0b261322a15a6e0ae53e243cbdc0f4208da9" +dependencies = [ + "itoa", + "ryu", + "serde", +] + +[[package]] +name = "serde_repr" +version = "0.1.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "cd02c7587ec314570041b2754829f84d873ced14a96d1fd1823531e11db40573" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "strsim" +version = "0.8.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8ea5119cdb4c55b55d432abb513a0429384878c15dde60cc77b1c99de1a95a6a" + +[[package]] +name = "structopt" +version = "0.3.13" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ff6da2e8d107dfd7b74df5ef4d205c6aebee0706c647f6bc6a2d5789905c00fb" +dependencies = [ + "clap", + "lazy_static", + "structopt-derive", +] + +[[package]] +name = "structopt-derive" +version = "0.4.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a489c87c08fbaf12e386665109dd13470dcc9c4583ea3e10dd2b4523e5ebd9ac" +dependencies = [ + "heck", + "proc-macro-error", + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "syn" +version = "1.0.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0df0eb663f387145cab623dea85b09c2c5b4b0aef44e945d928e682fce71bb03" +dependencies = [ + "proc-macro2", + "quote", + "unicode-xid", +] + +[[package]] +name = "syn-mid" +version = "0.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7be3539f6c128a931cf19dcee741c1af532c7fd387baa739c03dd2e96479338a" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "textwrap" +version = "0.11.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d326610f408c7a4eb6f51c37c330e496b08506c9457c9d34287ecc38809fb060" +dependencies = [ + "unicode-width", +] + +[[package]] +name = "unicode-segmentation" +version = "1.6.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e83e153d1053cbb5a118eeff7fd5be06ed99153f00dbcd8ae310c5fb2b22edc0" + +[[package]] +name = "unicode-width" +version = "0.1.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "caaa9d531767d1ff2150b9332433f32a24622147e5ebb1f26409d5da67afd479" + +[[package]] +name = "unicode-xid" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "826e7639553986605ec5979c7dd957c7895e93eabed50ab2ffa7f6128a75097c" + +[[package]] +name = "vec_map" +version = "0.8.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "05c78687fb1a80548ae3250346c3db86a80a7cdd77bda190189f2d0a0987c81a" + +[[package]] +name = "version_check" +version = "0.9.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "078775d0255232fb988e6fccf26ddc9d1ac274299aaedcedce21c6f72cc533ce" + +[[package]] +name = "vroomba" +version = "0.1.0" +dependencies = [ + "anyhow", + "serde", + "serde_json", + "serde_repr", +] + +[[package]] +name = "vroomba_analysis" +version = "0.1.0" +dependencies = [ + "anyhow", + "colored", + "pathfinding", + "structopt", + "vroomba", +] + +[[package]] +name = "winapi" +version = "0.3.8" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8093091eeb260906a183e6ae1abdba2ef5ef2257a21801128899c3fc699229c6" +dependencies = [ + "winapi-i686-pc-windows-gnu", + "winapi-x86_64-pc-windows-gnu", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" diff --git a/2020-overdrive/vroomba-analysis/Cargo.toml b/2020-overdrive/vroomba-analysis/Cargo.toml new file mode 100644 index 0000000..b39c01e --- /dev/null +++ b/2020-overdrive/vroomba-analysis/Cargo.toml @@ -0,0 +1,11 @@ +[package] +name = "vroomba_analysis" +version = "0.1.0" +edition = "2018" + +[dependencies] +anyhow = "1.0.27" +vroomba = { path = "../" } +pathfinding = "2.0.4" +structopt = "0.3" +colored = "1.9" diff --git a/2020-overdrive/vroomba-analysis/src/main.rs b/2020-overdrive/vroomba-analysis/src/main.rs new file mode 100644 index 0000000..994e021 --- /dev/null +++ b/2020-overdrive/vroomba-analysis/src/main.rs @@ -0,0 +1,182 @@ +use colored::*; +use pathfinding::prelude::*; +use std::path::PathBuf; +use structopt::StructOpt; +use vroomba::command::Command; +use vroomba::consts::*; +use vroomba::global_json; +use vroomba::state::*; + +#[derive(StructOpt, Debug)] +#[structopt(name = "vroomba-analysis")] +struct Opt { + /// Find out if there's a shorter path that uses the decelerate move + #[structopt(long)] + decelerate_experiment: bool, + /// Find out if there's a shorter path that uses the nothing move (instead of accelerate) + #[structopt(long)] + nothing_experiment: bool, + /// Path to GlobalState.json + path: PathBuf, +} + +fn main() { + let opt = Opt::from_args(); + let initial_state = + global_json::read_initial_state_from_global_json_file(opt.path.to_str().unwrap()).unwrap(); + + if opt.decelerate_experiment { + let shortest_path_with_decelerate = shortest_path(&initial_state, &[]); + let shortest_path_without_decelerate = + shortest_path(&initial_state, &[Command::Decelerate]); + println!("With Decelerate"); + log_shortest_path(&initial_state, &shortest_path_with_decelerate); + println!("Without Decelerate"); + log_shortest_path(&initial_state, &shortest_path_without_decelerate); + if shortest_path_with_decelerate.len() < shortest_path_without_decelerate.len() { + println!("With decelerate is faster!"); + } else { + println!("Same length!"); + } + } + if opt.nothing_experiment { + let shortest_path_with = shortest_path(&initial_state, &[]); + let shortest_path_without = shortest_path(&initial_state, &[Command::Nothing]); + println!("With Nothing"); + log_shortest_path(&initial_state, &shortest_path_with); + println!("Without Nothing"); + log_shortest_path(&initial_state, &shortest_path_without); + if shortest_path_with.len() < shortest_path_without.len() { + println!("With nothing is faster!"); + } else { + println!("Same length!"); + } + } else { + let shortest_path_actions = shortest_path(&initial_state, &[]); + log_shortest_path(&initial_state, &shortest_path_actions); + } +} + +fn shortest_path( + initial_state: &GameState, + blacklist: &[Command], +) -> Vec<(Position, Position, GameState, GameState, Command)> { + let shortest_path_states = astar( + initial_state, + |state| { + state + .valid_moves(0) + .into_iter() + .filter(|player_move| { + *player_move != Command::UseOil && !blacklist.contains(player_move) + }) + .map(|player_move| { + let mut state = state.clone(); + state.update([player_move, Command::Decelerate]); + (state, 1) + }) + .collect::<Vec<_>>() + }, + |state| (WIDTH - state.players[0].position.x) / SPEED_BOOST, + |state| state.status != GameStatus::Continue, + ) + .unwrap(); + + shortest_path_states + .0 + .iter() + .zip(shortest_path_states.0.iter().skip(1)) + .map(|(state, next)| { + let player = &state.players[0]; + let player_move = state + .valid_moves(0) + .into_iter() + .filter(|player_move| { + *player_move != Command::UseOil && !blacklist.contains(player_move) + }) + .find(|player_move| { + let mut state = state.clone(); + state.update([*player_move, Command::Decelerate]); + state == *next + }) + .unwrap(); + ( + player.position, + next.players[0].position, + state.clone(), + next.clone(), + player_move, + ) + }) + .collect() +} + +fn log_shortest_path( + initial_state: &GameState, + shortest_path_actions: &Vec<(Position, Position, GameState, GameState, Command)>, +) { + let chunk_size = 100; + for chunk in 0..(WIDTH / chunk_size) { + let start_x = chunk * chunk_size; + for i in 0..chunk_size / 10 { + print!("{:<10}", start_x + i * 10); + } + println!(); + for y in MIN_Y..MAX_Y { + for x in start_x..start_x + chunk_size { + let pos = Position { y, x }; + + let c = if initial_state.muds.contains(&pos) { + "O" + } else if initial_state.powerup_boosts.contains(&pos) { + ">" + } else if x == WIDTH { + "|" + } else { + "-" + }; + + let player_on_block = shortest_path_actions + .iter() + .find(|(position, _, _, _, _)| *position == pos); + let c_with_background = match player_on_block { + None => c.black(), + Some((_, _, _, _, Command::Accelerate)) => c.on_red(), + Some((_, _, _, _, Command::Decelerate)) => c.on_green(), + Some((_, _, _, _, Command::UseBoost)) => c.on_blue(), + Some(_) => c.on_yellow(), + }; + + let speed = shortest_path_actions + .iter() + .find(|(position, next_position, _, _, _)| { + position.x < x && x < next_position.x && y == next_position.y + }) + .map(|(_, _, _, next_state, _)| next_state.players[0].speed); + + let c_with_foreground = match speed { + None => c_with_background.white(), + Some(SPEED_0) | Some(SPEED_1) => c_with_background.green(), + Some(SPEED_2) => c_with_background.yellow(), + Some(SPEED_3) => c_with_background.red(), + Some(SPEED_4) => c_with_background.bright_red(), + Some(SPEED_BOOST) => c_with_background.blue(), + Some(_) => c_with_background.yellow(), + }; + + print!("{}", c_with_foreground); + } + println!(); + } + } + + for (i, (position, _, state, _, player_move)) in shortest_path_actions.iter().enumerate() { + let player = &state.players[0]; + println!( + "{:3}: x: {:4}, y: {:1}, speed: {:2}: {}", + i, position.x, position.y, player.speed, player_move + ); + } + + println!("{} moves", shortest_path_actions.len()); +} |