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

[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.

[Phineas]

i sollte Index bedeuten ( a[index] ), w word, m most und a Array. Bei Einzeilern mache ich mir keinen großen Kopf darum.

Schöne Erklärung von Dir, Meillo.

[Meillo]

Dann will ich hierauf mal noch eingehen:

Und bitte lass uns diese am Ende auch ansehen und wenn es nur abfotografiert in der Gallery ist!

Ich bin mir nicht sicher, ob der Autor nur noch nie von Pipelines gehoert hat oder ob er aus didaktischen (?) Gruenden auf sich verzichtet. Jedenfalls macht er alles in Einzelschritten.

Zuerst extrahiert er die acht-buchstabigen Woerter:

Code: Alles auswählen

grep '^........$' /usr/dict/words > eights

Dann holt er die Mittelteile raus:

Code: Alles auswählen

sed 's/^..//; s/..$//' eights > middle

(Diesen Befehl hat er nicht explizit so angegeben, sondern geschrieben, dass man die Ersetzungen mit ex oder sed machen koenne.)

Dann sortiert er die Mittelteile:

Code: Alles auswählen

sort middle -o middle

Anschliesend zaehlt er sie:

Code: Alles auswählen

uniq -c middle count

(Interessant! Mir war nicht bewusst, dass man bei uniq eine zweite Datei als Output angeben kann.)

Dann sortiert er numerisch:

Code: Alles auswählen

sort -nr count -o count

Er schaut dann in die Datei ``count'' und sieht, dass der haeufigste Mittelteil ``ippi'' ist, mit 11 Vorkommen.

Um alle Woerter mit diesem Mittelteil zu finden verwendet er diesen Befehl:

Code: Alles auswählen

grep '^..ippi' eights

Vom Vorgehen ist die Loesung straight-forward: acht-buchstabige Woerter selektieren, Mittelteile extrahieren, sortieren, zaehlen, numerisch sortieren -- so sehen die meisten Loesungen von uns auch aus.

Dass er keine Pipelines verwendet wundert mich etwas. Das kommt mir etwas un-Unix-artig vor, zeigt aber vielleicht, dass sie auch 1985 noch nicht so im Denken der Benutzer verankert waren wie heute. `sort file -o file' habe ich schon lange nicht mehr von einem heutigen Benutzer gesehen. Auch insgesamt wuerden die meisten `sort|uniq -c|sort -nr' als Pipeline schreiben, denke ich, weil das so sehr eine Sinneinheit ist. Dies alles ist wohl einfach der Zeit damals geschuldet, in der viele heutige Selbstverstaendlichkeiten noch nicht selbstverstaendlich waren.

[inne]

Dann will ich hierauf mal noch eingehen:

Und bitte lass uns diese am Ende auch ansehen und wenn es nur abfotografiert in der Gallery ist!

Ich bin mir nicht sicher, ob der Autor nur noch nie von Pipelines gehoert hat oder ob er aus didaktischen (?) Gruenden auf sich verzichtet. Jedenfalls macht er alles in Einzelschritten

Ich muss nochmal nachfragen.
Werden Pipes im dem Buch denn gernicht erwähnt, für mich wären Pipes erklären nun der nächste logische Schritt oder gab es das Konzept der Pipe erst später?
Muss mir das nun auch mal selbst ansehen, mit Chronic und wann McIlroy die Pipes bringt (Das Jahr könnte ich nicht sagen - hatte UNIX das von begin an), aber das Buch ist halt leider englisch?

[MSfree]

für mich wären Pipes erklären nun der nächste logische Schritt oder gab es das Konzept der Pipe erst später?

https://de.wikipedia.org/wiki/Pipe_(Informatik)
Pipes wurden 1973 "erfunden".

Auch unter DOS 2.0 gab es schon Pipes.

[fischig]

Code: Alles auswählen

ls -R ./Bilder | grep -ic '\.jpg$'

¹
Ein sehr schönes Besipiel dafür, wie es Informatikern immer wieder gelingt, einen eigentlich recht einfachen Sachverhalt sofort mit überflüssigen Komplikationen zu überfrachten.
Immerhin sei zur Ehrenrettung des Autors gesagt: Er erläutert die allermeisten (, nicht alle! ) seiner eingebauten Komplikationen angemessen in laienverständlicher Weise!

¹ https://de.wikipedia.org/wiki/Pipe_(Informatik)

[Meillo]

Ich muss nochmal nachfragen.
Werden Pipes im dem Buch denn gernicht erwähnt, für mich wären Pipes erklären nun der nächste logische Schritt [...]

Es ist kein Shellscripting-Buch, sondern eines ueber den Editor vi/ex, insofern ist diese Aufgabe nur ein Exkurs und Pipelines sind ausserhalb des Fokus des Buches. Das ist sicher auch ein Grund dafuer. Mit einem Editor arbeitet man dateizentriert; eine Pipeline ist datenflusszentriert.

[inne]

Auch unter DOS 2.0 gab es schon Pipes.

OK. Aber konnte man die sinnvoll nutzen? Das fehlt mir auch in Windows 11, was das Terminal und Pipes schon vor-installiert mitbringt.

[thoerb]

Auch unter DOS 2.0 gab es schon Pipes.

OK. Aber konnte man die sinnvoll nutzen? Das fehlt mir auch in Windows 11, was das Terminal und Pipes schon vor-installiert mitbringt.

Ich kann mich noch an so was wie "dir | more" erinnern.

[MSfree]

Aber konnte man die sinnvoll nutzen?

Naja, kommt drauf an, was du als "sinnvoll" erachtest

Code: Alles auswählen

prog1 | prog2 | prog3

Geht schon seit einer Eiwigkeit unter fast allen OS (ausser CP/M), mit denen ich in den letzen Jahrzehnten zu tun hatte..

Das fehlt mir auch in Windows 11

Verstehe ich das richtig, Win11 kann den o.g. Konstrukt nicht mehr

[tobo]

Unter Windows funktionierte das Pipen gefühlt schon immer. Es gab aber auch schon immer nur eine handvoll (mitgelieferte) Programme, die zum Pipen sinnvoll in der Lage waren (stdin/stdout inkompatibel). Keine Ahnung, ob das heute auch noch so ist. Die Shell soll ja ziemlich mächtig sein.

[inne]

Das fehlt mir auch in Windows 11

Verstehe ich das richtig, Win11 kann den o.g. Konstrukt nicht mehr

Doch es *kann* Pipes aber *mir* fehlen dann die Programme wie die coreutils um mit den Pips was "sinnvolles" anzufangen. Gebrauchen kann man die Pipes dann erst, wenn man z.B. Perl oder so installiert hat und Sachen wie cpan-outdated -p|cpanm tut. So war mein Eindruck.
Aber wahrscheinlich kenne ich mich dort zu wenig aus.