Eating Candy in the Correct Order

Question

When it comes to eating candy, I hold myself to higher standards than the typical layperson. There is a delicate balance between "mixing it up" and "saving the best for last."

In this challenge, you will be given a string of characters in which each character represents a piece of candy. Different characters (case-sensitive) represent different types of candy. Your program must then determine the correct order of candy consumption, based on the procedure below. You can write either a complete program (STDIN/STDOUT) or a named function to accomplish this task.

Let's say that my candy stash is oroybgrbbyrorypoprr. First, I sort the candy into piles of the same type, with larger quantities at the top, using lower ASCII character values as a tie-breaker.

rrrrrr
oooo
bbb
yyy
pp
g

Then, I take each row of candy and equally-space them along an interval. For example, if there are 3 pieces of candy, one is placed 1/3 of the way, 2/3 of the way, and at the end.

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

Then, I go down each column to create my final candy order, rorbyroprbyorrobypg.

Input

A string which contains the candy stash. The input for the above example could have been:

oroybgrbbyrorypoprr

Output

A string containing the candy reorganized into the correct order of consumption.

rorbyroprbyorrobypg

Scoring

This is code golf. The shortest answer in bytes wins. Standard code-golf rules apply.

Answer 1

CJam, 78 68 61 45 42 39 31 30 bytes

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

Takes the input string via STDIN

Inspired by recursive's approach, but a little different. No need of transpose or rectangle at all!.

How it works:

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

(Sad that CJam can no longer complete with Pyth due to need of so much bloat as syntax)

Try it here

Answer 2

Pyth, 25

shCoc/NhN/zhNm>o_/zZSzdUz

Uses an all new algorithm, inspired by this answer.

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

Step by step:

1. First, we sorted the characters by their commonness, ties broken alphabetically. This is o_/zZSz. o is the same as Python's sorted(<stuff>,key=<stuff>), with a lambda expression for the key, except it keeps it as a string.

2. Then we generate a list of the prefixes of that string, from length len(z) to length 1. > is equivalent to python's <stuff>[<int>:].

3. Then, we reorder this list of prefix strings by the fractional location, 0 being the left edge and 1 being the right, of the first character of the prefix on the rectangular layout seen in the question. /NhN counts how many times the first character in the prefix occurs in the prefix, while /zhN gives the number of occurrences of the first character in the prefix in the string as a hole. This assigns each prefix being led by each character in a group a different fraction, from 1/k for the right most occurrence of that character to k/k for the left most. Reordering the prefix list by this number gives the appropriate position in the layout. Ties are broken using the prior ordering, which was first by count then alphabetical, as desired.

4. Finally, we need to extract the first character from each prefix string, combine them into a single string, and print them out. Extracting the first characters is hC. C performs a matrix transpose on the list, actually zip(*x) in Python 3. h extracts the first row of the resultant matrix. This is actually the only row, because the presence of the 1 character prefix prevents any other complete rows from being formed. s sums the characters in this tuple into a single string. Printing is implicit.

Test:

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

Incremental program pieces on 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

---

Old answer:

Pyth, 34

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

This program works by calculating how many times to replicate a certain sublist. The sub-list looks like ['', '', '', '', ... , 'r']. The total length of this sub-list is the product of the number of occurrences of all of the other candies, which is u*G/zHS{-zd1. The full sublist is constructed by replicating the list of the empty string ,]k, that many times, then removing and element with t and add the candy name to the end with +d.

Then, this sub-list is replicated as many times as that candy is found in the input, /zd, ensuring each candy's list is of equal length.

Now, with this function mapped over all of the unique candies in proper sorted order (o_/zNS{z), we have a rectangle similar to the one in the question statement, but with empty strings instead of periods. Doing a matrix transpose (C) followed by two summations (ss) gives the final string.

Verification:

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

Answer 3

Perl 5 - 62

61 code + 1 flag.

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

First split the input into character array - /./g.

Add occurrence index to each letter leaving the counts in variables $a..$z with map++$$_.$_. Now the array is:

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

Then convert it to a sort key concatenating: ratio $_/$$1, count tie breaker ~$_ and ASCII value tie breaker $_. This will result in (here with added spaces for clarity).

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

This can be sorted with lexicographical (default) order. In the end extract last character and print: print map/(.$)/

Answer 4

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

Answer 5

Mathematica, 123 119 118 bytes

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

Defines a named function f. Ungolfed:

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

Using built-in rational types seemed like a good idea for this. Of course, this is nowhere near CJam. Basically, I'm representing the grid shown in the challenge as a list of pairs. The first thing in the pair is the character code, the second is it's position as a fraction less than or equal to 1 (the final column being 1). Having made sure that the individual characters are already in the right order, I just need to sort this stably by said fraction to get the desired result.

Answer 6

Pyth 45 47 48 51

This could also almost certainly be golfed further ;)

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

Works by building a list of lists, where each inner list is a row of empty strings and the name of the candy. This list is transposed and then the inner lists are joined followed by these lists being joined.

Thanks @isaacg for reminding me about sum!

Answer 7

APL: 38

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

Explanation:

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

Can be tested on tryapl.org

Answer 8

R - 166 characters

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

ungolfed version

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

Explanation:

• Split into individual characters
• Tabulate number of each character
• Sort table into most frequent and then by lexical order
• Index positions for selection at 1/n, 2/n, 3/n, ... n-1/n, 1 where n is the number of candies
• Sort candy names by index (order is stable in sorting, so will maintain the most frequent/lexical naming order when a tie in the index, particularly important with the last candies)
• Concatenate the candy names together to make the output string

---

The matrix nature of the problem made me think R might have a shot at this, but the best literal interpretation of the algorithm I could do was 211 characters:

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

Answer 9

Pyth, 29 bytes

This is a direct translation of my CJam answer in Pyth

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

Try it online here

---

There is a rather long story behind this solution and @isaacg helped me a lot in understanding this new language.

Ideally this is the exact word to word translation of my CJam code (17 bytes):

oc/~kNN/zNo_/zZSz

which means:

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

But sadly Python does not return anything in a += call, so that was not a valid Python code, thus an invalid Pyth code too as in Pyth, a lambda can only be a return statement.

Then I looked into various methods and finally found that Python's list.append returns a None value, which I can use. Making the code to be (19 bytes):

oc/|aYNYN/zNo_/zZSz

which means:

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

But sadly, support of a (append) was removed from Pyth and the version which do has the support, does not have the support for o.

Update : a support has been added back in Pyth now so the above 19 byte code will work in the online compiler. But since this is a new feature which was added after the OP, I am not putting it up as my score and letting the 29 byte code as my solution.

Therefore I had to rely on raw Python in that case, making the code to be

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