From 081398053614b9f17dc0bce2dd46b4967cc75bb0 Mon Sep 17 00:00:00 2001
From: Jordan Doyle <jordan@doyle.la>
Date: Wed, 13 Dec 2023 10:59:13 +0000
Subject: [PATCH] Add day 12

---
 .gitignore   |   3 +++
 2023/12.rs   | 353 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2023/5.rs    |  13 +------------
 Cargo.lock   | 132 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 Cargo.toml   |  25 +++++++++++++++++++++++++
 rustfmt.toml |   7 +++++++
 6 files changed, 521 insertions(+), 12 deletions(-)
 create mode 100644 2023/12.rs
 create mode 100644 Cargo.lock
 create mode 100644 Cargo.toml
 create mode 100644 rustfmt.toml

diff --git a/.gitignore b/.gitignore
index ec8275a..fb14600 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,3 +1,6 @@
 result
 .tfstate
 .terraform
+target
+input
+out*
diff --git a/2023/12.rs b/2023/12.rs
new file mode 100644
index 0000000..122d022
--- /dev/null
+++ b/2023/12.rs
@@ -0,0 +1,353 @@
+use std::{
+    fs::File,
+    io::{Read, Write},
+    iter::once,
+    str::FromStr,
+    sync::{Arc, Condvar, Mutex},
+};
+
+use arrayvec::ArrayVec;
+use nom::{
+    branch::alt,
+    character::complete::{char, digit1},
+    combinator::{map, map_res},
+    multi::{many1, separated_list1},
+    sequence::separated_pair,
+    IResult,
+};
+
+fn main() {
+    let mut input = Vec::new();
+    std::io::stdin().lock().read_to_end(&mut input).unwrap();
+    let input = std::str::from_utf8(&input).unwrap();
+
+    let (rest, input) = parse_input(input).unwrap();
+    assert!(rest.is_empty());
+
+    part1(input.clone());
+    part2(input.clone());
+}
+
+fn part1(input: Vec<RawInput>) {
+    let lines = input.into_iter().map(Line::from).collect::<Vec<_>>();
+
+    let res = run(lines, "p1");
+    eprintln!("part 1: {res}");
+}
+
+fn part2(input: Vec<RawInput>) {
+    let lines = input
+        .into_iter()
+        .map(|mut line| {
+            line.kinds = (0..5)
+                .flat_map(|_| line.kinds.iter().copied().chain(once(Kind::Unknown)))
+                .collect();
+            line.kinds.remove(line.kinds.len() - 1);
+
+            line.damaged = line.damaged.repeat(5);
+            line
+        })
+        .map(Line::from)
+        .collect::<Vec<_>>();
+
+    eprintln!("part 2: {}", run(lines, "p2-test"));
+}
+
+fn run(line: Vec<Line>, suffix: &str) -> u64 {
+    let mut out_file = File::options()
+        .read(true)
+        .create(true)
+        .append(true)
+        .open(format!("out-{suffix}"))
+        .unwrap();
+
+    let mut seen = String::new();
+    out_file.read_to_string(&mut seen).unwrap();
+
+    let seen = seen
+        .lines()
+        .filter_map(|v| v.split_once(','))
+        .map(|(idx, _)| usize::from_str(idx).unwrap())
+        .collect::<Vec<_>>();
+    eprintln!("recovered state - completed {seen:?}");
+
+    let (completed_send, completed_recv) = std::sync::mpsc::channel();
+    let handle = std::thread::spawn(move || {
+        while let Ok((i, c)) = completed_recv.recv() {
+            writeln!(out_file, "{i},{c}").unwrap();
+        }
+
+        eprintln!("shutdown");
+    });
+
+    let mut processing_handles = vec![];
+
+    let parallelism = std::thread::available_parallelism().unwrap().get();
+    eprintln!(
+        "using {parallelism} threads to process {}/{} tasks",
+        line.len() - seen.len(),
+        line.len()
+    );
+
+    let completed_count = Arc::new((Mutex::new(0_usize), Condvar::new()));
+
+    for (i, mut line) in line.into_iter().enumerate() {
+        if seen.contains(&i) {
+            continue;
+        }
+
+        {
+            let mut val = completed_count
+                .1
+                .wait_while(completed_count.0.lock().unwrap(), |count| {
+                    *count >= parallelism
+                })
+                .unwrap();
+            *val += 1;
+        }
+
+        let completed_send = completed_send.clone();
+        let completed_count = completed_count.clone();
+        processing_handles.push(std::thread::spawn(move || {
+            let damaged_length: u32 = line.damaged.iter().map(|(_, v)| v).sum();
+            let output_length = 128 - (line.kinds | line.unknown).leading_zeros();
+
+            line.damaged.reverse();
+
+            eprintln!("processing {i}");
+
+            let res = process_new(
+                ConstInput {
+                    input: line.kinds,
+                    output_length: output_length - damaged_length + 2
+                        - u32::try_from(line.damaged.len()).unwrap(),
+                    expected_packed: line.damaged_packed,
+                    unwritable_area: !(line.kinds | line.unknown),
+                },
+                &line.damaged,
+                0,
+                0,
+                0,
+                0,
+            );
+
+            *completed_count.0.lock().unwrap() -= 1;
+            completed_count.1.notify_one();
+
+            completed_send.send((i, res)).unwrap();
+
+            eprintln!("{i} - {res}");
+
+            res
+        }));
+    }
+
+    drop(completed_send);
+
+    let mut acc = 0;
+    for h in processing_handles {
+        acc += h.join().unwrap();
+    }
+
+    handle.join().unwrap();
+
+    acc
+}
+
+#[derive(Copy, Clone)]
+pub struct ConstInput {
+    input: u128,
+    output_length: u32,
+    expected_packed: u128,
+    unwritable_area: u128,
+}
+
+/// Rather than bruteforcing the inputs against the outputs, we'll instead turn
+/// this into a bit-fitting issue on the outputs - we know the groups of 1s we
+/// need to fit (ie. `3, 2, 1`) we'll turn that expected output into `11101101`
+/// and see how many times we can increase the amount of zeros between the groups
+/// and have it not write outside of `(input | unknown)`.
+fn process_new(
+    c: ConstInput,
+    expected_list: &[(u128, u32)],
+    current: u128,
+    i: u32,
+    shift: u32,
+    mask: u32,
+) -> u64 {
+    // take the next group out of the list
+    let (mut expected_as_bits, current_length) = expected_list[0];
+    let expected_rest = &expected_list[1..];
+
+    // the group as bits, so if the input asks for a group of `3` operational
+    // gears, we'll have `111` in this, shifted by the previous groups and
+    // their zeros
+    expected_as_bits <<= shift;
+
+    let mut acc = 0_u64;
+
+    if expected_rest.is_empty() {
+        for zeros in 0_u32..(c.output_length - i) {
+            // write our new bits with offsetted zeros to the current value
+            let with_new_bits = c.input | current | (expected_as_bits << zeros);
+
+            if with_new_bits & c.unwritable_area == 0
+                && compress_zeros(with_new_bits) == c.expected_packed
+            {
+                acc += 1;
+            }
+        }
+    } else {
+        // the base shift we'll ask the next group to do, which is the shift we
+        // were asked to do, along with the length of our number, plus our reserved
+        // 0.
+        let next_shift = shift + current_length + 1;
+        let mask = mask + current_length;
+        let m = (1 << mask) - 1;
+
+        // a mask over the compressed zeros we will be writing to so we can chop
+        // branches if our current write doesn't match the bit pattern expected
+        let c_exp = c.expected_packed & m;
+
+        for zeros in 0_u32..(c.output_length - i) {
+            // push our group into the number followed by `zeros` zeros.
+            let with_new_bits = current | (expected_as_bits << zeros);
+
+            if with_new_bits & c.unwritable_area == 0
+                && (compress_zeros(c.input | with_new_bits) & m) == c_exp
+            {
+                // give the next group `zeros` less zeros along with our reserved 0
+                acc += process_new(
+                    c,
+                    expected_rest,
+                    with_new_bits,
+                    i + zeros,
+                    next_shift + zeros,
+                    mask + 1,
+                );
+            }
+        }
+    }
+
+    acc
+}
+
+/// Takes an input such as `11110001111001` and compresses successive zeros
+/// down to a single zero (ie. `11110111101`). This will let us compare our
+/// current solution (`input | current`) over the expected output.
+#[inline]
+fn compress_zeros(mut num: u128) -> u128 {
+    let mut result: u128 = 0;
+    let mut last_bit = true;
+    let mut idx: u8 = 0;
+
+    num >>= num.trailing_zeros();
+
+    while num > 0 {
+        let current_bit = num & 1;
+        let cbit_bool = current_bit != 0;
+
+        if cbit_bool {
+            result |= 1 << idx;
+            idx += 1;
+            num >>= 1;
+            last_bit = true;
+        } else if last_bit {
+            idx += 1;
+            last_bit = false;
+            num >>= num.trailing_zeros();
+        }
+    }
+
+    result
+}
+
+#[derive(Debug, Copy, Clone, PartialEq, Eq)]
+pub enum Kind {
+    Damaged,
+    Operational,
+    Unknown,
+}
+
+#[derive(Debug, Clone)]
+pub struct Line {
+    kinds: u128,
+    unknown: u128,
+    damaged_packed: u128,
+    damaged: ArrayVec<(u128, u32), 32>,
+}
+
+impl From<RawInput> for Line {
+    fn from(
+        RawInput {
+            kinds,
+            damaged: damaged_vec,
+        }: RawInput,
+    ) -> Self {
+        let (kinds, unknown) = kinds.into_iter().rev().enumerate().fold(
+            (0, 0),
+            |(kinds_acc, unknown_acc), (i, kind)| match kind {
+                Kind::Damaged => (kinds_acc | (1 << i), unknown_acc),
+                Kind::Operational => (kinds_acc, unknown_acc),
+                Kind::Unknown => (kinds_acc, unknown_acc | (1 << i)),
+            },
+        );
+
+        let mut damaged_packed = 0_u128;
+        for d in damaged_vec.clone() {
+            damaged_packed <<= d + 1;
+            damaged_packed |= (1 << d) - 1;
+        }
+
+        let damaged = damaged_vec
+            .into_iter()
+            .map(|v| ((1_u128 << v) - 1, ((1_u32 << v) - 1).trailing_ones()))
+            .collect();
+
+        Self {
+            kinds,
+            unknown,
+            damaged_packed,
+            damaged,
+        }
+    }
+}
+
+#[derive(Clone, Debug)]
+pub struct RawInput {
+    kinds: Vec<Kind>,
+    damaged: Vec<u8>,
+}
+
+impl From<(Vec<Kind>, Vec<u8>)> for RawInput {
+    fn from((kinds, damaged): (Vec<Kind>, Vec<u8>)) -> Self {
+        Self { kinds, damaged }
+    }
+}
+
+fn parse_input(rest: &str) -> IResult<&str, Vec<RawInput>> {
+    separated_list1(char('\n'), parse_line)(rest)
+}
+
+fn parse_line(rest: &str) -> IResult<&str, RawInput> {
+    map(
+        separated_pair(fold_chars, char(' '), parse_damaged),
+        RawInput::from,
+    )(rest)
+}
+
+fn fold_chars(rest: &str) -> IResult<&str, Vec<Kind>> {
+    many1(parse_char)(rest)
+}
+
+fn parse_char(rest: &str) -> IResult<&str, Kind> {
+    alt((
+        map(char('#'), |_| Kind::Damaged),
+        map(char('.'), |_| Kind::Operational),
+        map(char('?'), |_| Kind::Unknown),
+    ))(rest)
+}
+
+fn parse_damaged(rest: &str) -> IResult<&str, Vec<u8>> {
+    separated_list1(char(','), map_res(digit1, u8::from_str))(rest)
+}
diff --git a/2023/5.rs b/2023/5.rs
index 65839c4..a9327c9 100755
--- a/2023/5.rs
+++ b/2023/5.rs
@@ -1,19 +1,8 @@
-#!/usr/bin/env nix-shell
-//! ```cargo
-//! [dependencies]
-//! rangemap = "1.4"
-//! strum = { version = "0.25", features = ["derive"] }
-//! nom = "7"
-//! itertools = "0.12"
-//! ```
-/*
-#!nix-shell -i rust-script -p rustc -p rust-script -p cargo
-*/
+use std::{collections::HashMap, io::Read, ops::Range, str::FromStr, time::Instant};
 
 use itertools::Itertools;
 use nom::IResult;
 use rangemap::RangeMap;
