Encontre a área de uma região de células unitárias, devido ao seu loop de perímetro, como uma sequência de curvas de 90 graus.

Por exemplo, considere a região de três células

XX
X

cujo perímetro desenhamos

L<S<L
v   ^
S R>L
v ^
L>L

Cada turno é marcado como esquerdo (L), reto (S) ou direito (R). A partir do R, as curvas são RLLSLSLL. Portanto, dada a entrada RLLSLSLL, devemos produzir 3 para a área.

A sequência de entrada é garantida para rastrear um loop envolvendo uma única região à sua esquerda.

• O caminho termina no ponto inicial, voltado para a direção inicial, formando um loop.
• O loop não se cruza ou se toca.
• O loop segue no sentido anti-horário em torno de uma região.

I / O

Você pode usar a entrada como uma lista ou sequência de caracteres LSRou como números -1, 0, 1para esquerda, reta, direita. A saída é um número inteiro positivo. Carros alegóricos estão OK.

Casos de teste

As entradas são fornecidas nos dois formatos, seguidas pelas respectivas saídas.

RLLSLSLL
LLLL
SLLSLL
LSRRSLLSSLSSLSSL
SSSSSLSSSSSLSSSSSLSSSSSL

[1, -1, -1, 0, -1, 0, -1, -1]
[-1, -1, -1, -1]
[0, -1, -1, 0, -1, -1]
[-1, 0, 1, 1, 0, -1, -1, 0, 0, -1, 0, 0, -1, 0, 0, -1]
[0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1]

3
1
2
7
36

Flak cerebral , 112 bytes

(([]){[{}]<{({}()){{}<>([{}]<([{}])>)(<>)}<>(({}[({})])[({}{})])<>}{}<>>({}<({}())>)<>([])}{})({()<({}()())>}{})

Experimente online!

Este programa usa o teorema de Green para calcular a área

A localização atual é armazenada na pilha certa, em um formato que depende da direção enfrentada.

Direction  top  second
north       -x       y
west        -y      -x
south        x      -y
east         y       x

Em todos os casos, o segundo valor na pilha aumentará em 1, e a integral da linha da área diminuirá pela metade do valor na parte superior da pilha. Para compensar, o final do programa divide o total em execução por -2.

# For each number in input
(([]){[{}]

  # Evaluate turn-handling to zero
  <

    # If turn:
    {

      # If right turn:
      ({}()){{}

        # Negate both values on other stack (reverse direction)
        <>([{}]<([{}])>)

      (<>)}

      # Swap the two stack elements and negate the new top of stack
      # This performs a left turn.
      <>(({}[({})])[({}{})])<>

    }{}

  <>>

  # Evaluate as top of stack and...
  ({}<

    # increment the number below it
    ({}())

  >)<>

([])}{})

# Divide total by -2
({()<({}()())>}{})

APL (Dyalog Classic) , 30 28 19 bytes

-2 graças a @ Adám

(+/9∘○×11○+\)0j1*+\

Experimente online!

usa truques com números complexos para calcular as coordenadas

a área é ½Σ (x _i -x _{i + 1} ) (y _i + y _{i + 1} ) ou equivalente Σ (x _i -x _{i + 1} ) y _i, pois as linhas são apenas horizontais ou verticais

JavaScript (ES6), 52 50 bytes

Guardado 2 bytes graças a @Neil

Espera o segundo formato de entrada.

a=>a.map(k=>r+=(2-(a=a+k&3))%2*(y+=~-a%2),r=y=0)|r

Experimente online!

Quão?

^{Esta descrição se aplica à versão anterior : x e y foram invertidos desde então.}

Isso se baseia na fórmula já mencionada por @ngn : A = Σ (x _i - x _{i + 1} ) y _i , que também pode ser escrita como Σdx _i y _i onde dx _i é -1, 0 ou 1.

Começamos com r = y = 0 .

Nós manter o controle de direção atual em um :

          | a = 0 | a = 1 | a = 2 | a = 3
----------+-------+-------+-------+-------
direction | East  | South | West  | North
       dx |  +1   |   0   |  -1   |   0     <--  -(~-a % 2)
       dy |   0   |  +1   |   0   |  -1     <--  (2 - a) % 2

É atualizado com a = a + k & 3, onde k é o elemento atual da matriz de entrada.

Como a inicialmente contém a matriz de entrada, a + k é coagido para NaN na primeira iteração e depois para 0 quando o AND bit a bit é aplicado. Isso significa que a primeira mudança de direção é realmente ignorada e sempre começamos a ir para o leste. Não importa, porque a área permanece a mesma, independentemente da orientação da forma final.

Então, atualizamos y com y += (2 - a) % 2.

