Quand il s'agit de manger des bonbons, je me tiens à des normes plus élevées que le laïc typique. Il existe un équilibre délicat entre "mélanger" et "conserver le meilleur pour la fin".

Dans ce défi, vous recevrez une chaîne de caractères dans laquelle chaque caractère représente un bonbon. Différents caractères (sensibles à la casse) représentent différents types de bonbons. Votre programme doit ensuite déterminer le bon ordre de consommation de bonbons, en suivant la procédure ci-dessous. Vous pouvez écrire un programme complet (STDIN / STDOUT) ou une fonction nommée pour accomplir cette tâche.

Disons que ma réserve de bonbons est oroybgrbbyrorypoprr. Premièrement, je trie les bonbons en piles du même type, avec de plus grandes quantités en haut, en utilisant des valeurs de caractères ASCII plus faibles comme point de départ.

rrrrrr
oooo
bbb
yyy
pp
g

Ensuite, je prends chaque rangée de bonbons et les espace de manière égale le long d'un intervalle. Par exemple, s'il y a 3 bonbons, l'un est placé à 1/3 du chemin, aux 2/3 du chemin et à la fin.

.r.r.r.r.r.r
..o..o..o..o
...b...b...b
...y...y...y
.....p.....p
...........g

Ensuite, je descends chaque colonne pour créer ma dernière commande de bonbons rorbyroprbyorrobypg.

Contribution

Une chaîne qui contient la réserve de bonbons. L'entrée pour l'exemple ci-dessus aurait pu être:

oroybgrbbyrorypoprr

Sortie

Une chaîne contenant les bonbons réorganisée dans le bon ordre de consommation.

rorbyroprbyorrobypg

Notation

C'est du code golf. La réponse la plus courte en octets l'emporte. Les règles standard de code-golf s'appliquent.

CJam, 78 68 61 45 42 39 31 30 octets

l$:L{L\/,~}${:DM+:MD/,LD/,d/}$

Prend la chaîne d'entrée via STDIN

Inspiré par l'approche récursive, mais un peu différent. Pas besoin de transposer ou de rectangle du tout!.

Comment ça marche:

l$:L                              "Sort the input line and store it in L";
    {     }$                      "Sort the string based on this code block output";
     L\/,~                        "Sort based on number of occurrences of each";
                                  "character in the full string";
            {               }$    "Sort the sorted string again";
             :DM+:M               "Store each character in D, add to M and update M";
                   D/,            "Count occurrences of D in M";
                      LD/,        "Count occurrences of D in L";
                          d/      "Sort string based on the ratio of two occurrences";

(Triste que CJam ne puisse plus utiliser Pyth à cause de la nécessité d'une syntaxe trop lourde)

Essayez-le ici

Pyth , 25

shCoc/NhN/zhNm>o_/zZSzdUz

Utilise un tout nouvel algorithme, inspiré de cette réponse .

(implicit)          z = input()
(implicit)          print
s                   combine list of strings into one string
 h                  first list in
  C                 matrix transpose of (e.g. first characters in first list, etc.)
   o                order_by(lambda N:
    c                        float_div(
     /NhN                              N.count(N[0]),
     /zhN                              z.count(N[0])),
    m                        map(lambda d:
     >                           slice_head(
      o                                     order_by(lambda Z:
       _/zZ                                          -1*z.count(Z),
       Sz                                            sorted(z)),
      d                                     d),
     Uz                          range(len(z))

Pas à pas:

1. Premièrement, nous avons trié les caractères selon leur caractère commun, les liens brisés par ordre alphabétique. C'est o_/zZSz. oest identique à celle de Python sorted(<stuff>,key=<stuff>), avec une expression lambda pour la clé, sauf qu'elle la conserve sous forme de chaîne.

2. Ensuite, nous générons une liste des préfixes de cette chaîne, de longueur len(z)en longueur 1. >est équivalent à celui de python <stuff>[<int>:].

3. Ensuite, nous réorganisons cette liste de chaînes de préfixe en fonction de l'emplacement fractionnaire, 0 étant le bord gauche et 1, le droit, du premier caractère du préfixe sur la présentation rectangulaire vue dans la question. /NhNcompte le nombre de fois où le premier caractère du préfixe apparaît dans le préfixe, tandis que /zhNle nombre d'occurrences du premier caractère du préfixe dans la chaîne est un trou. Ceci assigne à chaque préfixe dirigé par chaque caractère d'un groupe une fraction différente, de 1/kl'occurrence la plus à droite de ce caractère à k/kla plus à gauche. Réorganiser la liste de préfixes avec ce numéro donne la position appropriée dans la présentation. Les égalités sont brisées en utilisant l'ordre précédent, qui était d'abord compté puis alphabétique, comme vous le souhaitez.

4. Enfin, nous devons extraire le premier caractère de chaque chaîne de préfixe, les combiner en une seule chaîne et les imprimer. Extraire les premiers caractères est hC. Ceffectue une transposition de matrice sur la liste, en réalité zip(*x)en Python 3. hextrait la première ligne de la matrice résultante. Il s’agit en fait de la seule ligne, car la présence du préfixe 1 caractère empêche la formation d’autres lignes complètes. srésume les caractères de ce tuple en une seule chaîne. L'impression est implicite.

Tester:

$ pyth -c 'shCoc/NhN/zhNm>o_/zZSzdUz' <<< 'oroybgrbbyrorypoprr'
rorbyroprbyorrobypg

Programme incrémentiel sur oroybgrbbyrorypoprr:

Sub-Piece                  Output

Sz                         bbbgoooopprrrrrryyy
o_/zNSz                    rrrrrroooobbbyyyppg      (uses N because o uses N on first use.)
m>o_/zNSzdUz               ['rrrrrroooobbbyyyppg', 'rrrrroooobbbyyyppg', 'rrrroooobbbyyyppg', 'rrroooobbbyyyppg', 'rroooobbbyyyppg', 'roooobbbyyyppg', 'oooobbbyyyppg', 'ooobbbyyyppg', 'oobbbyyyppg', 'obbbyyyppg', 'bbbyyyppg', 'bbyyyppg', 'byyyppg', 'yyyppg', 'yyppg', 'yppg', 'ppg', 'pg', 'g']
oc/NhN/zhNm>o_/zZSzdUz     ['roooobbbyyyppg', 'obbbyyyppg', 'rroooobbbyyyppg', 'byyyppg', 'yppg', 'rrroooobbbyyyppg', 'oobbbyyyppg', 'pg', 'rrrroooobbbyyyppg', 'bbyyyppg', 'yyppg', 'ooobbbyyyppg', 'rrrrroooobbbyyyppg', 'rrrrrroooobbbyyyppg', 'oooobbbyyyppg', 'bbbyyyppg', 'yyyppg', 'ppg', 'g']
Coc/NhN/zhNm>o_/zZSzdUz    [('r', 'o', 'r', 'b', 'y', 'r', 'o', 'p', 'r', 'b', 'y', 'o', 'r', 'r', 'o', 'b', 'y', 'p', 'g')]
shCoc/NhN/zhNm>o_/zZSzdUz  rorbyroprbyorrobypg

Ancienne réponse:

Pyth , 34

ssCm*+t*u*G/zHS{-zd1]kd/zdo_/zNS{z

Ce programme calcule le nombre de fois qu'une réplique donnée est répliquée. La sous-liste ressemble à ['', '', '', '', ... , 'r']. La longueur totale de cette sous-liste est le produit du nombre d'occurrences de tous les autres bonbons, c'est-à-dire u*G/zHS{-zd1. La sous-liste complète est construite en répliquant la liste de la chaîne vide ]k, celle-ci plusieurs fois, puis en supprimant l'élément tet en ajoutant le nom du bonbon à la fin +d.

Ensuite, cette sous-liste est répliquée autant de fois que ce bonbon se trouve dans l'entrée, /zden s'assurant que la liste de chaque bonbon est de longueur égale.

Maintenant, avec cette fonction mappée sur tous les bonbons uniques dans le bon ordre trié ( o_/zNS{z), nous avons un rectangle similaire à celui de l'instruction de question, mais avec des chaînes vides au lieu de points. Faire une matrice transpose ( C) suivie de deux sommations ( ss) donne la chaîne finale.

Vérification:

$ pyth programs/candy.pyth <<< 'oroybgrbbyrorypoprr'
rorbyroprbyorrobypg

Perl 5 - 62

61 code + 1 drapeau.

#!perl -n
print map/(.$)/,sort map/(.$)/*$_/$$1.~$_.$1,map++$$_.$_,/./g

Commencez par diviser l’entrée en tableau de caractères /./g.

Ajouter un indice d’occurrence à chaque lettre en laissant les nombres dans les variables $a.. $zavec map++$$_.$_. Maintenant, le tableau est:

1o
1r
2o
1y
1b
1g
2r
2b
3b
2y
3r
3o
4r
3y
1p
4o
2p
5r
6r

Ensuite, convertissez-la en une clé de tri concaténant: ratio $_/$$1, count tie breaker ~$_et valeur ASCII $_. Cela se traduira par (ici avec des espaces ajoutés pour plus de clarté).

0.25 18446744073709551614 o
0.166666666666667 18446744073709551614 r
0.5 18446744073709551613 o
0.333333333333333 18446744073709551614 y
0.333333333333333 18446744073709551614 b
1 18446744073709551614 g
0.333333333333333 18446744073709551613 r
0.666666666666667 18446744073709551613 b
1 18446744073709551612 b
0.666666666666667 18446744073709551613 y
0.5 18446744073709551612 r
0.75 18446744073709551612 o
0.666666666666667 18446744073709551611 r
1 18446744073709551612 y
0.5 18446744073709551614 p
1 18446744073709551611 o
1 18446744073709551613 p
0.833333333333333 18446744073709551610 r
1 18446744073709551609 r

Ceci peut être trié par ordre lexicographique (par défaut). À la fin, extrayez le dernier caractère et imprimez:print map/(.$)/

Python 3.x - 124 octets

C=input()
print("".join(s[1]for s in sorted(enumerate(C),key=lambda
t:((C[:t[0]].count(t[1])+1+1e-10)/C.count(t[1]),t[1]))))

Mathematica, 123 119 118 octets

f=FromCharacterCode[s=SortBy;#&@@@s[Join@@(s[Tally@ToCharacterCode@#,-Last@#&]/.{x_,n_}:>({x,#/n}&~Array~n)),{Last}]]&

Définit une fonction nommée f. Ungolfed:

f = FromCharacterCode[
   s = SortBy;
   # & @@@ s[
     Join @@ (
       s[
         Tally@ToCharacterCode@#,
         -Last@# &
         ] /. {x_, n_} :> ({x, #/n} &~Array~n)
       ),
     {Last}
     ]
   ] &

L'utilisation de types rationnels intégrés semblait être une bonne idée pour cela. Bien sûr, cela n’est nulle part près de CJam. Fondamentalement, je représente la grille indiquée dans le défi sous forme de liste de paires. La première chose dans la paire est le code de caractère, la seconde est sa position en tant que fraction inférieure ou égale à 1 (la dernière colonne étant 1). Après m'être assuré que les caractères individuels sont déjà dans le bon ordre, il me suffit de trier celle-ci de manière stable par fraction pour obtenir le résultat souhaité.

Python 45 47 48 51

Cela pourrait aussi presque certainement être joué au golf plus loin;)

Ko_/zNS{zFGK~Y]*+*t/u*GHm/zdK1/zG]k]G/zG)ssCY

Travaille en construisant une liste de listes, où chaque liste interne est une rangée de chaînes vides et le nom du bonbon. Cette liste est transposée, puis les listes internes sont jointes, suivies de ces listes.

Merci @isaacg de m'avoir rappelé la somme!

APL: 38

v⌷⍨⊂⍋⌽(n/-n),⍪∊+\¨n⍴¨÷n←{≢⍵}⌸v←{⍵[⍋⍵]}

Explication:

v←{⍵[⍋⍵]}    orders input string
n←{≢⍵}⌸v     counts how many times each element appears in v
∊+\¨n⍴¨÷n     makes incremental sums in each letter "group" 
⍋⌽(n/-n),⍪   appends number of elements in letter group and orders the obtained matrix
v⌷⍨⊂         orders vector v with computed indices

Peut être testé sur tryapl.org

R - 166 caractères

library("plyr");s=function(a){l=table(strsplit(a,s="")[[1]]);l=ldply(l[order(-l,names(l))],function(n)data.frame(seq_len(n)/n));paste(l[order(l[[2]]),1],collapse="")}

version non golfée

library("plyr")
s <- function(a) {
    tbl <- table(strsplit(a, split = "")[[1]])
    tbl <- tbl[order(-tbl, names(tbl))]
    tbl <- ldply(tbl, function(n) {data.frame(seq_len(n)/n)})
    paste(tbl[order(tbl[[2]]),1], collapse = "")
}

Explication:

• Divisé en caractères individuels
• Tabuler le nombre de chaque caractère
• Trier le tableau dans l'ordre le plus fréquent, puis par ordre lexical
• Positions d'index pour la sélection à 1 / n, 2 / n, 3 / n, ... n-1 / n, 1 où n est le nombre de bonbons
• Trier les noms de bonbons par index ( orderest stable dans le tri, donc conservera l'ordre de nommage le plus fréquent / lexical quand un lien dans l'index est particulièrement important avec les derniers bonbons)
• Concaténer les noms de bonbons pour faire la chaîne de sortie

La nature matricielle du problème m'a fait penser que R pourrait peut-être essayer, mais la meilleure interprétation littérale de l'algorithme que je pouvais utiliser était de 211 caractères:

l=function(a){l=table(strsplit(a,s="")[[1]]);l=l[order(-l,names(l))];o=Reduce(`*`,l);m=matrix("",nc=o,nr=length(l));for(r in seq_along(l)){x=l[r];for(c in seq_len(x)*o/x){m[r,c]<-names(x)}};paste(m,collapse="")}

ungolfed:

l <- function(a) {
    tbl <- table(strsplit(a, split = "")[[1]])
    tbl <- tbl[order(-tbl, names(tbl))]
    o <- Reduce(`*`, tbl)
    m <- matrix("", ncol = o, nrow = length(tbl))
    for (r in seq_along(tbl)) {
        for (c in seq_len(tbl[r])*o/tbl[r]) {
            m[r,c] <- names(tbl[r])
        }
    }
    paste(m, collapse="")
}

Pyth, 29 octets

Ceci est une traduction directe de mon réponse CJam en Pyth

oc/|$Y.append(N)$YN/zNo_/zZSz

Essayez-le en ligne ici

Cette solution a une histoire assez longue et @isaacg m'a beaucoup aidé à comprendre ce nouveau langage.

Idéalement, il s'agit de la traduction exacte mot à mot de mon code CJam ( 17 octets ):

oc/~kNN/zNo_/zZSz

ce qui signifie:

o         order_by(lambda N:
 c                 div(
  /                    count(
   ~kN                       k+=N,                #Update k (initially ""), add N
   N                         N),                  #Count N in updated k
  /zN                  count(z, N)),
 o                 order_by(lambda Z:
  _                         neg(
   /zZ                          count(z, Z)),
  Sz                        sorted(z)))

Mais malheureusement, Python ne renvoie rien dans un += appel, ce qui n’était pas un code Python valide, donc un code Pyth non valide comme dans Pyth, un lambda ne peut être qu’une déclaration de retour.

Ensuite, j'ai examiné diverses méthodes et finalement trouvé que Python list.appendrenvoie une Nonevaleur que je peux utiliser. Rendre le code à être ( 19 octets ):

oc/|aYNYN/zNo_/zZSz

ce qui signifie:

o         order_by(lambda N:
 c                 div(
  /                    count(
   |aYN                      (Y.append(N) or
    Y                         Y)                 #Update Y (initially []), append N
   N                         N),                 #Count N in updated Y
  /zN                  count(z, N)),
 o                 order_by(lambda Z:
  _                         neg(
   /zZ                          count(z, Z)),
  Sz                        sorted(z)))

Mais malheureusement, le support de a(append) a été retiré de Pyth et la version qui le supporte n’a pas le support pour o.

Mise à jour : a support a été ajouté à nouveau dans Pyth maintenant afin que le code de 19 octets ci-dessus fonctionne dans le compilateur en ligne. Mais comme il s’agit d’une nouvelle fonctionnalité qui a été ajoutée après l’opération, je ne l’affiche pas comme mon score et ne laisse pas le code à 29 octets comme solution.

Par conséquent, je devais compter sur Python brut dans ce cas, ce qui rendait le code

o         order_by(lambda N:
 c                 div(
  /                    count(
   |$Y.append(N)$            (Y.append(N) or
    Y                         Y)                 #Update Y (initially []), append N
   N                         N),                 #Count N in updated Y
  /zN                  count(z, N)),
 o                 order_by(lambda Z:
  _                         neg(
   /zZ                          count(z, Z)),
  Sz                        sorted(z)))