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

[Meillo]

Hoi,

in einem Buch von 1985 habe ich eine Loesung fuer eine Programmieraufgabe von Donald Knuth gefunden. Leider steht kaum etwas ueber die Aufgabe dabei. Im Web habe ich auch nichts dazu finden koennen. Fuer Shellscripter scheint sie mir auch zu einfach zu sein, als dass es passen wuerde, dass sie von Knuth stammt.

Einerseits suche ich nun die eigentliche Aufgabe von Knuth -- Hinweise willkommen!

Andererseits koennen wir damit einen netten kleinen Scripting-Contest veranstalten.


In dem Buch heisst es:

Answer to Knuth's Challenge

Did you try to solve the problem of finding the largest set of words with the same middle four letters? Here is a solution. [...]

Das Problem, das es zu loesen gilt, scheint folgendes zu sein: Von allen acht-buchstabigen Woertern soll man Sets bilden fuer jeweils diejenigen Woerter, die die gleichen vier mittleren Buchstaben (d.h. die Buchstaben 3-6) haben. Von all diesen Sets will man das groesste wissen. Also die groesste Menge von acht-buchstabigen Woertern mit den gleichen vier mittleren Buchstaben.


Ich denke, dass das Problem nicht allzu schwierig umzusetzen sein wird. Interessanter wird sein, moeglichst kurze (und kryptische ) Loesungen zu finden. Darum schlage ich vor, nicht bis zum Wochenende zu warten, bis die ersten Loesungen gepostet werden duerfen: Loesungen duerfen ab Donnerstag gepostet werden.


Btw: Worlisten findet man in wamerican, wngerman und aehnlichen Paketen. Die liegen dann in /usr/share/dict/

[eggy]

Andererseits koennen wir damit einen netten kleinen Scripting-Contest veranstalten.

Sonntag war mal gedacht, damit auch die Leute, die unter der Woche keine Zeit finden, ne Möglichkeit haben mitzuspielen. Beim nächsten Kurzcontest mit dem Posten der Aufgabenstellung einfach bis Donnerstag/Freitag warten, dann gibt's "wenig Zeit" und sowohl Nichtwochenendtage als auch Wochenendtage.

[inne]

Hallo,

in einem Buch von 1985 habe ich eine Loesung fuer eine Programmieraufgabe von Donald Knuth gefunden. Leider steht kaum etwas ueber die Aufgabe dabei. Im Web habe ich auch nichts dazu finden koennen.

Wofür *ich* solch eine Lösung gebrauchen könnte, fällt mir auch erstmal kein Fall ein Vlt. einfach nur ein Beispiel für associative Arrays, wenn ich mir meine Lösung so ansehe?
Wie heisst denn das Buch (Google Books findet für Donald Knuth schon einige) und wie das Kapitel und Überschrift?

Fuer Shellscripter scheint sie mir auch zu einfach zu sein, als dass es passen wuerde, dass sie von Knuth stammt.

Kannst Du sagen in welcher Programmiersprache die Lösung im Buch ist, Shell/BASH?
Und bitte lass uns diese am Ende auch ansehen und wenn es nur abfotografiert in der Gallery ist!

[Meillo]

in einem Buch von 1985 habe ich eine Loesung fuer eine Programmieraufgabe von Donald Knuth gefunden. Leider steht kaum etwas ueber die Aufgabe dabei. Im Web habe ich auch nichts dazu finden koennen.

Wofür *ich* solch eine Lösung gebrauchen könnte, fällt mir auch erstmal kein Fall ein Vlt. einfach nur ein Beispie für associative Arrays, wenn ich mir meine Lösung so ansehe?
Wie heisst denn das Buch (Google Books findet für Donald Knuth schon einige) und wie das Kapitel und Überschrift?

Das Buch in dem ich die Erwaehnung gefunden habe ist: ``Editing in a UNIX Environment: The vi/ex Editor'' von Mohamed el Lozy. Wo aber Knuth diese Aufgabe gestellt haben sollte, das frage ich mich eben. Ich glaube nicht, dass er das in einem seiner Buecher getan hat, das passt irgendwie nicht. Ich kann mir auch nicht vorstellen, dass das eine grosse Sache war (so wie es in dem Buch von el Lozy dargestellt wird), weil Knuth normalerweise auf einem ganz anderen Niveau unterwegs ist. Das ist alles ein bisschen seltsam. Darum wuerde mich eben interessieren was es tatsaechlich damit auf sich hat.

