O(n) Fishbone

#!/usr/bin/env rustc

#![allow(dead_code)]

use std::fs::read_to_string;

const NULL: u8 = u8::MAX;

fn find_quality(line: Vec<u8>) -> u64 {
    let mut quality: u64 = 0;
    let mut spine: Vec<(u8, u8, u8)> = vec![];
    for &v in line.iter() {
        let mut placed = false;
        for s in &mut spine {
            if v < s.1 && s.0 == NULL {
                s.0 = v;
                placed = true;
                break;
            }
            else if v > s.1 && s.2 == NULL {
                s.2 = v;
                placed = true;
                break;
            }
        }
        if !placed {
            spine.push((NULL, v, NULL));
            quality = 10*quality + v as u64;
        }
    }
    quality

    // spine.iter()
    //     .map(|s| s.1.to_string())
    //     .collect::<String>()
    //     .parse::<u64>()
    //     .unwrap()
}

fn part1() {
    let q = read_to_string("in1.txt")
        .unwrap()
        .split_once(':')
        .unwrap()
        .1
        .split(',')
        .map(|s| s.parse::<u8>().unwrap())
        .collect();
    let ans = find_quality(q);
    println!("{ans}");
}

fn part2() {
    let mut q: Vec<u64> = read_to_string("in2.txt")
        .unwrap()
        .trim()
        .split('\n')
        .map(|line| {
            let vals = line.split_once(':')
                .unwrap()
                .1
                .split(',')
                .map(|s| s.parse::<u8>().unwrap())
                .collect();
            find_quality(vals)
        })
        .collect();
    q.sort_unstable();
    let ans = q[q.len() - 1] - q[0];
    println!("{ans}");
}

fn find_quality3(line: Vec<u8>) -> (u64, Vec<u64>) {
    let mut quality: u64 = 0;
    let mut spine: Vec<(u8, u8, u8)> = vec![];
    for &v in line.iter() {
        let mut placed = false;
        for s in &mut spine {
            if v < s.1 && s.0 == NULL {
                s.0 = v;
                placed = true;
                break;
            }
            else if v > s.1 && s.2 == NULL {
                s.2 = v;
                placed = true;
                break;
            }
        }
        if !placed {
            spine.push((NULL, v, NULL));
            quality = 10*quality + v as u64;
        }
    }

    let levels: Vec<u64> = spine
        .iter()
        .map(|s| {
            match s {
                &(NULL, v, NULL) => v as u64,
                &(u, v, NULL) => 10*u as u64 + v as u64,
                &(NULL, v, w) => 10*v as u64 + w as u64,
                &(u, v, w) => 100*u as u64 + 10*v as u64 + w as u64,
            }
        })
        .collect();
    (quality, levels)

    // let quality = spine
    //     .iter()
    //     .map(|s| s.1.to_string())
    //     .collect::<String>()
    //     .parse::<u64>()
    //     .unwrap();
    // let levels: Vec<u64> = spine
    //     .iter()
    //     .map(|s| {
    //         match s {
    //             (NULL, v, NULL) => format!("{}", v),
    //             (u, v, NULL) => format!("{}{}", u, v),
    //             (NULL, v, w) => format!("{}{}", v, w),
    //             (u, v, w) => format!("{}{}{}", u, v, w),
    //         }
    //         .parse::<u64>()
    //         .unwrap()
    //     })
    //     .collect();
}

fn read3(filename: &str) -> Vec<(u64, Vec<u8>)> {
    read_to_string(filename)
        .unwrap()
        .trim()
        .split('\n')
        .map(|line| {
            let (sid, svals) = line.split_once(':').unwrap();
            let id = sid.parse::<u64>().unwrap();
            let vals = svals
                .split(',')
                .map(|s| s.parse::<u8>().unwrap())
                .collect();
            (id, vals)
        })
        .collect()
}

