Kod golfa najlepsza permutacja

14

Wyzwanie

Biorąc pod uwagę liczbę całkowitą n ≥ 4 , wyprowadzaj permutację liczb całkowitych [0, n-1] z tą właściwością, że nie ma obok siebie dwóch kolejnych liczb całkowitych. Wartość permutacji pito suma abs(pi[i] - i)wszystkich wskaźników i.

Przykłady

  • (1, 3, 0, 2) ma wartość 6
  • (0, 2, 4, 1, 3) ma wartość 6
  • (0, 2, 4, 1, 3, 5) ma wartość 6
  • (0, 2, 4, 1, 5, 3, 6) ma wartość 8

Wynik Twojej odpowiedzi

Wynik Twojej odpowiedzi to suma wartości permutacji n = 4 .. 14plus liczba bajtów zajętych przez kod. Im niższy wynik, tym lepiej. Twój kod musi dawać prawidłowe dane wyjściowe dla wszystkich tych wartości n.

Musisz być w stanie uruchomić przesyłanie do ukończenia na swoim komputerze.

W przypadku remisu decydujący będzie czas ostatniej edycji, który spowodował odpowiedni wynik.

Czy to nie to samo pytanie, co to ?

Odpowiedzi na połączone pytanie nie będą konkurencyjne dla tego pytania, ponieważ nie podejmują żadnych wysiłków w celu optymalizacji wartości permutacji. Na przykład n=10permutacja [1, 3, 5, 7, 9, 0, 2, 4, 6, 8]podana w większości odpowiedzi daje wartość 30. Możesz zrobić znacznie więcej niż to.

W części dotyczącej permutacji ogólna optymalna wartość wynosi co najwyżej 120. (Dziękuję @Laikoni.) Natomiast odpowiedź Dennisa na poprzednie pytanie wynosi 222 . (Dziękujemy za @ user202729.)

Anush
źródło
4
@JoKing każdą odpowiedź można przenieść bez żadnych zmian, ale w tym wyzwaniu byłaby strasznie słaba. Opublikowanie tego kodu w tym wyzwaniu jest równoważne wysłaniu kodu z recenzji kodu do wyzwania golfowego.
Stewie Griffin
2
Mieszanie różnych ilości w partyturze może rzeczywiście stanowić problem. Odpowiedź z najlepszym algorytmem może być zazwyczaj przeniesiona na dowolny język, w którym to przypadku ocena ogranicza się do normalnego kodu golfowego.
Angs
4
Optymalne wartości są [6,6,6,8,10,12,12,12,14,16,18]dla wyniku 120. Co ciekawe, ten wzór można znaleźć w A078706 .
Laikoni
3
Ok, to zacznie się różnić od A078706z n=17, która może mieć wynik 20.
Laikoni
4
Potrafię zrozumieć to wyzwanie jasno i jednoznacznie. Jeśli nie zgadzasz się i głosujesz za zamknięciem, zostaw komentarz tutaj.
user202729

Odpowiedzi:

7

Galaretka , 36 34 33 32 31 30 bajtów, wynik: 120

Dzięki Dennis za -1 bajtów! (domyślnie przez naprawienie błędu Jelly, chociaż funkcja ta jest późniejsza niż wyzwanie)

ðRḟISị“Ƥ¿‘Ʋœ?$;@µ2x5~4¦ṁ_4$Ä’

Nowa funkcja: skumulowana suma ( Ä).

Wypróbuj online!

Użyj 1-indeksowania.

Zajmuje również czas liniowy.


Ten program C ++ generuje leksykograficznie najmniejszą permutację, zakładając, że | i - p i | ≤ szerokość (gdzie szerokość jest stałą zakodowaną na stałe) dla wszystkich 0 ≤ i <n , ze złożonością czasową około O (szerokość 2 × 2 2 × szerokość × n) (która jest tylko O (n) dla stałej szerokości ): Wypróbuj online !


W jaki sposób?

  1. Napisz program w C ++, który próbuje optymalnie rozwiązać problem.
  2. Obserwuj wzór. Zauważmy, że sekwencja wszystkich elementów oprócz 4 ostatnich jest prefiksem

    0 2 4 1 3 5 7 9 6 8 10 12 14 11 13 15 17 19 16 18 20 22 24 21 23 25 ...
    
  3. Oblicza różnicę przyrostową sekwencji.

    2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2 2 2 -3 2 2
    

    Zwróć uwagę na okres 5.

  4. Wdrożenie Jelly:

    • n-4 pierwsze elementy pochodzą z powyższej sekwencji. O (n) .
    • Dla 4 ostatnich elementów wystarczy brutalna siła wszystkich 24 możliwości . O (1) .

      (uwaga: nie używam już brutalnej siły wszystkich 24 możliwości z wersji 32-bajtowej)

użytkownik202729
źródło
Ach, poszedłeś z innym prefiksem do mnie. Mój zaczyna się 0 2 4 1 3 5 8 6i ma większy współczynnik rozgałęzienia, ale nie ma tak prostego wzorca.
Peter Taylor
7

CJam (60 bajtów + 120 = 180 punktów)

{_5/4*8e!961=7_)er<:A\,^e!{A\+}%{2ew::-:z1&!},{_$.-:z1b}$0=}

