Daily Challenge #311 - Connect the Letters

#challenge

Write a function which accepts a string consisting only of A, B, X and Y, and returns a maximum number of possible pairwise connection that can be made.

Here's the catch -- you need to follow the rules below:

You can connect A with B or B with A or X with Y or Y with X.
Each letter can participate in such connection only once.
Connections must all be done in the same direction.
Connections must not intersect.

Example

B X A B A Y B A
  | |_|   | |_|
  |_______|

No matter how you connect A to B and X to Y (without intersecting), you will only be able to make three connections in this example, so the answer for connect(BXABAYBA) is 3.

Tests

connect("BXABAYBA")
connect("AAAAAAAA")
connect("ABABABAB")
connect("BABBYYAYAAB")

This challenge comes from smiks on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (1)

Mihail Malo • Jan 22 '21 • Edited

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()));
    }
}