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

andrealiao profile image

Build a Conversational Generative AI Assistant Using Amazon Q Business – A Step-by-Step Guide

Andrea Liao -

rudrabhardwaj profile image

TEST

RUDRA SHARMA -

trev_the_dev profile image

Is ChatGPT Losing Its Mind? The Curious Case of Declining LLM Performance

Treveshan Naidoo -

sadiq_mooo profile image

Introducing LightUp: AI-Powered Annotations for the Web

Moe Sadiq -