Programmieraufgabe von Knuth: Woerter mit den gleichen 4 Buchstaben in der Mitte

[eggy]

Du sortierst damit im ersten Feld (die Zeile hat eh nur ein Feld) vom 2. bis zum 4. Buchstaben (1-based).

mit sort bin ich noch nie gut zurechtgekommen ... coreutils mal wieder

total offtopic:
ich hab grad noch was interessantes gefunden: "info tsort", der Teil zum Background ... frag mich, ob man damit nicht auch noch was cooles anstellen könnt

[eggy]

@tobo:
man soll halt nicht mitten in der nacht rumcoden
mir war der Fehler mit dem letzten Durchlauf schon klar, und dann meinte mein umnachtetes Gehirn "spielt keine Rolle, ob die 77 Treffer oder die anderen 77 Treffer ausgegeben werden" ... dass es zuletzt auch einmal 78 sein könnten, hab ich komplett nicht auf dem Schirm gehabt

[Meillo]

Meine erste Lösung ist recht awk-lastig:

Code: Alles auswählen

$ cat max_word_set_same_inner_chars_awk
#!/bin/sh

words=$(awk "length==$1" "$4" | sort -k"1.$2,1.$3")
N=$(($3-$2+1))
echo "$words" | awk "S==substr(\$0, $2, $N)" S="$(echo "$words" | awk '
	{
		s = substr($0, I, N);
		if (s != S) {
			if (L > mL) {
				mL = L;
				mS = S;
			}
			L = 0;
			S = s;
		}
		++L;
	}
	END { print(mS) }' I="$2" N=$N)"

Also mir dreht sich schon alles, wenn ich diesen Code lese, und dabei bin ich in awk eigentlich fit. Du scheinst mich herausfordern zu wollen. ... mal ehrlich, das ist schon harter Code! (Memo an mich: Ich sollte das naechste Mal nichts mehr von kryptischem Code schreiben, sonst steigt unser Terminal-Hacker bloss gleich wieder darauf ein. )

... ich seh' schon wie ich heute mitten in der Nacht aufstehe, weil mich dieser Code nicht schlafen laesst, oder wie ich aus Alptraeumen von awk-Code, den ich nicht verstehe, aufschrecke ... und dann poste ich auch mal zu nachtschlafener Zeit. Waere dann gut, wenn noch jemand da waere, mit dem ich mir die Sache von der Seele reden koennte.

Lose dem Motto „alles ist eine Datei“ folgend (auch Wortmengen) sieht meine zweite Variante mal etwas anders aus:

Code: Alles auswählen

$ cat max_word_set_same_inner_chars_files 
#!/bin/bash