Fuer Shellscripter scheint sie mir auch zu einfach zu sein, als dass es passen wuerde, dass sie von Knuth stammt.

Kannst Du sagen in welcher Programmiersprache die Lösung im Buch ist, Shell/BASH?
Und bitte lass uns diese am Ende auch ansehen und wenn es nur abfotografiert in der Gallery ist!

Die Umsetzung im Buch ist in der Shell. Ich kann sie dann gerne auch beitragen ... wobei meine eigene Umsetzung natuerlich besser ist.

[paedubucher]

In dem Buch heisst es:

Answer to Knuth's Challenge

Did you try to solve the problem of finding the largest set of words with the same middle four letters? Here is a solution. [...]

Mir ist spontan ein Artikel der NZZ eingefallen, den ich schon vor über einem Jahrzehnt einmal gelesen hatte:

Das Talent, sich in der Welt der Ziffern und Zeichen zu bewegen, zeigte sich so früh wie die Hartnäckigkeit, ein einmal gestecktes Ziel zu verfolgen. Im achten Schuljahr beteiligte er sich an einem Wettbewerb, den ein Süsswarenfabrikant ausgeschrieben hatte; es ging darum, wer am meisten Wörter aus den Buchstaben des Produktenamens «Ziegler’s Giant Bar» bilden konnte. Der kleine Knuth legte eine Liste von 4500 Wörtern vor - 2000 mehr, als die Jury hatte -, gewann den ersten Preis, einen Fernseher, sowie genug Schokoriegel, die ganze Schule zu versorgen.

Quelle

Dies war keine Aufgabe, die von Knuth gestellt worden ist, sondern eine, die Knuth gemeistert hatte. Ich könnte mir vorstellen, dass der Autor hier eine abgewandelte (einfachere) Variante verwendet. Es wäre natürlich auch möglich, dass Knuth diese Aufgabe seinen Studenten gestellt hat, und diese darum nicht in seinen Büchern zu finden ist.

[JTH]

Nette Bastelei, da bin ich ja mal gespannt auf morgen …

wobei meine eigene Umsetzung natuerlich besser ist.

… ich hab allerdings das Gefühl, die Jury ist voreingenommen

[Meillo]

… ich hab allerdings das Gefühl, die Jury ist voreingenommen

Ich weiss nicht was du meinst.


Aber wir machen das ja alle fuer die ``Experience''.

Wenn wir schon bewerten wollen, so gilt der Massstab der kuerzesten Loesung (Anzahl Zeichen des vollstaendigen Programmcodes).

Wo ich noch unschluessig bin ist, was die Ausgabe sein sollte: Nur der vier-buchstabige Mittelteil, also genau ein vier-buchstabiges ``Wort''. Oder die Liste aller Woerter die diesen Mittelteil beinhalten.

Es hat beides etwas fuer sich. Wenn es nur um das Finden des populaersten Mittelteils geht, dann kann man schoen kurze Programme schreiben. Wenn man die Woerter auflisten soll, dann muss man zweimal durch die Woerterliste laufen oder sich eine Menge im Speicher halten ... was dann wieder um einem zweimaligen Durchlaufen entspricht, bloss nicht indem man die Datei zweimal liest, sondern die Datenstruktur im Speicher nochmal durchgeht.

Mir kommt es eher auf den ersten Teil an: Finde das am oeftesten vorkommende Mittelstueck.

Aber da es insgesamt darum geht, dass wir Spass dabei haben, inspiriert werden und etwas lernen koennen, ist natuerlich alles erlaubt und gerne gesehen. Interessant wird's (fuer mich) vor allem dann wenn die Loesungen da sind und wir sie in einem zweiten Schritt versuchen zu verbessern.

[inne]

Wo ich noch unschluessig bin ist, was die Ausgabe sein sollte:

Nur der vier-buchstabige Mittelteil, also genau ein vier-buchstabiges ``Wort''.

Es können aber doch auch mehrere "vier-buchstabige Mittelteile" das Ergebniss sein?!

