Desafío

Dado un entero n ≥ 4 , genera una permutación de los enteros [0, n-1] con la propiedad de que no hay dos enteros consecutivos uno al lado del otro. El valor de una permutación pies la suma de abs(pi[i] - i)todos los índices i.

Ejemplos

• (1, 3, 0, 2) tiene valor 6
• (0, 2, 4, 1, 3) tiene valor 6
• (0, 2, 4, 1, 3, 5) tiene valor 6
• (0, 2, 4, 1, 5, 3, 6) tiene valor 8

Puntuación de tu respuesta

El puntaje de su respuesta es la suma de los valores de sus permutaciones para n = 4 .. 14más el número de bytes que toma su código. Cuanto más bajo sea el puntaje, mejor. Su código debe dar una salida válida para todos esos valores de n.

Debe poder ejecutar su envío hasta su finalización en su máquina.

En caso de empate, el momento de la última edición que resultó en la puntuación relevante será el decisivo.

¿No es esta la misma pregunta que esta? ?

Las respuestas a la pregunta vinculada no serán competitivas para esta pregunta ya que no hacen ningún esfuerzo para optimizar el valor de una permutación. Por ejemplo para n=10, la permutación[1, 3, 5, 7, 9, 0, 2, 4, 6, 8] dada por la mayoría de las respuestas allí da un valor de 30. Puedes hacerlo mucho mejor que eso.

Para la parte de permutación de la pregunta, el valor óptimo general es como máximo 120. (Gracias a @Laikoni.) Mientras que la respuesta de Dennis a la pregunta anterior es 222 . (Gracias a @ user202729.)

Gelatina , 36 34 33 32 31 30 bytes, resultado: 120

¡Gracias a Dennis por -1 byte! (implícitamente arreglando un error Jelly, aunque la característica es posterior al desafío)

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

Nueva característica: suma acumulada ( Ä).

Pruébalo en línea!

Utilice la indexación 1.

Toma tiempo lineal, también.

Este programa C ++ genera la permutación lexicográficamente más pequeña, suponiendo que | i - p _i | ≤ ancho (donde el ancho es una constante codificada) para todos 0 ≤ i <n , con una complejidad temporal de O (ancho ² × 2 ^{2 × ancho} × n) (que es solo O (n) para ancho fijo ): Pruébelo en línea !

¿Cómo?

1. Escriba un programa en C ++ que intente resolver el problema de manera óptima.

2. Observa el patrón. Observamos que la secuencia de todos los elementos, excepto los 4 últimos, es un prefijo de

   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. Calcula la diferencia incremental de la secuencia.

   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
   

   Tenga en cuenta el período 5.

4. La implementación de Jelly:

   • Los primeros elementos n-4 se toman de la secuencia anterior. O (n) .

   • Para 4 últimos elementos, solo fuerza bruta las 24 posibilidades . O (1) .

     (nota: ya no fuerza bruta las 24 posibilidades de la versión de 32 bytes)

CJam (60 bytes + 120 = 180 puntaje)

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

Conjunto de pruebas en línea con puntuación integrada

Extensión hasta n = 24

Disección

{
  _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 puntaje + bytes

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

Repite el patrón [1,3,0,2], los últimos mod i 4elementos se ajustan a mano.

Algoritmo anterior (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]

Fuerza bruta el número correcto de saltos de longitud ± 2 o ± 3. Selecciona el último que tiene los números correctos, parece funcionar bien y es mucho más barato que implementar la puntuación. Tio acaba el tiempo antes del último puntaje, que es 18.

Pruébalo en línea!

Japt, 120 + 20 = 140

(Copiar una de mis soluciones del otro desafío me hubiera marcado 227)

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

Pruébelo o use esta versión para verificar los puntajes. Ambas versiones pueden comenzar a arruinarte alrededor de las 9.

Explicación

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

Ruby , puntaje 120 + 112106 91 82 bytes

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

Pruébalo en línea!

La secuencia es básicamente (a-2)+(a+2)%5.

Si n mod 5 no es 0 o 1, los últimos 3 o 4 elementos son diferentes.

Esto todavía está medio codificado, siempre encuentra la mejor solución, tal vez podría jugar un poco más, pero me he quedado sin ideas.

JavaScript (Node.js) , 148 puntaje + 109 73 bytes

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)

Pruébalo en línea! Explicación: lrealiza un seguimiento del último número generado y mrealiza un seguimiento del siguiente número de la paridad opuesta a l; una vez que lexcede m+2las variables se intercambian. Se realiza un ajuste al comienzo de la secuencia para que las secuencias cuyas longitudes no sean múltiplos de 5 no pierdan ningún número, y se realiza otro ajuste n=4.