diff options
Diffstat (limited to 'aufgabe3/src')
| -rw-r--r-- | aufgabe3/src/main.rs | 194 |
1 files changed, 148 insertions, 46 deletions
diff --git a/aufgabe3/src/main.rs b/aufgabe3/src/main.rs index 6cb6724..94b8fa5 100644 --- a/aufgabe3/src/main.rs +++ b/aufgabe3/src/main.rs @@ -5,86 +5,161 @@ use std::fs; use std::process; use std::str::FromStr; -fn main() { - let task_file_name = match env::args().nth(1) { - Some(x) => x, - None => { - eprintln!("Nutzung: aufgabe3 <dateiname>"); - 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 solution = solve_task(task); - - print!("{}", solution) -} - +// Typ, der eine zu lösende Aufgabe beschreibt. struct Task { number: HexNumber, - max_moves: u32, + max_moves: usize, } +// 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 zwischen den Umlegungen, einschließlich des Anfangs- + // und Endzustandes. states: Vec<SevenSegmentDisplayRow>, + // Die ermittelte größtmögliche Hex-Zahl. r#final: HexNumber, - max_moves: u32, - used_moves: u32, + // Die gegebene Maximalzahl an Umlegungen. + max_moves: usize, + // Die Anzahl der tatsächlich genutzten Umlegungen. + used_moves: usize, } +// Implementiert den ersten Teil des Algorithmus, der aus einer Aufgabe die +// größtmögliche Hex-Zahl errechnet. fn solve_pt1(task: &Task) -> Vec<HexDigit> { + // `solve_pt1_internal` ist der rekursive Teil der Funktion, der versucht, + // den gegebenen Ausschnitt der Hex-Zahl zu maximieren. fn solve_pt1_internal( - state: &[HexDigit], - segment_balance: i32, - segment_flips_left: u32, - vacant_segments_left: u32, - available_segments_left: u32, + // 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 Stäbchen-Positionen 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. + 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<Vec<HexDigit>> { - if segment_balance.abs() as u32 > segment_flips_left - || segment_balance > vacant_segments_left as i32 - || -segment_balance > available_segments_left as i32 + // 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; } - match state.split_first() { + // 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_segments = digit.num_segments(); + // `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_segments); + // '1', die Ziffer bestehend aus den wenigsten Stäbchen, + // enthält 2 Stäbchen. + let new_occupied_segments_left = occupied_segments_left - (digit_num_segments - 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) { - let digit_num_segments = digit.num_segments(); + // `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_segments as i32 - candidate_digit.num_segments() as i32; + digit_num_segments as isize - candidate_digit.num_segments() 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, }; - let new_vacant_segments_left = vacant_segments_left - (7 - digit_num_segments); - let new_available_segments_left = - available_segments_left - (digit_num_segments - 2); 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, führt dieser Pfad zu keiner Lösung. Es 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_available_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, }; @@ -94,33 +169,45 @@ 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. 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; - let (initial_vacant_segments, initial_available_segments) = task.number.digits.iter().fold( + // 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_available_segments), digit| { + |(acc_vacant_segments, acc_occupied_segments), digit| { let num_segments = digit.num_segments(); ( acc_vacant_segments + (7 - num_segments), - acc_available_segments + (num_segments - 2), + acc_occupied_segments + (num_segments - 2), ) }, ); + solve_pt1_internal( - task.number.digits.as_slice(), + &task.number.digits, 0, max_segment_flips, initial_vacant_segments, - initial_available_segments, + initial_occupied_segments, ) .unwrap() } -// TODO: darstellung darf nie komplett geleert werden -> ist erfüllt +// 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<SevenSegmentDisplayRow> { let start_state = start.into_iter().map(|digit| digit.to_seven_segments()); let end_state = end.into_iter().map(|digit| digit.to_seven_segments()); @@ -185,11 +272,26 @@ fn solve_task(task: Task) -> Solution { digits: greatest_possible_number, }, max_moves: task.max_moves, - used_moves: (states.len() - 1) as u32, + used_moves: states.len() - 1, states, } } +fn main() { + let task_file_name = match env::args().nth(1) { + Some(x) => x, + None => { + eprintln!("Nutzung: aufgabe3 <dateiname>"); + 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 solution = solve_task(task); + + print!("{}", solution) +} + impl TryFrom<&str> for Task { type Error = (); @@ -198,7 +300,7 @@ impl TryFrom<&str> for Task { 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 = u32::from_str(max_moves_str).map_err(|_| ())?; + let max_moves = usize::from_str(max_moves_str).map_err(|_| ())?; Ok(Task { number, max_moves }) } @@ -265,7 +367,7 @@ impl Display for HexDigit { impl Display for HexNumber { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { - for digit in self.digits.as_slice() { + for digit in &self.digits { digit.fmt(f)?; } Ok(()) @@ -358,21 +460,21 @@ impl HexDigit { SevenSegmentDisplay(segments) } - fn num_segments(&self) -> u32 { + fn num_segments(&self) -> usize { self.to_seven_segments() .0 .into_iter() .filter(|x| *x) - .count() as u32 + .count() } - fn num_required_segment_flips(&self, other: &Self) -> u32 { + 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() as u32 + .count() } } |