Experimenting with Rust

rnaa.rs

use std::cmp;

// Note: this is a suboptimal solution made to exercise the Rust language.

// Approach A: using a struct/class
// Gotcha: Had to add lifetime specifier to store a reference to the byte array of a external
// string inside my struct.

struct Rnaa<'a> {
    chain: &'a [u8], // 'a is to get rid of "missing lifetype specifier"
    chain_len: usize,
    stack: Vec<u8>,
}

impl<'a> Rnaa<'a> {
    fn new(chain: &'a str) -> Rnaa {
        let chain_b = chain.as_bytes();
        Rnaa {
            chain: chain_b,
            chain_len: chain_b.len(),
            stack: Vec::new(),
        }
    }

    fn inv(c: u8) -> u8 {
        (match c as char {
            'F' => 'C',
            'C' => 'F',
            'B' => 'S',
            'S' => 'B',
            _ => '?',
        }) as u32 as u8
    }

    fn can_fold(&self, c: u8) -> bool {
        match self.stack.last() {
            None => false,
            Some(head) => *head == Rnaa::inv(c),
        }
    }

    fn solve(&mut self, i: usize) -> usize {
        if i >= self.chain_len {
            return (self.chain_len - self.stack.len()) / 2;
        }
        let c = self.chain[i];
        let mut ret;
        if self.can_fold(c) {
            let temp = self.stack.pop().unwrap();
            ret = self.solve(i + 1);
            self.stack.push(temp);
        } else {
            ret = 0;
        }
        self.stack.push(c);
        ret = cmp::max(ret, self.solve(i + 1));
        self.stack.pop();

        return ret;
    }
}

pub fn solve(chain: &str) -> usize {
    return Rnaa::new(chain).solve(0);
}



// Approach B: using closures (and local variables)
// Gotchas:
//   1. Closures requires different syntax than inner functions:
//     error[E0434]: can't capture dynamic environment in a fn item; use the || { ... } closure form instead
//   2. Can't use the return keyword in closures.
//   3. Can't call your closure recursively (without ugly workaround)
//     https://stackoverflow.com/questions/16946888/is-it-possible-to-make-a-recursive-closure-in-rust
// Too many problems. Gave up.






// Approach C: using local variables with inner functions (passing stuff as arguments)

pub fn solve2(s: &str) -> usize {
    let chain = s.as_bytes();
    let mut stack = Vec::new();

    fn inv(c: u8) -> u8 {
        (match c as char {
            'F' => 'C',
            'C' => 'F',
            'B' => 'S',
            'S' => 'B',
            _ => '?',
        }) as u32 as u8
    }

    fn can_fold(stack: &Vec<u8>, c: u8) -> bool {
        match stack.last() {
            None => false,
            Some(head) => *head == inv(c),
        }
    }

    fn solve(i: usize, chain: &[u8], stack: &mut Vec<u8>) -> usize {
        let chain_len = chain.len();
        if i >= chain_len {
            return (chain_len - stack.len()) / 2;
        }
        let c = chain[i];
        let mut ret;
        if can_fold(stack, c) {
            let temp = stack.pop().unwrap();
            ret = solve(i + 1, chain, stack);
            stack.push(temp);
        } else {
            ret = 0;
        }
        stack.push(c);
        ret = cmp::max(ret, solve(i + 1, chain, stack));
        stack.pop();

        return ret;
    }

    solve(0, &chain, &mut stack)
}




fn test_case(chain: &str) {
    println!("Chain {}\nSolution {}", chain, solve2(chain));
}

fn main() {
    test_case("SBC");
    test_case("FCC");
    test_case("SFBC");
    test_case("SFBCFSCB");
    test_case("CFCBSFFSBCCB");
}