starlight.rs

use std::io::{self, BufRead};

fn main() {
    let stdin = io::stdin();
    let problem = stdin.lock().lines().map(|x| x.unwrap()).collect::<Vec<String>>();
    let result = solve_problem(&problem[0][..], &problem[1][..]); 
    println!("{}", result);
}

fn solve_problem(start_line: &str, target_line: &str) -> i32 {
    if start_line.len() == 0 { return 0; }
    if start_line.chars().next() == target_line.chars().next() {
        return solve_problem(&start_line[1..], &target_line[1..]);
    } else {
        // modifiable subset is the subset needed to modify a given star (i.e.: 10..0)
        let modifiable_subset =
            (std::iter::repeat("1").take(1)
             .chain(std::iter::repeat("0")))
            .take(start_line.len() -1)
            .collect::<String>();
        return 1
            + solve_problem(&start_line[1..], &modifiable_subset[..])
            + solve_problem(&modifiable_subset[..], &target_line[1..]);
    }
}

#[cfg(test)]
mod tests {
    use crate::solve_problem;

    #[test]
    fn example_1() {
        let problem = [
            "1101",
            "0100"
        ];
        assert_eq!(2, solve_problem(&problem[0], &problem[1]));
    }

    #[test]
    fn example_2() {
        let problem = [
            "101010",
            "010101"
        ];
        assert_eq!(26, solve_problem(&problem[0], &problem[1]));
    }

    #[test]
    fn example_3() {
        let problem = [
            "11001001000",
            "10000110011"
        ];
        assert_eq!(877, solve_problem(&problem[0], &problem[1]));
    }
    #[test]
    #[ignore] // worst case computation, ~100s on local.
    fn worst_case() {
        let problem = [
            "0000000000000000000000000",
            "1000000000000000000000000"
        ];
        assert_eq!(33554431, solve_problem(&problem[0], &problem[1]));
    }
}