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.
Kola nut Macadamia Mamoncillo Maya nut Mongongo Oak acorns Ogbono nut Paradise nut Pili nut Pistachio Walnut
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"]
["walnut", "pistachio", "walnut"]
Solutions may not simply shuffle the array until it becomes unique by chance. The sort employed must be a deterministic one