Oder die Liste aller Woerter die diesen Mittelteil beinhalten.

Ich gebe beides aus, kann letztes aber leicht werglassen. Ich wollte das nur haben, weil es mich interessiert hat, welche Wörter den "vier-buchstabigen Mittelteil" enthalten. Hätte ich aber auch aus der Lösung rauslassen können.

Ich gebe aktuell "vier-buchstabiger Mittelteil, Anzahl, Wortliste" aus. Also z.B.

Code: Alles auswählen

abcd	3	aaabcdaa bbabcdbb ccabcdcc
0123	3	dd0123dd ee0123ee ff0123ff

Meine Lösung ist aber in Perl, weil mir in der Shell nichts gutes einfallen will.

// Wobei ich nun auch eine Shell-Lösung habe, aber mit anderer Ausgabe

Code: Alles auswählen

	3 0123
	3 abcd

[Meillo]

Nur der vier-buchstabige Mittelteil, also genau ein vier-buchstabiges ``Wort''.

Es können aber doch auch mehrere "vier-buchstabige Mittelteile" das Ergebniss sein?!

Das habe ich bisher ignoriert. Ich nehme dann halt nur eines von ggf. mehreren.

... es wird also genug Diskussionsstoff geben.

[inne]

Das habe ich bisher ignoriert. Ich nehme dann halt nur eines von ggf. mehreren.

Dann bin gestspannt auf Morgen. Auf deine Shell-Lösung und die aus dem Buch, nun wo mir da auch etwas eingefallen ist Vlt. blöd das man nun das Buch kennt, aber ich habe (noch) nicht nachgeschaut.

[inne]

Hola, 00:00 Uhr!

Ich fange mal an, damit meillo nicht sagen kann ich hätte bei ihm irgendwas abgeschrieben

Zuerst viel mir nur dieses Perl ein, weil ich immer das assozative Array im Kopf hatte.
Denke in Listen habe ich mir gesagt, aber besseres bekam ich nicht hin:

Code: Alles auswählen

#!/usr/bin/env perl

my %wordsets;

for ( grep { length == 9 } <STDIN> ) {
    chomp;
    my $key = substr( $_, 2, 4 );
    $wordsets{$key}->{count}++;
    #push( @{ $wordsets{$key}->{words} }, $_ );
}

# Kann man hierfür auch "sort" nutzen?
my $most;
my @keys;
for ( keys(%wordsets) ) {
    if ( $wordsets{$_}->{count} < $most ) {
        next;
    }
    if ( $wordsets{$_}->{count} > $most ) {
        $most = $wordsets{$_}->{count};
        @keys = ();
    }
    push( @keys, $_ );
}

for (@keys) {
    printf( "%s\t%d\t%s\n",
        $_,
        $wordsets{$_}->{count},
        join( " ", @{ $wordsets{$_}->{words} } ) );
}

Doch dann ist mir aber der Knoten für die Shell geplatzt:

Code: Alles auswählen

#!/usr/bin/env sh
sed -n -E '/^.{8}$/s/..(.*)../\1/p' | sort | uniq -c | sort -n

Für das sed/RE will ich meine Hand nicht ins Feuer legen

Code: Alles auswählen

#!/usr/bin/env sh
awk 'length($0)==8{print substr($0,3,4)}' | sort | uniq -c | sort -n \
| tac | awk 'NR==1{most=$1} $1==most{print $0}'

Code: Alles auswählen

#!/bin/sh
egrep '^.{8}$'|cut -c3-6|sort|uniq -c|sort -n|tail

Kürzer fällt mir nichts ein. Ausser das |tail noch weglassen.

Hätte zu Begin nicht gedacht, dass *diese Aufgabe* ein Einzeiler in der Shell wäre ... so trivial wie Du meillo, finde ich das garnicht!
Hoffe habe nun nicht zu große Schnitzer drin.

N8,
inne

[tobo]

Nur mal auf die letzte Lösung jetzt schauend:

Code: Alles auswählen

#!/bin/sh
egrep '^.{8}$'|cut -b3-6|sort|uniq -c|sort -n|tail

