a

use std::collections::VecDeque;
use std::fs::File;
use std::io::Read;

struct Tree<T>(Vec<Node<T>>);

struct Node<T> {
    sub_pos: i32,
    value: T,
    subtree: Vec<Node<T>>,
}

// Represents a substitution rule
struct Rule {
    from: String,
    to: String,
}

fn main() -> Result<(), Box<std::error::Error>> {
    // Parse the input :/
    // I hate this part
    let mut rules = Vec::new();
    let mut input_file = File::open("input.txt")?;
    let mut input_text = String::new();
    input_file.read_to_string(&mut input_text);
    let input_lines: Vec<String> = input_text.lines().map(ToOwned::to_owned).collect();

    // Now parse these as rules
    for i in 0..3 {
        let split: Vec<String> = input_lines[i].split(" ").map(ToOwned::to_owned).collect();
        rules.push(Rule {
            from: split[0].clone(),
            to: split[1].clone(),
        });
    }

    let split: Vec<String> = input_lines[3].split(" ").map(ToOwned::to_owned).collect();
    let seq_len = split[0].parse::<i32>()?;
    let start = split[1].clone();
    let end = split[2].clone();

    // Now we can build up a search tree
    let mut tree = Tree::<String>(vec![Node::<String> {
        sub_pos: 0,
        value: start,
        subtree: Vec::new(),
    }]);
    // Queue of the next layer
    let mut queue: VecDeque<&mut Node<String>> = VecDeque::new();
    queue.push_back(&mut tree.0[0]);
    for i in 0..seq_len {
        for node in &mut queue {
            for rule in &rules {
                for (new_string, sub_pos) in transform(&node.value, rule) {
                    if i == seq_len - 1 && new_string == end {
                        // Solution found!
                        // search it here - cba
                    }
                    node.subtree.push(Node::<String> {
                        sub_pos: sub_pos,
                        value: new_string,
                        subtree: Vec::new(),
                    });
                }
            }
        }
    }

    Ok(())
}

fn transform(input: &str, rule: &Rule) -> Vec<(String, i32)> {
    let mut solutions: Vec<(String, i32)> = Vec::new();
    let length = rule.from.len();
    for idx in 0..input.len() - length {
        let slice = &input[idx..idx + length];
        if slice == rule.from {
            // Avaliable substitution, so go ahead
            let new_string = format!(
                "{}{}{}",
                &input[0..idx],
                rule.to,
                &input[length + idx..input.len()]
            );
            // Add one to start position - 1 indexed
            solutions.push((new_string, (idx + 1) as i32));
        }
    }
    solutions
}