SPOJ: Grundschulrechnen

numerix · Mittwoch 25. Februar 2009, 11:26

Die schriftlichen Grundrechenarten haben die meisten von uns in der Schule gelernt, einige können es vielleicht immer noch ...

Bei SPOJ gibt es eine nette Aufgabe, die sich damit beschäftigt: http://www.spoj.pl/problems/ARITH/

Dabei geht es nicht darum, ein möglichst kurzes Programm zur Lösung zu schreiben, sondern zunächst mal eins, das überhaupt läuft. Obwohl die Problemstellung nicht schwierig ist und man mit einfachen Python-Mitteln auskommt, kann das eine Weile dauern (jedenfalls, wenn man die Aufgabenstellung nicht GENAU liest - so wie ich

).

Wenn man sich dann ans Optimieren des Codes macht, sollte man ohne weiteres auf den vorderen Python-Rangplätzen landen, denn da ist noch viiiiel Luft.

Falls sich einige hier im Forum beteiligen wollen, können wir natürlich auch unseren eigenen size-contest daraus machen. Ist halt nur mit dem veröffentlichen des Codes so eine Sache.

kbr · Mittwoch 25. Februar 2009, 14:03

Das Problem des nicht genauen Lesens habe ich, wie es scheint, auch. Der Output entspricht genau den Beispielen und ein paar Sonderfälle mit dem Alignment habe ich auch noch berücksichtigt. Dennoch erhalte ich stets nur "wrong answer". Damit kann man natürlich nicht optimieren ... jetzt liegt es erstmal auf Eis, bis ich wieder neu denken kann.

numerix · Mittwoch 25. Februar 2009, 15:55

kbr hat geschrieben:Das Problem des nicht genauen Lesens habe ich, wie es scheint, auch. Der Output entspricht genau den Beispielen und ein paar Sonderfälle mit dem Alignment habe ich auch noch berücksichtigt. Dennoch erhalte ich stets nur "wrong answer". Damit kann man natürlich nicht optimieren ... jetzt liegt es erstmal auf Eis, bis ich wieder neu denken kann.

Ich habe fast 20 Fehlversuche produziert, bis ich die erste funktionierende Lösung hatte ...
Wenn man den Fehler dann gefunden hat, versteht man gar nicht, wie man das bisher übersehen konnte.

Vielleicht helfen dir folgende testcases beim Fehler aufspüren:

Code: Alles auswählen

lines = ["1000-1", "325*440005", "98*9", "99*99", "1+1", "9+9", "1000+9001",
         "7*19", "123451234567890*99","100001*10","1000-1","8-3","2*444444","9999+9"]

sma · Mittwoch 25. Februar 2009, 16:23

Habe schnell eine Lösung zusammengestümpert. War Fun. Geht garantiert besser und kürzer.

Stefan

numerix · Mittwoch 25. Februar 2009, 17:28

sma hat geschrieben:Habe schnell eine Lösung zusammengestümpert. War Fun. Geht garantiert besser und kürzer.

Funktioniert auf jeden Fall nicht ...

name · Mittwoch 25. Februar 2009, 17:39

eval?

numerix · Mittwoch 25. Februar 2009, 18:12

name hat geschrieben:eval?

Ich schätze, du bist im Thread verrutscht und wolltest hier posten? Oder aber ich verstehe nicht, was du meinst ...

derdon · Mittwoch 25. Februar 2009, 19:30

Ich denke, name meint so etwas (natürlich nur der Ansatz):

Code: Alles auswählen

In [34]: lines = ["1000-1", "325*440005", "98*9", "99*99", "1+1", "9+9", "1000+9001",
         "7*19", "123451234567890*99","100001*10","1000-1","8-3","2*444444","9999+9"]

In [36]: print '\n'.join(str(eval(task)) for task in lines)
999
143001625
882
9801
2
18
10001
133
12221672222221110
1000010
999
5
888888
10008

Die Aufgabenstellung habe ich nur überflogen, sieht knifflig aus.

numerix · Mittwoch 25. Februar 2009, 20:06

derdon hat geschrieben:Ich denke, name meint so etwas (natürlich nur der Ansatz):

Ach so. Auf die Idee, dass sich jemand zum Problem äußert, ohne die Aufgabenstellung gelesen zu haben, bin ich gar nicht gekommen ...

derdon hat geschrieben:Die Aufgabenstellung habe ich nur überflogen, sieht knifflig aus.