Mal abgesehen davon, dass das cut -c3-6 heißen müsste (aber am Fehler nichts ändern würde), macht das cut die Umlaute kaputt:

Code: Alles auswählen

$ egrep '^.{8}$' /usr/share/dict/ngerman | grep "..sche.." | wc -l
77
$ egrep '^.{8}$' /usr/share/dict/ngerman | cut -b3-6 | grep "sche" | wc -l
63

EDIT:
Und wenn man schon keine Datei hartcodiert angeben mag, dann sollte man sie aber zumindest als Parameter angeben, damit auch irgendwas lauffähiges entsteht:

Code: Alles auswählen

#!/bin/sh
egrep '^.{8}$' "$1"|cut -b3-6|sort|uniq -c|sort -n|tail

Oder wüsstest du aus dem Stegreif, wie man bei J eine Datei einbindet?

[hikaru]

Meine Lösung war funktional nahezu identisch zu innes (Ich kenne das Buch nicht.) - mit dem gleichen Fehler:

Code: Alles auswählen

$ egrep '^.{8}$' /usr/share/dict/ngerman | cut -c 3-6 | sort | uniq -c | sort -hk 1 | tail -n 1
     64 chte

Selbstständig erkannt habe ich ihn nicht, da meine Tests auf wamerican liefen.

cut sollte sich durch sed ersetzen lassen:

Code: Alles auswählen

$ egrep '^.{8}$' /usr/share/dict/ngerman | sed 's/..\(....\)../\1/' | sort | uniq -c | sort -hk 1 | tail -n 1
     77 sche

Ich habe das vage Gefühl, dass man das erste sort vielleicht noch loswerden könnte. Stimmt mein Gefühl?

Wir sollten aber noch definieren, was ein achtstelliges Wort ist. Gerade in wamerican gibt es viele Worte mit Apostroph. Wann ist sowas achtstellig (z.B. "zombie's" vs. "zeppelin's")?
(Von Klingonisch gar nicht zu reden (ghay'cha'). )

[inne]

@tobo:
Danke, bei cut hätte ich doch nochmal in die Bescheibung sehen sollen!

Oder wüsstest du aus dem Stegreif, wie man bei J eine Datei einbindet?

./script <path/to/wordlist.text

Aber ich verstehe nicht was du genau meinst, wegen dem J. Ich sehe du hast "$1" ("$@") eingefügt, das dann die Datei als Parameter animmt?

PS: Habe noch das /.{2}/ zu /../ geändert

[tobo]

Oder wüsstest du aus dem Stegreif, wie man bei J eine Datei einbindet?

./script <path/to/wordlist.text

Aber ich verstehe nicht was du genau meinst, wegen dem J. Ich sehe du hast "$1" ("$@") eingefügt, das dann die Datei als Parameter animmt?

PS: Habe noch das /.{2}/ zu /../ geändert

J war nur als Beispiel für dessen Dateihandling gemeint. Ich hielt es für intuitiver eine/die Wörterbuchdatei anzugeben, damit die breite Nachvollziehbarkeit gewährleistet bleibt. Ich habe mir aber gerade sagen lassen, dass das nicht nur nicht stimmt, sondern das Gegenteil davon (deine Herangehensweise der vorgesetzten Pipe oder Eingabeumleitung ist besser) intuitiver ist. Ich nehme also alles zurück und behaupte das Gegenteil...

[eggy]

meine Holzhammermethode:

Code: Alles auswählen

export fund=$(grep "^........$" /usr/share/dict/ngerman | sed "s_^..__" | sed "s_..\$__" | sort  | uniq -c | sort -n | tail -n1 | sed "s_  *_ _"| cut -d " " -f 3); grep "^.."$fund /usr/share/dict/ngerman | grep "^........$" && echo "war wohl: "$fund " (andere treffer ignoriert)"

Ich habs aber nur runtergeschrieben und nichts optimiert ... ich war mehr damit beschäftigt mal zu schauen, ob ich die andere Aufgabe lösen kann. Ich denke, der Autor bezieht sich indirekt auf das Wortproblem, "Simple word problems in universal algebras". Ich würde am ehesten annehmen, er war Student oder jemand der bei den teachning meetings, Sympossien, Konferenzen, etc anwesend war. Steht im Lebenslauf vom Autor, was dass sich mit "The Genesis of Attribute Grammars" in Einklang bringen lässt?

