Когда дело доходит до еды конфет, я придерживаюсь более высоких стандартов, чем типичный непрофессионал. Существует тонкий баланс между «смешиванием» и «сохранением лучшего для последнего».

В этом задании вам дадут ряд символов, в которых каждый персонаж представляет собой конфету. Различные символы (с учетом регистра) представляют разные типы конфет. Ваша программа должна затем определить правильный порядок потребления конфет, основываясь на приведенной ниже процедуре. Вы можете написать либо полную программу (STDIN / STDOUT), либо именованную функцию для выполнения этой задачи.

Допустим, моя конфетка есть oroybgrbbyrorypoprr. Во-первых, я сортирую конфету на кучи того же типа, с большим количеством сверху, используя более низкие значения символов ASCII в качестве прерывателя связей.

rrrrrr
oooo
bbb
yyy
pp
g

Затем я беру каждый ряд конфет и равномерно распределяю их вдоль интервала. Например, если есть 3 конфеты, одна помещается на 1/3 пути, на 2/3 пути и в конце.

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

Затем я спускаюсь по каждому столбцу, чтобы создать мой окончательный заказ на конфеты rorbyroprbyorrobypg.

вход

Строка, которая содержит конфетный тайник. Входные данные для приведенного выше примера могли бы быть:

oroybgrbbyrorypoprr

Выход

Строка с конфетой реорганизована в правильном порядке потребления.

rorbyroprbyorrobypg

счет

Это код гольф. Самый короткий ответ в байтах побеждает. Применяются стандартные правила игры в гольф.

CJam, 78 68 61 45 42 39 31 30 байт

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

Принимает входную строку через STDIN

Вдохновленный подходом рекурсива, но немного другой. Нет необходимости транспонировать или прямоугольник на всех!

Как это работает:

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

(Печально, что CJam больше не может дополнять Pyth из-за необходимости раздувать как синтаксис)

Попробуй здесь

Пиф , 25

shCoc/NhN/zhNm>o_/zZSzdUz

Использует совершенно новый алгоритм, вдохновленный этим ответом .

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

Шаг за шагом:

1. Сначала мы отсортировали персонажей по их общности, связи разорваны по алфавиту. Это o_/zZSz. oто же самое, что и Python sorted(<stuff>,key=<stuff>), с лямбда-выражением для ключа, за исключением того, что оно хранится в виде строки.

2. Затем мы генерируем список префиксов этой строки, от длины len(z)до длины 1. >Это эквивалентно Python <stuff>[<int>:].

3. Затем мы упорядочиваем этот список строк префикса по дробному расположению, 0 - левый край, а 1 - правый, первого символа префикса в прямоугольной раскладке, видимой в вопросе. /NhNподсчитывает, сколько раз первый символ в префиксе встречается в префиксе, а /zhNколичество вхождений первого символа в префиксе в строке в виде дыры. Это присваивает каждому префиксу, возглавляемому каждым символом в группе, разные доли от 1/kнаиболее правого вхождения этого символа до k/kсамого левого. Изменение порядка номеров префиксов по этому номеру дает соответствующую позицию в макете. Связи разрываются с использованием предыдущего порядка, который сначала был по счету, а затем по алфавиту, по желанию.

4. Наконец, нам нужно извлечь первый символ из каждой строки префикса, объединить их в одну строку и распечатать. Извлечение первых символов есть hC. Cвыполняет транспонирование матрицы в списке, фактически zip(*x)в Python 3. hизвлекает первую строку результирующей матрицы. На самом деле это единственная строка, потому что наличие префикса из 1 символа предотвращает формирование любых других полных строк. sсуммирует символы в этом кортеже в одну строку. Печать неявная.

Тест:

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

Инкрементные программы 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

Старый ответ:

Пиф , 34

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

Эта программа работает, вычисляя, сколько раз реплицировать определенный подсписок. Подсписок выглядит так ['', '', '', '', ... , 'r']. Общая длина этого подсписка является произведением количества вхождений всех других конфет, которое есть u*G/zHS{-zd1. Полный подсписок создается путем ]kмногократного воспроизведения списка пустой строки, затем удаления, tдобавления элемента и добавления имени конфеты в конце +d.