-use std::{collections::HashMap, io::Read, ops::Range, str::FromStr, time::Instant};
 
 const TRANSLATION_PATH: &[MapKind] = &[
     MapKind::Soil,
diff --git a/Cargo.lock b/Cargo.lock
new file mode 100644
index 0000000..fbe92ee
--- /dev/null
+++ b/Cargo.lock
@@ -0,0 +1,132 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "aoc2023"
+version = "0.1.0"
+dependencies = [
+ "arrayvec",
+ "itertools",
+ "nom",
+ "rangemap",
+ "strum",
+]
+
+[[package]]
+name = "arrayvec"
+version = "0.7.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "96d30a06541fbafbc7f82ed10c06164cfbd2c401138f6addd8404629c4b16711"
+
+[[package]]
+name = "either"
+version = "1.9.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a26ae43d7bcc3b814de94796a5e736d4029efb0ee900c12e2d54c993ad1a1e07"
+
+[[package]]
+name = "heck"
+version = "0.4.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "95505c38b4572b2d910cecb0281560f54b440a19336cbbcb27bf6ce6adc6f5a8"
+
+[[package]]
+name = "itertools"
+version = "0.12.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "25db6b064527c5d482d0423354fcd07a89a2dfe07b67892e62411946db7f07b0"
+dependencies = [
+ "either",
+]
+
+[[package]]
+name = "memchr"
+version = "2.6.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f665ee40bc4a3c5590afb1e9677db74a508659dfd71e126420da8274909a0167"
+
+[[package]]
+name = "minimal-lexical"
+version = "0.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "68354c5c6bd36d73ff3feceb05efa59b6acb7626617f4962be322a825e61f79a"
+
+[[package]]
+name = "nom"
+version = "7.1.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d273983c5a657a70a3e8f2a01329822f3b8c8172b73826411a55751e404a0a4a"
+dependencies = [
+ "memchr",
+ "minimal-lexical",
+]
+
+[[package]]
+name = "proc-macro2"
+version = "1.0.70"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "39278fbbf5fb4f646ce651690877f89d1c5811a3d4acb27700c1cb3cdb78fd3b"
+dependencies = [
+ "unicode-ident",
+]
+
+[[package]]
+name = "quote"
+version = "1.0.33"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5267fca4496028628a95160fc423a33e8b2e6af8a5302579e322e4b520293cae"
+dependencies = [
+ "proc-macro2",
+]
+
+[[package]]
+name = "rangemap"
+version = "1.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "977b1e897f9d764566891689e642653e5ed90c6895106acd005eb4c1d0203991"
+
+[[package]]
+name = "rustversion"
+version = "1.0.14"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7ffc183a10b4478d04cbbbfc96d0873219d962dd5accaff2ffbd4ceb7df837f4"
+
+[[package]]
+name = "strum"
+version = "0.25.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "290d54ea6f91c969195bdbcd7442c8c2a2ba87da8bf60a7ee86a235d4bc1e125"
+dependencies = [
+ "strum_macros",
+]
+
+[[package]]
+name = "strum_macros"
+version = "0.25.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "23dc1fa9ac9c169a78ba62f0b841814b7abae11bdd047b9c58f893439e309ea0"
+dependencies = [
+ "heck",
+ "proc-macro2",
+ "quote",
+ "rustversion",
+ "syn",
+]
+
+[[package]]
+name = "syn"
+version = "2.0.40"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "13fa70a4ee923979ffb522cacce59d34421ebdea5625e1073c4326ef9d2dd42e"
+dependencies = [
+ "proc-macro2",
+ "quote",
+ "unicode-ident",
+]
+
+[[package]]
+name = "unicode-ident"
+version = "1.0.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b"
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..c4ce73e
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,25 @@
+[package]
+name = "aoc2023"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+arrayvec = "0.7"
+rangemap = "1.4"
+strum = { version = "0.25", features = ["derive"] }
+nom = "7"
+itertools = "0.12"
+
+[[bin]]
+name = "aoc2023-12"
+path = "2023/12.rs"
+
+[[bin]]
+name = "aoc2023-5"
+path = "2023/5.rs"
+
+[profile.release]
+overflow-checks = true
+
+[lints.clippy]
+pedantic = "deny"
diff --git a/rustfmt.toml b/rustfmt.toml
new file mode 100644
index 0000000..fd4d8a5
--- /dev/null
+++ b/rustfmt.toml
@@ -0,0 +1,7 @@
+edition = "2021"
+unstable_features = true
+imports_granularity = "Crate"
+group_imports = "StdExternalCrate"
+normalize_comments = true
+comment_width = 100
+wrap_comments = true
--
libgit2 1.7.2