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

Freitag 20. Februar 2009, 13:26

Seit ein paar Tagen gibt es einen neuen Size Contest bei SPOJ: https://www.spoj.pl/problems/NOP/

Grundidee dabei: Ein bestimmtes Problem ist zu lösen und der dafür benötigte Code (Quelltext) soll so kurz wie möglich sein. In diesem Fall sind maximal 360 Bytes erlaubt, aber das in Python keine wirkliche Einschränkung bei dieser Aufgabenstellung (allerdings gibt es z.Zt. immerhin eine Lösung mit 356 Bytes - würde ich gerne mal sehen ... :) )

Da das zu lösenden Problem hier sehr überschaubar ist (und weit weniger anspruchsvoll als ein Großteil der SPOJ-Aufgaben), hat der ein oder andere ja vielleicht Lust, beim Wettrennen um den kürzesten Python-Code sein Glück zu versuchen.

Zwar werden wir mit Python gegen Perl (zumindest was die Kürze des Codes angeht) nicht ankommen und anscheinend lässt sich das gestellte Problem auch in Ruby äußerst kompakt umsetzen, aber vielleicht können wir Python ja auf Platz 3 der Rangliste halten - das ist jedenfalls der aktuelle Stand: https://www.spoj.pl/ranks/NOP/.

Falls jemand gerne mitmachen will, aber mit der Aufgabenstellung wg. des Englischen (oder aus anderen Gründen) nicht klarkommt, wird er sicher hier auch Hilfe finden können.

Konkret zur Aufgabenstellung: Der übergebene String wird über stdin aufgenommen und über stdout zurückgeliefert, d.h. - wenn ich nichts übersehe - ein raw_input() und ein print sind auf jeden Fall fällig (zumindest kenne ich bis jetzt keine kürzeren Möglichkeiten für die Ein-/Ausgabe bei SPOJ).
Und: Der Eingabestring scheint in diesem Fall ein Zeilenende-Zeichen zu haben, das von raw_input() nicht automatisch entfernt wird. Muss man sich also selbst drum kümmern.
Benutzeravatar
b.esser-wisser
User
Beiträge: 272
Registriert: Freitag 20. Februar 2009, 14:21
Wohnort: Bundeshauptstadt B.

Freitag 20. Februar 2009, 14:39

Hab keine Lust mich bei SPOJ zu registrieren, aber ich mich mich mal daran versucht:
(74 Zeichen, aber nur mit den drei SPOJ-Beispielen getestet :roll: )

Code: Alles auswählen

import re
print sum(3-len(p)for p in re.split("[A-Z]",raw_input())[1:-1])
Mit python2.5 und RegEx krieg' ich's nicht kleiner, da muss wohl 'ne andere Lösung her.

gruß Jörg
Wir haben schon 10% vom 21. Jahrhundert hinter uns!
Benutzeravatar
snafu
User
Beiträge: 5536
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Freitag 20. Februar 2009, 14:40

Kannst du vielleicht mal deine derzeitige Version posten, damit man einen Anhaltspunkt hat? Ich blicke bei dem Problem ehrlich gesagt nicht durch, aber ich bin sowieso nicht gut in solchen Dingen.
shcol (Repo | Doc | PyPi)
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Freitag 20. Februar 2009, 15:01

b.esser-wisser hat geschrieben:Hab keine Lust mich bei SPOJ zu registrieren, aber ich mich mich mal daran versucht:
(74 Zeichen, aber nur mit den drei SPOJ-Beispielen getestet :roll: )

Code: Alles auswählen

import re
print sum(3-len(p)for p in re.split("[A-Z]",raw_input())[1:-1])
Mit python2.5 und RegEx krieg' ich's nicht kleiner, da muss wohl 'ne andere Lösung her.
Funktioniert nicht für alle Fälle korrekt. Ein paar Beispiele mit der richtigen Lösung:

Code: Alles auswählen

AdacBdadDasdEfaFweGsd
2
EaEbFabG
5
AbcdefttgBCDE
12
ABDdasdfasdfsdfas
6
Dein Code liefert:

Code: Alles auswählen

AdacBdadDasdEfaFweGsd
2
EaEbFabG
5
AbcdefttgBCDE
4
ABDdasdfasdfsdfas
6
@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 ... :)
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

Freitag 20. Februar 2009, 15:07

Code: Alles auswählen

