# Jordan Code v2c

Basic genetic algorithm to mutate results with pooled multi-threading.

This version uses a variable mutation rate and an improved output formatter.

Usage
v2c <file_num> <thread_count> <thread_delay> <mutation_rate> <mutation_decrease_secs> <stuck_limit_secs>

file_num: The input file to use (0 - 5).
thread_count: The number of threads to use. (Usually 2 per core.)
thread_delay: The number of milliseconds wait before checking threads for new answers and respawning threads.
mutation_rate: The number of changes to make per trial to start with. 
mutation_decrease_secs: The number of seconds to wait without finding an answer before decreasing the mutation rate by 1. (Never drops below 1.)
stuck_limit_secs: The number of seconds to wait without finding an answer before restarting.

Usage example: cargo run --release 5 8 1000 10 10 300

use num_format::{Locale, ToFormattedString};
use rand::prelude::*;
use simple_error::bail;
use std::collections::{HashMap, VecDeque};
use std::cmp::{max, min};
// use std::cmp::{Reverse};
use std::env;
use std::error::Error;
use std::fs::File;
use std::io::{BufRead, BufReader, Write};
use std::sync::mpsc::channel;
use std::thread::sleep;
use std::time::{Duration as TimeDuration, Instant};
use threadpool::ThreadPool;

// Types
type Duration = u32;
type IntersectionId = u32;
type Path = Vec<StreetId>;
type Paths = Vec<Path>;
type Score = u64;
#[derive(Clone, Debug)]
struct Street
{
	street_id: StreetId,
	start_intersection: IntersectionId,   
	end_intersection: IntersectionId,
	length: Duration
}
type StreetId = usize;
type StreetName = String;
type StreetNames = Vec<StreetName>;
type Streets = Vec<Street>;
#[derive(Clone, Debug)]
struct StreetSchedule
{
	street_id: StreetId,
	duration: Duration
}
#[derive(Clone, Debug)]
struct IntersectionSchedule
{
	intersection_id: IntersectionId,
	schedule: Vec<StreetSchedule>
}
type Submission = Vec<IntersectionSchedule>;

// Simulation Types
#[derive(Clone, Debug)]
struct Car
{
	active: bool, // Active if the car has not reached its destination.
	current_path_index: usize, // The current path index.
	duration_remaining: Duration, // The duration remaining before the car reaches the intersection.
	path: Path // The path the car will follow.
}
#[derive(Clone, Debug)]
struct Intersection
{
	intersection_id: IntersectionId,
	car_queue: HashMap<StreetId, VecDeque<usize>>,
	current_schedule_index: usize,
	duration_remaining: Duration,
	schedule: Vec<StreetSchedule>,
	available: bool // Only one car can pass per second. Is the intersection still available to allow a car through?
}

// Utility Functions
fn get_filename(file_number: usize) -> Result<String, Box<dyn Error>>
{
	match file_number
	{
		0 => Ok("../data/input/a.txt".to_owned()),
		1 => Ok("../data/input/b.txt".to_owned()),
		2 => Ok("../data/input/c.txt".to_owned()),
		3 => Ok("../data/input/d.txt".to_owned()),
		4 => Ok("../data/input/e.txt".to_owned()),
		5 => Ok("../data/input/f.txt".to_owned()),
		_ => bail!("Incorrect file number specified."),
	}
}

fn get_cli_args() -> Result<(usize, usize, usize, usize, usize, usize), Box<dyn Error>>
{
	let args: Vec<String> = env::args().collect();

	let input_file_index = args[1].parse()?;
	let thread_count = args[2].parse()?;
	let thread_delay = args[3].parse()?;
	let mutation_rate = args[4].parse()?;
	let mutation_decrease_secs = args[5].parse()?;
	let stuck_limit_secs = args[6].parse()?;

	Ok((input_file_index, thread_count, thread_delay, mutation_rate, mutation_decrease_secs, stuck_limit_secs))
}

