DEV Community

dev.to staff
dev.to staff

Posted on

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
  | |_|   | |_|
  |_______|
Enter fullscreen mode Exit fullscreen mode

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)

Collapse
 
qm3ster profile image
Mihail Malo • • 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()));
    }
}
Enter fullscreen mode Exit fullscreen mode

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

Read next

ehab7osam profile image

LeetCode in Golang: Parsing A Boolean Expression

Ehab Hosam -

i_am_vesh profile image

Understanding Microsoft Entra ID (Formerly Azure Active Directory) for the Azure Administration Certification Exam-Az 104

Avesh -

end3r profile image

Judging the first DEV Web Game Challenge

Andrzej Mazur -

jetthoughts-dev profile image

Why Your Form Submission Fails: Hotwire/Turbo 1.x, Cloudflare, and Missing Validation Messages

JetThoughts Dev -