From 56880de7ce4debd444fff85b0c45fdb1c4212e18 Mon Sep 17 00:00:00 2001 From: Malte Voos Date: Wed, 30 Mar 2022 20:01:39 +0200 Subject: aufgabe 3: cleanup and comments --- aufgabe3/src/main.rs | 292 +++++++++++++++++++++++++++++---------------------- 1 file changed, 164 insertions(+), 128 deletions(-) diff --git a/aufgabe3/src/main.rs b/aufgabe3/src/main.rs index 94b8fa5..beb6484 100644 --- a/aufgabe3/src/main.rs +++ b/aufgabe3/src/main.rs @@ -5,12 +5,34 @@ use std::fs; use std::process; use std::str::FromStr; -// Typ, der eine zu lösende Aufgabe beschreibt. +// 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. +// Die Reihenfolge der Segmente entspricht dieser Abbildung: +// https://en.wikipedia.org/wiki/Seven-segment_display#/media/File:7_Segment_Display_with_Labeled_Segments.svg +#[derive(Clone, Copy)] +struct SevenSegmentDisplay([bool; 7]); + +// 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. @@ -28,6 +50,23 @@ struct Solution { 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_possible_number = solve_pt1(&task); + let states = solve_pt2(&task.number.digits, &greatest_possible_number); + + Solution { + initial: task.number, + r#final: HexNumber { + digits: greatest_possible_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 { @@ -114,7 +153,7 @@ fn solve_pt1(task: &Task) -> Vec { // 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); + 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 @@ -209,51 +248,66 @@ fn solve_pt1(task: &Task) -> Vec { // Hex-Zahl und der errechneten größtmöglichen Hex-Zahl eine Abfolge von // Umlegungen erzeugt. fn solve_pt2(start: &[HexDigit], end: &[HexDigit]) -> Vec { - let start_state = start.into_iter().map(|digit| digit.to_seven_segments()); - let end_state = end.into_iter().map(|digit| digit.to_seven_segments()); - - struct Coordinate { - digit_idx: usize, + // 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::>(); + + // Beschreibt die Position eines Segments in einer Reihe von + // Siebensegmentanzeigen. + struct Coordinates { + display_idx: usize, segment_idx: usize, } - let mut on_flips: Vec = Vec::new(); - let mut off_flips: Vec = Vec::new(); + // 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 = Vec::new(); + let mut off_flips: Vec = Vec::new(); - for (digit_idx, (segments_start, segments_end)) in - start_state.clone().zip(end_state).enumerate() + for (display_idx, (segments_start, segments_end)) in + start_state.iter().zip(end_state.iter()).enumerate() { for (segment_idx, (segment_start, segment_end)) in segments_start .0 - .into_iter() - .zip(segments_end.0.into_iter()) + .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 { - digit_idx, - segment_idx, - }), - (true, false) => off_flips.push(Coordinate { - digit_idx, - segment_idx, - }), + (false, true) => on_flips.push(coordinate), + (true, false) => off_flips.push(coordinate), _ => {} } } } + // Sanity Check assert_eq!(on_flips.len(), off_flips.len()); - let start_state: Vec = start_state.collect(); let mut ret = vec![SevenSegmentDisplayRow { displays: start_state.clone(), }]; + // 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()) { - current_state[on_flip.digit_idx].0[on_flip.segment_idx] = true; - current_state[off_flip.digit_idx].0[off_flip.segment_idx] = false; + 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 { displays: current_state.clone(), }) @@ -262,21 +316,55 @@ fn solve_pt2(start: &[HexDigit], end: &[HexDigit]) -> Vec Solution { - let greatest_possible_number = solve_pt1(&task); - let states = solve_pt2(&task.number.digits, &greatest_possible_number); +impl HexDigit { + // Stellt eine Hex-Ziffer auf einer Siebensegmentanzeige dar. + fn to_seven_segments(self) -> SevenSegmentDisplay { + let segments = match self.0 { + 0x0 => [true, true, true, true, true, true, false], + 0x1 => [false, true, true, false, false, false, false], + 0x2 => [true, true, false, true, true, false, true], + 0x3 => [true, true, true, true, false, false, true], + 0x4 => [false, true, true, false, false, true, true], + 0x5 => [true, false, true, true, false, true, true], + 0x6 => [true, false, true, true, true, true, true], + 0x7 => [true, true, true, false, false, false, false], + 0x8 => [true, true, true, true, true, true, true], + 0x9 => [true, true, true, true, false, true, true], + 0xA => [true, true, true, false, true, true, true], + 0xB => [false, false, true, true, true, true, true], + 0xC => [true, false, false, true, true, true, false], + 0xD => [false, true, true, true, true, false, true], + 0xE => [true, false, false, true, true, true, true], + 0xF => [true, false, false, false, true, true, true], + _ => unreachable!(), + }; + SevenSegmentDisplay(segments) + } - Solution { - initial: task.number, - r#final: HexNumber { - digits: greatest_possible_number, - }, - max_moves: task.max_moves, - used_moves: states.len() - 1, - states, + // Gibt die Anzahl der Stäbchen zurück, die für die Darstellung einer + // Hex-Ziffer auf einer Siebensegmentanzeige benötigt werden. + fn num_segments(self) -> usize { + self.to_seven_segments() + .0 + .into_iter() + .filter(|x| *x) + .count() + } + + // Gibt die Anzahl der "Stäbchen-Flips" zurück, die benötigt werden, um + // von der Siebensegmentdarstellung einer Hex-Ziffer zu der einer anderen + // zu gelangen. + fn num_required_segment_flips(self, other: Self) -> usize { + self.to_seven_segments() + .0 + .into_iter() + .zip(other.to_seven_segments().0.into_iter()) + .filter(|(segment_self, segment_other)| *segment_self != *segment_other) + .count() } } +// Einstiegspunkt für das Programm. fn main() { let task_file_name = match env::args().nth(1) { Some(x) => x, @@ -292,6 +380,7 @@ fn main() { print!("{}", solution) } +// Liest eine Aufgabe im Format der Beispielaufgaben ein. impl TryFrom<&str> for Task { type Error = (); @@ -306,9 +395,21 @@ impl TryFrom<&str> for Task { } } -#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] -struct HexDigit(u8); +// 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 = (); @@ -335,9 +436,10 @@ impl TryFrom for HexDigit { } } -impl From for char { - fn from(digit: HexDigit) -> Self { - match digit.0 { +// 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', @@ -355,16 +457,26 @@ impl From for char { 0xE => 'E', 0xF => 'F', _ => unreachable!(), - } + }; + f.write_char(char) } } -impl Display for HexDigit { - fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - f.write_char((*self).into()) +// 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 { @@ -374,10 +486,8 @@ impl Display for HexNumber { } } -// Reihenfolge wie hier: https://en.wikipedia.org/wiki/Seven-segment_display#/media/File:7_Segment_Display_with_Labeled_Segments.svg -#[derive(Clone, Copy, PartialEq, Eq)] -struct SevenSegmentDisplay([bool; 7]); - +// Stellt eine Siebensegmentanzeige mithilfe von Zeichen des Unicode-Blocks +// "Box Drawing" dar. impl SevenSegmentDisplay { fn to_unicode(&self) -> [[char; 2]; 3] { let s = self.0; @@ -436,57 +546,8 @@ impl SevenSegmentDisplay { } } -impl HexDigit { - fn to_seven_segments(&self) -> SevenSegmentDisplay { - let segments = match self.0 { - 0x0 => [true, true, true, true, true, true, false], - 0x1 => [false, true, true, false, false, false, false], - 0x2 => [true, true, false, true, true, false, true], - 0x3 => [true, true, true, true, false, false, true], - 0x4 => [false, true, true, false, false, true, true], - 0x5 => [true, false, true, true, false, true, true], - 0x6 => [true, false, true, true, true, true, true], - 0x7 => [true, true, true, false, false, false, false], - 0x8 => [true, true, true, true, true, true, true], - 0x9 => [true, true, true, true, false, true, true], - 0xA => [true, true, true, false, true, true, true], - 0xB => [false, false, true, true, true, true, true], - 0xC => [true, false, false, true, true, true, false], - 0xD => [false, true, true, true, true, false, true], - 0xE => [true, false, false, true, true, true, true], - 0xF => [true, false, false, false, true, true, true], - _ => unreachable!(), - }; - SevenSegmentDisplay(segments) - } - - fn num_segments(&self) -> usize { - self.to_seven_segments() - .0 - .into_iter() - .filter(|x| *x) - .count() - } - - fn num_required_segment_flips(&self, other: &Self) -> usize { - self.to_seven_segments() - .0 - .into_iter() - .zip(other.to_seven_segments().0.into_iter()) - .filter(|(segment_self, segment_other)| *segment_self != *segment_other) - .count() - } -} - -// in lesereihenfolge -struct HexNumber { - digits: Vec, -} - -struct SevenSegmentDisplayRow { - displays: Vec, -} - +// Formatiert eine Reihe von Siebensegmentanzeigen mithilfe von 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 @@ -497,38 +558,13 @@ impl Display for SevenSegmentDisplayRow { for row_idx in 0..3 { for unicode_digit in displays_as_unicode.iter() { - let row = unicode_digit[row_idx].into_iter().collect::(); - write!(f, "{}", row)?; + for char in unicode_digit[row_idx] { + write!(f, "{}", char)?; + } } - writeln!(f, "")?; + writeln!(f)?; } Ok(()) } } - -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(()) - } -} - -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 }) - } -} -- cgit 1.4.1