Hintergrund
Das sogenannte "Urinal-Protokoll", das die Reihenfolge beschreibt, in der einzelne Urinale in einem Männerbad entnommen werden, wurde an mehreren Stellen erörtert. Eine Version finden Sie in diesem xkcd-Blogbeitrag . Diese Frage betrifft eine geringfügige Abweichung:
Anordnung : n Urinale in einer Reihe.
Protokoll : Jede neue Person wählt eines der Urinale aus, die am weitesten von den bereits verwendeten entfernt sind.
Beachten Sie, dass dies keine Einschränkungen dahingehend darstellt, welches Urinal von der ersten Person entnommen wird.
Update : Die Reihenfolge der verschiedenen Arten, wie n Personen n Urinale auswählen können, beginnt mit 1, 2, 4, 8, 20 ... Beachten Sie, dass dies nicht mit OEIS A095236 identisch ist , das geringfügig strengere Einschränkungen beschreibt Frage.
Aufgabe
Bei einer Ganzzahl n zwischen 0 und 10 werden (in beliebiger Reihenfolge) alle möglichen Reihenfolgen ausgegeben, in denen n Personen n Urinale belegen können. Jede Bestellung sollte als endgültige Anordnung gedruckt werden: eine Folge von Ziffern, die die Personen darstellen (1-9 für die ersten 9 Personen, 0 für die Zehnten), beginnend mit dem Urinal ganz links, mit optionalen nicht-alphanumerischen Trennzeichen zwischen (aber nicht vor) oder nach) den Ziffern. Beispielsweise sind die folgenden Ausgaben beide gültig:
>> 3
132
213
312
231
>> 4
1|3|4|2
1|4|3|2
3|1|4|2
4|1|3|2
2|3|1|4
2|4|1|3
2|3|4|1
2|4|3|1
Sie können ein Programm oder eine Funktion schreiben und Eingaben über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen. Die Ergebnisse sollten an STDOUT (oder die nächstgelegene Alternative) gesendet werden.
Wertung
Kürzester Code gewinnt. Es gelten die Allgemeinen Geschäftsbedingungen.
quelle
span
Länge 1, in der einespan
Länge 2 verfügbar ist. Ich habe es plötzlich geschafft, mich zu verwirren. Es scheint, dass das OP absichtlich von dem Link abgeleitet ist, und daher sollte dem Link gefolgt werden?Antworten:
Pyth,
5351Dies ist ein iterativer Ansatz. Bei eventuell teilweise ausgefüllten geordneten Ortssätzen finden wir alle optimalen weiteren Orte, erzeugen dann die entsprechende Ortsliste und wiederholen.
Die Ergebnisse werden im Formular generiert
[<first person's location>, <second person's location> ...]
und anschließend in das gewünschte Format umgewandelt.MhSm^-dG2H
definiert eine Hilfsfunktion, die die minimalen Abstände von einem bestimmten Stand zu einem besetzten Stand (im Quadrat) ermittelt. Amüsanterweise ist der Separator frei.Beispiellauf.
Erläuterung:
Erstens die Hilfsfunktion
g
, die den quadratischen Mindestabstand zwischen G und einem beliebigen Wert in H ermittelt.Als nächstes finden wir das Maximum über den Urinalpositionen des minimalen quadratischen Abstands zwischen diesem Urinal und irgendeinem belegten Urinal:
(
Q
ist der Eingang.)d
In diesem Fall wird die Liste der belegten Urinale angezeigt, währendb
über die Urinalpositionen iteriert wird.Als nächstes finden wir alle Urinalpositionen, deren quadratischer Mindestabstand zum nächsten belegten Urinal gleich dem oben gefundenen Maximalwert ist.
Als Nächstes generieren wir die Urinalstandortlisten, die durch Hinzufügen der oben gefundenen Urinalstandorte zu erstellt werden
d
. Wir werden dies für jede vorherige Liste von Urinalpositionen tun, wodurch die Listen von LängeN
zu Länge erweitert werdenN+1
.G
ist die Liste der legalen Listen besetzter Urinalstellen einer bestimmten Länge.Als nächstes werden wir den obigen Ausdruck wiederholt anwenden, um die vollständige Liste der Listen der besetzten Urinalstellen zu erzeugen.
u
Die Reduktionsfunktion tut genau dies, so oft Elemente in ihrem zweiten Argument enthalten sind.Konvertieren Sie von der obigen Darstellung
[<1st location>, <2nd location>, ... ]
in die gewünschte Ausgabeform[<person in slot 1>, <person in slot 2>, ... ]
. Anschließend wird das Ausgabeformular in die Ausgabezeichenfolge eingefügt und gedruckt. Drucken ist implizit.quelle
kajsdlkas^23asdjkla1lasdkj~JZasSSA
- fast halb so groß.Pyth,
75,71,67Rekursive kombinatorische Lösung.
Es ist eine ziemlich direkte Übersetzung aus dieser Python-Lösung:
quelle
C
929878 BytesDas ist ein Monster, Leute. Es tut uns leid.
Definiert 3 Funktionen
f(int*,int)
,P(int*,int,int,int,int)
undL(int)
. Rufen Sie aufL(n)
, und es wird an STDOUT ausgegeben.Ausgabe für
n=5
:Update: Ich habe Trennzeichen entfernt und den Code korrigiert. Der alte Code schlug nicht nur für n = 7 + fehl, sondern gab für n = 10 überhaupt nichts aus (oops!). Ich habe diesen Haufen gründlicher getestet. Es werden jetzt Eingaben von bis zu n = 13 unterstützt (obwohl
"%d"
geändert werden sollte,"%x"
damit hexadezimal gedruckt wird). Die Größe der Eingabe ist abhängig vonsizeof(long)
und wird8
in der Praxis angenommen.Hier ist eine Erklärung, wie es funktioniert und warum es so eine merkwürdige Einschränkung gibt:
Diese wurden häufig verwendet, daher definieren wir sie, um ein paar Bytes zu sparen:
typedef unsigned long U; typedef unsigned char C;
Hier ist
f
:f
nimmt eine Reihe von ganzen Zahlen der Größen
undn
sich. Das einzig clevere daran ist, dass es eine zurückgibtunsigned long
, diechar[8]
von der aufrufenden Funktion in eine umgewandelt wird . Jedes Zeichen in dem Array wird somit entweder auf0xFF
einen Index gesetzt oder auf einen Index, der auf ein gültiges Urinal für die nächste Person zeigt. Dennn<10
wir brauchen nie mehr als 5 Bytes, um jedes gültige Urinal aufzunehmen, das die nächste Person benutzen kann.Hier ist
P
:P
nimmt ein Array mitu
der Größe an, auf dasn
genau ein Element gesetzt ist1
, und der Rest ist0
. Es findet und druckt dann jede mögliche Permutation rekursiv.Hier ist
L
:L
ruft einfachP
n
mal mit unterschiedlichen startpositionen jedes mal auf.Für die Interessierten wird dies (weniger Golf)
f
die Sequenz in A095236 erzeugen .quelle
14352
Mittelwert Person # 1 wählte das Urinal ganz links. Person Nr. 2 wählte die am weitesten rechts stehende, die dann Nr. 3 in die Mitte zwang. Es ist nicht die Nummer des als nächstes entnommenen Urinals, die ausgegeben werden soll.Python 2, 208
Rekursiver Ansatz.
quelle
JavaScript (ES6) 153
160 169Bearbeiten Mit Math.min können Sie (natürlich) die maximale Entfernung ermitteln: Optimierter Code und 16 gespeicherte Bytes.
Rekursive Suche, kann mit n> 10 arbeiten, einfach% 10 entfernen (und warten, während die Konsole alle Ausgaben abrollt).
Ich verwende ein einzelnes Array, um den verwendeten Steckplatz (positive Zahlen) oder den aktuellen Abstand zum nächsten Steckplatz (negative Zahlen also
<
und>
im Code vertauscht) zu speichern .Ungolfed
Test In der Firefox / FireBug-Konsole
quelle
Mathematica,
123,104quelle
n~f~s~Join~{#}
wird werdenJoin[f[n,s],{#}]
.MATLAB, 164
quelle
Perl, 174
Nicht sehr kurz, aber lustig. Ich zähle nicht
use feature 'say';
auf die Bytesumme.Entgolft:
quelle
C 248 Bytes
Dieser Code verwendet einen rekursiven Algorithmus, um das gewünschte Ergebnis zu generieren.
Erweitert:
quelle
Bash,
744674 BytesDas ist noch viel zu lang :). Ich verwende eine Zeichenfolge, um die Reihe der Urinale darzustellen, und einen Flutungsalgorithmus, um die entferntesten Urinale in jeder Rekursionsphase zu finden. Der ungolfed Code ist fast selbsterklärend. Die Anzahl der Urinale wird von der Tastatur gelesen.
Code (Golf):
Verwenden:
Und ungolfed geht es:
quelle