tło
Tak zwany „protokół pisuaru”, opisujący kolejność wybierania poszczególnych pisuarów w męskiej łazience, był omawiany w wielu miejscach. Jedna wersja jest podana w tym poście na blogu xkcd . To pytanie dotyczy niewielkiej zmienności:
Rozmieszczenie : n pisuarów w linii.
Protokół : każda nowa osoba wybiera jeden z pisuarów najbardziej odległych od już używanych.
Pamiętaj, że nie nakłada to żadnych ograniczeń na to, który pisuar wybiera pierwsza osoba.
Aktualizacja : Sekwencja liczby różnych sposobów wyboru n pisuarów zaczyna się od 1, 2, 4, 8, 20 ... Zauważ, że to nie to samo co OEIS A095236 , które opisuje nieco bardziej rygorystyczne ograniczenia niż w tym pytanie.
Zadanie
Biorąc pod uwagę liczbę całkowitą n od 0 do 10, wyprowadzaj (w dowolnej kolejności) wszystkie możliwe porządki, w których n ludzi może zajmować n pisuarów. Każde zamówienie powinno być wydrukowane jako ostateczne ustawienie: ciąg cyfr reprezentujących ludzi (1-9 dla pierwszych 9 osób, 0 dla dziesiątej), zaczynając od pisuaru najbardziej na lewo, z opcjonalnymi niealfanumerycznymi separatorami między (ale nie wcześniej lub po) cyfrach. Na przykład następujące dane wyjściowe są poprawne:
>> 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
Możesz napisać program lub funkcję, przyjmując dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji. Wyniki należy wydrukować do STDOUT (lub najbliższej alternatywy).
Punktacja
Najkrótszy kod wygrywa. Obowiązują standardowe warunki.
źródło
span
długości 1, gdzie dostępna jestspan
długość 2. Nagle udało mi się pomylić. Wygląda na to, że PO jest celowo uzyskiwane z linku, a zatem link należy śledzić?Odpowiedzi:
Pyth,
5351To jest podejście iteracyjne. Biorąc pod uwagę możliwe częściowo wypełnione uporządkowane zestawy lokalizacji, znajdujemy wszystkie optymalne dalsze lokalizacje, a następnie generujemy odpowiednią listę lokalizacji i powtarzamy.
Wyniki są generowane w formie
[<first person's location>, <second person's location> ...]
, a następnie przekształcane w pożądany format.MhSm^-dG2H
definiuje funkcję pomocnika, która określa minimalne odległości od danego przeciągnięcia do zajętego przeciągnięcia (kwadrat). Zabawne jest, że separator jest bezpłatny.Przykładowy przebieg.
Wyjaśnienie:
Po pierwsze, funkcja pomocnika
g
, która znajduje minimalną kwadratową odległość między G i dowolną wartością w H.Następnie znajdujemy maksymalne położenie nad pisuarem minimalnej kwadratowej odległości między tym pisuarem a dowolnym zajętym pisuarem:
(
Q
jest wejściem.)d
w tym przypadku jest to lista zajętych pisuarów, podczas gdyb
iteracja dotyczy lokalizacji pisuarów.Następnie znajdujemy wszystkie lokalizacje pisuaru, których minimalna kwadratowa odległość od najbliższego zajmowanego pisuaru jest równa maksymalnej wartości podanej powyżej.
Następnie wygenerujemy listy lokalizacji pisuarów utworzone przez dodanie do powyższych pozycji pisuaru
d
. Zrobimy to dla każdej poprzedniej listy lokalizacji pisuaru, rozszerzając w ten sposób listy z długościN
doN+1
.G
to lista legalnych list zajętych lokalizacji pisuarów o danej długości.Następnie zastosujemy powyższe wyrażenie wielokrotnie, aby wygenerować pełną listę list zajętych lokalizacji pisuaru.
u
, funkcja redukująca, robi to dokładnie tyle razy, ile jest elementów w drugim argumencie.Konwersja z powyższego przedstawienia, który przechodzi
[<1st location>, <2nd location>, ... ]
do pożądanej postaci wyjściowej[<person in slot 1>, <person in slot 2>, ... ]
. Następnie formularz wyjściowy jest łączony z ciągiem wyjściowym i drukowany. Drukowanie jest niejawne.źródło
kajsdlkas^23asdjkla1lasdkj~JZasSSA
- prawie połowa wielkości.Pyth,
757167Rekurencyjne rozwiązanie kombinatoryczne.
Jest to dość bezpośrednie tłumaczenie z tego rozwiązania Python:
źródło
C,
929878 bajtówTo jest potwór, chłopaki. Przepraszam.
Definiuje 3 funkcje,
f(int*,int)
,P(int*,int,int,int,int)
, iL(int)
. WywołajL(n)
i wyśle do STDOUT.Dane wyjściowe dla
n=5
:Aktualizacja: usunąłem separatory i poprawiłem kod. Stary kod nie tylko nie powiódł się dla n = 7 +, ale w ogóle nie wypisał niczego dla n = 10 (ups!). Dokładniej przetestowałem tę grupę. Obsługuje teraz wejście do n = 13 (chociaż
"%d"
należy zmienić na,"%x"
aby drukowało w systemie szesnastkowym). Wielkość wkładu zależy odsizeof(long)
i zakłada się, że jest to8
w praktyce.Oto wyjaśnienie, jak to działa i dlaczego istnieje takie dziwne ograniczenie:
Były one często używane, więc definiujemy je, aby zaoszczędzić kilka bajtów:
typedef unsigned long U; typedef unsigned char C;
Oto
f
:f
przyjmuje tablicę liczb całkowitych wielkościn
in
siebie. Jedynym sprytnym bitem jest to, że zwraca anunsigned long
, który jest konwertowany nachar[8]
funkcję wywołującą. Każdy znak w tablicy jest zatem ustawiony0xFF
na indeks lub na indeks wskazujący na prawidłowy pisuar dla następnej osoby. Ponieważn<10
nigdy nie potrzebujemy więcej niż 5 bajtów do przechowywania każdego ważnego pisuaru, którego może użyć następna osoba.Oto
P
:P
przyjmuje tablicęu
rozmiarów, wn
której ustawiony jest dokładnie jeden element1
, a pozostałe są0
. Następnie wyszukuje i drukuje każdą możliwą kombinację rekurencyjnie.Oto
L
:L
po prostu wywołujeP
n
czasy z różnymi pozycjami początkowymi za każdym razem.Dla zainteresowanych ta (mniej golfa)
f
wygeneruje sekwencję w A095236 .źródło
14352
środka osoba nr 1 wybrała pisuar najbardziej na lewo. Osoba # 2 wybrała najbardziej prawą, która następnie zmusiła # 3 do przejścia na środek. To nie liczba pobranego pisuaru, która powinna zostać wydana.Python 2, 208
Podejście rekurencyjne.
źródło
JavaScript (ES6) 153
160 169Edytuj za pomocą Math.min, aby znaleźć (oczywiście) maksymalną odległość: usprawniony kod i 16 zapisanych bajtów.
Wyszukiwanie rekurencyjne, może pracować z n> 10, wystarczy usunąć% 10 (i być przygotowanym na czekanie, aż konsola rozwija wszystkie dane wyjściowe).
Używam pojedynczej tablicy do przechowywania używanego gniazda (liczby dodatnie) lub bieżącej odległości od najbliższego gniazda (liczby ujemne tak
<
i>
zamieniane są w kodzie).Bez golfa
Przetestuj w konsoli Firefox / FireBug
źródło
Mathematica,
123104źródło
n~f~s~Join~{#}
stanie sięJoin[f[n,s],{#}]
.MATLAB, 164
źródło
Perl, 174
Niezbyt krótki, ale zabawny. Nie liczę
use feature 'say';
do całkowitej bajtu.Gra w golfa:
źródło
C, 248 bajtów
Ten kod używa algorytmu rekurencyjnego do generowania pożądanego wyniku.
Rozszerzony:
źródło
Bash,
744674 bajtyTo wciąż za długo :). Używam ciągu znaków do reprezentowania rzędu pisuarów i algorytmu zalewania, aby znaleźć najbardziej odległe pisuary w każdej fazie rekurencji. Nieskluczony kod jest prawie oczywisty. Liczba pisuarów jest odczytywana z klawiatury.
Kod (golfowy):
Posługiwać się:
I bez golfa idzie:
źródło