\documentclass[a4paper,10pt,ngerman]{scrartcl} \usepackage{babel} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage[a4paper,margin=2.5cm,footskip=0.5cm]{geometry} \DeclareUnicodeCharacter{25CB}{$\circ$} % Die nächsten drei Felder bitte anpassen: \newcommand{\Aufgabe}{Aufgabe 2: Rechenrätsel} % Aufgabennummer und Aufgabennamen angeben \newcommand{\TeilnahmeId}{60813} % Teilnahme-ID angeben \newcommand{\Name}{Marcel Zinkel} % Name des Bearbeiter / der Bearbeiterin dieser Aufgabe angeben % 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} % Für Bilder \usepackage{graphicx} % Für Algorithmen \usepackage{algpseudocode} % Für Quelltext \usepackage{minted} \usepackage{color} \definecolor{mygreen}{rgb}{0,0.6,0} \definecolor{mygray}{rgb}{0.5,0.5,0.5} \definecolor{mymauve}{rgb}{0.58,0,0.82} % Anführungszeichen \usepackage{csquotes} % 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} \subsection{Allgemeines} Der Beweis, ob ein Rechenrätsel eindeutig lösbar ist, ist ein Entscheidungsproblem mit NP-Schwere. Eine mögliche Lösung ist, eine interessante Ziffernfolge zufällig zu wählen und alle möglichen Kombinationen von Operatoren auszuprobieren. Kommt ein Ergebnis nur einmal vor, wurde ein eindeutig lösbares Rätsel gefunden, was in der Regel der Fall sein sollte, ansonsten muss der Vorgang mit anderen Ziffern wiederholt werden. Theoretisch wäre es möglich, dass die Operanden immer zufällig so gewählt werden, dass es kein interessantes und eindeutiges Rätsel gibt und das Programm somit nie zu einem Ergebnis kommt. Allerdings läuft die Wahrscheinlichkeit dafür gegen null. Die beschriebene Brute-Force\footnote{Alle Möglichkeiten werden ausprobiert.} Operation dauert allerdings bei zunehmender Anzahl der Operatoren exponentiell länger. Die Anzahl der Möglichkeiten $|\Omega|$ kann in Abhängigkeit von der Operatorenanzahl $n$ berechnet werden: $|\Omega|=4^{n}$. Dabei gilt es zu beachten, dass dies der Maximalwert ist, da die Division oft im Vorhinein ausgeschlossen werden kann, weil diese eine nicht ganze Zahl ergibt. Das Programm sollte Rätsel mit mindestens 15 Operatoren erstellen können, da dies in der Aufgabenstellung als Richtwert angegeben wird. Für $n=15$ gilt $|\Omega|=4^{15}=1073741824\approx10^{6}$. So viele Möglichkeiten können noch mit einer guten Laufzeit berechnet werden. \subsection{Die Null als Operand?} Nach Aufgabenstellung ist jeder Operand nur eine Ziffer. Bei den gegebenen Beispielen kommt jede Ziffer vor außer der Null, allerdings wird auch nicht ausdrücklich gesagt, dass man sie nicht verwenden darf. Die Addition und Subtraktion einer Null kann in einem Rätsel nicht verwendet werden, da beide Operationen das gleiche Ergebnis haben und das Rätsel damit uneindeutig wäre. Da die Division durch Null nicht definiert ist, bleibt nur noch die Multiplikation übrig. Es ergibt jedoch wenig Sinn ein Rätsel zu stellen, wo bereits zu Beginn ein Teil der Lösung bekannt ist. Dies gilt insbesondere, da die Rätsel nach Aufgabenstellung \enquote{richtig schwer} sein sollen. Also wird die Null in meiner Lösung nicht als Operand benutzt. \subsection{Interessante Rätsel} Die Aufgabenstellung gibt nicht genau vor, wie ein Rätsel, das \enquote{interessant und unterschiedlich} ist, zu sein hat. Allerdings wird ein Beispiel gegeben, wie ein Rätsel aussehen kann. Das Beispielrätsel habe ich mit einer leicht modifizierten Version meines Programms lösen lassen: \begin{minted}{text} Rätsel: 4 ○ 3 ○ 2 ○ 6 ○ 3 ○ 9 ○ 7 ○ 8 ○ 2 ○ 9 ○ 4 ○ 4 ○ 6 ○ 4 ○ 4 ○ 5 = 4792 Lösung: 4 * 3 * 2 * 6 * 3 * 9 + 7 * 8 : 2 * 9 * 4 - 4 * 6 - 4 * 4 * 5 = 4792 \end{minted} Es fällt auf das jeder Operator mindestens einmal vorkommt, wobei die Multiplikation überwiegt. Außerdem ist das Ergebnis noch relativ klein im Vergleich zu anderen eindeutig lösbaren Rätseln, wie ich beim Vergleich mit der ungefilterten Ausgabe meines Programms festgestellt habe. Zudem kommen einige verschiedene Ziffern vor. Meine Regeln für ein interessantes Rätsel sind noch etwas strenger, da in dem Beispiel schon recht oft die Multiplikation vertreten ist. Diese lauten wie folgt: \begin{enumerate} \item Sei $n$ die Anzahl der Operatoren und $m_i$, die Anzahl, mit der der jeweilige Operator vorkommt. Dann soll gelten: \begin{align} \frac{n}{10} - 1 < m_i \leq \frac{n}{2} + 1 \end{align} Die Division ist oft nicht möglich, da das Ergebnis keine ganze Zahl ist. Deshalb muss die Untergrenze relativ klein sein, damit für die Division die Bedingung noch erfüllt werden kann. Die Formel wurde so gewählt, dass bei Rätsel mit zwei Operatoren noch zweimal derselbe Operator gewählt werden darf. Allerdings finde ich es bei Rätseln mit drei Operatoren nicht interessant, jedes Mal denselben Operator zu haben. Darum habe ich die Formel so gewählt, dass in diesem Fall die Obergrenze nicht erfüllt ist. \item Sei $n$ die Anzahl der Ziffern und $m_i$, die Anzahl mit der die jeweilige Ziffer vorkommt. Dann soll gelten: \begin{align} \frac{n}{18} - 1 < m_i \leq \frac{2}{9} \cdot n + 1 \end{align} Für diese Untergrenze habe ich mich entschieden, damit, wenn durchschnittlich jede Ziffer der neun Ziffern zweimal vorkommen sollte, mindestens eine vorhanden ist. Aus einem ähnlichen Grund habe ich auch die Obergrenze so gewählt, dass $\lim_{n \to \infty} \frac{2}{9} \cdot n + 1 = \lim_{n \to \infty} \frac{2}{9} \cdot n$ \end{enumerate} In der Regel werden viele interessante Rätsel gefunden. Da das Beispielrätsel ein kleines Ergebnis hat und kleinere Ergebnisse auch eleganter sind, wird von allen interessanten Rätseln, das mit dem kleinsten Ergebnis ausgewählt. \section{Umsetzung} \subsection{Umgebung und Bibliotheken} Die Lösungsidee wird in Rust nightly implementiert, da Trait Aliase noch nicht in Rust stable sind. Jeder Typ, der ein Trait implementiert, muss bestimmte Methoden haben. Traits sind daher für Generics essenziell. Trait Aliase machen es nun möglich für mehrere Traits einen Alias zu erstellen, was Schreibarbeit spart. Außerdem werden einige crates, also Abhängigkeiten in Rust, verwendet: \begin{itemize} \item Mit rand werden zufällige Ziffern als Operanden erstellt. \item Mit clap werden die Kommandozeilenargumente verarbeitet. \item Zudem werden noch einige crates des rust-num Teams genutzt. Dabei wird nicht das meta-crate num verwendet, sondern die sub-crates werden einzeln verwendet, um die Abhängigkeiten kleinzuhalten. num-traits ist dabei u. a. für die Konvertierung eines bestimmten Integer-Typs zu einen generischen Integer-Typ zuständig. num-derive stellt Macros zur Verfügung, die es erlauben Integers zu Enums zu konvertieren. Mit num-integer können arithmetischen Operationen generisch für verschiedene Integer-Typen implementiert werden. \end{itemize} \subsection{Benutzung} Mit der Option -c kann die Anzahl der Operatoren angegeben werden. Der Standartwert ist 5. Allerdings können maximal Rätsel mit 32 Operatoren berechnet werden, da die verwendeten Operatoren eines Rätsels in 64 Bit Integers gespeichert werden. Da es vier Grundrechenarten gibt brauchen wir für jeden Operator 2 Bits, um diesen darzustellen. Da $64/2=32$ können also maximal 32 Operatoren verwendet werden. Mit dem flag -s kann man die Ausgabe der Lösung zu dem Rätsel einschalten. Schließlich können optional mit -d die Operanden angegeben werden, z. B. : \mintinline{text}|-d={1,4,5,8}|. Dies ist sehr nützlich zu Testzwecken. Wenn man die Operanden nicht angibt, werden automatisch interessante gewählt. \subsection{Implementierungsart} In der main-Funktion befindet sich direkt eine while-Schleife, die solange läuft bis ein interessantes Rätsel gefunden wurde. In der Regel wird die Schleife nur einmal durchlaufen, weil sich für die erste ausgewählte Operandenkombination normalerweise auch ein interessantes und eindeutiges Rätsel ergibt. Wenn der Nutzer keine Operanden angibt, werden diese zufällig ausgewählt. Dabei befinden sich die Ziffern in einem Vector\footnote{Implementierung von Arrays mit dynamischer Größe aus Rusts Standartbibliothek} und werden daraus zufällig gewählt. Damit die minimale und maximale Anzahl aller Ziffern garantiert werden kann, sodass das Rätsel interessant ist, werden in Laufe der Auswahl Ziffern aus dem Vector entfernt. Danach wird die Funktion \mintinline{rs}|calc_results| mit diesen Operanden aufgerufen. Diese kann durch Generics alle Integertypen für die (Zwischen)ergebnisse verwenden. Das größte Ergebnis für die Operanden wird berechnet, indem sie alle miteinander multipliziert werden. Wenn dieses zu groß ist für 64 Bit Integers, werden 128 Bit Integers verwendet, ansonsten 64 Bit Integers. Dafür habe ich mich entschieden, da mit 64 Bit Rechnern schneller mit 64 Bit Integers gerechnet werden kann. Jedoch kann man trotzdem Rätsel berechnen, die 128 Bit Integers erfordern. Innerhalb der Funktion \mintinline{rs}|calc_results| gibt es eine for-Schleife, die über alle Möglichkeiten, Operanden mit Punkt- bzw. Strichrechnung zu wählen, iteriert. Dabei wird die Variablen \mintinline{rs}|dm_as_map| nach jedem Durchlauf um eins erhöht. Jedes Bit der Variable steht dabei für Punkt- oder Strichrechnung, wobei das least significant Bit für den Operatoren ganz links steht. In der Schleife wird die Funktion \mintinline{rs}|multiplicate_divide| mit einer Sequenz von Operanden, zwischen denen nur Punktrechnung vorkommt, aufgerufen. Diese ruft sich selber doppelt rekursiv auf, wobei einmal multipliziert und einmal dividiert wird. Die Division wird ausgelassen, wenn das Zwischenergebnis keine ganze Zahl ist. Wenn das Ende der Sequenz erreicht ist, werden die verwendeten Operatoren in einer Hashmap mit dem Zwischenergebnis als Schüssel abgespeichert. Wenn das Zwischenergebnis bereits einmal vorkam, wird unter dem Ergebnis \mintinline{rs}|None| abspeichert und das Zwischenergebnis somit als uneindeutig markiert. Die Hashmaps mit den möglichen Zwischenergebnissen werden zusammen in einem Vector \mintinline{rs}|results_multiplicate| gespeichert. Zusätzlich werden die Operanden, die nicht Teil einer Punktrechnungssequenz sind, einfach in den Vector übernommen, indem eine Hashmap mit nur einem möglichen Zwischenergebnis erstellt wird. In der rekursiven Funktion \mintinline{rs}|add_sub| wird mit einer for-Schleife über alle möglichen Zwischenergebnisse iteriert. Innerhalb der Schleife ruft sich die Funktion pro Durchlauf zweimal auf, wobei einmal addiert und einmal subtrahiert wird. Dies passiert solange, bis die letzte Hashmap mit möglichen Ergebnissen erreicht wurde. Dann wird das Ergebnis mit den verwendeten Operatoren mithilfe der Struktur \mintinline{rs}|ResultStore| gespeichert, wobei es auch passieren kann, dass das Ergebnis direkt als uneindeutig markiert wird, da schon eines der Zwischenergebnisse uneindeutig war. Die Struktur \mintinline{rs}|ResultStore| besteht aus einer Hashmap mit den Operatoren als Wert und den dazugehörigen Ergebnissen als Schüssel. Außerdem hat sie noch ein weiters Attribut, ein Hashset, mit den Ergebnissen für die das Rätsel uneindeutig ist. Die Methode \mintinline{rs}|store| hat als Parameter das Ergebnis und eine Option von Operatoren. Wenn die Option \mintinline{rs}|None| ist, wird das Ergebnis in das Hashset der uneindeutigen Ergebnisse aufgenommen. Wenn das Ergebnis weder in der Hashmap noch in dem Hashset ist, wird das Rätsel in der Hashmap gespeichert. Wenn es bereits in der Hashmap ist, wird es als uneindeutig im Hashset gespeichert. Schließlich wird über alle Schlüssel-Werte-Paare der Hashmap einer Instanz der \mintinline{rs}|ResultStore| Struktur iteriert. Es wird gezählt wie oft welche Operatoren verwendet wurden und überprüft, ob die Anzahl innerhalb des Bereiches liegt, in dem das Rätsel als interessant befunden wird. Von allen interessanten und uneindeutigen Rätseln wird bestimmt, welches das kleinste Ergebnis hat, und dieses wird ausgegeben. Wenn kein interessantes Rätsel gefunden wurde, muss die while-Schleife der main-Funktion noch einmal durchlaufen werden. \section{Beispiele} Im Ordner \enquote{ergebnisdateien} findet man die Beispielausgaben nummeriert nach der Operatorenanzahl. \input{|./ergebnis-latex.sh} \section{Quellcode} \begin{minted}[breaklines,fontsize=\footnotesize]{rs} #![feature(trait_alias)] // aktiviert Trait Aliase // Importe use clap::Parser; use std::collections::{HashSet, HashMap}; use rand::distributions::{Distribution, Uniform}; use num_derive::FromPrimitive; use num_traits::FromPrimitive; use num_integer::Integer; use std::hash::Hash; use std::fmt::Display; use num_traits::bounds::Bounded; // definiert einen Trait Alias, da diese Traits öfter gemeinsam benötigt werden trait BasicInteger = Integer + Hash + Copy; // Enum für die vier Grundoperatoren #[derive(FromPrimitive)] // Durch FromPrimitive können ganze Zahlen zu Enums konvertiert werden. enum Operator { Add, Subtract, Multiplicate, Divide, } // Enum für Punkt- oder Strichrechnung #[derive(FromPrimitive, PartialEq, Clone, Copy)] enum AddSubOrMultiplicateDivide { AddSub, MultiplicateDivide, } // Struktur für die Kommandozeilenargumente #[derive(Parser)] struct Args { /// Anzahl der Operatoren #[clap(short, long, default_value_t = 5)] count: u8, /// zeigt die Lösung an #[clap(short, long)] solution_print: bool, /// nutzt vorgegebene Ziffern zur Erstellung des Rätsels (für reproduzierbare Testfälle) #[clap(short, long)] digits: Vec, } struct PartOperation { // mögliche Zwischenergebnisse eines Teils der Rechnung, der nur Punktrechnung enthält. results: HashMap>, last_operator: Option, // der Operator, der vor dieser Rechnungsteil steht } // Struktur, die eindeutige Ergebnisse speichert struct ResultStore { riddles: HashMap, // speichert eindeutige Rätsel // speichert Ergebnisse, für die es bereits mehrere Operatorenkombinationen gibt results_already_taken: HashSet, } impl ResultStore { // erstellt einen neuen, leere ResultStore fn new() -> Self { Self { riddles: HashMap::new(), results_already_taken: HashSet::new(), } } /* Methode, zum Speichern eines neuen Ergebnisses. * Ist der Parameter operators == None, so ist das Ergebnis uneindeutig. */ fn store(&mut self, result: T, operators: Option) { // Wenn das Ergebnis bereits uneindeutig ist, wird nichts gemacht. if self.results_already_taken.contains(&result) {return;} // Wenn es das Ergebnis bereits gibt, ... if match operators { None => true, Some(_x) => self.riddles.contains_key(&result), } { // ... dann wird es von den eindeutigen Rätseln entfernt ... self.riddles.remove(&result); self.results_already_taken.insert(result); // ... und zu den uneindeutigen hinzugefügt. } // Ist es eindeutig, wird zu den eindeutigen hinzugefügt. else {self.riddles.insert(result, operators.unwrap());} } } fn main() { // Methode des crates clap, die die Kommandozeilenargumente einliest. let args = Args::parse(); /* Rätsel für größere Operatorenanzahlen können nicht berechnet werden, da die verwendeten * Operatoren als u64 gespeichert werden müssen und für jeden Operator zwei Bits benötigt * werden. Natürlich ist die praktische Grenze laufzeitbedingt schon vorher erreicht. */ if args.count > 32 { println!("Es können maximal Rätsel mit 32 Operatoren erstellt werden."); return; } let mut continue_searching = true; let mut digits = args.digits; // Wenn keine Ziffern bzw. Operanden vorgegeben wurden, werden diese zufällig ausgewählt. let random_digits = digits.is_empty(); while continue_searching { if random_digits { digits = vec!(0; (args.count + 1) as usize); // erstellt einen neuen Vektor für die Ziffern /* die Ziffern, die noch zur Auswahl stehen. Dabei steht jedes Element des Vektors für * die Ziffer, die um eins größer ist. */ let mut selectable_digits: Vec = Vec::from_iter(0..9); let mut digits_count: [u8; 9] = [0; 9]; // Counter wie oft die jeweiligen Ziffern vorkommen let min: u8 = digits.len() as u8 / 18; // minmale Anzahl der jeweiligen Ziffern let max: u8 = digits.len() as u8 * 2 / 9 + 1; // maximale Anzahl /* Anzahl der Operanden, die verwendet werden können ohne, dass dadurch der Erfüllung * der minimalen Anzahl der Ziffern nähergekommen wird. */ let mut left_for_non_min: u8 = digits.len() as u8 - 9 * min; /* die Ziffern, die bereits in der minimalen Anzahl vorhanden sind. * Es sei denn die minimale Anzahl ist Null, dann ist das Hashset leer. */ let mut digits_min_statisfied: HashSet = HashSet::with_capacity(9); for digit in digits.iter_mut() { // Eine zufällige Ziffer wird aus den übrig bleibenden ausgewählt. let rand_i = Uniform::new(0, selectable_digits.len()).sample(&mut rand::thread_rng()); let rand_number = selectable_digits[rand_i]; digits_count[rand_number as usize] += 1; // erhöht den Zifferncounter let digit_used = digits_count[rand_number as usize]; if digit_used == min { if left_for_non_min == 0 { // Wenn keine Operanden frei sind, ... selectable_digits.remove(rand_i); // ... wird die Ziffer aus den ausgewählbaren entfernt. } else {digits_min_statisfied.insert(rand_number);} } if digit_used > min { // wird die Ziffern öfter als notwendig verwendet left_for_non_min -= 1; /* Wenn die restlichen Operanden gebraucht werden, um die minimale Anzahl der * übrigen Ziffern zu erfüllen, werden die Ziffern die bereits genug vorkommen, * aus den auswählbaren entfernt. */ if left_for_non_min == 0 { selectable_digits.retain(|x| !digits_min_statisfied.contains(x)); } } // Kommt eine Ziffer oft genug vor, wird diese aus den auswählbaren entfernt. if digit_used == max {selectable_digits.remove(rand_i);} /* weist die zufällig ausgewählte Ziffer zu. Diese wird zuvor noch um eins erhöht, * da die Zufallszahl im Bereich von null bis acht liegt. */ *digit = rand_number + 1; } } // berechnet das maximale Ergebnis durch die Multiplikation aller Operanden let mut max_result: u128 = 1; for digit in &digits { max_result *= *digit as u128; } /* nutzt 64 Bit Integers wenn möglich und 128 Bit Integers das maximale Ergebnis zu groß für * 64 Bit Integers ist. */ continue_searching = if max_result <= i64::MAX as u128 { calc_results::(args.solution_print, &digits) } else {calc_results::(args.solution_print, &digits)}; // Wenn die Ziffern vom Nutzer festgelegt sind, wird es nicht nochmal mit anderen versucht. if !random_digits {break;} } } /* Funktion, die eindeutige Rätsel mit den vorgegebenen Operanden berechnet und eins davon ausgibt. * Dabei kann der Integer-Typ der für die (Zwischen)ergebnisse verwendet mit Generics angegeben werden. */ fn calc_results (solution_print: bool, digits: &[u8]) -> bool { let number_operators = digits.len() - 1; let mut results = ResultStore::new(); // Hier werden die Rätsel gespeichert. // Bei dm_as_map steht jedes Bit für Punkt- oder Strichrechnung. for dm_as_map in 0..2u32.pow(number_operators as u32) { // enthält die Zwischenergebnisse mit bereits durchgeführter Punktrechnung let mut results_multiplicate: Vec> = Vec::new(); { let mut last_i: usize = 0; let mut i: usize; let mut state = AddSubOrMultiplicateDivide::from_u32(dm_as_map & 1).unwrap(); while last_i < number_operators { i = last_i; // bestimmt das Ende einer Sequenz, die nur aus Punkt- oder Strichrechnung besteht while i < number_operators && dm_as_map >> i & 1 == state as u32 { /* In einer Strichrechnungssequenz können die Operanden direkt als * Zwischenergebnisse verwendet werden. */ if state == AddSubOrMultiplicateDivide::AddSub { results_multiplicate.push(insert_digit(digits, i)); } i += 1; } if state == AddSubOrMultiplicateDivide::MultiplicateDivide { // speichert die Ergebnisse einer Punktrechnungssequenz let mut part_results: HashMap> = HashMap::new(); i += 1; let mut digits_calc = digits[last_i .. i].iter(); // Slice mit den Operanden der Sequenz // der erste Operand der Sequenz let first_digit = T::from_u8(*digits_calc.next().unwrap()).unwrap(); // berechnet die Zwischenergebnisse multiplicate_divide(digits_calc, &mut part_results, last_i as u8 * 2, first_digit, 0); // speichert die Zwischenergebnisse results_multiplicate.push(PartOperation{ results: part_results, last_operator: last_operator_helper(last_i), }); } /* Nachdem eine Punkt- oder Strichrechnungssequenz fertig, ist kommt eine Sequenz * der anderen Rechenart. */ state = match state { AddSubOrMultiplicateDivide::MultiplicateDivide => AddSubOrMultiplicateDivide::AddSub, AddSubOrMultiplicateDivide::AddSub => AddSubOrMultiplicateDivide::MultiplicateDivide, }; last_i = i; } /* Wenn der letzte Operator eine Strichrechnung ist, muss der letzte Operand noch als * Zwischenergebnis hinzugefügt werden. */ if dm_as_map >> number_operators - 1 & 1 == AddSubOrMultiplicateDivide::AddSub as u32 { results_multiplicate.push(insert_digit(digits, digits.len() - 1)); } { // führt die Strichrechnung mit den Zwischenergebnissen durch let mut iter = results_multiplicate.iter(); for (part_result, operators) in &iter.next().unwrap().results { add_sub(iter.clone(), &mut results, *part_result, *operators); } } } } let mut best_riddle_operators: Option = None; // die Operatoren des endgültig ausgewählten Rätsel /* das Ergebnis des ausgewählten Rätsels. Zu Beginn wird der maximale Wert verwendet, damit die * Bedingung, dass das Ergebnis des Rätsels kleiner ist, in beim ersten Rätsel erfüllt ist. */ let mut smallest_result = T::max_value(); for (result, operators) in results.riddles { let mut operator_count: [u8; 4] = [0; 4]; // Anzahlen der Operatoren // zählt die Operatoren for i in 0..number_operators { operator_count[(operators as usize) >> 2 * i & 3] += 1; } /* überprüft, ob alle Operatorenanzahlen innerhalb eines Bereiches liegen und das Rätsel * somit interessant ist. */ let mut interessing_riddle = true; for count in operator_count { interessing_riddle &= number_operators as u8 / 10 <= count && count <= number_operators as u8 / 2 + 1; } /* Ist das Rätsel interessant und das Ergebnis kleiner als das aktuelle Rätsel, dann wird * dieses als vorläufig bestes Rätsel gespeichert. */ if interessing_riddle && result < smallest_result { smallest_result = result; best_riddle_operators = Some(operators); } } match best_riddle_operators { /* wurde kein Rätsel gefunden wird true zurückgeben und die Suche wird wiederholt, da der * Rückwert als Bedingung in der while-Schleife genutzt wird. */ None => true, Some(operators) => { // Wenn ein Rätsel gefunden wurde, wird es ausgegeben. (siehe Quelltext) false } } } /* rekursive Funktion, die Punktrechnung auf einer Sequenz der Operanden durchführt und die * Ergebnisse in einer Hashmap speichert. */ fn multiplicate_divide<'a, T: BasicInteger + FromPrimitive> (mut iter: impl Clone + Iterator, results: &mut HashMap>, operator_index: u8, part_result: T, operators: u64) { match iter.next() { /* Wenn keine Ziffern mehr übrig sind, werden die Operatoren in einer Hashmap abspeichert. * Wenn das gleiche Zwischenergebnis bereits durch andere Operatoren erreicht wurde ist * dieses uneindeutig und None wird in der Hashmap gespeichert. */ None => { results.insert(part_result, if results.contains_key(&part_result) {None} else {Some(operators)}); } Some(next) => { let next_digit = T::from_u8(*next).unwrap(); // führt Multiplikation und Division durch for operator in [Operator::Multiplicate, Operator::Divide] { multiplicate_divide(iter.clone(), results, operator_index + 2, match operator { Operator::Multiplicate => part_result * next_digit, Operator::Divide => { /* Ist das Ergebnis der Division keine ganze Zahl, wird diese * abgebrochen. */ if part_result \% next_digit != T::zero() {continue;} part_result / next_digit } /* wird nie ausgeführt. Nur vorhanden, da bei einer match-Anweisung * alle möglichen Werte abgedeckt werden müssen. */ _ => T::zero(), // Methode returned eine Null des Typs T }, // verwendeter Operator wird in einer Bitmap gespeichert. operators | (operator as u64) << operator_index); } } } } /* rekursive Funktion, die Strichrechnung auf einer Sequenz der Zwischenergebnisse durchführt und * die Ergebnisse mithilfe der Struktur ResultStore speichert. */ fn add_sub<'a, T: BasicInteger + 'static> (mut iter: impl Clone + Iterator>, results: &mut ResultStore, part_result: T, operators: Option) { match iter.next() { None => { // speichert das Rätsel, wenn das Ergebnis eine natürliche Zahl ist if part_result > T::zero() {results.store(part_result, operators);} } Some(next) => { // für jedes mögliche Zwischenergebnis ... for (next_result, part_operators) in &next.results { // ... wird Addition und Subtraktion durchführt. for operator in [Operator::Add, Operator::Subtract] { add_sub(iter.clone(), results, match operator { Operator::Add => part_result + *next_result, Operator::Subtract => part_result - *next_result, /* wird nie ausgeführt. Nur vorhanden, da bei einer match-Anweisung * alle möglichen Werte abgedeckt werden müssen. */ _ => T::zero(), }, /* Wenn mindestens einer der beiden verrechneten Zwischenergebnisse * uneindeutig ist, ist das resultierende Ergebnis auch uneindeutig. */ if operators == None || *part_operators == None {None} else { // Ansonsten werden die Teiloperatoren zusammengefasst gespeichert. Some(operators.unwrap() | part_operators.unwrap() | (operator as u64) << 2 * next.last_operator.unwrap()) } ); } } } } } // gibt den Operatorenindex vor dem entsprechenden Operandenindex zurück fn last_operator_helper(index: usize) -> Option { if index == 0 {None} else {Some(index as usize - 1)} } // Hilfsfunktion, um eine einzelne Ziffer als Zwischenergebnis hinzufügen fn insert_digit(digits: &[u8], i: usize) -> PartOperation { let mut result_map: HashMap> = HashMap::new(); // Some(0) heißt, dass keine Operatoren verwendet wurden result_map.insert(T::from_u8(digits[i]).unwrap(), Some(0)); PartOperation{ results: result_map, last_operator: last_operator_helper(i), } } \end{minted} \end{document}