Расстояние Хэмминга между двумя строками одинаковой длины - это количество позиций, в которых соответствующие символы различны. Если строки не имеют одинаковую длину, расстояние Хэмминга не определяется.

Вызов

Напишите программу или функцию, которая находит наибольшее расстояние Хэмминга среди всех пар строк из списка строк, дополненных согласно требованиям, описанным ниже.

Персонажи будут изнутри a-zA-Z0-9.

Строки не могут быть равными по длине, поэтому для каждого сравнения более короткая строка должна быть дополнена следующим образом:

• оберните строку с начала столько раз, сколько необходимо, чтобы соответствовать требуемой длине
• меняйте регистры букв каждый раз за нечетное время (1, 3, 5 и т. д.)
• оставить вещи a-zA-Zбез изменений при упаковке

Например, допустим, вам нужно добавить 5-символьную строку, ab9Cdчтобы она заканчивалась 18 символами. Вы бы в конечном итоге с:

ab9CdAB9cDab9CdAB9
     ^^^^^     ^^^

с ^добавленными под 1 и 3 обертками, чтобы выделить изменения в регистре.

Ввод, вывод

Формат ввода / вывода гибкий. Можно предположить, что на входе есть как минимум две строки, и что все строки будут иметь хотя бы один символ.

Вывод является целым числом.

правила

Это код-гольф . Стандартные правила применяются.

Контрольные примеры

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

Ссылочная реализация

Я проверил примеры с (совершенно не загнанным) R-кодом, который вы можете попробовать здесь, чтобы сравнить любые другие примеры, которые вы можете попробовать с вашим кодом.

Желе , 20 байт

Не очень доволен этим. Должно быть пригодным для игры в гольф, возможно, даже до ~ 15 байт.

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

Попробуйте онлайн!

или проверить набор тестов!

объяснение

LÞŒcµṁ / sḢL $ ŒsÐeFn) §Ṁ Полная программа или монадическая ссылка. N = вход. | Пример: ["abc12D5", "abC34d3", "ABC14dabc23DAbC89d"]
Сортировка N по длине. | [['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 ']] (в Jelly строки представляют собой список символов)
  Unc Неупорядоченные пары: [x, y] для всех различных x, y в 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',
                        Здесь под разным я имею в виду разные позиции. |
    µ) Карта с монадической ссылкой. |
     Mold / Плесень х, как у. То есть цикл 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»]]
       sḢL $ Разбить на куски длины х. | [[['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 Поменяйте местами чётно-индексированные чанки (1-индексированные). | [[['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 Flatten. | [['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 Векторизованное неравенство с y. | [[[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, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]]]
                  § После окончания карты, суммируйте каждый массив bool (0 или 1). | [[5], [17], [14]]
                   Ṁ максимум. | 17

Python 2 , 86 байт

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)

Попробуйте онлайн!

Даны две строки, s,t, zip((s+s.swapcase())*len(t),t))будет список кортежей длины , len(t)так как zipУсекает кратчайшее итерацию. Если len(s)<len(t), то это «дополняет» sнужным регистром, и мы вычисляем sumразличные символы.

Если len(t)<=len(s), то результат sumбудет меньше или равен, sumесли мы оценивали t,s; так что это не влияет на результат maxв этом случае.

JavaScript (Node.js) , 111 байт

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

Попробуйте онлайн!

Желе , 19 байт

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

Попробуйте онлайн!

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.

Рубин , 89 82 байта

Создает перекрестное произведение списка входных данных против себя перед вычислением расстояния Хэмминга каждой пары, используя метод дублирования, аналогичный ответу Часа Брауна . Тем не менее, Ruby не может объединять строки в цепочку или добавлять логические значения без дополнительных затрат, поэтому вместо этого возникает необходимость перебирать пару строк вручную.

-7 байт из ГБ.

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

Попробуйте онлайн!

Java 10 ,+748 740 667 666 616 байт

Это должен быть самый плотный и нечитаемый, но самый длинный гольф, который я когда-либо придумывал.

Вызовите метод h(String[])с явным массивом (без аргументов var): например,

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

возвращается 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();}

Вы можете попробовать это онлайн !

Развернулся и прокомментировал:

// 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();
}

Я знаю, что лучшее решение может быть достигнуто, особенно в части сопряжения строк.

РЕДАКТИРОВАТЬ : сбрить 8 байтов, изменив размер массива int hammingDistance()на квадрат числа заданных строк. Это также исправляет ArrayIndexOutOfBoundsбросок в одном из тестовых случаев.

РЕДАКТИРОВАТЬ 2 : Сохранено 33 байта благодаря комментариям Кевина Круйссена : удалено объявление класса, сокращены имена до 1 символа, изменены операторы и т. Д.

РЕДАКТИРОВАТЬ 3 : Сохранить 1 байт и достичь оценки, утвержденной сатаной, изменив метод с помощью var-arg в массив.

РЕДАКТИРОВАТЬ 4 : Сохраните еще 50 байтов благодаря Кевину Круйссену , снова: обновите версию Java с 8 до 10, чтобы использовать varключевое слово, удаленный StringBuilderэкземпляр и т. Д.

05AB1E , 33 29 байт

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

Попробуйте онлайн или проверьте все контрольные примеры .

Скорее всего, можно уменьшить число байтов вдвое, но это работает ..

Объяснение:

Ć           # 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 байт

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;}

Попробуйте онлайн. (ПРИМЕЧАНИЕ. Поскольку Java 11 еще не включена в TIO, String.repeat(int)она была эмулирована с repeat(String,int)тем же счетчиком байтов.)

Объяснение:

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 байта

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

Попробуйте онлайн!

@ngm: Я старался изо всех сил сыграть в твой код ( конечно, с моими тяжелыми настройками), но, как ты хорошо знаешь, R не очень хорош в манипулировании строками: P