Input is a randomized array of nuts (in your language), the possible nuts follow. Your program must have a way of representing each kind of nut, such as an integer code. Program must be able to handle any size array of any configuration of nuts.

Possible Nuts:

Kola nut
Maya nut
Oak acorns
Ogbono nut
Paradise nut
Pili nut


Output must be the array sorted in such a fashion that there are no adjacent nuts of the same kind. If this is impossible, the output should be an empty array.

Example Input (simplified):

["walnut", "walnut", "pistachio"]

Example Output:

["walnut", "pistachio", "walnut"]

Solutions may not simply shuffle the array until it becomes unique by chance. The sort employed must be a deterministic one

Mixed nuts? I see two almonds touching!

  • 4
    \$\begingroup\$ "Your program must have a way of representing each kind of nut, such as an integer code" why is that? — "may not simply shuffle the array until it becomes unique by chance. The sort employed must be a deterministic one" a shuffle can still be deterministic. Do you just mean to impose a limit on the program's time complexity? \$\endgroup\$ Jun 28, 2012 at 7:50
  • 4
    \$\begingroup\$ I have to agree with @leftaroundabout forbidding a particular algorithm is silly without a very good reason. One of the most rewarding things about code games like this is exactly the variety of methods that get employed. \$\endgroup\$ Jun 28, 2012 at 14:37
  • 1
    \$\begingroup\$ @dmckee, I think the requirement that the algorithm be deterministic is reasonable -- if the RNG is faulty or the input fairly long, a nondeterministic solution may fail to terminate. \$\endgroup\$
    – boothby
    Jun 28, 2012 at 20:27
  • \$\begingroup\$ @boothby. Meh. I'm a particle physicist. Monte Carlo is a important tool in its own right. Moreover, If I choose a fixed PRNG and a fixed seed it is deterministic. \$\endgroup\$ Jun 28, 2012 at 20:32
  • 1
    \$\begingroup\$ I think I found an example that has several solutions, but may cause some answers to fail to find any of them. Can I add it? (5,4,4,3,3,2) perl6 -e 'my @a="aaaaabbbbccccdddee".comb;my @b = @a.pick(*) while @b.squish !== @a;say [~] @b' baedcbdacdecbabaca (3,3,2) may cause them to fail also. \$\endgroup\$ Nov 19, 2015 at 22:18

8 Answers 8


GolfScript, 42 41 37 38 characters


The code expects input on STDIN and prints result to STDOUT, e.g.:

> ["walnut" "walnut" "walnut" "macadamia" "pistachio"]
["walnut" "macadamia" "walnut" "pistachio" "walnut"]

> ["walnut" "walnut" "walnut" "macadamia" "walnut"]

The script became longer than expected but I suppose there is room for improvement.

