Tell me more ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 4 down vote favorite

Input:

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
Macadamia
Mamoncillo
Maya nut
Mongongo
Oak acorns
Ogbono nut
Paradise nut
Pili nut
Pistachio
Walnut

Output:

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!

share|improve this question
3  
"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? – leftaroundabout Jun 28 '12 at 7:50
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. – dmckee♦ Jun 28 '12 at 14:37
@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. – boothby Jun 28 '12 at 20:27
@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. – dmckee♦ Jun 28 '12 at 20:32
@dmckee, forgive me, but I'm a mathematician, so we may never see eye to eye here. With a fixed PRNG, it isn't an algorithm because valid inputs result in a nonterminating condition. – boothby Jun 28 '12 at 20:37
show 3 more comments

3 Answers

up vote 8 down vote accepted

GolfScript, 42 41 37 38 characters

~.`{\`{=}+%1-,}+$.,)2//zip[]*.2<..&=*p

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

share|improve this answer
1  
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. – Peter Taylor Jun 28 '12 at 18:03
@PeterTaylor, cool. Works for me. – boothby Jun 29 '12 at 7:39
This crashes on input ["walnut"] in the compare-the-first-two section. – Peter Taylor Jun 29 '12 at 21:21
@PeterTaylor You're right. I'll have to work on that corner case. – Howard Jun 30 '12 at 5:04
up vote 4 down vote

GolfScript, 32 chars

~:x{]x\-,}$.,)2//zip[]*.2<..&=*`

Same input and output format as Howard's solution.

share|improve this answer
I had the same idea on the sort part but didn't code it up yet :-) Good work! – Howard Jun 30 '12 at 5:00
up vote 1 down vote

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

Example:

macadamia walnut walnut pistachio walnut

group (</.]):

macadamia walnut walnut walnut pistachio

sort (\:#&.>):

walnut walnut walnut macadamia pistachio

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

walnut macadamia walnut pistachio walnut
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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