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
name
User
Beiträge: 254
Registriert: Dienstag 5. September 2006, 16:35
Wohnort: Wien
Kontaktdaten:

numerix hat geschrieben:
name hat geschrieben:Weil es keine { und } hat sind so wenig Zeilen wie moeglich noch bloedsinniger...
Das verstehe ich nicht.

Code: Alles auswählen

if [foo]:
    do something
    do something else
geht schwer mit einer zeile.
Ohloh | Mein Blog | Jabber: segfaulthunter@swissjabber.eu | asynchia – asynchrone Netzwerkbibliothek

In the beginning the Universe was created. This has made a lot of people very angry and has been widely regarded as a bad move.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Dann löst man das Problem eben anders. :roll:
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

Faszinierend auch, meine echte Einzeiler Lösung ist auch die langsamste auf der ersten Seite =D

Sind diese ganzen funktionalen Sachen so langsam? ._. Ich find die total toll.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

name hat geschrieben:

Code: Alles auswählen

if [foo]:
    do something
    do something else
geht schwer mit einer zeile.

Code: Alles auswählen

if foo: do_something()
:)

Mal im Ernst: Worauf willst du mit solchen Argumenten hinaus? Es bestreitet niemand, dass gewisse Konstrukte sich auch bei Python über mehrere Zeilen erstrecken, trotzdem kann man IMHO zurecht behaupten, dass in sehr vielen Fällen weniger Zeilen in Python nötig sind als in anderen Sprachen, um bestimmte Probleme zu lösen.
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

BlackVivi hat geschrieben:Sind diese ganzen funktionalen Sachen so langsam? ._. Ich find die total toll.
In Python schon. Du könntest ja Haskell nehmen ;)
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

b.esser-wisser hat geschrieben:
Die berücksichtigt noch nicht die garstigen Zeilenenden, die weg müssen.
Wo wird sowas bei der Aufgabenstellung erwähnt?
(Und welchen Einfluß hat es überhaupt?
Es wird nicht erwähnt - das ist ja das Problem. Deshalb habe ich in meinem eröffnenden Posting extra darauf hingewiesen.
Es hat mich bei meinen ersten Versuchen bei SPOJ fast an den Rand der Verzweiflung gebracht, weil alle mir vorstellbaren testcases bei mir einwandfrei gelaufen sind, aber mir SPOJ jedesmal eine "wrong answer" lieferte. Dann habe ich aus schierer Verzweiflung die Eingabe mal mit einem strip() behandelt - und siehe da, jetzt lief es ...

Mittlerweile gibt es auch andere, die es gemerkt haben, es gibt z.B. inzwischen einen entsprechenden Kommentar unter der Aufgabenstellung.

Der Einfluss ist, dass die Ergebnisse dann falsch sind ...
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

DasIch hat geschrieben:
BlackVivi hat geschrieben:Sind diese ganzen funktionalen Sachen so langsam? ._. Ich find die total toll.
In Python schon. Du könntest ja Haskell nehmen ;)
Für Haskell bin ich ja sogar für'ne Ausgabe zu plöd, also... >_<
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

BlackVivi hat geschrieben:Sind diese ganzen funktionalen Sachen so langsam? ._. Ich find die total toll.
Generell nein, in Python sind aber Funktionsaufrufe recht teuer und Endrekursion wird nicht optimiert, daher sind funktionale Lösungen oft nicht die schnellsten. Ich nutze sie aber trotzdem gerne wo man die Laufzeit verkraften kann.

Ansonsten kannst du dir ja auch funktionale Sprachen ansehen (wie Scheme oder OCaml). Die haben dann entsprechende Optimierungen (und echte lambdas!).
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

BlackVivi hat geschrieben:Faszinierend auch, meine echte Einzeiler Lösung ist auch die langsamste auf der ersten Seite =D
Mich begeistert ja immernoch die 356 Bytes Lösung, die ungefähr 5x so langsam ist wie die anderen und auch noch mehr Speicher braucht (weil irgendwelche Module eingebunden wurden). :D
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

numerix hat geschrieben:
BlackVivi hat geschrieben:Faszinierend auch, meine echte Einzeiler Lösung ist auch die langsamste auf der ersten Seite =D
Mich begeistert ja immernoch die 356 Bytes Lösung, die ungefähr 5x so langsam ist wie die anderen und auch noch mehr Speicher braucht (weil irgendwelche Module eingebunden wurden). :D

Code: Alles auswählen

class Function(object):
    def __init__(self, function, *args):
        self.function = function
        self.args = list(args)
        
    def get_number_of_args(self):
        return len(self.args)
        
    def add_arg(self, arg):
        self.args.append(arg)
        
class Argument(object):
    def __init__(self, arg):
        self.arg = arg
        
class Parser(object):
    def __init__(self, src):
        t = Tokenizer(src)
        self.lister = t.yield_token()
        
    def get_next_function(self):
        func = Function(self.lister.next())
        
        
class Tokenizer(object):
    def __init__(self, text):
        self.text = text
        
    def yield_token(self):
        for i in text:
            yield i
    
Ungefähr so, vielleicht :P Das macht ja noch nichmal, was's soll ._.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

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 ...
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

numerix hat geschrieben:
wuf hat geschrieben:Hallo kbr

Da wir PEP-8 vernachlässigen könnten wir doch auch noch beim einrücken einige Zeichen einsparen:

Code: Alles auswählen

N=p=0
for c in raw_input():
 if c<'a' and p:N+=4-p;p=0
 p=(p+1)%4
print N
Sind total 69 Zeichen

Gruss wuf :wink:
Es sind 73 Bytes und mit der SPOJ-Original-Eingabe läuft es immer noch nicht ..
Ja. Aber man kann was draus machen (Score 66 bei SPOJ). :D
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

bords0 hat geschrieben:
numerix hat geschrieben:
wuf hat geschrieben:Hallo kbr

Da wir PEP-8 vernachlässigen könnten wir doch auch noch beim einrücken einige Zeichen einsparen:

Code: Alles auswählen

N=p=0
for c in raw_input():
 if c<'a' and p:N+=4-p;p=0
 p=(p+1)%4
print N
Sind total 69 Zeichen

Gruss wuf :wink:
Es sind 73 Bytes und mit der SPOJ-Original-Eingabe läuft es immer noch nicht ..
Ja. Aber man kann was draus machen (Score 66 bei SPOJ). :D
Gratuliere!
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

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 (zum Glück haben die keinen Opcode mit mehr als 7 Operanden, sonst müsste man p=96 oder gar p=200 nehmen).
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

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? :)
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 =(
Antworten