Odległość Hamminga między dwoma strunami o równej długości jest liczbą pozycji, w których odpowiadające znaki są różne. Jeśli struny nie są równej długości, odległość Hamminga nie jest zdefiniowana.

Wyzwanie

Napisz program lub funkcję, która znajdzie największą odległość Hamminga spośród wszystkich par ciągów z listy ciągów, wypełnionych zgodnie z wymaganiami zgodnie z zasadami opisanymi poniżej.

Postacie będą z wewnątrz a-zA-Z0-9.

Ciągi mogą nie być równej długości, więc dla każdego porównania krótszy ciąg musi być wypełniony w następujący sposób:

• owiń ciąg od początku tyle razy, ile potrzeba, aby dopasować wymaganą długość
• zmieniaj wielkość liter każdego owijania nieparzystego (1, 3, 5 itd.)
• pozostawiając rzeczy na zewnątrz a-zA-Zbez zmian podczas pakowania

Załóżmy na przykład, że musisz ab9Cduzupełnić ciąg 5 znaków, aby kończył się 18 znakami. Skończyłbyś z:

ab9CdAB9cDab9CdAB9
     ^^^^^     ^^^

z ^dodanym pod 1. i 3. owinięciem, aby podkreślić zmiany wielkości liter.

Wejście wyjście

Format wejścia / wyjścia jest elastyczny. Możesz założyć, że dane wejściowe mają co najmniej dwa ciągi i że wszystkie ciągi będą miały co najmniej jeden znak.

Dane wyjściowe to liczba całkowita.

Zasady

To jest golf golfowy . Obowiązują standardowe zasady.

Przypadki testowe

[ "a", "b" ] => 1
[ "a", "b", "c" ] => 1
[ "a", "a", "c" ] => 1
[ "abc", "abcd" ] => 1
[ "abc12D5", "abC34d3", "ABC14dabc23DAbC89d"] => 17  
[ "a", "Aaa", "AaaA", "aAaAa", "aaaaaaaaaaaaaa", "AAaAA", "aAa" ] => 8
["AacaAc", "Aab"] => 2

Realizacja referencyjna

Testowałem przykłady z (całkowicie nie golfowym) kodem R, który możesz wypróbować tutaj, aby porównać inne przykłady, które możesz wypróbować ze swoim kodem.

Galaretka , 20 bajtów

Nie bardzo z tego zadowolony. Powinno być możliwe do gry w golfa, nawet do ~ 15 bajtów.

LÞŒcµṁ/sḢL$ŒsÐeFn)§Ṁ

Wypróbuj online!

lub Sprawdź zestaw testowy!

Wyjaśnienie

