Discussion on: Daily Challenge #311 - Connect the Letters

View post

Rust

A brute force approach, by recursing and treating the three parts each "bracket" splits the input into as separate inputs (since they can never interact).
A lot of typical optimizations could be possible, such as memoizing on range, or memoizing on pattern (and compressing the pattern to 2 characters per byte for the hash), but this might be slower.
However, a better optimization would be based on some topological insight, for example that we don't need to ever pick a smaller bracket if that doesn't release a different (or keep track of necessary?) letter to the outside.
(eg. AXABYYB doesn't need to be aXabYyb, only aXabyYb, AXABYXYB doesn't need to be aXabYxyb, only aXabyxYb (yx can now match inside, in mid part))
Or some other observation of the sort.

#![feature(format_args_capture)]
fn dig(r: &[u8]) -> Result<usize, ()> {
    let mut num = 0;
    // take one letter at a time
    for (left, l) in r.iter().enumerate() {
        // recurse on left
        let left_max = dig(&r[..left])?;
        let rest = &r[left + 1..];
        // get matching letter
        let matched = match l {
            b'A' => b'B',
            b'B' => b'A',
            b'X' => b'Y',
            b'Y' => b'X',
            _ => return Err(()),
        };
        let mut mid_max = usize::MAX;
        // get indexes of matching letter in `rest`
        for right in rest
            .iter()
            .enumerate()
            .rev()
            .filter_map(|(i, &x)| (x == matched).then(|| i))
        {
            // if it was previously zero, it's still zero after shrinking
            // honestly a questionable optimization, since it can cause branching
            mid_max = if mid_max != 0 {
                dig(&rest[..right])?
            } else {
                0
            };
            let end_max = dig(&rest[right + 1..])?;
            let num2 = 1 + left_max + mid_max + end_max;
            if num2 > num {
                num = num2;
            }
        }
    }
    Ok(num)
}
fn main() {
    for s in &[
        "AAXXXBBYYY",
        "BXABAYBA",
        "AAAAAAAA",
        "ABABABAB",
        "BABBYYAYAAB",
        "error",
    ] {
        println!("{s} -> {:?}", dig(s.as_bytes()));
    }
}

Look at it go!

only recurse on the prefix when prefix size changes
only determine matching letter once per prefix move
work directly with passed in string, without "parsing" into enum
a questionable optimization to stop recursing on the mid slice if it's always 0

Version history:

Ver 1

no iterating one "left letter" at a time
use Iterator::max for inner iterator

Initial