Naive, slow solution for google code jam 2009 qualification problem A, "Alien Language." Rust 0.6 (incoming branch)

alien2009

extern mod std;
use core::io::ReaderUtil;
use core::vec;
use core::vec::*;

fn main() {
    let input = get_lines();
    let first_line: &str = input[0];
    let toks = str::split_char(first_line, ' ');
    let ldn = map(toks, |&s| uint::from_str(s).get());
    let (d, n) = (ldn[1], ldn[2]);
    let dictionary = slice(input, 1, d+1);
    let test_cases = slice(input, d+1, n+d+1);
    for test_cases.eachi |i, &t| {
        let answer = num_matching(dictionary, t);
        io::println(fmt!("Case #%?: %d", i, answer));
    }
}

fn num_matching(dic: &[~str], lex: &str) -> int {
    let mut result = 0;
    let combinations = parse_combinations(lex);
    for combinations.each |c| {
        if contains(dic, c) {
            result += 1;
        }
    }
    result
}

fn parse_combinations(lex: &str) -> ~[~str] {
    let cvec = break_str_into_groups(lex);
    let p = product_n(cvec);
    p
}

fn break_str_into_groups(lex: &str) -> ~[~[~str]] {
    let mut cvec = ~[];
    let mut inner_vec = ~[];
    let mut in_parens = false;
    let pieces = map(str::chars(lex), |&c| { str::from_char(c) } );
    for pieces.each |&c| {
        if c == ~"(" {
            in_parens = true;
        }
        else if c == ~")" {
            in_parens = false;
            let mut tmp = ~[];
            for inner_vec.each |&t| { tmp.push(t); }
            cvec.push(tmp);
            inner_vec.clear();
        }
        else {
            if in_parens == true {
                inner_vec.push(c);
            }
            else {
                cvec.push(~[c]);
            }
        }
    }
    cvec
}

fn product_n(v: &[~[~str]]) -> ~[~str] {
    match v.len() {
        n if n < 2 => fail!(),
        n if n == 2 => product_pair(v[0], v[1]),
        n => product_pair(v[0], product_n(slice(v, 1, n)))
    }
}

fn product_pair(a: &[~str], b: &[~str]) -> ~[~str] {
    let mut result = ~[];
    for a.each |&i| {
        for b.each |&j| {
            result.push(i + j);
        }
    }
    result
}

fn get_lines() -> ~[~str] {
    let mut result = ~[];
    let reader = io::stdin();
    let util = @reader as @ReaderUtil;
    while !reader.eof() {
        result.push(util.read_line());
    }
    result
}

No regular expressions yet, so I just solve it the naive way using cartesian product. It's too slow to solve even the "small" input sample google provides (or runs out of memory, not sure).