Fixing a Froot Loop Necklace 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.
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''&lt;.{&lt;/"&amp;~"&amp;~"&amp;&lt;_.&gt;/{.\.....~..&amp;.&gt;}&lt;.._...=.&gt;\&lt;=..}.|&gt;'%&lt;}|\.._\..&gt;....\.}.&gt;&lt;.|\{{*&lt;.&gt;,&lt;.&gt;/.\}/.&gt;...\'/../==.|....|./".&lt;_&gt;){{&lt;\....._&gt;\'=.|.....&gt;{&gt;)&lt;._\....&lt;..\..=.._/}\~&gt;&lt;.|.....&gt;e''\.&lt;.}\{{\|./&lt;../e;*\.@=_.~&gt;&lt;.&gt;{}&lt;&gt;&lt;;.(~.__..&gt;\._..&gt;'"n{{&lt;&gt;{&lt;...="&lt;.&gt;../


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 ' ' &lt; .
        { &lt; / " &amp; ~ " &amp; ~ " &amp; &lt;
       _ . &gt; / { . \ . . . . . ~
      . . &amp; . &gt; } &lt; . . _ . . . =
     . &gt; \ &lt; = . . } . | &gt; ' % &lt; }
    | \ . . _ \ . . &gt; . . . . \ . }
   . &gt; &lt; . | \ { { * &lt; . &gt; , &lt; . &gt; /
  . \ } / . &gt; . . . \ ' / . . / = = .
 | . . . . | . / " . &lt; _ &gt; ) { { &lt; \ .
  . . . . _ &gt; \ ' = . | . . . . . &gt; {
   &gt; ) &lt; . _ \ . . . . &lt; . . \ . . =
    . . _ / } \ ~ &gt; &lt; . | . . . . .
     &gt; e ' ' \ . &lt; . } \ { { \ | .
      / &lt; . . / e ; * \ . @ = _ .
       ~ &gt; &lt; . &gt; { } &lt; &gt; &lt; ; . (
        ~ . _ _ . . &gt; \ . _ . .
         &gt; ' " n { { &lt; &gt; { &lt; .
          . . = " &lt; . &gt; . . /


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 { / . . . . . . .
             . . . . . . . . . . . . . . . . . . . . .
            . . . . . . . . . . . . . . . . . . . . . .
           . . . . . . . . &gt; . . . . &lt; . . . . . . . . .
          . . . . . . . . . . . . . . &gt; . . ) &lt; . . . . .
         . . . . . . . . . . / = { { &lt; . . . . ( . . . . .
        . . . . . . . . . . . ; . . . &gt; . . . . . . . . . &lt;
       . . . . . . . . . . . . &gt; &lt; . / e ; * \ . . . . . . .
      . . . . . . . . . . . . @ . } . &gt; { } &lt; . . | . . . . .
     . . . . . / } \ . . . . . . . &gt; &lt; . . . &gt; { &lt; . . . . . .
    . . . . . . &gt; &lt; . . . . . . . . . . . . . . . | . . . . . .
   . . . . . . . . _ . . &gt; . . \ \ " ' / . . . . . . . . . . . .
  . . . . . . \ { { \ . . . &gt; &lt; . . &gt; . . . . \ . . . . . . . . .
 . &lt; . . . . . . . * . . . { . &gt; { } n = { { &lt; . . . / { . \ . . |
  . &gt; { { ) &lt; . . ' . . . { . \ ' &lt; . . . . . _ . . . &gt; } &lt; . . .
   | . . . . &gt; , &lt; . . . e . . . . . . . . . . . . . = . . } . .
    . . . . . . . &gt; ' % &lt; . . . . . . . . . . . . . &amp; . . . | .
     . . . . _ . . } . . &gt; } } = ~ &amp; " ~ &amp; " ~ &amp; " &lt; . . . . .
      . . . \ . . &lt; . . . . . . . . . . . . . . . . } . . . .
       . \ . . . . . . . . . . . . . . . . . . . . . . . &lt; .
        . . . . | . . . . . . . . . . . . . . . . . . = . .
         . . . . . . \ . . . . . . . . . . . . . . . . / .
          . . . . . . &gt; . . . . . . . . . . . . . . . . &lt;
           . . . . . . . . . . . . . . . . . . . . . . .
            _ . . . . . . . . . . . . . . . . . . . . .
             . . . . . . . . . . . . . . . . . . . . .
              . . . . . . . . . . . . . . . . . . . .
               . . . . . . . . . . . . . . . . . . .
                . . . . . . . . . . . . . . . . . .
                 . . . . . . . . . . . . . . . . .


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:


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

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.