Edit: The case of a list with a single item costs me 1 character (the best comparison I could come up with is the same as Peter's).

  • 1
    \$\begingroup\$ I hadn't sat down to implement this yet, but $.,)2//zip is exactly what I had in mind. My interpretation of the spec was that it could take input on the stack and leave it on the stack, so maybe we should push for clarification. \$\endgroup\$ Jun 28, 2012 at 18:03
  • \$\begingroup\$ @PeterTaylor, cool. Works for me. \$\endgroup\$
    – boothby
    Jun 29, 2012 at 7:39
  • \$\begingroup\$ This crashes on input ["walnut"] in the compare-the-first-two section. \$\endgroup\$ Jun 29, 2012 at 21:21
  • \$\begingroup\$ @PeterTaylor You're right. I'll have to work on that corner case. \$\endgroup\$
    – Howard
    Jun 30, 2012 at 5:04

GolfScript, 32 chars


Same input and output format as Howard's solution.

  • \$\begingroup\$ I had the same idea on the sort part but didn't code it up yet :-) Good work! \$\endgroup\$
    – Howard
    Jun 30, 2012 at 5:00

Brachylog v2, 10 bytes


Try it online!

Brute-force solution. (This is a function, allowed because the challenge does not say "full program".) It's also mostly a direct translation of the spec (the only real subtlety is that I managed to arrange things so that all the implicit constraints arrived in exactly the right places, thus not needing any extra characters to disambiguate them).

Note that this is a generic algorithm for rearranging any sort of list so that it does not have two touching elements; it can handle string representations of the elements, and it can handle integer codes just as well. So it doesn't really matter how the "Your program must have a way of representing each kind of nut, such as an integer code." requirement from the question is interpreted.


p            Find a permutation of {the input}
  ¬{   }     which does not have the following property:
    s₂         it contains a pair of adjacent elements
      =        that are equal
        ∨    {no constraint on what value the equal elements can have}
 .           If you find such a permutation, output it.
        ∨    If no permutation is found, ignore the input and
         Ė     {output} an empty list

Nibbles, 7 bytes (14 nibbles)


Systematically (non-randomly) finds all permutations of the input without adjacent identical nuts, and then returns the first of these (or an empty list if there aren't any).

 |               # filter
  ``p            # all permutations of 
     $           # the input list
                 # by 
      /      *   # fold-by-multiplication
       !         #   zip together
        >>$      #     list without first element
           @     #     the same list
            !    #     are elements equal?
/                # finally get first element

enter image description here

  • \$\begingroup\$ @Jacob This doesn't look like it's shuffling it, at least from the description. Rather, it's iterating over all possible permutations (same with the other answer) \$\endgroup\$
    – Jo King
    Feb 20, 2023 at 0:04
  • 1
    \$\begingroup\$ @Jacob JoKing - this indeed iterates non-randomly over all permutations. It's completely deterministic. \$\endgroup\$ Feb 20, 2023 at 6:38

Vyxal r, 12 8 bytes


Try it Online!

-4 thanks to @Steffan

Explanation (old)

I'll update it when I have time.

Ṗ¾wJλ:Ḣ=a¬;c  # Implicit input
Ṗ             # Permutations
 ¾wJ          # With an empty list appended
              # (In case there is no truthy item)
    λ     ;c  # First item such that:
     :Ḣ=      #  Adjacent elements are equal?
        a¬    #  None are true
              # Implicit output
  • 1
    \$\begingroup\$ @Jacob it's not shuffling the array until it becomes unique. \$\endgroup\$
    – The Thonnu
    Feb 20, 2023 at 7:16
  • \$\begingroup\$ 9 bytes: Ṗ¾wJ‡ÞǓ⁼c. I think there's a way to remove the ¾wJ and add something at the end to convert 0 to an empty list too. \$\endgroup\$
    – naffetS
    Feb 21, 2023 at 0:55
  • \$\begingroup\$ ah, well, you could do Ṗ‡ÞǓ⁼c¾∨ with r flag \$\endgroup\$
    – naffetS
    Feb 21, 2023 at 0:56
  • \$\begingroup\$ @Steffan thanks, updated \$\endgroup\$
    – The Thonnu
    Feb 21, 2023 at 6:45

J, 80 characters

]`_:@.(0<2&([:+/=/\))({.~-:@#),((],.|.)~>.@-:@#)<"1;(\:#&.>)(</.])[;.1' ',1!:1[1

Not really in the same league as Golfscript on this one. I suspect there are gains to be made, but the 14 characters needed just to get the list into the program [;.1' ',1!:1[1 is a major handicap.

Basically the program takes in the list, groups similar items together, sorts by number of items in each group descending, and alternates the output between the first half and the second half of the list. The rest if the code gets rid of extraneous items and decides if the list is valid output (outputting infinity _ if it isn't).


macadamia walnut walnut pistachio walnut

group (</.]):

macadamia walnut walnut walnut pistachio

sort (\:#&.>):

walnut walnut walnut macadamia pistachio

ravel ((],.|.)~>.@-:@#):

walnut macadamia walnut pistachio walnut

Jelly, 14 bytes


Try it online!

The last 6 bytes can be removed if we can have undefined behavior for invalid inputs.


Stax, 10 bytes


Run and debug it

Here's the same program unpacked, ungolfed, and commented.

|T      get all permutations
{       block to filter by
  :g_=  after dropping repeated elements, it's still equal
f       execute filter
|c      terminate and pop if falsy (no match)
hJ      take the first permutation, and join with spaces

Run this one


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.