fn part3() {
    let schemas = read3("in3.txt");
    let mut q: Vec<(u64, Vec<u64>, u64)> = schemas
        .into_iter()
        .map(|(id, line)| {
            let (x, y) = find_quality3(line);
            (x, y, id)
        })
        .collect();
    q.sort_unstable();
    q.reverse();
    let ans: u64 = (0..q.len())
        .map(|i| (i + 1) as u64 * q[i].2)
        .sum();
    println!("{ans}");
}

fn main() {
    part1();
    part2();
    part3();
}

// ChatGPT Below This Line //

// O(n) fishbone builder for values in 1..=9.
// Keeps 18 queues: L[1..=9] and R[1..=9] (we index them 0..=8 for convenience).
// Each queue is a doubly-linked list over spine indices, with O(1) push_back/pop_front/remove.

const DIGITS: usize = 9;
const K: usize = DIGITS * 2; // 18 queues: 0..8 = left[u], 9..17 = right[u]

#[inline] fn q_left(u: u8) -> usize  { (u as usize) - 1 }            // u in 1..=9
#[inline] fn q_right(u: u8) -> usize { DIGITS + (u as usize) - 1 }   // u in 1..=9

#[derive(Clone)]
struct Node {
    s: u8,                    // spine value (1..=9)
    left_free: bool,
    right_free: bool,
    // For each queue t in 0..K:
    prev: [Option<usize>; K],
    next: [Option<usize>; K],
    inq:  [bool; K],          // membership flag to avoid double-insert / stale remove
    // (Optional: store placed side values if you want the final full structure)
    left_val: Option<u8>,
    right_val: Option<u8>,
}

impl Node {
    fn new(s: u8) -> Self {
        Self {
            s, left_free: true, right_free: true,
            prev: [None; K], next: [None; K], inq: [false; K],
            left_val: None, right_val: None,
        }
    }
}

struct MultiQueues {
    head: [Option<usize>; K],
    tail: [Option<usize>; K],
}

impl MultiQueues {
    fn new() -> Self { Self { head: [None; K], tail: [None; K] } }

    // O(1) append to queue t
    fn push_back(&mut self, nodes: &mut [Node], t: usize, j: usize) {
        if nodes[j].inq[t] { return; }
        nodes[j].inq[t] = true;
        nodes[j].prev[t] = self.tail[t];
        nodes[j].next[t] = None;
        match self.tail[t] {
            Some(tail) => { nodes[tail].next[t] = Some(j); }
            None => { self.head[t] = Some(j); }
        }
        self.tail[t] = Some(j);
    }

    // O(1) remove arbitrary j from queue t (if present)
    fn remove(&mut self, nodes: &mut [Node], t: usize, j: usize) {
        if !nodes[j].inq[t] { return; }
        let p = nodes[j].prev[t];
        let n = nodes[j].next[t];

        match p {
            Some(pi) => nodes[pi].next[t] = n,
            None => self.head[t] = n,
        }
        match n {
            Some(ni) => nodes[ni].prev[t] = p,
            None => self.tail[t] = p,
        }
        nodes[j].prev[t] = None;
        nodes[j].next[t] = None;
        nodes[j].inq[t]  = false;
    }

    // O(1) pop front of queue t
    fn pop_front(&mut self, nodes: &mut [Node], t: usize) -> Option<usize> {
        let j = self.head[t]?;
        self.remove(nodes, t, j);
        Some(j)
    }

    // Just peek head (no mutation)
    fn peek_front(&self, _nodes: &[Node], t: usize) -> Option<usize> {
        self.head[t]
    }
}