@wanne: Dein egrep bringt bei /usr/share/dict/ngerman 63 sche und 64 chte, mein Code 77 sche

mit awk finde ich ne etwas andere Lösung, aber auch Länge 77

awk.awk:

Code: Alles auswählen

BEGIN {FS = ""
		l1 = 1
		l2 = 1
		oldvorne = ""
		v2 = ""
}
{ 
		vorne = $1 $2 $3 $4
		hinten = $7 $8 $5 $6
		} 

NR==1{ oldvorne = vorne }

{ 
		if (oldvorne == vorne) { liste1[l1++] = hinten; }
		else {
				if (l1 > l2 ){ 
						split("", liste2 ) 
						l2 = 1
	   					for (i in liste1) {liste2[l2++] = liste1[i]}
						v2 = oldvorne
						l1 = 1
						liste1[l1++] = hinten;		
				}
				else {  v1 = ""
						l1 = 1 
						split("", liste1 ) 
						}
				}
		oldvorne = vorne
}

END {	
	   for (i in liste2) {print substr(liste2[i],1,2) " " v2 " " substr(liste2[i],3,2)}
	   print "laenge:" l2 " treffer: " v2
}

Code: Alles auswählen

grep ^........$  /usr/share/dict/ngerman | sed "s_\(^..\)\(.*\)_\2\1_" | sort | awk -f awk.awk

edit: sche 77 kam bei awk raus
Vorteil von Lösung 1: ist einfach nur runtergeschrieben, verschwendete Arbeitszeit gegen null
Vorteil von der awk Lösung: die Datei muss nur einmal gelesen werden, die Anzahl der Arrays bei awk bleibt minimal
aber beides bei dem Spielkram hier nicht weiter wichtig
... und Meillo wird sicher auch wieder was zu meckern finden, was nicht posix passend ist

[Meillo]

Klasse, dass schon so viel Aktivitaet hier ist.


Ich poste mal ein paar Gedanken, die mir bei den bisherigen Posts kommen:

Code: Alles auswählen

sort | uniq -c | sort -n

Das ist ein typisches Konstrukt, fuer immer dann wenn man wissen will, was am haeufigsten vorkommt. Shell-Loesungen werden das fast immer enthalten.

Wenn mich nur das oder die haeufigsten interessieren, dann wuerde ich in Scripten normalerweise `sort -nr' nehmen (um absteigend zu sortieren) und dann von oben runter nur die ersten paar ausgeben. Das ist einfacher als vom Ende her.


Dieses Konstrukt von inne gefaellt mir sehr gut:

Code: Alles auswählen

awk 'NR==1{most=$1} $1==most{print $0}'

D.h. als Alternative zu `head -n1'.


Wie schon erkannt ist `cut -b' bei Text selten sinnvoll. Richtig ist `cut -c' ... wobei das in vielen Implementierungen auch nur Bytes macht und keine Multibyte-Zeichen versteht (wie es das eigentlich sollte). Das ist je nach Implementierung unterschiedlich. (Als ich die Situation 2015 analysiert habe haben nur die Implementierungen von FreeBSD und den Heirloom-Tools, Multibyte-Characters korrekt unterstuetzt.) Da muss man ein bisschen aufpassen.


Dass in den Wordlists auch ``seltsame'' Woerter (also auch konjungierte Formen und so) drin sind ist fuer unsere Aufgabe etwas unguenstig, aber nunja. Das soll nicht gross stoeren.


