From d0c70ad88b11f412c9d8c6735b74cce1b1ff015b Mon Sep 17 00:00:00 2001
From: Malte Voos <git@mal.tc>
Date: Sat, 20 Aug 2022 14:12:11 +0200
Subject: cleanup

---
 aufgabe3/doc/aufgabe3.tex | 1090 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 1090 insertions(+)
 create mode 100644 aufgabe3/doc/aufgabe3.tex

(limited to 'aufgabe3/doc/aufgabe3.tex')

diff --git a/aufgabe3/doc/aufgabe3.tex b/aufgabe3/doc/aufgabe3.tex
new file mode 100644
index 0000000..3a2b13d
--- /dev/null
+++ b/aufgabe3/doc/aufgabe3.tex
@@ -0,0 +1,1090 @@
+\documentclass[a4paper,10pt,ngerman]{scrartcl}
+\usepackage{babel}
+\usepackage[T1]{fontenc}
+\usepackage[utf8x]{inputenc}
+\usepackage[a4paper,margin=2.5cm,footskip=0.5cm]{geometry}
+
+\newcommand{\Aufgabe}{Aufgabe 3: Hex-Max}
+\newcommand{\TeilnahmeId}{61099}
+\newcommand{\Name}{Malte Voos}
+
+\usepackage{fontspec}
+\setmonofont{mononoki}
+
+% Anführungszeichen
+\usepackage{csquotes}
+\MakeOuterQuote{"}
+
+% Kopf- und Fußzeilen
+\usepackage{scrlayer-scrpage, lastpage}
+\setkomafont{pageheadfoot}{\large\textrm}
+\lohead{\Aufgabe}
+\rohead{Teilnahme-ID: \TeilnahmeId}
+\cfoot*{\thepage{}/\pageref{LastPage}}
+
+% Position des Titels
+\usepackage{titling}
+\setlength{\droptitle}{-1.0cm}
+
+% Für mathematische Befehle und Symbole
+\usepackage{amsmath}
+\usepackage{amssymb}
+\usepackage{amsthm}
+
+\newtheorem{lemma}{Lemma}
+
+\newtheorem{subproblem}{Unterproblem}
+
+\theoremstyle{definition}
+\newtheorem{definition}{Definition}
+
+\usepackage{siunitx}
+
+% Für Bilder
+\usepackage{graphicx}
+
+% Für Algorithmen
+\usepackage{algpseudocode}
+
+\usepackage{float}
+\usepackage{multirow}
+
+\usepackage{color}
+\usepackage{listings}
+\definecolor{GrayCodeBlock}{RGB}{241,241,241}
+\definecolor{BlackText}{RGB}{110,107,94}
+\definecolor{RedTypename}{RGB}{182,86,17}
+\definecolor{GreenString}{RGB}{96,172,57}
+\definecolor{PurpleKeyword}{RGB}{184,84,212}
+\definecolor{GrayComment}{RGB}{170,170,170}
+\definecolor{GoldDocumentation}{RGB}{180,165,45}
+\lstdefinelanguage{rust}
+{
+    columns=fullflexible,
+    keepspaces=true,
+    frame=single,
+    framesep=0pt,
+    framerule=0pt,
+    framexleftmargin=4pt,
+    framexrightmargin=4pt,
+    framextopmargin=5pt,
+    framexbottommargin=3pt,
+    xleftmargin=4pt,
+    xrightmargin=4pt,
+    backgroundcolor=\color{GrayCodeBlock},
+    basicstyle=\ttfamily\color{BlackText}\footnotesize,
+    keywords={
+        true,false,
+        unsafe,async,await,move,
+        use,pub,crate,super,self,mod,
+        struct,enum,fn,const,static,let,mut,ref,type,impl,dyn,trait,where,as,
+        break,continue,if,else,while,for,loop,match,return,yield,in
+    },
+    keywordstyle=\color{PurpleKeyword},
+    ndkeywords={
+        bool,u8,u16,u32,u64,u128,i8,i16,i32,i64,i128,char,str,
+        Self,Option,Some,None,Result,Ok,Err,String,Box,Vec,Rc,Arc,Cell,RefCell,HashMap,BTreeMap,
+        macro_rules
+    },
+    ndkeywordstyle=\color{RedTypename},
+    comment=[l][\color{GrayComment}\slshape]{//},
+    morecomment=[s][\color{GrayComment}\slshape]{/*}{*/},
+    morecomment=[l][\color{GoldDocumentation}\slshape]{///},
+    morecomment=[s][\color{GoldDocumentation}\slshape]{/*!}{*/},
+    morecomment=[l][\color{GoldDocumentation}\slshape]{//!},
+    morecomment=[s][\color{RedTypename}]{\#![}{]},
+    morecomment=[s][\color{RedTypename}]{\#[}{]},
+    stringstyle=\color{GreenString},
+    string=[b]"
+}
+
+% Diese beiden Pakete müssen zuletzt geladen werden
+%\usepackage{hyperref} % Anklickbare Links im Dokument
+\usepackage{cleveref}
+
+% Daten für die Titelseite
+\title{\textbf{\Huge\Aufgabe}}
+\author{\LARGE Teilnahme-ID: \LARGE \TeilnahmeId \\\\
+      \LARGE Bearbeiter/-in dieser Aufgabe: \\ 
+      \LARGE \Name\\\\}
+\date{\LARGE\today}
+
+\begin{document}
+
+\maketitle
+\tableofcontents
+
+\vspace{0.5cm}
+
+\section{Lösungsidee}
+
+Gegeben ist eine Hex-Zahl $z_1$ mit $n$ Ziffern und eine Maximalzahl an Umlegungen $m$. Gesucht ist eine Abfolge von maximal $m$ Umlegungen der in der Siebensegmentdarstellung von $z_1$ enthaltenen Stäbchen, die mit der größtmöglichen auf diese Weise erzeugbaren Hex-Zahl $z_2$ endet. Dabei gilt die zusätzliche Bedingung, dass bei keiner Umlegung die Siebensegmentdarstellung einer Hex-Ziffer komplett geleert werden darf.
+
+\begin{definition}
+  Zwei Hex-Zahlen sind genau dann \textit{verbunden}, wenn ihre Siebensegmentdarstellungen gleich viele Stäbchen beinhalten.
+\end{definition}
+
+\begin{definition}
+  Eine Umlegungs-Abfolge zwischen zwei verbundenen Hex-Zahlen ist genau dann \textit{optimal}, wenn keine andere Umlegungs-Abfolge mit einer geringeren Anzahl an Umlegungen zwischen diesen beiden Hex-Zahlen existiert.
+\end{definition}
+
+\begin{definition}
+  Eine Umlegungs-Abfolge zwischen zwei verbundenen Hex-Zahlen ist genau dann \textit{zulässig}, wenn bei keiner Umlegung die Siebensegmentdarstellung einer Hex-Ziffer komplett geleert wird.
+\end{definition}
+
+\subsection{Zerlegung in Unterprobleme}
+
+Zunächst soll gezeigt werden, dass sich das obige Problem in folgende zwei unabhängige Unterprobleme zerlegen lässt:
+
+\begin{subproblem}
+  Gegeben ist eine Hex-Zahl $z_1$ und eine natürliche Zahl $m$. Welche ist die größte verbundene Hex-Zahl $z_2$, die sich in der Siebensegmentdarstellung in nicht mehr als $2m$ Segmenten von $z_1$ unterscheidet?
+\end{subproblem}
+
+\begin{subproblem}
+  Gegeben sind zwei verbundene Hex-Zahlen $z_1$ und $z_2$. Was ist eine optimale und zulässige Umlegungs-Abfolge von $z_1$ zu $z_2$?
+\end{subproblem}
+
+Die Formulierung von Unterproblem 2 deutet schon folgende Tatsache an:
+
+\begin{lemma}
+  Zwischen jeden zwei verbundenen Hex-Zahlen $z_1$ und $z_2$, deren Siebensegmentdarstellungen sich in $p$ Segmenten unterscheiden, existiert eine optimale und zulässige Umlegungs-Abfolge aus $\frac{p}{2}$ Umlegungen.
+\end{lemma}
+\begin{proof}
+  Sei $D_1$ die Menge der Segmente, in denen $z_1$ ein Stäbchen hat und $z_2$ nicht, und $D_2$ die Menge der Segmente, in denen $z_2$ ein Stäbchen hat und $z_1$ nicht. Da $z_1$ und $z_2$ verbunden sind, ist $|D_1| = |D_2| = \frac{p}{2}$. Jeder Isomorphismus zwischen $D_1$ und $D_2$ entspricht einer Menge von $\frac{p}{2}$ Umlegungen, bei denen jeweils ein Stäbchen von einem Segment in $D_1$ zu einem Segment in $D_2$ umgelegt wird. Alle Umlegungs-Abfolgen, die diese $\frac{p}{2}$ Umlegungen in beliebiger Reihenfolge enthalten, sind optimal, da keine "unnötigen" Umlegungen stattfinden, d.h., dass Stäbchen niemals "zwischengelagert" werden und jede Umlegung die beiden beteiligten Segmente in den gewünschten Endzustand bringt.
+
+  In einigen Fällen kann es aber vorkommen, dass bei einer Ziffer der Start- und Endwert keine gemeinsamen Stäbchen haben (z.B. bei \texttt{1} und \texttt{F}) und dass alle Stäbchen der Ziffer in andere Ziffern umgelegt werden, bevor Stäbchen aus anderen Ziffern in die Ziffer zurückgelegt werden. In solch einem Fall wäre die Umlegungs-Abfolge unzulässig, da die Siebensegmentdarstellung einer Ziffer komplett geleert würde. Um dies zu vermeiden, werden zunächst die jeweils in der selben Ziffer liegenden Segmente aus $D_1$ und $D_2$ paarweise kombiniert. Übrige Segmente, die auf diese Weise nicht zugeordnet werden konnten, werden beliebig mit Segmenten aus anderen Ziffern kombiniert. Dadurch, dass Umlegungen immer priorisiert innerhalb einer Ziffer stattfinden, ist es nicht möglich, dass die Siebensegmentdarstellung einer Ziffer komplett geleert wird. Bei einem so konstruierten Isomorphismus zwischen $D_1$ und $D_2$ ist also jede zugehörige Umlegungs-Abfolge unabhängig von der Reihenfolge der Umlegungen optimal und zulässig.
+\end{proof}
+
+Damit kann das Hex-Max-Problem in die Unterprobleme 1 und 2 zerlegt werden: Die Lösung für Unterproblem 1 liefert die größte verbundene Hex-Zahl $z_2$, die sich in der Siebensegmentdarstellung in nicht mehr als $2m$ Segmenten von $z_1$ unterscheidet. Dies ist auch die größte Hex-Zahl, die mit maximal $m$ Umlegungen in der Siebensegmentdarstellung von $z_1$ erzeugt werden kann, da eine möglicherweise größere Hex-Zahl mit mehr als $2m$ unterschiedlichen Segmenten gemäß Lemma 1 zwangsläufig nur mit mehr als $\frac{2m}{2} = m$ Umlegungen erzeugt werden könnte. Die Lösung für Unterproblem 2 liefert dann eine zulässige Umlegungs-Abfolge von $z_1$ zu $z_2$, die nach Lemma 1 nicht mehr als $\frac{2m}{2} = m$ Umlegungen enthält.
+
+\subsection{Algorithmus für Unterproblem 1}
+
+Der Algorithmus für Unterproblem 1 arbeitet im Großen und Ganzen nach dem Backtracking-Verfahren. Ausgehend von $z_1$ wird rekursiv versucht, die wichtigen (vorderen) Ziffern zu maximieren, indem für für die erste Ziffer absteigend die Werte \texttt{F} bis \texttt{0} gewählt werden und jeweils versucht wird, die restlichen Ziffern rekursiv auf die gleiche Weise zu maximieren. Dabei gibt es mehrere Backtracking-Kriterien, die früh signalisieren, dass der gewählte Pfad im "Backtracking-Baum" zu keiner Lösung führt und daher verworfen werden muss.
+
+Diese Backtracking-Kriterien stützen sich auf einige Variablen, welche im Laufe der Rekursion ständig aktualisiert werden:
+\begin{itemize}
+  \item $b \in \mathbb{Z}$ ist der "Stäbchen-Kontostand", welcher bei negativen Werten den Mangel und bei positiven Werten den Überschuss an Stäbchen angibt. Zu Anfang der Rekursion ist $b = 0$. Wenn beispielsweise die erste Ziffer von \texttt{7} auf \texttt{F} erhöht wird, wird $b$ um $1$ herabgesetzt, da die Siebensegmentdarstellung von \texttt{F} ein Stäbchen mehr enthält als die von \texttt{7} und somit ein Stäbchen "verbraucht" wurde.
+  \item $l \in \mathbb{N}$ gibt an, wie viele Segmente noch "geflippt" (d.h. gefüllt oder geleert) werden können, ohne die Maximalzahl an Umlegungen $m$ zu überschreiten. Gemäß Lemma 1 ist $l$ zu Anfang der Rekursion gleich $2m$. Wenn beispielsweise die erste Ziffer von \texttt{7} auf \texttt{F} erhöht wird, wird $l$ um $5$ herabgesetzt, da sich die Siebensegmentdarstellungen von \texttt{7} und \texttt{F} in $5$ Segmenten unterscheiden.
+  \item $v \in \mathbb{N}$ gibt an, wie viele überschüssige Stäbchen theoretisch noch in den hinteren Ziffern untergebracht werden könnten, wenn diese zu \texttt{8} (Ziffer bestehend aus den meisten Stäbchen) aufgefüllt würden. Zu Anfang der Rekursion ist $v$ gleich der Gesamtanzahl der leeren Segmente in der Siebensegmentdarstellung der Hex-Zahl. Bei jedem rekursiven Aufruf wird $v$ um die Anzahl der leeren Segmente in der zuvor betrachteten Ziffer herabgesetzt.
+  \item $o \in \mathbb{N}$ ist gewissermaßen das Gegenstück zu $v$ und gibt an, wie viele fehlende Stäbchen theoretisch noch aus den hinteren Ziffern entnommen werden könnten, wenn diese zu \texttt{1} (Ziffer bestehend aus den wenigsten Stäbchen) reduziert würden. Zu Anfang der Rekursion ist $o$ gleich der Gesamtanzahl der Stäbchen in der Siebensegmentdarstellung der Hex-Zahl minus $2n$ (die Ziffer \texttt{1} besteht schließlich immer noch aus $2$ Stäbchen). Bei jedem rekursiven Aufruf wird $v$ um [die Anzahl der Stäbchen in der zuvor betrachteten Ziffer minus $2$] herabgesetzt.
+\end{itemize}
+Mit diesen Variablen lassen sich nun folgende Backtracking-Bedingungen aufstellen, welche signalisieren, dass die gewählten ersten Ziffern zu keiner Lösung führen:
+\begin{itemize}
+  \item $|b| > l$: Der Überschuss bzw. Mangel an Stäbchen ist so groß, dass er nicht mehr ausgeglichen werden kann, ohne die Maximalzahl an Umlegungen zu überschreiten.
+  \item $b > v$: Der Überschuss an Stäbchen ist so groß, dass er nicht mehr ausgeglichen werden kann, selbst wenn alle übrigen Ziffern zu \texttt{8} aufgefüllt werden.
+  \item $-b > o$:
+Der Mangel an Stäbchen ist so groß, dass er nicht mehr ausgeglichen werden kann, selbst wenn alle übrigen Ziffern zu \texttt{1} reduziert werden.
+\end{itemize}
+
+Wenn keine dieser Backtracking-Bedingungen erfüllt ist, wird die erste Ziffer der gegebenen Hex-Zahl abgespalten. Falls dies nicht möglich ist, da bereits alle Ziffern betrachtet wurden, handelt es sich nur um eine gültige Lösung, wenn es keinen Mangel oder Überschuss an Stäbchen gibt ($b = 0$).
+
+Falls noch nicht alle Ziffern betrachtet wurden, werden für die erste Ziffer absteigend die Werte \texttt{F} bis \texttt{0} angenommen und jeweils die neuen Werte für $l$ und $b$ berechnet. Wenn bei der Berechnung des neuen $l$ ein negativer Wert entstehen würde, d.h. dass schon die Änderung der ersten Ziffer nicht mehr mit den übrigen "Stäbchen-Flips" zu bewerkstelligen wäre, kann sofort zum nächstniedrigeren Wert für die erste Ziffer übergegangen werden.
+
+Ansonsten hängt das weitere Vorgehen von den neuen Werten für $l$ und $b$ ab:
+
+\begin{itemize}
+  \item $l = 0$; $b = 0$: In diesem Fall sind keine weiteren Umlegungen mehr möglich und es gibt auch keinen Mangel oder Überschuss an Stäbchen. Damit ist die Lösung gefunden; die restlichen Ziffern bleiben unverändert.
+  \item $l = 0$; $b \neq 0$: Es sind keine weiteren Umlegungen mehr möglich, aber es besteht ein Mangel oder Überschuss an Stäbchen. Daher muss zum nächstniedrigeren Wert für die erste Ziffer übergegangen werden.
+  \item $l \neq 0$: Es sind weitere Umlegungen möglich. Mit diesen weiteren Umlegungen wird versucht, die restlichen Ziffern rekursiv zu maximieren. Falls dies gelingt, ist die Lösung gefunden. Anderenfalls wird der nächstniedrigere Wert für die erste Ziffer probiert.
+\end{itemize}
+
+Falls für keinen Wert der ersten Ziffer eine gültige neue Ziffernfolge gefunden werden konnte, wird der Pfad verworfen.
+
+\bigskip
+
+Dieser Algorithmus gibt immer die größtmögliche mit der gegebenen Maximalzahl an Umlegungen erreichbare Hex-Zahl zurück, da stets höhere Ziffernwerte zuerst probiert werden und Pfade nur dann verworfen werden, wenn sie sicher zu keiner Lösung führen.
+
+\subsection{Algorithmus für Unterproblem 2}
+
+Der Algorithmus für Unterproblem 2 ist im Wesentlichen schon im Beweis für Lemma 1 enthalten. Der Vollständigkeit halber wird er hier nochmal in expliziter Form niedergeschrieben.
+
+\begin{enumerate}
+  \item Die beiden gegebenen verbundenen Hex-Zahlen $z_1$ und $z_2$ werden zu ihren jeweiligen Siebensegmentdarstellungen konvertiert.
+  \item Für jede Ziffer-Siebensegmentanzeige der beiden Siebensegmentdarstellungen:
+  \begin{enumerate}
+    \item Die Positionen der Segmente, in denen die Ziffer von $z_1$ ein Stäbchen hat und die Ziffer von $z_2$ nicht, und die Positionen derer, in denen die Ziffer von $z_2$ ein Stäbchen hat und die Ziffer von $z_1$ nicht, werden in zwei Listen $L_1$ bzw. $L_2$ gespeichert.
+    \item Es wird, soweit möglich, je ein Segment aus $L_1$ mit einem aus $L_2$ kombiniert, die entsprechende Umlegung ausgeführt und der Gesamt-Zwischenstand gespeichert.
+    \item Die Positionen übriger Segmente, welche innerhalb der Ziffer keinen "Umlegungs-Partner" gefunden haben, werden für die spätere Verarbeitung analog zu Schritt a) zu zwei Listen $U_1$ bzw. $U_2$ hinzugefügt. Bei $U_1$ und $U_2$ handelt es sich für jede Ziffer um die selbe Liste.
+  \end{enumerate}
+  \item Analog zu Schritt 2b) wird nun je ein Segment aus $U_1$ mit einem aus $U_2$ kombiniert, die entsprechende Umlegung ausgeführt, und der Gesamt-Zwischenstand gespeichert; dieses Mal finden die Umlegungen aber jeweils zwischen verschiedenen Ziffern statt. Da $z_1$ und $z_2$ verbunden sind, enthalten $U_1$ und $U_2$ hier stets gleich viele Segmente.
+  \item Die in den vorherigen Schritten gesammelten Zwischenstände definieren nun eine optimale und zulässige Umlegungs-Abfolge von $z_1$ zu $z_2$. (siehe Lemma 1)
+\end{enumerate}
+
+\subsection{Laufzeitanalyse}
+
+Der Algorithmus für Unterproblem 1 führt Backtracking über $n$ Variablen mit je 16 möglichen Werten durch. Seine Laufzeit ist daher asymptotisch von oben durch $\mathcal{O}(16^n)$ begrenzt. Hier ist anzumerken, dass diese Grenze in der Regel nicht ausgereizt wird, da viele Pfade durch die in Abschnitt 1.2 beschriebenen Backtracking-Kriterien frühzeitig ausgeschlossen werden können.
+
+Der Algorithmus für Unterproblem 2 iteriert über alle $n$ Ziffern, findet dabei die veränderten Segmente und führt dann $k$ Umlegungen aus, mit $k \leq m$. Die Anzahl der ausgeführten Umlegungen $k$ ist aber auch durch die Anzahl der Ziffern begrenzt: Selbst bei beliebig großem $m$ werden nur so viele Umlegungen ausgeführt, wie erforderlich sind, um die größte verbundene Hex-Zahl zu erreichen. Weitere Umlegungen wären dann nur mit einer höheren Anzahl an Ziffern möglich; es gilt offensichtlich $k \in \mathcal{O}(n)$. Die Laufzeit des Algorithmus für Unterproblem 2 ist also insgesamt in $\mathcal{O}(n + n) = \mathcal{O}(n)$.
+
+Damit ist die Laufzeit des Gesamt-Algorithmus für das Hex-Max-Problem in $\mathcal{O}(16^n + n) = \mathcal{O}(16^n)$.
+
+\section{Umsetzung}
+
+Das Programm wurde in der Programmiersprache Rust geschrieben. Die Funktion \texttt{solve\_pt1} implementiert den Algorithmus für Unterproblem 1, die Funktion \texttt{solve\_pt2} den für Unterproblem 2. Die Funktion \texttt{solve\_task} entspricht dem Gesamt-Algorithmus für das Hex-Max-Problem: Sie erhält die eingelesene Aufgabe (Datentyp \texttt{Task}), ruft \texttt{solve\_pt1} und \texttt{solve\_pt2} nacheinander auf, und gibt schließlich die Lösung (Datentyp \texttt{Solution}) zurück.
+
+Um Speicherplatz zu sparen, wird eine Siebensegmentanzeige (Datentyp \texttt{SevenSegmentDisplay}) als 8-Bit-Integer repräsentiert:
+\begin{lstlisting}[language=rust]
+#[derive(Clone, Copy)]
+struct SevenSegmentDisplay(u8);
+\end{lstlisting}
+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 erforderlichen Operationen für Siebensegmentanzeigen wurden mithilfe von bitweisen Operationen realisiert:
+\begin{lstlisting}[language=rust]
+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;
+    }
+}
+\end{lstlisting}
+
+Abgesehen von dieser implementierungsspezifischen Besonderheit entspricht das Programm ziemlich direkt der in Abschnitt 1 beschriebenen Lösungsidee. Für weitere Details zur Implementierung wird auf den angehängten, ausgiebig kommentierten Quellcode verwiesen.
+
+\section{Beispiele}
+
+Zunächst die Beispiele von der BwInf-Webseite:
+
+\begin{verbatim}
+$ AusführbaresProgramm/aufgabe3-x86_64-linux-static Beispieleingaben/hexmax0.txt 
+Gegebene Hex-Zahl: D24
+ ╻╺┓╻╻
+┏┫┏┛┗┫
+┗┛┗╸ ╹
+╺╸╺┓╻╻
+┏┓┏┛┗┫
+┗┛┗╸ ╹
+┏╸╺┓╻╻
+┣╸┏┛┗┫
+┗╸┗╸ ╹
+┏╸┏╸╻╻
+┣╸┣╸┗┫
+┗╸┗╸ ╹
+Größtmögliche Hex-Zahl: EE4
+Gegebene Maximalzahl an Umlegungen: 3
+Anzahl genutzter Umlegungen: 3
+
+Laufzeit ohne I/O: 5.891µs
+
+$ AusführbaresProgramm/aufgabe3-x86_64-linux-static Beispieleingaben/hexmax1.txt
+Gegebene Hex-Zahl: 509C431B55
+┏╸┏┓┏┓┏╸╻╻╺┓ ╻╻ ┏╸┏╸
+┗┓┃┃┗┫┃ ┗┫╺┫ ┃┣┓┗┓┗┓
+╺┛┗┛╺┛┗╸ ╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏┓┏┓┏╸╻╻╺┓ ╻╻ ┏╸┏╸
+┣╸┃┃┗┫┃ ┗┫╺┫ ┃┣┓┗┓┗┓
+┗╸┗┛╺┛┗╸ ╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏┓┏╸╻╻╺┓ ╻╻ ┏╸┏╸
+┣╸┣┓┗┫┃ ┗┫╺┫ ┃┣┓┗┓┗┓
+┗╸┗┛╺┛┗╸ ╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸╻╻╺┓ ╻╻ ┏╸┏╸
+┣╸┣┓┣┓┃ ┗┫╺┫ ┃┣┓┗┓┗┓
+┗╸┗┛┗┛┗╸ ╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸╻╻╺┓ ╻╻ ┏╸┏╸
+┣╸┣┓┣┓┣╸┗┫╺┫ ┃┣┓┗┓┗┓
+╹ ┗┛┗┛┗╸ ╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸┏┓╺┓ ╻╻ ┏╸┏╸
+┣╸┣╸┣┓┣╸┗┫╺┫ ┃┣┓┗┓┗┓
+╹ ┗╸┗┛┗╸ ╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸┏┓╺┓ ╻╻ ┏╸┏╸
+┣╸┣╸┣┓┣╸┣┫╺┫ ┃┣┓┗┓┗┓
+╹ ╹ ┗┛┗╸╹╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸┏┓┏┓ ╻╻ ┏╸┏╸
+┣╸┣╸┣╸┣╸┣┫┗┫ ┃┣┓┗┓┗┓
+╹ ╹ ┗╸┗╸╹╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸┏┓┏┓╺┓╻ ┏╸┏╸
+┣╸┣╸┣╸┣╸┣┫┗┫ ┃┣┓┗┓┗┓
+╹ ╹ ╹ ┗╸╹╹╺┛ ╹┗┛╺┛╺┛
+Größtmögliche Hex-Zahl: FFFEA97B55
+Gegebene Maximalzahl an Umlegungen: 8
+Anzahl genutzter Umlegungen: 8
+
+Laufzeit ohne I/O: 13.251µs
+
+$ AusführbaresProgramm/aufgabe3-x86_64-linux-static Beispieleingaben/hexmax2.txt
+Gegebene Hex-Zahl: 632B29B38F11849015A3BCAEE2CDA0BD496919F8
+┏╸╺┓╺┓╻ ╺┓┏┓╻ ╺┓┏┓┏╸ ╻ ╻┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓╺┫┏┛┣┓┏┛┗┫┣┓╺┫┣┫┣╸ ┃ ┃┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛╺┛┗╸┗┛┗╸╺┛┗┛╺┛┗┛╹  ╹ ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸╺╸╺┓╻ ╺┓┏┓╻ ╺┓┏┓┏╸ ╻ ╻┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┏┓┏┛┣┓┏┛┗┫┣┓╺┫┣┫┣╸ ┃ ┃┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗┛┗╸┗┛┗╸╺┛┗┛╺┛┗┛╹  ╹ ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸╺┓╻ ╺┓┏┓╻ ╺┓┏┓┏╸ ╻ ╻┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┏┛┣┓┏┛┗┫┣┓╺┫┣┫┣╸ ┃ ┃┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗┛┗╸╺┛┗┛╺┛┗┛╹  ╹ ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸╻ ╺┓┏┓╻ ╺┓┏┓┏╸ ╻ ╻┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣┓┏┛┗┫┣┓╺┫┣┫┣╸ ┃ ┃┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗┛┗╸╺┛┗┛╺┛┗┛╹  ╹ ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸╺┓┏┓╻ ╺┓┏┓┏╸ ╻ ╻┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┏┛┗┫┣┓╺┫┣┫┣╸ ┃ ┃┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸╺┛┗┛╺┛┗┛╹  ╹ ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏┓╻ ╺┓┏┓┏╸ ╻ ╻┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┗┫┣┓╺┫┣┫┣╸ ┃ ┃┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸╺┛┗┛╺┛┗┛╹  ╹ ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸╻ ╺┓┏┓┏╸ ╻ ╻┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┣┓┣┓╺┫┣┫┣╸ ┃ ┃┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸┗┛┗┛╺┛┗┛╹  ╹ ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸╺┓┏┓┏╸ ╻ ╻┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┣┓┣╸╺┫┣┫┣╸ ┃ ┃┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸┗┛┗╸╺┛┗┛╹  ╹ ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸╺╸┏┓┏╸ ╻ ╻┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┣┓┣╸┏┓┣┫┣╸ ┃ ┃┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸┗┛┗╸┗┛┗┛╹  ╹ ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸ ╻ ╻┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸ ┃ ┃┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸┗┛┗╸┗╸┗┛╹  ╹ ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸╺╸ ╻┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸ ╻ ┃┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸┗┛┗╸┗╸┗┛╹  ╹ ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸╺╸ ╻┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸╻  ┃┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸┗┛┗╸┗╸┗┛╹ ╹  ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸╺╸╺╸┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸╻  ╻┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸┗┛┗╸┗╸┗┛╹ ╹  ╹┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸╺╸╺╸┏┓╻╻┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸╻ ╻ ┣┫┗┫┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸┗┛┗╸┗╸┗┛╹ ╹ ╹ ┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸╺╸╺╸┏┓┏╸┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸╻ ╻ ┣┫┗┓┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸┗┛┗╸┗╸┗┛╹ ╹ ╹ ┗┛ ╹╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸╺╸╺╸┏┓┏╸┏┓┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸╻ ╻ ┣┫┣╸┗┫┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸┗┛┗╸┗╸┗┛╹ ╹ ╹ ┗┛╹ ╺┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸╺╸╺╸┏┓┏╸┏╸┏┓ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸╻ ╻ ┣┫┣╸┣┓┃┃ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸┗┛┗╸┗╸┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸╺╸╺╸┏┓┏╸┏╸┏╸ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣┓┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸╻ ╻ ┣┫┣╸┣┓┣┓ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗┛┗╸┗╸┗╸┗╸┗┛┗╸┗╸┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸╺╸┏┓┏╸┏╸┏╸ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸┃ ╻ ┣┫┣╸┣┓┣┓ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+┗╸┗╸┗╸┗╸┗╸┗┛┗╸┗╸┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸╺╸┏┓┏╸┏╸┏╸ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸┣╸╻ ┣┫┣╸┣┓┣┓ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ┗╸┗╸┗╸┗╸┗┛┗╸┗╸┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸┏╸┏┓┏╸┏╸┏╸ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸┣╸┃ ┣┫┣╸┣┓┣┓ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ┗╸┗╸┗╸┗┛┗╸┗╸┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸┏╸┏┓┏╸┏╸┏╸ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸┣╸┣╸┣┫┣╸┣┓┣┓ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ┗╸┗╸┗┛┗╸┗╸┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛ ╹╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸┏╸┏┓┏╸┏╸┏╸ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸┣╸┣╸┣┫┣╸┣┓┣┓ ┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ┗╸┗┛┗╸┗╸┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛╺┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸┏╸┏┓┏╸┏╸┏╸ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣┫┣╸┣╸┣╸┣┫┣╸┣┓┣┓╻┃┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ┗┛┗╸┗╸┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸┏╸┏┓┏╸┏╸┏╸ ╻┏╸┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┫┣╸┣╸┣╸┣┫┣╸┣┓┣┓┏┫┗┓┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ┗╸┗╸┗╸┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸┏╸┏┓┏╸┏╸┏╸ ╻┏┓┏┓╺┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┫┣╸┣╸┣╸┣┫┣╸┣┓┣┓┏┫┗┫┣┫╺┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ┗╸┗╸┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸┏╸┏┓┏╸┏╸┏╸ ╻┏┓┏┓┏┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┫┣╸┣╸┣╸┣┫┣╸┣┓┣┓┏┫┗┫┣┫┗┫┣┓┃ ┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗╸┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸┏╸┏┓┏╸┏╸┏╸ ╻┏┓┏┓┏┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┫┣╸┣╸┣╸┣┫┣╸┣┓┣┓┏┫┗┫┣┫┗┫┣┓┣╸┣┫┣╸┣╸┏┛┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗╸┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸┏╸ ╻┏┓┏┓┏┓╻ ┏╸┏┓┏╸┏╸╺┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┓┣╸┣╸┣╸┣┫┣╸┣┓┣┓┏┫┗┫┣┫┗┫┣┓┣╸┣┫┣╸┣╸┏┫┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗┛╹ ╹ ╹ ┗┛╹ ┗┛┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗┛┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸┏╸ ╻┏┓┏┓┏┓╻ ┏╸┏┓┏╸┏╸┏┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┫┣╸┣┓┣┓┏┫┗┫┣┫┗┫┣┓┣╸┣┫┣╸┣╸┣┫┃ ┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗╸╹ ╹ ╹ ┗┛╹ ┗┛┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗┛┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸┏╸┏╸ ╻┏┓┏┓┏┓╻ ┏╸┏┓┏╸┏╸┏┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┫┣╸┣┓┣┓┏┫┗┫┣┫┗┫┣┓┣╸┣┫┣╸┣╸┣┫┣╸┏┫┣┫┃┃┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗┛╹ ┗┛┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗┛┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸ ╻┏┓┏┓┏┓╻ ┏╸┏┓┏╸┏╸┏┓┏╸ ╻┏┓┏┓╻  ╻╻╻┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┓┣╸┣┓┣┓┏┫┗┫┣┫┗┫┣┓┣╸┣┫┣╸┣╸┣┫┣╸┏┫┣┫┣┫┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗┛╹ ┗┛┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗┛┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸ ╻┏┓┏┓┏┓╻ ┏╸┏┓┏╸┏╸┏┓┏╸ ╻┏┓┏┓╻  ╻┏┓┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┓┣┓┏┫┗┫┣┫┗┫┣┓┣╸┣┫┣╸┣╸┣┫┣╸┏┫┣┫┣┫┣┓┏┫┗┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗╸╹ ┗┛┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗┛┗╸┗┛╹╹┗┛┗┛┗┛ ╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸ ╻┏┓┏┓┏┓╻ ┏╸┏┓┏╸┏╸┏┓┏╸ ╻┏┓┏┓╻  ╻┏┓┏┓┏╸┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┓┣┓┏┫┗┫┣┫┗┫┣┓┣╸┣┫┣╸┣╸┣┫┣╸┏┫┣┫┣┫┣┓┏┫┣┫┗┫┣┓┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗┛┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗┛┗╸┗┛╹╹┗┛┗┛┗┛╹╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸ ╻┏┓┏┓┏┓╻ ┏╸┏┓┏╸┏╸┏┓┏╸ ╻┏┓┏┓╻  ╻┏┓┏┓┏┓┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┓┏┫┗┫┣┫┗┫┣┓┣╸┣┫┣╸┣╸┣┫┣╸┏┫┣┫┣┫┣┓┏┫┣┫┗┫┣┫┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗╸┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗┛┗╸┗┛╹╹┗┛┗┛┗┛╹╹╺┛┗┛╺┛ ╹╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸ ╻┏┓┏┓┏┓╻ ┏╸┏┓┏╸┏╸┏┓┏╸ ╻┏┓┏┓╻  ╻┏┓┏┓┏┓┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┓┏┫┗┫┣┫┗┫┣┓┣╸┣┫┣╸┣╸┣┫┣╸┏┫┣┫┣┫┣┓┏┫┣┫┗┫┣┫┗┫ ┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗┛┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗┛┗╸┗┛╹╹┗┛┗┛┗┛╹╹╺┛┗┛╺┛╺┛╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸ ╻┏┓┏┓┏┓╻ ┏╸┏┓┏╸┏╸┏┓┏╸ ╻┏┓┏┓╻  ╻┏┓┏┓┏┓┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┏┫┗┫┣┫┗┫┣┓┣╸┣┫┣╸┣╸┣┫┣╸┏┫┣┫┣┫┣┓┏┫┣┫┗┫┣┫┗┫╻┃┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗╸┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗┛┗╸┗┛╹╹┗┛┗┛┗┛╹╹╺┛┗┛╺┛┗┛╺┛╹ ┗┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸ ╻┏┓┏┓┏┓╻ ┏╸┏┓┏╸┏╸┏┓┏╸ ╻┏┓┏┓╻  ╻┏┓┏┓┏┓┏┓ ╻┏┓┏╸┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┏┫┗┫┣┫┗┫┣┓┣╸┣┫┣╸┣╸┣┫┣╸┏┫┣┫┣┫┣┓┏┫┣┫┗┫┣┫┗┫┏┫┗┫┣╸┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗┛╺┛╹╹╺┛┗┛┗╸╹╹┗╸┗╸┗┛┗╸┗┛╹╹┗┛┗┛┗┛╹╹╺┛┗┛╺┛┗┛╺┛╹ ┗┛
+Größtmögliche Hex-Zahl: FFFFFFFFFFFFFFFFD9A9BEAEE8EDA8BDA989D9F8
+Gegebene Maximalzahl an Umlegungen: 37
+Anzahl genutzter Umlegungen: 37
+
+Laufzeit ohne I/O: 42.484µs
+
+$ AusführbaresProgramm/aufgabe3-x86_64-linux-static Beispieleingaben/hexmax3.txt
+Gegebene Hex-Zahl: 0E9F1DB46B1E2C081B059EAF198FD491F477CE1CD37EBFB65F8D765055757C
+6F4796BB8B3DF7FCAC606DD0627D6B48C17C09
+-- Ausgabe gekürzt --
+Größtmögliche Hex-Zahl: FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+FFFFFFFAA98BB8B9DFAFEAE888DD888AD8BA8EA8888
+Gegebene Maximalzahl an Umlegungen: 121
+Anzahl genutzter Umlegungen: 121
+
+Laufzeit ohne I/O: 102.92µs
+
+$ AusführbaresProgramm/aufgabe3-x86_64-linux-static Beispieleingaben/hexmax4.txt
+Gegebene Hex-Zahl: 1A02B6B50D7489D7708A678593036FA265F2925B21C28B4724DD822038E3B4
+804192322F230AB7AF7BDA0A61BA7D4AD8F888
+-- Ausgabe gekürzt --
+Größtmögliche Hex-Zahl: FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEB8DE88BAA8ADD8888
+98E9BA88AD98988F898AB7AF7BDA8A61BA7D4AD8F888
+Gegebene Maximalzahl an Umlegungen: 87
+Anzahl genutzter Umlegungen: 87
+
+Laufzeit ohne I/O: 119.441µs
+
+$ AusführbaresProgramm/aufgabe3-x86_64-linux-static Beispieleingaben/hexmax5.txt
+Gegebene Hex-Zahl: EF50AA77ECAD25F5E11A307B713EAAEC55215E7E640FD263FA529BBB48DC8F
+AFE14D5B02EBF792B5CCBBE9FA1330B867E330A6412870DD2BA6ED0DBCAE553115C9A31FF350C5DF9
+93824886DB5111A83E773F23AD7FA81A845C11E22C4C45005D192ADE68AA9AA57406EB0E7C9CA13AD
+03888F6ABEDF1475FE9832C66BFDC28964B7022BDD969E5533EA4F2E4EABA75B5DC11972824896786
+BD1E4A7A7748FDF1452A5079E0F9E6005F040594185EA03B5A869B109A283797AB31394941BFE4D38
+392AD12186FF6D233585D8C820F197FBA9F6F063A0877A912CCBDCB14BEECBAEC0ED061CFF60BD517
+B6879B72B9EFE977A9D3259632C718FBF45156A16576AA7F9A4FAD40AD8BC87EC569F9C1364A63B16
+23A5AD559AAF6252052782BF9A46104E443A3932D25AAE8F8C59F10875FAD3CBD885CE68665F2C826
+B1E1735EE2FDF0A1965149DF353EE0BE81F3EC133922EF43EBC09EF755FBD740C8E4D024B033F0E8F
+3449C94102902E143433262CDA1925A2B7FD01BEF26CD51A1FC22EDD49623EE9DEB14C138A7A6C47B
+677F033BDEB849738C3AE5935A2F54B99237912F2958FDFB82217C175448AA8230FDCB3B3869824A8
+26635B538D47D847D8479A88F350E24B31787DFD60DE5E260B265829E036BE340FFC0D8C05555E750
+92226E7D54DEB42E1BB2CA9661A882FB718E7AA53F1E606
+-- Ausgabe gekürzt --
+Größtmögliche Hex-Zahl: FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
+FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF88EFA9EBE89EFA99FBDAA8E8EAD88AB899
+F8E8F9AA9E9AD88988EDA9A99888EDAD989A8BAFD8A88888888888888888888888888888888888888
+888888888888888888888888888888888888888888888888888888888888888888888888888888888
+888888888888888888888888888888888888888888888888888888888888888888888888888888888
+8888888888888888888888888888888888888888888888888888
+Gegebene Maximalzahl an Umlegungen: 1369
+Anzahl genutzter Umlegungen: 1369
+
+Laufzeit ohne I/O: 2.009263ms
+\end{verbatim}
+
+Bei den BwInf-Beispielen wurde die Maximalzahl an Umlegungen immer voll ausgeschöpft. Die Beispieleingabe \texttt{ungenutzte\_umlegungen.txt} deckt den Fall ab, dass am Ende noch ungenutzte Umlegungen verbleiben:
+
+\begin{verbatim}
+$ AusführbaresProgramm/aufgabe3-x86_64-linux-static Beispieleingaben/ungenutzte_umlegungen.txt
+Gegebene Hex-Zahl: 7777
+╺┓╺┓╺┓╺┓
+ ┃ ┃ ┃ ┃
+ ╹ ╹ ╹ ╹
+╺╸╺┓╺┓╺┓
+╻╻ ┃ ┃ ┃
+╹╹ ╹ ╹ ╹
+┏╸╺┓╺┓╺┓
+┃  ┃ ┃ ┃
+╹  ╹ ╹ ╹
+┏╸╺┓╺┓ ╻
+┣╸ ┃ ┃ ┃
+╹  ╹ ╹ ╹
+Größtmögliche Hex-Zahl: F771
+Gegebene Maximalzahl an Umlegungen: 5
+Anzahl genutzter Umlegungen: 3
+
+Laufzeit ohne I/O: 7.52µs
+\end{verbatim}
+
+Erst bei $m = 6$ kann eine größere Hex-Zahl erreicht werden:
+
+\begin{verbatim}
+$ AusführbaresProgramm/aufgabe3-x86_64-linux-static Beispieleingaben/ungenutzte_umlegungen_bump.txt 
+Gegebene Hex-Zahl: 7777
+╺┓╺┓╺┓╺┓
+ ┃ ┃ ┃ ┃
+ ╹ ╹ ╹ ╹
+╺╸╺┓╺┓╺┓
+╻╻ ┃ ┃ ┃
+╹╹ ╹ ╹ ╹
+┏╸╺┓╺┓╺┓
+┃  ┃ ┃ ┃
+╹  ╹ ╹ ╹
+┏╸╺╸╺┓╺┓
+┃ ╻╻ ┃ ┃
+╹ ╹╹ ╹ ╹
+┏╸┏╸╺┓╺┓
+┃ ┃  ┃ ┃
+╹ ╹  ╹ ╹
+┏╸┏╸ ╻╺┓
+┣╸┃  ┃ ┃
+╹ ╹  ╹ ╹
+┏╸┏╸ ╻ ╻
+┣╸┣╸ ┃ ┃
+╹ ╹  ╹ ╹
+Größtmögliche Hex-Zahl: FF11
+Gegebene Maximalzahl an Umlegungen: 6
+Anzahl genutzter Umlegungen: 6
+
+Laufzeit ohne I/O: 8.68µs
+\end{verbatim}
+
+Bei dem Beispiel \texttt{keine\_umlegungen.txt} ist die Maximalzahl an Umlegungen $m$ gleich $0$:
+
+\begin{verbatim}
+$ AusführbaresProgramm/aufgabe3-x86_64-linux-static Beispieleingaben/keine_umlegungen.txt
+Gegebene Hex-Zahl: 509C431B55
+┏╸┏┓┏┓┏╸╻╻╺┓ ╻╻ ┏╸┏╸
+┗┓┃┃┗┫┃ ┗┫╺┫ ┃┣┓┗┓┗┓
+╺┛┗┛╺┛┗╸ ╹╺┛ ╹┗┛╺┛╺┛
+Größtmögliche Hex-Zahl: 509C431B55
+Gegebene Maximalzahl an Umlegungen: 0
+Anzahl genutzter Umlegungen: 0
+
+Laufzeit ohne I/O: 7.691µs
+\end{verbatim}
+
+Das Beispiel \texttt{umlegungen\_en\_masse.txt} behandelt den umgekehrten Fall, dass weit mehr Umlegungen zur Verfügung stehen, als überhaupt verarbeitet werden können:
+
+\begin{verbatim}
+$ AusführbaresProgramm/aufgabe3-x86_64-linux-static Beispieleingaben/umlegungen_en_masse.txt
+Gegebene Hex-Zahl: 509C431B55
+┏╸┏┓┏┓┏╸╻╻╺┓ ╻╻ ┏╸┏╸
+┗┓┃┃┗┫┃ ┗┫╺┫ ┃┣┓┗┓┗┓
+╺┛┗┛╺┛┗╸ ╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏┓┏┓┏╸╻╻╺┓ ╻╻ ┏╸┏╸
+┣╸┃┃┗┫┃ ┗┫╺┫ ┃┣┓┗┓┗┓
+┗╸┗┛╺┛┗╸ ╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏┓┏╸╻╻╺┓ ╻╻ ┏╸┏╸
+┣╸┣┓┗┫┃ ┗┫╺┫ ┃┣┓┗┓┗┓
+┗╸┗┛╺┛┗╸ ╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸╻╻╺┓ ╻╻ ┏╸┏╸
+┣╸┣┓┣┓┃ ┗┫╺┫ ┃┣┓┗┓┗┓
+┗╸┗┛┗┛┗╸ ╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸╻╻╺┓ ╻╻ ┏╸┏╸
+┣╸┣┓┣┓┣╸┗┫╺┫ ┃┣┓┗┓┗┓
+┗╸┗┛┗┛╹  ╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸┏╸╺┓ ╻╻ ┏╸┏╸
+┣╸┣┓┣┓┣╸┗┓╺┫ ┃┣┓┗┓┗┓
+┗╸┗┛┗┛╹  ╹╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸┏╸╺┓ ╻╻ ┏╸┏╸
+┣╸┣┓┣┓┣╸┣╸╺┫ ┃┣┓┗┓┗┓
+┗╸┗┛┗┛╹ ╹ ╺┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸┏╸╺╸ ╻╻ ┏╸┏╸
+┣╸┣┓┣┓┣╸┣╸┏┓ ┃┣┓┗┓┗┓
+┗╸┗┛┗┛╹ ╹ ┗┛ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸┏╸┏╸ ╻╻ ┏╸┏╸
+┣╸┣┓┣┓┣╸┣╸┣╸ ┃┣┓┗┓┗┓
+┗╸┗┛┗┛╹ ╹ ┗╸ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸┏╸┏╸╺╸╻ ┏╸┏╸
+┣╸┣┓┣┓┣╸┣╸┣╸ ╻┣┓┗┓┗┓
+┗╸┗┛┗┛╹ ╹ ┗╸ ╹┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸┏╸┏╸╺╸╻ ┏╸┏╸
+┣╸┣┓┣┓┣╸┣╸┣╸╻ ┣┓┗┓┗┓
+┗╸┗┛┗┛╹ ╹ ┗╸╹ ┗┛╺┛╺┛
+┏╸┏╸┏╸┏╸┏╸┏╸╺╸┏╸┏╸┏╸
+┣╸┣┓┣┓┣╸┣╸┣╸╻ ┣╸┗┓┗┓
+┗╸┗┛┗┛╹ ╹ ┗╸╹ ┗╸╺┛╺┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸
+┣╸┣┓┣┓┣╸┣╸┣╸┃ ┣╸┗┓┗┓
+╹ ┗┛┗┛╹ ╹ ┗╸╹ ┗╸╺┛╺┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸
+┣╸┣╸┣┓┣╸┣╸┣╸┣╸┣╸┗┓┗┓
+╹ ┗╸┗┛╹ ╹ ┗╸╹ ┗╸╺┛╺┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸
+┣╸┣╸┣┓┣╸┣╸┣╸┣╸┣╸┗┫┗┓
+╹ ╹ ┗┛╹ ╹ ┗╸╹ ┗╸╺┛╺┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏╸
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┫┗┓
+╹ ╹ ┗╸╹ ╹ ┗╸╹ ┗╸┗┛╺┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┫┗┫
+╹ ╹ ╹ ╹ ╹ ┗╸╹ ┗╸┗┛╺┛
+┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏╸┏┓┏┓
+┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣╸┣┫┣┫
+╹ ╹ ╹ ╹ ╹ ╹ ╹ ┗╸┗┛┗┛
+Größtmögliche Hex-Zahl: FFFFFFFE88
+Gegebene Maximalzahl an Umlegungen: 1000
+Anzahl genutzter Umlegungen: 17
+
+Laufzeit ohne I/O: 13.622µs
+\end{verbatim}
+
+\section{Quellcode}
+
+Teile des Quellcodes, die nur der Ein- bzw. Ausgabe dienen, werden hier nicht abgedruckt.
+
+\begin{lstlisting}[language=rust]
+// Beschreibt eine einzelne Hex-Ziffer. Der enthaltene Integer nimmt nur die
+// Werte 0x0 bis 0xF an.
+#[derive(Clone, Copy)]
+struct HexDigit(u8);
+
+// Beschreibt eine Hex-Zahl mit beliebig vielen Ziffern. Die Ziffern sind in
+// Lesereihenfolge gespeichert.
+struct HexNumber {
+    digits: Vec<HexDigit>,
+}
+
+// Beschreibt eine zu lösende Aufgabe.
+struct Task {
+    number: HexNumber,
+    max_moves: usize,
+}
+
+// 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(u8);
+
+// Beschreibt den Zustand einer Reihe von Siebensegmentanzeigen.
+struct SevenSegmentDisplayRow {
+    displays: Vec<SevenSegmentDisplay>,
+}
+
+// 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, 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,
+}
+
+// Löst eine gegebene Aufgabe, indem Teil 1 und 2 des Algorithmus nacheinander
+// aufgerufen werden.
+fn solve_task(task: Task) -> Solution {
+    let greatest_reachable_number = solve_pt1(&task);
+    let states = solve_pt2(&task.number.digits, &greatest_reachable_number);
+
+    Solution {
+        initial: task.number,
+        r#final: HexNumber {
+            digits: greatest_reachable_number,
+        },
+        max_moves: task.max_moves,
+        used_moves: states.len() - 1,
+        states,
+    }
+}
+
+// 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 Segmente 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 würden.
+        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_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_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_sticks - 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_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.
+                    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, 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_sticks = digit.num_sticks();
+            (
+                acc_vacant_segments + (7 - num_sticks),
+                acc_occupied_segments + (num_sticks - 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> {
+    // Zunächst werden die beiden Hex-Zahlen jeweils zu einem Array von
+    // Siebensegmentanzeigen konvertiert.
+    let start_state = start
+        .into_iter()
+        .map(|digit| digit.to_seven_segments())
+        .collect::<Vec<SevenSegmentDisplay>>();
+    let end_state = end
+        .into_iter()
+        .map(|digit| digit.to_seven_segments())
+        .collect::<Vec<SevenSegmentDisplay>>();
+
+    // In diesem Array werden die Zwischenstände zwischen den Umlegungen
+    // gesammelt. Diese werden am Ende auch zurückgegeben.
+    let mut states = vec![SevenSegmentDisplayRow {
+        displays: start_state.clone(),
+    }];
+
+    // Beschreibt die Position eines Segments in einer Reihe von
+    // Siebensegmentanzeigen.
+    struct Coordinates {
+        display_idx: usize,
+        segment_idx: u8,
+    }
+
+    let mut current_state = start_state.clone();
+
+    // In diesen beiden Arrays werden die Positionen der Segmente gespeichert,
+    // die "ein-" bzw. "ausgeschaltet" werden müssen, um von der urspünglichen
+    // Hex-Zahl zur größtmöglichen zu kommen, und die nicht schon durch eine
+    // Umlegung innerhalb einer Siebensegmentanzeige richtiggestellt werden
+    // konnten.
+    let mut unmatched_on_flips: Vec<Coordinates> = Vec::new();
+    let mut unmatched_off_flips: Vec<Coordinates> = Vec::new();
+
+    for (display_idx, (segments_start, segments_end)) in
+        start_state.iter().zip(end_state.iter()).enumerate()
+    {
+        // 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::<u8>::new();
+        let mut off_flips = VecDeque::<u8>::new();
+
+        for (segment_idx, (segment_start, segment_end)) in segments_start
+            .into_iter()
+            .zip(segments_end.into_iter())
+            .enumerate()
+        {
+            match (segment_start, segment_end) {
+                (false, true) => on_flips.push_back(segment_idx as u8),
+                (true, false) => off_flips.push_back(segment_idx as u8),
+                _ => {}
+            }
+        }
+
+        // `num_intra_display_moves` ist die Anzahl der Umlegungen, die
+        // innerhalb dieser Siebensegmentanzeige erfolgen können.
+        let num_intra_display_moves = on_flips.len().min(off_flips.len());
+        // Es werden vorab schon innerhalb dieser Siebensegmentanzeige
+        // `num_intra_display_moves` Umlegungen ausgeführt, indem gleichzeitig
+        // über die ersten `num_intra_display_moves` "On-Flips" und "Off-Flips"
+        // iteriert wird. Nach jeder Umlegung wird eine Kopie des
+        // Gesamt-Zwischenstandes gespeichert.
+        for (on_flip, off_flip) in on_flips
+            .drain(..num_intra_display_moves)
+            .zip(off_flips.drain(..num_intra_display_moves))
+        {
+            current_state[display_idx].toggle(on_flip);
+            current_state[display_idx].toggle(off_flip);
+            states.push(SevenSegmentDisplayRow {
+                displays: current_state.clone(),
+            })
+        }
+
+        // Übrig gebliebene "Stäbchen-Flips", die nicht durch eine Umlegung
+        // innerhalb dieser Siebensegmentanzeige realisiert werden konnten,
+        // werden für die spätere Verarbeitung gespeichert.
+        let complete_coords = |segment_idx| Coordinates {
+            display_idx,
+            segment_idx,
+        };
+        unmatched_on_flips.extend(on_flips.drain(..).map(complete_coords));
+        unmatched_off_flips.extend(off_flips.drain(..).map(complete_coords));
+    }
+
+    // Sanity Check
+    assert_eq!(unmatched_on_flips.len(), unmatched_off_flips.len());
+
+    // Zuletzt wird gleichzeiting über die noch nicht realisierten
+    // "Stäbchen-Flips" iteriert. Es wird jeweils die beschriebene Umlegung
+    // ausgeführt, und nach jeder Umlegung wird eine Kopie des Zwischenstandes
+    // gespeichert, sodass am Ende die genaue Umlegungs-Abfolge einsehbar ist.
+    for (on_flip, off_flip) in unmatched_on_flips
+        .into_iter()
+        .zip(unmatched_off_flips.into_iter())
+    {
+        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(),
+        })
+    }
+
+    states
+}
+
+impl HexDigit {
+    // Stellt eine Hex-Ziffer auf einer Siebensegmentanzeige dar.
+    fn to_seven_segments(self) -> SevenSegmentDisplay {
+        let segments = match self.0 {
+            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 dieser
+    // Hex-Ziffer auf einer Siebensegmentanzeige benötigt werden.
+    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 dieser Hex-Ziffer zu der einer anderen
+    // zu gelangen.
+    fn num_required_segment_flips(self, other: Self) -> usize {
+        (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,
+        }
+    }
+}
+
+// Einstiegspunkt für das Programm.
+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 start = time::Instant::now();
+    let solution = solve_task(task);
+    let elapsed = start.elapsed();
+
+    println!("{}", solution);
+    println!("Laufzeit ohne I/O: {:?}", elapsed);
+}
+\end{lstlisting}
+
+\end{document}
-- 
cgit 1.4.1

