Kurzer Prozess: Size Contest bei SPOJ

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

snafu hat geschrieben:
numerix hat geschrieben:@snafu: So lange ich mit meinem Code in der SPOJ-Rangliste für Python auf Platz 1 stehe, werde ich ihn noch nicht rausrücken ... :)
Tust du's jetzt? :)
Nein, stattdessen habe ich mir Platz 1 zurück erorbert: 63 Bytes ... :wink:

@bords0: Deinen Trick verstehe ich nicht ...

Nachtrag: Auffällig ist, dass vor ein paar Minuten eine weitere Python Lösung mit 74 Bytes aus "Germany" bei SPOJ aufgetaucht ist - das entspricht genau der Länge des kürzesten bisher hier (und zwar von mir) geposteten Codes. Kann natürlich Zufall sein ...
BlackJack

So, nun habe ich auch eine 65er Lösung. :-)
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

numerix hat geschrieben:Nachtrag: Auffällig ist, dass vor ein paar Minuten eine weitere Python Lösung mit 74 Bytes aus "Germany" bei SPOJ aufgetaucht ist - das entspricht genau der Länge des kürzesten bisher hier (und zwar von mir) geposteten Codes. Kann natürlich Zufall sein ...
Dann oute ich mich mal. Dachte das wäre kein Problem, wenn ich einfach mal den Code ausprobiere ;) Ich wollte sichergehn, dass wenn ich den Code schon als Ausgangsbasis benutze, er auch wirklich funktioniert. Leider fällt mir zu dem Code keine Verbesserung mehr ein und meine anderen Ansätze sind noch länger.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Nocta hat geschrieben:
numerix hat geschrieben:Nachtrag: Auffällig ist, dass vor ein paar Minuten eine weitere Python Lösung mit 74 Bytes aus "Germany" bei SPOJ aufgetaucht ist - das entspricht genau der Länge des kürzesten bisher hier (und zwar von mir) geposteten Codes. Kann natürlich Zufall sein ...
Dann oute ich mich mal.
Das ist anständig. :D
Nocta hat geschrieben:Ich wollte sicher gehn, dass wenn ich den Code schon als Ausgangsbasis benutze, er auch wirklich funktioniert.
Davon konnte man eigentlich ausgehen.
Wenn man sich die Aufgabenstellung ansieht, dann gibt es eigentlich nur eine Handvoll Fälle, die man gesondert prüfen muss und die habe ich mit den Werten eines von SPOJ als korrekt angesehenen Skripts verglichen.
BlackJack hat geschrieben:So, nun habe ich auch eine 65er Lösung.
Damit haben wir jetzt schon die ein oder andere Perl-Lösung auf die Plätze verwiesen ... :D

Ärgerlich finde ich, dass - jedenfalls bei meiner 63er Lösung - immer noch einige Bytes für das vermurkste Zeilenende draufgehen. Die würde ich gerne noch einsparen, sehe aber noch nicht wie. Davon abgesehen sehe ich für meine Lösung keine Möglichkeit mehr zur weiteren Verkürzung. Schade, dass man "raw_input()" nicht ersetzen kann (oder kann man? Ich meine natürlich durch eine kürzere Variante.)
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

Machst du wahrscheinlich schon, aber raw_input().strip() entfernt dieses doofe Zeilenende. Oder du iterierst halt nur bis [-1] was wohl kürzer ist =/ raw_input()[:-1] ... das sind 5 Zeichen mehr, hm...

Geht wohl nich anders. Dein Konzept lässt es nicht zu, dass es übersehen wird. Meins wohl schon, auch wenn mein Konzept wohl doof ist =(
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

BlackVivi hat geschrieben:Machst du wahrscheinlich schon, aber raw_input().strip() entfernt dieses doofe Zeilenende. Oder du iterierst halt nur bis [-1] was wohl kürzer ist =/ raw_input()[:-1] ... das sind 5 Zeichen mehr, hm...
Ja, natürlich werde ich das Zeichen los, aber 5 Bytes (ich schaffe es mit 4, aber trotzdem tut es weh), das sind bei diesen Größenordnungen 8% des Gesamtcodes ... :)
BlackJack

@numerix: Hab' Dich eingeholt. :-)
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