Finalmente, computamos -dx com ~-a % 2e subtraímos y * -dx de r , que - no final do processo - é o nosso resultado final.

Python 2 , 64 bytes

f=lambda c,d=1,x=0:c>[]and f(c[1:],d*1j**c[0],x+d.real)-x*d.imag

Experimente online!

Calcula ∑xΔy usando números complexos.

Haskell , 71 70 69 bytes

a 0 0
a x d(t:r)|k<-t+d=x*g k+a(x+g(k-1))k r
a _ _ _=0
g a=sin$a*pi/2

Explicação: O Teorema de Green fornece a fórmula para a área: A = ½∑ (x _{k + 1} + x _k ) (y _{k + 1} -y _k ), que simplifica para A = ½∑ _{Δx = 0} 2x _k Δy + ½∑ _{Δy = 0} (x _{k + 1} + x _k ) * 0 = ∑xΔy quando as curvas são 90 graus ao longo dos eixos. Temos o seguinte pseudocódigo para uma função recursiva de deslizamento de curvas que controla a posição e a direção x:

A x dir (turn:turns) = ΔA + A (x+Δx) (dir+turn) turns

onde a nova direção, ΔA e Δx pode ser vista nas tabelas a seguir. Podemos ver uma periodicidade sinusoidal de comprimento quatro em ΔA e Δx ao longo do eixo diagonal dir+turn, que é implementado usando sinaritmética modular em vez da aritmética.

  ↔|L S R ΔA| L  S  R  Δx| L  S  R 
←   ↓ ← ↑    -x  0  x      0 -1  0  
↑   ← ↑ →     0  x  0     -1  0  1
→   ↑ → ↓     x  0 -x      0  1  0
↓   → ↓ ←     0 -x  0      1  0 -1

Experimente online!

Wolfram Language (Mathematica) , 36 30 bytes

Area@Polygon@AnglePath[.5Pi#]&

Se você possui uma versão mais antiga do Mathematica (~ v10), precisará Most@na frente AnglePathpara evitar fechar o polígono. (Obrigado a @ user202729 pelas dicas).

original: Experimente online!

atualizado: Experimente online!

Geléia , 15 11 bytes

Obrigado a @xnor por apontar uma etapa inútil, economizando 2 bytes
Obrigado a @dylnan por salvar outro byte

Espera o segundo formato de entrada. Retorna um flutuador.

+\ı*Ḟ_\×ƊĊS

Experimente online! ou execute todos os casos de teste

Comentado

+\ı*Ḟ_\×ƊĊS  - main link, taking the input list   e.g. [1, -1, -1, 0, -1, 0, -1, -1]
+\           - cumulative sum                     -->  [1, 0, -1, -1, -2, -2, -3, -4]
  ı*         - compute 1j ** d,                   -->  [(0+1j), (1+0j), (0-1j), (0-1j),
               which gives a list of (-dy + dx*j)       (-1+0j), (-1+0j), (0+1j), (1+0j)]
         Ċ   - isolate the imaginary part (dx)    -->  [1, 0, -1, -1, 0, 0, 1, 0] (floats)
        Ɗ    - invoke the last 3 links as a monad
    Ḟ        - isolate the real part (-dy)        -->  [0, 1, 0, 0, -1, -1, 0, 1] (floats)
     _\      - negated cumulative sum (gives y)   -->  [0, -1, -1, -1, 0, 1, 1, 0]
       ×     - compute dx * y                     -->  [0, 0, 1, 1, 0, 0, 1, 0]
          S  - sum                                -->  3

Python 2 , 62 bytes

f=lambda l,p=0,s=1:l>[]and(p/s).imag/2+f(l[1:],p+s,s*1j**l[0])

Experimente online!

Semelhante à solução de Lynn , mas usando uma aritmética complexa para extrair o componente certo do número complexo de uma só vez.

Pitão , 25 bytes

Usa o -1, 0, 1 formato de entrada.

s*Vm_sd._sMKm^.j)sd._QeMK

Experimente aqui!

Pitão , 14 bytes

_smec^.j)sd2.:

Suíte de teste

_smec^.j)sd2.:
              Q     implicit input
            .:      take all non-empty contiguous sublists
  m                map this operation onto each one:
   ec^.j)sd2
         s           the sum of the sublist
     ^.j)            raise it to the complex unit 1j to that power
    c      2         halve it
   e                take the imaginary part
_s                take the negated sum of the result

Isso expressa a área como a soma de -1/2 * g(sum(l))todas as sublistas contíguas lda entrada, onde gé feita a indexação modular [0,1,0,-1]. O código implementa gcomo g(x)=imag(1j**x). Pode haver um método mais curto com indexação modular direta, usando sinou com uma função aritmética ativada x%4.