Jeśli chodzi o jedzenie cukierków, trzymam się wyższych standardów niż typowy laik. Istnieje delikatna równowaga między „pomieszaniem” a „zachowaniem tego, co najlepsze na koniec”.

W tym wyzwaniu otrzymasz ciąg znaków, w którym każda postać reprezentuje kawałek cukierka. Różne znaki (z uwzględnieniem wielkości liter) reprezentują różne rodzaje cukierków. Twój program musi następnie ustalić prawidłową kolejność konsumpcji słodyczy, zgodnie z poniższą procedurą. Możesz napisać albo pełny program (STDIN / STDOUT), albo nazwaną funkcję, aby wykonać to zadanie.

Powiedzmy, że moja skrytka z cukierkami jest oroybgrbbyrorypoprr. Najpierw sortuję cukierki na stosy tego samego typu, z większymi ilościami na górze, używając niższych wartości znaków ASCII jako elementu rozstrzygającego.

rrrrrr
oooo
bbb
yyy
pp
g

Następnie biorę każdy rząd cukierków i układam je równo w odstępie czasu. Na przykład, jeśli są 3 kawałki cukierków, jedna jest umieszczana 1/3 drogi, 2/3 drogi i na końcu.

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

Następnie idę w dół każdej kolumny, aby stworzyć mój ostateczny rozkaz cukierków, rorbyroprbyorrobypg.

Wkład

Sznurek zawierający skrytkę z cukierkami. Dane wejściowe dla powyższego przykładu mogły być następujące:

oroybgrbbyrorypoprr

Wydajność

Sznurek zawierający cukierki zreorganizowany w prawidłowej kolejności konsumpcji.

rorbyroprbyorrobypg

Punktacja

To jest kod golfowy. Najkrótsza odpowiedź w bajtach wygrywa. Obowiązują standardowe zasady gry w golfa.

CJam, 78 68 61 45 42 39 31 30 bajtów

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

Bierze ciąg wejściowy przez STDIN

Zainspirowany podejściem rekurencyjnym, ale trochę innym. Nie ma potrzeby transpozycji ani prostokąta!

Jak to działa:

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