Ganz nett ist das `-x' Flag bei grep. Folgende zwei Aufrufe sind aequivalent:

Code: Alles auswählen

grep '^........$'
grep -x '........'

Hier meine Loesung von gestern:

Code: Alles auswählen

sed -n 's/^..\(....\)..$/\1/p' /usr/share/dict/ngerman | sort | uniq -c | sort -nr | cut -c9- | sed q

Straight-forward:
- Mittelteil der 8-buchstabigen Woerter ausgeben
- sortieren
- zaehlen
- nach Haeufigkeit sortieren
- Zahl wegschneiden
- nur den ersten Eintrag

Nun mit innes Code um bei Gleichheit alle gleich haeufigen auszugeben:

Code: Alles auswählen

sed -n 's/^..\(....\)..$/\1/p' /usr/share/dict/ngerman | sort | uniq -c | sort -nr | awk 'NR==1{m=$1} $1==m{print $2}'

(Eigentlich hatte ich statt dem awk am Ende zuerst ja `cut -c9-' stehen, um die Anzahl wegzuschneiden. Aber als ich in POSIX geschaut habe, musste ich feststellen, dass uniq-Implementierungen sich hier nicht an POSIX halten, nachdem die Ausgabe der Form "%d %s" entsprechen sollte und nicht etwa der Form "% 7d %s" (GNU uniq 8.13) oder "% 4d %s" (uniq in FreeBSD).)

[hikaru]

Wenn mich nur das oder die haeufigsten interessieren, dann wuerde ich in Scripten normalerweise `sort -nr' nehmen (um absteigend zu sortieren) und dann von oben runter nur die ersten paar ausgeben. Das ist einfacher als vom Ende her.

Wir hatten das so ähnlich schon mal in fischigs Systemd-Paketsuch-Thread:
Ob die Sortierung aufsteigend oder absteigend ist halte ich für unerheblich. Die Eine ist genauso leserlich wie das Andere. Sie muss nur klar sein. Wenn dann die zusätzliche Anforderung kommt, die kürzeste Lösung zu liefern, dann ist sort -r | head schlechter als sort | tail.

Dieses Konstrukt von inne gefaellt mir sehr gut:

Code: Alles auswählen

awk 'NR==1{most=$1} $1==most{print $0}'

D.h. als Alternative zu `head -n1'.

Warum? Es ist deutlich länger und ich meine auch schwerer lesbar als head.

Ganz nett ist das `-x' Flag bei grep. Folgende zwei Aufrufe sind aequivalent:

Code: Alles auswählen

grep '^........$'
grep -x '........'

-x ist aber länger.

Straight-forward:
- Mittelteil der 8-buchstabigen Woerter ausgeben
- sortieren
- zaehlen
- nach Haeufigkeit sortieren
- Zahl wegschneiden
- nur den ersten Eintrag

Meine Vermutung war, dass die Eingangswörterliste in diesem Spezialfall bereits sortiert ist, weshalb das erste sort unnötig sein sollte. In der Praxis einsetzen würde ich es trotzdem, aber wen nach der kürzesten Lösung gefragt ist, wird dieses Detail relevant. Offenbar war meine Annahme falsch. Warum?
Ob "Zahl wegschneiden" Teil der Aufgabe ist, war für mich nicht eindeutig.

[Meillo]

Wenn mich nur das oder die haeufigsten interessieren, dann wuerde ich in Scripten normalerweise `sort -nr' nehmen (um absteigend zu sortieren) und dann von oben runter nur die ersten paar ausgeben. Das ist einfacher als vom Ende her.

Wir hatten das so ähnlich schon mal in fischigs Systemd-Paketsuch-Thread:
Ob die Sortierung aufsteigend oder absteigend ist halte ich für unerheblich. Die Eine ist genauso leserlich wie das Andere. Sie muss nur klar sein. Wenn dann die zusätzliche Anforderung kommt, die kürzeste Lösung zu liefern, dann ist sort -r | head schlechter als sort | tail.

Wenn man nicht nur das eine erste haben will, sondern wenn mehrere gleich oft vorkommen, dann geht das nur mit absteigender Sortierung (einfach). Wenn man die Ausgabe weiterverarbeiten will, dann ist es meist sinnvoll, die relevanten Werte zu Beginn zu haben. (Das ist meine Erfahrung.)

Dieses Konstrukt von inne gefaellt mir sehr gut:

Code: Alles auswählen

awk 'NR==1{most=$1} $1==most{print $0}'

D.h. als Alternative zu `head -n1'.

Warum? Es ist deutlich länger und ich meine auch schwerer lesbar als head.

Es macht etwas anderes, `head -n1' nimmt nur stur die erste Zeile. Der awk-Code nimmt alle Zeilen vom Anfang, bei denen das erste Feld gleich ist, d.h. wenn mehrere gleich haeufig sind, gibt es alle aus.