Also eigentlich nicht - wenn man die Aufgabenstellung gleich richtig liest und nicht nur überfliegt.

sma · Samstag 28. Februar 2009, 10:53

numerix hat geschrieben:
sma hat geschrieben:Habe schnell eine Lösung zusammengestümpert. War Fun. Geht garantiert besser und kürzer.
Funktioniert auf jeden Fall nicht ... :(

Was funktioniert da nicht? Mein Script läuft und liefert für die vier enthaltenen Beispiele IMHO die richtige Ausgabe. Dass ich da nicht in der ersten Zeile die Anzahl der weiteren Zeilen erwarte sei geschenkt. Mir geht es nicht darum, ob ich wohl die Zeilen richtig einlesen kann, sondern um die korrekte Darstellung der mathematischen Operationen.

Stefan

numerix · Samstag 28. Februar 2009, 11:30

sma hat geschrieben:Was funktioniert da nicht? Mein Script läuft und liefert für die vier enthaltenen Beispiele IMHO die richtige Ausgabe.

Naja, die Aufgabe lautete aber nicht, ein Programm zu schreiben, was nur die 4 Beispiele richtig verarbeitet. Von meinen oben geposteten Testcases werden mehrere nicht richtig verarbeitet. Kannst sie ja mal durchlaufen lassen. Und dann nochmal GENAU die Aufgabenstellung lesen ...

Mir ist es aber zunächst nicht anders ergangen als dir mit der Aufgabenstellung. Ich hatte einige Versionen, von denen ich jeweils der festen Überzeugung war, dass sie korrekt seien - bis ich sie eingeschickt habe und eines besseren belehrt wurde.

Wenn alle o.g. testcases korrekt laufen, dann ist die Wahrscheinlichkeit schon recht hoch, dass es auch bei SPOJ durchkommt.

sma · Samstag 28. Februar 2009, 12:24

numerix hat geschrieben:Naja, die Aufgabe lautete aber nicht, ein Programm zu schreiben, was nur die 4 Beispiele richtig verarbeitet.

Mir egal: Mehr kann ich nicht prüfen.

numerix hat geschrieben:Von meinen oben geposteten Testcases werden mehrere nicht richtig verarbeitet. Kannst sie ja mal durchlaufen lassen. Und dann nochmal GENAU die Aufgabenstellung lesen ...

Das ist mir zu viel Rätselraten. Ich denke, bei "print res" muss es "print res.ljust(l2)" heißt, denn "2*444444" passte nicht, doch ansonsten bin ich zufrieden :)

Ich glaube, die Beschreibung will, dass

Code: Alles auswählen

1000
  -1
----
 999

als

Code: Alles auswählen

1000
  -1
 ---
 999

dargestellt werden soll. Das mache ich anders. Wer will, kann's ja ändern. Der Lösungsansatz bleibt aber gleich: Statt mit Zahlen wird mit Strings gearbeitet, da es so viel einfacher ist, die Dinge auszurichten.

Stefan

numerix · Samstag 28. Februar 2009, 14:17

sma hat geschrieben:Das ist mir zu viel Rätselraten.

Ich verstehe nicht, was das mit Rätselraten zu tun hat. Auf Python Challenge trifft so eine Aussage sicher zu, aber hier muss doch nichts gerätselt werden. Die Aufgabenstellung ist eindeutig und lösbar. Dein Code löst sie halt nicht.

sma · Sonntag 1. März 2009, 11:27

numerix hat geschrieben:
sma hat geschrieben:Das ist mir zu viel Rätselraten.
Ich verstehe nicht, was das mit Rätselraten zu tun hat.

Du behauptest, es ist fehlerhaft, ohne den Beweis dafür zu erbringen. Ich will nicht raten, was du wohl meinst. Das meine ich. Es ist mir schon klar, dass ein Teil der ursprünglichen SPOJ-Aufgabe auch das Knobeln ist, ob man wohl die Aufgabenstellung richtig verstanden hat, aber ich finde es nicht hilfreich, einfach nur "falsch" zu sagen. Dann bleibt es eben falsch ;)

Stefan

hendrikS · Sonntag 1. März 2009, 11:47

@sma
Tu' s doch mal einstellen bei SPOJ. Jetzt hast Du schon Zeit reingesteckt das Programm "zusammenzustümpern" Ich hätte jetzt den Ehrgeiz die Aufgabe jetzt auch richtig zu lösen.