use rand::Rng;
use std::collections::HashMap;
use std::time::Instant;

/// Represents a Turing Machine.
///
/// This Turing Machine struct consists of a set of states, transitions, a current state,
/// final states, a tape, and a head position.
#[derive(Clone, Debug)]
struct TuringMachine {
    /// The states of the Turing Machine.
    states: Vec<String>,

    /// The transition function of the Turing Machine.
    /// Maps a pair of current state and tape character to a tuple containing
    /// the next state, the character to write, and the direction to move.
    transitions: HashMap<(String, char), (String, char, char)>,

    /// The current state of the Turing Machine.
    current_state: String,

    /// The final (accepting) states of the Turing Machine.
    final_states: Vec<String>,

    /// The tape of the Turing Machine.
    tape: Vec<char>,

    /// The current position of the tape head.
    head_position: usize,
}

impl TuringMachine {
    /// Creates a new Turing Machine.
    ///
    /// # Arguments
    ///
    /// * `states` - A vector of strings representing the states of the Turing Machine.
    /// * `transitions` - A hash map representing the transition function.
    /// * `initial_state` - The initial state of the Turing Machine.
    /// * `final_states` - A vector of strings representing the final states.
    ///
    /// # Returns
    ///
    /// A new instance of `TuringMachine`.
    fn new(
        states: Vec<String>,
        transitions: HashMap<(String, char), (String, char, char)>,
        initial_state: String,
        final_states: Vec<String>,
    ) -> Self {
        Self {
            states,
            transitions,
            current_state: initial_state,
            final_states,
            tape: vec!['_'], // Start with a blank tape
            head_position: 0,
        }
    }

    /// Executes a single step of the Turing Machine.
    ///
    /// This function checks if the current state is a final state. If it is,
    /// the machine halts and returns `false`. Otherwise, it reads the current
    /// symbol under the tape head, finds the corresponding transition, writes
    /// the new symbol, moves the tape head, and updates the current state.
    ///
    /// # Returns
    ///
    /// `true` if the Turing Machine successfully performed a step, or `false`
    /// if it has reached a final state and halted.
    ///
    /// # Panics
    ///
    /// This function will panic if there is no transition defined for the
    /// current state and symbol, or if the direction in the transition is not
    /// 'R' or 'L'.
    fn step(&mut self) -> bool {
        if self.final_states.contains(&self.current_state) {
            return false; // Halt if in a final state
        }

        let current_symbol = self.tape[self.head_position];
        if let Some(&(ref new_state, new_symbol, direction)) = self
            .transitions
            .get(&(self.current_state.clone(), current_symbol))
        {
            // Write the new symbol to the tape
            self.tape[self.head_position] = new_symbol;

            // Move the head
            match direction {
                'R' => {
                    self.head_position += 1;
                    if self.head_position >= self.tape.len() {
                        self.tape.push('_'); // Extend the tape with a blank symbol if needed
                    }
                }
                'L' => {
                    if self.head_position > 0 {
                        self.head_position -= 1;
                    } else {
                        self.tape.insert(0, '_'); // Extend the tape to the left if needed
                    }
                }
                _ => panic!("Direction must be 'R' or 'L'"),
            }

            // Update the current state
            self.current_state = new_state.clone();
            true
        } else {
            panic!("No transition defined for this state and symbol");
        }
    }

    /// Runs the Turing Machine with a given input string.
    ///
    /// This function initializes the tape with the provided input string,
    /// appends a blank symbol at the end, and sets the head position to the
    /// start of the tape. It then repeatedly executes steps until the machine
    /// halts.
    ///
    /// # Arguments
    ///
    /// * `input_string` - A string representing the initial input on the tape.
    ///
    /// # Returns
    ///
    /// A `String` representing the contents of the tape after the machine has
    /// halted, with trailing blank symbols removed.
    fn run(&mut self, input_string: &str) -> String {
        // Initialize the tape with the input string
        self.tape = input_string.chars().collect();
        self.tape.push('_'); // Add a blank symbol at the end
        self.head_position = 0;
        self.current_state = self.states[0].clone();

        // Run the Turing machine until it halts
        while self.step() {}

        self.tape
            .iter()
            .collect::<String>()
            .trim_end_matches('_')
            .to_string() // Return the tape contents without trailing blanks
    }
}