``Alternative'' war ein schlechter Begriff von mir. Gemeint habe ich, dass man das Konstrukt an die Stelle von `head -n1' setzt. Im Fall von nur einem am oeftesten vorkommenden Mittelteil tut es das Gleiche. Wenn aber mehrere gleich oft vorkommen, verhaelt es sich anders.

Ganz nett ist das `-x' Flag bei grep. Folgende zwei Aufrufe sind aequivalent:

Code: Alles auswählen

grep '^........$'
grep -x '........'

-x ist aber länger.

Da hast du recht. ... Ich wollte nur etwas Werbung fuer `grep -x' machen, weil das Flag eher wenig bekannt ist, manchmal aber ganz nett ist. (U.a. kann es fuer Einsteiger einfacher sein als die Zeilenanker.)

Straight-forward:
- Mittelteil der 8-buchstabigen Woerter ausgeben
- sortieren
- zaehlen
- nach Haeufigkeit sortieren
- Zahl wegschneiden
- nur den ersten Eintrag

Meine Vermutung war, dass die Eingangswörterliste in diesem Spezialfall bereits sortiert ist, weshalb das erste sort unnötig sein sollte. In der Praxis einsetzen würde ich es trotzdem, aber wen nach der kürzesten Lösung gefragt ist, wird dieses Detail relevant. Offenbar war meine Annahme falsch. Warum?

Es muss deshalb sortiert werden, weil zwar moeglicherweise die Wortliste sortiert war, aber es die Mittelteile damit nicht auch sind. Z.B.:

Code: Alles auswählen

aaxxxxaa
aayyyyaa
bbxxxxbb

Das ergibt dann:

Code: Alles auswählen

xxxx
yyyy
xxxx

Und daraus macht `uniq -c' dann:

Code: Alles auswählen

1 xxxx
1 yyyy
1 xxxx

... wenn man sie nicht nochmal sortiert. Das sort sortiert ja nur die extrahierten Mittelteile und nicht die urspruengliche Wortliste.