print reduce(lambda x,y:x+(-(x+y)%4),[x for x,y in enumerate(raw_input()) if y.isupper()])
Ich denke meine Version ist schon relativ kurz :)

85 Zeichen...

Ich überleg die ganze Zeit, was ich noch kürzer kriegen könnte òo

Edit: 84 Zeichen, nach dem ich das eine Leerzeichen noch entfernt habe Oo

Mhm, hab noch das print vergessen... Ich depp. 90 Zeichen.
Zuletzt geändert von BlackVivi am Freitag 20. Februar 2009, 15:15, insgesamt 2-mal geändert.
Benutzeravatar
kbr
User
Beiträge: 931
Registriert: Mittwoch 15. Oktober 2008, 09:27

Freitag 20. Februar 2009, 15:10

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
Und bitte nicht auf PEP 8 hinweisen ... :)

Klaus
Benutzeravatar
b.esser-wisser
User
Beiträge: 272
Registriert: Freitag 20. Februar 2009, 14:21
Wohnort: Bundeshauptstadt B.

Freitag 20. Februar 2009, 15:22

Stimmt, mein Code funktionierte nicht , sobald mehr als 3 Kleinbuchstaben hintereinander vorkommen :(
Korrektur:

Code: Alles auswählen

import re;print sum(3-len(p)&3for p in re.split("[A-Z]",raw_input())[1:-1])
("%4" wäre ja langweilig :twisted: )

Sehe ich das richtig, dass der letzte "Befehl" nicht aufgefüllt werden muss?
Wir haben schon 10% vom 21. Jahrhundert hinter uns!
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

Freitag 20. Februar 2009, 15:29

kbr hat geschrieben: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
Und bitte nicht auf PEP 8 hinweisen ... :)

Klaus
Den Algo selbst habe ich nicht gecheckt, aber der input soll ueber stdin kommen und nicht ueber einen Programmparameter. Also nimmst Du einfach raw_input und sparst Dir den import.
Benutzeravatar
kbr
User
Beiträge: 931
Registriert: Mittwoch 15. Oktober 2008, 09:27

Freitag 20. Februar 2009, 15:41

hendrikS hat geschrieben:der input soll ueber stdin kommen und nicht ueber einen Programmparameter. Also nimmst Du einfach raw_input und sparst Dir den import.
Hast Recht. Das spart dann noch mal 11 Zeichen (=73).

Klaus
Benutzeravatar
name
User
Beiträge: 254
Registriert: Dienstag 5. September 2006, 16:35
Wohnort: Wien
Kontaktdaten:

Freitag 20. Februar 2009, 15:42

Weit ham wirs gebracht, Code Golfing im Python Forum...
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.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Freitag 20. Februar 2009, 15:42

b.esser-wisser hat geschrieben:Stimmt, mein Code funktionierte nicht , sobald mehr als 3 Kleinbuchstaben hintereinander vorkommen :(
Korrektur:

Code: Alles auswählen

import re;print sum(3-len(p)&3for p in re.split("[A-Z]",raw_input())[1:-1])
("%4" wäre ja langweilig :twisted: )

Sehe ich das richtig, dass der letzte "Befehl" nicht aufgefüllt werden muss?
Ja, so ist es. Da dann nur noch "Parameter" folgen, ist da nichts mehr aufzufüllen.

Dein Code scheint jetzt richtig zu funktionieren, jedenfalls für die geposteten "testcases"; nach meiner Zählung 76 Bytes.
Edit: Sorry, 75 Bytes.

@kbr: Eingabe erfolgt über raw_input() nicht als Parameter. Und: Dein Algorithmus ist fehlerhaft. Ergebnis für obige testcases:
3
8
15
7
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Freitag 20. Februar 2009, 15:46

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

Freitag 20. Februar 2009, 15:48

numerix hat geschrieben:
name hat geschrieben: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 ;-)
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.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Freitag 20. Februar 2009, 15:52

name hat geschrieben: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. Und ich finde bei < 100 Bytes darf PEP 8 ausnahmsweise auch mal außen vor bleiben ... :wink:
Benutzeravatar
name
User
Beiträge: 254
Registriert: Dienstag 5. September 2006, 16:35
Wohnort: Wien
Kontaktdaten:

Freitag 20. Februar 2009, 15:53

numerix hat geschrieben:
name hat geschrieben: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....
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.
Antworten