From d0c70ad88b11f412c9d8c6735b74cce1b1ff015b Mon Sep 17 00:00:00 2001 From: Malte Voos Date: Sat, 20 Aug 2022 14:12:11 +0200 Subject: cleanup --- einreichung/Aufgabe3/Quelltext/src/main.rs | 655 +++++++++++++++++++++++++++++ 1 file changed, 655 insertions(+) create mode 100644 einreichung/Aufgabe3/Quelltext/src/main.rs (limited to 'einreichung/Aufgabe3/Quelltext/src') diff --git a/einreichung/Aufgabe3/Quelltext/src/main.rs b/einreichung/Aufgabe3/Quelltext/src/main.rs new file mode 100644 index 0000000..fbf554d --- /dev/null +++ b/einreichung/Aufgabe3/Quelltext/src/main.rs @@ -0,0 +1,655 @@ +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. +#[derive(Clone, Copy)] +struct HexDigit(u8); + +// Beschreibt eine Hex-Zahl mit beliebig vielen Ziffern. Die Ziffern sind in +// Lesereihenfolge gespeichert. +struct HexNumber { + digits: Vec, +} + +// Beschreibt eine zu lösende Aufgabe. +struct Task { + number: HexNumber, + max_moves: usize, +} + +// Beschreibt den Zustand einer Siebensegmentanzeige als 8-Bit-Zahl. +// +// Die ersten sieben Bits (von rechts) geben jeweils an, ob das entsprechende +// Segment der Siebensegmentanzeige "an" ist bzw. ein Stäbchen enthält: wenn +// ja, ist das Bit eine 1; anderenfalls eine 0. Das letzte Bit ist immer eine +// 0. +// +// Die Reihenfolge der Segmente entspricht dieser Abbildung: +// https://en.wikipedia.org/wiki/Seven-segment_display#/media/File:7_Segment_Display_with_Labeled_Segments.svg +// +// Allgemein wird der Zustand der Siebensegmentanzeige also durch die Zahl +// 0b0GFEDCBA repräsentiert. +#[derive(Clone, Copy)] +struct SevenSegmentDisplay(u8); + +// Beschreibt den Zustand einer Reihe von Siebensegmentanzeigen. +struct SevenSegmentDisplayRow { + displays: Vec, +} + +// Vom Algorithmus zurückgegebene Lösung. +// Der Typ enthält ein paar redundante Informationen, die aber die Ausgabe des +// Programms anschaulicher machen. +struct Solution { + // Die gegebene Anfangs-Hex-Zahl. + initial: HexNumber, + // Alle Zwischenstände, einschließlich des Anfangs- und Endzustandes. + states: Vec, + // Die ermittelte größtmögliche Hex-Zahl. + r#final: HexNumber, + // Die gegebene Maximalzahl an Umlegungen. + max_moves: usize, + // Die Anzahl der tatsächlich genutzten Umlegungen. + used_moves: usize, +} + +// Löst eine gegebene Aufgabe, indem Teil 1 und 2 des Algorithmus nacheinander +// aufgerufen werden. +fn solve_task(task: Task) -> Solution { + 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_reachable_number, + }, + max_moves: task.max_moves, + used_moves: states.len() - 1, + states, + } +} + +// Implementiert den ersten Teil des Algorithmus, der aus einer Aufgabe die +// größtmögliche Hex-Zahl errechnet. +fn solve_pt1(task: &Task) -> Vec { + // `solve_pt1_internal` ist der rekursive Teil der Funktion, der versucht, + // den gegebenen Ausschnitt der Hex-Zahl zu maximieren. + fn solve_pt1_internal( + // Der zu maximierende Ausschnitt der Hex-Zahl. + digits: &[HexDigit], + // `segment_balance` enthält im Laufe der Rekursion immer den + // "Kontostand" der Stäbchen. Wenn es einen Überschuss bzw. Mangel an + // Stäbchen gibt, ist `segment_balance` positiv bzw. negativ. Nur wenn + // `segment_balance` am Ende 0 ist, kann die neue Ziffernreihe durch + // Umlegungen realisiert werden. + segment_balance: isize, + // `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 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, + // wenn diese zu '1' (Ziffer bestehend aus den wenigsten Stäbchen) + // reduziert werden. + occupied_segments_left: usize, + ) -> Option> { + // Es gibt mehrere Backtracking-Bedingungen, die signalisieren, dass + // dieser Pfad zu keiner gültigen Lösung führen kann. + if + // 1. Der Überschuss bzw. Mangel an Stäbchen ist so groß, dass er nicht + // mehr ausgeglichen werden kann, ohne die Maximalzahl an Umlegungen zu + // überschreiten. + segment_balance.abs() as usize > segment_flips_left + // 2. Der Überschuss an Stäbchen ist so groß, dass er nicht mehr + // ausgeglichen kann, selbst wenn alle übrigen Ziffern zu '8' + // aufgefüllt werden. + || segment_balance > vacant_segments_left as isize + // 3. Der Mangel an Stäbchen ist so groß, dass er nicht mehr + // ausgeglichen werden kann, selbst wenn alle übrigen Ziffern zu + // '1' reduziert werden. + || -segment_balance > occupied_segments_left as isize + { + return None; + } + // Es wird immer nur die erste Ziffer betrachtet, und die restlichen + // Ziffern werden rekursiv ergänzt. + match digits.split_first() { + // Falls schon alle Ziffern betrachtet wurden, handelt es sich nur + // um eine gültige Lösung, wenn der Stäbchen-Kontostand + // `segment_balance` gleich 0 ist (s.o.). + None => match segment_balance { + 0 => Some(Vec::new()), + _ => None, + }, + Some((digit, rest)) => { + // Die Anzahl der Stäbchen, aus der die erste Ziffer besteht. + let digit_num_sticks = digit.num_sticks(); + // `vacant_segments_left` und `occupied_segments_left` müssen + // bezogen auf die restlichen Stäbchen angepasst werden. + // '8', die Ziffer bestehend aus den meisten Stäbchen, enthält + // 7 Stäbchen. + let new_vacant_segments_left = vacant_segments_left - (7 - digit_num_sticks); + // '1', die Ziffer bestehend aus den wenigsten Stäbchen, + // enthält 2 Stäbchen. + let new_occupied_segments_left = occupied_segments_left - (digit_num_sticks - 2); + + // Es wird versucht, die erste Ziffer zu maximieren. Dafür + // werden alle möglichen Hex-Ziffern absteigend durchgegangen + // und jeweils versucht, die erste Ziffer auf die gewählte + // Ziffer zu setzen und davon ausgehend die restlichen Ziffern + // anzupassen, sodass am Ende die gefundene maximale Hex-Zahl + // durch eine nicht zu hohe Anzahl an Umlegungen erreicht + // werden kann. + for candidate_digit in (0x0..=0xF).rev().map(HexDigit) { + // `segment_num_difference` ist die Differenz zwischen der + // alten und der neuen Anzahl an Stäbchen für die erste + // Ziffer. + let segment_num_difference = + digit_num_sticks as isize - candidate_digit.num_sticks() as isize; + // `num_required_segment_flips` ist die erforderliche + // Anzahl an "Stäbchen-Flips" (s.o.), um von der alten + // ersten Ziffer zur neuen zu kommen. + let num_required_segment_flips = + digit.num_required_segment_flips(candidate_digit); + + // Der "Stäbchen-Kontostand" sowie die noch verfügbare + // Anzahl an "Stäbchen-Flips" werden bezogen auf die + // restlichen Ziffern angepasst. + let new_segment_balance = segment_balance + segment_num_difference; + let new_segment_flips_left = + match segment_flips_left.checked_sub(num_required_segment_flips) { + // Wenn schon die Änderung der ersten Ziffer nicht + // mehr mit den übrigen "Stäbchen-Flips" zu + // bewerkstelligen ist, kann sofort zum + // nächstniedrigeren Wert für die erste Ziffer + // übergegangen werden. + None => continue, + Some(x) => x, + }; + + match (new_segment_flips_left, new_segment_balance) { + // Wenn keine weiteren Umlegungen mehr möglich sind und + // es keinen Mangel oder Überschuss an Stäbchen gibt, + // ist die Lösung gefunden. Die restlichen Ziffern + // bleiben unverändert. + (0, 0) => { + let mut ret = vec![candidate_digit]; + ret.append(&mut rest.to_vec()); + return Some(ret); + } + // Wenn keine weiteren Umlegungen mehr möglich sind, + // aber es einen Mangel oder Überschuss an Stäbchen + // gibt, wird der nächstniedrigere Wert für die erste + // Ziffer probiert. + (0, _) => continue, + // Ansonsten wird versucht, die restlichen Ziffern + // rekursiv zu maximieren. + (_, _) => { + let mut new_rest = match solve_pt1_internal( + rest, + new_segment_balance, + new_segment_flips_left, + new_vacant_segments_left, + new_occupied_segments_left, + ) { + // Falls dies nicht gelingt, wird der + // nächstniedrigere Wert für die erste Ziffer + // probiert. + None => continue, + Some(x) => x, + }; + let mut ret = vec![candidate_digit]; + ret.append(&mut new_rest); + return Some(ret); + } + } + } + // Der Pfad wird verworfen, da unter den gegebenen Bedingungen + // für keinen Wert der ersten Ziffer eine gültige neue + // Ziffernfolge gefunden werden konnte. + None + } + } + } + + // Die Maximalzahl an "Stäbchen-Flips" ist zweimal die Maximalzahl an + // Umlegungen, da eine Umlegung aus zwei "Stäbchen-Flips" besteht: an einer + // Position wird ein Stäbchen entfernt und an einer zweiten ein Stäbchen + // abgelegt. + let max_segment_flips = 2 * task.max_moves; + // Die Startwerte für `vacant_segments_left` und `occupied_segments_left` + // werden ermittelt, indem einmal über alle Ziffern iteriert wird. + let (initial_vacant_segments, initial_occupied_segments) = task.number.digits.iter().fold( + (0, 0), + |(acc_vacant_segments, acc_occupied_segments), digit| { + let num_sticks = digit.num_sticks(); + ( + acc_vacant_segments + (7 - num_sticks), + acc_occupied_segments + (num_sticks - 2), + ) + }, + ); + + solve_pt1_internal( + &task.number.digits, + 0, + max_segment_flips, + initial_vacant_segments, + initial_occupied_segments, + ) + .unwrap() +} + +// Implementiert den zweiten Teil des Algorithmus, der aus der gegebenen +// Hex-Zahl und der errechneten größtmöglichen Hex-Zahl eine Abfolge von +// Umlegungen erzeugt. +fn solve_pt2(start: &[HexDigit], end: &[HexDigit]) -> Vec { + // Zunächst werden die beiden Hex-Zahlen jeweils zu einem Array von + // Siebensegmentanzeigen konvertiert. + let start_state = start + .into_iter() + .map(|digit| digit.to_seven_segments()) + .collect::>(); + let end_state = end + .into_iter() + .map(|digit| digit.to_seven_segments()) + .collect::>(); + + // 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 { + display_idx: usize, + segment_idx: u8, + } + + 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, und die nicht schon durch eine + // Umlegung innerhalb einer Siebensegmentanzeige richtiggestellt werden + // konnten. + let mut unmatched_on_flips: Vec = Vec::new(); + let mut unmatched_off_flips: Vec = 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::::new(); + let mut off_flips = VecDeque::::new(); + + for (segment_idx, (segment_start, segment_end)) in segments_start + .into_iter() + .zip(segments_end.into_iter()) + .enumerate() + { + match (segment_start, segment_end) { + (false, true) => on_flips.push_back(segment_idx as u8), + (true, false) => off_flips.push_back(segment_idx as u8), + _ => {} + } + } + + // `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].toggle(on_flip); + current_state[display_idx].toggle(off_flip); + 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!(unmatched_on_flips.len(), unmatched_off_flips.len()); + + // 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].toggle(on_flip.segment_idx); + current_state[off_flip.display_idx].toggle(off_flip.segment_idx); + states.push(SevenSegmentDisplayRow { + displays: current_state.clone(), + }) + } + + states +} + +impl HexDigit { + // Stellt eine Hex-Ziffer auf einer Siebensegmentanzeige dar. + fn to_seven_segments(self) -> SevenSegmentDisplay { + let segments = match self.0 { + 0x0 => 0b0111111, + 0x1 => 0b0000110, + 0x2 => 0b1011011, + 0x3 => 0b1001111, + 0x4 => 0b1100110, + 0x5 => 0b1101101, + 0x6 => 0b1111101, + 0x7 => 0b0000111, + 0x8 => 0b1111111, + 0x9 => 0b1101111, + 0xA => 0b1110111, + 0xB => 0b1111100, + 0xC => 0b0111001, + 0xD => 0b1011110, + 0xE => 0b1111001, + 0xF => 0b1110001, + _ => unreachable!(), + }; + SevenSegmentDisplay(segments) + } + + // Gibt die Anzahl der Stäbchen zurück, die für die Darstellung dieser + // Hex-Ziffer auf einer Siebensegmentanzeige benötigt werden. + fn num_sticks(self) -> usize { + self.to_seven_segments().0.count_ones() as usize + } + + // Gibt die Anzahl der "Stäbchen-Flips" zurück, die benötigt werden, um + // von der Siebensegmentdarstellung dieser Hex-Ziffer zu der einer anderen + // zu gelangen. + fn num_required_segment_flips(self, other: Self) -> usize { + (self.to_seven_segments().0 ^ other.to_seven_segments().0).count_ones() as usize + } +} + +impl SevenSegmentDisplay { + // Gibt das `idx`-te Segment dieser Siebensegmentanzeige zurück. + fn get(self, idx: u8) -> bool { + self.0 & (1 << idx) != 0 + } + + // Schaltet das `idx`-te Segmente dieser Siebensegmentanzeige um. + fn toggle(&mut self, idx: u8) { + self.0 ^= 1 << idx; + } +} + +// Iterator über die Segmente einer Siebensegmentanzeige. +struct SevenSegmentDisplayIterator { + idx: u8, + display: SevenSegmentDisplay, +} + +impl Iterator for SevenSegmentDisplayIterator { + type Item = bool; + + fn next(&mut self) -> Option { + if self.idx <= 7 { + let bit = self.display.get(self.idx); + self.idx += 1; + Some(bit) + } else { + None + } + } +} + +impl IntoIterator for SevenSegmentDisplay { + type Item = bool; + type IntoIter = SevenSegmentDisplayIterator; + + fn into_iter(self) -> Self::IntoIter { + SevenSegmentDisplayIterator { + idx: 0, + display: self, + } + } +} + +// Einstiegspunkt für das Programm. +fn main() { + let task_file_name = match env::args().nth(1) { + Some(x) => x, + None => { + eprintln!("Nutzung: aufgabe3 "); + process::exit(1); + } + }; + 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 start = time::Instant::now(); + let solution = solve_task(task); + let elapsed = start.elapsed(); + + println!("{}", solution); + println!("Laufzeit ohne I/O: {:?}", elapsed); +} + +// Liest eine Aufgabe im Format der Beispielaufgaben ein. +impl TryFrom<&str> for Task { + type Error = (); + + fn try_from(value: &str) -> Result { + let mut lines = value.lines(); + let number_str = lines.next().ok_or(())?; + let max_moves_str = lines.next().ok_or(())?; + let number = HexNumber::try_from(number_str)?; + let max_moves = usize::from_str(max_moves_str).map_err(|_| ())?; + + Ok(Task { number, max_moves }) + } +} + +// Formatiert die Lösung zur Ausgabe. +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)?; + } + 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)?; + Ok(()) + } +} + +// Liest eine Hex-Ziffer aus einem ASCII-Zeichen. +impl TryFrom for HexDigit { + type Error = (); + + fn try_from(c: char) -> Result { + match c { + '0' => Ok(Self(0x0)), + '1' => Ok(Self(0x1)), + '2' => Ok(Self(0x2)), + '3' => Ok(Self(0x3)), + '4' => Ok(Self(0x4)), + '5' => Ok(Self(0x5)), + '6' => Ok(Self(0x6)), + '7' => Ok(Self(0x7)), + '8' => Ok(Self(0x8)), + '9' => Ok(Self(0x9)), + 'A' => Ok(Self(0xA)), + 'B' => Ok(Self(0xB)), + 'C' => Ok(Self(0xC)), + 'D' => Ok(Self(0xD)), + 'E' => Ok(Self(0xE)), + 'F' => Ok(Self(0xF)), + _ => Err(()), + } + } +} + +// Stellt eine Hex-Ziffer als ASCII-Zeichen dar. +impl Display for HexDigit { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + let char = match self.0 { + 0x0 => '0', + 0x1 => '1', + 0x2 => '2', + 0x3 => '3', + 0x4 => '4', + 0x5 => '5', + 0x6 => '6', + 0x7 => '7', + 0x8 => '8', + 0x9 => '9', + 0xA => 'A', + 0xB => 'B', + 0xC => 'C', + 0xD => 'D', + 0xE => 'E', + 0xF => 'F', + _ => unreachable!(), + }; + f.write_char(char) + } +} + +// Liest eine Hex-Zahl aus einem ASCII-String. +impl TryFrom<&str> for HexNumber { + type Error = (); + + fn try_from(value: &str) -> Result { + let digits = value + .chars() + .map(|c| HexDigit::try_from(c)) + .collect::, ()>>()?; + + Ok(HexNumber { digits }) + } +} + +// Stellt eine Hex-Zahl als ASCII-String dar. +impl Display for HexNumber { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + for digit in &self.digits { + digit.fmt(f)?; + } + Ok(()) + } +} + +// Stellt eine Siebensegmentanzeige mithilfe der Zeichen des Unicode-Blocks +// "Box Drawing" dar. +impl SevenSegmentDisplay { + fn to_unicode(&self) -> [[char; 2]; 3] { + [ + [ + match (self.get(0), self.get(5)) { + (false, false) => ' ', + (false, true) => '╻', + (true, false) => '╺', + (true, true) => '┏', + }, + match (self.get(0), self.get(1)) { + (false, false) => ' ', + (false, true) => '╻', + (true, false) => '╸', + (true, true) => '┓', + }, + ], + [ + match (self.get(4), self.get(5), self.get(6)) { + (false, false, false) => ' ', + (false, false, true) => '╺', + (false, true, false) => '╹', + (false, true, true) => '┗', + (true, false, false) => '╻', + (true, false, true) => '┏', + (true, true, false) => '┃', + (true, true, true) => '┣', + }, + match (self.get(1), self.get(2), self.get(6)) { + (false, false, false) => ' ', + (false, false, true) => '╸', + (false, true, false) => '╻', + (false, true, true) => '┓', + (true, false, false) => '╹', + (true, false, true) => '┛', + (true, true, false) => '┃', + (true, true, true) => '┫', + }, + ], + [ + match (self.get(3), self.get(4)) { + (false, false) => ' ', + (false, true) => '╹', + (true, false) => '╺', + (true, true) => '┗', + }, + match (self.get(2), self.get(3)) { + (false, false) => ' ', + (false, true) => '╸', + (true, false) => '╹', + (true, true) => '┛', + }, + ], + ] + } +} + +// 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 { + let displays_as_unicode: Vec<[[char; 2]; 3]> = self + .displays + .iter() + .map(|display| display.to_unicode()) + .collect(); + + for row_idx in 0..3 { + for unicode_digit in displays_as_unicode.iter() { + for char in unicode_digit[row_idx] { + write!(f, "{}", char)?; + } + } + writeln!(f)?; + } + + Ok(()) + } +} -- cgit 1.4.1