summaryrefslogtreecommitdiff
path: root/aufgabe3/src
diff options
context:
space:
mode:
Diffstat (limited to 'aufgabe3/src')
-rw-r--r--aufgabe3/src/main.rs175
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 {
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-21 17:42:15 +0000