LÞŒcµṁ / sḢL $ ŒsÐeFn) §Ṁ Pełny program lub łącze monadyczne. N = wejście. | Przykład: [„abc12D5”, „abC34d3”, „ABC14dabc23DAbC89d”]
LÞ Sortuj N według długości. | [[„a”, „b”, „c”, „1”, „2”, „D”, „5”], [„a”, „b”, „C”, „3”, „4 „,” d ”,„ 3 ”], [„ A ”,„ B ”,„ C ”,„ 1 ”,„ 4 ”,„ d ”,„ a ”,„ b ”,„ c ”,„ 2 ”,„ 3 ”,„ D ”,„ A ”,„ b ”,„ C ”,„ 8 ”,„ 9 ”,„ d ”]] (w galaretce ciągi znaków to lista znaków)
  Œc Pary nieuporządkowane: [x, y] dla wszystkich różnych x, y w N. | [[[„a”, „b”, „c”, „1”, „2”, „D”, „5”], [„a”, „b”, „C”, „3”, „ 4 ”,„ d ”,„ 3 ”]], [[„ a ”,„ b ”,„ c ”,„ 1 ”,„ 2 ”,„ D ”,„ 5 ”], [„ A ”,„ B ”,„ C ”,„ 1 ”,„ 4 ”,„ d ”,„ a ”,„ b ”,„ c ”,„ 2 ”,„ 3 ”,„ D ”,„ A ”,„ b ” , „C”, „8”, „9”, „d”]], [[„a”, „b”, „C”, „3”, „4”, „d”, „3”], [„A”, „B”, „C”, „1”, „4”, „d”, „a”, „b”, „c”, „2”, „3”, „D”,
                        Tutaj, wyraźnie, mam na myśli różne pozycje. |
    µ) Mapa z linkiem monadycznym. |
     ṁ / Mold x jak y. To znaczy, cykl x, aż osiągnie długość y. | [[„a”, „b”, „c”, „1”, „2”, „D”, „5”], [„a”, „b”, „c”, „1”, „2 ”,„ D ”,„ 5 ”,„ a ”,„ b ”,„ c ”,„ 1 ”,„ 2 ”,„ D ”,„ 5 ”,„ a ”,„ b ”,„ c ”, „1”], [„a”, „b”, „C”, „3”, „4”, „d”, „3”, „a”, „b”, „C”, „3”, „4”, „d”, „3”, „a”, „b”, „C”, „3”]]
       sḢL $ Podziel na kawałki o długości x. | [[[„a”, „b”, „c”, „1”, „2”, „D”, „5”]], [[„a”, „b”, „c”, „1” , „2”, „D”, „5”], [„a”, „b”, „c”, „1”, „2”, „D”, „5”], [„a”, „ b ”,„ c ”,„ 1 ”]], [[„ a ”,„ b ”,„ C ”,„ 3 ”,„ 4 ”,„ d ”,„ 3 ”], [„ a ”,„ b ”,„ C ”,„ 3 ”,„ 4 ”,„ d ”,„ 3 ”], [„ a ”,„ b ”,„ C ”,„ 3 ”]]]
           SwsÐe Zamiana wielkości na parzyste indeksy (1 indeksowane). | [[[„a”, „b”, „c”, „1”, „2”, „D”, „5”]], [[„a”, „b”, „c”, „1” , „2”, „D”, „5”], [„A”, „B”, „C”, „1”, „2”, „d”, „5”], [„a”, „ b ”,„ c ”,„ 1 ”]], [[„ a ”,„ b ”,„ C ”,„ 3 ”,„ 4 ”,„ d ”,„ 3 ”], [„ A ”,„ B ”,„ c ”,„ 3 ”,„ 4 ”,„ D ”,„ 3 ”], [„ a ”,„ b ”,„ C ”,„ 3 ”]]]
               F Spłaszcz. | [[„a”, „b”, „c”, „1”, „2”, „D”, „5”], [„a”, „b”, „c”, „1”, „2 ”,„ D ”,„ 5 ”,„ A ”,„ B ”,„ C ”,„ 1 ”,„ 2 ”,„ d ”,„ 5 ”,„ a ”,„ b ”,„ c ”, „1”], [„a”, „b”, „C”, „3”, „4”, „d”, „3”, „A”, „B”, „c”, „3”, „4”, „D”, „3”, „a”, „b”, „C”, „3”]]
                n Wektoryzowana nierówność zy. | [[[0, 0, 1, 1, 1, 1, 1]], [[1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 1]], [[1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]]]
                  § Po zakończeniu mapy zsumuj każdą tablicę bool (0 lub 1). | [[5], [17], [14]]
                   Ṁ Maksymalnie. | 17

Python 2 , 86 bajtów

lambda a:max(sum(x!=y for x,y in zip((s+s.swapcase())*len(t),t))for s in a for t in a)

Wypróbuj online!

Podane dwa ciągi, s,t, zip((s+s.swapcase())*len(t),t))będzie to lista krotek o długości len(t)od zipskraca do najkrótszych iterable. Jeśli len(s)<len(t), to „padnie” sprzy żądanej zamianie wielkości liter i obliczamy sumróżne znaki.

Jeśli len(t)<=len(s), to wynik sumbędzie mniejszy lub równy, sumjeśli oceniamy t,s; więc nie ma to wpływu na wynik maxw takim przypadku.

JavaScript (Node.js) , 111 bajtów

a=>a.map(m=S=>a.map(s=>B(S).map((c,k)=>m=(c^(c=B(s)[k%(l=s.length)])^(k/l&c>9)<<5&&++x)<m?m:x,x=0)),B=Buffer)|m

Wypróbuj online!

Galaretka , 19 bajtów

WṁŒsÐeF=ċ0
LÞŒcç/€Ṁ

Wypróbuj online!

LÞŒcç/€Ṁ
LÞ         Sort by length
  Œc       unordered pairs
      €    to each of the pairs
    ç/     find the hamming distance with molding and swapping case (helper link)
       Ṁ   maximum

WṁŒsÐeF=ċ0
W            wrap the shorter string
 ṁ           repeat this string once for each character in the second string
    Ðe       for every other repeated string
  Œs         swap case
      F      flatten
       =     characterwise equality check between the two strings. If the first
             string is longer, the leftover characters are appended to the result.
             e.g. 'abABab' and 'xbA' give [0,1,1,'B','a','b']
        ċ0   count the number of 0s, giving the Hamming distance.

Rubin , 89 82 bajtów

Tworzy iloczyn krzyżowy listy wejściowej względem siebie przed obliczeniem odległości Hamminga dla każdej pary, przy użyciu metody duplikacji podobnej do Chasa Browna . Ruby nie może jednak skompresować razem łańcuchów znaków ani dodać wartości logicznych bez dodatkowego obciążenia, dlatego konieczne jest ręczne iterowanie pary łańcuchów.

-7 bajtów z GB.

->a{a.product(a).map{|s,t|(0...w=t.size).count{|i|(s+s.swapcase)[i%w]!=t[i]}}.max}

Wypróbuj online!

Java 10 ,748 740 667 666 616 bajtów

To musi być najgęstszy i nieczytelny, a jednocześnie najdłuższy golf, jaki kiedykolwiek wymyśliłem.

Metoda wywołania h(String[])z jawną tablicą (bez zmiennych argumentów): np.

h(new String[] {"a", "b", "c"});

zwraca 1.

char e(boolean w,char c){return(char)(w&(64<c&c<91|96<c&c<123)?c^32:c);}String p(String s,int l){var p="";int m=s.length(),n=l/m,r=l%m,i=0,j=0;var w=1<0;for(;i<n;++i,w=!w)for(char c:s.toCharArray())p+=e(w,c);for(;j<r;)p+=e(w,s.charAt(j++));return p;}int d(String s,String t){int l=s.length(),n=0,i=0;for(;i<l;)if(s.charAt(i)!=t.charAt(i++))++n;return n;}int h(String s,String t){int l=s.length(),m=t.length();return l>m?d(s,p(t,l)):l<m?d(p(s,m),t):d(s,t);}int h(String[]s){int l=s.length,i=0,j;int[]n=new int[l*l];for(;i<l;++i)for(j=i;++j<l;)n[i*l+j]=h(s[i],s[j]);return java.util.Arrays.stream(n).max().getAsInt();}

Możesz wypróbować online !

Nie golfił i skomentował:

// Encode the character (swap case)
char e(boolean w, char c) {
    return (char) (w & (64 < c & c < 91 | 96 < c & c < 123) ? c ^ 32 : c);
}

// Pad the string to desired length
String p(String s, int l) {
    var p = "";
    int m = s.length(), n = l / m, r = l % m, i = 0, j = 0;
    var w = 1 < 0;
    for (; i < n; ++i, w = !w)
        for (char c : s.toCharArray())
            p += e(w, c);
    for (; j < r;)
        p += e(w, s.charAt(j++));
    return p;
}

// Calculate the actual hamming distance between two same-length strings
int d(String s, String t) {
    int l = s.length(), n = 0, i = 0;
    for (; i < l;)
        if (s.charAt(i) != t.charAt(i++))
            ++n;
    return n;
}
// Pad the strings as needed and return their hamming distance
int h(String s, String t) {
    int l = s.length(), m = t.length();
    return l > m ? d(s, p(t, l)) : l < m ? d(p(s, m), t) : d(s, t);
}

    // Dispatch the strings and gather their hamming distances, return the max
int h(String[] s) {
    int l = s.length, i = 0, j;
    int[] n = new int[l * l];
    for (; i < l; ++i)
        for (j = i; ++j < l;)
            n[i * l + j] = h(s[i], s[j]);
    return java.util.Arrays.stream(n).max().getAsInt();
}

Ja wiem, lepszym rozwiązaniem może być osiągnięty, zwłaszcza dla części ciąg parowania.

EDYCJA : ogol 8 bajtów, zmieniając rozmiar tablicy int hammingDistance()na kwadrat podanej liczby ciągów znaków. Naprawia także ArrayIndexOutOfBoundswyrzucenie w jednym z przypadków testowych.

EDYCJA 2 : Zaoszczędzono 33 bajty dzięki komentarzom Kevina Cruijssena : usunięto deklarację klasy, skrócono nazwy do 1 znaku, zmieniono operatory itp.

EDYCJA 3 : Zapisz 1 bajt i osiągnij wynik zatwierdzony przez szatana, zmieniając metodę z var-arg na tablicę.

EDYCJA 4 : Zaoszczędź kolejne 50 bajtów dzięki Kevin Cruijssen , ponownie: zaktualizuj wersję Java z 8 do 10, aby użyć varsłowa kluczowego, usuniętej StringBuilderinstancji itp.

05AB1E , 33 29 bajtów

Ćü)€é©εćDš«s`g∍}®€¤‚ø€ζ€€Ë_Oà

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Najprawdopodobniej można go zmniejszyć o połowę w liczbie bajtów, ale działa ...

Wyjaśnienie:

Ć           # Enclose the input-list (adding the first item to the end of the list)
            #  i.e. ['ABC1','abcD','abCd32e'] → ['ABC1','abcD','abCd32e','ABC1']
 ü)         # Pair-vectorize each of them
            #  i.e. ['ABC1','abcD','abCd32e','ABC1']
            #   → [['ABC1','abcD'],['abcD','abCd32e'],['abCd32e','ABC1']]
   ێ       # Sort each pair by length
            #  i.e. [['ABC1','abcD'],['abcD','abCd32e'],['abCd32e','ABC1']]
            #   → [['ABC1','abcD'],['abcD','abCd32e'],['ABC1','abCd32e']]
     ©      # Store this list in the register to re-use later on
ε        }  # Map each inner list in this list to:
 ć          # Head extracted
            #  i.e. ['abcD','abCd32e'] → 'abcD' and ['abCd32e']
  Dš        # Duplicate it, and swap the capitalization of the copy
            #  i.e. 'abcD' → 'ABCd'
    «       # Then merge it together
            #  i.e. 'abcD' and 'ABCd' → 'abcDABCd'
     s`     # Swap so the tail-list is at the top of the stack, and get it's single item
            #  i.e. ['abCd32e'] → 'abCd32e'
       g    # Get the length of that
            #  i.e. 'abCd32e' → 7
        ∍   # Extend/shorten the string to that length
            #  i.e. 'abcDABCd' and 7 → 'abcDABC'
