Quando se trata de comer doces, eu me mantenho em padrões mais elevados do que o típico leigo. Há um delicado equilíbrio entre "misturar tudo" e "guardar o melhor para o final".

Neste desafio, você receberá uma série de caracteres nos quais cada personagem representa um pedaço de doce. Caracteres diferentes (diferenciam maiúsculas de minúsculas) representam diferentes tipos de doces. Seu programa deve determinar a ordem correta do consumo de doces, com base no procedimento abaixo. Você pode gravar um programa completo (STDIN / STDOUT) ou uma função nomeada para realizar esta tarefa.

Digamos que meu estoque de doces é oroybgrbbyrorypoprr. Primeiro, eu ordeno o doce em pilhas do mesmo tipo, com quantidades maiores no topo, usando valores mais baixos de caracteres ASCII como desempate.

rrrrrr
oooo
bbb
yyy
pp
g

Então, pego cada fileira de doces e espaço-as igualmente ao longo de um intervalo. Por exemplo, se houver 3 pedaços de doce, um será colocado 1/3 do caminho, 2/3 do caminho e no final.

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

Então, desço cada coluna para criar meu pedido final de doces rorbyroprbyorrobypg,.

Entrada

Uma corda que contém o estoque de doces. A entrada para o exemplo acima poderia ter sido:

oroybgrbbyrorypoprr

Saída

Uma sequência contendo o doce reorganizada na ordem correta de consumo.

rorbyroprbyorrobypg

Pontuação

Isso é código de golfe. A resposta mais curta em bytes vence. Aplicam-se as regras padrão de código de golfe.

CJam, 78 68 61 45 42 39 31 30 bytes

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

Toma a string de entrada via STDIN

Inspirado pela abordagem recursiva, mas um pouco diferente. Não há necessidade de transpor ou retângulo!

Como funciona:

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

(Infelizmente, o CJam não pode mais concluir o Pyth devido à necessidade de tanto inchaço quanto sintaxe)

Experimente aqui

Pyth , 25

shCoc/NhN/zhNm>o_/zZSzdUz

Usa um algoritmo totalmente novo, inspirado nesta resposta .

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

Passo a passo:

1. Primeiro, classificamos os caracteres por sua comunhão, laços quebrados alfabeticamente. Isto é o_/zZSz. oé o mesmo que o de Python sorted(<stuff>,key=<stuff>), com uma expressão lambda para a chave, exceto que a mantém como uma string.

2. Em seguida, geramos uma lista dos prefixos dessa cadeia, do comprimento len(z)ao comprimento 1. >é equivalente ao do python <stuff>[<int>:].

3. Em seguida, reordenamos essa lista de sequências de prefixos pela localização fracionária, sendo 0 a aresta esquerda e 1 a direita, do primeiro caractere do prefixo no layout retangular visto na pergunta. /NhNconta quantas vezes o primeiro caractere no prefixo ocorre no prefixo, enquanto /zhNfornece o número de ocorrências do primeiro caractere no prefixo na cadeia como um buraco. Isso atribui a cada prefixo liderado por cada caractere em um grupo uma fração diferente, da 1/kocorrência mais à direita desse caractere à k/kda esquerda. Reordenar a lista de prefixos por esse número fornece a posição apropriada no layout. Os laços são quebrados usando a ordem anterior, que era primeiro por contagem e depois alfabética, conforme desejado.

4. Finalmente, precisamos extrair o primeiro caractere de cada sequência de prefixos, combiná-los em uma única sequência e imprimi-los. Extrair os primeiros caracteres é hC. Crealiza uma transposição de matriz na lista, zip(*x)na verdade no Python 3. hextrai a primeira linha da matriz resultante. Essa é realmente a única linha, porque a presença do prefixo de 1 caractere impede a formação de outras linhas completas. ssoma os caracteres nesta tupla em uma única sequência. A impressão está implícita.

Teste:

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

Partes incrementais do programa em 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

Resposta antiga:

Pyth , 34

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

Este programa funciona calculando quantas vezes replicar uma certa sublist. A sub-lista é semelhante ['', '', '', '', ... , 'r']. O comprimento total desta sub-lista é o produto do número de ocorrências de todos os outros doces, o que é u*G/zHS{-zd1. A sub-lista completa é construída replicando a lista da cadeia vazia, ]kmuitas vezes, removendo o elemento te adicionando o nome do doce ao final +d.

