Considere una permutación de los valores enteros de 1
a N
. Por ejemplo, este ejemplo para N = 4
:
[1, 3, 4, 2]
Vamos a considerar que esta lista sea cíclico, de tal manera que 1
y 2
son tratados como adyacente. Una cantidad que podemos calcular para dicha lista es la diferencia al cuadrado total de los valores adyacentes:
(1-3)² + (3-4)² + (4-2)² + (2-1)² = 10
Su tarea es encontrar una permutación que maximice esta cantidad, dado un número entero positivo N
. En el caso del N = 4
ejemplo anterior, no es óptimo (de hecho, es mínimo). Podemos lograr una diferencia al cuadrado total de 18
con la siguiente permutación (así como varias otras):
[1, 4, 2, 3]
Su algoritmo debe ejecutarse en tiempo polinómico (de N
). En particular, no puede simplemente calcular la diferencia al cuadrado total de todas las permutaciones.
Puede escribir un programa o función, tomando la entrada a través de STDIN (o la alternativa más cercana), argumento de línea de comando o argumento de función y generando el resultado a través de STDOUT (o la alternativa más cercana), el valor de retorno de la función o el parámetro de función (out).
La salida puede estar en cualquier formato de cadena o lista conveniente, inequívoca y plana. Puede elegir devolver una lista con valores de 0
a en N-1
lugar de 1
a N
.
Aplican reglas estándar de código de golf .
Datos de prueba
Hay una buena solución analítica para este problema. Por ejemplo, todas las soluciones válidas N = 10
son equivalentes a la siguiente lista (hasta cambios cíclicos y reversión):
[7, 5, 6, 4, 8, 2, 10, 1, 9, 3]
No quiero revelar mucho más allá de eso (aunque probablemente sea suficiente para descubrir el patrón), por lo que en lugar de dar más ejemplos, puede verificar que sus resultados tengan las siguientes diferencias cuadradas totales para un determinado 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
Esta es la entrada OEIS A064842 (que también contiene una referencia a un documento con una solución a este desafío si está atascado).
fuente
(i<n/2||n%2)^i%2?i+1:n-i
.Python2,
10598 bytes7 bytes guardados gracias al comentario de @Dennis
Versión editada 58 bytes
Ya creía que debería ser posible hacerlo de una sola vez, pero la lógica era demasiado compleja para mí. Al ver la respuesta JavaScript de @ user81655 y la notación lambda en @Dennis Python-answer, le di una nueva oportunidad.
La condición es igual a
Desafortunadamente, todo el esfuerzo de transformación ahorra
unsolo byte en comparación con la traducción directa(i<n/2or n%2)!=i%2
de la lógica de JavaScript.fuente
int()
la entrada. Además, puede colocar el cuerpo del bucle for en la misma línea quefor...
.Python,
5149 bytes¡Gracias a @xnor por jugar 2 bytes!
Pruébalo en Ideone .
Cómo funciona
Si i es un número en [0, ..., n - 1] , entonces ~ i% n = - (i + 1)% n = - (i + 1) + n = (n - 1) - i , lo que significa que los mapas de 0 a n - 1 , 1 a n - 2 y, en general, el j ésimo elemento de la izquierda a la j ésimo desde la derecha.
Como se explica en mi respuesta de Jelly , podemos construir la salida mirando el valor más bajo entre i y ~ i% n , y elegir i si es par y ~ i% n si es impar. Logramos esto de la siguiente manera.
Si el mínimo es par,
min(i,~i%n)%-2
producirá 0 , entonces XORing el resultado con i producirá i , y calcular su módulo de residuo n devolverá i .Si el mínimo es impar,
min(i,~i%n)%-2
producirá -1 , por lo que XORing el resultado con i producirá ~ i , por lo que toda la expresión se evalúa a ~ i% n como se desee.fuente
(i^min(i,n+~i)%-2)%n
.PHP,
7776515049 bytesUtiliza la codificación ISO 8859-1.
Ensamblar la primera mitad de la matriz de esta manera:
N+1-index
(9, 7, 5)1, 9, 3, 7, 5
En cuanto a la segunda mitad de la matriz, los valores más externos se suman
N+1
, lo que significa que puede obtener el valor correcto correspondiente deN-[left value]
donde ya se conoce el valor izquierdo.Ejecutar así (esto también muestra la diferencia al cuadrado total) (
-d
agregado solo para la estética):echo
~ß
para producir un espacio.fuente
Pitón 2, 100
Sé que ya hay una respuesta de Python, pero creo que podría haberlo hecho de manera diferente.
Y como extra para probar la puntuación total:
fuente
def t(x,n):return sum((x[i]-x[i-1])**2for i in range(n))
usa la envoltura implícita de índices negativos y guarda 4 bytes. Lo sé, no era parte de la competencia. ;)CJam,
171514 bytesEsta es una función que saca un entero n de la pila y empuja una permutación de [0 ... n-1] a cambio. El código utiliza el mismo enfoque que mi respuesta Jelly .
Pruébalo en línea!
Cómo funciona
fuente
LISP, 86 bytes
Las entradas de la función permiten elegir los valores de inicio (m) y final (n) de la secuencia.
Para probar la función de acuerdo con las muestras proporcionadas, n se fija a N ym a 1.
Aquí el código para probar la función:
Pruébalo en Ideone !
fuente
Julia, 39 bytes
Esto imprime una permutación de 1: n . Una permutación de 0: n-1 no cuesta ni guarda bytes:
Esta última versión es un puerto directo de mi respuesta de Python .
fuente
ES6, 77 bytes
Las
i&1
muestras de los dígitos de los extremos hacia el centro. Losi&2
agrega al principio o al final del resultado en pares.fuente
R,
11786 bytesedit reemplazó la versión larga con errores con una implementación del algoritmo Jelly de @Dennis
fuente