®           # Get the saved list from the register again
 €¤         # Get the tail from each
            #  i.e. [['ABC1','abcD'],['abcD','abCd32e'],['abCd32e','ABC1']]
            #   → ['abcD','abCd32e','abCd32e']
   ‚        # Pair it with the other list
            #  i.e. ['ABC1','abcDABC','ABC1abc'] and ['abcD','abCd32e','abCd32e']
            #   → [['ABC1','abcDABC','ABC1abc'],['abcD','abCd32e','abCd32e']]
    ø       # Zip it, swapping rows / columns
            #  i.e. [['ABC1','abcDABC','ABC1abc'],['abcD','abCd32e','abCd32e']]
            #   → [['ABC1','abcD'],['abcDABC','abCd32e'],['ABC1abc','abCd32e']]
     €ζ     # And then zip each pair again
            #  i.e. [['ABC1','abcD'],['abcDABC','abCd32e'],['ABC1abc','abCd32e']]
            #   → [['Aa','Bb','Cc','1D'],['aa','bb','cC','Dd','A3','B2','Ce'],['Aa','Bb','CC','1d','a3','b2','ce']]
€           # Then for each inner list
 €          #  And for each inner string
  Ë         #   Check if all characters are the same
            #    i.e. 'aa' → 1
            #    i.e. 'cC' → 0
   _        # And inverse the booleans
            #  i.e. [['Aa','Bb','Cc','1D'],['aa','bb','cC','Dd','A3','B2','Ce'],['Aa','Bb','CC','1d','a3','b2','ce']]
            #   → [[1,1,1,1],[0,0,1,1,1,1,1],[1,1,0,1,1,1,1]]