Em seguida, essa sub-lista é replicada quantas vezes esse doce for encontrado na entrada /zd, garantindo que a lista de cada doce tenha o mesmo comprimento.

Agora, com essa função mapeada sobre todos os doces únicos na ordem classificada adequada ( o_/zNS{z), temos um retângulo semelhante ao da declaração da pergunta, mas com cadeias vazias em vez de pontos. Fazer uma matriz transpose ( C) seguida de dois somatórios ( ss) fornece a sequência final.

Verificação:

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

Perl 5-62

Código 61 + 1 sinalizador.

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

Primeiro divida a entrada na matriz de caracteres - /./g.

Adicione índice de ocorrência a cada letra, deixando as contagens nas variáveis $a.. $zcom map++$$_.$_. Agora a matriz é:

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

Em seguida, converta-o em uma chave de classificação concatenando: razão $_/$$1, desempate de contagem ~$_e desempate de valor ASCII $_. Isso resultará em (aqui com espaços adicionais para maior clareza).

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

Isso pode ser classificado com ordem lexicográfica (padrão). No final, extraia o último caractere e imprima:print map/(.$)/

Python 3.x - 124 bytes

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 bytes

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

Define uma função nomeada f. Ungolfed:

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

Usar tipos racionais embutidos parecia uma boa ideia para isso. Claro, isso não está nem perto de CJam. Basicamente, estou representando a grade mostrada no desafio como uma lista de pares. A primeira coisa no par é o código do caractere, a segunda é a posição como uma fração menor ou igual a 1 (a coluna final é 1). Tendo me assegurado de que os caracteres individuais já estejam na ordem correta, só preciso classificar isso de forma estável pela referida fração para obter o resultado desejado.

Pitão 45 47 48 51

Isso também certamente poderia ser ainda mais jogado;)

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

Funciona criando uma lista de listas, onde cada lista interna é uma linha de cadeias vazias e o nome do doce. Essa lista é transposta e as listas internas são unidas, seguidas por essas listas.

Obrigado @isaacg por me lembrar da soma!

APL: 38

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

Explicação:

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

Pode ser testado em tryapl.org

R - 166 caracteres

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="")}

versão ungolfed

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 = "")
}

Explicação:

• Dividir em caracteres individuais
• Tabular o número de cada caractere
• Classifique a tabela em mais frequente e depois em ordem lexical
• Posições de índice para seleção em 1 / n, 2 / n, 3 / n, ... n-1 / n, 1 em que n é o número de doces
• Classificar nomes de doces por índice ( orderé estável na classificação, portanto, manterá a ordem de nomeação mais frequente / lexical quando um empate no índice, particularmente importante com os últimos doces)
• Concatene os nomes dos doces juntos para criar a sequência de saída

A natureza da matriz do problema me fez pensar que R poderia ter uma chance disso, mas a melhor interpretação literal do algoritmo que eu pude fazer foi de 211 caracteres:

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="")
}

Pitão, 29 bytes

Esta é uma tradução direta do meu CJam answe r em Pyth

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

Experimente online aqui

Há uma história bastante longa por trás dessa solução e o @isaacg me ajudou muito na compreensão desse novo idioma.

Idealmente, esta é a tradução exata palavra a palavra do meu código CJam ( 17 bytes ):

oc/~kNN/zNo_/zZSz

que significa:

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

Mas, infelizmente, o Python não retorna nada em uma +=chamada, de modo que não era um código Python válido, portanto, um código Pyth inválido também como no Pyth, um lambda pode ser apenas uma declaração de retorno.

Depois, examinei vários métodos e finalmente descobri que o Python list.appendretorna um Nonevalor que eu posso usar. Tornando o código ( 19 bytes ):

oc/|aYNYN/zNo_/zZSz

que significa:

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

Mas, infelizmente, o suporte de a(append) foi removido do Pyth e a versão que possui o suporte, não tem suporte o.

Atualização: o asuporte foi adicionado novamente no Pyth agora, para que o código de 19 bytes acima funcione no compilador online. Mas como esse é um novo recurso que foi adicionado após o OP, não o coloco como minha pontuação e deixo o código de 29 bytes como minha solução.

Portanto, eu tive que confiar no Python bruto, nesse caso, tornando o código

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