// adventofcode - day 13 // part 1 // shamelessly copied from 9.2 and slightly modified use std::io::prelude::*; use std::fs::File; use std::collections::HashSet; struct Graph { nodes: Option<Vec<String>>, matrix: Option<Vec<Vec<i32>>>, } impl Graph { fn new(names: HashSet<String>) -> Graph { let mut graph = Graph{nodes: None, matrix: None}; let size = names.len(); graph.nodes = Some(Vec::with_capacity(size)); match graph.nodes { Some(ref mut nodes) => { for name in names { nodes.push(name.to_string()); } nodes.sort(); }, None => { panic!("Failed to create graph!"); } } graph.matrix = Some(Vec::<Vec<i32>>::with_capacity(size)); match graph.matrix { Some(ref mut matrix) => { for ii in 0..size { matrix.push(Vec::<i32>::with_capacity(size)); for _ in 0..size { matrix[ii].push(0); } } }, None => { panic!("Failed to create graph!"); } } graph } fn size(&self) -> usize { match self.nodes { Some(ref nodes) => nodes.len(), None => 0, } } #[allow(dead_code)] fn get_node_names(&self) -> Vec<String> { match self.nodes { Some(ref nodes) => nodes.clone(), None => Vec::<String>::new(), } } fn insert_edge(&mut self, src: &String, dest: &String, length: i32) { let src_idx = match self.nodes { Some(ref nodes) => match nodes.binary_search(src){ Ok(x) => x, Err(e) => { println!("Error: {}", e); return; }, }, None => return, }; let dst_idx = match self.nodes { Some(ref nodes) => match nodes.binary_search(dest){ Ok(x) => x, Err(e) => { println!("Error: {}", e); return; }, }, None => return, }; match self.matrix { Some(ref mut matrix) => { matrix[src_idx][dst_idx] = length; }, None => return, } } fn calculate_happiness(&self, seated: Vec<usize>) -> (i32, Vec<usize>){ if seated.len() == self.size() { return (self.calculate_happiness_of_table(&seated), seated); } let mut max_happiness = std::i32::MIN; let mut max_table = Vec::new(); for ii in 0..self.size(){ if ! seated.contains(&ii){ let mut table = seated.clone(); table.push(ii); // NOT table.flip() ! let (happiness, table) = self.calculate_happiness(table); if happiness > max_happiness { max_happiness = happiness; max_table = table; } } } (max_happiness, max_table) } // bruteforce solution fn calculate_happiness_of_table(&self, table: &Vec<usize>) -> i32 { let mut seats = table.iter(); let first = seats.next().unwrap(); let mut from = first; let mut happiness = 0i32; loop { match seats.next() { Some(to) => { happiness += self.get_happiness_of_seatmates(*from, *to); from = to; }, None => { return happiness + self.get_happiness_of_seatmates(*from, *first); }, } } } fn get_happiness_of_seatmates(&self, a: usize, b: usize) -> i32 { match self.matrix { // happiness changes in both ways Some(ref matrix) => matrix[a][b] + matrix[b][a], None => 0, } } fn get_persons_name(&self, id: usize) -> String { match self.nodes { Some(ref persons) => persons[id].clone(), None => "N/A".to_string(), } } } fn main(){ println!("Advent of Code - day 13 | part 2"); // import data let data = import_data(); let family = match parse_data(data){ Some(x) => x, None => panic!("Couldn\'t parse data!"), }; let table = Vec::new(); let (happiness, table) = family.calculate_happiness(table); println!("Highest happiness possible: {}", happiness); for id in table { println!("{}", family.get_persons_name(id)); } } fn parse_data(data: String) -> Option<Graph> { let mut all_names = HashSet::new(); let mut connections = Vec::<(String, String, i32)>::new(); for line in data.lines(){ print!("{} -> ", line); let (to, from, cost) = parse_line(line.to_string()); println!("{} to {} = {}", to, from, cost); all_names.insert(to.clone()); connections.push( (to, from, cost) ); } let mut graph = Graph::new(all_names); for (to, from, cost) in connections { graph.insert_edge(&to, &from, cost); } Some(graph) } fn parse_line(line: String) -> (String, String, i32) { let mut values = line.split(" would ") .flat_map(|s| s.split(" happiness units by sitting next to ")) .map(|s| s.parse::<String>().unwrap()) .collect::<Vec<String>>(); let cost = if values[1].starts_with("lose") { -1 } else { 1 } * &values[1][5..].parse::<i32>().unwrap(); // remove the . at the end values[2].pop(); (values[0].clone(), values[2].clone(), cost ) } // This function simply imports the data set from a file called input.txt fn import_data() -> String { let mut file = match File::open("../../inputs/13.txt") { Ok(f) => f, Err(e) => panic!("file error: {}", e), }; let mut data = String::new(); match file.read_to_string(&mut data){ Ok(_) => {}, Err(e) => panic!("file error: {}", e), }; // remove trailing \n data.pop(); data }