From fc4a74355747085f7441b6601907121099e81b65 Mon Sep 17 00:00:00 2001 From: Malte Voos Date: Mon, 21 Mar 2022 16:27:33 +0100 Subject: aufgabe 3 verbesserung --- aufgabe3/src/main.rs | 112 +++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 90 insertions(+), 22 deletions(-) (limited to 'aufgabe3/src/main.rs') diff --git a/aufgabe3/src/main.rs b/aufgabe3/src/main.rs index 8c32ec1..6cb6724 100644 --- a/aufgabe3/src/main.rs +++ b/aufgabe3/src/main.rs @@ -1,5 +1,6 @@ use std::env; use std::fmt::Display; +use std::fmt::Write; use std::fs; use std::process; use std::str::FromStr; @@ -14,8 +15,9 @@ 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); - println!("{}", solution) + let solution = solve_task(task); + + print!("{}", solution) } struct Task { @@ -24,7 +26,11 @@ struct Task { } struct Solution { + initial: HexNumber, states: Vec, + r#final: HexNumber, + max_moves: u32, + used_moves: u32, } fn solve_pt1(task: &Task) -> Vec { @@ -32,12 +38,13 @@ fn solve_pt1(task: &Task) -> Vec { state: &[HexDigit], segment_balance: i32, segment_flips_left: u32, - free_segments_left: u32, + vacant_segments_left: u32, + available_segments_left: u32, ) -> Option> { - if segment_balance.abs() as u32 > segment_flips_left { - return None; - } - if segment_balance > free_segments_left as i32 { + if segment_balance.abs() as u32 > segment_flips_left + || segment_balance > vacant_segments_left as i32 + || -segment_balance > available_segments_left as i32 + { return None; } match state.split_first() { @@ -50,15 +57,19 @@ fn solve_pt1(task: &Task) -> Vec { let digit_num_segments = digit.num_segments(); let segment_num_difference = digit_num_segments as i32 - candidate_digit.num_segments() as i32; - let new_segment_balance = segment_balance + segment_num_difference; let num_required_segment_flips = digit.num_required_segment_flips(&candidate_digit); + + let new_segment_balance = segment_balance + segment_num_difference; let new_segment_flips_left = match segment_flips_left.checked_sub(num_required_segment_flips) { None => continue, Some(x) => x, }; - let new_free_segments_left = free_segments_left - (7 - digit_num_segments); + 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) { (0, 0) => { let mut ret = vec![candidate_digit]; @@ -71,7 +82,8 @@ fn solve_pt1(task: &Task) -> Vec { rest, new_segment_balance, new_segment_flips_left, - new_free_segments_left, + new_vacant_segments_left, + new_available_segments_left, ) { None => continue, Some(x) => x, @@ -88,21 +100,27 @@ fn solve_pt1(task: &Task) -> Vec { } let max_segment_flips = 2 * task.max_moves; - let initial_free_segments = task - .number - .digits - .iter() - .fold(0, |acc, digit| acc + (7 - digit.num_segments())); + let (initial_vacant_segments, initial_available_segments) = task.number.digits.iter().fold( + (0, 0), + |(acc_vacant_segments, acc_available_segments), digit| { + let num_segments = digit.num_segments(); + ( + acc_vacant_segments + (7 - num_segments), + acc_available_segments + (num_segments - 2), + ) + }, + ); solve_pt1_internal( task.number.digits.as_slice(), 0, max_segment_flips, - initial_free_segments, + initial_vacant_segments, + initial_available_segments, ) .unwrap() } -// TODO: darstellung darf nie komplett geleert werden +// TODO: darstellung darf nie komplett geleert werden -> ist erfüllt 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()); @@ -157,11 +175,19 @@ fn solve_pt2(start: &[HexDigit], end: &[HexDigit]) -> Vec Solution { - let greatest_possible_number = solve_pt1(task); +fn solve_task(task: Task) -> Solution { + let greatest_possible_number = solve_pt1(&task); let states = solve_pt2(&task.number.digits, &greatest_possible_number); - Solution { states } + Solution { + initial: task.number, + r#final: HexNumber { + digits: greatest_possible_number, + }, + max_moves: task.max_moves, + used_moves: (states.len() - 1) as u32, + states, + } } impl TryFrom<&str> for Task { @@ -207,7 +233,46 @@ impl TryFrom for HexDigit { } } -// reihenfolge wie hier: https://en.wikipedia.org/wiki/Seven-segment_display#/media/File:7_Segment_Display_with_Labeled_Segments.svg +impl From for char { + fn from(digit: HexDigit) -> Self { + match digit.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!(), + } + } +} + +impl Display for HexDigit { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + f.write_char((*self).into()) + } +} + +impl Display for HexNumber { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + for digit in self.digits.as_slice() { + digit.fmt(f)?; + } + Ok(()) + } +} + +// 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]); @@ -293,7 +358,6 @@ impl HexDigit { SevenSegmentDisplay(segments) } - // TODO: lookup table? fn num_segments(&self) -> u32 { self.to_seven_segments() .0 @@ -343,9 +407,13 @@ impl Display for SevenSegmentDisplayRow { 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(()) } } -- cgit 1.4.1