aufgabe 3 implementierung

1 files changed, 364 insertions, 0 deletions

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 <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);
+    println!("{}", solution)
+}
+
+struct Task {
+    number: HexNumber,
+    max_moves: u32,
+}
+
+struct Solution {
+    states: Vec<SevenSegmentDisplayRow>,
+}
+
+fn solve_pt1(task: &Task) -> Vec<HexDigit> {
+    fn solve_pt1_internal(
+        state: &[HexDigit],
+        segment_balance: i32,
+        segment_flips_left: u32,
+        free_segments_left: u32,
+    ) -> Option<Vec<HexDigit>> {
+        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<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());
+
+    struct Coordinate {
+        digit_idx: usize,
+        segment_idx: usize,
+    }
+
+    let mut on_flips: Vec<Coordinate> = Vec::new();
+    let mut off_flips: Vec<Coordinate> = 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<SevenSegmentDisplay> = 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<Self, Self::Error> {
+        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<char> for HexDigit {
+    type Error = ();
+
+    fn try_from(c: char) -> Result<Self, Self::Error> {
+        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<HexDigit>,
+}
+
+struct SevenSegmentDisplayRow {
+    displays: Vec<SevenSegmentDisplay>,
+}
+
+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::<String>();
+                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<Self, Self::Error> {
+        let digits = value
+            .chars()
+            .map(|c| HexDigit::try_from(c))
+            .collect::<Result<Vec<HexDigit>, ()>>()?;
+
+        Ok(HexNumber { digits })
+    }
+}