🏡 index : ~doyle/aoc.git

author Jordan Doyle <jordan@doyle.la> 2023-12-13 10:59:13.0 +00:00:00
committer Jordan Doyle <jordan@doyle.la> 2023-12-17 2:58:35.0 +00:00:00
commit 
081398053614b9f17dc0bce2dd46b4967cc75bb0 [patch]
tree 
3880b9bea7e70c4038a47b3c13afe5e7021ba3c2
parent 
425176c84de4e1d6ce160a99933e8de19adad78f
download 
081398053614b9f17dc0bce2dd46b4967cc75bb0.tar.gz

Add day 12




Diff


 .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(-)

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