path: root/aufgabe3/src/main.rs

use std::env;
use std::fmt::Display;
use std::fmt::Write;
use std::fs;
use std::process;
use std::str::FromStr;

// Typ, der eine zu lösende Aufgabe beschreibt.
struct Task {
    number: HexNumber,
    max_moves: usize,
}

// Vom Algorithmus zurückgegebene Lösung.
// Der Typ enthält ein paar redundante Informationen, die aber die Ausgabe des
// Programms anschaulicher machen.
struct Solution {
    // Die gegebene Anfangs-Hex-Zahl.
    initial: HexNumber,
    // Alle Zwischenstände zwischen den Umlegungen, einschließlich des Anfangs-
    // und Endzustandes.
    states: Vec<SevenSegmentDisplayRow>,
    // Die ermittelte größtmögliche Hex-Zahl.
    r#final: HexNumber,
    // Die gegebene Maximalzahl an Umlegungen.
    max_moves: usize,
    // Die Anzahl der tatsächlich genutzten Umlegungen.
    used_moves: usize,
}

// Implementiert den ersten Teil des Algorithmus, der aus einer Aufgabe die
// größtmögliche Hex-Zahl errechnet.
fn solve_pt1(task: &Task) -> Vec<HexDigit> {
    // `solve_pt1_internal` ist der rekursive Teil der Funktion, der versucht,
    // den gegebenen Ausschnitt der Hex-Zahl zu maximieren.
    fn solve_pt1_internal(
        // Der zu maximierende Ausschnitt der Hex-Zahl.
        digits: &[HexDigit],
        // `segment_balance` enthält im Laufe der Rekursion immer den
        // "Kontostand" der Stäbchen. Wenn es einen Überschuss bzw. Mangel an
        // Stäbchen gibt, ist `segment_balance` positiv bzw. negativ. Nur wenn
        // `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: 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.
        vacant_segments_left: usize,
        // `occupied_segments_left` gibt an, wie viele fehlende Stäbchen
        // theoretisch noch aus den hinteren Ziffern entnommen werden könnten,
        // wenn diese zu '1' (Ziffer bestehend aus den wenigsten Stäbchen)
        // reduziert werden.
        occupied_segments_left: usize,
    ) -> Option<Vec<HexDigit>> {
        // Es gibt mehrere Backtracking-Bedingungen, die signalisieren, dass
        // dieser Pfad zu keiner gültigen Lösung führen kann.
        if
        // 1. Der Überschuss bzw. Mangel an Stäbchen ist so groß, dass er nicht
        // mehr ausgeglichen werden kann, ohne die Maximalzahl an Umlegungen zu
        // überschreiten.
        segment_balance.abs() as usize > segment_flips_left
            // 2. Der Überschuss an Stäbchen ist so groß, dass er nicht mehr
            // ausgeglichen kann, selbst wenn alle übrigen Ziffern zu '8'
            // aufgefüllt werden.
            || segment_balance > vacant_segments_left as isize
            // 3. Der Mangel an Stäbchen ist so groß, dass er nicht mehr
            // ausgeglichen werden kann, selbst wenn alle übrigen Ziffern zu
            // '1' reduziert werden.
            || -segment_balance > occupied_segments_left as isize
        {
            return None;
        }
        // Es wird immer nur die erste Ziffer betrachtet, und die restlichen
        // Ziffern werden rekursiv ergänzt.
        match digits.split_first() {
            // Falls schon alle Ziffern betrachtet wurden, handelt es sich nur
            // um eine gültige Lösung, wenn der Stäbchen-Kontostand
            // `segment_balance` gleich 0 ist (s.o.).
            None => match segment_balance {
                0 => Some(Vec::new()),
                _ => None,
            },
            Some((digit, rest)) => {
                // Die Anzahl der Stäbchen, aus der die erste Ziffer besteht.
                let digit_num_segments = digit.num_segments();
                // `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);
                // '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);

                // Es wird versucht, die erste Ziffer zu maximieren. Dafür
                // werden alle möglichen Hex-Ziffern absteigend durchgegangen
                // und jeweils versucht, die erste Ziffer auf die gewählte
                // Ziffer zu setzen und davon ausgehend die restlichen Ziffern
                // anzupassen, sodass am Ende die gefundene maximale Hex-Zahl
                // durch eine nicht zu hohe Anzahl an Umlegungen erreicht
                // werden kann.
                for candidate_digit in (0x0..=0xF).rev().map(HexDigit) {
                    // `segment_num_difference` ist die Differenz zwischen der
                    // 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;
                    // `num_required_segment_flips` ist die erforderliche
                    // Anzahl an "Stäbchen-Flips" (s.o.), um von der alten
                    // ersten Ziffer zur neuen zu kommen.
                    let num_required_segment_flips =
                        digit.num_required_segment_flips(&candidate_digit);

                    // Der "Stäbchen-Kontostand" sowie die noch verfügbare
                    // Anzahl an "Stäbchen-Flips" werden bezogen auf die
                    // restlichen Ziffern angepasst.
                    let new_segment_balance = segment_balance + segment_num_difference;
                    let new_segment_flips_left =
                        match segment_flips_left.checked_sub(num_required_segment_flips) {
                            // Wenn schon die Änderung der ersten Ziffer nicht
                            // mehr mit den übrigen "Stäbchen-Flips" zu
                            // bewerkstelligen ist, kann sofort zum
                            // nächstniedrigeren Wert für die erste Ziffer
                            // übergegangen werden.
                            None => continue,
                            Some(x) => x,
                        };

                    match (new_segment_flips_left, new_segment_balance) {
                        // Wenn keine weiteren Umlegungen mehr möglich sind und
                        // es keinen Mangel oder Überschuss an Stäbchen gibt,
                        // ist die Lösung gefunden. Die restlichen Ziffern
                        // bleiben unverändert.
                        (0, 0) => {
                            let mut ret = vec![candidate_digit];
                            ret.append(&mut rest.to_vec());
                            return Some(ret);
                        }
                        // 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.
                        (0, _) => continue,
                        // Ansonsten wird versucht, die restlichen Ziffern
                        // rekursiv zu maximieren.
                        (_, _) => {
                            let mut new_rest = match solve_pt1_internal(
                                rest,
                                new_segment_balance,
                                new_segment_flips_left,
                                new_vacant_segments_left,
                                new_occupied_segments_left,
                            ) {
                                // Falls dies nicht gelingt, wird der
                                // nächstniedrigere Wert für die erste Ziffer
                                // probiert.
                                None => continue,
                                Some(x) => x,
                            };
                            let mut ret = vec![candidate_digit];
                            ret.append(&mut new_rest);
                            return Some(ret);
                        }
                    }
                }
                // Der Pfad wird verworfen, da unter den gegebenen Bedingungen
                // für keinen Wert der ersten Ziffer eine gültige neue
                // Ziffernfolge gefunden werden konnte.
                None
            }
        }
    }

    // Die Maximalzahl an "Stäbchen-Flips" ist zweimal die Maximalzahl an
    // Umlegungen, da eine Umlegung aus zwei "Stäbchen-Flips" besteht: an einer
    // Position wird ein Stäbchen entfernt und an einer zweiten ein Stäbchen
    // abgelegt.
    let max_segment_flips = 2 * task.max_moves;
    // Die Startwerte für `vacant_segments_left` und `occupied_segments_left`
    // werden ermittelt, indem einmal über alle Ziffern iteriert wird.
    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();
            (
                acc_vacant_segments + (7 - num_segments),
                acc_occupied_segments + (num_segments - 2),
            )
        },
    );

    solve_pt1_internal(
        &task.number.digits,
        0,
        max_segment_flips,
        initial_vacant_segments,
        initial_occupied_segments,
    )
    .unwrap()
}

// Implementiert den zweiten Teil des Algorithmus, der aus der gegebenen
// Hex-Zahl und der errechneten größtmöglichen Hex-Zahl eine Abfolge von
// Umlegungen erzeugt.
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 {
        initial: task.number,
        r#final: HexNumber {
            digits: greatest_possible_number,
        },
        max_moves: task.max_moves,
        used_moves: states.len() - 1,
        states,
    }
}

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);

    print!("{}", solution)
}

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 = usize::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(()),
        }
    }
}

impl From<HexDigit> 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 {
            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]);

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)
    }

    fn num_segments(&self) -> usize {
        self.to_seven_segments()
            .0
            .into_iter()
            .filter(|x| *x)
            .count()
    }

    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()
    }
}

// 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 {
        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(())
    }
}

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 })
    }
}