779 lines
43 KiB
TeX
779 lines
43 KiB
TeX
\documentclass[a4paper,12pt,ngerman]{scrartcl}
|
|
\usepackage{babel}
|
|
\usepackage[T1]{fontenc}
|
|
\usepackage[utf8]{inputenc}
|
|
\usepackage[a4paper,margin=2.5cm,footskip=2cm]{geometry}
|
|
\DeclareUnicodeCharacter{25CB}{$\circ$}
|
|
|
|
% Kopf- und Fußzeilen
|
|
\usepackage{scrlayer-scrpage, lastpage}
|
|
\setkomafont{pageheadfoot}{\large\textrm}
|
|
\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}
|
|
\usepackage{forloop}
|
|
|
|
% Diese beiden Pakete müssen zuletzt geladen werden
|
|
\usepackage{hyperref} % Anklickbare Links im Dokument
|
|
\usepackage{cleveref}
|
|
|
|
% Daten für die Titelseite
|
|
\title{40. Bundeswettbewerb Informatik}
|
|
\author{Marcel Zinkel}
|
|
|
|
\newcommand{\beispiel}[1] {
|
|
hexmax#1.txt:
|
|
\inputminted[breaklines,breakanywhere]{text}{Aufgabe3-HexMax/ergebnisdateien/#1.txt}
|
|
}
|
|
|
|
\newcommand{\rechen}[1] {
|
|
\inputminted[breaklines]{text}{Aufgabe2-Rechenraetsel/ergebnisdateien/#1.txt}
|
|
}
|
|
|
|
\begin{document}
|
|
|
|
\maketitle
|
|
|
|
Der Bundeswettbewerb Informatik ist ein seit 1980 jedes Jahr stattfindender
|
|
Schülerwettbewerb, der die Schüler für die Informatik begeistern soll. Dabei
|
|
soll die Teilnehmer ein Programm entwickeln, das das in der Aufgabenstellung
|
|
beschriebene Problem löst. Außerdem soll der Lösungsweg dokumentiert werden. Der
|
|
Wettbewerb wird in drei Runden ausgetragen. Die Aufgaben der ersten beiden
|
|
Runden werden zu Hause bearbeitet. Die besten der zweite Runde werden zur
|
|
Endrunde eingeladen, die bei einem jährlich wechselnden Sponsor ausgerichtet
|
|
wird. Weitere Informationen zum Bundeswettbewerb Informatik kann man auf der
|
|
\href{https://bwinf.de/bundeswettbewerb/}{offiziellen Webseite} erhalten.
|
|
|
|
Ich habe dieses Jahr auch teilgenommen und im Folgenden kann meine Einsendungen
|
|
der ersten beiden Runden finden. Dabei habe ich beim Zusammenstellen noch
|
|
geringfügige Überarbeitungen vorgenommen und einige Beispiele entfernt, damit
|
|
die Arbeit übersichtlicher wird.
|
|
|
|
\tableofcontents
|
|
|
|
\vspace{0.5cm}
|
|
|
|
\part{Runde 1}
|
|
In der ersten Runde musste man mindestens drei von fünf Aufgaben bearbeiten, wobei die
|
|
besten drei gewertet werden. Ich habe die Aufgabe 1, 2 und 4 bearbeitet und mit
|
|
15 Punkten die Höchstpunktzahl erreicht und mich damit für die zweite Runde
|
|
qualifiziert. Der Quelltext meiner Programme, die Aufgabenstellung und weitere
|
|
Beispielausgaben findet man in meinem
|
|
\href{https://git.zinkel.org/MrGeorgen/bwinf40-runde1}{Git-Repository}.
|
|
|
|
\section{Aufgabe 1: Schiebeparkplatz}
|
|
Auf einen Parkplatz parken die Autos senkrecht zur Straße. Vor diesen Autos
|
|
parken außerdem noch welche parallel zur Straße. Im folgenden Bild kann solch einen
|
|
Parkplatz sehen.
|
|
\begin{center}
|
|
\includegraphics{Schiebeparkplatz.png}
|
|
\end{center}
|
|
Die quer parkenden Autos können verschoben werden, damit die Autos, die dahinter
|
|
parken, rausfahren können. Es soll ein Programm geschrieben werden, das bei
|
|
einer gegebenen Parkplatzsituation für jedes normal parkende Auto ausgibt,
|
|
wie die quer parkenden Autos verschoben werden müssen, damit es ausfahren kann.
|
|
Dabei sollen möglichst wenige Autos verschoben werden.
|
|
|
|
\subsection{Lösungsidee}
|
|
Für jede normale Textdatei wird die ASCII-Codierung verwendet bzw. ein
|
|
Zeichensatz, der auf ASCII basiert und zusätzliche Sonderzeichen enthält, wobei
|
|
die Codes, die bereits in ASCII enthalten sind, übernommen wurden. Die
|
|
ASCII-Codes für die Buchstaben sind entsprechend dem Alphabet hintereinander
|
|
angeordnet. Dies ist sehr nützlich, da somit eine Liste der Buchstaben und deren
|
|
Position im Alphabet nicht benötigt wird. So kann der Buchstabe des nächsten
|
|
einfach bestimmt werden.
|
|
|
|
Zur Lösung des Parkplatzproblems werden die Autos, wenn möglich nach links bzw.
|
|
rechts verschoben, bis die Parklücke frei ist. Je nachdem, in welche Richtung
|
|
weniger Autos verschoben werden müssen, wird die Verschiebungsrichtung gewählt.
|
|
|
|
\subsection{Umsetzung}
|
|
Da die Lösung des Problems keine besondere Library benötigt und die Anforderungen
|
|
an die Ausführungsgeschwindigkeit gering sind, hätte man fast jede Programmiersprache
|
|
wählen können. Ich habe mich für Go entschieden.
|
|
|
|
Das Programm akzeptiert als Argumente eine beliebige Anzahl an Pfaden zu Parkplatzdateien.
|
|
Für das Iterieren über die Argumente wird eine for-Schleife benutzt.
|
|
Innerhalb der Schleife wird die Eingabedatei ausgelesen. Anhand des ersten und letzten
|
|
Buchstabens der Autos auf den normalen Parkplätzen wird die Anzahl an Parkplätzen
|
|
bestimmt. Anschließend wird eine Slice\footnote{ein dynamisch vergrößerbares Array in Go}
|
|
mit den Buchstaben der quer parkenden Autos befüllt an den Indexen, an denen sie die
|
|
normalen Parkplätze blockieren.
|
|
|
|
In einer for-Schleife wird die Funktion \mintinline{go}|move| je Index der Parkplätze doppelt
|
|
für beide Verschiebungsrichtungen aufgerufen.
|
|
In der Funktion \mintinline{go}|move| wird ein Auto verschoben, wenn nicht das Ende des
|
|
Parkplatzes erreicht ist. Die Funktion ruft sich rekursiv auf, um weitere Autos zu
|
|
verschieben. Je nachdem, in welche Richtung weniger Autos verschoben werden müssen,
|
|
wird sich für das Verschieben in diese Richtung entschieden.
|
|
Wenn es allerdings gleich viele sind, ist die geringere Anzahl der verschobenen
|
|
Plätze aller Autos ausschlaggebend für das Verschieben in diese Richtung.
|
|
|
|
\subsection{Beispiele}
|
|
Zunächst habe ich das Programm mit dem vorhin abgebildeten Parkplatz
|
|
ausprobiert:
|
|
\begin{minted}[]{text}
|
|
beispieldaten/parkplatz0.txt:
|
|
A:
|
|
B:
|
|
C: H 1 rechts
|
|
D: H 1 links
|
|
E:
|
|
F: H 1 links, I 2 links
|
|
G: I 1 links
|
|
\end{minted}
|
|
Diese Ausgabe entspricht der Lösung, die in der Aufgabenstellung gegeben wurde.
|
|
|
|
Außerdem habe ich selbst noch weitere Testfälle erstellt, die man unter
|
|
\enquote{a1-Schiebeparkplatz/testdaten} finden kann.
|
|
Als Erstes habe ich getestet, ob das Programm auch mit dem Verschieben
|
|
sehr vieler Autos klarkommt. Es gibt 26 Parkplätze, wovon alle außer die ersten
|
|
beiden mit quer parkenden Autos blockiert sind. Für die quer parkenden Autos
|
|
wurden Kleinbuchstaben verwendet, da alle Großbuchstaben schon belegt sind.
|
|
\begin{minted}[breaklines]{text}
|
|
testdaten/test0.txt:
|
|
A:
|
|
B:
|
|
C: a 2 links
|
|
D: a 1 links
|
|
E: a 2 links, b 2 links
|
|
F: a 1 links, b 1 links
|
|
G: a 2 links, b 2 links, c 2 links
|
|
H: a 1 links, b 1 links, c 1 links
|
|
I: a 2 links, b 2 links, c 2 links, d 2 links
|
|
J: a 1 links, b 1 links, c 1 links, d 1 links
|
|
K: a 2 links, b 2 links, c 2 links, d 2 links, e 2 links
|
|
L: a 1 links, b 1 links, c 1 links, d 1 links, e 1 links
|
|
M: a 2 links, b 2 links, c 2 links, d 2 links, e 2 links, f 2 links
|
|
N: a 1 links, b 1 links, c 1 links, d 1 links, e 1 links, f 1 links
|
|
O: a 2 links, b 2 links, c 2 links, d 2 links, e 2 links, f 2 links, g 2 links
|
|
P: a 1 links, b 1 links, c 1 links, d 1 links, e 1 links, f 1 links, g 1 links
|
|
Q: a 2 links, b 2 links, c 2 links, d 2 links, e 2 links, f 2 links, g 2 links, h 2 links
|
|
R: a 1 links, b 1 links, c 1 links, d 1 links, e 1 links, f 1 links, g 1 links, h 1 links
|
|
S: a 2 links, b 2 links, c 2 links, d 2 links, e 2 links, f 2 links, g 2 links, h 2 links, i 2 links
|
|
T: a 1 links, b 1 links, c 1 links, d 1 links, e 1 links, f 1 links, g 1 links, h 1 links, i 1 links
|
|
U: a 2 links, b 2 links, c 2 links, d 2 links, e 2 links, f 2 links, g 2 links, h 2 links, i 2 links, j 2 links
|
|
V: a 1 links, b 1 links, c 1 links, d 1 links, e 1 links, f 1 links, g 1 links, h 1 links, i 1 links, j 1 links
|
|
W: a 2 links, b 2 links, c 2 links, d 2 links, e 2 links, f 2 links, g 2 links, h 2 links, i 2 links, j 2 links, k 2 links
|
|
X: a 1 links, b 1 links, c 1 links, d 1 links, e 1 links, f 1 links, g 1 links, h 1 links, i 1 links, j 1 links, k 1 links
|
|
Y: a 2 links, b 2 links, c 2 links, d 2 links, e 2 links, f 2 links, g 2 links, h 2 links, i 2 links, j 2 links, k 2 links, l 2 links
|
|
Z: a 1 links, b 1 links, c 1 links, d 1 links, e 1 links, f 1 links, g 1 links, h 1 links, i 1 links, j 1 links, k 1 links, l 1 links
|
|
\end{minted}
|
|
Die Autos wurden abwechselnd jeweils um ein oder zwei Parkplätze verschoben,
|
|
je nachdem ob das ausfahrende Auto hinter der linken oder rechten Hälfe des quer
|
|
stehenden Autos steht.
|
|
|
|
Die Bezeichner der Autos müssen auch nicht bei A beginnen. Der Beginn mit
|
|
anderen Buchstaben ist möglich. Dies zeigt das folgende Beispiel an der
|
|
Eingabedatei \enquote{parkplatz3.txt} mit veränderten Bezeichnern.
|
|
\begin{minted}[]{text}
|
|
testdaten/test1.txt:
|
|
C:
|
|
D: X 1 rechts
|
|
E: X 1 links
|
|
F:
|
|
G: Y 1 rechts
|
|
H: Y 1 links
|
|
I:
|
|
J:
|
|
K: Q 2 links
|
|
L: Q 1 links
|
|
M: Q 2 links, R 2 links
|
|
N: Q 1 links, R 1 links
|
|
O: Q 2 links, R 2 links, S 2 links
|
|
P: Q 1 links, R 1 links, S 1 links
|
|
\end{minted}
|
|
|
|
\section{Aufgabe 2: Vollgeladen}
|
|
Es sind Hotels mit der Entfernung vom Start und einer Bewertung gegebenen. Man
|
|
soll ein Programm schreiben, dass eine Route zu einem Ziel über diese Hotels
|
|
bildet. Dabei darf an einem Tag nur sechs Stunden gefahren werden und das Ziel
|
|
muss innerhalb fünf Tagen erreicht werden. Dabei soll die niedrigste Bewertung
|
|
eines angesteuerten Hotels möglichst hoch sein.
|
|
|
|
\subsection{Lösungsidee}
|
|
Da die niedrigste Bewertung möglichst hoch sein soll, sollte zuerst versucht
|
|
eine Route mit einer Mindestbewertung von 5.0 zu bilden. Scheitert dies wird
|
|
es mit 4.9, 4.8, ..., 0.1 versucht. Die Routenbildung mit einer bestimmten
|
|
Mindestbewertung kann aus zwei Gründen fehlschlagen:
|
|
\begin{itemize}
|
|
\item Innerhalb der 6 Stunden Fahrzeit gibt es kein Hotel mit der
|
|
Mindestbewertung.
|
|
\item an mehr als 4 Hotels muss gehalten werden
|
|
\end{itemize}
|
|
|
|
\subsection{Umsetzung}
|
|
Die Lösungsidee wird in C implementiert. Eine Hilfsfunktion der
|
|
\href{https://git.zinkel.org/MrGeorgen/advanced_C_standard_library}{advanced
|
|
C standard library},
|
|
die Textdateien ausliest, wird außerdem verwendet.
|
|
Das Programm erhält als Argumente eine beliebige Anzahl Dateipfade
|
|
zu Eingabedateien. Mit einer for-Schleife wird über die Dateipfade iteriert. In
|
|
der Schleife wird die Eingabedatei ausgelesen. Die Anzahl der Hotels und die
|
|
Gesamtfahrzeit werden jeweils in einer Variable abgespeichert. Anschließend wird
|
|
ein Array mit Strukturen, die Hotels darstellen, befüllt. In einer
|
|
do-while-Schleife wird mit einer Bewertung von 5.0, 4.9, ..., 0.1 versucht eine
|
|
Route zu bilden. Im Programm werden die Bewertungen als Integer dargestellt,
|
|
wobei die Bewertung der Eingabedatei mit 10 multipliziert wird. Die Ausgabe ist
|
|
wiederum im ursprünglichen Format. Wenn dies bei einer Bewertung erfolgreich
|
|
ist, wird die Schleife beendet. In dieser Schleife ist wiederum eine
|
|
for-Schleife, die über die Hotels iteriert, worin das letzte Hotel gespeichert
|
|
wird, das mindestens die angestrebte Bewertung hat. Ist das Hotel allerdings
|
|
mehr als 6 Stunden vom letzten Haltepunkt entfernt, muss das letzte Hotel
|
|
verwendet werden, an dem das Halten möglich ist. Es sei denn es gibt kein Hotel
|
|
mit der entsprechenden Bewertung oder es wurde bereits an mehr als drei Hotels
|
|
gehalten. Dann muss mit der nächsten Bewertung fortgefahren werden. Nachdem eine
|
|
Route gefunden wurde, wird diese ausgegeben und eventuell mit der nächsten
|
|
Eingabedatei fortgefahren.
|
|
|
|
\subsection{Beispiele}
|
|
Bei den folgenden Lösungen der gegebenen Beispiele steht jede Zeile für ein
|
|
Hotel, in dem übernachtet wird.
|
|
\begin{minted}[]{text}
|
|
hotels1.txt:
|
|
Entfernung vom Start: 347 Minuten, Bewertung: 2.7
|
|
Entfernung vom Start: 687 Minuten, Bewertung: 4.4
|
|
Entfernung vom Start: 1007 Minuten, Bewertung: 2.8
|
|
Entfernung vom Start: 1360 Minuten, Bewertung: 2.8
|
|
hotels2.txt:
|
|
Entfernung vom Start: 341 Minuten, Bewertung: 2.3
|
|
Entfernung vom Start: 700 Minuten, Bewertung: 3.0
|
|
Entfernung vom Start: 1053 Minuten, Bewertung: 4.8
|
|
Entfernung vom Start: 1380 Minuten, Bewertung: 5.0
|
|
hotels3.txt:
|
|
Entfernung vom Start: 360 Minuten, Bewertung: 1.0
|
|
Entfernung vom Start: 717 Minuten, Bewertung: 0.3
|
|
Entfernung vom Start: 1076 Minuten, Bewertung: 3.8
|
|
Entfernung vom Start: 1433 Minuten, Bewertung: 1.7
|
|
hotels4.txt:
|
|
Entfernung vom Start: 340 Minuten, Bewertung: 4.6
|
|
Entfernung vom Start: 676 Minuten, Bewertung: 4.6
|
|
Entfernung vom Start: 1032 Minuten, Bewertung: 4.9
|
|
Entfernung vom Start: 1316 Minuten, Bewertung: 4.9
|
|
hotels5.txt:
|
|
Entfernung vom Start: 317 Minuten, Bewertung: 5.0
|
|
Entfernung vom Start: 636 Minuten, Bewertung: 5.0
|
|
Entfernung vom Start: 987 Minuten, Bewertung: 5.0
|
|
Entfernung vom Start: 1286 Minuten, Bewertung: 5.0
|
|
\end{minted}
|
|
|
|
\section{Aufgabe 4: Würfelglück}
|
|
Es soll eine \enquote{Mensch ärgere dich nicht}-Simulation geschrieben werden.
|
|
Dabei auch werden modifizierte Würfel eingesetzt mit einer veränderten
|
|
Seitenanzahl und/oder veränderten Augenzahlen. Aus einer gegebenen
|
|
Würfelauswahl sollen alle möglichen Würfelpaare wiederholt gegeneinander
|
|
spielen. Dadurch soll bestimmt werden, wie gut jeder Würfel geeignet ist, um zu
|
|
gewinnen.
|
|
|
|
\subsection{Lösungsidee}
|
|
Mithilfe eines Zufallsgenerators kann eine Seite des Würfels und somit die
|
|
Augenzahl bestimmt werden. Dann muss entschieden werden welche Figur gezogen
|
|
wird. In der folgenden Reihenfolge wird probiert, die Figuren zu ziehen:
|
|
\begin{enumerate}
|
|
\item Wenn eine Figur auf Feld A steht, muss diese gezogen werden.
|
|
\item Wurde eine 6 gewürfelt, wird eine neue Figur rausgebracht.
|
|
\item Die vorderste Figur auf der Laufbahn, die gezogen werden kann, wird gezogen.
|
|
\item Die Figur auf dem Zielfeld, die der Laufbahn am nächsten ist, wird gezogen.
|
|
\end{enumerate}
|
|
Welche Figur auf dem Zielfeld gezogen wird, ist nicht in den Regeln festgelegt.
|
|
Es wäre auch möglich so zu ziehen, dass möglichst keine Figur vor dem Ziel
|
|
blockiert wird, d. h. sie mit keiner möglichen Augenzahl gezogen werden kann.
|
|
Allerdings wird der Fall, dass zwei verschiedene Figuren auf die Zielfelder
|
|
gezogen werden können, selten auftreten. Außerdem wird durch Regeländerung
|
|
zu einer festen Priorität der Figuren auf der Laufbahn klar, dass so weit
|
|
vorausschauende Lösungen nicht in dieser Aufgabe erwartet werden.
|
|
|
|
Sollte der Spieler eine 6 würfeln, ist er nochmal dran, ansonsten der andere.
|
|
Allerdings stellt sich die Frage, ob dieser auch nochmal dran ist, wenn er mit
|
|
der 6 nicht ziehen kann. Nach der Anmerkung gilt \enquote{Wenn kein Stein bewegt
|
|
werden kann, verfällt der Zug}. Hier ist fraglich, was mit \enquote{Zug} gemeint
|
|
ist. Einerseits können mehrere bewegte Figuren hintereinander als ein Zug
|
|
angesehen werden, da der gleiche Spieler dran ist. Allerdings werden zwei
|
|
Figuren gezogen, weshalb es auch als zwei Züge angesehen werden kann. Mit
|
|
\enquote{Wer eine \enquote{6} würfelt, hat nach seinem Zug einen weiteren Wurf
|
|
frei.} wird letzteres unterstützt, weil \enquote{nach seinem Zug} bedeutet, dass
|
|
bereits ein Zug beendet ist, bevor das zweite Mal gewürfelt wird. Es sind also
|
|
zwei Züge sind und nur der erste der beiden verfällt, sodass der Spieler auch
|
|
nach Verfallen eines Wurfes mit einer 6 nochmal würfeln darf.
|
|
|
|
Es ist auch möglich, dass ein Spiel unentschieden ausgeht. Wenn beide Spieler z. B.
|
|
keine 1 auf dem Würfel haben, diese aber brauchen, um ins Ziel zu kommen. Stellt
|
|
sich die Frage, wie unentschiedene Spiele gezählt werden. Eine Möglichkeit wäre die
|
|
Spiele zu wiederholen. Allerdings steht in der Aufgabenstellung: \enquote{wie gut diese
|
|
Würfel geeignet sind, um das Spiel zu gewinnen}. D. h., dass es irrelavant ist, ob
|
|
ein Würfel verloren oder unentschieden gespielt hat, sondern nur, wie oft gewonnen
|
|
wurde.
|
|
|
|
\subsection{Umsetzung}
|
|
Das Programm wird in Rust implementiert. Als Argumente müssen Dateipfade zu den
|
|
Eingabedateien übergeben werden. Das Spielfeld ist in einer Struktur gespeichert.
|
|
Die Laufbahn wird einem 40er-Array innerhalb der Struktur gespeichert. Die
|
|
Figuren der beiden Spieler werden durch 0 und 1 dargestellt. Auch die Spieler werden
|
|
Spieler 0 und Spieler 1 genannt. Ist an der entsprechenden Stelle keine
|
|
Figur, wird dies durch -1 dargestellt. Mit dem gleichen Format hat die Struktur zwei
|
|
Arrays für die Zielfelder für die beiden Spieler. Außerdem hat die Struktur ein Attribut, das
|
|
die Anzahl der Figuren auf den B-Feldern der beiden Spieler in einem Array speichert.
|
|
Schließlich hat die Struktur noch ein Attribut, das in einem 2d-Array die Positionen
|
|
der Figuren abgespeichert, der erste Index 0 oder 1 entsprechend der beiden Spieler und
|
|
der zweite Index für die Figuren des jeweiligen Spielers. Dies ist notwendig, damit schnell
|
|
die Figuren gezogen werden können, ohne das das ganze Laufbahn-Array durchsucht werden muss.
|
|
Die Methode \mintinline{rs}|step| der Struktur \mintinline{rs}|Field| zieht die Figuren unter Angabe einer
|
|
Figur und dem Würfelergebnis, wenn es möglich ist, und gibt je nach Erfolg
|
|
einen Boolean zurück. Außerdem ruft sie die Methode \mintinline{rs}|beat| auf, um die Figur zu
|
|
schlagen, die dem Zug im Weg stehen.
|
|
|
|
In der \mintinline{rs}|main| Funktion wird mit einer for-Schleife über die Eingabedateien iteriert.
|
|
In einer weiteren for-Schleife werden alle möglichen Würfelkombinationen ermittelt.
|
|
Wie oft gespielt wird, kann durch die Variable \mintinline{rs}|runs| verändert werden.
|
|
Eine while-Schleife läuft, solange das Spiel läuft. Mit der \enquote{rand}
|
|
Bibliothek werden Zufallszahlen erstellt und die Augenzahl bestimmt. Dann wird
|
|
entsprechend des oben beschriebenen Algorithmus die Methode
|
|
\mintinline{rs}|step| aufgerufen.
|
|
Wurde erfolgreich ein Zug gemacht, wird überprüft, ob der Spieler gewonnen hat.
|
|
Konnte nicht gezogen werden, wird in einem Hashset die Augenzahl gespeichert.
|
|
Kann bei keiner Augenzahl bei beiden Spielern eine Figur bewegt werden, wird das Spiel
|
|
für Unentschieden erklärt. Wurden alle Spiele simuliert, wird das Ergebnis ausgegeben.
|
|
|
|
\subsection{Beispiele}
|
|
Es folgen die Ergebnisse zweier durchgeführten Simulationsreihen.
|
|
\begin{minted}[breaklines]{text}
|
|
beispieldaten/wuerfel2.txt:
|
|
1. Würfel: Würfelseiten: [1, 6, 6, 6, 6, 6], Siege: 783855, Siegwahrscheinlichkeit: 0.97981875, Niederlagen: 16145, Niederlagewahrscheinlichkeit: 0.02018125, Unentschieden: 0, Unentschiedenwahrscheinlichkeit: 0
|
|
2. Würfel: Würfelseiten: [1, 1, 6, 6, 6, 6], Siege: 603829, Siegwahrscheinlichkeit: 0.75478625, Niederlagen: 196171, Niederlagewahrscheinlichkeit: 0.24521375, Unentschieden: 0, Unentschiedenwahrscheinlichkeit: 0
|
|
3. Würfel: Würfelseiten: [1, 1, 1, 6, 6, 6], Siege: 404042, Siegwahrscheinlichkeit: 0.5050525, Niederlagen: 395958, Niederlagewahrscheinlichkeit: 0.4949475, Unentschieden: 0, Unentschiedenwahrscheinlichkeit: 0
|
|
4. Würfel: Würfelseiten: [1, 1, 1, 1, 6, 6], Siege: 205234, Siegwahrscheinlichkeit: 0.2565425, Niederlagen: 594766, Niederlagewahrscheinlichkeit: 0.7434575, Unentschieden: 0, Unentschiedenwahrscheinlichkeit: 0
|
|
5. Würfel: Würfelseiten: [1, 1, 1, 1, 1, 6], Siege: 3040, Siegwahrscheinlichkeit: 0.0038, Niederlagen: 796960, Niederlagewahrscheinlichkeit: 0.9962, Unentschieden: 0, Unentschiedenwahrscheinlichkeit: 0
|
|
beispieldaten/wuerfel3.txt:
|
|
1. Würfel: Würfelseiten: [1, 2, 5, 6], Siege: 753656, Siegwahrscheinlichkeit: 0.753656, Niederlagen: 246344, Niederlagewahrscheinlichkeit: 0.246344, Unentschieden: 0, Unentschiedenwahrscheinlichkeit: 0
|
|
2. Würfel: Würfelseiten: [1, 2, 3, 4, 5, 6, 7, 8], Siege: 612055, Siegwahrscheinlichkeit: 0.612055, Niederlagen: 387945, Niederlagewahrscheinlichkeit: 0.387945, Unentschieden: 0, Unentschiedenwahrscheinlichkeit: 0
|
|
3. Würfel: Würfelseiten: [1, 2, 3, 4, 5, 6], Siege: 593636, Siegwahrscheinlichkeit: 0.593636, Niederlagen:
|
|
406364, Niederlagewahrscheinlichkeit: 0.406364, Unentschieden: 0, Unentschiedenwahrscheinlichkeit: 0
|
|
4. Würfel: Würfelseiten: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], Siege: 446248, Siegwahrscheinlichkeit: 0.446248, Niederlagen: 553752, Niederlagewahrscheinlichkeit: 0.553752, Unentschieden: 0, Unentschiedenwahrscheinlichkeit: 0
|
|
5. Würfel: Würfelseiten: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], Siege: 440136, Siegwahrscheinlichkeit: 0.440136, Niederlagen: 559864, Niederlagewahrscheinlichkeit: 0.559864, Unentschieden: 0, Unentschiedenwahrscheinlichkeit: 0
|
|
6. Würfel: Würfelseiten: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], Siege: 154269, Siegwahrscheinlichkeit: 0.154269, Niederlagen: 845731, Niederlagewahrscheinlichkeit: 0.845731, Unentschieden: 0, Unentschiedenwahrscheinlichkeit: 0
|
|
\end{minted}
|
|
Allgemein sind die Würfel, mit der größten Wahrscheinlichkeit eine 6 zu würfeln,
|
|
am besten. Zum einen, da eine 6 benötigt wird, um rauszukommen. Außerdem kann man
|
|
nochmal würfeln, auch wenn man mit der 6 nicht ziehen konnte. Sehr große Augenzahlen
|
|
dagegen sind zwar gut, um viele Schritte auf einmal zu gehen. Allerdings sind sie
|
|
kurz vor dem Ziel von Nachteil, da man mit ihnen nicht mehr gehen kann.
|
|
|
|
\part{Runde 2}
|
|
Zum Anlass des Jubiläums (40. Wettbewerb) gibt es diesmal eine Bonusaufgabe
|
|
zusätzlich zu den normalen drei Aufgaben. Aus diesen vier Aufgaben müssen zwei
|
|
ausgewählt werden. Der Quelltext meiner Programme, die Aufgabenstellung und
|
|
weitere Beispielausgaben findet man in meinem
|
|
\href{https://git.zinkel.org/MrGeorgen/bwinf40-runde2}{Git-Repository}.
|
|
|
|
\section{Aufgabe 2: Rechenrätsel}
|
|
Das Programm soll Rechenrätsel erstellen, bei denen die Operanden aus einer
|
|
einzigen Ziffer bestehen. Das Ergebnis des Terms muss positiv sein. Es soll nur
|
|
eine Möglichkeit geben, die Grundrechenarten als Operatoren zwischen die
|
|
Operanden einzusetzen, sodass die Gleichung erfüllt ist. Ein Beispiel für so ein
|
|
Rätsel ist: $4\cdot4\cdot3=13$
|
|
|
|
\subsection{Lösungsidee}
|
|
\subsubsection{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.
|
|
|
|
\subsubsection{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.
|
|
|
|
\subsubsection{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}[breaklines]{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.
|
|
|
|
\subsection{Umsetzung}
|
|
\subsubsection{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}
|
|
|
|
\subsubsection{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.
|
|
|
|
\subsubsection{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.
|
|
|
|
\subsection{Beispiele}
|
|
\rechen{2}
|
|
\rechen{3}
|
|
\rechen{6}
|
|
\rechen{15}
|
|
\rechen{26}
|
|
|
|
\section{Aufgabe 3: HexMax}
|
|
Mit Stäbchen wird eine hexadezimale Zahl dargestellt wie bei einer
|
|
Siebensegmentanzeige. Ein Programm soll geschrieben werden, dass bei einer
|
|
gegebenen Maximalzahl für die Umlegungen, die Stäbchen so umgelegt werden,
|
|
dass die Zahl möglichst groß wird.
|
|
|
|
\subsection{Lösungsidee}
|
|
Durch ebenso häufiges Hinlegen und Wegnehmen der Stäbchen erhält man eine Hex-Zahl,
|
|
die man auch durch Umlegen der Stäbchen erreichen kann. Der Algorithmus kann also erstmal mehr
|
|
Stäbchen hinlegen wie wegnehmen oder umgekehrt, solange am Ende die Anzahl der
|
|
hingelegten Stäbchen gleich der der weggenommenen Stäbchen ist.
|
|
|
|
Die größte Zahl erhält man, wenn man möglichst die vorderen Ziffern erhöht. Der
|
|
Algorithmus geht, angefangen mit der ersten Ziffer, jede Ziffer der Zahl durch.
|
|
Davon ausgenommen sind Ziffern, die schon geändert wurden. Bei jeder Ziffer,
|
|
sofern sie nicht schon F ist, wird probiert sie auf F,E,... umzulegen. Dabei
|
|
wird gezählt,
|
|
wie viele Stäbchen weggenommenen und hingelegt werden müssen. Überschreitet
|
|
weder die Gesamtzahl der weggenommenen Stäbchen, noch die der hingelegten Stäbchen
|
|
die gegebene maximale Anzahl der Umlegungen, wird die Ziffer entsprechend
|
|
geändert. Ansonsten wird probiert die Ziffer zu der nächst kleineren Ziffern zu
|
|
ändern. Dies wird so lange wiederholt, bis die Änderung der Ziffer erfolgreich
|
|
war oder bereits alle Ziffern, die größer sind, ausprobiert wurden. Danach wird
|
|
zu der nächsten Ziffer übergegangen.
|
|
|
|
Nachdem die vorderen Ziffern entsprechend erhöht wurden, kann es sein, dass noch
|
|
Stäbchen benötigt werden oder loszuwerden sind, damit gleich viele Stäbchen
|
|
weggenommenen wie hingelegt wurden. Da zuvor schon die Ziffern nach Möglichkeit
|
|
erhöht wurden, kann dies nur erreicht werden, indem Ziffern verringert werden.
|
|
Damit das nicht so stark ins Gewicht fällt, wird über die Ziffern von hinten
|
|
iteriert. Ziffer für Ziffer wird nun probiert, die Ziffer so zu ändern, dass sich
|
|
der Abstand zwischen der Anzahl der hingelegten und der weggenommenen Stäbchen
|
|
verringert. Es kann auch eine vorherige Änderung der Ziffer wieder rückgängig
|
|
gemacht
|
|
werden. Es kommt zu einem Fehler, wenn man bei einer hinteren Ziffer weniger
|
|
Stäbchen hätte loswerden bzw. wegnehmen sollen, um später bei einer Ziffer, die
|
|
weiter vorne ist, mehr Stäbchen hinlegen bzw. wegnehmen zu können. Wenn sie
|
|
dadurch größer würde oder es dadurch überhaupt erst möglich wäre den
|
|
Ausgleichsvorgang schon bei ihr abzuschließen, ist das Ergebnis falsch.
|
|
Glücklicherweise tritt dieser Fall bei den gegebenen Beispielen nicht ein. Unter
|
|
\ref{negativ} findet sich noch ein entsprechendes Negativbeispiel. Auch bei
|
|
diesem Algorithmusteil darf natürlich nicht die maximale Anzahl der Umlegungen
|
|
überschritten werden. Der Algorithmus wird so lange wiederholt bis die maximale
|
|
Anzahl der Umlegungen ausgeschöpft wurde.
|
|
|
|
Schließlich werden Paare von jeweils einem hingelegten und einem weggenommenen
|
|
Stäbchen gebildet, die eine Umlegung ergeben. Theoretisch könnte es passieren,
|
|
dass dabei \enquote{die Darstellung einer Ziffer komplett \enquote{geleert}}
|
|
wird. Praktisch tritt dieser Fall bei den gegebenen Beispielen jedoch nicht ein.
|
|
|
|
Sei $n$ die Anzahl der Ziffern, so hat der Algorithmus im besten Fall eine
|
|
Laufzeit von $O(n) = n$, wenn keine Wiederholung notwendig ist. Dies ist für die
|
|
Beispiele 2-5 auch die tatsächliche Laufzeit. Da es maximal $n$ Wiederholung
|
|
geben kann, ist die Laufzeit im schlechtesten Fall $O(n) = n^2$
|
|
|
|
\subsection{Umsetzung}
|
|
\subsubsection{Umgebung und Bibliotheken}
|
|
Die Lösungsidee wird in Rust implementiert. Zum Erleichtern der Implementierung
|
|
habe ich noch zwei crates\footnote{Abhängigkeiten in Rust} benutzt:
|
|
\begin{enumerate}
|
|
\item Mit clap werden die Kommandozeilenargumente verarbeitet.
|
|
\item derive\_more bietet u. a. die Möglichkeit die einzelnen Attribute
|
|
einer Struktur jeweils zu addieren oder zu subtrahieren wie bei
|
|
einem Vektor.
|
|
\end{enumerate}
|
|
|
|
\subsubsection{Benutzung}
|
|
Dem Programm muss als Argument der Dateipfad zu der Eingabedatei übergeben
|
|
werden. Außerdem können noch weitere Optionen angepasst werden. Mit der Option
|
|
-d kann die Anzahl der Ziffern, die beim Ausgeben des Zwischenstands der
|
|
Umlegungen maximal in einer Zeile anzeigt werden sollen, geändert werden.
|
|
Standardmäßig sind dies 20 Ziffern, da jede Ziffer ein
|
|
ASCII-Art\footnote{ASCII-Art ist die Darstellung eines Bildes oder Piktogramms
|
|
mit Zeichen der ASCII-Codierung.} ist und
|
|
dementsprechend Platz braucht. Beim Verwenden des flags -n wird die Anzahl
|
|
der durchgeführten Umlegungen ausgegeben. Benutzt man den flag -s, so wird der
|
|
Zwischenstand der 7-Segmentanzeige nach jeder Umlegung ausgegeben. Schließlich
|
|
kann man den flag -l verwenden, für den Latex-Code mit dem Ergebnis des
|
|
Programms. Dies ist hilfreich, da dafür gesorgt wird, dass kein Seitenumbruch
|
|
mitten in einem ASCII-Art auftritt.
|
|
|
|
\subsubsection{Implementierungsart}
|
|
Die Implementierung ist in zwei Dateien aufgeteilt. In der Datei lib.rs wird die
|
|
größtmögliche Hex-Zahl ermittelt und die Umlegungen werden entsprechend
|
|
generiert. In der Datei main.rs werden die Nutzereingaben verarbeitet und das
|
|
Ergebnis sowie weitere Informationen ausgegeben.
|
|
|
|
Kommen wir zum Code in der Datei main.rs: Zuerst werden in der
|
|
main-Funktion die Kommandozeilenargumente verarbeitet. Danach wird die Funktion
|
|
\mintinline{rs}|hexmax::largest_hex| aufgerufen. Diese ermittelt die
|
|
größtmögliche Hex-Zahl mit der gegebenenen maximalen Anzahl der Umlegungen.
|
|
Danach wird die Hex-Zahl mit der Funktion \mintinline{rs}|hexmax::to_hex_str| zu
|
|
einem String konvertiert und ausgegeben. Falls die Zwischenstände der Umlegungen
|
|
ausgegeben werden sollen, wird die Funktion \mintinline{rs}|hexmax::gen_swaps|
|
|
aufgerufen, die die Umlegungen zurückgibt. Anschließend wird jede Umlegung
|
|
hintereinander ausgeführt und die 7-Segmentanzeige nach jeder Umlegung mithilfe
|
|
der Funktion \mintinline{rs}|swap_print| als ASCII-Art ausgegeben.
|
|
|
|
In der Datei lib.rs gibt ein konstantes Array namens \mintinline{rs}|HEX|, dass
|
|
am Index der jeweiligen Ziffer eine Bitmap der 7-Segmentrepräsentation enthält.
|
|
Bei 1 leuchtet das Segment und bei 0 nicht.
|
|
|
|
Die Funktion \mintinline{rs}|change_digits| durchläuft Ziffer für Ziffer eines
|
|
als Argument übergebenen Iterators. Für jede Ziffer wird nun jede mögliche
|
|
Änderung der Ziffer durchgegangen, angefangen mit F,E,... . Dabei wird nach
|
|
folgender Vorgehensweise berechnet, wie viele Stäbchen im Vergleich zur
|
|
ursprünglichen Ziffer hingelegt und weggenommenen werden müssen:
|
|
|
|
Sei $u$ die 7-Segmentbitmap der ursprünglichen Ziffer und $n$ die der neuen
|
|
Ziffer:
|
|
\begin{align}
|
|
c = u \oplus n \\
|
|
h = c \& n \label{h} \\
|
|
g = c \& u \label{g}
|
|
\end{align}
|
|
Mit diesen Formeln erhält man eine Bitmap der hingelegten Stäbchen $h$ und der
|
|
weggenommenen Stäbchen $g$. Zählt man nun die Einsen der binären Schreibweise
|
|
von $h$ oder $g$, so ergibt sich die Anzahl der hingelegten bzw. weggenommenen
|
|
Stäbchen. Mit diesen sowie der Gesamtzahl der hingelegten bzw. weggenommenen
|
|
Stäbchen wird eine der Funktion \mintinline{rs}|change_digits| übergebene
|
|
Lambdafunktion aufgerufen, sofern bei der Ziffernänderung nicht die maximale Anzahl der
|
|
Umlegungen überschritten werden würde. Diese entscheidet mit diesen Angaben, ob die Ziffer
|
|
entsprechend geändert werden soll. Diese Änderung ist entweder final oder es
|
|
wird probiert, die Ziffer auf einen niedrigen Wert zu ändern.
|
|
|
|
In der Funktion \mintinline{rs}|largest_hex| wird zuerst die Eingabedatei
|
|
ausgelesen. Im Vector \mintinline{rs}|digits| werden die einzelnen Ziffern der
|
|
gegebenen Hex-Zahl gespeichert. Innerhalb einer for-Schleife wird der
|
|
Algorithmus wiederholt, bis die Anzahl der maximalen Umlegungen ausgeschöpft ist
|
|
oder er schon so oft wiederholt wurde wie die Anzahl der Ziffern. Letzteres
|
|
bedeutet nämlich, dass keine größere Zahl mehr gefunden werden kann, die alle
|
|
Umlegungen ausschöpft. Zuerst wird probiert die vorderen Ziffern zu erhöhen.
|
|
Dafür wird die Funktion \mintinline{rs}|change_digits| mit einer Lambdafunktion
|
|
aufgerufen, die gleich die erste Ziffernänderung final akzeptiert. Die erste ist
|
|
dabei automatisch die größtmögliche Erhöhung.
|
|
|
|
Wenn die Anzahl der hingelegten ungleich der weggenommenen Stäbchen ist, müssen
|
|
noch Stäbchen genommen bzw. hingelegt werden. Dafür wird Ziffer für Ziffer von
|
|
hinten mithilfe der Funktion \mintinline{rs}|change_digits| betrachtet. Jede
|
|
Ziffer wird nun so geändert, dass der Abstand zwischen den hingelegten und
|
|
weggenommenen Stäbchen am geringsten ist. Nachdem alle Ziffern durchgegangen
|
|
worden sind, ist die Anzahl der hingelegten gleich der weggenommenen Stäbchen.
|
|
Allerdings kann es sein, dass dafür eine vorherige Änderung rückgängig gemacht
|
|
werden musste und die maximale Anzahl der Umlegungen nicht ausgeschöpft wurde.
|
|
In diesem Fall wird der Algorithmus nochmal wiederholt.
|
|
|
|
Die Funktion \mintinline{rs}|gen_swaps| generiert aus den Änderungen der Ziffern
|
|
konkrete Umlegungen. Dafür wird in einer for-Schleife über jede Ziffernänderung
|
|
iteriert. Wie in \eqref{h} und \eqref{g} beschrieben, wird ermittelt welche
|
|
Stäbchen dafür hingelegt und weggenommenen werden müssen. Die Bitmaps $h$ und
|
|
$g$ werden Bit für Bit durchlaufen. Für jede 1, d. h. das Stäbchen wurde
|
|
geändert, wird diese Änderung dem Vector \mintinline{rs}|moves_put| angehängt,
|
|
wenn das Stäbchen hingelegt wurde. Wenn es weggenommenen wurde, dann wird sie
|
|
dem Vector \mintinline{rs}|moves_taken| angehängt. Die beiden
|
|
Vectors\footnote{Da Vector der Name der Struktur ist, habe ich hier auch die
|
|
englische Mehrzahl verwendet. Eigentlich müsste es heißen \enquote{Variablen der
|
|
Struktur Vector}} werden schließlich zurückgegeben. Ordnet man die Elemente der
|
|
Vectors mit dem gleichen Index einander zu, so erhält man die Umlegungen.
|
|
|
|
Die Funktion \mintinline{rs}|to_hex_str| konvertiert eine Slice mit den Ziffern
|
|
zu einem hexadezimalen String. Dies wird erreicht, indem mit einer for-Schleife
|
|
über alle Ziffern iteriert wird, und jede Ziffer einzeln zu dem entsprechenden
|
|
Zeichen konvertiert wird.
|
|
|
|
\subsection{Beispiele}
|
|
\subsubsection{gegebene Beispiele}
|
|
\beispiel{0}
|
|
Die Zahl D24 wird erst mit 3 weggenommenen und 2 hingelegten Stäbchen auf F24
|
|
erhöht. Danach kann man allerdings das übrige Stäbchen nicht bei den Ziffern 4
|
|
oder 2 loswerden, sodass die Zahl auf E24 geändert wird, da dort gleich viele
|
|
Stäbchen hingelegt wie weggenommenen wurden. Darauffolgend wird wieder probiert
|
|
die Ziffern zu erhöhen, wobei die erste Ziffer ausgelassen wird, sodass der
|
|
Algorithmus schließlich zur Lösung EE4 kommt.
|
|
|
|
\newcounter{beispielcounter}
|
|
\forloop{beispielcounter}{1}{\value{beispielcounter}<5}{
|
|
\beispiel{\arabic{beispielcounter}}
|
|
}
|
|
|
|
\subsubsection{Negativbeispiel\label{negativ}}
|
|
\begin{minted}[]{text}
|
|
$ hexmax testdaten/negativBeispiel.txt
|
|
ED8
|
|
\end{minted}
|
|
|
|
Die richtige Lösung wäre F89.
|
|
|
|
\end{document}
|