Fixing a Froot Loop Necklace

Question

Suppose you are stringing a strand of Froot Loops for a necklace, bracelet, shoelace, or whatever. There are 6 loop colors: red, orange, yellow, green, blue, and purple. You want your strand to start with red at the very left and cycle in rainbow order going right, ending with purple. That is, you want to make it so your strand could be represented by the string roygbp repeated some number of times (possibly 0).

The problem is, you've already strung your loops, and not in any particular order. Which loops should you eat and not eat so that you can maximize the number of correct rainbow cycles going from left to right, with the very first loop red and the very last loop purple?

Write a program or function that takes in an arbitrary string of the characters roygbp and prints or returns a string of the same length with e in the place of loops to eat and n in the place of loops to not eat.

For example, if your Froot Loop strand looked like

the input would be

gorboypbgbopyroybbbogppbporyoygbpr

and going from left to right we can find 3 complete roygbp rainbow sequences, but some of the loops need to be eaten away. Thus the output would be

eenenneennenennneeeeneennenennnnne

resulting in a perfect 3 cycle strand:

If there are no complete rainbow cycles in the input then the output would be all e's and the strand ends up loopless. e.g. the input proygb has output eeeeee. Conversely, proygbp has output ennnnnn.

You can assume all input strands have at least one loop.

The shortest code in bytes wins.

Answer 1

Hexagony, 920 722 271 bytes

