Kurzer Prozess: Size Contest bei SPOJ

[BlackVivi]

Weit ham wirs gebracht, Code Golfing im Python Forum...

Für zwischendurch ist das doch mal eine nette Abwechslung. Andere lösen Kreuzworträtsel. Oder Sudokus ...

Da missbrauchen sie aber nicht eine Programmiersprache

Man programmiert ja auch keine Applikation für den ernsten Einsatz. Man löst mit einer Programmiersprache ein Problem. Das Problem ist diesmal nicht der Algorithmus selbst, sondern die Größe des Algorithmus Und alles was unter dem Perfektionismus liegt, ist'n Flaschenhals ;P

[name]

Man löst mit einer Programmiersprache ein Problem. Das Problem ist diesmal nicht der Algorithmus selbst, sondern die Größe des Algorithmus

Man loest ein nicht-existentes Problem, aber gut, wenns Spass macht

Und alles was unter dem Perfektionismus liegt, ist'n Flaschenhals ;P

Hae? Nix verstehen...

[BlackVivi]

Man löst mit einer Programmiersprache ein Problem. Das Problem ist diesmal nicht der Algorithmus selbst, sondern die Größe des Algorithmus

Man loest ein nicht-existentes Problem, aber gut, wenns Spass macht

Und alles was unter dem Perfektionismus liegt, ist'n Flaschenhals ;P

Hae? Nix verstehen...

Das 2te beantwortet das erste. Stell dir vor - das Problem heißt: "Mach den Code so kurz wie möglich. Alles was länger ist als 0 Zeichen ist zu lang. Dann versucht man das Problem zu lösen Und zwar immer besser...

[numerix]

Da missbrauchen sie aber nicht eine Programmiersprache

Ich sehe das eher als eine von vielen Möglichkeiten, die Leistungsfähigkeit einer Sprache zum Ausdruck zu bringen.

Das finde ich aber ueberhaupt nicht. Das wuerde ja heissen das Perl leistungsfaehiger als Python ist, weil mit Perl laesst sich normalerweise besser golfen....

Leistungsfähigkeit hat ja unterschiedliche Facetten. C als leistungsfähiger einzustufen als Python ist als allgemeine Aussage auch falsch, nur weil C Programme bei vergleichbaren Algorithmen schneller sind als Python-Programme.

Auch die Lesbarkeit eines Codes oder die Entwicklungsgeschwindigkeit sind Leistungsmerkmale und da spielt Python ja nachweislich auf den vorderen Plätzen mit.

Was die Kürze des Codes angeht, so ist Perl Python nun mal überlegen.

[name]

Was die Kürze des Codes angeht, so ist Perl Python nun mal überlegen.

Seh ich zwar nicht so als Leistungsmerkmal, solang ich keine Romane schreiben muss

[numerix]

Man loest ein nicht-existentes Problem

Naja, das geht jetzt ins Philosophische über: Ab wann gilt ein Problem als "existent"? Wenn es ein Kunden-Projekt ist, das Geld einbringt?

Man denke nur mal an die zahlreichen Programmieraufgaben, die man zu lösen hat oder lösen will oder was auch immer, um eine Programmiersprache zu lernen. Da werden zuerst künstlich Probleme geschaffen, nur um sehen, ob man sie lösen kann. Sind die "nicht-existent"?

Und dieser Size-Contest ist zumindest so, dass man sich zunächst mit einem Problem auseinandersetzen muss (auch wenn es sehr überschaubar ist), dann einen Algorithmus entwickeln muss und dann überlegen kann, wie man den möglichst kurz bekommt.

Auch für Programmieranfänger ist diese konkrete Problemstellung nicht ungeeignet, weil man - zumindest, wenn die Lösungen dann offengelegt werden, was bei SPOJ an sich nicht so ist, aber hier im Forum ja anders gehandhabt werden kann - an einem solch kleinen Beispiel sehen kann, auf welche unterschiedlichen Weisen sich ein Problem lösen lässt.

Die Auseinandersetzung mit den verschiedenen Lösungen bringt in aller Regel auch einen Erkenntnisgewinn.

Wenn ich mal die beiden bisher geposteten funktionsfähigen Lösungen und meine eigene (noch nicht gepostete) Lösung nehme, dann ist jede in ihrem Ansatz völlig unterschiedlich. Und das finde ich spannend.

[name]

Und dieser Size-Contest ist zumindest so, dass man sich zunächst mit einem Problem auseinandersetzen muss (auch wenn es sehr überschaubar ist), dann einen Algorithmus entwickeln muss und dann überlegen kann, wie man den möglichst kurz bekommt.

Hmm, entwickelt man da wirklich einen Algorithmus oder nimmt man nicht eher den der die Sprache anbietet der am wenigsten Zeichen braucht?

Auch für Programmieranfänger ist diese konkrete Problemstellung nicht ungeeignet, weil man - zumindest, wenn die Lösungen dann offengelegt werden, was bei SPOJ an sich nicht so ist, aber hier im Forum ja anders gehandhabt werden kann - an einem solch kleinen Beispiel sehen kann, auf welche unterschiedlichen Weisen sich ein Problem lösen lässt.

Man kriegt dadurch leider sehr viele suboptimale Loesungen praesentiert, wo man als Anfaenger wieder nicht weiss dass und warum sie das sind.

[kbr]