td=$(mktemp -d) || exit
cd "$td"
I=$(($2-1))
N=$(($3-I))
while read w; do
	[ ${#w} -eq "$1" ] && printf "%s\n" "$w" >>"${w:$I:$N}"
done < "$4"
cat -- "$(wc -l * | sort -nrk1 | awk 'NR==2 {print $2}')"
rm -fr "$td"

Das kann ich jetzt wenigstens lesen. Toll finde ich, dass du so schoen kreative Ansaetze gewaehlt hast, waehrend wir anderen so straight-forward rangegangen sind.

Zwei technische Anmerkungen zu deinem Shellscript:

1) Loeschen von Temp-Dirs. Wenn man ein Temp-Dir am Anfang erzeugt und am Ende loescht, dann kann man im Script zwischendurch nicht aussteigen, sondern braucht dann eine Cleanup-Funktion, usw. Dabei gibt es einen so eleganten Weg mit Traps, um das Temp-Dir automatisch aufraeumen zu lassen:

Code: Alles auswählen

td=$(mktemp -d) || exit
trap 'rm -rf "$td"' 0 1 2 15

Damit wird es beim Ende des Scripts automatisch geloescht, sowohl bei einem normalen Ende (mit `exit') als auch beim Abbruch mit ^C. Will man Abbrechen, um das Tempdir anzuschauen, dann kann man ^\ verwenden (das ist SIGQUIT, womit man auch Coredumps erzeugen kann).

Schoen daran ist, dass damit das Loeschen des Temp-Dirs an der gleichen Stelle im Code ist wie das Erzeugen.

2) `sort -k1'. Soweit ich weiss ist `-k1' nicht anders als wenn man es ganz weglaesst. `-k' ist 1-basiert in der Nummerierung, d.h. es wird ab dem ersten Feld (bis zum Ende der Zeile!) sortiert. Das ist aber auch das was ohne `-k' passiert, naemlich die ganze Zeile. Das vergisst man oft: Will man *nur* nach dem ersten Feld sortieren, dann muss man `-k1,1' schreiben ... was hier aber keinen Unterschied macht.

[tobo]

Dein sort stimmt nicht. Es muss so aussehen:

Code: Alles auswählen

sort  -k1.2,1.6

Bist du da sicher? Es soll sortiert werden ab Buchstabe 3ff.

Code: Alles auswählen

$ printf "aabbbbcc\nbbaaaacc\nccaaaabb\nabbbbcca\nbaaaaccb\ncbbbbaac\n" | sort -k1.2,1.6
baaaaccb
aabbbbcc
bbaaaacc
cbbbbaac
abbbbcca
ccaaaabb
$ printf "aabbbbcc\nbbaaaacc\nccaaaabb\nabbbbcca\nbaaaaccb\ncbbbbaac\n" | sort -k1.3
ccaaaabb
bbaaaacc
baaaaccb
cbbbbaac
aabbbbcc
abbbbcca

[Meillo]

Dein sort stimmt nicht. Es muss so aussehen:

Code: Alles auswählen

sort  -k1.2,1.6

Bist du da sicher? Es soll sortiert werden ab Buchstabe 3ff.

Du hast recht. Jetzt bin ich selber schon ganz mit dem 0-basiert und 1-basiert durcheinander gekommen.

So waere es richtig (denke ich):

Code: Alles auswählen

sort -k1.3,1.6

Wobei es egal ist, ob wir den Rest hinten mitsortieren oder nicht.

[JTH]

So waere es richtig (denke ich):

Code: Alles auswählen

sort -k1.3,1.6

Jo, so stimmts. Mit diesen Grenzen, durch Parameter ersetzt, hab ich die Sortierung auch benutzt.

... ich seh' schon wie ich heute mitten in der Nacht aufstehe, weil mich dieser Code nicht schlafen laesst, oder wie ich aus Alptraeumen von awk-Code, den ich nicht verstehe, aufschrecke ... und dann poste ich auch mal zu nachtschlafener Zeit. Waere dann gut, wenn noch jemand da waere, mit dem ich mir die Sache von der Seele reden koennte.

Na, so schlimm ists hoffentlich auch nicht (Ich hab zumindest nicht die Foren-Nachtschicht heute ) Der Ablauf ist ähnlich wie bei den anderen Schnipseln (Sortieren, häufigste Mitte suchen, Wörter mit eben jener Mitte ausgeben). Nur minimal unnötig zusätzlich verschachtelt.

Das kann ich jetzt wenigstens lesen. Toll finde ich, dass du so schoen kreative Ansaetze gewaehlt hast, waehrend wir anderen so straight-forward rangegangen sind.

Spannend wäre natürlich noch, das Ganze in einer Pipeline, ohne (Shell-)Variablen und mit einmal Einlesen des Wörterbuchs zu lösen – und (nur) die ausgewählten Wörter ausgegeben zu bekommen. Wenn ich das richtig mitverfolgt habe, sind wir da ja noch nicht angekommen (oder?!).

Dabei gibt es einen so eleganten Weg mit Traps, um das Temp-Dir automatisch aufraeumen zu lassen:

Da bin ich einmal faul … Ja, du hast natürlich Recht, dass das über trap die sicherste und sauberste Variante ist. Ich muss allerdings jedes Mal überlegen, welche Signale sinnvoll abzufangen sind. Das Pseudo EXIT verhält sich in z.B. dash und bash ja meine ich nicht gleich.

2) `sort -k1'. Soweit ich weiss ist `-k1' nicht anders als wenn man es ganz weglaesst.

Ich glaube, da vertust du dich. Die Manpage sagt:

[…] both are origin 1, and the stop position defaults to the line's end.

Also wäre das Standardverhalten eher, die ganze Zeile heranzuziehen. An der Stelle im Skript haben die Zeilen aber zwei Felder (Wortanzahl und Dateiname), nur das erste soll Schlüssel sein.

[Meillo]

Spannend wäre natürlich noch, das Ganze in einer Pipeline, ohne (Shell-)Variablen und mit einmal Einlesen des Wörterbuchs zu lösen – und (nur) die ausgewählten Wörter ausgegeben zu bekommen. Wenn ich das richtig mitverfolgt habe, sind wir da ja noch nicht angekommen (oder?!).

Dieser Vorschlag von eggy (halt noch bei sort wie eben besprochen korrigiert) kann das, AFAICS: viewtopic.php?f=34&t=182218&start=15#p1283933

Dabei gibt es einen so eleganten Weg mit Traps, um das Temp-Dir automatisch aufraeumen zu lassen:

Da bin ich einmal faul … Ja, du hast natürlich Recht, dass das über trap die sicherste und sauberste Variante ist. Ich muss allerdings jedes Mal überlegen, welche Signale sinnvoll abzufangen sind.

Ich nehme immer: 0 1 2 15

(Edit: Das kann ich mir auch problemlos merken. Halt die ersten drei Zahlen am Stueck (EXIT, SIGHUB, SIGINT) und dann die 15 (SIGTERM). Signal 3 (SIGQUIT) ist das was ich nicht trappe, damit ich debuggen kann wenn ich das Temp-Dir anschauen will.)

Das Pseudo EXIT verhält sich in z.B. dash und bash ja meine ich nicht gleich.

Davon ist mir nichts bekannt, aber ich lerne gerne dazu.

2) `sort -k1'. Soweit ich weiss ist `-k1' nicht anders als wenn man es ganz weglaesst.

