SPOJ 400 "wrong answer"

[hulkhomer]

Ich schon wieder
Alle möglichen Testfälle die ich mir ausgedacht habe, funktionieren. Aber auf SPOJ funktioniert es nicht.

Habe ich wieder was mit der Größe der möglichen Eingaben übersehen? Es läuft ja auf eine Matrix mit maximal 200 Spalten hinaus. Das sollte aber auch klappen...

(Der Code is von mir. Die Kommentare sind nur auf Englisch, damit ich mir das gleich von Anfang an angewöhne)

Code: Alles auswählen

# SPOJ 400
# c=colums (Spalten)
# r=rows (Zeilen)

c = -1
l_output = []
output=""

while c != 0:
    c = int(input())
    if c == 0:
        break
    output = ""
    l_not_clear = []
    l_clear = []
    inp_str = input()
    r = int(len(inp_str)/c)
    for i in range(r):
        l_not_clear.append(inp_str[i*c:c*(i+1)])    # Split in rows, every second entry still in the wrong order
    for rows in l_not_clear:                        # Reverse entries in every second item
        if l_not_clear.index(rows)%2 != 0:
            rows = rows[::-1]
        l_clear.append(rows)
    for i in range(c):                              # Get i-th letter of each entry and concatenate 
        for rows in l_clear:
            output += rows[i]
    l_output.append(output)
for i in l_output:
    print(i)

[Sirius3]

@hulkhomer: hier ein Testfall wo Dein Programm Probleme macht:

Code: Alles auswählen

2
tathaestst
0

Am Code sind noch andere Dinge unschön: Zeile 7 ist überflüssig; die Bedingung in Zeile 9 ist nie unwahr, also kann man gleich "while True:" schreiben; in Zeile 17: für Ganzzahldivision gibt es //; Variablen sollten erst dann initialisiert werden, wenn sie auch gebraucht werden, Zeile 13 und 15 gehören also viel später hin; die Namensgebung ist noch nicht optimal: c und r haben so eine wichtige Bedeutung für den Algorithmus, dass sie doch etwas aussagekräftigere Namen haben sollten, rows ist nur eine Reihe und i in Zeile 28 assoziiert man mit einer Zahl, was aber keine ist; Der Suffix l_ vor allen Listen ist überflüssig. Wenn jemand append auf ein Objekt aufruft, oder es in einer for-Schleife benutzt, dann ist das doch ganz offensichtlich eine Liste, braucht also nicht extra gekennzeichnet werden;

[hulkhomer]

Danke für deine Hinweise und die Zeit die du investiert hast!

Wer hätte gedacht, dass index() immer nur das erste Auftreten zurückgibt Das hat mich einige Stunden gekostet. Aber vergessen werde ich das auch so schnell nicht mehr.

Die Variablen, Listen usw. hab ich deswegen gleich am Anfang angelegt, damit es übersichtlicher ist. Es leuchtet mir aber auch ein, dass es bei einem größeren Projekt Mist ist, wenn man alles "oben" nachsehen muss.

Gibt es einen Trick, wie man sich geeignete Tests ausdenkt? Ich habe auch einige probiert, bin aber leider nie auf einen gekommen, bei dem dann die gleiche Zeile 2 oder mehrmals auftritt. Und deswegen haben die auch gepasst. Zu unrecht, wie sich herausgestellt hat

Code: Alles auswählen

# SPOJ 400

output = []
while True:
    column = int(input())
    if column == 0:
        break
    
    not_clear = [] 
    inp_str = input()
    row = len(inp_str)//column
    for i in range(row):
        not_clear.append(inp_str[i*column:(i+1)*column])
        # Split in rows (length = column), every second entry still in the wrong order

    count = 0
    clear = []
    for entry in not_clear:  # Reverse entries in every second item
        if count%2 != 0:
            entry = entry[::-1]
        clear.append(entry)
        count+=1
        
    solution = ""
    for i in range(column): # Get i-th letter of each entry and concatenate 
        for entry in clear:
            solution += entry[i]
    output.append(solution)
for text in output:
    print(text)

[Sirius3]

@hulkhomer: jetzt kannst Du Dir noch enumerate und list-comprehension anschauen.

[DaftWullie]

Gibt es einen Trick, wie man sich geeignete Tests ausdenkt?

Nicht unbedingt ein Trick, aber generell muss man unbedingt alle Extremfälle genau durch gehen. Nicht nur die "großen", wo es Speicher- oder Laufzeitprobleme gaben kann, sondern auch die minimalen. Die Testcases bei SPOJ grasen das allermeistens tatsächlich ab. Wenn Dir dann immer noch Ideen für knifflige Testfälle fehlen, solltest Du im SPOJ-Forum nachschauen. Eine Suche nach dem Problemcode (hier TOANDFRO) liefert oft Testfälle, die andere schon gecheckt haben. Aber wie es aussieht kennst Du das Forum dort ja schon.

http://www.spoj.com/problems/TOANDFRO

[darktrym]

Ich hab mich mal dran versucht um dem Essen zu entfliehen.

Code: Alles auswählen

def decrypt(data, column_length):
    ignore_char = "x"
    message  = []
   
    for offset in xrange(column_length):
        line_offset = 0
        for index in xrange(2**16):
            if index % 2 == 0:
                position = offset
            else:
                position = column_length - offset - 1
            try:    
                char = data[line_offset + position]
            except IndexError:
                break
            
            message.append(char)
            if char == ignore_char:
                break
            line_offset += column_length
    return "".join(message)

results = []
while True:
    column_length = int(raw_input(""))
    if column_length == 0:
        break
    results.append(decrypt(raw_input(""), column_length))
    
print "\n".join(results)

[hulkhomer]

@darktrym Wieso nimmst du x raus? So wie ich das verstanden habe, können die zusätzlichen Buchstaben alles mögliche sein. Und x kann ja auch in der Nachricht vorkommen.

[darktrym]

Im Original wurden die Füllzeichen auch nicht ausgegeben, die Idee der Transpositionschiffre ist ganz schon alt.

[snafu]

Ich denke schon, dass man die Füllzeichen mit ausgeben soll. Das sieht man ja auch an den zwei Beispielen. Meine Lösung mit Füllzeichen wird jedenfalls angenommen und benötigt laut SPOJ-Messung 0,00 Sekunden, was schwer vorstellbar ist - aber nunja...

Mein Ansatz war übrigens Slicing, wobei ich aufgrund der Aufgabenstellung mit einem Slice immer nur jedes zweite Element für die Original-Spalte holen konnte. Ein weiterer Slice hat dann die fehlenden Elemente gebracht. Und diese beiden Chunks habe ich dann ebenfalls mittels Slicing ganz unpythonisch in eine mit ``None``-Werten vorbelegte Liste abgelegt, die das Ergebnis zeichenweise darstellt. An der Stelle habe ich bereits auf die korrekte Reihenfolge der Zeichen geachtet - ein ``[::-1]`` war nicht nötig. Das habe ich dann in einer Schleife für jede Spalte gemacht und mich so in der Ergebnis-Liste vorgearbeitet bis alle Spalten verarbeitet waren. Das ``step``-Argument war beim Slicing auf jeden Fall mein Freund.

Es geht sicherlich auch eine ``itertools``-basierte Lösung. Die hatte ich aber aufgegeben, weil mir da ein bißchen zuviel durch die Gegend gereicht wurde bis man zum korrekten Ergebnis gekommen wäre.