Zestaw testów online ze zintegrowanym ocenianiem

Przedłużenie do n = 24

Sekcja

{
  _5/4*        e# Work out how much of the hard-coded prefix to use
  8e!961=7_)er e# Prefix [0 2 4 1 3 5 8 6]
               e# I identified this by brute forcing up to n=10 and looking for patterns
               e# I then used the identified prefix [0 2 4 1] to brute-force further
  <:A          e# Take the desired prefix of the hard-coded array, and store a copy in A
  \,^e!        e# Generate all permutations of the values in [0 .. n-1] which aren't in A
  {A\+}%       e# Prepend A to each of them
  {            e# Filter...
    2ew::-     e#   Take each difference of two consecutive elements
    :z         e#   Find their absolute values
    1&         e#   Test whether 1 is among those absolute values
    !          e#   Reject if it is
  },
  {            e# Sort by...
    _$.-       e#   Take pairwise differences of permutation with the identity
    :z         e#   Absolute values
    1b         e#   Add them (by interpreting in base 1)
  }$
  0=           e# Take the first
}
Peter Taylor
źródło
Bardzo imponujące! Czekam na odkrycie, jak to zrobiłeś.
Anush
Czy jest optymalny aż do 24?
Anush
@Anush Według mojego programu, prawdopodobnie.
user202729
@Anush, nie udowodniłem tego, ale wierzę, że to prawdopodobne.
Peter Taylor
Jeszcze bardziej intryguje mnie twój algorytm!
Anush
6

Haskell , 146 + 89 punktów + bajty

f i|k<-mod i 4=scanl(+)1$take(i-2-k)(cycle[2,-3,2,3])++[[2],[2,2],[5,-3,2],[5,-3,2,2]]!!k

Powtarza wzór [1,3,0,2], ostatnie mod i 4elementy są ręcznie dostrojone.

Poprzedni algorytm (132 + 116):

f i=last$filter(\a->all(`elem`a)[0..i-1]).(!!(i-1)).iterate((\l->map((:l).(+head l))[-3,2,-2,3])=<<)$pure<$>[i-3..i]

Bruteforuje prawidłową liczbę skoków o długości ± 2 lub ± 3. Wybiera ostatni, który zawiera prawidłowe liczby, wydaje się działać dobrze i jest znacznie tańszy niż implementacja wyniku. Tio właśnie kończy czas przed ostatnim wynikiem, który wynosi 18.

Wypróbuj online!

Angs
źródło
2

Japt, 120 + 20 = 140

(Kopiowanie jednego z moich rozwiązań z drugiego wyzwania dałoby mi 227)

o á k_äa d¥1ÃñxÈaYÃg

Wypróbuj lub użyj tej wersji, aby sprawdzić wyniki. Obie wersje mogą zacząć się na ciebie pojawiać około 9.


Wyjaśnienie

o                        :Range [0,input)
  á                      :All permutations
    k_      Ã            :Remove sub-arrays that return true
      äa                 :  Get the consecutive absolute differnces
         d¥1             :  Do any equal 1?
               È  Ã      :Pass the integers in each remaining sub-array through a function
                aY       :  Get the absolute difference with the integer's index
              x          :Reduce by addition
             ñ           :Sort the main array by those values
                   ñ     :Return the first sub-array
Kudłaty
źródło
9
Musisz być w stanie uruchomić przesyłanie do ukończenia na swoim komputerze. ” Czy poważnie udało Ci się przetworzyć permutacje 87E9 14 elementów w ciągu dwóch godzin od opublikowania pytania?
Peter Taylor
3
Poza tym, weź pod uwagę, że Japt jest oparty na JavaScript, czy naprawdę może obsłużyć permutacje 87E9? To pytanie mówi, że tablica JavaScript może mieć długość co najwyżej ~ 4E9. Czy Japt ma funkcję generującą czy coś ... \
user202729
2

Rubin , 120 punktów + 112 106 91 82 bajtów

->n{(0...n).map{|a|a+(a+2)%5-([[],[],[0,4,3],[-1,4,4,4],[1,1,6,1]][n%5][a-n]||2)}}

Wypróbuj online!

Sekwencja jest w zasadzie (a-2)+(a+2)%5.

Jeśli n mod 5 nie jest równy 0 lub 1, ostatnie 3 lub 4 elementy są różne.

Jest to wciąż na wpół zakodowane, zawsze znajduje najlepsze rozwiązanie, może może być trochę bardziej golfa, ale zabrakło mi pomysłów.

GB
źródło
1

JavaScript (Node.js) , wynik 148 + 109 73 bajtów

n=>[...Array(n)].map(_=>l=!m|l>n%5+2&&l>m+2?[+m,m=l+2][0]:l+2,m=n>4,l=~m)

Wypróbuj online! Objaśnienie: lśledzi ostatnią wygenerowaną liczbę i mśledzi kolejną liczbę przeciwnej parzystości do l; po lprzekroczeniu m+2zmienne są wymieniane. Korekta jest wykonywana na początku sekwencji, aby sekwencje, których długości nie są wielokrotnościami 5, nie pomijały żadnych liczb, i dokonano innej korekty n=4.

Neil
źródło