Geben Sie bei Eingabe einer Liste von Wörtern und deren Abkürzungen das Muster aus, nach dem die Abkürzungen gebildet werden können.

Nehmen wir die Beispieleingabe von

potato ptao
puzzle pzze

als Beispiel (dh die Abkürzung für potatoist ptaound die Abkürzung für puzzleist pzze).

Betrachten Sie alle möglichen Möglichkeiten, um ptaovon zu erhalten potato. Eine Möglichkeit besteht darin, den ersten, dritten, vierten und sechsten Buchstaben zu verwenden, auf den wir uns beziehen werden 1346. Aber da tund omehrfach im Wort erscheinen, gibt es mehrere andere Möglichkeiten zur Erzeugung ptaovon potato: 1546, 1342, und 1542.

Beachten Sie in ähnlicher Weise, dass mit jedem von pzzegeneriert puzzlewerden kann1336 , 1346, 1436, 1446. Das einzige Muster, das diese beiden Abkürzungen gemeinsam haben, ist 1346: Daher muss dies die Ausgabe für diese Eingabe sein. Wenn mehrere mögliche Muster möglich sind, können Sie eines, einige oder alle (mindestens eines) ausgeben.

Sie können davon ausgehen, dass:

• Eingabewörter und Abkürzungen enthalten nur Kleinbuchstaben.

• Die Eingabe enthält mindestens ein Wort- / Abkürzungspaar.

• Es ist möglich, dass jede Abkürzung aus ihrem entsprechenden Wort gebildet wird.

• Es wird immer mindestens ein Muster geben, das jede Abkürzung bildet.

• Die maximale Länge jedes Wortes beträgt 9 Zeichen.

Die Eingabe kann wie folgt erfolgen:

• 2-dimensionales Array / Liste / Array von Tupeln / etc. [[word, abbr], [word, abbr], ...]

• flaches 1-dimensionales Array / Liste [word, abbr, word, abbr, ...]

• Einzelne Zeichenfolge, die durch ein einzelnes Zeichen begrenzt wird, das kein Kleinbuchstabe ist "word abbr word abbr"

• Hash / Assoziatives Array / etc. {word => abbr, word => abbr, ...}

In jeder dieser Eingabemöglichkeiten können Sie auch die Reihenfolge von Wort / Abkürzung tauschen (beschreiben Sie das Eingabeformat in Ihrem Beitrag vollständig).

Die Ausgabe kann als einzelne Zahl, als durch Nicht-Ziffern begrenzte Zeichenfolge oder als Array / Liste / Tupel / usw. erfolgen. von Zahlen.

Da dies Code-Golf ist , wird der kürzeste Code in Bytes gewinnen.

Testfälle (denken Sie daran, dass Sie nur ≥ 1 Ergebnisse ausgeben müssen, wenn mehrere Muster funktionieren):

In                                Out
--------------------------------------------------------
potato ptao puzzle pzze         | 1346
aabbcc abc fddeef def           | 246
prgrmming prgmg puzzles pzzlz   | 14353
aaaaa a bbbb b ccc c dd d e e   | 1
aaaaa a bbbb b ccc c            | 1, 2, 3
abcxyz zbcyax                   | 623514
abcxyz acbbacbcbacbbac          | 132213232132213
potato ptao                     | 1346, 1546, 1342, 1542
a aaaaa                         | 11111

Pyth, 19 Bytes

[email protected]

Probieren Sie es hier aus!

Erstellt eine Liste im folgenden Format:

[["word","abbr"],["word","abbr"],...]

Alternative 17-Byte-Lösung, die das Ergebnis als Liste von nullbasierten Indizes ausgibt, die in eine 1-Element-Liste eingeschlossen sind:

[email protected]

Erläuterung

Beispiel: [["potato", "ptao"],["puzzle", "pzze"]]

Zuerst ordnen wir jedes Zeichen in der Abkürzung einer Liste der Indizes aller Vorkommen in dem Wort zu, das ergibt

[[[0], [2, 4], [3], [1, 5]], [[0], [2, 3], [2, 3], [5]]]

Dann transponieren wir diese Liste, die uns gibt

[[[0], [0]], [[2, 4], [2, 3]], [[3], [2, 3]], [[1, 5], [5]]]

Somit sind die Indizes jedes Zeichens jeder Abkürzung in einer Liste zusammengefasst.

Dann müssen wir in allen Listen nur einen gemeinsamen Index finden, der ergibt:

[[0], [2], [3], [5]]

Dies ist die Ausgabe meiner alternativen 17-Byte-Lösung oben. Dies wird dann in umgewandelt [1,3,4,6].

Code-Aufschlüsselung

[email protected] # Q = Eingabe

