Last active
May 2, 2024 08:46
-
-
Save emirikol/f6f75a291b2881a454e5682b34ce7d41 to your computer and use it in GitHub Desktop.
coin game
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
[package] | |
name = "ant" | |
version = "0.1.0" | |
edition = "2021" | |
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html | |
[dependencies] | |
[[bin]] | |
name = "game" | |
path = "main.rs" | |
[profile.dist] | |
inherits = "release" | |
opt-level = 3 | |
debug = false | |
strip = "none" | |
lto = true | |
codegen-units = 1 | |
incremental = false | |
panic = "abort" |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// build with `cargo build --profile=dist` then run `target/dist/game` | |
use std::collections::HashMap; | |
use std::time::Instant; | |
#[derive(PartialEq, Eq, Hash, Copy, Clone)] | |
struct Subpart { | |
ascore: u32, | |
bscore: u32, | |
ends_with_eagle: bool, | |
starts_with_eagle: bool, | |
} | |
fn generate_unique_subparts(subpart_size: usize) -> HashMap<Subpart, u128> { | |
let mut subpart_counts = HashMap::new(); | |
let subparts_num = (1 << subpart_size) as u128; | |
for i in 0..subparts_num { | |
let bits = i as u128; | |
let ascore = (i & (i >> 1)).count_ones() as u32; | |
let bscore = (i&((!i & (subparts_num-1))>>1)).count_ones() as u32; | |
let ends_with_eagle = (bits & (1 << (subpart_size - 1))) != 0; | |
let starts_with_eagle = (bits & 1) == 1; | |
let subpart = Subpart { | |
ascore, | |
bscore, | |
ends_with_eagle, | |
starts_with_eagle | |
}; | |
*subpart_counts.entry(subpart).or_insert(0) += 1; | |
} | |
subpart_counts | |
} | |
fn combine(a: (&Subpart, u128), b: (&Subpart, u128)) -> (Subpart, u128) { | |
let (subpart1, value1) = a; | |
let (subpart2, value2) = b; | |
let mut ascore = subpart1.ascore + subpart2.ascore; | |
let mut bscore = subpart1.bscore + subpart2.bscore; | |
let starts_with_eagle = subpart1.starts_with_eagle; | |
let ends_with_eagle = subpart2.ends_with_eagle; | |
if subpart1.ends_with_eagle { | |
if subpart2.starts_with_eagle { | |
ascore += 1; | |
} else { | |
bscore += 1; | |
} | |
} | |
(Subpart { | |
ascore, | |
bscore, | |
starts_with_eagle, | |
ends_with_eagle | |
}, value1 * value2) | |
} | |
struct CartesianProduct<T: Clone> { | |
vec: Vec<T>, | |
indices: Vec<usize>, | |
first: bool, | |
} | |
impl<T: Clone> Iterator for CartesianProduct<T> { | |
type Item = Vec<T>; | |
fn next(&mut self) -> Option<Self::Item> { | |
if self.first { | |
self.first = false; | |
return Some(self.indices.iter().map(|&i| self.vec[i].clone()).collect()); | |
} | |
let n = self.indices.len(); | |
let len = self.vec.len(); | |
for i in (0..n).rev() { | |
if self.indices[i] + 1 < len { | |
self.indices[i] += 1; | |
return Some(self.indices.iter().map(|&i| self.vec[i].clone()).collect()); | |
} else { | |
self.indices[i] = 0; | |
} | |
} | |
None | |
} | |
} | |
fn cartesian_product<T: Clone>(vec: Vec<T>, n: usize) -> CartesianProduct<T> { | |
CartesianProduct { | |
vec, | |
indices: vec![0; n], | |
first: true, | |
} | |
} | |
fn combine_subparts(subparts: &HashMap<Subpart, u128>, subpart_count: usize) -> HashMap<Subpart, u128> { | |
let mut combined_subparts = HashMap::<Subpart, u128>::new(); | |
let subpart_vec: Vec<(&Subpart, &u128)> = subparts.iter().collect(); | |
for combination in cartesian_product(subpart_vec, subpart_count) { | |
let (combined_subpart, combined_value) = combination.iter().fold( | |
None, | |
|acc, item| { | |
match acc { | |
Some((accpart, accval)) => { | |
let (subpart, value) = *item; | |
let (new_subpart, new_value) = combine((&accpart, accval), (subpart, *value)); | |
Some((new_subpart, new_value)) | |
} | |
None => { | |
let (subpart, value) = *item; | |
Some((*subpart, *value)) | |
} | |
} | |
}, | |
).unwrap(); | |
*combined_subparts.entry(combined_subpart).or_insert(0) += combined_value; | |
}; | |
combined_subparts | |
} | |
fn count_wins(segments: &HashMap<Subpart, u128>) -> (u128, u128) { | |
let mut alice_wins = 0; | |
let mut bob_wins = 0; | |
for (segment, count) in segments { | |
if segment.ascore > segment.bscore { | |
alice_wins += count; | |
} else if segment.ascore < segment.bscore { | |
bob_wins += count; | |
} | |
} | |
(alice_wins, bob_wins) | |
} | |
fn count_wins_recursive(turns: usize) -> HashMap<Subpart, u128> { | |
let divisor = (2..=turns) | |
.find(|&d| turns % d == 0) | |
.unwrap(); | |
let subpart_size = turns / divisor; | |
if divisor == turns { | |
println!("generating base segment: {}", turns); | |
generate_unique_subparts(turns) | |
} else { | |
println!("subparts: size: {}, divisor: {}", subpart_size, divisor); | |
let subparts = count_wins_recursive(subpart_size); | |
println!("Number of unique subparts: {}", subparts.len()); | |
let combined = combine_subparts(&subparts, divisor); | |
println!("Number of combined subparts: {}", combined.len()); | |
println!("total number of subparts: {}", combined.values().sum::<u128>()); | |
combined | |
} | |
} | |
fn main() { | |
let turns = 100; | |
let start_time = Instant::now(); | |
let segments = count_wins_recursive(turns); | |
let (awins, bwins) = count_wins(&segments); | |
let duration = start_time.elapsed(); | |
println!("Execution time: {:?}", duration); | |
println!("Alice wins: {}", awins); | |
println!("Bob wins: {}", bwins); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment