La distance de Hamming entre deux chaînes de longueur égale est le nombre de positions auxquelles les caractères correspondants sont différents. Si les cordes ne sont pas de longueur égale, la distance de Hamming n'est pas définie.

Défi

Écrivez un programme ou une fonction qui trouve la plus grande distance de Hamming parmi toutes les paires de chaînes d'une liste de chaînes, complétées selon les besoins selon les règles décrites ci-dessous.

Les personnages seront de l'intérieur a-zA-Z0-9.

Les chaînes peuvent ne pas être de longueur égale, donc pour chaque comparaison, la chaîne la plus courte doit être complétée comme suit:

• envelopper la chaîne depuis le début autant de fois que nécessaire pour correspondre à la longueur requise
• changer la casse des lettres à chaque emballage impair (1er, 3e, 5e, etc.)
• laisser les choses à l'extérieur a-zA-Zinchangées lors de l'emballage

Par exemple, disons que vous devez remplir la chaîne de 5 caractères ab9Cdpour qu'elle se termine par 18 caractères. Vous vous retrouveriez avec:

ab9CdAB9cDab9CdAB9
     ^^^^^     ^^^

avec ^ajouté sous les 1er et 3e tours pour mettre en évidence les changements de casse.

Entrée sortie

Le format d'entrée / sortie est flexible. Vous pouvez supposer que l'entrée a au moins deux chaînes et que toutes les chaînes auront au moins un caractère.

La sortie est un entier.

Règles

C'est du code-golf . Des règles standard s'appliquent.

Cas de test

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

Implémentation de référence

J'ai testé les exemples avec du code R (complètement non golfé) que vous pouvez essayer ici pour comparer tous les autres exemples que vous pourriez essayer avec votre code.

Gelée , 20 octets

Pas vraiment content avec ça. Devrait être jouable au golf, même à ~ 15 octets peut-être.

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

Essayez-le en ligne!

ou Découvrez une suite de tests!

Explication

LÞŒcµṁ / sḢL $ ŒsÐeFn) §Ṁ Programme complet ou lien monadique. N = entrée. | Exemple: ["abc12D5", "abC34d3", "ABC14dabc23DAbC89d"]
LÞ Triez N par longueur. | [['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 ']] (dans Jelly, les chaînes sont une liste de caractères)
  Œc Paires non ordonnées: [x, y] pour tous les x, y distincts dans 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»,
                        Ici, par distinct, je veux dire à différentes positions. |
    µ) Carte avec un lien monadique. |
     ṁ / Moule x comme y. Autrement dit, cycle x jusqu'à ce qu'il atteigne la longueur 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 $ Divisé en morceaux de longueur 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Ðe Échangez le cas des morceaux à index pair (1 indexé). | [[['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 Aplatir. | [['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 Inégalité vectorisée avec 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, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]]]
                  § Après avoir terminé la carte, additionnez chaque tableau booléen (0 ou 1). | [[5], [17], [14]]
                   Ṁ Maximum. | 17

Python 2 , 86 octets

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)

Essayez-le en ligne!

Étant donné deux chaînes, s,t, zip((s+s.swapcase())*len(t),t))seront une liste de tuples de longueur len(t)depuis ziptronque à la plus courte itérables. Si len(s)<len(t), alors cela "se remplit" savec le changement de cas souhaité et nous calculons le nombre sumde caractères différents.

Si len(t)<=len(s), alors le résultat sumsera inférieur ou égal au sumsi nous évaluions t,s; il n'a donc aucun effet sur le résultat maxdans ce cas.

JavaScript (Node.js) , 111 octets

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

Essayez-le en ligne!

Gelée , 19 octets

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

Essayez-le en ligne!

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.

Rubis , 89 82 octets

Crée le produit croisé de la liste d'entrée par rapport à lui-même avant de calculer la distance de Hamming de chaque paire, en utilisant une méthode de duplication similaire à la réponse de Chas Brown . Ruby ne peut pas compresser les chaînes ensemble ou ajouter des booléens sans surcharge supplémentaire, cependant, il devient donc nécessaire d'itérer manuellement la paire de chaînes à la place.

-7 octets de Go.

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

Essayez-le en ligne!

Java 10 ,748 740 667 666 616 octets

Ce doit être le golf le plus dense et illisible, mais le plus long que j'aie jamais imaginé.

Méthode d'appel h(String[])avec un tableau explicite (pas d'arguments var): par exemple,

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

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

Vous pouvez l' essayer en ligne !

Non golfé et commenté:

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

Je sais qu'une meilleure solution peut être obtenue, en particulier pour la partie d'appariement de cordes.

EDIT : raser 8 octets en changeant la taille du tableau int hammingDistance()au carré du nombre de chaînes donné. Il corrige également un ArrayIndexOutOfBoundsjet dans l'un des cas de test.

EDIT 2 : 33 octets enregistrés grâce aux commentaires de Kevin Cruijssen : déclaration de classe supprimée, noms raccourcis à 1 caractère, opérateurs modifiés, etc.

EDIT 3 : économisez 1 octet et atteignez le score approuvé par Satan en changeant la méthode avec var-arg en tableau.

EDIT 4 : économisez encore 50 octets grâce à Kevin Cruijssen , encore une fois: mettez à jour la version Java de 8 à 10 pour utiliser le varmot-clé, l' StringBuilderinstance supprimée , etc.

05AB1E , 33 29 octets

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

Essayez-le en ligne ou vérifiez tous les cas de test .

Peut très probablement être divisé par deux en nombre d'octets, mais cela fonctionne.

Explication:

Ć           # 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 octets

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

Essayez-le en ligne. (REMARQUE: Étant donné que Java 11 n'est pas encore sur TIO, il String.repeat(int)a été émulé comme repeat(String,int)pour le même nombre d'octets.)

Explication:

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 octets

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

Essayez-le en ligne!

@ngm: J'ai fait de mon mieux pour jouer à votre code (avec mes personnalisations lourdes bien sûr) mais, comme vous le savez bien, R n'est pas très golfique pour manipuler les cordes: P