BlackJack hat geschrieben:@numerix: Hab' Dich eingeholt. :-)
Prima! Vielleicht könnten wir unsere Codes mal bei Gelegenheit austauschen. Nach den Erfahrungen hier würde ich PM vorschlagen, sonst tauchen in Kürze haufenweise 63er Lösungen bei SPOJ auf ...

Allerdings schätze ich, dass das nicht das Ende der Fahnenstange sein wird. Was mich betrifft zwar schon (sofern mir nicht doch noch eine Idee kommt, wie ich auf die zusätzlichen Bytes verzichten kann, die mir das Extra-Zeilenende beschert), aber verglichen mit den Typen, die bei SPOJ an den Start gehen, bin ich auch nur ein kleines Licht. Da kommt bestimmt noch einiges nach ... :?
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

bords0 hat geschrieben:
numerix hat geschrieben:Seit eben gibt es bei SPOJ eine 66 Bytes Python Lösung ... :(

Edit: Ich vermute es war jemand hier aus dem Forum. Wäre nett, wenn er seine Lösung zur gegebenen Zeit mal zeigen würde ...
Ein nicht ganz offensichtlicher Trick ist vielleicht:
Ersetze p=0, p+=1 und (4-p)%4 durch p=8, p-=1 und p%4
Ich habe aufgrund dieser Tipps eine 65er-Lösung. Zählt das auch oder ist das Schummeln?
BlackJack

IMHO ist das sowieso ein bisschen geschummelt weil es anscheinend mehr Wissen über die Eingabe voraussetzt, als in der Aufgabe steht. Das eine Instruktion nicht mehr als 7 Argumente hat, steht da AFAIK nämlich nirgends.

Wenn man also schon solches "Indiderwissen" verwendet, kann man auch gleich das Ergebnis heraus finden und mit einem ``print xxx`` eine 9-Byte-Lösung präsentieren.
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

BlackJack hat geschrieben:Wenn man also schon solches "Indiderwissen" verwendet, kann man auch gleich das Ergebnis heraus finden und mit einem ``print xxx`` eine 9-Byte-Lösung präsentieren.
Wait, mir kommt eine Idee òo Man könnte doch theoreitsch die Lösung via Email oder so an sich schicken óo Die Lösung an sich wird zwar dann nich akzeptiert, aber danach schreibt man die print xxx Lösung :)
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Bezieht sich das "print xxx" auf die Lösung, die man hier ins Forum schreiben würde oder wie ist das gemeint? Der Beweis, dass man's richtig hat, zeigt sich doch in der Bestenliste durch den eigenen Namen. Also wird man ja dann schon den richtigen Code gespeichert haben.

