Die erste Runde in Python lösen

Geschrieben von Johannes Kapfhammer.

Du hast schon ein bisschen Erfahrung in Python und möchtest wissen, wie du am besten die Eingabe/Ausgabe machst? Dann bist du hier goldrichtig.

Du kennst dich gut mit Python aus? Dann schaue dir kurz den Abschnitt “Lösungs-Template” an.

Vorneweg: Dieses Tutorial bezieht sich auf Python 3. Falls du noch Python 2 verwendest, dann ersetze input durch raw_input und lasse die Klammern um print weg, dann sollte es auch gehen.

Zunächst wird allgemeiner Python-Code gezeigt und unten steht, wie man diesen in die verschiedenen Editoren/IDEs/Notebooks einbauen kann.

Beispiel-Lösung: Seilbahn

Als Beispiel lösen wir hier die Aufgabe Seilbahn aus der ersten Runde 2016. Solltest du dich für die Lösungen interessieren, findest du diese hier. Fürs Verständnis dieses Artikels spielt das aber keine Rolle.

Eingabe

Die Eingabe entspricht so ziemlich dem Standardgerüst, dem die meisten Aufgaben folgen:

Auf der ersten Zeile steht die Zahl \(T\), die Anzahl Seilbahnen, die Stofl bauen möchte. Für jede dieser Seilbahnen folgt dann eine Beschreibung der Masten, die folgendermassen aufgebaut ist: Auf der ersten Zeile steht eine Zahl \(N\), die Anzahl der Masten und auf der zweiten Zeile stehen \(N\) ganze Zahlen, die Höhen \(h_i\) der Masten.

Formal entspricht das folgendem Muster:

T
N
h1 h2 h3 ... hN
N
h1 h2 ... hN
N
h1 h2 h3 h4 ... hN
...

Oder konkret am Beispiel:

3
3
3 5 7
4
20 15 10 5
8
1 2 3 4 5 6 7 9

Die einfachste Möglichkeit, um etwas in Python zu lesen, ist input(). Die Funktion liest eine Zeile auf der Standardeingabe und gibt eine Zeichenkette (String) zurück. In der Eingabe oben hätte der erste Aufruf von input() den Rückgabewert "3", der zweite wieder "3", dann "3 5 7", dann "4", dann "20 15 10 5", usw.

Mit Zeichenketten können wir aber wenig anfangen. Schliesslich wollen wir mit Zahlen arbeiten. In Python geht das mit dem Konstruktor von int. Dieser nimmt eine Zeichenkette entgegen und wandelt sie in einen int um. So ist int("3") gleich 3, genau das, was wir wollen.

Damit haben wir schon einen ersten Teil:

T = int(input())
for testcase in range(T):
    N = int(input())
    h = input()  # ???
    answer = "TODO"
    print(f"Case #{testcase}: {answer}")

(Mehr zu der Zeile mit dem print später, es geht zunächst primär um die Eingabe.)

Lassen wir dieses Programm mit obiger Eingabe laufen, erhalten wir:

Case #0: TODO
Case #1: TODO
Case #2: TODO

Das sieht schonmal ganz gut aus.

Die nächste Schwierigkeit ist es, N Zahlen einzulesen, die noch dazu alle auf einer Zeile sind. Da hilft uns die split()-Funktion, welche an Leerzeichen auftrennt. "20 15 10 5".split() gibt ['20', '15', '10', '5'] zurück. Wir sind schon fast da! Die Elemente sind aber noch Zeichenketten, keine Zahlen. Wir müssen noch irgendwie int darauf anwenden.

Da gibt es mehrere Möglichkeiten. Die erste ist mit einer Schleife:

h = []
for x in input().split():
    h.append(int(x))

Hier gehen wir über jedes Element in input().split(). In jedem Durchgang wandeln wir es in einen int um und fügen es der Liste h an.

Falls du List-Comprehensions kennst, geht es damit kürzer:

h = [int(x) for x in input().split()]

Im Grunde passiert hier das gleiche, nur ist die Schleife versteckt in der Definition der Liste.

Es geht aber noch ein ganz wenig kürzer:

h = list(map(int, input().split()))

map(func, list) wendet die Funktion func auf jedes Element an, ist also im Grund genommen [func(x) for x in list]. map gibt aber keine Liste zurück, sondern einen Iterator. Das kann nützlich sein, wenn man nicht alle Elemente benötigt oder nur einmal darüber geht. Wir wollen aber eine Liste, deshalb wandeln wir es in eine Liste um.

Damit wären wir fertig:

T = int(input())
for testcase in range(T):
    N = int(input())
    h = list(map(int, input().split()))
    answer = "TODO""
    print(f"Case #{testcase}: {answer}")

Ausgabe

Die Ausgabe schreibt man am einfachsten mit der Funktion print. print erwartet aber eine Zeichenkette, wir wollen aber "Case #i: answer" schreiben, wobei i der Testfall und answer die Lösung ist.

Es gibt 4 Arten in Python, Zeichenketten zu formatieren:

  • Manuell:

    print("Case #" + str(testcase) + ": " + answer)
    
  • Mit dem Interpolationsoperator %:

    print("Case #%d: %s" % (testcase, answer))
    
  • Mit .format:

    print("Case #{}: {}".format(testcase, answer))
    
  • Mit Literal String Interpolation (ab Python 3.6):

    print(f"Case #{testcase}: {answer}")
    

Wir empfehlen die letzte Variante, da sie für Variablen am übersichtlichsten ist. Ist dein Python-Interpreter nicht neu genug, kann es sein, dass er einen Fehler ausspuckt. In diesem Fall empfehlen wir, auf .format zurückzugreifen.