(Smutne, że CJam nie może już ukończyć Pyth'a z powodu potrzeby tak dużego wzdęcia jak składni)

Wypróbuj tutaj

Pyth , 25

shCoc/NhN/zhNm>o_/zZSzdUz

Wykorzystuje zupełnie nowy algorytm, zainspirowany tą odpowiedzią .

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

Krok po kroku:

1. Najpierw posortowaliśmy postacie według ich pospolitości, powiązania zerwane alfabetycznie. Jest o_/zZSz. ojest taki sam jak Python sorted(<stuff>,key=<stuff>), z wyrażeniem lambda dla klucza, tyle że zachowuje go jako ciąg znaków.

2. Następnie generujemy listę prefiksów tego ciągu, od długości len(z)do długości 1. >jest równoważna pythonowi <stuff>[<int>:].

3. Następnie zmieniamy kolejność tej listy ciągów prefiksów według położenia ułamkowego, gdzie 0 oznacza lewą krawędź, a 1 prawą, pierwszego znaku prefiksu na układzie prostokątnym widocznym w pytaniu. /NhNzlicza, ile razy pierwszy znak w prefiksie występuje w prefiksie, a jednocześnie /zhNpodaje liczbę wystąpień pierwszego znaku w prefiksie w ciągu jako dziury. Przypisuje to każdemu prefiksowi prowadzonemu przez każdą postać w grupie inną frakcję, od 1/kskrajnego prawego wystąpienia tego znaku do k/kskrajnego lewego. Zmiana kolejności listy prefiksów o ten numer daje odpowiednią pozycję w układzie. Więzy są zrywane przy użyciu wcześniejszego zamówienia, które najpierw było zliczane, a następnie alfabetycznie, zgodnie z życzeniem.

4. Na koniec musimy wyodrębnić pierwszy znak z każdego ciągu prefiksu, połączyć je w jeden ciąg i wydrukować. Wyodrębnianie pierwszych znaków to hC. Cwykonuje transpozycję macierzy na liście, faktycznie zip(*x)w Pythonie 3. hwyodrębnia pierwszy wiersz wynikowej macierzy. Jest to właściwie jedyny wiersz, ponieważ obecność prefiksu 1 znaku uniemożliwia utworzenie innych kompletnych wierszy. ssumuje znaki w tej krotce w pojedynczy ciąg. Drukowanie jest niejawne.

Test:

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

Przyrostowe elementy programu na 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

Stara odpowiedź:

Pyth , 34

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

Ten program działa na zasadzie obliczania, ile razy ma być replikowana określona lista podrzędna. Wygląda na to lista podrzędna ['', '', '', '', ... , 'r']. Całkowita długość tej podlisty jest iloczynem liczby wystąpień wszystkich innych cukierków, to jest u*G/zHS{-zd1. Pełna lista podrzędna jest konstruowana poprzez replikację listy pustego łańcucha, ]kwiele razy, a następnie usuwanie i wstawianie toraz dodawanie nazwy cukierka na końcu za pomocą +d.

Wtedy to sub-lista jest powtórzone tyle razy, że cukierek znajduje się w wejściu, /zdzapewniając każdej listy cukierek jest jednakowej długości.

Teraz, gdy ta funkcja jest odwzorowana na wszystkie unikalne cukierki w odpowiedniej kolejności sortowania ( o_/zNS{z), mamy prostokąt podobny do tego w pytaniu, ale z pustymi ciągami zamiast kropek. Wykonanie transpozycji macierzy ( C), po której następują dwa sumy ( ss), daje końcowy ciąg znaków.

Weryfikacja:

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

Perl 5 - 62

61 kod + 1 flaga.

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

Najpierw podziel dane wejściowe na tablicę znaków - /./g.

Dodaj indeks występowania do każdej litery, pozostawiając liczby w zmiennych $a.. za $zpomocą map++$$_.$_. Teraz tablica jest:

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

Następnie przekonwertuj go na klucz sortowania konkatenujący: współczynnik $_/$$1, licznik remisów ~$_i wyłącznik remisów wartości ASCII $_. Spowoduje to (tutaj z dodanymi spacjami dla przejrzystości).

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

Można to sortować według kolejności leksykograficznej (domyślnej). Na koniec wyodrębnij ostatni znak i wydrukuj:print map/(.$)/

Python 3.x - 124 bajty

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 bajtów

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

Definiuje nazwaną funkcję f. Nie golfowany:

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

Korzystanie z wbudowanych typów wymiernych wydawało się dobrym pomysłem. Oczywiście nie jest to nigdzie blisko CJam. Zasadniczo reprezentuję siatkę pokazaną w wyzwaniu jako listę par. Pierwszą rzeczą w parze jest kod znaku, a drugą jego pozycja jako ułamek mniejszy lub równy 1 (ostatnia kolumna to 1). Po upewnieniu się, że poszczególne postacie są już we właściwej kolejności, muszę tylko posortować to stabilnie według wspomnianej frakcji, aby uzyskać pożądany wynik.

Pyth 45 47 48 51

Niemal na pewno można by dalej grać w golfa;)

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

Działa poprzez budowanie listy list, gdzie każda wewnętrzna lista jest rzędem pustych ciągów i nazwą cukierka. Ta lista jest transponowana, a następnie łączone listy wewnętrzne, a następnie dołączane są te listy.

Dzięki @isaacg za przypomnienie mi o sumie!

APL: 38

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

Wyjaśnienie:

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

Można przetestować na tryapl.org

R - 166 znaków

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

wersja bez golfa

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

Wyjaśnienie:

• Podziel na poszczególne postacie
• Tabelaryczną liczbę każdego znaku
• Sortuj tabelę według najczęstszych, a następnie według kolejności leksykalnej
• Indeksuj pozycje do wyboru przy 1 / n, 2 / n, 3 / n, ... n-1 / n, 1 gdzie n jest liczbą cukierków
• Sortuj nazwy cukierków według indeksu ( orderjest stabilny w sortowaniu, więc zachowa najczęstszą / leksykalną kolejność nazewnictwa, gdy remis w indeksie, szczególnie ważny w przypadku ostatnich cukierków)
• Połącz nazwy cukierków razem, aby utworzyć ciąg wyjściowy

Matrycowa natura problemu sprawiła, że ​​pomyślałem, że R może mieć na to szansę, ale najlepszą dosłowną interpretacją algorytmu, jaką mogłem zrobić, było 211 znaków:

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

bez golfa:

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 bajtów

To jest bezpośrednie tłumaczenie mojej odpowiedzi CJam w Pyth

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

Wypróbuj online tutaj

Za tym rozwiązaniem kryje się dość długa historia, a @isaacg bardzo mi pomógł w zrozumieniu tego nowego języka.

Idealnie jest to dokładne tłumaczenie słowa do słowa mojego kodu CJam ( 17 bajtów ):

oc/~kNN/zNo_/zZSz

co znaczy:

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

Ale niestety Python nic nie zwraca += wywołaniu, więc nie był to prawidłowy kod Pythona, dlatego też jest to niepoprawny kod Pythona, tak jak w Pyth, lambda może być tylko instrukcją return.

Potem przejrzałem różne metody i w końcu odkryłem, że Python list.appendzwraca Nonewartość, której mogę użyć. Tworzenie kodu ( 19 bajtów ):

oc/|aYNYN/zNo_/zZSz

co znaczy:

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

Niestety, obsługa a(append) została usunięta z Pytha, a wersja, która ją obsługuje, nie obsługuje o.

Aktualizacja: aobsługa Pythona została teraz ponownie dodana, aby powyższy 19-bajtowy kod działał w kompilatorze online. Ale ponieważ jest to nowa funkcja, która została dodana po OP, nie przedstawiam jej jako mojego wyniku i nie pozwalam na kod 29-bajtowy jako rozwiązanie.

Dlatego musiałem polegać na surowym Pythonie, tworząc kod

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