fn parse_input_data(input_data: &Vec<String>) -> Result<(Duration, u32, u32, u32, Score, Streets, StreetNames, Paths), Box<dyn Error>>
{
	let mut line01 = input_data[0].split_whitespace();

	let duration_total: Duration = line01.next().unwrap().parse()?;
	let intersection_count = line01.next().unwrap().parse()?;
	let streets_count = line01.next().unwrap().parse()?;
	let cars_count = line01.next().unwrap().parse()?;
	let car_bonus = line01.next().unwrap().parse()?;

	let mut streets: Streets = vec!();
	let mut street_names: StreetNames = vec!();
	for i in 0..streets_count as usize
	{
		// println!("Processing Streets {}/{}", i+1, streets_count);

		let mut line = input_data[i+1].split_whitespace();
		let start: IntersectionId  = line.next().unwrap().parse()?;
		let end: IntersectionId = line.next().unwrap().parse()?;
		let name: StreetName = line.next().unwrap().parse()?;
		let duration: Duration = line.next().unwrap().parse()?;

		street_names.push(name);
		let street = Street
		{
			street_id: i as StreetId,
			start_intersection: start,
			end_intersection: end,
			length: duration
		};

		streets.push(street);
	}

	let mut paths: Paths = vec!();
	for i in 0..cars_count as usize
	{
		// println!("Processing Cars {}/{}", i+1, cars_count);

		let ii = i + 1 + streets_count as usize;
		let mut line = input_data[ii].split_whitespace();
		let mut path: Path = vec!();
		let count: usize = line.next().unwrap().parse()?;

		for _c in 0..count
		{
			let street_name = line.next().unwrap();
			let street_id = street_names.iter().position(|x|x==street_name).unwrap();
			path.push(street_id);
		}

		paths.push(path);
	}

	// dbg!(&streets);
	// dbg!(&paths);

	Ok((duration_total, intersection_count, streets_count, cars_count, car_bonus, streets, street_names, paths))
}

fn read_input(file_path: &str) -> Result<Vec<String>, Box<dyn Error>>
{
	let file = File::open(file_path)?;
	let reader = BufReader::new(file);
	let mut lines = Vec::new();

	for line in reader.lines()
	{
		let line = line?;
		let line = line.trim().parse()?;
		lines.push(line);
	}

	Ok(lines)
}

fn write_output(file_path: &str, submissions: &Submission, street_names: &StreetNames) -> Result<(), Box<dyn Error>>
{
	// Create a new submissions that omits any street schedules with a duration of 0.
	let mut submissions_new = vec!();
	for intersection_schedule in submissions.iter()
	{
		// Create a replacement empty intersection schedule.
		let mut intersection_schedule_new = IntersectionSchedule
		{
			intersection_id: intersection_schedule.intersection_id,
			schedule: vec!()
		};

		// Cycle through each street schedule.
		for street_schedule in intersection_schedule.schedule.iter()
		{
			// Populate the intersection schedule.
			if street_schedule.duration > 0
			{
				intersection_schedule_new.schedule.push(street_schedule.clone());				
			}
		}

		// If there is at least a single street schedule with duration > 0, add the intersection schedule the submissions.
		let duration_total: Duration = intersection_schedule_new.schedule.iter().map(|x|x.duration).sum();
		if duration_total > 0
		{
			submissions_new.push(intersection_schedule_new);
		}
	}

	let mut file = File::create(file_path)?;
	file.write_all(format!("{}\n", submissions_new.len()).as_bytes())?;

	for intersection_schedule in submissions_new
	{
		file.write_all(format!("{}\n", intersection_schedule.intersection_id).as_bytes())?;
		file.write_all(format!("{}\n", intersection_schedule.schedule.len()).as_bytes())?;

		for i in 0..intersection_schedule.schedule.len()
		{
			file.write_all(format!("{} {}\n", street_names[intersection_schedule.schedule[i].street_id as usize], intersection_schedule.schedule[i].duration).as_bytes())?;
		}
	}

	Ok(())
}

fn validate_args() -> Result<(), Box<dyn Error>>
{
	let args: Vec<String> = env::args().collect();
	if args.len() != 7
	{
		bail!("Incorrect number of arguments. Correct usage is <file_num> <thread_count> <thread_delay> <mutation_rate> <mutation_decrease_secs> <stuck_limit_secs>.");
	}

	Ok(())
}

