Biorąc pod uwagę listę słów i ich skrótów, wypisz wzór, według którego można tworzyć skróty.

Weźmy przykładowe dane wejściowe

potato ptao
puzzle pzze

jako przykład (to znaczy skrót dla potatois ptao, a skrót dla puzzleis pzze).

Rozważyć wszystkie możliwe sposoby, aby uzyskać ptaood potato. Jednym z możliwych sposobów jest wzięcie pierwszej, trzeciej, czwartej i szóstej litery, które będziemy nazywać 1346. Ale ponieważ ti opojawiają się kilka razy w słowie, istnieje wiele innych możliwych sposobów generowania ptaoz potato: 1546, 1342, i 1542.

Podobnie należy pamiętać, że pzzemogą być generowane puzzlez dowolnego 1336, 1346, 1436, 1446. Jedyny wzór, który łączy te dwa skróty, to 1346; dlatego musi to być wynik dla tego wejścia. Jeśli możliwych jest wiele możliwych wzorców, możesz wypisać dowolny, niektóre lub wszystkie z nich (przynajmniej jeden).

Możesz założyć, że:

• Wprowadzane słowa i skróty zawierają tylko małe litery.

• Na wejściu znajduje się co najmniej jedna para słowo / skrót.

• Możliwe jest utworzenie każdego skrótu z odpowiadającego mu słowa.

• Zawsze będzie istniał co najmniej jeden wzór, który tworzy każdy skrót.

• Maksymalna długość każdego słowa wynosi 9 znaków.

Dane wejściowe można przyjąć jako jedno z poniższych:

• Dwuwymiarowa tablica / lista / tablica krotek / itp. [[word, abbr], [word, abbr], ...]

• płaska 1-wymiarowa tablica / lista [word, abbr, word, abbr, ...]

• pojedynczy ciąg, rozdzielany dowolnym pojedynczym znakiem, który nie jest małą literą "word abbr word abbr"

• skrót / tablica asocjacyjna / itp. {word => abbr, word => abbr, ...}

W każdej z tych opcji wprowadzania danych możesz również zamieniać kolejność słów / abbr (proszę dokładnie opisać format wprowadzania w swoim poście).

Dane wyjściowe mogą być podawane w postaci pojedynczej liczby, ciągu ograniczonego cyframi lub tablicy / listy / krotki / itp. liczb.

Ponieważ jest to code-golf , wygra najkrótszy kod w bajtach.

Przypadki testowe (pamiętaj, że musisz wygenerować wyniki ≥1, jeśli działa wiele wzorców):

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 bajtów

[email protected]

Wypróbuj tutaj!

Pobiera listę w następującym formacie:

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

Alternatywne 17 bajtowe rozwiązanie, które wyświetla wynik jako listę indeksów zerowych, które są zawinięte w 1-elementową listę:

[email protected]

Wyjaśnienie

Przykład: [["potato", "ptao"],["puzzle", "pzze"]]

Najpierw mapujemy każdy znak w skrócie na listę indeksów wszystkich zdarzeń w słowie, które daje

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

Następnie transponujemy tę listę, która nam daje

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

Tak więc indeksy każdego znaku każdego skrótu są razem na jednej liście.

Następnie musimy tylko znaleźć jeden wspólny indeks na wszystkich tych listach, który daje:

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

To jest wynik mojego alternatywnego 17-bajtowego rozwiązania powyżej. Następnie przekształca się w [1,3,4,6].

Podział kodu

[email protected] # Q = wejście

m Wprowadzanie mapy Q # za pomocą d
        edytuj # mapuj każdy skrót za pomocą k
            mbhd # słowo map do listy znaków
         mxk # zamapuj każdy skrót char na listę indeksów
      .T # Transpozycja
    Fd # Złożyć każdy element
   @ # i filtruj według obecności
 hh # Weź pierwszy element wyniku i zwiększ go

MATL , 29 bajtów

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

Dane wejściowe to tablica 2D w następującym formacie:

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

Wypróbuj online! ( połączony kod zawiera pewne modyfikacje wynikające ze zmian w języku od czasu opublikowania tej odpowiedzi )

!       % 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

Kod wymagał pewnych zaangażowanych (i długich!) Sztuczek do

• Zapobiegaj zmianie orientacji wektorów wytwarzanych przez find( f) w zależności od kształtu wejściowego. Są to instrukcje X:wX:: wymuś, aby oba wyjścia były wektorami kolumnowymi.
• Przeciwdziałaj domyślnemu zachowaniu funkcji min( X>) wzdłuż pierwszego wymiaru nie singletonowego . Są to stwierdzenia tv: konkatuj kopię samego siebie, aby zapewnić co najmniej dwa wiersze);

Perl, 46 45 42 bajtów

Obejmuje +1 dla -p

Podaj dane wejściowe jako sekwencyjne słowa w STDIN, np

perl -p abbrev.pl
prgrmming
prgmg
puzzles
pzzlz

Zakończ STDIN za pomocą ^Dlub ^Zcokolwiek jest potrzebne w twoim systemie

abbrev.pl:

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

Wyjaśnienie

Rozważ to wejście (układ koncepcyjny, a nie prawdziwy sposób wprowadzania danych dla tego programu):

potatoes     ptao
puzzle       pzze

Program buduje ciągi znaków reprezentujące pionowe kolumny pełnych ciągów indeksowanych na id kolumny

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

itp. To samo robi dla skrótów, ale używając innego identyfikatora

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

Słowa są domyślnie przetwarzane jeden po drugim za pomocą -popcji. Ciągi kolumn są konstruowane przy użyciu powtarzających się konkatenacji, podczas gdy każde słowo jest używane s#.# ...code.. #eg, więc każda kolumna potrzebuje powtarzalnego identyfikatora. Używam minus numer kolumny, po której następuje numer linii modulo 2. Numer kolumny można skonstruować za pomocą, --$_która zaczyna się jako bieżące słowo, które ze względu na użycie tylko a-zgwarantuje, że będzie oceniane jako 0 w kontekście numerycznym. Więc rozumiem -1, -2, -3, .... Naprawdę wolałbym użyć 1, 2, 3, ..., ale użycie $_++spowoduje wyzwolenie przyrostu magicznego ciągu znaków perla zamiast normalnego licznika numerycznego. I nie chcesz używać$_ a nie jakąkolwiek inną zmienną, ponieważ każdą inną zmienną musiałbym zainicjować do zera w każdej pętli, która zajmuje zbyt wiele bajtów.

Numer wiersza modulo 2 ma zapewnić, że identyfikatory dla pełnego słowa i identyfikatory dla skrótu się nie kolidują. Zauważ, że nie mogę użyć pełnego słowa i skrótu na jednym ciągu, aby numer kolumny przechodził przez połączony ciąg, ponieważ pełne słowa nie mają tej samej długości, więc skrócone kolumny słów nie byłyby ustawione w jednej linii. Nie mogę też umieścić słowa skróconego na pierwszym miejscu (wszystkie mają tę samą długość), ponieważ potrzebuję liczby pierwszych kolumn pełnych słów jako 1.

Nadużywam globalnej przestrzeni nazw Perla przez nieswoiste odniesienie do skonstruowania ciągów kolumn jako:

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

Następnie odwzorowuję każdy ciąg kolumn na pierwszy numer kolumny, w którym ciąg kiedykolwiek się pojawia (mapowanie już wskazane powyżej), ponownie nadużywając globalnej przestrzeni nazw Perla (ale zauważ, że nazwy nie mogą się ze sobą kolidować, więc globale nie będą sobie przeszkadzać):

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

Muszę zanegować, $_ponieważ jak wyjaśniono powyżej, liczę kolumny jako -1, -2, -3, .... ||=Make pewien tylko pierwsze pojawienie się danej kolumnie otrzymuje nowy numer kolumny, w przeciwnym razie poprzedni numer kolumny jest zachowana i zwracane jako wartości. Stanie się tak w szczególności dla każdego słowa skróconego, ponieważ specyfikacja gwarantuje, że w pełnych słowach pojawi się kolumna, która pojawi się wcześniej. Tak więc w ostatnim skróconym słowie każda litera zostanie zastąpiona numerem kolumny w pełnym słowie, która odpowiada kolumnie dla wszystkich słów skróconych. Tak więc wynikiem ostatniej zamiany jest pożądany wynik końcowy. Więc drukuj tylko wtedy, gdy jesteśmy na końcu danych wejściowych:

$_ x=eof

Przypisanie indeksu kolumny spowoduje również utworzenie pozycji dla niekompletnych kolumn, ponieważ kolumna nie jest jeszcze całkowicie zbudowana lub niektóre słowa są krótsze i nie osiągają pełnej długości kolumny. Nie stanowi to problemu, ponieważ kolumny potrzebne w każdym skróconym słowie mają zagwarantowaną kolumnę odpowiadającą pełnemu słowu, która ma maksymalną możliwą długość (liczbę aktualnie widocznych par), więc te dodatkowe wpisy nigdy nie powodują fałszywych dopasowań.

Haskell, 74 bajty

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

Format wejściowy to lista par ciągów znaków, np .:

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

Jak to działa: mapM(tak samo jak sequence . map) najpierw przekształca każdą parę (w,a)w listę list indeksów liter w skrócie ( ' ':naprawia natywny indeks Haskell oparty na 0 na 1), ("potato", "ptao") -> [[1],[3,5],[4],[2,6]]a następnie na listę wszystkich ich kombinacji, gdzie element w miejscu ijest pobierany z ipodlisty, np [[1,3,4,2],[1,3,4,6],[1,5,4,2],[1,5,4,6]]. foldl1 intersectznajduje przecięcie wszystkich takich list list.

ES6, 92 bajty

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

Akceptuje wprowadzanie jako tablicę słów i tablicę skrótów. Zwraca tablicę indeksów opartych na 1 (co kosztuje mnie 2 bajty do cholery). W przypadku wielu rozwiązań zwracane są najwyższe wskaźniki.

Python 3, 210 bajtów

Nie jest to imponująca odpowiedź, która pokazuje tutaj najlepsze wyniki, ale jest to naprawdę jedno z najbardziej szalonych list, jakie kiedykolwiek widziałem w Pythonie. Podejście jest dość proste.

 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]]

Funkcja oczekuje, że dane wejściowe są zawsze w postaci ciągów tablic 2-D, takich jak: [[word, abbr],...]i zwraca listę liczb całkowitych.

Ps: Szczegółowe wyjaśnienie już wkrótce

Ps2: Dalsze sugestie dotyczące gry w golfa są mile widziane!