Für jede normale Textdatei wird ASCII encoding verwendet bzw. ein Encoding Standard, welcher auf ASCII basiert und zusätzliche Sonderzeichen enthält, wobei die Werte, die bereits in ASCII enthalten sind, übernommen wurden. Die ASCII Codes für die Buchstaben sind entsprechend des Alphabets hintereinander angeordnet. Dies ist sehr nützlich, da somit eine Liste der Buchstaben und deren Position im Alphabet nicht benötigt wird.

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.

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 (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 "move"-Funktion je Index der Parkplätze doppelt für beide Verschiebungsrichtungen aufgerufen. In der "move"-Funktion 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.

Beispiele

Zunächst wird das Programm mit den bereitgestellten Beispieldaten getestet.

parkplatz0.txt:
A: 
B: 
C: H 1 rechts
D: H 1 links
E: 
F: H 1 links, I 2 links
G: I 1 links
parkplatz1.txt:
A: 
B: O 1 rechts, P 1 rechts
C: O 1 links
D: P 1 rechts
E: O 1 links, P 1 links
F: 
G: Q 1 rechts
H: Q 1 links
I: 
J: 
K: R 1 rechts
L: R 1 links
M: 
N: 
parkplatz2.txt:
A: 
B: 
C: O 1 rechts
D: O 1 links
E: 
F: O 1 links, P 2 links
G: P 1 links
H: Q 1 rechts, R 1 rechts
I: P 1 links, Q 1 links
J: R 1 rechts
K: P 1 links, Q 1 links, R 1 links
L: 
M: P 1 links, Q 1 links, R 1 links, S 2 links
N: S 1 links
parkplatz3.txt:
A: 
B: O 1 rechts
C: O 1 links
D: 
E: P 1 rechts
F: P 1 links
G: 
H: 
I: Q 2 links
J: Q 1 links
K: Q 2 links, R 2 links
L: Q 1 links, R 1 links
M: Q 2 links, R 2 links, S 2 links
N: Q 1 links, R 1 links, S 1 links
parkplatz4.txt:
A: Q 1 rechts, R 1 rechts
B: Q 2 rechts, R 2 rechts
C: R 1 rechts
D: R 2 rechts
E: 
F: 
G: S 1 rechts
H: S 1 links
I: 
J: 
K: T 1 rechts
L: T 1 links
M: 
N: U 1 rechts
O: U 1 links
P: 
parkplatz5.txt:
A: 
B: 
C: P 2 links
D: P 1 links
E: Q 1 rechts
F: Q 2 rechts
G: 
H: 
I: R 1 rechts
J: R 1 links
K: 
L: 
M: S 1 rechts
N: S 1 links
O:

Außerdem habe ich noch weitere Testfälle erstellt, die sich im Ordner "testdaten" befinden. 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.

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

Die Autos wurden abwechselend 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 "parkplatz3.txt" mit veränderten Bezeichnern.

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