Lösungs-Template

Es ist übersichtlicher, die Lösung nicht mit dem Code für Eingabe/Ausgabe zu mischen. Das ermöglicht dann auch einfacheres Testen.

Diese Löse-Funktion heisst typischerweise solve (oder solve_sub2 oder solve_cablecar_sub2) und erhält die Eingabe als Python-Objekt (als Liste von Zahlen). Die Funktion sollte auch ein Python-Objekt zurückgeben (z.B. True/False anstatt "yes"/"no").

def solve(n, h):
    d = h[1] - h[0]
    return all(b - a == d for a, b in zip(h, h[1:]))

Das hat als Vorteil, dass man sie leicht testen kann. Nicht nur per direktem Aufruf solve([3,5,7]), sondern auch mit generierten Testdaten, wie z.B. solve(range(100)). Zudem lassen sich die Ausgaben zweier Teilaufgaben leicht vergleichen.

Als nächstes schreiben wir eine Funktion parse: Sie liest die Eingabe für einen Testfall ein und wandelt sie in ein Python-Objekt um.

def parse():
    n = int(input())
    h = list(map(int, input().split()))
    return n, h

Dann noch eine Funktion für die Ausgabe:

def display(answer):
    return "yes" if answer else "no"

Das können wir schon jetzt zusammensetzen.

n, h = parse()
answer = solve(n, h)
output = display(answer)
print(output)

Oder auf einer Zeile:

print(display(solve(*parse())))

Den Rest schreiben wir in die main-Funktion:

def main():
    for i in range(int(input())):
        print(f"Case #{i}: {display(solve(*parse()))}")

if __name__ == "__main__":
    main()

Ausführen

Je nach Entwicklungsumgebung kannst du kleine Änderungen an diesem Template vornehmen, um das Auführen und besonders einfach zu machen.

Editor + Konsole

Die einfachste Kombination ist es, die Funktionen von oben in einem Editor (Emacs, Vim, Sublime, Notepad++) zu schreiben und in der Konsole auszuführen. In vielen Editoren geht das sogar direkt im Editor (als Compile-Command).

Dazu erstellst du am besten pro Aufgabe einen Ordner, schreibst den Code und legst darin die Testdaten ab (sample.in).

Ausführen geht per Konsole:

$ python cablecar-sub2.py <sample.in
Case #0: yes
Case #1: yes
Case #2: no
$ python cablecar-sub2.py <cablecar-sub1.in >cablecar-sub1.out

Je nach System musst du python3 schreiben. Du kannst deine Python-Version wiefolgt herausfinden:

$ python --version
Python 3.6.5

Steht in der Ausgabe “Python 2.7.15” (oder irgendetwas mit 2.X), musst du explizit python3 schreiben.

PyCharm und andere IDEs

Falls es deine IDE nicht unterstützt, die Eingabe umzuleiten, empfehlen wir dir, die Datei von Python aus zu lesen.

Dazu muss du folgende Änderungen vornehmen:

def main():
    # Eingabe/Ausgabe umlenken
    sys.stdin = open("sample.in", "r")
    sys.stdout = open("sample.out", "w")

    # der Rest gleich wie bisher
    for i in range(int(input())):
        print(f"Case #{i}: {display(solve(*parse()))}")

Möchtest du die Ausgabe sehen, kannst du sys.stdout = open("sample.out", "w") einfach auskommentieren.

Jupyter Notebook

Ein Jupyter-Notebook hat den Vorteil, dass man die Funktion direkt testen kann.

In [..]:  solve(3, [3,5,7])
Out[..]:  True
In [..]:  solve(4, [20, 15, 10, 5])
Out[..]:  True
In [..]:  solve(8, [1, 2, 3, 4, 5, 6, 7, 9])
Out[..]:  False

Das macht es einfach, auch grosse Eingaben zu testen:

In [..]:  solve(10000, [42]*10000)
Out[..]:  True

Das Ausführen an den Testdaten wird dafür etwas komplizierter. Zum Testen kann man natürlich main() aufrufen und die Eingabe manuell schreiben. Mit der Zeit wird das aber mühsam, deshalb wollen die Eingabe und Ausgabe umleiten. Würden wir das aber wie im Abschnitt über PyCharm und andere IDEs machen, wäre nachher input() und print(...) “kaputt” und man müsste den Jupyter-Kernel neustarten.

Stattdessen können wir eine Funktion run schreiben:

import sys
def run(infile, outfile):
    global input, print
    old_input = input  # save original input function
    old_print = print  # save original print function
    try:
        with open(infile, "r") as inp, open(outfile, "w") as outp:
            input = inp.readline                       # now input reads from a inp
            def print(*args, **kwargs):                # define a special print
                old_print(*args, **kwargs, file=outp)  # write to output file
                old_print(*args, **kwargs)             # and also show it in jupyter
            main()
    finally:
        input = old_input  # restore input
        print = old_print  # restore print

Um es auszuführen, müssen wir noch die Dateipfade angeben:

run("sample.in", "sample.out")

Falls “sample.in” nicht im aktuellen Verzeichnis liegt, muss der ganze Pfad angegeben werden.

Aufgaben

Wir empfehlen, die folgenden Aufgaben zu lösen.

  • addition: You need to log in in order to submit for this task.

    Addition ist eine sehr einfache Aufgabe, mit ihr kannst du ausprobieren, ob du alles richtig aufgesetzt hast.

  • cablecar: You need to log in in order to submit for this task.

    Das ist die Aufgabe “Seilbahn”, die im Artikel beschrieben wurde.