/// Generates two random numbers.
///
/// The first number is generated between 2 and 999 (inclusive),
/// and the second number is generated between 1 and the first number (exclusive),
/// ensuring that it is always smaller.
///
/// # Returns
///
/// A tuple containing two `u32` numbers, where the first number is greater than the second.
fn generate_random_numbers() -> (u32, u32) {
    let mut rng = rand::thread_rng();
    let num1: u32 = rng.gen_range(2..1000); // Generate a random number
    let num2: u32 = rng.gen_range(1..num1); // Ensure the second number is smaller
    (num1, num2)
}

/// Main function to execute the Turing Machine simulation.
///
/// This function sets up the Turing Machine with predefined states and transitions,
/// generates random numbers, converts them to binary, and runs the Turing Machine
/// to verify that the sum of the numbers is correctly computed in binary form.
/// It runs a series of tests and asserts that the Turing Machine's output matches
/// the expected binary sum.
///
/// # Panics
///
/// The function will panic if the Turing Machine's result does not match the expected
/// binary sum of the two random numbers generated.
fn main() {
    // Define the Turing machine components
    let states = vec![
        "A".to_string(),
        "B".to_string(),
        "C".to_string(),
        "D".to_string(),
        "E".to_string(),
        "Z".to_string(),
    ];
    let transitions = HashMap::from([
        (("A".to_string(), '0'), ("A".to_string(), '0', 'R')),
        (("A".to_string(), '1'), ("A".to_string(), '1', 'R')),
        (("A".to_string(), '+'), ("A".to_string(), '+', 'R')),
        (("A".to_string(), '_'), ("B".to_string(), '_', 'L')),
        (("B".to_string(), '0'), ("B".to_string(), '1', 'L')),
        (("B".to_string(), '1'), ("C".to_string(), '0', 'L')),
        (("B".to_string(), '+'), ("E".to_string(), '_', 'R')),
        (("C".to_string(), '0'), ("C".to_string(), '0', 'L')),
        (("C".to_string(), '1'), ("C".to_string(), '1', 'L')),
        (("C".to_string(), '+'), ("D".to_string(), '+', 'L')),
        (("D".to_string(), '0'), ("A".to_string(), '1', 'R')),
        (("D".to_string(), '_'), ("A".to_string(), '1', 'R')),
        (("D".to_string(), '1'), ("D".to_string(), '0', 'L')),
        (("E".to_string(), '1'), ("E".to_string(), '_', 'R')),
        (("E".to_string(), '_'), ("Z".to_string(), '_', 'L')),
    ]);
    let initial_state = "B".to_string();
    let final_states = vec!["Z".to_string()];

    // Create a Turing machine instance
    let mut tm = TuringMachine::new(states, transitions, initial_state, final_states);

    let start = Instant::now();

    for _ in 0..10000 {
        // Generate two random numbers
        let (num1, num2) = generate_random_numbers();

        // Convert numbers to binary strings
        let binary1 = format!("{:b}", num1);
        let binary2 = format!("{:b}", num2);

        // Prepare the input for the Turing machine
        // Assuming the Turing machine expects the format "binary1+binary2"
        let tm_input = format!("{}+{}", binary1, binary2);

        // Run the Turing machine with the input
        let result = tm.run(&tm_input);

        // Calculate the expected result
        let expected_sum = num1 + num2;
        let expected_binary_sum: String = format!("{:b}", expected_sum);

        // Verify the Turing machine result
        assert_eq!(
            result, expected_binary_sum,
            "The Turing machine result does not match the expected binary sum."
        );
    }
    println!("All tests passed!");

    let duration = start.elapsed();
    println!("Time elapsed in running the Turing Machine: {:?}", duration);
}