Trouvez le motif optimal

33

Étant donné une chaîne s composé de lettres minuscules, telles que

aabaaababbbbaaba

et un nombre entier positif n , tel que 4, une sortie longueur - n chaîne t de telle sorte que lorsque t est répété à la longueur de s , ils ont autant de caractères communs que possible. Pour l'exemple donné, la sortie optimale serait aaba, car elle a treize caractères en commun avec la chaîne cible:

s: aabaaababbbbaaba
t: aabaaabaaabaaaba (aaba)
   ^^^^^^^^  ^ ^^^^

et pas possible t a plus. Cependant, pour aaaaaab, il existe deux sorties possibles: aaaaet aaba, qui ont chacune 6 caractères en commun avec la chaîne cible:

s: aaaaaab
t: aaaaaaaa (aaaa)
   ^^^^^^ 

s: aaaaaab
t: aabaaaba (aaba)
   ^^ ^^^^

Soit aaaaou aabapeut être sorti, ou les deux si vous le souhaitez. Notez que s n'est jamais répété; la fin adans les deux valeurs répétées de t est simplement ignorée.

Cas de test

Inputs -> Valid outputs
1 a -> a
1 aa -> a
2 aa -> aa
1 ab -> a b
2 ab -> ab
1 abb -> b
2 abb -> ab bb
2 ababa -> ab
2 abcba -> ab
2 aabbbbb -> bb  (ab is not a valid output here)
3 aababba -> aab abb
3 aababbaa -> aab
3 asdasfadf -> asf
3 asdasfadfsdf -> asf adf
2 abcdefghijklmnopqrstuvwxyzyx -> yx
2 supercalifragilisticexpialidocious -> ic ii
3 supercalifragilisticexpialidocious -> iri ili ioi
4 supercalifragilisticexpialidocious -> scii
5 supercalifragilisticexpialidocious -> iapic
2 eeeebaadbaecaebbbbbebbbbeecacebdccaecadbbbaceebedbbbddadebeddedbcedeaadcabdeccceccaeaadbbaecbbcbcbea -> bb be
10 bbbbacacbcedecdbbbdebdaedcecdabcebddbdcecebbeeaacdebdbebaebcecddadeeedbbdbbaeaaeebbedbeeaeedadeecbcd -> ebbbdbeece ebdbdbeece
20 aabbbaaabaaabaaaabbbbabbbbabbbabbbbbabbaaaababbbaababbbaababaaaabbaaabbaabbbabaaabbabbaaabbaaaaaaaba -> aabbbbaaabbabbbaabba

Règles

  • Vous pouvez supposer que l'entrée ne sera jamais qu'une chaîne non vide de lettres minuscules et un entier positif non supérieur à la longueur de la chaîne.
  • Vous pouvez prendre les entrées dans n'importe quel format standard et dans n'importe quel ordre.
  • Vous pouvez sortir une seule chaîne, ou plusieurs chaînes sous la forme d'un tableau, séparées par des lignes ou des espaces, etc.
  • Votre code doit être terminé pour chaque cas de test en moins d'une minute sur un ordinateur assez moderne.
  • C'est du , alors faites en sorte que votre code soit le plus court possible.
ETHproductions
la source
2
Ce défi est de qualité Zgarb. Bon travail!
Martin Ender
Je suppose que seuls les caractères de fin sont ignorés? Donc, vous n'êtes pas autorisé à ignorer les caractères principaux de la manière suivante: 2 abb -> baoù il est construit sous la forme suivante (b)[ab]a: l'index (b)est ignoré, [ab]correspond.
Kevin Cruijssen
@KevinCruijssen Oui, le motif doit commencer à se répéter au début.
ETHproductions

Réponses:

11

Gelée , 11 octets

sZµṢŒrUṀṪµ€

Essayez-le en ligne!

Je ne m'attendais pas à battre Dennis sur celui-ci, alors j'ai essayé de le fGITW (après avoir essayé plusieurs possibilités, il y a plus d'une façon de faire 11). Je suis venu plus court, à ma grande surprise.

Prend la chaîne puis le compte en tant qu'arguments de ligne de commande. Sorties sur stdout.

Explication

sZµṢŒrUṀṪµ€
s            Split {the first input} into {the second input}-sized groups
 Z           Transpose
  µ      µ€  On each of the transposed groups:
   Ṣ           Sort it;
    Œr         Run-length encode it;
      U        Rearrange it to the form {count, letter};
       Ṁ       Take the largest element (i.e. largest count)
        Ṫ      Take the second element of the pair (i.e. just the letter)

Ceci utilise l'idée que la lettre dans chaque position du motif doit être la lettre la plus commune correspondant à cette position. Nous pouvons trouver les lettres correspondant à un motif particulier en les divisant en groupes de la taille d’un motif et en les transposant. La raison principale pour laquelle cette solution est si longue est que Jelly ne semble pas avoir le chemin court pour trouver le mode d’une liste (j’ai fait plusieurs tentatives, mais elles ont toutes au moins six octets de long).

Jelly , 10 octets, basé sur la solution de @Dennis

⁸ċ$ÞṪ
sZÇ€

Essayez-le en ligne!

Ceci est une combinaison de la solution de @Dennis et de la mienne; il y avait un mode cinq octets dans cette solution, que j'ai volé pour cette solution. (J'avais déjà des solutions basées sur ⁸ċ, mais je ne pouvais pas descendre en dessous de six octets; je n'avais pas pensé à utiliser Þ.)

Explication

µ…µ€et Ç€(avec le sur la ligne précédente) ont tous deux une longueur de trois octets (la dernière nécessite une nouvelle ligne) et leur équivalent. Normalement, j'utilise le premier, mais le dernier est plus flexible, car cela vous permet de mentionner l'argument.

Cela permet de trier ( Þ) par le nombre d'occurrences dans ( ⁸ċ), puis de prendre le dernier élément ( ), pour trouver le mode en cinq caractères seulement.


la source
5
Beau boulot sur Dennis avec son propre langage! : P
HyperNeutrino
10

Mathematica, 51 octets

#&@@@Commonest/@(PadRight@Partition[#2,UpTo@#])&

L'entrée et la sortie sont des listes de caractères.

Également basé sur les modes des lignes de la transposition. Je crois qu'ils ont appelé le mode intégré pour le mode d'une liste Commonest uniquement pour les golfeurs de code dépit.

Martin Ender
la source
Au moins, c'est un octet plus court que MostCommon...
ETHproductions
7

Python 3, 99, 73 61 octets

-12, merci à @Rod

lambda s,n:''.join(max(s,key=s[i::n].count)for i in range(n))

Même idée, mais réécrit pour éliminer l'instruction d'importation.

lambda s,n:''.join(max(s,key=lambda c:s[i::n].count(c))for i in range(n))

Original

from collections import*
lambda s,n:''.join(Counter(s[i::n]).most_common(1)[0][0]for i in range(n))

Explication:

s[i::n]                  a slice of every nth character of s, starting at position i

Counter(s[i::n])         counts the characters in the slice
  .most_common()         returns a list of (character, count) pairs, sorted by decreasing count
    [0][0]               grabs the letter from the first pair (i.e., the most common letter
      for i in range(n)  repeat for all starting positions

''.join                  combines the most common letters into a single string
RootTwo
la source
vous pouvez passer à python2.7 et laisser tomber le ''.join()pour retourner une liste de chaînes
Rod
@Rod Dropping ''.join(...)renverrait un générateur, ne sachant pas si cela est autorisé.
L3viathan
@ L3viathan, il doit être python2.7 pour fonctionner, ajouté à l'autre commentaire
Rod
Pouvez-vous écrire une explication de la façon dont cela fonctionne?
Dead Possum
2
@Rod Une liste de chaînes n'est autorisée dans la question que si vous renvoyez toutes les solutions possibles. C'est ce que j'ai compris.
mbomb007
5

Python 2, 106

Maintenant, c'est une réponse différente! Je pensais à un (presque) -liner du début. Maintenant encore plus court, basé sur l'utilisation du zip par @Rod.

Merci à @ L3viathan et @Rod pour des éclaircissements sur l’utilisation de lambdas comme réponse

Essayez-le en ligne

lambda S,N:max(combinations(S,N),key=lambda s:sum(x==y for x,y in zip(S,s*len(S))))
from itertools import*

Explication:

combinations(S,N) crée toutes les combinaisons de longueur N à partir des caractères de S

max()avoir un argument keyqui prend comme fonction d'entrée à utiliser pour comparer des éléments

lambda s:sum(x==y for x,y in zip(S,s*len(S))) passé comme telle fonction

Ce lambda compte le nombre de caractères correspondants dans la liste des tuples, produit par zip(S,s*len(S))

s- une des combinaisons et il est multiplié par len(S)ce qui crée une chaîne garantie plus longtemps que S

zipcrée des nuplets de caractères de chaque chaîne Set s*len(S)ignore tous les caractères qui ne peuvent pas être mis en correspondance (dans le cas d'une chaîne plus longue que l'autre)

Alors maxchoisit la combinaison, qui produit la somme maximale

Mort possum
la source
1
vous n'avez pas besoin d'utiliser la []compréhension de liste à l'intérieur des fonctions, vous utilisez aussi, 1 for ... if <cond>vous pouvez utiliser directement <cond> for ...car il sera utilisé sur sum, python prendra au Truefur 1et à Falsemesure0
Rod
@Rod Merci! Si je répondais davantage à ma réponse, elle se transformerait en votre réponse, l'approche est la même: D J'essaie donc quelque chose de différent en ce moment
Dead Possum
Oui, je vous dis simplement que vous pouvez utiliser vos réponses futures: 3
Rod
1
Passer à un lambda économisera 7 octets.
L3viathan
1
@DeadPossum Il voulait dire cela (notez le pied de page et l'en-tête) et oui, une fonction est une réponse valable . Si c'est un lambda, vous n'avez même pas besoin de laf= (sauf si c'est récursif)
Rod
5

JavaScript (ES6), 104 101 94 octets

(n,s)=>s.replace(/./g,(_,i)=>[...s].map((c,j,a)=>j%n-i||(a[c]=-~a[c])>m&&(m++,r=c),m=r=``)&&r)

Enregistré 3 fois deux fois grâce à @Arnauld. Solution de 97 octets qui fonctionne avec tous les caractères non-newline:

(n,s)=>s.replace(/./g,(_,i)=>[...s].map((c,j)=>j%n-i||(o[c]=-~o[c])>m&&(m++,r=c),m=r=``,o={})&&r)

La solution précédente de 104 octets fonctionne également avec les caractères de nouvelle ligne:

(n,s)=>[...Array(n)].map((_,i)=>[...s].map((c,j)=>j%n-i||(o[c]=-~o[c])>m&&(m++,r=c),m=0,o={})&&r).join``
Neil
la source
Très agréable. J'ai joué au golf avec une solution de référence lors de l'ajout de scénarios de test et je suis arrivé à 122 octets, en passant en revue chaque caractère, en sauvegardant les comptes dans un tableau d'objets, puis en créant la chaîne à partir de ce tableau.
ETHproductions
Plutôt que d’initialiser oun nouvel objet, pourriez-vous simplement réutiliser le tableau transmis mapen utilisant son troisième paramètre?
Arnauld
@Arnauld Hmm, je suppose que cela fonctionne parce que la question garantit les minuscules, je ne confondre donc pas les éléments du tableau avec les chiffres ...
Neil
Je pense que (n,s)=>s.replace(/./g,(_,i)=>i<n?[...s].map((c,j,a)=>j%n-i||(a[c]=-~a[c])>m&&(m++,r=c),m=0)&&r:'')devrait sauver 3 octets de plus. (Ou 4 octets en utilisant la syntaxe de currying.)
Arnauld
@Arnauld Pas mal, mais je me suis coupé deux octets de plus. (Et j'ai aussi corrigé mes comptages d'octets; une nouvelle ligne les lançait.)
Neil
3

Gelée , 12 à 11 octets

s@ZċþZMḢ$€ị

Essayez-le en ligne!

Comment ça marche

s@ZċþZMḢ$€ị  Main link. Arguments: n (integer), s (string)

s@           Split swapped; split s into chunks of length n.
  Z          Zip/transpose, grouping characters that correspond to repetitions.
   ċþ        Count table; for each slice in the previous result, and each character
             in s, count the occurrences of the character in the group.
             This groups by character.
     Z       Zip/transpose to group by slice.
        $€   Map the two-link chain to the left over the groups.
      M        Find all maximal indices.
       Ḣ       Head; pick the first.
          ị  Index into s to retrieve the corresponding characters.
Dennis
la source
Est-ce que Jelly a des commentaires?
Caird coinheringaahing
Non.
Dennis
2

Pyth, 11 octets

meo/dNd.TcF

Prend les entrées s,net sorties sous forme de liste de caractères.

Explication

meo/dNd.TcF
         cFQ   Split s into chunks of length n.
       .T      Transpose.
m o/dNd        Sort characters in each string by frequency.
 e             Take the most common.

la source
2

Japt , 16 à 15 octets

Enregistré 1 octet grâce à @obarakon

Ç=VëUZ)¬ñ!èZ o

14 octets de code + 1 octet pour le -Pdrapeau. Essayez-le en ligne!

Ungolfed et explication

 Ç   =VëUZ)¬ ñ!èZ o
UoZ{Z=VëUZ)q ñ!èZ o}
                          Implicit: U = input number, V = input string
Uo                        Create the range [0...U).
  Z{               }      Map each item Z by this function:
      VëUZ                  Take every U'th char of V, starting at index Z.
    Z=    )                 Call the result Z.
           q                Split the result into chars.
             ñ!èZ           Sort each char X by the number of occurrences of X in Z.
                  o         Pop; grab the last item (the most common char).
                      -P  Join the results (array of most common chars) into a string.
ETHproductions
la source
Je pense que vous pouvez remplacer gJparo
Oliver
@obarakon C'est du génie, merci!
ETHproductions
1

Python 2 , 132 octets

from itertools import*
p,k=input()
b=l=len(p)
for i in combinations(p,k):
 x=sum(x!=y for x,y in zip(p,i*l))
 if x<b:b,o=x,i
print o

Essayez-le en ligne!

Barre
la source
1

05AB1E , 17 octets

Iôð«øvy{.¡é®èÙJðÜ

Essayez-le en ligne!

Explication

Iô                 # split 2nd input in chunks of 1st input size
  ð«               # append a space to each
    ø              # zip
     vy            # for each y in the zipped list
       {           # sort the string
        .¡         # group into chunks of consecutive equal elements
          é        # sort by length
           ®è      # pop the last element (the longest)
             Ù     # remove duplicate characters from the string
              J    # join the stack into one string
               ðÜ  # remove any trailing spaces
Emigna
la source
1

PHP, 245 octets

function p($c,$s,$r=""){global$a;if(($c-strlen($r)))foreach(str_split(count_chars($s,3))as$l)p($c,$s,$r.$l);else{for($v=str_pad("",$w=strlen($s),$r);$z<$w;)$t+=$v[$z]==$s[$z++];$a[$t][]=$r;}}p($argv[1],$argv[2]);ksort($a);echo join(" ",end($a));

Version en ligne

Panne

function p($c,$s,$r=""){
    global$a;
    if(($c-strlen($r)))  # make permutation
        foreach(str_split(count_chars($s,3))as$l)
            p($c,$s,$r.$l); #recursive
    else{
        for($v=str_pad("",$w=strlen($s),$r);$z<$w;) 
        $t+=$v[$z]==$s[$z++]; #compare strings
        $a[$t][]=$r; # insert value in array
    }
}
p($argv[1],$argv[2]); #start function with the input parameter
ksort($a); # sort result array 
echo join(" ",end($a)); #Output
Jörg Hülsermann
la source
1

Haskell, 84 octets

import Data.Lists
f n=map(argmax=<<(length.).flip(filter.(==))).transpose.chunksOf n

Exemple d'utilisation:

f 10 "bbbbacacbcedecdbbbdebdaedcecdabcebddbdcecebbeeaacdebdbebaebcecddadeeedbbdbbaeaaeebbedbeeaeedadeecbcd"
"ebbbdbeece"

Diviser la chaîne d'entrée en morceaux de longueur n, transposer et rechercher pour chaque sous-liste l'élément le plus fréquent.

nimi
la source