m Q # -Karteneingabe mit d
        m ed # ordne jede Abkürzung mit k zu
            mbhd # map wort zur char liste
         mxk # ordnet jedes Abkürzungszeichen einer Liste von Indizes zu
      .T # Transponieren
    Fd # Falte jedes Element
   @ # und nach Anwesenheit filtern
 hh # Nimm das erste Element des Ergebnisses und erhöhe es

MATL , 29 Bytes

!"@Y:!=2#fX:wX:h]N$v1XQtv4#X>

Die Eingabe ist ein 2D-Array im folgenden Format:

{'potato' 'ptao'; 'puzzle' 'pzze'}

Probieren Sie es online! ( Der verknüpfte Code enthält einige Änderungen aufgrund von Änderungen in der Sprache seit dem Posten dieser Antwort. )

!       % take input. Transpose
"       % for each column
  @Y:   %   push column. Unpack the two strings and push them onto the stack
  !     %   transpose second string
  =     %   matrix with all pairwise matchings of characters in word and abbreviation
  2#f   %   find row and col indices of those matchings
  X:    %   transform into column vector
  wX:   %   swap, transform into column vector
  h     %   concat into a two-col matrix
]       % end for
N$v     % concatenate all matrices containing the indices
1       % push 1
XQ      % build matrix adding 1 for each (row,col) index
tv      % concat vertically with itself, so that it has at least two rows.
        % This forces the following function to work on each col.
4#X>    % arg max of each col: position that produces a match in all pairs.
        % If there are several maximizers in each col this gives the first

Der Code erforderte einige umständliche (und langwierige!) Tricks

• Verhindern Sie, dass sich die Ausrichtung der von find( f) erzeugten Vektoren in Abhängigkeit von der Eingabeform ändert. Dies sind Anweisungen X:wX:: Erzwinge, dass beide Ausgaben Spaltenvektoren sind.
• Entgegenwirken des Standardverhaltens der min( X>) -Funktion "Erste Nicht-Singleton-Dimension bearbeiten" . Hierbei handelt es sich um folgende Anweisungen tv: Eine Kopie von sich selbst zusammenfassen, um mindestens zwei Zeilen zu gewährleisten);

Perl, 46 45 42 Bytes

Beinhaltet +1 für -p

Geben Sie STDIN als aufeinanderfolgende Wörter ein, z

perl -p abbrev.pl
prgrmming
prgmg
puzzles
pzzlz

Beenden Sie STDIN mit ^Doder ^Zoder was auch immer auf Ihrem System benötigt wird

abbrev.pl:

s#.#${${--$_.$.%2}.=$&}||=-$_#eg;$_ x=eof

Erläuterung

Betrachten Sie diese Eingabe (konzeptionelles Layout, nicht die tatsächliche Eingabemethode für dieses Programm):

potatoes     ptao
puzzle       pzze

Das Programm erstellt Zeichenfolgen, die die vertikalen Spalten der vollständigen Zeichenfolgen darstellen, die in einer Spalten-ID indiziert sind

id1    pp     -> 1
id2    ou     -> 2
id3    tz     -> 3
id4    az     -> 4
...

usw. Dies gilt auch für die Abkürzungen, jedoch unter Verwendung einer anderen ID

ID1    pp     -> 1
ID2    tz     -> 3
ID3    az     -> 4
ID4    oe     -> 6

Die Wörter werden implizit einzeln mit der -pOption verarbeitet. Die s#.# ...code.. #egSpaltenfolgen werden unter Verwendung wiederholter Verkettungen erstellt, während jedes Wort durchlaufen wird. Daher benötigt jede Spalte eine wiederholbare ID. Ich verwende minus die Spaltennummer, gefolgt von der Zeilennummer modulo 2. Die Spaltennummer kann so konstruiert werden, --$_dass sie als das aktuelle Wort beginnt, das aufgrund der Verwendung von nur a-zgarantiert als 0 in einem numerischen Kontext ausgewertet wird. Also verstehe ich -1, -2, -3, .... Ich hätte es wirklich gerne benutzt 1, 2, 3, ..., aber mit $_++würde Perl Magic String Increment anstelle eines normalen numerischen Zählers ausgelöst. Ich tue verwenden möchten$_ und nicht irgendeine andere Variable, weil ich jede andere Variable in jeder Schleife, die zu viele Bytes benötigt, auf Null initialisieren müsste.

Die Zeilennummer Modulo 2 soll sicherstellen, dass die IDs für das vollständige Wort und die IDs für die Abkürzung nicht in Konflikt geraten. Beachten Sie, dass ich nicht das vollständige Wort und die Abkürzung für eine Zeichenfolge verwenden kann, um eine Spaltennummer über der kombinierten Zeichenfolge zu haben, da die vollständigen Wörter nicht alle dieselbe Länge haben und die Spalten mit den abgekürzten Wörtern nicht in einer Reihe stehen. Ich kann das abgekürzte Wort auch nicht an die erste Stelle setzen (sie haben alle die gleiche Länge), da die Anzahl der ersten Spalte der vollständigen Wörter 1 sein muss.

