Considere uma permutação dos valores inteiros de 1
a N
. Por exemplo, este exemplo para N = 4
:
[1, 3, 4, 2]
Consideraremos que esta lista é cíclica, de modo que 1
e 2
é tratada como adjacente. Uma quantidade que podemos calcular para essa lista é a diferença total quadrática dos valores adjacentes:
(1-3)² + (3-4)² + (4-2)² + (2-1)² = 10
Sua tarefa é encontrar uma permutação que maximize essa quantidade, dado um número inteiro positivo N
. No caso do N = 4
exemplo acima, não é o ideal (na verdade, é mínimo). Podemos alcançar uma diferença quadrática total 18
com a seguinte permutação (bem como várias outras):
[1, 4, 2, 3]
Seu algoritmo deve ser executado em tempo polinomial (de N
). Em particular, você não pode simplesmente calcular a diferença quadrática total de todas as permutações.
Você pode escrever um programa ou função, recebendo entrada via STDIN (ou alternativa mais próxima), argumento da linha de comando ou argumento da função e emitindo o resultado via STDOUT (ou alternativa mais próxima), valor de retorno da função ou parâmetro da função (saída).
A saída pode estar em qualquer formato conveniente, inequívoco, de lista simples ou de seqüência de caracteres. Você pode optar por retornar uma lista com valores de 0
para em N-1
vez de 1
para N
.
Aplicam-se as regras padrão de código de golfe .
Dados de teste
Existe uma boa solução analítica para esse problema. Por exemplo, todas as soluções válidas para N = 10
são equivalentes à seguinte lista (até turnos cíclicos e reversão):
[7, 5, 6, 4, 8, 2, 10, 1, 9, 3]
Eu não quero revelar muito além disso (embora seja provavelmente o suficiente para descobrir o padrão), então, em vez de dar mais exemplos, você pode verificar se seus resultados têm as seguintes diferenças quadráticas totais para um dado 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
Essa é a entrada A064842 da OEIS (que também contém uma referência a um papel com uma solução para esse desafio, se você estiver preso).
fonte
(i<n/2||n%2)^i%2?i+1:n-i
.Python2,
10598 bytes7 bytes salvos graças ao comentário de @Dennis
Versão editada 58 bytes
Eu já acreditava que deveria ser possível fazê-lo como uma linha, mas a lógica era muito complexa para mim. Vendo a resposta JavaScript de @ user81655 e a notação lambda em @Dennis Python-answer, tentei novamente.
A condição é igual a
Infelizmente, todo o esforço de transformação economiza apenas
umbyte em comparação com a tradução direta(i<n/2or n%2)!=i%2
da lógica JavaScript.fonte
int()
da entrada. Além disso, você pode colocar o corpo do loop for na mesma linha quefor...
.Python,
5149 bytesGraças a @xnor por jogar fora 2 bytes!
Experimente em Ideone .
Como funciona
Se i é um número em [0, ..., n - 1] , então ~ i% n = - (i + 1)% n = - (i + 1) + n = (n - 1) - i , significando que mapeia 0 para n - 1 , 1 para n - 2 e, em geral, o j- ésimo item da esquerda para o j- ésimo da direita.
Como explicado na minha resposta Jelly , podemos construir a saída por espreitar pelo menor valor entre i e ~ i% n , e escolher i se é mesmo e ~ i% n se é estranho. Conseguimos isso da seguinte maneira.
Se o mínimo for par,
min(i,~i%n)%-2
produzirá 0 , então XORing o resultado com i produzirá i , e computando seu módulo de resíduo n retornará i .Se o mínimo for ímpar,
min(i,~i%n)%-2
produzirá -1 , então XORing o resultado com i produzirá ~ i , para que toda a expressão seja avaliada como ~ i% n, conforme desejado.fonte
(i^min(i,n+~i)%-2)%n
.PHP,
7776515049 bytesUsa codificação ISO 8859-1.
Montando a primeira metade da matriz assim:
N+1-index
(9, 7, 5)1, 9, 3, 7, 5
Quanto à segunda metade da matriz, os valores mais externos são somados
N+1
, o que significa que você pode obter o valor correto correspondente deN-[left value]
onde o valor esquerdo já é conhecido.Execute assim (isso também mostra a diferença quadrática total) (
-d
adicionado apenas para estética):echo
~ß
para gerar um espaço.fonte
Python 2, 100
Eu sei que já existe uma resposta em python, mas acho que posso ter feito isso de maneira diferente.
E como um extra para testar a pontuação total:
fonte
def t(x,n):return sum((x[i]-x[i-1])**2for i in range(n))
usa o contorno implícito de índices negativos e salva 4 bytes. Eu sei, não fazia parte da competição. ;)CJam,
171514 bytesEsta é uma função que exibe um número inteiro n da pilha e empurra uma permutação de [0… n-1] em troca. O código usa a mesma abordagem da minha resposta Jelly .
Experimente online!
Como funciona
fonte
LISP, 86 bytes
As entradas da função permitem escolher os valores inicial (m) e final (n) da sequência.
Para testar a função de acordo com as amostras fornecidas, n é fixado em N e m em 1.
Aqui o código para testar a função:
Experimente no Ideone !
fonte
Julia, 39 bytes
Isso imprime uma permutação de 1: n . Uma permutação de 0: n-1 não custa nem salva bytes:
Esta última versão é uma porta direta da minha resposta Python .
fonte
ES6, 77 bytes
As
i&1
amostras são os dígitos dos extremos para o meio. Oi&2
adiciona ao início ou ao final do resultado em pares.fonte
R,
11786 byteseditar versão longa com bugs substituída por uma implementação do algoritmo @Dennis 'Jelly
fonte