Man kann sich merken, dass vor `uniq' fast immer sortiert werden muss. Jedenfalls ist es in meiner Praxis sehr selten, dass ich davor mal nicht sortieren will.

Ob "Zahl wegschneiden" Teil der Aufgabe ist, war für mich nicht eindeutig.

Es war ja insgesamt sehr offen wie die Ausgabe ueberhaupt aussehen soll.

Erstmal kann man ja einfach nur den haeufigsten Mittelteil ausgeben. Davon zu den Woerten zu kommen ist nicht allzu schwer (der Mittelteil steckt in $m):

Code: Alles auswählen

grep -x ..$m.. /usr/share/dict/ngerman

Fuer die ganz harten Quoteing-Vermeider und Kurzcode-Schreiber gerne auch so:

Code: Alles auswählen

grep ^..$m..$ /usr/share/dics/ngerman

(Ihr koennt euch ja mal klar machen, warum das so funktioniert.)

Bzw. fuer den Fall mehrerer haeufigster Mittelteile, falls man sie in eine Liste zusammenfassen will, z.B. in dieser Weise:

Code: Alles auswählen

... | sed 's,.*,..&..,' | grep -x -f- /usr/share/dict/ngerman

[eggy]

ich hab grade übrigens noch nen Grund gefunden, der für "Abgabe Sonntagabend" spricht: man kann "live" mitlesen und direkt nachfragen und steht nicht am nächsten Morgen vor drei Seiten unverständlichen Lösungen, bei denen man gar nicht weiß, wo man zuerst fragen soll ... ich nehm einfach mal an, hier lesen mehr Leute gegen 18:00 mit als nachts um 4

[eggy]

ich hab mich nochmal mit uniq beschäftigt, aber irgendwie passt da was nicht

Code: Alles auswählen

grep "^........$" /usr/share/dict/ngerman | sort -k1.3 | uniq -s 2 -c -w 4 | sort -n

41 bebendem - also 41 bend
kann mir jemand erklären, was ich da übersehe?

[JTH]

und steht nicht am nächsten Morgen vor drei Seiten unverständlichen Lösungen

Der letzte Beitrag heute Nacht stammt von einem gewissen „eggy“, da könntest du dich beschweren

von eggy » Heute 02:24

Interessant, welche Interpretationen der Aufgabe und Ansätze ihr schon habt

Ich hab mir als Aufgabe genommen, einfach die gesuchte Teilmenge eines Dictionaries auszugeben, also eine lange Reihe Wörter. (Die Anzahl der Wörter kann man ja immer leicht mit einem angehängten | wc -l bekommen und den ermittelten Wortmittelteil sieht man hoffenlich auf den ersten Blick.) Meine Ausgaben sind also einfach solche:

Code: Alles auswählen

Abscheus
Anschein
[…]
zischend
zischest

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)"

Manche Stellen würde ich da normalerweise ausführlicher schreiben, aber ums kurz zu halten … Flexibel aufzurufen etwa so (die zweite Lösung genauso):

Code: Alles auswählen

$ ./max_word_set_same_inner_chars_awk 8 3 6 /usr/share/dict/ngerman

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"

Ist leider Bash-spezifisch, da mir $(echo "$w" | cut -c"$2-$3"), statt ${w:$I:$N}, in Schleife dann doch zu langsam war und, wie ihr schon angemerkt habt, anscheinend nicht multibyte-fähig. Eigentlich sollte das eine möglichst reine Shell-Lösung werden, die Subshell in der vorletzten Zeile zum Ermitteln der längsten Datei stört mich da etwas.

[eggy]

Der letzte Beitrag heute Nacht stammt von einem gewissen „eggy“, da könntest du dich beschweren

Ja, das ist der allerschlimmste von dieser komischen Scriptingfutzigang

[Meillo]

ich hab mich nochmal mit uniq beschäftigt, aber irgendwie passt da was nicht

Code: Alles auswählen

grep "^........$" /usr/share/dict/ngerman | sort -k1.3 | uniq -s 2 -c -w 4 | sort -n

41 bebendem - also 41 bend
kann mir jemand erklären, was ich da übersehe?

Dein sort stimmt nicht. Es muss so aussehen:

Code: Alles auswählen

sort  -k1.2,1.6

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

Die Idee mit dem selektiven Sortieren und dem selektiven Uniq finde ich cool! Das schafft es dann tatsaechlich in einem Dateidurchlauf, die Liste der Woerter auszugeben. Man muss die Ausgabe dann nur noch abbrechen wenn sich der Mittelteil zum ersten Mal aendert. Das sollte mit awk kein Problem sein.

Nur fuer den Fall, dass es mehrere gleiche haeufig auftretende Mittelteile gaebe, muesste man etwas mehr awk-Logik hinten anhaengen.

[tobo]

ich hab mich nochmal mit uniq beschäftigt, aber irgendwie passt da was nicht

Code: Alles auswählen

grep "^........$" /usr/share/dict/ngerman | sort -k1.3 | uniq -s 2 -c -w 4 | sort -n

41 bebendem - also 41 bend
kann mir jemand erklären, was ich da übersehe?

Ich denke, dass du die 2 übersprungenen Zeichen zu den Gesamtzeichen hinzuzählen musst. Zumindest kommen hier 77 zusammen:

Code: Alles auswählen

grep "^........$" /usr/share/dict/ngerman | sort -k1.3 | uniq -s 2 -c -w 6 | sort -n | grep " [^ ][^ ]sche"

Zu deinem awk-Code sind mir 2 Sachen aufgefallen: Die Anzahl der Treffer ist eins zu hoch. Aufgefallen ist mir das bei deinem 2 Fehler, den ich nämlich auch gemacht habe. Nämlich wenn der häufigste Treffer am Ende der Datei steht und somit das Dateiende aber nicht die Abfrage stattfindet. Beispieldatei dafür:

Code: Alles auswählen

11aaaa11
22bbbb22
22bbbb22
yyzzzzyy
yyzzzzyy
yyzzzzyy
yyzzzzyy
yyzzzzyy
yyzzzzyy
yyzzzzyy
yyzzzzyy

ergibt:

Code: Alles auswählen

$ grep ^........$  t.txt | sed "s_\(^..\)\(.*\)_\2\1_" | sort | awk -f awk.awk
22 bbbb 22
22 bbbb 22
laenge:3 treffer: bbbb