Затем этот подсписок реплицируется столько раз, сколько конфет находится во входных данных /zd, обеспечивая одинаковую длину списка каждой конфетки.

Теперь, когда эта функция сопоставлена ​​со всеми уникальными конфетами в правильном отсортированном порядке ( o_/zNS{z), у нас есть прямоугольник, похожий на прямоугольник в вопросе, но с пустыми строками вместо точек. Выполнение матрицы transpose ( C) с последующими двумя суммами ( ss) дает окончательную строку.

Проверка:

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

Perl 5 - 62

61 код + 1 флаг.

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

Сначала разделите ввод на массив символов - /./g.

Добавить индекс вхождения к каждой букве, оставляя счетчики в переменных $a.. $zс map++$$_.$_. Теперь массив:

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

Затем преобразуйте его в конкатенацию ключей сортировки: коэффициент $_/$$1, счетчик связей ~$_и счетчик значений ASCII $_. Это приведет к (здесь с добавленными пробелами для ясности).

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

Это можно отсортировать в лексикографическом (по умолчанию) порядке. В конце извлеките последний символ и напечатайте:print map/(.$)/

Python 3.x - 124 байта

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 байт

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

Определяет именованную функцию f. Ungolfed:

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

Использование встроенных рациональных типов казалось хорошей идеей для этого. Конечно, это далеко не CJam. По сути, я представляю сетку, показанную в конкурсе, в виде списка пар. Первым в паре является код символа, а во-вторых, его позиция в виде дроби, меньшей или равной 1 (последний столбец равен 1). Убедившись, что отдельные символы уже находятся в правильном порядке, мне просто нужно отсортировать их по дробной части, чтобы получить желаемый результат.

Pyth 45 47 48 51

Это также может быть почти наверняка дальше в гольф;)

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

Работает путем построения списка списков, где каждый внутренний список представляет собой ряд пустых строк и название конфеты. Этот список транспонируется, а затем соединяются внутренние списки, за которыми следуют эти списки.

Спасибо @isaacg за напоминание о сумме!

APL: 38

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

Объяснение:

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

Может быть проверено на tryapl.org

R - 166 символов

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

негольфированная версия

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

Объяснение:

• Разделить на отдельных персонажей
• Табличное число каждого символа
• Сортировка таблицы по наиболее частым, а затем по лексическому порядку
• Индексные позиции для выбора 1 / n, 2 / n, 3 / n, ... n-1 / n, 1, где n - количество конфет
• Сортировка названий конфет по индексу ( orderстабильна при сортировке, поэтому будет поддерживать наиболее частый / лексический порядок именования, когда в индексе есть связь, особенно важно с последними конфетами)
• Объединить имена конфет вместе, чтобы сделать строку вывода

Матричный характер проблемы заставил меня подумать, что R мог бы попытаться это сделать, но лучшая буквальная интерпретация алгоритма, который я мог сделать, была 211 символов:

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 байт

Это прямой перевод моего CJam answe г в Pyth

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

Попробуйте онлайн здесь

За этим решением стоит довольно длинная история, и @isaacg очень помог мне в понимании этого нового языка.

В идеале это точный межсловесный перевод моего кода CJam ( 17 байт ):

oc/~kNN/zNo_/zZSz

что значит:

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

Но, к сожалению, Python ничего не возвращает в +=вызове, так что это не был действительный код Python, следовательно, недопустимый код Pyth, как и в Pyth, лямбда может быть только оператором возврата.

Затем я изучил различные методы и, наконец, обнаружил, что Python list.appendвозвращает Noneзначение, которое я могу использовать. Создание кода ( 19 байт ):

oc/|aYNYN/zNo_/zZSz

что значит:

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

Но, к сожалению, поддержка a(append) была удалена из Pyth, а версия, у которой есть поддержка, не имеет поддержки o.

Обновление: aподдержка была добавлена ​​еще в Pyth, поэтому вышеуказанный 19-байтовый код будет работать в онлайн-компиляторе. Но так как это новая функция, которая была добавлена ​​после ОП, я не ставлю ее в качестве оценки и не допускаю использование 29-байтового кода в качестве решения.

Поэтому в этом случае мне пришлось положиться на сырой Python, чтобы код был

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