16
1
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
4"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? – ceased to turn counterclockwis – 2012-06-28T07:50:37.913
1I 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 --- ex-moderator kitten – 2012-06-28T14:37:26.230
@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 – 2012-06-28T20:27:45.570
@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 --- ex-moderator kitten – 2012-06-28T20:32:38.573
@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 – 2012-06-28T20:37:49.770
@TomDignan, is it OK to have the internal representation of the nut be those strings you passed in? That portion of the question is quite unclear. – boothby – 2012-06-28T20:39:10.457
@boothby yes -- represent the nut any way as long as you have the same number of unique nuts – Thomas Dignan – 2012-06-29T00:10:32.070
@leftaroundabout -- I may have been overly verbose, as boothby notes, the strings are a fine representation (for any language I can think of) but due to the fact that they take up so many characters, and this is code golf, the use of integer codes is permitted to save chars – Thomas Dignan – 2012-06-29T00:11:59.683
1I 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. – Brad Gilbert b2gills – 2015-11-19T22:18:17.357@BradGilbertb2gills makes me want to try perl6 – Thomas Dignan – 2015-11-27T02:05:40.850
I really wanted to know if it was alright if I added an example that followed that pattern. – Brad Gilbert b2gills – 2015-11-28T01:29:30.750
An algorithm that finds all permutations without repeating is possible and deterministic. Add checking for success on each and it is still deterministic. And, a PRING plus a test that terminates—do you (@dmckee) also call that nondeterministic? For me, a predictable sequence is deterministic even if infinitely long. – WGroleau – 2018-05-14T08:13:01.353
@WGroleau I think you directed that at the wrong person. – dmckee --- ex-moderator kitten – 2018-05-14T16:30:57.980
You say a PRNG is not deterministic because it doesn't terminate. I ask whether you say one that does terminate is deterministic. (I say both are deterministic in that both have repeatable and predictable sequences.) – WGroleau – 2018-05-14T19:57:58.693
@WGroleau You've misreading the history. I'm not the one who said that. – dmckee --- ex-moderator kitten – 2018-05-16T17:31:25.553
oops, looked at the wrong end of the comment. It was actually @boothby Mea culpa. – WGroleau – 2018-05-16T22:10:32.627