From 6c028b01bf3c365f15ed0d68af5d3e68f27b0773 Mon Sep 17 00:00:00 2001 From: Malte Voos Date: Sun, 20 Feb 2022 14:04:50 +0100 Subject: aufgabe 3 implementierung --- aufgabe3/src/main.rs | 364 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 364 insertions(+) create mode 100644 aufgabe3/src/main.rs (limited to 'aufgabe3/src/main.rs') diff --git a/aufgabe3/src/main.rs b/aufgabe3/src/main.rs new file mode 100644 index 0000000..8c32ec1 --- /dev/null +++ b/aufgabe3/src/main.rs @@ -0,0 +1,364 @@ +use std::env; +use std::fmt::Display; +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 "); + 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); + println!("{}", solution) +} + +struct Task { + number: HexNumber, + max_moves: u32, +} + +struct Solution { + states: Vec, +} + +fn solve_pt1(task: &Task) -> Vec { + fn solve_pt1_internal( + state: &[HexDigit], + segment_balance: i32, + segment_flips_left: u32, + free_segments_left: u32, + ) -> Option> { + if segment_balance.abs() as u32 > segment_flips_left { + return None; + } + if segment_balance > free_segments_left as i32 { + return None; + } + match state.split_first() { + None => match segment_balance { + 0 => Some(Vec::new()), + _ => None, + }, + Some((digit, rest)) => { + for candidate_digit in (0x0..=0xF).rev().map(HexDigit) { + 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_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); + match (new_segment_flips_left, new_segment_balance) { + (0, 0) => { + let mut ret = vec![candidate_digit]; + ret.append(&mut rest.to_vec()); + return Some(ret); + } + (0, _) => continue, + (_, _) => { + let mut new_rest = match solve_pt1_internal( + rest, + new_segment_balance, + new_segment_flips_left, + new_free_segments_left, + ) { + None => continue, + Some(x) => x, + }; + let mut ret = vec![candidate_digit]; + ret.append(&mut new_rest); + return Some(ret); + } + } + } + None + } + } + } + + 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())); + solve_pt1_internal( + task.number.digits.as_slice(), + 0, + max_segment_flips, + initial_free_segments, + ) + .unwrap() +} + +// TODO: darstellung darf nie komplett geleert werden +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, + segment_idx: usize, + } + + 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 (segment_idx, (segment_start, segment_end)) in segments_start + .0 + .into_iter() + .zip(segments_end.0.into_iter()) + .enumerate() + { + 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, + }), + _ => {} + } + } + } + + assert_eq!(on_flips.len(), off_flips.len()); + + let start_state: Vec = start_state.collect(); + let mut ret = vec![SevenSegmentDisplayRow { + displays: start_state.clone(), + }]; + + 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; + ret.push(SevenSegmentDisplayRow { + displays: current_state.clone(), + }) + } + + ret +} + +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 } +} + +impl TryFrom<&str> for Task { + type Error = (); + + fn try_from(value: &str) -> Result { + let mut lines = value.lines(); + 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(|_| ())?; + + Ok(Task { number, max_moves }) + } +} + +#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +struct HexDigit(u8); + +impl TryFrom for HexDigit { + type Error = (); + + fn try_from(c: char) -> Result { + match c { + '0' => Ok(Self(0x0)), + '1' => Ok(Self(0x1)), + '2' => Ok(Self(0x2)), + '3' => Ok(Self(0x3)), + '4' => Ok(Self(0x4)), + '5' => Ok(Self(0x5)), + '6' => Ok(Self(0x6)), + '7' => Ok(Self(0x7)), + '8' => Ok(Self(0x8)), + '9' => Ok(Self(0x9)), + 'A' => Ok(Self(0xA)), + 'B' => Ok(Self(0xB)), + 'C' => Ok(Self(0xC)), + 'D' => Ok(Self(0xD)), + 'E' => Ok(Self(0xE)), + 'F' => Ok(Self(0xF)), + _ => Err(()), + } + } +} + +// 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]); + +impl SevenSegmentDisplay { + fn to_unicode(&self) -> [[char; 2]; 3] { + let s = self.0; + [ + [ + match (s[0], s[5]) { + (false, false) => ' ', + (false, true) => '╻', + (true, false) => '╺', + (true, true) => '┏', + }, + match (s[0], s[1]) { + (false, false) => ' ', + (false, true) => '╻', + (true, false) => '╸', + (true, true) => '┓', + }, + ], + [ + match (s[4], s[5], s[6]) { + (false, false, false) => ' ', + (false, false, true) => '╺', + (false, true, false) => '╹', + (false, true, true) => '┗', + (true, false, false) => '╻', + (true, false, true) => '┏', + (true, true, false) => '┃', + (true, true, true) => '┣', + }, + match (s[1], s[2], s[6]) { + (false, false, false) => ' ', + (false, false, true) => '╸', + (false, true, false) => '╻', + (false, true, true) => '┓', + (true, false, false) => '╹', + (true, false, true) => '┛', + (true, true, false) => '┃', + (true, true, true) => '┫', + }, + ], + [ + match (s[3], s[4]) { + (false, false) => ' ', + (false, true) => '╹', + (true, false) => '╺', + (true, true) => '┗', + }, + match (s[2], s[3]) { + (false, false) => ' ', + (false, true) => '╸', + (true, false) => '╹', + (true, true) => '┛', + }, + ], + ] + } +} + +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) + } + + // TODO: lookup table? + fn num_segments(&self) -> u32 { + self.to_seven_segments() + .0 + .into_iter() + .filter(|x| *x) + .count() as u32 + } + + fn num_required_segment_flips(&self, other: &Self) -> u32 { + 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 + } +} + +// in lesereihenfolge +struct HexNumber { + digits: Vec, +} + +struct SevenSegmentDisplayRow { + displays: Vec, +} + +impl Display for SevenSegmentDisplayRow { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + let displays_as_unicode: Vec<[[char; 2]; 3]> = self + .displays + .iter() + .map(|display| display.to_unicode()) + .collect(); + + 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)?; + } + writeln!(f, "")?; + } + + Ok(()) + } +} + +impl Display for Solution { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + for state in &self.states { + state.fmt(f)?; + } + 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