diff options
Diffstat (limited to 'aufgabe3/src/main.rs')
| -rw-r--r-- | aufgabe3/src/main.rs | 175 |
1 files changed, 131 insertions, 44 deletions
diff --git a/aufgabe3/src/main.rs b/aufgabe3/src/main.rs index beb6484..556ff9d 100644 --- a/aufgabe3/src/main.rs +++ b/aufgabe3/src/main.rs @@ -1,9 +1,11 @@ +use std::collections::VecDeque; use std::env; use std::fmt::Display; use std::fmt::Write; use std::fs; use std::process; use std::str::FromStr; +use std::time; // Beschreibt eine einzelne Hex-Ziffer. Der enthaltene Integer nimmt nur die // Werte 0x0 bis 0xF an. @@ -39,8 +41,7 @@ struct SevenSegmentDisplayRow { struct Solution { // Die gegebene Anfangs-Hex-Zahl. initial: HexNumber, - // Alle Zwischenstände zwischen den Umlegungen, einschließlich des Anfangs- - // und Endzustandes. + // Alle Zwischenstände, einschließlich des Anfangs- und Endzustandes. states: Vec<SevenSegmentDisplayRow>, // Die ermittelte größtmögliche Hex-Zahl. r#final: HexNumber, @@ -53,13 +54,13 @@ struct Solution { // Löst eine gegebene Aufgabe, indem Teil 1 und 2 des Algorithmus nacheinander // aufgerufen werden. fn solve_task(task: Task) -> Solution { - let greatest_possible_number = solve_pt1(&task); - let states = solve_pt2(&task.number.digits, &greatest_possible_number); + let greatest_reachable_number = solve_pt1(&task); + let states = solve_pt2(&task.number.digits, &greatest_reachable_number); Solution { initial: task.number, r#final: HexNumber { - digits: greatest_possible_number, + digits: greatest_reachable_number, }, max_moves: task.max_moves, used_moves: states.len() - 1, @@ -67,6 +68,8 @@ fn solve_task(task: Task) -> Solution { } } +static mut BACKTRACK: usize = 0; + // Implementiert den ersten Teil des Algorithmus, der aus einer Aufgabe die // größtmögliche Hex-Zahl errechnet. fn solve_pt1(task: &Task) -> Vec<HexDigit> { @@ -81,14 +84,14 @@ fn solve_pt1(task: &Task) -> Vec<HexDigit> { // `segment_balance` am Ende 0 ist, kann die neue Ziffernreihe durch // Umlegungen realisiert werden. segment_balance: isize, - // `segment_flips_left` gibt an, wie viele Stäbchen-Positionen noch - // "geflippt" (d.h. gefüllt oder geleert) werden können, ohne die - // Maximalzahl an Umlegungen zu überschreiten. + // `segment_flips_left` gibt an, wie viele Segmente noch "geflippt" + // (d.h. gefüllt oder geleert) werden können, ohne die Maximalzahl an + // Umlegungen zu überschreiten. segment_flips_left: usize, // `vacant_segments_left` gibt an, wie viele überschüssige Stäbchen // theoretisch noch in den hinteren Ziffern untergebracht werden // könnten, wenn diese zu '8' (Ziffer bestehend aus den meisten - // Stäbchen) aufgefüllt werden. + // Stäbchen) aufgefüllt würden. vacant_segments_left: usize, // `occupied_segments_left` gibt an, wie viele fehlende Stäbchen // theoretisch noch aus den hinteren Ziffern entnommen werden könnten, @@ -112,6 +115,7 @@ fn solve_pt1(task: &Task) -> Vec<HexDigit> { // '1' reduziert werden. || -segment_balance > occupied_segments_left as isize { + unsafe { BACKTRACK += 1 }; return None; } // Es wird immer nur die erste Ziffer betrachtet, und die restlichen @@ -122,7 +126,10 @@ fn solve_pt1(task: &Task) -> Vec<HexDigit> { // `segment_balance` gleich 0 ist (s.o.). None => match segment_balance { 0 => Some(Vec::new()), - _ => None, + _ => { + unsafe { BACKTRACK += 1 }; + None + } }, Some((digit, rest)) => { // Die Anzahl der Stäbchen, aus der die erste Ziffer besteht. @@ -182,9 +189,8 @@ fn solve_pt1(task: &Task) -> Vec<HexDigit> { } // Wenn keine weiteren Umlegungen mehr möglich sind, // aber es einen Mangel oder Überschuss an Stäbchen - // gibt, führt dieser Pfad zu keiner Lösung. Es wird - // der nächstniedrigere Wert für die erste Ziffer - // probiert. + // gibt, wird der nächstniedrigere Wert für die erste + // Ziffer probiert. (0, _) => continue, // Ansonsten wird versucht, die restlichen Ziffern // rekursiv zu maximieren. @@ -211,6 +217,7 @@ fn solve_pt1(task: &Task) -> Vec<HexDigit> { // Der Pfad wird verworfen, da unter den gegebenen Bedingungen // für keinen Wert der ersten Ziffer eine gültige neue // Ziffernfolge gefunden werden konnte. + unsafe { BACKTRACK += 1 }; None } } @@ -234,14 +241,17 @@ fn solve_pt1(task: &Task) -> Vec<HexDigit> { }, ); - solve_pt1_internal( + let ret = solve_pt1_internal( &task.number.digits, 0, max_segment_flips, initial_vacant_segments, initial_occupied_segments, ) - .unwrap() + .unwrap(); + + println!("backtracks: {}", unsafe { BACKTRACK }); + ret } // Implementiert den zweiten Teil des Algorithmus, der aus der gegebenen @@ -259,6 +269,12 @@ fn solve_pt2(start: &[HexDigit], end: &[HexDigit]) -> Vec<SevenSegmentDisplayRow .map(|digit| digit.to_seven_segments()) .collect::<Vec<SevenSegmentDisplay>>(); + // In diesem Array werden die Zwischenstände zwischen den Umlegungen + // gesammelt. Diese werden am Ende auch zurückgegeben. + let mut states = vec![SevenSegmentDisplayRow { + displays: start_state.clone(), + }]; + // Beschreibt die Position eines Segments in einer Reihe von // Siebensegmentanzeigen. struct Coordinates { @@ -266,54 +282,87 @@ fn solve_pt2(start: &[HexDigit], end: &[HexDigit]) -> Vec<SevenSegmentDisplayRow segment_idx: usize, } + let mut current_state = start_state.clone(); + // In diesen beiden Arrays werden die Positionen der Segmente gespeichert, // die "ein-" bzw. "ausgeschaltet" werden müssen, um von der urspünglichen - // Hex-Zahl zur größtmöglichen zu kommen. - let mut on_flips: Vec<Coordinates> = Vec::new(); - let mut off_flips: Vec<Coordinates> = Vec::new(); + // Hex-Zahl zur größtmöglichen zu kommen, und die nicht schon durch eine + // Umlegung innerhalb einer Siebensegmentanzeige richtiggestellt werden + // konnten. + let mut unmatched_on_flips: Vec<Coordinates> = Vec::new(); + let mut unmatched_off_flips: Vec<Coordinates> = Vec::new(); for (display_idx, (segments_start, segments_end)) in start_state.iter().zip(end_state.iter()).enumerate() { + // In diesen beiden Arrays werden die Indizes der Segmente gespeichert, + // die in dieser Siebensegmentanzeige "ein-" bzw. "ausgeschaltet" + // werden müssen. + let mut on_flips = VecDeque::<usize>::new(); + let mut off_flips = VecDeque::<usize>::new(); + for (segment_idx, (segment_start, segment_end)) in segments_start .0 .iter() .zip(segments_end.0.iter()) .enumerate() { - let coordinate = Coordinates { - display_idx, - segment_idx, - }; match (segment_start, segment_end) { - (false, true) => on_flips.push(coordinate), - (true, false) => off_flips.push(coordinate), + (false, true) => on_flips.push_back(segment_idx), + (true, false) => off_flips.push_back(segment_idx), _ => {} } } + + // `num_intra_display_moves` ist die Anzahl der Umlegungen, die + // innerhalb dieser Siebensegmentanzeige erfolgen können. + let num_intra_display_moves = on_flips.len().min(off_flips.len()); + // Es werden vorab schon innerhalb dieser Siebensegmentanzeige + // `num_intra_display_moves` Umlegungen ausgeführt, indem gleichzeitig + // über die ersten `num_intra_display_moves` "On-Flips" und "Off-Flips" + // iteriert wird. Nach jeder Umlegung wird eine Kopie des + // Gesamt-Zwischenstandes gespeichert. + for (on_flip, off_flip) in on_flips + .drain(..num_intra_display_moves) + .zip(off_flips.drain(..num_intra_display_moves)) + { + current_state[display_idx].0[on_flip] = true; + current_state[display_idx].0[off_flip] = false; + states.push(SevenSegmentDisplayRow { + displays: current_state.clone(), + }) + } + + // Übrig gebliebene "Stäbchen-Flips", die nicht durch eine Umlegung + // innerhalb dieser Siebensegmentanzeige realisiert werden konnten, + // werden für die spätere Verarbeitung gespeichert. + let complete_coords = |segment_idx| Coordinates { + display_idx, + segment_idx, + }; + unmatched_on_flips.extend(on_flips.drain(..).map(complete_coords)); + unmatched_off_flips.extend(off_flips.drain(..).map(complete_coords)); } // Sanity Check - assert_eq!(on_flips.len(), off_flips.len()); - - let mut ret = vec![SevenSegmentDisplayRow { - displays: start_state.clone(), - }]; + assert_eq!(unmatched_on_flips.len(), unmatched_off_flips.len()); - // Zuletzt wird gleichzeiting über `on_flips` und `off_flips` iteriert. - // Es wird jeweils die beschriebene Umlegung ausgeführt, und nach jeder - // Umlegung wird eine Kopie des Zwischenstandes gespeichert, sodass am Ende - // die genaue Umlegungs-Abfolge einsehbar ist. - let mut current_state = start_state; - for (on_flip, off_flip) in on_flips.into_iter().zip(off_flips.into_iter()) { + // Zuletzt wird gleichzeiting über die noch nicht realisierten + // "Stäbchen-Flips" iteriert. Es wird jeweils die beschriebene Umlegung + // ausgeführt, und nach jeder Umlegung wird eine Kopie des Zwischenstandes + // gespeichert, sodass am Ende die genaue Umlegungs-Abfolge einsehbar ist. + for (on_flip, off_flip) in unmatched_on_flips + .into_iter() + .zip(unmatched_off_flips.into_iter()) + { current_state[on_flip.display_idx].0[on_flip.segment_idx] = true; current_state[off_flip.display_idx].0[off_flip.segment_idx] = false; - ret.push(SevenSegmentDisplayRow { + states.push(SevenSegmentDisplayRow { displays: current_state.clone(), }) } - ret + states } impl HexDigit { @@ -375,9 +424,47 @@ fn main() { }; let task_str = fs::read_to_string(task_file_name).expect("Datei kann nicht gelesen werden"); let task = Task::try_from(task_str.as_str()).expect("Datei enthält keine gültige Aufgabe"); - let solution = solve_task(task); - print!("{}", solution) + // let start = time::Instant::now(); + // let solution = solve_task(task); + // let elapsed = start.elapsed(); + + // println!("{}", solution); + // println!("Laufzeit ohne I/O: {:?}", elapsed); + + println!("Gegebene Hex-Zahl: {}", &task.number); + + let start_pt1 = time::Instant::now(); + let greatest_reachable_number = solve_pt1(&task); + let elapsed_pt1 = start_pt1.elapsed(); + + println!( + "Größtmögliche Hex-Zahl: {}", + HexNumber { + digits: greatest_reachable_number.clone(), + } + ); + + println!(); + println!("Laufzeit (Teil 1): {:?}", elapsed_pt1); + println!(); + + // let start_pt2 = time::Instant::now(); + // let states = solve_pt2(&task.number.digits, &greatest_reachable_number); + // let elapsed_pt2 = start_pt2.elapsed(); + + // println!("Zwischenstände:"); + // for state in &states { + // print!("{}", state); + // } + // println!(); + + println!("Gegebene Maximalzahl an Umlegungen: {}", task.max_moves); + // println!("Anzahl genutzter Umlegungen: {}", states.len() - 1); + + // println!(); + // println!("Laufzeit (Teil 2): {:?}", elapsed_pt2); + // println!("Laufzeit (gesamt ohne I/O): {:?}", elapsed_pt1 + elapsed_pt2); } // Liest eine Aufgabe im Format der Beispielaufgaben ein. @@ -399,9 +486,9 @@ impl TryFrom<&str> for Task { impl Display for Solution { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { writeln!(f, "Gegebene Hex-Zahl: {}", self.initial)?; - for state in &self.states { - state.fmt(f)?; - } + // for state in &self.states { + // state.fmt(f)?; + // } writeln!(f, "Größtmögliche Hex-Zahl: {}", self.r#final)?; writeln!(f, "Gegebene Maximalzahl an Umlegungen: {}", self.max_moves)?; writeln!(f, "Anzahl genutzter Umlegungen: {}", self.used_moves)?; @@ -486,7 +573,7 @@ impl Display for HexNumber { } } -// Stellt eine Siebensegmentanzeige mithilfe von Zeichen des Unicode-Blocks +// Stellt eine Siebensegmentanzeige mithilfe der Zeichen des Unicode-Blocks // "Box Drawing" dar. impl SevenSegmentDisplay { fn to_unicode(&self) -> [[char; 2]; 3] { @@ -546,7 +633,7 @@ impl SevenSegmentDisplay { } } -// Formatiert eine Reihe von Siebensegmentanzeigen mithilfe von Zeichen des +// Formatiert eine Reihe von Siebensegmentanzeigen mithilfe der Zeichen des // Unicode-Blocks "Box Drawing". impl Display for SevenSegmentDisplayRow { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { |