Wejście:

Dwa ciągi bez znaków nowej linii i białych znaków.

Wynik:

Oba ciągi wejściowe w oddzielnych wierszach, w razie potrzeby ze spacjami ^† dla jednego z dwóch ciągów. Oraz trzecią linię z postaci A, R, Mi , reprezentujący dodane , usunięte , zmodyfikowane i niezmienione .

^† Dodajemy spacje do górnego lub dolnego ciągu wejściowego (jeśli musimy). Celem tego wyzwania jest uzyskanie ARMmożliwie najmniejszej liczby zmian ( ), znanych również jako odległość Levenshteina .

Przykład:

Powiedzmy, że ciągi wejściowe ABCDEFi AFBECD, następnie wyjście byłoby to:

A B CDEF
AFBECD  
 A A  RR

Oto kilka innych możliwych nieprawidłowych danych wyjściowych jako przykład (i jest o wiele więcej):

ABCDEF
AFBECD
 MMMMM

A BCDEF
AFBECD 
 A MMMR

AB CDEF
AFBECD 
 MAMMMR

ABC DEF
AFBECD 
 MMAMMR

ABC  DEF
AFBECD  
 MMAA RR

ABCDEF 
AFB ECD
 MMR MA

 AB CDEF   // This doesn't make much sense,
AFBECD     // but it's to show leading spaces are also allowed
AM A  RR

Żadna z nich nie ma jednak tylko czterech zmian, więc A B CDEF\nAFBECD \n A A RRjest to tylko poprawny wynik dla tego wyzwania.

Zasady konkursu:

• Możesz założyć, że ciągi wejściowe nie będą zawierać żadnych nowych wierszy ani spacji.
• Dwa ciągi wejściowe mogą mieć różne długości.
• Jeden z dwóch ciągów wejściowych powinien pozostać bez zmian, z wyjątkiem opcjonalnych spacji początkowych / końcowych.
• Jeśli twoje języki nie obsługują niczego oprócz ASCII, możesz założyć, że dane wejściowe będą zawierały tylko drukowalne znaki ASCII.
• Format wejściowy i wyjściowy są elastyczne. Możesz mieć trzy oddzielne ciągi, tablicę ciągów, pojedynczy ciąg znaków z nowymi wierszami, tablicę znaków 2D itp.
• Możesz użyć czegoś innego zamiast ARM, ale określ, czego użyłeś (tj. 123Lub abc., itd.)
• Jeśli możliwe jest więcej niż jedno prawidłowe wyjście z taką samą ilością zmian ( ARM), możesz wybrać, czy chcesz wypisać jedno z możliwych wyników, czy wszystkie.

• Wiodące i końcowe spacje są opcjonalne:

  A B CDEF
  AFBECD
   A A  RR
  

  lub

  "A B CDEF\nAFBECD\n A A  RR"
                   ^
                   Note there are no spaces here
  

Główne zasady:

• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.
  Nie pozwól, aby języki gry w golfa zniechęcały Cię do publikowania odpowiedzi w językach niekodujących golfa. Spróbuj znaleźć możliwie najkrótszą odpowiedź na „dowolny” język programowania.
• Do odpowiedzi odnoszą się standardowe reguły , więc możesz używać STDIN / STDOUT, funkcji / metody z odpowiednimi parametrami, pełnych programów. Twoja decyzja.
• Domyślne luki są zabronione.
• Jeśli to możliwe, dodaj link z testem swojego kodu.
• W razie potrzeby dodaj również wyjaśnienie.

Przypadki testowe:

In: "ABCDEF" & "AFBECD"

Output (4 changes):
A B CDEF
AFBECD  
 A A  RR                  

In: "This_is_an_example_text" & "This_is_a_test_as_example"

Possible output (13 changes):
This_is_an       _example_text
This_is_a_test_as_example     
         MAAAAAAA        RRRRR

In: "AaAaABBbBBcCcCc" & "abcABCabcABC"

Possible output (10 changes):
AaAaABBbBBcCcCc
 abcABCab cABC 
R MM  MMMR MM R

In: "intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}" & "intf(){intr=(int)(Math.random()*10);returnr>0?r%2:2;}"

Possible output (60 changes):
intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}
intf(){i ntr=(      i    n      t)(M  ath.r   andom        ()*         10          );returnr>0?r%2:2;}
       MR M  MRRRRRR RRRR RRRRRR MMMRR MMMMRRR     RRRRRRRR  MRRRRRRRRR  RRRRRRRRRR 

In: "ABCDEF" & "XABCDF"

Output (2 changes):
 ABCDEF
XABCD F 
A    R 

In: "abC" & "ABC"

Output (2 changes):
abC
ABC
MM 

Haskell , 192 181 174 161 158 150 147 143 158 ¹ bajtów

e@(a:r)&f@(b:s)=snd$maximum[([1|' '<-s!!2],s)|s<-z(z(:))[a:" R",' ':b:"A",a:b:last("M":[" "|a==b])][r&f,e&s,r&s]]
x&y=[x,y,"RA"!!(0^length x)<$x++y]
z=zipWith

Wypróbuj online! Przykładowe zastosowania: "ABCDEF" & "AFBECD". Zwraca listę trzech ciągów. Jest to rozszerzenie mojego rekurencyjnego rozwiązania na zwykłe pytanie dystansowe Levenshteina .

Wyjaśnienie:

Aby obliczyć minimalne modyfikacje do przejścia od "xyz"do "yw", skupiamy się na pierwszym znaku obu ciągów. Istnieją trzy możliwości:

• Usuń: upuść xz pierwszego ciągu i rekurencyjnie oblicz modyfikacje, aby uzyskać od "yz"do "yw". To daje trzy linie ["yz","yw"," M"]. Dodaj xdo pierwszego, spację do drugiego i Rdo trzeciego. Dostajemy

  xyz
  yw
  RM

• Dodaj: Usuń yz drugiego ciągu i oblicz "xyz" & "w", co zwróci wynik ["xyz","w","MRR"]. Musimy dodać spację w pierwszym wierszu, yw drugim i Atrzecim wierszu:

   xyz
  yw
  AMRR

• Zmodyfikowany / Niezmieniony: Możemy łączyć te dwie sprawy, ponieważ oba wymagają spadnie pierwszy znak obu ciągów i obliczyć minimalne zmiany między pozostałych strun: "yz" & "w". Do wyniku ["yz","w","MR"]dodajemy xon pierwszy i ydrugi wiersz. Tylko w ostatnim wierszu musimy rozróżnić, czy początkowe znaki są takie same. Jeśli są takie same, spacja jest dodawana do trzeciego wiersza, w przeciwnym razie (jak w tym przypadku, ponieważ x \= y) Mdodaje się:

  xyz
  yw
  MMR

Spośród tych trzech kandydatów musimy znaleźć tę z najmniejszą liczbą modyfikacji. Jest to równoważne z posiadaniem największej liczby spacji w trzeciej linii. Dlatego konwertujemy każdego kandydata s(listę trzech ciągów) na krotkę ([1|' '<-s!!2],s), gdzie spojawia się jako drugi składnik, a pierwszy składnik jest listą z tyloma elementami, ile jest spacji w trzecim wierszu s(z s!!2powodu indeksowania 0). Ponieważ 1używany jest element listy , ale rzeczywisty element nie ma znaczenia, o ile jest taki sam dla wszystkich kandydatów.

W sumie daje to listę krotek

[([1], [„xyz”, „yw”, „RM”]), ([], [„xyz”, „yw”, „AMRR”]), ([], [„xyz”, „ yw ”,„ MMR ”])]

_{¹ +15 bajtów, aby naprawić błąd, w którym A-changes na końcu łańcucha byłyby wyświetlane jako R-changes}

JavaScript (ES6), 413 ... 343 342 bajtów

Zaoszczędzono 5 bajtów, modyfikując indeksy pętli, jak sugeruje @KevinCruijssen

Pobiera dane wejściowe jako 2 ciągi w składni curry. Zwraca tablicę 3 ciągów znaków.

b=>a=>{m=[];x=a.length;y=b.length;for(i=j=0,c=d='';i<=y;c+=R='R')m[i]=[[c,i++]];for(;j++<x;)m[i=0][j]=[d+=A='A',j];for(;i<y;i++)for(j=0;j<x;)[C]=m[[X,S]=m[i][j],[Y,I]=m[i+1][j],[Z,D]=m[i][++j],Q=[Z+R,D+1],i+1][j]=b[i]==a[j-1]?[X+' ',S]:S<I?D<S?Q:[X+'M',S+1]:D<I?Q:[Y+A,I+1];return[(g=s=>C.replace(/./g,c=>c==s?' ':b[i++],i=0))(A),g(R,b=a),C]}

Przypadki testowe

let f =

b=>a=>{m=[];x=a.length;y=b.length;for(i=j=0,c=d='';i<=y;c+=R='R')m[i]=[[c,i++]];for(;j++<x;)m[i=0][j]=[d+=A='A',j];for(;i<y;i++)for(j=0;j<x;)[C]=m[[X,S]=m[i][j],[Y,I]=m[i+1][j],[Z,D]=m[i][++j],Q=[Z+R,D+1],i+1][j]=b[i]==a[j-1]?[X+' ',S]:S<I?D<S?Q:[X+'M',S+1]:D<I?Q:[Y+A,I+1];return[(g=s=>C.replace(/./g,c=>c==s?' ':b[i++],i=0))(A),g(R,b=a),C]}

console.log(f('ABCDEF')('AFBECD').join`\n`);
console.log(f('This_is_an       _example_text')('This_is_a_test_as_example').join`\n`);
console.log(f('AaAaABBbBBcCcCc')('abcABCabcABC').join`\n`);
console.log(f("intf(){longr=java.util.concurrent.ThreadLocalRandom.current().nextLong(10000000000L);returnr>0?r%2:2;}")("intf(){intr=(int)(Math.random()*10);returnr>0?r%2:2;}").join`\n`);
console.log(f('ABCDEF')('XABCDF').join`\n`);

Mniej golfa

b => a => {
  m = []; x = a.length; y = b.length;

  // initialize the leftmost column and the topmost row
  for(i = j = 0, c = d = ''; i <= y; c += R = 'R')
    m[i] = [[c, i++]];
  for(; j++ < x;)
    m[i = 0][j] = [d += A = 'A', j];

  // walk through the Levenshtein matrix
  for(; i < y; i++)
    for(j = 0; j < x;)
      [C] = m[                                // C = current string, once updated
        [X, S] = m[i][j],                     // substitution
        [Y, I] = m[i + 1][j],                 // insertion
        [Z, D] = m[i][++j],                   // deletion
        Q = [Z + R, D + 1],                   // precomputed update for deletion
        i + 1
      ][j] =
        b[i] == a[j - 1] ?
          [X + ' ', S]                        // unchanged character
        :
          S < I ?
            D < S ? Q : [X + 'M', S + 1]      // deletion or substitution
          :
            D < I ? Q : [Y + A, I + 1];       // deletion or insertion

  return [
    // g = helper function to format the output strings by inserting spaces
    (g = s => C.replace(/./g, c => c == s ? ' ' : b[i++], i = 0))(A),
    g(R, b = a),

    // final modification string, picked from the last visited cell
    C
  ]
}

Przykład

Poniżej znajduje się początkowa macierz dla b = „foo” i a = „ok” :

//                     'o'           'k'
[ [ [ '',    0 ], [ 'A',   1 ], [ 'AA',  2 ] ],
  [ [ 'R',   1 ],  (undefined),  (undefined) ],  // 'f'
  [ [ 'RR',  2 ],  (undefined),  (undefined) ],  // 'o'
  [ [ 'RRR', 3 ],  (undefined),  (undefined) ] ] // 'o'

a oto ostatnia macierz po wszystkich iteracjach:

//                     'o'           'k'
[ [ [ '',    0 ], [ 'A',   1 ], [ 'AA',  2 ] ],
  [ [ 'R',   1 ], [ 'M',   1 ], [ 'MA',  2 ] ],  // 'f'
  [ [ 'RR',  2 ], [ 'R ',  1 ], [ 'R A', 2 ] ],  // 'o'
  [ [ 'RRR', 3 ], [ 'RR ', 2 ], [ 'R M', 2 ] ] ] // 'o'

Ostateczny ciąg modyfikacji wraz z odległością Levenshteina są przechowywane w prawej dolnej komórce.

Python 2 , 548 536 484 500 ¹ 488 447 381 ² 373 371 357 350 bajtów

s,t=input()
n,m=len(s),len(t)
r=range
L=[[(j,'RA'[i<1]*j)for j in r(i,m-~i)]for i in r(n+1)]
for i in r(n):
 for j in r(m):M,R=L[i][j:j+2];A=L[i+1][j];v,V=min(A,R,M);x=('AR'[v in R],'M_'[s[i]==t[j]])[v in M];_=M;X=eval(x)[1]+x;L[i+1][j+1]=v+(x<'_'),X
for i in r(len(X)):s=s[:i]+' '*('B'>X[i])+s[i:];t=t[:i]+' '*('R'==X[i])+t[i:]
print s+'\n'+t+'\n'+X

Wypróbuj online!

Używa 'ARM_'zamiast'ARM '

Działa, budując matrycę Levenshteina, a następnie przechodząc do tyłu, aby znaleźć operacje . Teraz buduje ciąg operacji w tym samym czasie, co macierz Levenshteina, jak w odpowiedzi JS Arnaulda

_{1: Więcej bajtów, ponieważ nie działało, jeśli pierwszy ciąg był jednym znakiem.}

_{2: Przełączono na tworzenie kombinacji w matrycy Levenshteina.}

Python 2 , 310 bajtów

from difflib import*
a,b=input()
U,j=[],' '
for g,s,t,x,y in SequenceMatcher(0,a,b).get_opcodes():
	g,Y,T=g[0],y-x,t-s
	z,A,B=Y-T,a[s:t],b[x:y]
	if'q'<g:U+=[A+z*j,B+j*-z,'M'*min(T,Y)+'A'*z+'R'*-z]
	if'e'==g:U+=[A,B,j*Y]
	if'i'==g:U+=[j*Y,B,'A'*Y]
	if'e'>g:U+=[A,j*T,'R'*T]
for e in[0,1,2]:print''.join(U[e::3])

Wypróbuj online!

Zastosowanie difflib.SequenceMatchertego oblicza wyrównanie między dwoma łańcuchami

Mathematica, 250 256 259 384 bajty

~ 0,00035 sekund w przypadku kodu Java.

(i=o=p="";a=Array;r=StringLength;If[Length@#>0,g=#&@@#;h=#[[2]];u=r@g;v=r@h;i=i<>g;o=o<>h;w=Abs[v-u];k=a[" "&,w];If[u<v,i=i<>k,o=o<>k];p=p<>a["M"&,u~Min~v];p=p<>a[If[u>v,"R","A"]&,w],i=i<>#;o=o<>#;p=p<>a[" "&,r@#]]&/@SequenceAlignment[#,#2];{i,o,p})&

Stosowanie: f["ABCDE", "ABCDF"]

Wypróbuj online!

Kod oparty jest na fakcie, że SequenceAlignmentdziała domyślnie na

Przy ustawieniu domyślnym SimilarityRules-> Automatic, każde dopasowanie między dwoma elementami przyczynia się 1 do całkowitego wyniku podobieństwa, a każde niedopasowanie, wstawienie lub usunięcie przyczynia się do -1.

Mianowicie, punktacja jest obliczana M, Ai R, odpowiednio.

Przykład:

D , 351 345 bajtów

-6 bajtów dzięki dla KevinCruijssen

string f(string a,string b){import std.algorithm;string x,y,z;size_t i,j,k;foreach(c;levenshteinDistanceAndPath(a,b)[1]){final switch(c)with(EditOp){case none:x~=a[i++];y~=b[j++];z~=" ";break;case substitute:x~=a[i++];y~=b[j++];z~="M";break;case insert:x~=" ";y~=b[j++];z~="A";break;case remove:x~=a[i++];y~=" ";z~="R";}}return x~"\n"~y~"\n"~z;}

Wypróbuj online!