O           # Then sum each inner list
            #  i.e. [[1,1,1,1],[0,0,1,1,1,1,1],[1,1,0,1,1,1,1]] → [4,5,6]
 à          # And take the max as result
            #  i.e. [4,5,6] → 6

Java 11, 387 bajtów

a->{int l=a.length,i=l,t,j=0,C[]=new int[l];var p=new String[l][2];for(;i-->0;p[i][0]=a[t>0?i:j],p[i][1]=a[t>0?j:i])t=a[i].length()<a[j=-~i%l].length()?1:0;i=0;for(var P:p){var s="";for(var x:P[0].getBytes())s+=(char)(x>64&x<91|x>96&x<123?x^32:x);for(P[0]=repeat(P[0]+s,t=P[1].length()).substring(0,t);t-->0;)if(P[0].charAt(t)!=P[1].charAt(t))C[i]++;i++;}for(int c:C)j=c>j?c:j;return j;}

Wypróbuj online. (UWAGA: Ponieważ Java 11 nie jest jeszcze w TIO, String.repeat(int)został emulowany jak repeat(String,int)dla tej samej liczby bajtów.)

Wyjaśnienie:

a->{                      // Method with String-array parameter and integer return-type
  int l=a.length,         //  Length of the input-array
      i=l,                //  Index-integer, starting at the length
      t,j=0,              //  Temp-integers
      C[]=new int[l];     //  Count-array the same size as the input
  var p=new String[l][2]; //  String-pairs array the same size as the input
  for(;i-->0              //  Loop `i` in the range [`l`, 0)
      ;                   //    After every iteration:
       p[i][0]=           //     Set the first String of the pair at index `i` to:
               a[t>0?i:j],//      The smallest of the `i`'th or `j`'th Strings of the input-array
       p[i][1]=           //     And set the second String of the pair at index `i` to:
               a[t>0?j:i])//      The largest of the `i`'th or `j`'th Strings of the input-array
    t=a[i].length()<      //    If the length of the `i`'th item is smaller than
      a[j=-~i%l].length()?//    the length of the `i+1`'th item
                          //    (and set `j` to this `i+1` with wrap-around to 0 for the last item
       1                  //     Set `t` to 1 as flag
      :                   //    Else:
       0;                 //     Set `t` to 0 as flag
                          //  We've now created the String pairs, where each pair is sorted by length
  i=0;                    //  Reset `i` to 0
  for(var P:p){           //  Loop over the pairs
    var s="";             //   Temp-String starting empty
    for(var x:P[0].getBytes())
                          //   Loop over the characters of the first String of the pair
      s+=                 //    Append the temp-String with:
         (char)(x>64&x<91|x>96&x<123?
                         //      If the current character is a letter:
           x^32          //       Swap it's case before appending it to `s`
         :               //      Else (not a letter):
          x);            //       Append it to `s` as is
    for(P[0]=            //    Now replace the first String with:
        repeat(P[0]+s,   //     The first String appended with the case-swapped first String
               t=P[1].length())
                         //     Repeated `t` amount of times,
                         //     where `t` is the length of the second String of the pair
        .substring(0,t); //     And then shorten it to length `t`
        t-->0;)          //    Inner loop over the character of the now same-length Pairs
      if(P[0].charAt(t)!=P[1].charAt(t))
                         //     If the characters at the same indices in the pair are not equal
        C[i]++;          //      Increase the counter for this pair by 1
    i++;}                //    After every iteration of the outer loop,
                         //    increase `i` by 1 for the next iteration
  for(int c:C)           //  Now loop over the calculated counts
    j=c>j?c:j;           //   And set `j` to the maximum
  return j;}             //  And finally return this maximum `j` as result

R 173 bajtów

function(x,U=utf8ToInt,N=nchar)max(combn(x,2,function(z,v=z[order(N(z))])sum(U(substr(Reduce(paste0,rep(c(v[1],chartr('A-Za-z','a-zA-Z',v[1])),n<-N(v[2]))),1,n))!=U(v[2]))))

Wypróbuj online!

@ngm: Starałem się jak najlepiej zagrać w twój kod ( oczywiście z dużymi modyfikacjami), ale, jak dobrze wiesz, R nie jest zbyt golfistą w manipulowaniu ciągami: P