// Build fishbone; returns spine nodes (with sides filled) and the concatenated spine number as u64.
fn build_fishbone(line: &[u8]) -> (Vec<Node>, u64) {
    let mut nodes: Vec<Node> = Vec::with_capacity(line.len());
    let mut qs = MultiQueues::new();

    for &v in line {
        debug_assert!((1..=9).contains(&v));

        // Try left bucket for v
        if let Some(j) = qs.peek_front(&nodes, q_left(v)) {
            // let j = qs.pop_front(&mut nodes, q_left(v)).unwrap();
            // Place v on left of node j
            debug_assert!(nodes[j].left_free && nodes[j].s > v);
            nodes[j].left_free = false;
            nodes[j].left_val = Some(v);

            // Remove j from ALL left buckets for u < s
            let s = nodes[j].s;
            for u in 1..s {
                qs.remove(&mut nodes, q_left(u), j);
            }
            // Right buckets remain valid (if right_free)
            continue;
        }

        // Try right bucket for v
        if let Some(j) = qs.peek_front(&nodes, q_right(v)) {
            // let j = qs.pop_front(&mut nodes, q_right(v)).unwrap();
            // Place v on right of node j
            debug_assert!(nodes[j].right_free && nodes[j].s < v);
            nodes[j].right_free = false;
            nodes[j].right_val = Some(v);

            // Remove j from ALL right buckets for u > s
            let s = nodes[j].s;
            for u in (s + 1)..=9 {
                qs.remove(&mut nodes, q_right(u), j);
            }
            // Left buckets remain valid (if left_free)
            continue;
        }

        // No slot found: create new spine segment
        let j = nodes.len();
        nodes.push(Node::new(v));

        // Register this index in all buckets it can serve (exactly 8 of them)
        // Left side accepts u < v
        for u in 1..v {
            qs.push_back(&mut nodes, q_left(u), j);
        }
        // Right side accepts u > v
        for u in (v + 1)..=9 {
            qs.push_back(&mut nodes, q_right(u), j);
        }
    }

    // Compute the "quality" as concatenated spine digits (like the event’s scoring)
    let mut q: u64 = 0;
    for n in &nodes {
        q = q * 10 + (n.s as u64);
    }
    (nodes, q)
}

// --- Example / quick check ---
#[cfg(test)]
mod tests {
    use super::build_fishbone;

    const NULL: u8 = u8::MAX;

    fn oracle(line: &[u8]) -> u64 {
        let mut quality: u64 = 0;
        let mut spine: Vec<(u8, u8, u8)> = vec![];
        for &v in line.iter() {
            let mut placed = false;
            for s in &mut spine {
                if v < s.1 && s.0 == NULL {
                    s.0 = v;
                    placed = true;
                    break;
                }
                else if v > s.1 && s.2 == NULL {
                    s.2 = v;
                    placed = true;
                    break;
                }
            }
            if !placed {
                spine.push((NULL, v, NULL));
                quality = 10*quality + v as u64;
            }
        }
        quality
    }

    fn rng(seed: &mut u64) -> u64 {
        if *seed == 0 { *seed = 0xCAFE_BEEF_FADE_4321; }
        let mut x = *seed;
        x ^= x >> 7;
        x ^= x << 25;
        x ^= x >> 27;
        *seed = x;
        x.wrapping_mul(0xDEAD_FEED_5432_5433)
    }

    #[test]
    fn rand_tests() {
        for mut seed in (3..1_000_007).step_by(107) {
            let len = rng(&mut seed) as usize % 20 + 1;
            let mut line = Vec::with_capacity(len);
            for _ in 0..len {
                let v = (rng(&mut seed) % 9) as u8 + 1;
                line.push(v);
            }
            let want = oracle(&line);
            let got = build_fishbone(&line).1;
            assert_eq!(got, want);
        }
    }

    #[test]
    fn monotone_increasing_creates_single_spine() {
        let line = [1,2,3,4,5,6,7,8,9];
        let (nodes, q) = build_fishbone(&line);
        assert_eq!(nodes.len(), 5);
        assert_eq!(q, 13579);
    }

    #[test]
    fn ec_demo() {
        let line = [5,3,7,8,9,9,4,5,7,8,8];
        let q = build_fishbone(&line).1;
        assert_eq!(q, 58978);
    }
}