coin game

Cargo.toml

[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"

main.rs

// 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);
}