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.)

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 × 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)

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
}

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!

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

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.

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.