// Calculation Functions
fn calculate_submission_score(submission: &Submission, paths: &Paths, streets: &Streets, duration_total: Duration, car_bonus: Score, _street_names: &StreetNames) -> Result<Score, Box<dyn Error>>
{
	let mut score = 0;

	// Create initial intersection state from submissions.
	let mut intersections = HashMap::new();
	for (_i, intersection_schedule) in submission.iter().enumerate()
	{
		let intersection_id = intersection_schedule.intersection_id;

		let intersection = Intersection
		{
			intersection_id: intersection_id,
			car_queue: intersection_schedule.schedule.iter().map(|x|(x.street_id, VecDeque::new())).collect(),
			current_schedule_index: 0,
			duration_remaining: intersection_schedule.schedule[0].duration,
			schedule: intersection_schedule.schedule.clone(),
			available: true
		};
		intersections.insert(intersection_id, intersection);
	}

	// Create initial car position from paths.
	let mut cars = vec!();
	for (i, path) in paths.iter().enumerate()
	{
		// Create the car instance.
		let car = Car
		{
			active: true,
			current_path_index: 0,
			duration_remaining: 0,
			path: path.clone()
		};
		cars.push(car);

		// Add the car to the car_queue on the intersection.
		let street_id = path[0];
		let intersection = intersections.get_mut(&streets[street_id as usize].end_intersection).unwrap();
		intersection.car_queue.get_mut(&street_id).unwrap().push_back(i);
	}

	// Run simulation time indexes.
	for t in 1..duration_total+1
	{
		// Update car positions.
		for (car_id, car) in cars.iter_mut().enumerate()
		{
			// Skip all inactive cars.
			if !car.active
			{
				continue;
			}

			// If car is at an intersection.
			if car.duration_remaining == 0
			{
				let car_street_id = car.path[car.current_path_index];
				let car_intersection = streets[car_street_id as usize].end_intersection;
				let intersection = intersections.get_mut(&car_intersection).unwrap();

				// If car is on the final street.
				if car.current_path_index == car.path.len() - 1
				{
					// Remove car and add to score immediately.
					car.active = false;
					score += car_bonus + (duration_total - t) as Score;

					continue;
				}
				// Car has reached an intersection, but is not on the final street.
				else
				{
					let intersection_car_queue = intersection.car_queue.get_mut(&car_street_id).unwrap();
					
					// If the intersection queue does not already has this car waiting.
					if !intersection_car_queue.contains(&car_id)
					{
						// Add to the car to the back of the intersection queue.
						intersection_car_queue.push_back(car_id);
					}					
				}

				// Is there a green light at the intersection for the street the car is currently on?
				let is_green_light = intersection.schedule[intersection.current_schedule_index].street_id == car_street_id;

				// If the car is at an intersection with a green light on the current street and no other car has already passed in the same time slice.
				if is_green_light && intersection.available
				{
					let intersection_car_queue = intersection.car_queue.get_mut(&car_street_id).unwrap();
					let front_car_id = intersection_car_queue.front().unwrap();
	
					// If the car is at the front of the line.
					if *front_car_id == car_id
					{
						// Remove car from the car queue.
						intersection_car_queue.pop_front();

						// Mark the intersection as no longer available until the next time slot.
						intersection.available = false;

						// Update the path index and duration. This should never be out of index since it is detected above.
						car.current_path_index += 1;
						car.duration_remaining = streets[car.path[car.current_path_index]].length;
					}
				}
			}

			// If we have not hit the end of the street.
			if car.duration_remaining > 0
			{
				// Move car forward a step.
				car.duration_remaining -= 1;

				// If we hit the end of a street.
				if car.duration_remaining == 0
				{
					// If car is on the final street.
					if car.current_path_index == car.path.len() - 1
					{
						// Remove car and add to score immediately.
						car.active = false;
						score += car_bonus + (duration_total - t) as Score;
	
						continue;
					}
				}
			}
		}

		// Update intersections.
		for (_i, intersection) in intersections.iter_mut()
		{
			// If there are no schedules with a duration of at least 1, disable the intersection.
			let intersection_total_duration: Duration = intersection.schedule.iter().map(|x|x.duration).sum();
			if intersection_total_duration < 1
			{
				intersection.available = false;
				continue;
			}

			// Step forward in time.
			intersection.duration_remaining -= 1;

			// Intersection is at end of cycle (duration_remaining == 0)
			if intersection.duration_remaining == 0
			{
				// We loop here until we find a schedule with a duration > 0 or there are no schedules available.
				loop
				{
					// Set to the next index.
					intersection.current_schedule_index += 1;
	
					// If the index is out of range, go back to the first.
					if intersection.current_schedule_index >= intersection.schedule.len()
					{
						intersection.current_schedule_index = 0;
					}
	
					// Set the duration remaining to the duration in the schedule. 
					intersection.duration_remaining = intersection.schedule[intersection.current_schedule_index].duration;

					// Break if we have an intersection with a duration > 0.
					if intersection.duration_remaining > 0
					{
						break;
					}
				}
			}

			// Reset the available flag.
			intersection.available = true;
		}
	}

	Ok(score)
}

