emirikol · May 2, 2024 08:46 · May 2, 2024 · May 2, 2024 · May 1, 2024
diff --git a/Cargo.toml b/Cargo.toml
@@ -0,0 +1,22 @@
+[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"
diff --git a/coin game → main.rs b/coin game → main.rs
@@ -1,3 +1,4 @@
+// build with `cargo build --profile=dist` then run `target/dist/game`
 use std::collections::HashMap;
 use std::time::Instant;
 

diff --git a/coin game b/coin game
@@ -59,34 +59,42 @@ fn combine(a: (&Subpart, u128), b: (&Subpart, u128)) -> (Subpart, u128) {
     }, value1 * value2)
 }
 
+struct CartesianProduct<T: Clone> {
+    vec: Vec<T>,
+    indices: Vec<usize>,
+    first: bool,
+}
 
-fn cartesian_product<T: Clone>(vec: &Vec<T>, n: usize) -> Vec<Vec<T>> {
-    let mut result = vec![];
-
-    let mut indices = vec![0; n];
-    let len = vec.len();
+impl<T: Clone> Iterator for CartesianProduct<T> {
+    type Item = Vec<T>;
 
-    loop {
-        let mut product = vec![];
-        for &i in &indices {
-            product.push(vec[i].clone());
+    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());
         }
-        result.push(product);
 
-        let mut carry = 1;
+        let n = self.indices.len();
+        let len = self.vec.len();
+
         for i in (0..n).rev() {
-            if indices[i] + carry >= len {
-                if i == 0 {
-                    return result;
-                }
-                indices[i] = 0;
-                carry = 1;
+            if self.indices[i] + 1 < len {
+                self.indices[i] += 1;
+                return Some(self.indices.iter().map(|&i| self.vec[i].clone()).collect());
             } else {
-                indices[i] += carry;
-                // carry = 0;
-                break;
+                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,
     }
 }
 
@@ -95,7 +103,7 @@ fn combine_subparts(subparts: &HashMap<Subpart, u128>, subpart_count: usize) ->
     let subpart_vec: Vec<(&Subpart, &u128)> = subparts.iter().collect();
 
 
-    cartesian_product(&subpart_vec, subpart_count).iter().for_each(|combination| {
+    for combination in cartesian_product(subpart_vec, subpart_count) {
         let (combined_subpart, combined_value) = combination.iter().fold(
             None,
             |acc, item| {
@@ -112,10 +120,9 @@ fn combine_subparts(subparts: &HashMap<Subpart, u128>, subpart_count: usize) ->
                 }
             },
         ).unwrap();
-
         *combined_subparts.entry(combined_subpart).or_insert(0) += combined_value;
 
-    });
+    };
 
     combined_subparts
 }

diff --git a/coin game b/coin game
@@ -0,0 +1,168 @@
+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)
+}
+
+
+fn cartesian_product<T: Clone>(vec: &Vec<T>, n: usize) -> Vec<Vec<T>> {
+    let mut result = vec![];
+
+    let mut indices = vec![0; n];
+    let len = vec.len();
+
+    loop {
+        let mut product = vec![];
+        for &i in &indices {
+            product.push(vec[i].clone());
+        }
+        result.push(product);
+
+        let mut carry = 1;
+        for i in (0..n).rev() {
+            if indices[i] + carry >= len {
+                if i == 0 {
+                    return result;
+                }
+                indices[i] = 0;
+                carry = 1;
+            } else {
+                indices[i] += carry;
+                // carry = 0;
+                break;
+            }
+        }
+    }
+}
+
+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();
+
+
+    cartesian_product(&subpart_vec, subpart_count).iter().for_each(|combination| {
+        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);
+}
No results found