diff options
Diffstat (limited to 'aufgabe3/src')
| -rw-r--r-- | aufgabe3/src/main.rs | 224 |
1 files changed, 111 insertions, 113 deletions
diff --git a/aufgabe3/src/main.rs b/aufgabe3/src/main.rs index 556ff9d..fbf554d 100644 --- a/aufgabe3/src/main.rs +++ b/aufgabe3/src/main.rs @@ -24,11 +24,20 @@ struct Task { max_moves: usize, } -// Beschreibt den Zustand einer Siebensegmentanzeige. +// 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([bool; 7]); +struct SevenSegmentDisplay(u8); // Beschreibt den Zustand einer Reihe von Siebensegmentanzeigen. struct SevenSegmentDisplayRow { @@ -68,8 +77,6 @@ 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> { @@ -115,7 +122,6 @@ 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 @@ -126,22 +132,19 @@ fn solve_pt1(task: &Task) -> Vec<HexDigit> { // `segment_balance` gleich 0 ist (s.o.). None => match segment_balance { 0 => Some(Vec::new()), - _ => { - unsafe { BACKTRACK += 1 }; - None - } + _ => None, }, Some((digit, rest)) => { // Die Anzahl der Stäbchen, aus der die erste Ziffer besteht. - let digit_num_segments = digit.num_segments(); + 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_segments); + 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_segments - 2); + 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 @@ -155,7 +158,7 @@ fn solve_pt1(task: &Task) -> Vec<HexDigit> { // alten und der neuen Anzahl an Stäbchen für die erste // Ziffer. let segment_num_difference = - digit_num_segments as isize - candidate_digit.num_segments() as isize; + 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. @@ -217,7 +220,6 @@ 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 } } @@ -233,25 +235,22 @@ fn solve_pt1(task: &Task) -> Vec<HexDigit> { let (initial_vacant_segments, initial_occupied_segments) = task.number.digits.iter().fold( (0, 0), |(acc_vacant_segments, acc_occupied_segments), digit| { - let num_segments = digit.num_segments(); + let num_sticks = digit.num_sticks(); ( - acc_vacant_segments + (7 - num_segments), - acc_occupied_segments + (num_segments - 2), + acc_vacant_segments + (7 - num_sticks), + acc_occupied_segments + (num_sticks - 2), ) }, ); - let ret = solve_pt1_internal( + solve_pt1_internal( &task.number.digits, 0, max_segment_flips, initial_vacant_segments, initial_occupied_segments, ) - .unwrap(); - - println!("backtracks: {}", unsafe { BACKTRACK }); - ret + .unwrap() } // Implementiert den zweiten Teil des Algorithmus, der aus der gegebenen @@ -279,7 +278,7 @@ fn solve_pt2(start: &[HexDigit], end: &[HexDigit]) -> Vec<SevenSegmentDisplayRow // Siebensegmentanzeigen. struct Coordinates { display_idx: usize, - segment_idx: usize, + segment_idx: u8, } let mut current_state = start_state.clone(); @@ -298,18 +297,17 @@ fn solve_pt2(start: &[HexDigit], end: &[HexDigit]) -> Vec<SevenSegmentDisplayRow // 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(); + let mut on_flips = VecDeque::<u8>::new(); + let mut off_flips = VecDeque::<u8>::new(); for (segment_idx, (segment_start, segment_end)) in segments_start - .0 - .iter() - .zip(segments_end.0.iter()) + .into_iter() + .zip(segments_end.into_iter()) .enumerate() { match (segment_start, segment_end) { - (false, true) => on_flips.push_back(segment_idx), - (true, false) => off_flips.push_back(segment_idx), + (false, true) => on_flips.push_back(segment_idx as u8), + (true, false) => off_flips.push_back(segment_idx as u8), _ => {} } } @@ -326,8 +324,8 @@ fn solve_pt2(start: &[HexDigit], end: &[HexDigit]) -> Vec<SevenSegmentDisplayRow .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; + current_state[display_idx].toggle(on_flip); + current_state[display_idx].toggle(off_flip); states.push(SevenSegmentDisplayRow { displays: current_state.clone(), }) @@ -355,8 +353,8 @@ fn solve_pt2(start: &[HexDigit], end: &[HexDigit]) -> Vec<SevenSegmentDisplayRow .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; + 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(), }) @@ -369,47 +367,82 @@ 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], + 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 einer + // Gibt die Anzahl der Stäbchen zurück, die für die Darstellung dieser // Hex-Ziffer auf einer Siebensegmentanzeige benötigt werden. - fn num_segments(self) -> usize { - self.to_seven_segments() - .0 - .into_iter() - .filter(|x| *x) - .count() + 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 einer Hex-Ziffer zu der einer anderen + // 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 - .into_iter() - .zip(other.to_seven_segments().0.into_iter()) - .filter(|(segment_self, segment_other)| *segment_self != *segment_other) - .count() + (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<Self::Item> { + 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, + } } } @@ -425,46 +458,12 @@ 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 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 = time::Instant::now(); + let solution = solve_task(task); + let elapsed = start.elapsed(); - // 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); + println!("{}", solution); + println!("Laufzeit ohne I/O: {:?}", elapsed); } // Liest eine Aufgabe im Format der Beispielaufgaben ein. @@ -486,9 +485,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)?; @@ -577,16 +576,15 @@ impl Display for HexNumber { // "Box Drawing" dar. impl SevenSegmentDisplay { fn to_unicode(&self) -> [[char; 2]; 3] { - let s = self.0; [ [ - match (s[0], s[5]) { + match (self.get(0), self.get(5)) { (false, false) => ' ', (false, true) => '╻', (true, false) => '╺', (true, true) => '┏', }, - match (s[0], s[1]) { + match (self.get(0), self.get(1)) { (false, false) => ' ', (false, true) => '╻', (true, false) => '╸', @@ -594,7 +592,7 @@ impl SevenSegmentDisplay { }, ], [ - match (s[4], s[5], s[6]) { + match (self.get(4), self.get(5), self.get(6)) { (false, false, false) => ' ', (false, false, true) => '╺', (false, true, false) => '╹', @@ -604,7 +602,7 @@ impl SevenSegmentDisplay { (true, true, false) => '┃', (true, true, true) => '┣', }, - match (s[1], s[2], s[6]) { + match (self.get(1), self.get(2), self.get(6)) { (false, false, false) => ' ', (false, false, true) => '╸', (false, true, false) => '╻', @@ -616,13 +614,13 @@ impl SevenSegmentDisplay { }, ], [ - match (s[3], s[4]) { + match (self.get(3), self.get(4)) { (false, false) => ' ', (false, true) => '╹', (true, false) => '╺', (true, true) => '┗', }, - match (s[2], s[3]) { + match (self.get(2), self.get(3)) { (false, false) => ' ', (false, true) => '╸', (true, false) => '╹', |