Click to change color scheme

Notes on codes, projects and everything

Learning a new language for more than 2 months (feat. Exercism)

Bracket push

In short this exercise is to check if the brackets are balanced. Nothing too major here, but my mentor told me apparently the code generated by Rust deals with recursion is good enough. There seems to be some TCO in place, though I don’t really care. I usually swap recursion code back to normal loop only when necessary (after I blow up the stack).

pub struct Brackets(Vec<char>);

impl<'a> From<&'a str> for Brackets {
    fn from(input: &str) -> Self {
        Brackets(
            input
                .chars()
                .filter(|x| vec!['{', '}', '[', ']', '(', ')'].contains(x))
                .collect::<Vec<char>>(),
        )
    }
}

impl Brackets {
    pub fn are_balanced(&self) -> bool {
        Self::balance_test(true, &[], &self.0[..])
    }

    fn balance_test(result: bool, stack: &[char], brackets: &[char]) -> bool {
        match (stack.first(), brackets.first()) {
            (Some(o), Some(c)) if [('{', '}'), ('[', ']'), ('(', ')')].contains(&(*o, *c)) => {
                Self::balance_test(result, &stack[1..], &brackets[1..])
            }
            (_, Some(n)) if ['}', ')', ']'].contains(n) => false,
            (_, Some(n)) => Self::balance_test(
                result,
                &vec![vec![*n], stack.to_vec()].concat().as_slice(),
                &brackets[1..],
            ),
            (_, None) => result && stack.len() == 0,
        }
    }
}

However, the notable part of this exercise is that I was told about the rpds crate. This is an awesome crate for functional people I suppose because it doesn’t really do mutation in place, which gave me a lot of headache. Knowing Rust mutates stuff in a safe way is one thing, but wanting something that is done differently to completely eliminate mutation in place is another.

Unfortunately the use of that crate seems to slightly impact performance.

Sublist

Again, a rather clumsy submission in the beginning.

#[derive(Debug, PartialEq)]
pub enum Comparison {
    Equal,
    Unequal,
    Sublist,
    Superlist,
}

pub fn sublist<T: PartialEq>(alpha: &[T], beta: &[T]) -> Comparison {
    match (alpha.len(), beta.len()) {
        (a, b) if a < b => is_sublist(&alpha, &beta),
        (a, b) if a > b => is_superlist(&alpha, &beta),
        _ => is_equal(&alpha, &beta),
    }
}

fn is_sublist<T: PartialEq>(alpha: &[T], beta: &[T]) -> Comparison {
    if alpha.len() == 0 {
        return Comparison::Sublist;
    }

    let _result = (0..(1 + beta.len() - alpha.len()))
        .any(|idx_start| alpha == &beta[idx_start..(idx_start + alpha.len())]);

    match _result {
        true => Comparison::Sublist,
        false => Comparison::Unequal,
    }
}

fn is_superlist<T: PartialEq>(alpha: &[T], beta: &[T]) -> Comparison {
    match is_sublist(&beta, &alpha) {
        Comparison::Sublist => Comparison::Superlist,
        _result => _result,
    }
}

fn is_equal<T: PartialEq>(alpha: &[T], beta: &[T]) -> Comparison {
    match alpha == beta {
        true => Comparison::Equal,
        false => Comparison::Unequal,
    }
}

One of the problem is that I abuse match statement everywhere that it really should be written as an if statement. Also through the review conversation I was also told about the window method so I could rely on it instead of calculating the sublist indices myself.

#[derive(Debug, PartialEq)]
pub enum Comparison {
    Equal,
    Unequal,
    Sublist,
    Superlist,
}

pub fn sublist<T: PartialEq>(alpha: &[T], beta: &[T]) -> Comparison {
    if is_sublist(&alpha, &beta) {
        Comparison::Sublist
    } else if is_sublist(&beta, &alpha) {
        Comparison::Superlist
    } else if alpha == beta {
        Comparison::Equal
    } else {
        Comparison::Unequal
    }
}

fn is_sublist<T: PartialEq>(alpha: &[T], beta: &[T]) -> bool {
    alpha.len() < beta.len()
        && (alpha.len() == 0 || beta.windows(alpha.len()).any(|window| window == alpha))
}

There seems to be a lot of quality-of-life kind of method calls in Rust (which makes it a fun language to learn) that I always overlooked. While the doumentation takes me some time to get used to, but methods like window, flat_map are not things I would look for in the documentation (which was why I usually ended up writing my own version).

At this stage, I am starting to get used to the borrow checker, and sometimes would get some intuition on how to fix the error by just reading the errors. The word use of ‘intuition’ here is deliberately chosen, because it sometimes becomes a reflex action whenever an error is shown, without thinking what causes it.

leave your comment

name is required

email is required

have a blog?

This blog uses scripts to assist and automate comment moderation, and the author of this blog post does not hold responsibility in the content of posted comments. Please note that activities such as flaming, ungrounded accusations as well as spamming will not be entertained.