Code Golf: Mischen Sie die Nüsse so, dass sich keine der gleichen Nüsse berührt

16

Eingang:

Die Eingabe ist eine zufällige Anordnung von Nüssen (in Ihrer Sprache), die möglichen Nüsse folgen. In Ihrem Programm muss jede Art von Mutter dargestellt werden können, z. B. ein ganzzahliger Code. Das Programm muss in der Lage sein, ein Array beliebiger Größe und Konfiguration von Muttern zu verarbeiten.

Mögliche Muttern:

Kola nut
Macadamia
Mamoncillo
Maya nut
Mongongo
Oak acorns
Ogbono nut
Paradise nut
Pili nut
Pistachio
Walnut

Ausgabe:

Die Ausgabe muss so sortiert sein, dass keine benachbarten Muttern der gleichen Art vorhanden sind. Ist dies nicht möglich, sollte die Ausgabe ein leeres Array sein.

Beispieleingabe (vereinfacht):

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

Beispielausgabe:

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

Lösungen können das Array nicht einfach mischen, bis es zufällig eindeutig wird. Die Art muss deterministisch sein

Gemischte Nüsse?  Ich sehe zwei sich berührende Mandeln!

Thomas Dignan
quelle
4
"Ihr Programm muss eine Möglichkeit haben, jede Art von Nuss darzustellen, z. B. einen Integer-Code." Warum ist das so? - "Das Array darf nicht einfach gemischt werden, bis es zufällig eindeutig wird. Die verwendete Sortierung muss deterministisch sein." Ein Shuffle kann immer noch deterministisch sein. Wollen Sie nur die zeitliche Komplexität des Programms einschränken?
Hört auf, gegen den Uhrzeigersinn am
1
Ich muss mit @leftaroundabout einverstanden sein, dass das Verbieten eines bestimmten Algorithmus ohne einen sehr guten Grund albern ist. Eines der lohnendsten Dinge bei solchen Code-Spielen ist genau die Vielfalt der Methoden, die angewendet werden.
DMCKEE
@dmckee, ich denke, die Anforderung, dass der Algorithmus deterministisch ist, ist vernünftig - wenn der RNG fehlerhaft ist oder die Eingabe ziemlich lang ist, kann eine nicht deterministische Lösung möglicherweise nicht beendet werden.
Stand
@boothby. Meh. Ich bin Teilchenphysiker. Monte Carlo ist ein wichtiges Instrument für sich. Außerdem ist es deterministisch , wenn ich einen festen PRNG und einen festen Samen wähle .
dmckee
1
Ich glaube, ich habe ein Beispiel gefunden, das mehrere Lösungen enthält, bei einigen Antworten jedoch möglicherweise keine gefunden werden kann. Kann ich es hinzufügen? (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) kann ebenfalls zum Versagen führen.
Brad Gilbert b2gills

Antworten:

8

GolfScript, 42 41 37 38 Zeichen

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

Der Code erwartet eine Eingabe an STDIN und gibt das Ergebnis an STDOUT aus, zB:

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

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

Das Skript wurde länger als erwartet, aber ich nehme an, dass es Raum für Verbesserungen gibt.

Bearbeiten: Der Fall einer Liste mit einem einzelnen Element kostet mich 1 Zeichen (der beste Vergleich, den ich finden konnte, ist der gleiche wie bei Peter).

Howard
quelle
1
Ich hatte mich noch nicht hingesetzt, um dies umzusetzen, aber $.,)2//zipgenau das hatte ich vor. Meine Interpretation der Spezifikation war, dass sie Eingaben in den Stapel aufnehmen und auf dem Stapel belassen könnte, also sollten wir vielleicht auf eine Klärung drängen.
Peter Taylor
@ PeterTaylor, cool. Funktioniert bei mir.
Stand
Dies stürzt bei der Eingabe ["walnut"]im Abschnitt "Compare the First Two" ab.
Peter Taylor
@PeterTaylor Du hast recht. Ich werde an diesem Eckfall arbeiten müssen.
Howard
6

GolfScript, 32 Zeichen

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

Gleiches Eingabe- und Ausgabeformat wie Howards Lösung.

Peter Taylor
quelle
Ich hatte die gleiche Idee bezüglich des Sortierteils, habe sie aber noch nicht kodiert :-) Gute Arbeit!
Howard,
6

Brachylog v2, 10 Bytes

p.¬{s₂=}∨Ė

Probieren Sie es online!

Brute-Force-Lösung. (Dies ist eine Funktion, die erlaubt ist, weil die Herausforderung nicht "volles Programm" sagt.) Es ist auch meistens eine direkte Übersetzung der Spezifikation (die einzige feine Sache ist, dass ich es geschafft habe, die Dinge so anzuordnen, dass alle impliziten Einschränkungen in genau der angekommen sind richtige Stellen, so dass keine zusätzlichen Zeichen erforderlich sind, um sie zu disambiguieren).

Beachten Sie, dass dies ein allgemeiner Algorithmus zum Neuanordnen einer Liste ist, sodass sich keine zwei Elemente berühren. es kann Zeichenfolgendarstellungen der Elemente verarbeiten, und es kann auch ganzzahlige Codes verarbeiten. Es spielt also keine Rolle, wie "Ihr Programm jede Art von Nuss darstellen muss, z. B. einen Integer-Code". Anforderung aus der Frage wird interpretiert.

Erläuterung

p.¬{s₂=}∨Ė
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
ais523
quelle
1

J, 80 Zeichen

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

Nicht wirklich in der gleichen Liga wie Golfscript. Ich vermute, es gibt Gewinne zu erzielen, aber die 14 Zeichen, die benötigt werden, um die Liste in das Programm aufzunehmen, [;.1' ',1!:1[1sind ein großes Handicap.

Grundsätzlich nimmt das Programm die Liste auf, gruppiert ähnliche Elemente, sortiert nach Anzahl der Elemente in jeder Gruppe absteigend und wechselt die Ausgabe zwischen der ersten und der zweiten Hälfte der Liste. Der Rest, wenn der Code überflüssige Elemente entfernt und entscheidet, ob die Liste eine gültige Ausgabe ist (Ausgabe unendlich, _wenn dies nicht der Fall ist).

Beispiel:

macadamia walnut walnut pistachio walnut

Gruppe (</.]):

macadamia walnut walnut walnut pistachio

sortieren (\:#&.>):

walnut walnut walnut macadamia pistachio

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

walnut macadamia walnut pistachio walnut
Gareth
quelle
0

Jelly , 14 Bytes

Ġz0UẎḟ0ịµẋ⁻ƝẠ$

Probieren Sie es online!

Die letzten 6 Bytes können entfernt werden, wenn wir undefiniertes Verhalten für ungültige Eingaben haben können.

Erik der Outgolfer
quelle
0

Stax , 10 Bytes

│éÿ∞å[zàL⌂

Führen Sie es aus und debuggen Sie es

Hier ist das gleiche Programm entpackt, ungolfed und kommentiert.

|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

Führen Sie dieses aus

rekursiv
quelle