Außerdem habe ich Zeichen statt Bytes gezählt. :oops: So komme ich dann doch nur auf 70 Bytes. :(
BlackJack

@BlackVivi: Ganz so einfach ist es nicht, weil Du in diesem Fall pro Einsendung nur 1.5 Bit Information zurück bekommen kannst. *Ganz* so einfach macht SPOJ das schummeln dann doch nicht.

Bei diesem Fall sollte man die Lösung aber in maximal 10 Versuchen erraten können.

Aber wie gesagt ist das IMHO schummeln und zumindest mir wär's peinlich mit so einer "Lösung" sichtbar auf vorderen Plätzen zu stehen.

@snafu: Man kann mit ``print xxx`` wobei `xxx` für die richtige Zahl als literaler Wert steht in die Bestenliste kommen. Aber ob man das will…
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Ja, grundsätzlich lässt sich das System natürlich austricksten, da hier wohl mit einer immer gleichen Eingabe gearbeitet wird und somit das Ergebnis auch immer das gleiche ist. Hat man das irgendwie ausgetüftelt - und das sollte möglich sein -, dann lassen sich natürlich ganz kurze Lösungen finden.

Bei einem anderen, schon lange laufenden size contest bei SPOJ ist das auch genauso passiert: https://www.spoj.pl/ranks/SIZECON/

Im SPOJ-Forum kann man mehr dazu lesen, falls es einen interessiert.

Aber, mal ehrlich: Wenn da irgendwann eine 10 Bytes Python Lösung für das NOP-Problem auftaucht, ist klar, dass hier geschummelt wurde. Muss jeder selber wissen.

Was die 65-Bytes Lösung von Snafu/bords0 angeht, würde ich mich BlackJack anschließen: Sauberer ist es IMHO, wenn die Lösung für alle Fälle funktioniert, die gemäß Aufgabenstellung möglich sind (was für BlackJacks und meine Lösung gleichermaßen gilt, die sich im übrigen kaum von einander unterscheiden) und nicht bestimmte, herausgetüftelte Eigenarten der tatsächlichen Eingabewerte verwendet. Das interessiert SPOJ natürlich nicht und so richtig geschummelt ist es ja auch nicht.
snafu hat geschrieben:Ich habe aufgrund dieser Tipps eine 65er-Lösung. Zählt das auch oder ist das Schummeln?
Als Schummeln würde ich es nicht ansehen. Wenn ich an deiner Stelle wäre, würde ich mir wahrscheinlich überlegen, wie hoch mein Eigenanteil an der endgültigen Lösung ist und wie hoch der Anteil desjenigen ist, der die Vorlage oder Idee dazu geliefert hat. Davon würde ich dann abhängig machen, ob ich so etwas bei SPOJ einschicke oder nicht.
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Ich wusste nicht, dass es so schlimm ist, wenn man bei dem Teil irgendwelche Lösungen einsendet, die einem nicht gehören. Ich kannte die Seite vorher nicht und hab auch nicht gedacht, dass ich mit meiner Lösung dann unter irgendeiner Top 10 stehe und die Statistik total verfälsche. Also sorry nochmal für das Klauen der Lösung hier im Board (weil ja jetzt immer so Anspielungen darauf fallen). Ist ja nicht so, dass ich geil darauf bin, Lösungen zu klauen und dann so zu tun als ob ich der King wär, nur weil ich dadurch irgendwo oben stehe. Beim nächsten Mal weiß ich's besser ;)
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

numerix hat geschrieben:@bords0: Deinen Trick verstehe ich nicht ...
Inzwischen habe ich festgestellt, dass Python ja auch negative Zahlen mit %4 in den Bereich von 0-3 abbildet - prima, dann ist es schnuppe, wie viele Operanden es gibt, und man kann bei 0 anfangen.

Der "Trick" war ja nur, N+=(4-p)%4 durch N+=p%4 zu ersetzen, indem man p runterzählt statt hoch.
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

BlackJack hat geschrieben:@numerix: Hab' Dich eingeholt. :-)
Eine kleine Frage: iterierst du über die Zeichen von raw_input(), oder machst du es anders? (Meine Experimente mit re.split waren entmutigend...)
BlackJack

Ein ganz banales ``for c in raw_input():``.
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Mal Offtopic:
https://www.spoj.pl/problems/KAMIL/
Da gibt's Pythonlösungen mit der Länge 53, ich hab aber keine Ahnung, wie man das schaffen könnte.
Meine 75 lange Version:

Code: Alles auswählen

for i in range(10):
  print 2**sum([1 for x in raw_input() if x in 'TDLF'])
Wo könnte man hier noch Zeichen einsparen? Irgendeinen Trick muss es ja geben :) Oder muss man die Sache ganz anders angehn? Regex wäre zB kürzer aber das `import re` ist dann auch wieder 9 Zeichen lang.
Wenn mir jetzt jemand eine Lösung präsentiert oder mir einen entscheidenden Tipp gibt, werd ich das auch nicht als meine eigene Lösung dort absenden, mich interessiert's nach einer halben Stunde ausprobieren alternativer Lösungen einfach mal. Naja bzw. wie Numerix schon sagte, kann man ja abwägen wie hoch der Anteil desjenigen ist, der die Vorlage/Idee geliefert hat und wie hoch der Eigenanteil ist ;)
BlackJack

Also die ganz offensichtlichen überflüssigen Zeichen wären erst einmal ein Leerzeichen am Anfang von Zeile 2 und die eckigen Klammern in der Summe. In Python 2.5 gibt's schon Generator-Ausdrücke.

Das nächste Einsparungspotential ist die literale 1 und das ``if``. Man kann nämlich mit Wahrheitswerten rechnen. Die erben von `int` und `True` hat den Wert 1 und `False` den Wert 0.

Damit wären wir bei:

Code: Alles auswählen

for i in range(10):
 print 2**sum(x in 'TDLF' for x in raw_input())
Antworten