starlight_less_strings_created.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][..], &one_then_zeros()[..]); 
    println!("{}", result);
}

fn solve_problem(start_line: &str, target_line: &str, modification_requirement :&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..], modification_requirement);
    } else {
        let new_requirement = &modification_requirement[..start_line.len()-1];
        return 1
            + solve_problem(&start_line[1..], new_requirement, modification_requirement)
            + solve_problem(new_requirement, &target_line[1..], modification_requirement);
    }
}

fn one_then_zeros() -> String {
    return (std::iter::repeat("1").take(1)
            .chain(std::iter::repeat("0")))
           .take(25)
           .collect::<String>();
}

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

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

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

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