fn generate_submission(_duration_total: Duration, _intersection_count: u32, _streets_count: u32, _cars_count: u32, _car_bonus: u64, streets: &Streets, _street_names: &StreetNames, paths: &Paths) -> Result<Submission, Box<dyn Error>>
{
	// let mut rng = rand::thread_rng();

	// Cycle through each path and create a hashmap of intersections with schedules.
	let mut intersections: HashMap<IntersectionId, Vec<StreetSchedule>> = HashMap::new();
	for path in paths
	{
		for (_path_order, street_id) in path.iter().enumerate()
		{
			let intersection = streets[*street_id as usize].end_intersection;

			if !intersections.contains_key(&intersection)
			{
				intersections.insert(intersection, vec!());
			}

			let schedules = intersections.get_mut(&intersection).unwrap();
			let mut found = false;
			for schedule in schedules.iter_mut()
			{
				if schedule.street_id == *street_id
				{
					// schedule.duration += 1;
					found = true;
				}
			}
			if found == false
			{
				let street_schedule = StreetSchedule
				{
					street_id: *street_id,
					duration: 1 //rng.gen_range(0, 5)
				};
				
				schedules.push(street_schedule);
			}
		}
	}

	// Adjust the duration by taking into account the street length and order in paths.
	// for (_intersection_id, street_schedule) in intersections.iter_mut()
	// {
	// 	street_schedule.sort_by_key(|x|Reverse(x.duration));

	// 	// Adjust durations.
	// 	let count = street_schedule.len() as i32;
	// 	for (i, street_schedule) in street_schedule.iter_mut().enumerate()
	// 	{
	// 		let duration = count - (i as i32);

	// 		duration = max(duration, 1); // Ensure minimum.
	// 		duration = min(duration, 2); // Ensure maximum.

	// 		street_schedule.duration = duration as u32;
	// 	}

	// 	// dbg!(&street_schedule);
	// }

	// Create schedule for all intersections.
	let mut intersection_schedules = vec!();
	for intersection in intersections
	{
		let intersection_schedule = IntersectionSchedule
		{
			intersection_id: intersection.0,
			schedule: intersection.1
		};

		intersection_schedules.push(intersection_schedule);
	}

	Ok(intersection_schedules)
}

fn mutate_submission(mut submission: Submission, mut rng: ThreadRng, duration_total: Duration, mutation_rate: usize) -> Submission
{
	for _ in 0..mutation_rate
	{
		// Select a random action.
		let action = rng.gen_range(0, 5);

		// Action 0 = swap schedule order.
		if action == 0
		{
			// Select a random intersection.
			let index = rng.gen_range(0, submission.len()-1);
			let intersection_schedule = &mut submission[index];

			if intersection_schedule.schedule.len() > 1
			{
				let index_0 = rng.gen_range(0, intersection_schedule.schedule.len()-1);
				let index_1 = rng.gen_range(0, intersection_schedule.schedule.len()-1);

				if index_0 != index_1
				{
					intersection_schedule.schedule.swap(index_0, index_1);
				}
			}
		}

		// Action 1+ = modify duration.
		if action >= 1
		{
			// Select a random intersection.
			let index = rng.gen_range(0, submission.len()-1);
			let intersection_schedule = &mut submission[index];

			if intersection_schedule.schedule.len() > 1
			{
				let index = rng.gen_range(0, intersection_schedule.schedule.len()-1);
				let street_schedule = &mut intersection_schedule.schedule[index];
			
				if rng.gen_range(0, 1) == 0
				{
					street_schedule.duration -= 1;
				}
				else
				{
					street_schedule.duration += 1;
				}
		
				street_schedule.duration = max(street_schedule.duration, 0); // Ensure minimum.
				street_schedule.duration = min(street_schedule.duration, duration_total); // Ensure maximum.
			}
		}
	}

	submission
}

