25-10 rustHEADmaster

3 files changed, 231 insertions, 0 deletions

diff --git a/2025/10/rust/Cargo.lock b/2025/10/rust/Cargo.lock
new file mode 100644
index 0000000..fcb9609
--- /dev/null
+++ b/2025/10/rust/Cargo.lock
@@ -0,0 +1,155 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 4
+
+[[package]]
+name = "aoc_2025-10"
+version = "0.1.0"
+dependencies = [
+ "good_lp",
+ "itertools",
+]
+
+[[package]]
+name = "autocfg"
+version = "1.5.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c08606f8c3cbf4ce6ec8e28fb0014a2c086708fe954eaa885384a6165172e7e8"
+
+[[package]]
+name = "either"
+version = "1.15.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "48c757948c5ede0e46177b7add2e67155f70e33c07fea8284df6576da70b3719"
+
+[[package]]
+name = "fnv"
+version = "1.0.7"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3f9eec918d3f24069decb9af1554cad7c880e2da24a9afd88aca000531ab82c1"
+
+[[package]]
+name = "good_lp"
+version = "1.14.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "776aa1ba88ac058e78408c17f4dbff826a51ae08ed6642f71ca0edd7fe9383f3"
+dependencies = [
+ "fnv",
+ "microlp",
+]
+
+[[package]]
+name = "itertools"
+version = "0.14.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2b192c782037fadd9cfa75548310488aabdbf3d2da73885b31bd0abd03351285"
+dependencies = [
+ "either",
+]
+
+[[package]]
+name = "log"
+version = "0.4.28"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "34080505efa8e45a4b816c349525ebe327ceaa8559756f0356cba97ef3bf7432"
+
+[[package]]
+name = "matrixmultiply"
+version = "0.3.10"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a06de3016e9fae57a36fd14dba131fccf49f74b40b7fbdb472f96e361ec71a08"
+dependencies = [
+ "autocfg",
+ "rawpointer",
+]
+
+[[package]]
+name = "microlp"
+version = "0.2.11"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "51d1790c73b93164ff65868f63164497cb32339458a9297e17e212d91df62258"
+dependencies = [
+ "log",
+ "sprs",
+]
+
+[[package]]
+name = "ndarray"
+version = "0.16.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "882ed72dce9365842bf196bdeedf5055305f11fc8c03dee7bb0194a6cad34841"
+dependencies = [
+ "matrixmultiply",
+ "num-complex",
+ "num-integer",
+ "num-traits",
+ "portable-atomic",
+ "portable-atomic-util",
+ "rawpointer",
+]
+
+[[package]]
+name = "num-complex"
+version = "0.4.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "73f88a1307638156682bada9d7604135552957b7818057dcef22705b4d509495"
+dependencies = [
+ "num-traits",
+]
+
+[[package]]
+name = "num-integer"
+version = "0.1.46"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7969661fd2958a5cb096e56c8e1ad0444ac2bbcd0061bd28660485a44879858f"
+dependencies = [
+ "num-traits",
+]
+
+[[package]]
+name = "num-traits"
+version = "0.2.19"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "071dfc062690e90b734c0b2273ce72ad0ffa95f0c74596bc250dcfd960262841"
+dependencies = [
+ "autocfg",
+]
+
+[[package]]
+name = "portable-atomic"
+version = "1.11.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f84267b20a16ea918e43c6a88433c2d54fa145c92a811b5b047ccbe153674483"
+
+[[package]]
+name = "portable-atomic-util"
+version = "0.2.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d8a2f0d8d040d7848a709caf78912debcc3f33ee4b3cac47d73d1e1069e83507"
+dependencies = [
+ "portable-atomic",
+]
+
+[[package]]
+name = "rawpointer"
+version = "0.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "60a357793950651c4ed0f3f52338f53b2f809f32d83a07f72909fa13e4c6c1e3"
+
+[[package]]
+name = "smallvec"
+version = "1.15.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "67b1b7a3b5fe4f1376887184045fcf45c69e92af734b7aaddc05fb777b6fbd03"
+
+[[package]]
+name = "sprs"
+version = "0.11.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "6dca58a33be2188d4edc71534f8bafa826e787cc28ca1c47f31be3423f0d6e55"
+dependencies = [
+ "ndarray",
+ "num-complex",
+ "num-traits",
+ "smallvec",
+]
diff --git a/2025/10/rust/Cargo.toml b/2025/10/rust/Cargo.toml
new file mode 100644
index 0000000..20ee505
--- /dev/null
+++ b/2025/10/rust/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "aoc_2025-10"
+version = "0.1.0"
+edition = "2024"
+
+[dependencies]
+good_lp = { version = "1.14.2", features = ["microlp"], default-features = false }
+itertools = "0.14.0"
diff --git a/2025/10/rust/src/main.rs b/2025/10/rust/src/main.rs
new file mode 100644
index 0000000..b0cd6ed
--- /dev/null
+++ b/2025/10/rust/src/main.rs
@@ -0,0 +1,68 @@
+use good_lp::*;
+use itertools::Itertools;
+use std::io;
+
+fn main() {
+    let ms = io::stdin()
+        .lines()
+        .flatten()
+        .map(|line| {
+            let mut iter = line.split_whitespace();
+            let p1 = iter
+                .next()
+                .unwrap()
+                .chars()
+                .filter_map(|ch| match ch {
+                    '.' => Some(0),
+                    '#' => Some(1),
+                    _ => None,
+                })
+                .collect::<Vec<u32>>();
+
+            let mut iter = iter.map(|s| {
+                s.split(|ch: char| ch.is_ascii_punctuation())
+                    .filter_map(|n| n.parse().ok())
+                    .collect::<Vec<u32>>()
+            });
+            let p2 = iter.next_back().unwrap();
+            let bs = iter.collect::<Vec<_>>();
+            (p1, p2, bs)
+        })
+        .collect::<Vec<_>>();
+
+    let silver: usize = ms.iter().map(|(want, _, bs)| solve_p1(&want, &bs)).sum();
+    let gold: usize = ms.iter().map(|(_, want, bs)| solve_p2(&want, &bs)).sum();
+    println!("silver: {silver}");
+    println!("gold: {gold}");
+}
+
+fn solve_p1(want: &Vec<u32>, bs: &Vec<Vec<u32>>) -> usize {
+    bs.into_iter()
+        .powerset()
+        .map(|sub| (sub.len(), sub.into_iter().flatten().counts()))
+        .filter(|(_, counts)| {
+            want.iter()
+                .enumerate()
+                .all(|(n, w)| counts.get(&(n as u32)).unwrap_or(&0) % 2 == *w as usize)
+        })
+        .next()
+        .unwrap()
+        .0
+}
+
+fn solve_p2(want: &Vec<u32>, bs: &Vec<Vec<u32>>) -> usize {
+    variables! {vars: 0 <= xs[bs.len()] (integer);}
+    let obj: Expression = xs.iter().sum();
+    let mut model = vars.minimise(&obj).using(default_solver);
+    for (n, w) in want.iter().enumerate() {
+        let xsum: Expression = bs
+            .iter()
+            .enumerate()
+            .filter(|&(_, b)| b.contains(&(n as u32)))
+            .map(|(x, _)| xs[x])
+            .sum();
+        model = model.with(constraint!(xsum == *w));
+    }
+
+    model.solve().unwrap().eval(&obj).round() as usize
+}