Ich glaube, da vertust du dich. Die Manpage sagt:

[…] both are origin 1, and the stop position defaults to the line's end.

Also wäre das Standardverhalten eher, die ganze Zeile heranzuziehen. An der Stelle im Skript haben die Zeilen aber zwei Felder (Wortanzahl und Dateiname), nur das erste soll Schlüssel sein.

Ja, eben, wenn *nur* nach dem ersten Feld sortiert werden soll, dann darf man *nicht* `-k1' verwenden, sondern muss `-k1,1' verwenden! Das ist unerwartet, aber nunmal so.

Allerdings macht es keinen Unterschied wenn man numerisch sortiert. Zeilen der Form ``Zahl Wort'' kann man ohne die Angabe eines Feldes numerisch sortieren.

Was ich aber eigentlich sagen wollte: `sort -k1' ist identisch zu nur `sort', weil beide von der ersten Spalte bis zum Ende der Zeile sortieren. Denn die erste Spalte ist der Beginn der Zeile.

[Meillo]

Spannend wäre natürlich noch, das Ganze in einer Pipeline, ohne (Shell-)Variablen und mit einmal Einlesen des Wörterbuchs zu lösen – und (nur) die ausgewählten Wörter ausgegeben zu bekommen. Wenn ich das richtig mitverfolgt habe, sind wir da ja noch nicht angekommen (oder?!).

Dieser Vorschlag von eggy (halt noch bei sort wie eben besprochen korrigiert) kann das, AFAICS: viewtopic.php?f=34&t=182218&start=15#p1283933

Das war Quatsch, was ich da geschrieben habe.

Ich glaube, dass das gar nicht gehen kann. Denn wir muessen irgendwann man zaehlen, von welchem Mittelteil es am meisten Vorkommen gibt. Dazu muessen wir alle durchlesen. Dann sind wir aber schon am Ende. Bevor wir nicht am Ende sind, koennen wir nicht wissen, welcher Mittelteil der haeufigste ist. Da es jeder sein kann, muessten wir alle Woerter zwischenspeichern, was dann einem erneuten Durchlesen der Ausgangsdatei gleich kommt. Es wird also nicht ohne eines davon gegen: Zwischenspeichern oder nochmal Einlesen.

[JTH]

