Rozważ permutację wartości całkowitych od 1
do N
. Np. Ten przykład dla N = 4
:
[1, 3, 4, 2]
Będziemy rozważać tę listę być cykliczne, takie, że 1
i 2
są traktowane jako sąsiadujące. Jedną wielkością, którą możemy obliczyć dla takiej listy, jest całkowita kwadratowa różnica sąsiednich wartości:
(1-3)² + (3-4)² + (4-2)² + (2-1)² = 10
Twoim zadaniem jest znalezienie permutacji, która maksymalizuje tę ilość, biorąc pod uwagę dodatnią liczbę całkowitą N
. W przypadku N = 4
powyższego przykładu nie jest optymalny (w rzeczywistości jest minimalny). Możemy osiągnąć całkowitą kwadratową różnicę o 18
następującej permutacji (jak również kilku innych):
[1, 4, 2, 3]
Twój algorytm musi działać w czasie wielomianowym (z N
). W szczególności nie można po prostu obliczyć całkowitej kwadratowej różnicy wszystkich permutacji.
Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).
Dane wyjściowe mogą być w dowolnym dogodnym, jednoznacznym, płaskim formacie lub w postaci łańcucha. Możesz zwrócić listę z wartościami od 0
do N-1
zamiast 1
do N
.
Obowiązują standardowe zasady gry w golfa .
Dane testowe
Istnieje ładne analityczne rozwiązanie tego problemu. Np. Wszystkie prawidłowe rozwiązania N = 10
są równoważne z następującą listą (do cyklicznych przesunięć i cofnięć):
[7, 5, 6, 4, 8, 2, 10, 1, 9, 3]
Nie chcę ujawniać zbyt wiele poza tym (chociaż prawdopodobnie wystarczy, aby wymyślić wzór), więc zamiast podawać więcej przykładów, możesz sprawdzić, czy wyniki mają następujące całkowite kwadratowe różnice dla danej N
:
N Total squared difference
1 0
2 2
3 6
4 18
5 36
6 66
7 106
8 162
9 232
10 322
33 11936
100 333202
333 12308236
1000 333332002
To jest pozycja OEIS A064842 (która również zawiera odniesienie do artykułu zawierającego rozwiązanie tego wyzwania, jeśli utkniesz).
źródło
(i<n/2||n%2)^i%2?i+1:n-i
.Python2,
10598 bajtów7 bajtów zapisanych dzięki komentarzowi @Dennis
Wersja edytowana 58 bajtów
Wierzyłem już, że powinno być możliwe zrobienie tego w jednej linijce, ale logika była dla mnie zbyt złożona. Widząc odpowiedź JavaScript na @ @ user81655 i notację lambda w @Dennis Python-answer, podjąłem nową próbę.
Warunek jest równy
Niestety cały wysiłek związany z transformacją pozwala zaoszczędzić tylko
jedenbajt w porównaniu z bezpośrednim tłumaczeniem(i<n/2or n%2)!=i%2
logiki JavaScript.źródło
int()
wokół danych wejściowych. Możesz również umieścić ciało pętli for w tej samej linii cofor...
.Python,
5149 bajtówDzięki @xnor za grę w golfa z 2 bajtów!
Wypróbuj na Ideone .
Jak to działa
Jeśli i jest liczbą w [0, ..., n - 1] , to ~ i% n = - (i + 1)% n = - (i + 1) + n = (n - 1) - i , co oznacza, że odwzorowuje 0 na n - 1 , 1 na n - 2 i, ogólnie rzecz biorąc, j- ty element od lewej do j- ty od prawej.
Jak wyjaśniono w mojej odpowiedzi na Jelly , możemy skonstruować wynik, zerkając na niższą wartość spośród i i ~ i% n , i wybierz i, jeśli jest parzyste, i ~ i% n, jeśli jest nieparzyste. Osiągamy to w następujący sposób.
Jeśli minimalna jest równa,
min(i,~i%n)%-2
przyniesie 0 , więc w wyniku XORing i przyniesie I i obliczanie jej pozostałości modulo n powróci I .Jeśli minimum jest nieparzyste,
min(i,~i%n)%-2
da -1 , więc XOR wyniku za pomocą i da ~ i , więc całe wyrażenie ocenia się na ~ i% n zgodnie z potrzebą.źródło
(i^min(i,n+~i)%-2)%n
.PHP,
7776515049 bajtówWykorzystuje kodowanie ISO 8859-1.
Składanie pierwszej połowy tablicy w ten sposób:
N+1-index
(9, 7, 5)1, 9, 3, 7, 5
Jeśli chodzi o drugą połowę tablicy, najbardziej zewnętrzne wartości sumują się
N+1
, co oznacza, że można uzyskać odpowiednią prawą wartość, zN-[left value]
której znana jest już lewa wartość.Działaj w ten sposób (pokazuje to także całkowitą różnicę do kwadratu) (
-d
dodano tylko dla estetyki):echo
~ß
do uzyskania spacji.źródło
Python 2, 100
Wiem, że jest już odpowiedź na python, ale myślę, że mogłem to zrobić inaczej.
I jako dodatek do przetestowania całkowitego wyniku:
źródło
def t(x,n):return sum((x[i]-x[i-1])**2for i in range(n))
używa niejawnego zawijania ujemnych indeksów i oszczędza 4 bajty. Wiem, że nie był częścią konkursu. ;)CJam,
171514 bajtówJest to funkcja, która wyrzuca liczbę całkowitą n ze stosu i wypycha w zamian permutację [0… n-1] . Kod używa tego samego podejścia, co moja odpowiedź Jelly .
Wypróbuj online!
Jak to działa
źródło
LISP, 86 bajtów
Wejścia funkcji pozwalają wybrać wartości początkowe (m) i końcowe (n) sekwencji.
W celu przetestowania funkcji zgodnie z dostarczonymi próbkami, n jest ustalone na N, a m na 1.
Oto kod do testowania funkcji:
Wypróbuj na Ideone !
źródło
Julia, 39 bajtów
Wyświetla permutację 1: n . Permutacja 0: n-1 nie kosztuje ani nie oszczędza bajtów:
Ta ostatnia wersja jest bezpośrednim portem mojej odpowiedzi w języku Python .
źródło
ES6, 77 bajtów
Te
i&1
próbki cyfry od skrajności do środka.i&2
Dodaje je do początku lub końca wynik w parach.źródło
R,
11786 bajtówedytuj zastąpioną długą wersję buggy z implementacją algorytmu Jelly @Dennis
źródło