Ich missbrauche den globalen Namensraum von Perl durch einen nicht strengen Verweis, um die Spaltenfolgen wie folgt zu konstruieren:

${--$_.$.%2}.=$&

Als Nächstes ordne ich jede Spaltenzeichenfolge der ersten Spaltennummer zu, in der die Zeichenfolge jemals vorkommt (die oben bereits angegebene Zuordnung), indem ich den globalen Perl-Namespace erneut missbrauche (beachte jedoch, dass die Namen nicht kollidieren können, damit sich die globalen Zeichenfolgen nicht gegenseitig stören):

${${--$_.$.%2}.=$&} ||= -$_

Ich muss negieren, $_weil ich, wie oben erklärt, die Spalten als zähle -1, -2, -3, .... Das ||=stellen Sie sicher , nur das erste Auftreten einer bestimmten Spalte erhält eine neue Spaltennummer, andernfalls wird die vorherige Spaltennummer wird beibehalten und als Wert zurückgegeben. Dies geschieht insbesondere für jedes abgekürzte Wort, da die Spezifikation garantiert, dass eine Spalte mit den vollständigen Wörtern vorhanden ist, die zuvor angezeigt wurden. Daher wird im allerletzten abgekürzten Wort jeder Buchstabe durch die Spaltennummer im vollständigen Wort ersetzt, die der Spalte für alle abgekürzten Wörter entspricht. Das Ergebnis der allerletzten Auswechslung ist also das gewünschte Endergebnis. Drucken Sie also genau dann, wenn wir am Ende der Eingabe stehen:

$_ x=eof

Durch die Zuweisung des Spaltenindex werden auch Einträge für unvollständige Spalten erstellt, da die Spalte noch nicht vollständig aufgebaut ist oder einige Wörter kürzer sind und nicht die volle Spaltenlänge erreichen. Dies ist kein Problem, da die Spalten, die in jedem abgekürzten Wort benötigt werden, garantiert eine entsprechende Spalte aus den vollständigen Wörtern haben, die die maximal mögliche Länge (die Anzahl der aktuell gesehenen Paare) hat, so dass diese zusätzlichen Einträge niemals falsche Übereinstimmungen verursachen.

Haskell, 74 Bytes

import Data.List
foldl1 intersect.map(\(w,a)->mapM(`elemIndices`(' ':w))a)

Das Eingabeformat ist eine Liste von Zeichenfolgenpaaren, z.

*Main > foldl1 intersect.map(\(w,a)->mapM(`elemIndices`(' ':w))a)  $ [("potato","ptao"),("puzzle","pzze")]
[[1,3,4,6]]

So funktioniert es: mapM(wie sequence . map) verwandelt zuerst jedes Paar (w,a)in eine Liste von ' ':Indexlisten der Buchstaben in der Abkürzung ( fixiert Haskells nativen 0-basierten Index auf 1-basiert), z. B. ("potato", "ptao") -> [[1],[3,5],[4],[2,6]]und dann in eine Liste aller Kombinationen davon, in denen Das Element an der Position iwird aus der iUnterliste gezogen, z [[1,3,4,2],[1,3,4,6],[1,5,4,2],[1,5,4,6]]. foldl1 intersectFindet den Schnittpunkt all dieser Listen von Listen.

ES6, 92 Bytes

(w,a)=>[...a[0]].map((_,i)=>[...w[0]].reduce((r,_,j)=>w.some((s,k)=>s[j]!=a[k][i])?r:++j,0))

Akzeptiert Eingaben als Array von Wörtern und als Array von Abkürzungen. Gibt ein Array von 1-basierten Indizes zurück (was mich 2 Bytes Dammit kostet). Bei mehreren Lösungen werden die höchsten Indizes zurückgegeben.

Python 3, 210 Bytes

Keine eindrucksvolle Antwort auf die Topscores, aber dies ist wirklich eine der verrücktesten Listen, die ich je mit Python gemacht habe. Der Ansatz ist recht einfach.

 def r(p):
    z=[[[1+t[0]for t in i[0]if l==t[1]]for l in i[1]]for i in[[list(enumerate(w[0])),w[1]]for w in p]]
    return[list(set.intersection(set(e),*[set(i[z[0].index(e)])for i in z[1:]]))[0]for e in z[0]]

Die Funktion erwartet die Eingabe immer als String-2-D-Array wie: [[word, abbr],...]und gibt eine Liste von Ganzzahlen zurück.

Ps: Eine ausführliche Erklärung folgt in Kürze

PS2: Weitere Golfvorschläge sind willkommen!