(Edit: Das kann ich mir auch problemlos merken. Halt die ersten drei Zahlen am Stueck (EXIT, SIGHUB, SIGINT) und dann die 15 (SIGTERM).

EXIT, INT und TERM nehme ich auch normalerweise. HUP wäre wohl sinnvoll, mir anzugewöhnen, wenns nicht gerade für andere Zwecke herhalten muss.

Das Pseudo EXIT verhält sich in z.B. dash und bash ja meine ich nicht gleich.

Davon ist mir nichts bekannt, aber ich lerne gerne dazu.

Nachdem ich wiedergefunden hab, was ich da im Hinterkopf hatte: (Zumindest) die beiden verhalten sich anscheinend unterschiedlich, wenn man nur EXIT trapt. dash ruft dann den Handler bei einem Signal nicht auf. Ein kleines, sich selbst killendes Skriptchen:

Code: Alles auswählen

for s in $1; do trap "echo '$s handler'" $s; done
sleep 1 &
${2:+kill $2 $$}
wait

Liefert folgendes:

Code: Alles auswählen

$ bash ./sh EXIT
EXIT handler
$ bash ./sh EXIT -sTERM
EXIT handler
Terminated
$ bash ./sh "EXIT TERM" -sTERM
TERM handler
EXIT handler
$ dash ./sh EXIT
EXIT handler
$ dash ./sh EXIT -sTERM
Terminated
$ dash ./sh "EXIT TERM" -sTERM
TERM handler
EXIT handler

Das Verhalten mag gewollt (stammts womöglich aus Posix?) sein, aber wenn man unbedacht nur EXIT trapt, könnte man drüber stolpern.

Ja, eben, wenn *nur* nach dem ersten Feld sortiert werden soll, dann darf man *nicht* `-k1' verwenden, sondern muss `-k1,1' verwenden! Das ist unerwartet, aber nunmal so.

[…]

Was ich aber eigentlich sagen wollte: `sort -k1' ist identisch zu nur `sort', weil beide von der ersten Spalte bis zum Ende der Zeile sortieren. Denn die erste Spalte ist der Beginn der Zeile.

Du hast natürlich völlig recht, das war Käse, was ich vorhin geschrieben habe (hätte mein eigenes Manpage-Zitat mal richtig lesen sollen ). Ist wohl etwas her, dass ich sort „exzessiv“ benutzt hab.

Spannend wäre natürlich noch, das Ganze in einer Pipeline, ohne (Shell-)Variablen und mit einmal Einlesen des Wörterbuchs zu lösen – und (nur) die ausgewählten Wörter ausgegeben zu bekommen.

[…]

Ich glaube, dass das gar nicht gehen kann. […]

Ja, ich denke auch, dass das nicht geht, ohne, dass man auf die ein oder andere Art zweimal über die Wortliste geht. Ich dachte mehr daran, das möglichst geschickt in der Pipeline zu verstecken, vielleicht die Zählung zwischendrin mit in die Wortzeilen zu hängen. Denn auch ein tac oder sort müssten ja alle Daten einmal be-/vorhalten, sonst würde das Umkehren oder Sortieren nicht funktionieren.

[tobo]

So waere es richtig (denke ich):

Code: Alles auswählen

sort -k1.3,1.6

Wobei es egal ist, ob wir den Rest hinten mitsortieren oder nicht.

Genau! Und gerade deswegen ist doch auch an eggys Sortierung nichts falsch.

[Meillo]

So waere es richtig (denke ich):

Code: Alles auswählen

sort -k1.3,1.6

Wobei es egal ist, ob wir den Rest hinten mitsortieren oder nicht.

Genau! Und gerade deswegen ist doch auch an eggys Sortierung nichts falsch.

Stimmt!

Das hier war ja echt ein idiotischer Post von mir: viewtopic.php?f=34&t=182218&start=15#p1283937 An dem ist inhaltlich einfach gar nichts richtig. ... es waere besser, ich wuerde etwas mehr nachdenken, bevor ich poste.

Danke, dass du nicht locker gelassen hast, bis ich's auch blicke!

[Meillo]

Hier eine Loesung, die aus genau einer Pipeline besteht und alle Woerter mit dem haeufigsten Mittelteil ausgibt:

Code: Alles auswählen

#!/bin/sh

dict=/usr/share/dict/ngerman 

grep '^........$' "$dict" | sort -k1.3 | awk '
{
        m=substr($0,3,4)
        print (m==last)?++n:n=1, $0
        last=m
}
' | sort -nr | awk '
NR==1 {
        m=substr($2,3,4)
}
substr($2,3,4)==m {
        print $2
}
'

Funktionsweise:
- Sortiere nach den Mittelteilen
- Nummeriere wie oft der jeweilige Mittelteil schon hintereinander vorgekommen ist
- Sortiere numerisch, damit der haeufigste ganz oben ist
- Schaue dir den ersten an und gebe dann alle mit gleichem Mittelteil aus

Es wird nicht mehr als ein Mittelstueck und eine Zaehler gespeichert. (Plus dass beim Sortieren natuerlich zwangslaeufig der gesamte Inhalt zwischengespeichert werden muss.)

Nimmt bei mehreren gleich haeufig auftretenden Mittelteilen nur einen davon.

[Meillo]

... bloss funktioniert mein sort irgendwie nicht richtig:

Code: Alles auswählen

: printf 'irgendwo\nangenehm\näugendes\n' | sort -k 1.3
irgendwo
angenehm
äugendes

``äugendes'' muesste vor ``angenehm'' kommen.

Sieht nach einer fehlenden Multibyte-Unterstuetzung aus. (Bei mir ist es ein GNU sort 8.13 ... vielleicht macht es ein neueres sort besser.)

Auf FreeBSD (sort 2.3-FreeBSD) tut es korrekt:

Code: Alles auswählen

$ printf 'irgendwo\nangenehm\näugendes\n' | sort -k 1.3
äugendes
irgendwo
angenehm

... dafuer kann dort der FreeBSD-awk kein UTF-8.

Ich habe schon alles mit den Locales ausprobiert.

Ach! Das naechste Mal schreibe ich rein, dass nur US-ASCII verarbeitet werden soll ...


Edit:
Hier mein Script (das zumindest mit englischen Wortlisten funktioniert) nochmal ein bisschen kuerzer:

Code: Alles auswählen

#!/bin/sh

dict=/usr/share/dict/words 

grep '^........$' "$dict" | sort -k1.3 | awk '
{
        m=substr($0,3,4)
        print (m==last)?++n:n=1, m, $0
        last=m
}
' | sort -nr | awk '
NR==1 { m=$2 }
$2==m { print $3 }
'

[JTH]

Wobei es egal ist, ob wir den Rest hinten mitsortieren oder nicht.

Genau! Und gerade deswegen ist doch auch an eggys Sortierung nichts falsch.

Ich glaube, das ist es tatsächlich nicht (je nach Zielsetzung natürlich). Vielleicht ist uns das hier in mehreren Beiträgen schon auf die Füße gefallen. Wenn man mal voraussetzt, dass die Wörterbuchdateien für die Sprache sinnvoll vorsortiert sind und man als Ausgabe auf die gleiche Weise sortierte Wörter haben möchte, macht es nen Unterschied, ob man wirklich nur den Mittelteil sortiert oder den ganzen hinteren Substring: Das erste Sortierergebnis ist eher unerwartet:

Code: Alles auswählen

$ printf "aab\nabb\nbaa\nbba\n" | sort -k1.2
baa
aab
bba
abb
$ printf "aab\nabb\nbaa\nbba\n" | sort -k1.2,1.2
aab
baa
abb
bba

(Oder denk ich da womöglich um zu viele Ecken?)

Hier eine Loesung, die aus genau einer Pipeline besteht und alle Woerter mit dem haeufigsten Mittelteil ausgibt:

Ja genau, an so einer Variante war ich gestern am Grübeln und Basteln

Sieht nach einer fehlenden Multibyte-Unterstuetzung aus. (Bei mir ist es ein GNU sort 8.13 ... vielleicht macht es ein neueres sort besser.)

Kann ich mit 8.32 nachvollziehen. Wahrscheinlich wird tatsächlich byteweise nach irgendwo, angenehm, äugendes sortiert.

Man könnte das Problem umgehen, indem man mit (dem anscheinend mutlibyte fähigen) (g)awk die Mittelteile raussucht, dann direkt nach der neuen Mittelteil-Spalte sortiert (die naive, byteweise Interpretation durch sort ist dann egal) und auch stabil sortiert, um die Reihenfolge aus dem Dictionary zu behalten:

Code: Alles auswählen

awk 'length == 8 { print(substr($0, 3, 4), $0) }' "$1" |
sort -s -k1,1 -k2,2r |
awk '
{
        print ($1==last)?++n:n=1, $0
        last=$1
}
' | sort -nrs | awk '
NR==1 { m=$2 }
$2==m { print $3 }
'

Mag sein, dass man nicht an beiden Stellen stabil sortieren müsste. Aber das scheint so auch mit dem deutschen Wörterbuch zu funktionieren.

[tobo]

Wobei es egal ist, ob wir den Rest hinten mitsortieren oder nicht.

Genau! Und gerade deswegen ist doch auch an eggys Sortierung nichts falsch.

Ich glaube, das ist es tatsächlich nicht (je nach Zielsetzung natürlich).

Für die gestellte Aufgabe ist es egal. Es ist ja nur relevant, dass die Wörter mit den 4 gleichen mittleren Buchstaben untereinander stehen. Diese Wörter könnte man danach auch gerne noch in ihrer Reihenfolge randomisieren.

Das erste Sortierergebnis ist eher unerwartet:

Code: Alles auswählen

$ printf "aab\nabb\nbaa\nbba\n" | sort -k1.2
baa
aab
bba
abb
$ printf "aab\nabb\nbaa\nbba\n" | sort -k1.2,1.2
aab
baa
abb
bba

Wieso ist das unerwartet - bei gleichem 2. Buchstaben folgt im 3. Buchstaben a vor b. Wäre das die Aufgabenstellung gewesen (gleicher 2. Buchstabe von 3), dann wären die beiden Wortlisten gleichwertig. Da beide Sortierungen nicht stabil sind, wären hier auch noch andere Reihenfolgen denkbar und richtig (2. Sortierung bzw. bei größerer Eingabe auch 1.).

PS: sort 8.30 liefert auch das falsche Ergebnis.

[Meillo]

tobos Anmerkungen stimme ich zu.

Wahrscheinlich wird tatsächlich byteweise nach irgendwo, angenehm, äugendes sortiert.

Ja, das denke ich auch.

Man könnte das Problem umgehen, indem man mit (dem anscheinend mutlibyte fähigen) (g)awk die Mittelteile raussucht, dann direkt nach der neuen Mittelteil-Spalte sortiert (die naive, byteweise Interpretation durch sort ist dann egal)

Klasse Idee!

Code: Alles auswählen

awk 'length == 8 { print(substr($0, 3, 4), $0) }' "$1" |
sort -s -k1,1 -k2,2r |
awk '
{
        print ($1==last)?++n:n=1, $0
        last=$1
}
' | sort -nrs | awk '
NR==1 { m=$2 }
$2==m { print $3 }
'

... dreimal awk in einer Pipeline zu verwenden ist immer ein gutes Zeichen.

Dieses `length==8' in awk mag ich ... ist irgendwie netter als mit grep.

Hier mal ein paar Varianten, nur so zur Uebung:

Code: Alles auswählen

:-Q awk 'length==8' /usr/share/dict/ngerman | wc -l            
21032

:-Q egrep -x '........' /usr/share/dict/ngerman | wc -l
21032

:-Q egrep '^........$' /usr/share/dict/ngerman | wc -l 
21032

:-Q egrep '^.{8}$' /usr/share/dict/ngerman | wc -l    
21032

:-Q egrep -x '.{8}' /usr/share/dict/ngerman | wc -l  
21032

:-Q grep -x '.\{8\}' /usr/share/dict/ngerman | wc -l   
21032

:-Q sed -n '/^........$/p' /usr/share/dict/ngerman | wc -l
21032

:-Q sed '/^........$/!d' /usr/share/dict/ngerman | wc -l  
21032

:-Q sed '/^.\{8\}$/!d' /usr/share/dict/ngerman | wc -l  
21032

:-Q egrep ^.{8}$ /usr/share/dict/ngerman | wc -l          
21032

... ist die letzte die kuerzest moegliche?


Edit:
@JTH, du machst dir zu viele Gedanken beim Sortieren. Es geht auch so einfach:

Code: Alles auswählen

awk 'length == 8 { print(substr($0, 3, 4), $0) }' "$1" |
sort |
awk '
{
        print ($1==last)?++n:n=1, $0
        last=$1
}
' | sort -nr | awk '
NR==1 { m=$2 }
$2==m { print $3 }
'

[Phineas]

Awk sollte die Aufgabe alleine lösen können:

Code: Alles auswählen

</usr/share/dict/words awk '{if(length($0)==8){i=substr($0,3,4);a[i]++;if(a[i]>m){m=a[i];w=i}}}END{print m,w}'

Verzeiht einem Nicht-Debianer, dass er eine andere Wortliste benutzt.

[tobo]

Ja, sowas nennt man dann kompakt!

[Phineas]

Aber ziemlich schnell (runtime), behaupte ich mal. Was aber natürlich nicht an der Kompaktheit liegt.

[tobo]

Macht halt die Abwägung zwischen Laufzeit und Speicherplatz (RAM), aber ja - ordentlich flott. Zeigt somit, dass man die Sortierung in die Tonne treten kann.

[Meillo]

Awk sollte die Aufgabe alleine lösen können:

Code: Alles auswählen

</usr/share/dict/words awk '{if(length($0)==8){i=substr($0,3,4);a[i]++;if(a[i]>m){m=a[i];w=i}}}END{print m,w}'

Coole Sache!

Ich habe mir erlaubt, das noch ein bisschen mehr zu kompaktifizieren:

Code: Alles auswählen

</usr/share/dict/words awk 'length==8&&++a[i=substr($0,3,4)]>a[w]{w=i}END{print w}'

[Phineas]

Vielen Dank!

Ist schon heftig, was mit awk alles möglich ist. Bei mir ist awk übrigens nur noch ein Link auf gawk.

[hikaru]

Awk sollte die Aufgabe alleine lösen können:

Code: Alles auswählen

</usr/share/dict/words awk '{if(length($0)==8){i=substr($0,3,4);a[i]++;if(a[i]>m){m=a[i];w=i}}}END{print m,w}'

Coole Sache!

Ich habe mir erlaubt, das noch ein bisschen mehr zu kompaktifizieren:

Code: Alles auswählen

</usr/share/dict/words awk 'length==8&&++a[i=substr($0,3,4)]>a[w]{w=i}END{print w}'

Nachdem ich von JTHs Lösungen und dem Traps-Exkurs bereits angeschlagen war, habe ich gerade fünf Minuten wie hypnotisiert auf diesen Beitrag gestarrt (beide Code-Schnipsel).
Ich finde, wir brauchen einen neuen BB-Tag für Gesundheitswarnungen.

[Phineas]

Tatsächlich tun wir da nichts, was nicht schon vorher hier im Thread angesprochen wurde: Die Awk-Funktionen length() und substr(), sowie das assoziative Array, alles nochmal in die Tüte getan und gut geschüttelt.

[Meillo]

Nachdem ich von JTHs Lösungen und dem Traps-Exkurs bereits angeschlagen war, habe ich gerade fünf Minuten wie hypnotisiert auf diesen Beitrag gestarrt (beide Code-Schnipsel).
Ich finde, wir brauchen einen neuen BB-Tag für Gesundheitswarnungen.

Ich nehme das mal zum Anlass, meinen Code schrittweise zu zerlegen und zu erklaeren.

Code: Alles auswählen

</usr/share/dict/words awk 'length==8&&++a[i=substr($0,3,4)]>a[w]{w=i}END{print w}'

Beginnen wir mit der Formatierung:

Code: Alles auswählen

</usr/share/dict/words awk '
length==8 && ++a[i=substr($0,3,4)]>a[w] {
	w=i
}
END{
	print w
}
'

Wir haben also zwei Bloecke: Der erste hat als Bedingung zwei Vergleiche, der zweite ist ein END-Block. Zuerst der einfache Teil: Der END-Block wird ausgefuehrt, wenn der Input komplett gelesen worden ist, also bevor awk sich beendet. Darin wird die Variable `w' ausgegeben.

Nun zum koplizierteren Teil:

Code: Alles auswählen

length==8 && ++a[i=substr($0,3,4)]>a[w] {
	w=i
}

Awk funktioniert so, dass ein Script aus Bedingungs-Aktions-Paaren besteht. Die Aktion steht in geschweiften Klammern (hier `{w=i}'), die Bedingung ist das davor (hier zwei verundete Vergleiche). Die Bedingung sagt, fuer welche Zeilen die Aktion ausgefuehrt wird. Gibt man keine Bedingung an, dann wird die Aktion fuer alle Zeilen ausgefuehrt.

Statt die Bedingung vor den Block zu schreiben, kann man sie auch mit einem if nutzen. Die folgenden vier Formen sind alle aequivalent:

Code: Alles auswählen

length==8 && ++a[i=substr($0,3,4)]>a[w] {
	w=i
}

Code: Alles auswählen

{
	if (length==8 && ++a[i=substr($0,3,4)]>a[w]) {
		w=i
	}
}

Code: Alles auswählen

length==8 {
	if (++a[i=substr($0,3,4)]>a[w]) {
		w=i
	}
}

Code: Alles auswählen

{
	if (length==8) {
		if (++a[i=substr($0,3,4)]>a[w]) {
			w=i
		}
	}
}

Letztere Form hatte Phineas gewaehlt. Ich habe das dann zur ersten Form verkuerzt, um mir das if zu sparen.

`length' ohne etwas ist identisch zu `length($0)', was eine Funktion ist, die die Laenge der Inputzeile ausgibt. In awk kann man bei Funktionen manchmal die Klammern weglassen, so auch z.B. bei `print', das ohne irgendwas gleich wie `print($0)' ist, aber man kann es sowohl in der Form `print var` als auch `print(var)' nutzen. Das ist ein bisschen eine awk-Eigenheit, die nur darum akzeptabel ist, weil die Sprache so klein ist und die Anzahl der Funktionen so uebersichtlich (also verhaeltnismaessig zu anderen Sprachen).

Damit trifft die erste Bedingung nur auf Zeilen der Laenge 8 zu.

Nun weiter zum eigentlich kryptischen Teil -- die zweite Bedingung:

Code: Alles auswählen

++a[i=substr($0,3,4)]>a[w]

Hierzu muss man sich ein bisschen mit C-aehnlichen Sprachen auskennen, was Praezedenzen und Seiteneffekte angeht. Wenn man so einen Ausdruck zerlegen will, dann muss man Parser spielen und anhand der Praezedenzen gruppieren. Dann beginnt man bei der niedrigsten Praezedenz zu zerlegen, wie man das auch mit einem mathematischen Ausdruck ohne Klammern machen wuerde, bloss dass es dort nicht so viele Praezedenzstufen gibt.

Hier die Praezedenzen von C (die auch hier gelten) aus der Manpage operator(7):

Code: Alles auswählen

       Operator                             Associativity
       () [] -> .                           left to right
       ! ~ ++ -- + - (type) * & sizeof      right to left
       * / %                                left to right
       + -                                  left to right
       << >>                                left to right
       < <= > >=                            left to right
       == !=                                left to right
       &                                    left to right
       ^                                    left to right
       |                                    left to right
       &&                                   left to right
       ||                                   left to right
       ?:                                   right to left
       = += -= *= /= %= <<= >>= &= ^= |=    right to left
       ,                                    left to right

Das `&&' habe ich oben stillschweigend schon zerteilt.

Nun geht es weiter mit dem `>':

Code: Alles auswählen

++a[i=substr($0,3,4)]  >  a[w]

Das Linke muss also groesser als das Rechte sein. Das Rechte ist ein Arrayzugriff des Arrays `a' an der Stelle `w'. Arrays in awk sind assoziativ (also Hashes). `w' ist, wie man spaeter versteht, ein Mittelteil, also ein String mit vier Buchstaben. Der Wert von `a[w]' ist eine Zahl, wie auch spaeter klar wird.

Nehmen wir uns die linke Seite vor:

Code: Alles auswählen

++a[i=substr($0,3,4)]

Die eckige Klammer ist eine Klammer (hoechste Praezedenz), also muessen wir uns das darn erstmal noch nicht anschauen. Das `++' (Prae-Inkrement) hat eine niedrigere Praezedenz als der Arrayzugriff (`[...]') damit wirkt das `++' auf alles was rechts davon steht. Und da steht ein Arrayzugriff vom Array `a' an der Stelle:

Code: Alles auswählen

i=substr($0,3,4)

Das ist eine Zuweisung. In C-aehnlichen Sprachen sind Zuweisungen zugleich Ausdruecke, d.h. sie geben den zugewiesenen Wert auch zurueck. Die folgenden zwei Zeilen sind aequivalent:

Code: Alles auswählen

a[i=substr($0,3,4)]
i=substr($0,3,4); a[i]

Ob ich also erst zuweise und dann die Variable nutze, oder ob ich die Zuweisung auch zur Nutzung verwende, ist in C-aehnlichen Sprachen egal.

Was das `substr()' macht sollte recht klar sein: Es extrahiert den Mittelteil, also von der Inputzeile (`$0' ... die aus genau einem 8-buchstabigen Wort besteht), nimmt es den Teil ab Buchstaben 3 und zwar 4 Buchstaben lang.

Dieser Mittelteil wird dann der Variable `i' zugewiesen und dann wird ...


-- jetzt, wo wir am innersten Punkt angekommen sind, bauen wir das ganze wieder schrittweise nach aussen zusammen --


(Anm: Ich habe `a[i_]' mit Unterstrich schreiben muessen, damit der BB-Code darauf nicht anspricht. Den Unterstrich muesst ihr euch wegdenken. Es ging technisch leider nicht anders.)


... der Wert von `a[i_]' um 1 inkrementiert mit dem (`++'). (Falls es einen Arraywert in awk nicht gibt, dann wird er mit dem Wert 0 automatisch angelegt.)

D.h. wir speichern in `a' ab, wie oft wir einen Mittelteil schon gefunden haben. Beim ersten Mal wird `a[i_]' von 0 auf 1 erhoeht, beim zweiten Mal dann von 1 auf 2, usw. Das macht dieser Code:

Code: Alles auswählen

++a[i=substr($0,3,4)]

Der Unterschied zu

Code: Alles auswählen

a[i=substr($0,3,4)]++

wirkt sich nur auf die weiteren Aktionen aus. Wenn das `++' vorne steht, dann wird das Inkrement naemlich sofort ausgefuehrt, bevor wir nun weiter gehen. Wenn es hinten steht, dann wird erst der ganze Ausdruck ausgewertet und *danach* erst wird das Inkrement ausgefuehrt. Wir moechten hier, dass es sofort passiert. Hier nochmal jeweils drei aequivalente Zeilen:

Code: Alles auswählen

# es wird der neue Wert ausgegeben
++a[i]; print a[i]
a[i]++; print a[i]
print ++a[i]

# es wird der alte Wert ausgegeben
print a[i]; ++a[i]
print a[i]; a[i]++
print a[i]++

Also wird bei uns `a[i_]' erhoeht und dann mit `a[w]' verglichen. `i' ist der aktuelle Mittelteil, den wir gerade mit `substr()' ermittelt haben. `w' ist der bislaeng haeufigste Mittelteil, den wir uns merken (dazu kommen wir gleich).

Wir vergleichen nun also, ob der aktuelle Mittelteil haeufiger ist als der bislang haeufigste:

Code: Alles auswählen

++a[i=substr($0,3,4)]  >  a[w]

Und wenn dem so ist, dann merken wir uns den aktuellen als den haeufigsten:

Code: Alles auswählen

w=i

So sind wir nun einmal durch.

Phineas hatte etwa mehr hintereinander was ich dann zu mehr verschachteltem Code umgeformt habe.

Code: Alles auswählen

</usr/share/dict/words awk '
length==8 && ++a[i=substr($0,3,4)]>a[w] {
	w=i
}
END{
	print w
}
'

Nochmal natuerlichlichsprachlich: Bei allen Zeilen mit 8 Zeichen, speichern wir den Mittelteil in `i', inkrementieren wie oft er bisher vorgekommen ist `a[i_]', und wenn dies oefter war als der bisher haeufigste Mittelteil `a[w]', dann merken wir uns den aktuellen (`i') als den haeufigsten Mittelteil (`w'). Am Ende des Scripts geben wir den haeufigsten Mittelteil (`w') aus.

(Es waere fuer das Verstaendnis wahrscheinlich besser gewesen, wenn der aktuelle Mittelteil `m' geheissen haette und nicht `i', weil `i' per Konvention normalerweise nur fuer Zaehlvariablen verwendet wird und meist nur fuer Zahlen. `w' steht hier moeglicherweise fuer ``Winner''. `a' steht fuer ``Array''. -- Aussagekraeftige Bezeichner helfen beim Codeverstaendnis. Bei einbuchstabigen Bezeichnern wird das natuerlich umsoschwieriger.)


Vielleicht hat diese (lange) Erklaerung etwas Licht ins Dunkel gebracht.