Dein Algorithmus ist fehlerhaft. Ergebnis für obige testcases:
3
8
15
7

Natürlich habe ich die Testcases vor dem posten auf das Script losgelassen und bei mir kommt

2
5
12
6

heraus.

[snafu]

Hier mein Ansatz (84 Zeichen):

Code: Alles auswählen

import sys
N=p=0
for c in sys.argv[1]:
	if c<'a' and p:N+=4-p;p=0
	p=(p+1)%4
print N

Da habe ich aber was anderes raus:

Code: Alles auswählen

>>> len("""import sys
... N=p=0
... for c in sys.argv[1]:
...     if c<'a' and p:N+=4-p;p=0
...     p=(p+1)%4
... print N""")
90

[b.esser-wisser]

Code: Alles auswählen

n=p=0
for c in raw_input()[1:]:
    if c.islower():
        p+=1
    else:
        n+=3-p%4
        p=0
print n

... meine kürzeste "konventionelle" Version.
Und ich stimme denen zu, die keinen Sinn darin sehen, das kürzest-mögliche Programm zu schreiben. Pythonprogramme erreichen doch meistens automatisch ein Längen/Lesbarkeits-Optimum

gruß Jörg
ps.: Zählen Leerzeichen/Tab's eigentlich mit?
falls ja:

Code: Alles auswählen

n=p=0
for c in raw_input()[1:]:
 if c.islower():p+=1
 else:n+=3-p%4;p=0
print n

-> 79

[name]

Und ich stimme denen zu, die keinen Sinn darin sehen, das kürzest-mögliche Programm zu schreiben. Pythonprogramme erreichen doch meistens automatisch ein Längen/Lesbarkeits-Optimum

Juhu, Verstaerkung!

[numerix]

ps.: Zählen Leerzeichen/Tab's eigentlich mit?

Bei diesem size-contest: ja.
Es wird einfach die Gesamtzahl an Bytes gezählt, also das, was man als Dateigröße erhält, wenn man das Skript in eine Datei schreibt.

@kbr: Dein Programm berücksichtigt nicht die speziellen Zeilenenden (siehe das erste Posting im Thread).

Man kriegt dadurch leider sehr viele suboptimale Loesungen praesentiert, wo man als Anfaenger wieder nicht weiss dass und warum sie das sind.

Mag sein. Aber dafür gibt es dann ja die Könner hier im Forum, die einen darauf hinweisen.

[wuf]

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

[name]

Dann ja die Könner hier im Forum, die einen darauf hinweisen.

Naja, das ist ja nicht wirklich Sinn der Sache. Ich finde Code-Golfing fuer Anfaenger einfach total ungeeignet. Falsche Loesungen lernen und dann von andren drauf hingewiesen werden is glaub ich keine paedagogisch hochwertige Lernmethode.

[numerix]

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

Es sind 73 Bytes und mit der SPOJ-Original-Eingabe läuft es immer noch nicht ..

[kbr]

@kbr: Dein Programm berücksichtigt nicht die speziellen Zeilenenden (siehe das erste Posting im Thread).

Hallo numerix,

ich sehe keine speziellen Zeilenenden, weder in der Beschreibung bei SPOJ bezüglich des Inputs noch in den Daten die raw_input() selber liefert. Bei

Code: Alles auswählen

n = raw_input()
print len(n), n
print n[:-1]

kommt ganz unspektakulär

Code: Alles auswählen

MacPro:~ klaus$ python nop2.py
abcde
5 abcde
abcd

heraus. Also nichts, was am Ende irgendwo stört.

@wuf: das ist exakt meine raw_input() Variante (bei mir mit Tabulatoren ).

Klaus

[numerix]

ich sehe keine speziellen Zeilenenden, weder in der Beschreibung bei SPOJ bezüglich des Inputs noch in den Daten die raw_input() selber liefert.

Dann sende es doch bei SPOJ mal ein ...

[snafu]

Für Python könnte ich mir höchstens Wettbewerbe vorstellen, wo man möglichst wenig Zeilen benutzen soll. Ich glaube, da kann die Sprache eher ihre Stärken ausspielen.

(Ich bitte, von möglichen Semikolon-Witzen abzusehen...)

[kbr]

ich sehe keine speziellen Zeilenenden, weder in der Beschreibung bei SPOJ bezüglich des Inputs noch in den Daten die raw_input() selber liefert.

Dann sende es doch bei SPOJ mal ein ...

Eigentlich ist es mir auch egal. Von mir aus dann eben

Code: Alles auswählen

n = raw_input()[:-1]

oder irgendsowas.

Interessanter finde ich zu sehen, welche Lösungsvorschläge andere posten.

[numerix]

Eigentlich ist es mir auch egal. Von mir aus dann eben

Code: Alles auswählen

n = raw_input()[:-1]

oder irgendsowas.

Als finaler Code ergäbe sich dann, wenn man noch das Leerzeichen hinter "a" entfernt:

Code: Alles auswählen

n=p=0
for c in raw_input()[:-1]:
 if c<'a'and p:n+=4-p;p=0
 p=(p+1)%4
print n

Das läuft jetzt korrekt mit 77 Bytes.

Interessanter finde ich zu sehen, welche Lösungsvorschläge andere posten.

Ich warte mal noch ein wenig ab und dann stelle ich alle funktionsfähigen geposteten Lösungen nochmal zusammen.