// Main Entry Point
fn main() -> Result<(), Box<dyn Error>>
{
	validate_args()?;
	let (input_file_index, thread_count, thread_delay, mutation_rate, mutation_decrease_secs, stuck_limit_secs) = get_cli_args()?;
	let filename = get_filename(input_file_index)?;

	let input_data = read_input(&filename)?;
	let (duration_total, intersection_count, streets_count, cars_count, car_bonus, streets, street_names, paths) = parse_input_data(&input_data)?;

	let baseline_timer = Instant::now();
	let baseline_submission = generate_submission(duration_total, intersection_count, streets_count, cars_count, car_bonus, &streets, &street_names, &paths)?;
	let baseline_score = calculate_submission_score(&baseline_submission, &paths, &streets, duration_total, car_bonus, &street_names)?;
	println!("Baseline Score: {} (Generated in {:#?}.)", baseline_score.to_formatted_string(&Locale::en), baseline_timer.elapsed());

	let mut best_score = baseline_score;
	let mut best_submission = baseline_submission.clone();
	let mut current_mutation_rate = mutation_rate;
	let mut mutation_timer = Instant::now();
	let mut solution_timer = Instant::now();
	let mut thread_channels = vec!();
	let (tx, rx) = channel();

	let pool = ThreadPool::new(thread_count);

	loop
	{
		while pool.active_count() < thread_count
		{
			let mut thread_best_score = best_score;
			let mut thread_best_submission = best_submission.clone();
			let thread_paths = paths.clone();
			let thread_street_names = street_names.clone();
			let thread_streets = streets.clone();

			let tx = tx.clone();
			let (tx_thread, rx_thread) = channel();
			thread_channels.push(tx_thread);

			pool.execute(move ||
			{
				let rng = rand::thread_rng();

				loop
				{
					let thread_submission = mutate_submission(thread_best_submission.clone(), rng, duration_total, current_mutation_rate);
					let thread_score = calculate_submission_score(&thread_submission, &thread_paths, &thread_streets, duration_total, car_bonus, &thread_street_names).unwrap();

					if thread_score > thread_best_score
					{
						// println!("New Best Thread Score: {}", thread_score.to_formatted_string(&Locale::en));

						thread_best_score = thread_score;
						thread_best_submission = thread_submission.clone();

						tx.send((thread_best_score, thread_best_submission.clone())).expect("Thread tx channel failed.");
					}

					if let Ok(_) = rx_thread.try_recv()
					{
						// println!("Thread received kill notice.");
						break;
					}
				}
			});
		}

		// Delay before checking for messages to avoid non-stop checking on this thread. 
		sleep(TimeDuration::from_millis(thread_delay as u64));

		// Check new best scores were received from the threads.
		let mut new_best_score_found = false;
		loop
		{
			if let Ok((trial_score, trial_submission)) = rx.try_recv()
			{
				if trial_score > best_score
				{
					best_score = trial_score;
					best_submission = trial_submission;
					new_best_score_found = true;
				}
			}
			else
			{
				break;
			}
		}

		// If a new best score was found, record it and restart the threads.
		if new_best_score_found
		{
			println!("New Best Score: {}", best_score.to_formatted_string(&Locale::en));

			// Restart both timers.
			mutation_timer = Instant::now();
			solution_timer = Instant::now();

			// Write the output file.
			let filename = filename.replace(".txt", &format!(".{}.{}.jm.out", best_score, env!("CARGO_PKG_NAME"))).replace("/input/", "/output/");
			write_output(&filename, &best_submission, &street_names)?;

			// Restart all threads.
			thread_channels.drain(..).for_each(|x|{let _ = x.send(());});
		}

		// If no scores were generated for x seconds, decrease mutation rate.
		if current_mutation_rate > 1 && mutation_timer.elapsed().as_secs() > mutation_decrease_secs as u64
		{
			current_mutation_rate -= 1;
			mutation_timer = Instant::now();
			println!("Decreasing mutation rate to: {}.", current_mutation_rate);

			// Restart all threads.
			thread_channels.drain(..).for_each(|x|{let _ = x.send(());});
		}

		// If no scores were generated for x seconds, restart.
		if solution_timer.elapsed().as_secs() > stuck_limit_secs as u64
		{
			println!("Stuck time limit exceeded. Restarting.");

			best_score = baseline_score;
			best_submission = baseline_submission.clone();
			current_mutation_rate = mutation_rate;
			mutation_timer = Instant::now();
			solution_timer = Instant::now();

			// Restart all threads.
			thread_channels.drain(..).for_each(|x|{let _ = x.send(());});
		}
	}

	#[allow(unreachable_code)]
	Ok(())
}