Six different types of fruit loops, you say? That is what Hexagony was made for.

){r''o{{y\p''b{{g''<.{</"&~"&~"&<_.>/{.\.....~..&.>}<.._...=.>\<=..}.|>'%<}|\.._\..>....\.}.><.|\{{*<.>,<.>/.\}/.>...\'/../==.|....|./".<_>){{<\....._>\'=.|.....>{>)<._\....<..\..=.._/}\~><.|.....>e''\.<.}\{{\|./<../e;*\.@=_.~><.>{}<><;.(~.__..>\._..>'"n{{<>{<...="<.>../

Okay, it wasn't. Oh god, what did I do to myself...

This code is now a hexagon of side length 10 (it started out at 19). It could probably be golfed some more, maybe even to size 9, but I think my job is done here... For reference, there are 175 actual commands in the source, many of which are potentially unnecessary mirrors (or were added to cancel out a command from a crossing path).

Despite the apparent linearity, the code is actually two-dimensional: Hexagony will rearrange it into a regular hexagon (which is also valid code, but all whitespace is optional in Hexagony). Here is the unfolded code in all its... well I don't want to say "beauty":

          ) { r ' ' o { { y \
         p ' ' b { { g ' ' < .
        { < / " & ~ " & ~ " & <
       _ . > / { . \ . . . . . ~
      . . & . > } < . . _ . . . =
     . > \ < = . . } . | > ' % < }
    | \ . . _ \ . . > . . . . \ . }
   . > < . | \ { { * < . > , < . > /
  . \ } / . > . . . \ ' / . . / = = .
 | . . . . | . / " . < _ > ) { { < \ .
  . . . . _ > \ ' = . | . . . . . > {
   > ) < . _ \ . . . . < . . \ . . =
    . . _ / } \ ~ > < . | . . . . .
     > e ' ' \ . < . } \ { { \ | .
      / < . . / e ; * \ . @ = _ .
       ~ > < . > { } < > < ; . (
        ~ . _ _ . . > \ . _ . .
         > ' " n { { < > { < .
          . . = " < . > . . /

Explanation

I won't even try and begin explaining all the convoluted execution paths in this golfed version, but the algorithm and overall control flow are identical to this ungolfed version which might be easier to study for the really curious after I've explained the algorithm:

                 ) { r ' ' o { { \ / ' ' p { . . .
                . . . . . . . . y . b . . . . . . .
               . . . . . . . . ' . . { . . . . . . .
              . . . . . . . . \ ' g { / . . . . . . .
             . . . . . . . . . . . . . . . . . . . . .
            . . . . . . . . . . . . . . . . . . . . . .
           . . . . . . . . > . . . . < . . . . . . . . .
          . . . . . . . . . . . . . . > . . ) < . . . . .
         . . . . . . . . . . / = { { < . . . . ( . . . . .
        . . . . . . . . . . . ; . . . > . . . . . . . . . <
       . . . . . . . . . . . . > < . / e ; * \ . . . . . . .
      . . . . . . . . . . . . @ . } . > { } < . . | . . . . .
     . . . . . / } \ . . . . . . . > < . . . > { < . . . . . .
    . . . . . . > < . . . . . . . . . . . . . . . | . . . . . .
   . . . . . . . . _ . . > . . \ \ " ' / . . . . . . . . . . . .
  . . . . . . \ { { \ . . . > < . . > . . . . \ . . . . . . . . .
 . < . . . . . . . * . . . { . > { } n = { { < . . . / { . \ . . |
  . > { { ) < . . ' . . . { . \ ' < . . . . . _ . . . > } < . . .
   | . . . . > , < . . . e . . . . . . . . . . . . . = . . } . .
    . . . . . . . > ' % < . . . . . . . . . . . . . & . . . | .
     . . . . _ . . } . . > } } = ~ & " ~ & " ~ & " < . . . . .
      . . . \ . . < . . . . . . . . . . . . . . . . } . . . .
       . \ . . . . . . . . . . . . . . . . . . . . . . . < .
        . . . . | . . . . . . . . . . . . . . . . . . = . .
         . . . . . . \ . . . . . . . . . . . . . . . . / .
          . . . . . . > . . . . . . . . . . . . . . . . <
           . . . . . . . . . . . . . . . . . . . . . . .
            _ . . . . . . . . . . . . . . . . . . . . .
             . . . . . . . . . . . . . . . . . . . . .
              . . . . . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . .
                . . . . . . . . . . . . . . . . . .
                 . . . . . . . . . . . . . . . . .

Honestly, in the first paragraph I was only half joking. The fact that we're dealing with a cycle of six elements was actually a great help. The memory model of Hexagony is an infinite hexagonal grid where each edge of the grid contains a signed arbitrary-precision integer, initialised to zero.

Here is a diagram of the layout of the memory I've used in this program:

The long straight bit on the left is used as a 0-terminated string a of arbitrary size which is associated with the letter r. The dashed lines on the other letters represent the same kind of structure, each one rotated by 60 degrees. Initially, the memory pointer points at the edge labelled 1, facing north.

The first, linear bit of the code sets the inner "star" of edges to the letters roygbp as well as setting the initial edge to 1, such that we know where the cycle ends/begins (between p and r):

){r''o{{y''g{{b''p{

After this, we're back on the edge labelled 1.

Now the general idea of the algorithm is this:

1. For each letter in the cycle, keep reading letters from STDIN and, if they are different from the current letter, append them to the string associated with that letter.
2. When we read the letter we're currently looking for, we store an e in the edge labelled ?, because as long as the cycle is not complete, we have to assume that we'll have to eat this character as well. Afterwards, we'll move around the ring to the next character in the cycle.
3. There are two ways this process can be interrupted:
   • Either we've completed cycle. In this case, we make another quick round through the cycle, replacing all those es in the ? edges with ns, because now we want that cycle to remain on the necklace. Then we move on to printing code.
   • Or we hit EOF (which we recognise as a negative character code). In this case, we write a negative value into the ? edge of the current character (so that we can easily distinguish it from both e and n). Then we search for the 1 edge (to skip the remainder of a potentially incomplete cycle) before moving to printing code as well.
4. The printing code goes through the cycle again: for each character in the cycle it clears the stored string while printing an e for each character. Then it moves to the ? edge associated with the character. If it's negative, we simply terminate the program. If it's positive, we simply print it and move on to the next character. Once we complete the cycle we go back to step 2.

Another thing that might be interesting is how I've implemented the arbitrary-size strings (because it's the first time I've used unbounded memory in Hexagony).

Imagine we're at some point where we're still reading characters for r (so we can use the diagram as is) and a[0] and a1 have already been filled with characters (everything north-west of them is still zero). E.g. maybe we've just read the first two characters og of the input into those edges and are now reading a y.

The new character is read into the in edge. We use the ? edge to check whether this character is equal to r. (There's a nifty trick here: Hexagony can only distinguish between positive and non-positive easily, so checking for equality via subtraction is annoying and requires at least two branches. But all the letters are less than a factor of 2 from each other, so we can compare the values by taking the modulo, which will only give zero if they are equal.)

Because y is different from r, we move the (unlabelled) edge left of in and copy the y there. We now move further around the hexagon, copying the character one edge further each time, until we have the y on the edge opposite of in. But now there is already a character in a[0] which we don't want to overwrite. Instead, we "drag" the y around the next hexagon and check a1. But there's a character there as well, so we go another hexagon further out. Now a[2] is still zero, so we copy the y into it. The memory pointer now moves back along the string towards the inner ring. We know when we've reached the beginning of the string, because the (unlabelled) edges between the a[i] are all zero whereas ? is positive.

This will probably be a useful technique for writing non-trivial code in Hexagony in general.

Answer 2

Hexagony, 169 bytes

I was inspired by Martin Büttner’s answer (it’s his esolang, too) and decided I can do it in size 8. (I’m convinced it’s possible in size 7, too, but it’s very difficult. I’ve already spent four days non-stop on this.)

r'.'o\|{##|_#{#>\_{b{"]_\..<>"<>\/><#y/''"_<.}]''/'\>)}}.\}}'{<"\\#_#/<|##|#@#"p><n'>"{,<##g#_/#'.\<\##'#{(.<#e;#"\##%\\(};/*#>.)\>##_/"{__\}#>}=\#>=<|>##)|###_'#\"{__\\

Laid out hexagonally:

       r ' . ' o \ | {
      # # | _ # { # > \
     _ { b { " ] _ \ . .
    < > " < > \ / > < # y
   / ' ' " _ < . } ] ' ' /
  ' \ > ) } } . \ } } ' { <
 " \ \ # _ # / < | # # | # @
# " p > < n ' > " { , < # # g
 # _ / # ' . \ < \ # # ' # {
  ( . < # e ; # " \ # # % \
   \ ( } ; / * # > . ) \ >
    # # _ / " { _ _ \ } #
     > } = \ # > = < | >
      # # ) | # # # _ '
       # \ " { _ _ \ \

The program does not actually use the # instruction, so I’ve used that character to show which cells are actually unused. Furthermore, every no-op cell that is traversed in only one direction is a mirror (e.g. _ if traversed horizontally), so you know all the . characters are traversed in more than one direction.

Explanation

At the start, we execute the sequence of instructions r''o{{y''g{{b''p"")". These are strewn a bit haphazardly across the code because I squeezed them in after I wrote everything else. I use ] to switch to the next instruction pointer a few times; this way I can essentially teleport to another corner of the hexagon. The entire rest of the program is executed by instruction pointer #3.

The memory now looks as follows, with the important edges labeled with names I will use in this explanation:

The labeled edges mean the following:

• in: We use this edge to store a character we read from STDIN.
• %: We use this edge to perform a modulo operation on the character read from STDIN (in) and the current “valid” character (r, o, etc.), which will be 0 if they are equal. I stole this trick from Martin Büttner’s answer, but the rest of the program is different.
• #: For as long as we read “invalid” characters (i.e. colors we need to eat), we increment this edge. Thus, this edge remembers how many es we need to output later.
• r?: Always 0 except where the r (red) part is. This tells us when we’ve completed a cycle.

The program proceeds thusly:

• Keep reading characters. If it’s not the character we’re currently looking for, increment #. Otherwise move to the next segment of the memory in clockwise order.
• When moving to the next segment, if r? is positive, we’ve made a whole revolution. Make a complete round and output # es and 1 n per segment. This sets each # back to 0. (The e is placed on an unlabeled edge, but for the n we misappropriate the # edge, which we set to 0 using a * (multiplication) afterwards, which works because we know that all the % edges are zero at this time.)
• When reading a character, if it is not positive (i.e., EOF), go backwards through the circle and output #+1 es until you get back to where r? is positive, then exit.

After a complete run, the memory looks approximately as follows at the end. You will notice the edges containing 101 (the ASCII code of e); one of the in edges is -1 (EOF); all the # edges are at 0; and the memory pointer ends at the positive r? edge.

Answer 3

Retina, 148 85 79 bytes

$
#roygbp
.(?<=(?=((?=.*#(\2?(.))).*?\3(?<=^\5())?)+.*\3$)(.*))\4
n
#.*

[^n]
e

You can run this from a single source file with the -s interpreter flag.

Explanation

Let's get the simple stuff out of the way first:

$
#roygbp

Appends #roygbp to the end of the string, which we'll use to compute the cycle of letters dynamically.

The next (long) step figures out which loops to keep and replaces them with n. We'll look into how this works in a bit.

#.*
<empty>

This gets rid of our lookup helper at the end of the string.

[^n]
e

This replaces all characters that weren't replaced in the second step with e, completing the transformation.

Now let's go back to the second step.

The basic structure uses a trick, which I discovered a few months ago to replace selected characters in a global match:

.(?<=(?=...(?<=^\k<prefix>(?<flag>))?...)^(?<prefix>.*))\k<flag>

where ... corresponds to an arbitrarily complex pattern. This matches the character to be replaced with . and then starts a lookbehind (which you should read from right to left). The lookbehind captures everything up to the matched character into a group prefix. Then it switches to a lookahead, which now starts from the beginning of the string and can contain a complex pattern. After the character which we want to replace in that pattern, we put an optional lookbehind, which checks if the prefix group matches here. If it does, it captures an empty string into the flag group. If it doesn't, because it's optional, it doesn't affect the state of the regex engine at all and is ignored. Finally, once the lookahead is matched successfully, only the \k<flag> at the end is left which only matches if the flag was set at some point during the computation.

Now let's ungolf the long regex a bit by using named groups and freespacing mode:

.
(?<=
  (?=
    (?:
      (?=
        .*#
        (?<cycle>
          \k<cycle>?
          (?<char>)
        )
      )
      .*?
      \k<char>
      (?<=^\k<prefix>(?<flag>))?
    )+
    .*
    \k<char>$
  )
  (?<prefix>.*)
)
\k<flag>

I hope you recognise the general outline from above, so we only need to look at what I filled in for ....

We want to capture the next character in the cycle into the group char. We do this by also remembering the string from # to the current character in cycle. To get the next character, we use a lookahead to search for the #. Now we try to match cycle and then match the next character in char. This will usually be possible, unless char is the last character p. In this case, \k<cycle> will match the entire remainder of the string and there won't be a character left to capture into char. So the engine backtracks, omits the backreference to cycle and just matches the first character r instead.

Now we've got the next character in the cycle in char, we search for next possible occurrence of that character with .*?\k<char>. These are the characters we want to replace, so we put the prefix check after it. These steps (find the next char in the cycle, search for the next occurrence of it, set flag if appropriate) are now simply repeated with a +.

That's actually all there is to finding the cyclic subsequence, but we also need to make sure that we end on a p. This is fairly easy: just check that the value currently stored in char matches the p at the end of the string with .*\k<char>$. This also ensures that our lookup string isn't used to finish an incomplete cycle, because we need the trailing p for this check.

Answer 4

Pyth, 31 bytes

:*lz\nhf!:jk.DzT"roygbp"kyUlz\e

Incredibly inefficient, explanation coming soon.

yUlz generates all possible subsets of all possible indices of z (the input) in order. E.g. if the input is abc:

[[], [0], [1], [2], [0, 1], [0, 2], [1, 2], [0, 1, 2]]

Then hf! finds the first T in the above list such that :jk.DzT"roygbp"k is false. .D takes a string and list of indices, and deletes the elements at those indices. So .D"abcd",1 3 is "ac". Since .D returns a list (which should not be the case, will fix in future versions of Pyth), I use jk (k is "") to join it together back into a string. The :_"roygbp"k part replaces every instance of a cycle with the empty string.

Since the empty string is false, the above paragraphs explain how I find the smallest set of indices needed to eat to get a string consisting only of cycles.

:*lz\n_\e then turns that list of indices into an nnnneeennene string.

Answer 5

Python 2, 133 130 126 121 bytes

r=n=''
for c in input():r+='en'[c=='roygbp'[r.count('n')%6]]
for c in r:n+=['e',c][n.count('n')<r.count('n')/6*6]
print n

The first loop gets cycles, and the second removes an incomplete cycle

Saved 3 bytes thanks to J F and 5 from DLosc

Answer 6

Perl 5, 76 65 bytes

A pinch of pure undiluted regular expressions.
First finds what shouldn't be eaten. What remains is eatable.

s/r(.*?)o(.*?)y(.*?)g(.*?)b(.*?)p/n$1n$2n$3n$4n$5n/g;s/[^n\s]/e/g

Test

$ perl -p fruitloops.pl <<<gorboypbgbopyroybbbogppbporyoygbpr
eenenneennenennneeeeneennenennnnne

Answer 7

Lua, 101 bytes

s=arg[1]:gsub("r(.-)o(.-)y(.-)g(.-)b(.-)p.-","*%1*%2*%3*%4*%5*"):gsub("%w","e"):gsub("*","n")print(s)

Uses Lua patterns creatively; I think it's an interesting approach.

It replaces all non-eaten characters with "*"s, replaces all alphanumeric characters with "e"s, then replaces all "*"s with "n"s.

Answer 8

Javascript (ES6), 118

a=>eval("b=[...a],d=0,e=b.map(f=>f=='roygbp'[d%6]?'n'[++d&0]:'e');for(i=e.length-1;i&&b[i]!='p';e[i--]='e');e.join``")

Fiddle tested in Firefox. I hear Chrome supports arrow functions now but I haven't tested this in Chrome yet.

Ungolfed:

input=>eval("
    array = [...input],
    rainbow_index = 0,
    mapped = array.map( item=>
        item == 'roygbp'[rainbow_index%6] ? 'n'[++rainbow_index&0] : 'e'
        // when we encounter an item of the rainbow, do not eat and start using
        // the next rainbow item, otherwise eat
    );
    // go through backwards and eat until we find a 'p' indicating the last
    // complete loop
    for(i = mapped.length - 1; i && array[i]!='p'; mapped[i--] = 'e');

    mapped.join``
")

Answer 9

gawk, 96

{for(;c=substr("roygbp",++i,1);r=r"\\"i"n")p=p"([^"c"]*)"c;$0=gensub(p,r,"g");gsub(/[^n]/,"e")}1

Constructs the search pattern "([^r]*)r([^o]*)o([^y]*)y([^g]*)g([^b]*)b([^p]*)p" and the replacement "\\1n\\2n\\3n\\4n\\5n\\6n". After that replacement it declares everything food ("e"), that's not part of a complete rainbow.

This combination automatically ensures, that no rainbows will be harmed during this operation, and no severed rainbows show up at the end.

Answer 10

Pyth, 42 bytes

Jf-Z=+Zq@zT@"roygbp"ZUzs.e@"en"}k<J*6/lJ6z

Try it online: Demonstration

Answer 11

CJam, 41 bytes

2r:R,m*{R.*s__,6/"roygbp"*=\,~*}$0="en"f=

Brute-force approach that tries all eat/not-eat variations and selects the one that results in the longest, valid necklace.

Try it online in the CJam interpreter.

Answer 12

CJam, 50 bytes

l{"roygbp"T=={'nT):T;}{'e}?}%W%_'ne=6%{_'n#'et}*W%

Try it online

This is a little longer than some of the other submissions, but it is very efficient with linear complexity. It scans through the input string, and matches characters one by one.

The core part of the algorithm is actually fairly compact. About half of the code is for removing the incomplete cycle at the end.

Answer 13

C90, 142-146 bytes (down to 119, depending)

Operates in linear time to efficiently eat those fruit loops that can't be part of a pretty rainbow. Then, a postprocess kills any partial loop at the end.

Here are four versions:

• Version 1 (146 bytes), call with [name] [string]:
  main(int a,char**b){char*v=b[1],*s="roygbp",i=0,k=0;for(;v[i];++i)if(s[k]==v[i]){++k;k%=6;v[i]='n';}else v[i]='e';while(k-->0)v[--i]='e';puts(v);}

• Version 2 (142 bytes), call with [name] [string] [rainbow order]:
  main(int a,char**b){char*v=b[1],*s=b[2],i=0,k=0;for(;v[i];++i)if(s[k]==v[i]){++k;k%=6;v[i]='n';}else v[i]='e';while(k-->0)v[--i]='e';puts(v);}
  This allows you to define your own rainbow ordering with any colors you want so long as they aren't n or e. This actually makes the code shorter!

• Version 3 (123 bytes), call like version 1:
  main(int a,char**b){char*v=b[1],*s="roygbp",i=0,k=0;for(;v[i];++i)if(s[k]==v[i]){++k;k%=6;v[i]='n';}else v[i]='e';puts(v);}
  This one gives you as much of your rainbow as possible! The incomplete trailing rainbows show promise! We shouldn't eat them!

• Version 4 (119 bytes), call like version 2:
  main(int a,char**b){char*v=b[1],*s=b[2],i=0,k=0;for(;v[i];++i)if(s[k]==v[i]){++k;k%=6;v[i]='n';}else v[i]='e';puts(v);}
  Same as version 3, but MOAR RAINBOW TYPES!

Minor limitation: machine must have signed chars (the general case), and string must be fairly short. Outputs a trailing \n for clarity.

Version 1 is the only one that clearly passes the requirements, although version 2 is arguable. Versions 3 and 4 are less-correct (but still fun) interpretation of the question.

Answer 14

Pyth, 38 bytes

I know this is significantly longer than orlp's answer, but this one runs in linear time :o)

u+G?qH@"roygbp"/G\n\n\e+_>_zJx_z\p*Jdk

Try it out here.

In brief, this program replaces all characters after the final 'p' with spaces, then iterates over each character in the resulting string. If the character is the next in the 'roygbp' sequence, print 'n', otherwise print 'e'.

                                          Implicit: z=input(), d=' ', k=''
                            Jx_z\p        Find number of chars after last p, store in J
                        _>_zJ             Take all but J chars of the input
                       +          *Jd     Append J spaces
u                                    k    Reduce on the above, starting with ''
               /G\n                       Count 'n' in output so far
      @"roygbp"                           Take relevant char from sequence string (modulus indexing)
   ?qH                                    Does the current char equal the above?
 +G                \n\e                   Select 'n' or 'e' as appropriate and append

I've struggled to find a shorter way to process the input string. _>_zJ in particular feels awkward, but <Jz doesn't give the required string when J == 0, i.e. when the input ends with a 'p'.

Answer 15

Haskell, 138 bytes

g does it.

f(c:r)(h:t)|c==h='n':(f(r++[c])t)|0<1='e':(f(c:r)t)
f _""=""
z 'n' 'n'='n'
z a b='e'
r=reverse
g s=zipWith z(f"roygbp"s)(r$f"pbgyor"(r s))

Answer 16

Javascript (ES6), 85 82 bytes

The "necklace must end in a purple" rule was originally a great hurdle, increasing my score from 66 to 125, but I found a shorter way over it (thankfully!).

s=>(i=j=0,s.replace(/./g,x=>s.lastIndexOf`p`>=j++&x=='roygbp'[i%6]?(i++,'n'):'e'))

Explanation:

This code loops through each character in the input and replaces each with r or e with this logic:

• If the character's position is <= the last position of p, AND the character is the next one in the rainbow, keep it (replace it with n).
• Otherwise, eat it (replace it with e).

Ungolfed:

function a(s) {
  var i=0, j=0, r='';
  t = t.replace(/./g, function (x) {
    if (s.lastIndexOf('p') >= j++ && x == 'roygbp'.charAt(i)) {
      i++;
      i %= 6;
      return 'n';
    } else {
      return 'e';
    }
  });
  return r;
}

Suggestions welcome!

Answer 17

Python 2, 254 bytes

Loops!

i=raw_input();r='roygbp';l='r';d=''
for n in i:
 if n==l:d+='n';l=r[(r.index(l)+1)%6]
 else:d+='e'
d=list(d)[::-1];p=(r.index(l)+1)%6;
for s in range(len(d)):
 if d[s]=='n'and p-1:d[s]='e';p-=1
if d.count('n')<6:print'e'*len(d)
else:print''.join(d[::-1])

Excuse the pun. :P