Calcular o número do enrolamento

15

O número do enrolamento é o número inteiro de rotações líquidas no sentido anti-horário que um observador deve ter feito para seguir um determinado caminho fechado. Observe que quaisquer rotações no sentido horário contam negativas para o número do enrolamento. O caminho pode se auto-interceptar.

Alguns exemplos (descaradamente retirados da Wikipedia) são dados abaixo:

insira a descrição da imagem aqui

Seu objetivo é calcular o número do enrolamento para um determinado caminho.

Entrada

Presume-se que o observador esteja na origem (0,0).

A entrada é uma sequência finita de pontos (pareados de números inteiros) de qualquer fonte de entrada desejada que descreva o caminho linear em partes. Você pode achatar isso em uma sequência 1D de números inteiros, se desejar, e também pode deslizar a entrada para obter todas as coordenadas x antes de todas as coordenadas y / vice-versa. Você também pode considerar a entrada como um número complexo a+b i. O caminho pode se auto-interceptar e pode conter segmentos de comprimento zero. O primeiro ponto é o início do caminho e supõe-se que esteja em algum lugar no eixo x positivo.

Nenhuma parte do caminho cruzará a origem. O caminho sempre será fechado (ou seja, o primeiro e o ponto perdido são os mesmos). Seu código pode implicar o último ponto ou exigir que ele seja incluído.

Por exemplo, dependendo da sua preferência, ambas as entradas especificam o mesmo quadrado:

ponto final implícito

1,0
1,1
-1,1
-1,-1
1,-1

ponto final explícito

1,0
1,1
-1,1
-1,-1
1,-1
1,0

Resultado

A saída é um único inteiro para o número do enrolamento. Pode ser para qualquer fonte (valor de retorno, stdout, arquivo etc.).

Exemplos

Todos os exemplos têm o ponto final definido explicitamente e são dados como pares x, y. Aliás, você também deve alimentar esses exemplos diretamente em qualquer código, assumindo pontos finais definidos implicitamente e as saídas devem ser as mesmas.

1. Teste básico

1,0
1,1
-1,1
-1,-1
1,-1
1,0

Resultado

1

2. Teste de ponto repetido

1,0
1,0
1,1
1,1
-1,1
-1,1
-1,-1
-1,-1
1,-1
1,-1
1,0

Resultado

1

3. Teste no sentido horário

1,0
1,-1
-1,-1
-1,1
1,1
1,0

Resultado

-1

4. Teste externo

1,0
1,1
2,1
1,0

Resultado

0

5. Enrolamento misto

1,0
1,1
-1,1
-1,-1
1,-1
1,0
1,-1
-1,-1
-1,1
1,1
1,0
1,1
-1,1
-1,-1
1,-1
1,0
1,1
-1,1
-1,-1
1,-1
1,0

Resultado

2

Pontuação

Isso é código de golfe; o código mais curto vence. Aplicam-se brechas padrão. Você pode usar quaisquer funções internas, desde que não tenham sido projetadas especificamente para calcular o número do enrolamento.

helloworld922
fonte
2
Entrada pode ser tomado como números complexos (ou uma representação em cadeia deles, como "1-i"ou "1-1i"?)
Nível River St
Sim, qualquer tipo de par é permitido.
precisa saber é o seguinte

Respostas:

10

ES6, 83 bytes

a=>a.map(([x,y])=>r+=Math.atan2(y*b-x*c,y*c+x*b,b=x,c=y),b=c=r=0)&&r/Math.PI/2

Toma como entrada uma matriz de pares de pontos que são interpretados como números complexos. Em vez de converter cada ponto em um ângulo, os pontos são divididos pelo ponto anterior, que Math.atan2 então converte em um ângulo entre -π e π, determinando automaticamente de que maneira o caminho está girando. A soma dos ângulos é então 2π vezes o número do enrolamento.

Como Math.atan2 não se importa com a escala de seus argumentos, na verdade não realizo a divisão completa, z / w = (z * w*) / (w * w*)apenas multiplico cada ponto pelo complexo conjugado do ponto anterior.

Editar: salvou 4 bytes graças a @ edc65.

Neil
fonte
Bom e rápido. E eu não entendo sua matemática. Mas reduceé quase sempre uma má escolha.
Edc65 31/01
a=>a.map(([x,y])=>r+=Math.atan2(y*b-x*c,y*c+x*b,b=x,c=y),b=c=r=0)&&r/Math.PI/2usando o mapa ou reduza. De qualquer forma, você tem o meu voto
edc65
@ edc65 Obrigado; Usei reduceporque não percebi que Math.atan2 (0,0) é 0. (Bem, depende se um de seus 0s é realmente -0.) A matemática é baseada em divisão complexa, que normalmente é calculada como z / w = z * w* / |w|², mas não me importo com a magnitude, por isso é apenas a multiplicação pelo conjugado complexo. Também um pouco confuso Math.atan2 aceita (y, x) argumentos.
Neil
Admito que não entendo o código, mas se sua descrição for precisa, acredito que sua resposta está errada. De fato, se você introduzido pontos de este caminho (eu estou dando uma imagem para maior clareza), então o número de enrolamento é 1, enquanto o seu problema seria a saída 2.
Wojowu
@Wojowu Desculpe, eu quis dizer o ângulo entre os pontos medidos a partir da origem, em vez de ângulos externos do polígono, portanto, para a sua imagem, o meu código deve realmente calcular a resposta como 1.
Neil
3

MATL , 11 bytes

X/Z/0)2/YP/

A entrada é uma sequência de números complexos, incluindo o ponto final.

Experimente online!

Explicação

A maior parte do trabalho é realizada pela Z/função ( unwrap), que desembrulha os ângulos em radianos alterando saltos absolutos iguais ou superiores a pi ao seu complemento 2 * pi.

X/       % compute angle of each complex number
Z/       % unwrap angles
0)       % pick last value. Total change of angle will be a multiple of 2*pi because 
         % the path is closed. Total change of angle coincides with last unwrapped
         % angle because the first angle is always 0
2/       % divide by 2
YP/      % divide by pi
Luis Mendo
fonte
1
Ultimamente, MATL e Jelly têm atado a maioria dos desafios matemáticos. Estou impressionado, você quase
derrotou a
@ETHproductions Obrigado por suas boas palavras! Sim, eles estão envolvidos em alguns desafios recentes. Por outro lado, já vi alguns problemas em que a contagem de bytes de Jelly é aproximadamente a metade do MATL :-D
Luis Mendo
2

Gelatina, 11 bytes

æAI÷ØPæ%1SH

Isso leva a entrada como uma lista de coordenadas y e uma lista de coordenadas x.

Experimente aqui .

lirtosiast
fonte
1

Python, 111

Resposta mais longa até agora. Minhas motivações são 1) aprender python e 2) possivelmente portar isso para pyth.

from cmath import *
q=input()
print reduce(lambda x,y:x+y,map(lambda (x,y):phase(x/y)/pi/2,zip(q[1:]+q[:1],q)))

A entrada é fornecida como uma lista de números complexos.

Ideone.

Eu acho que a abordagem é semelhante à resposta ES6.

Quando dois números complexos são multiplicados, o argumento ou a fase do produto é a soma do argumento ou da fase dos dois números. Assim, quando um número complexo é dividido por outro, a fase do quociente é a diferença entre as fases do numerador e do denominador. Assim, podemos calcular o ângulo percorrido para cada ponto e o próximo ponto. Soma esses ângulos e divida por 2π para obter o número de enrolamento necessário.

Trauma Digital
fonte