Encuentre el área de una región de celdas unitarias dado su bucle perimetral como una secuencia de giros de 90 grados.

Por ejemplo, tome la región de tres celdas

XX
X

cuyo bucle perimetral dibujamos

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

Cada giro se marca como izquierda (L), recta (S) o derecha (R). A partir de la R, los turnos son RLLSLSLL. Entonces, dada la entradaRLLSLSLL , deberíamos generar 3 para el área.

Se garantiza que la secuencia de entrada trazará un bucle que encierra una sola región a su izquierda.

• El camino termina de regreso en el punto de inicio, mirando hacia la dirección inicial, formando un bucle.
• El bucle no se cruza ni se toca.
• El bucle va en sentido antihorario alrededor de una región.

I / O

Puede tomar la entrada como una lista o cadena de caracteres LSR, o como números -1, 0, 1para izquierda, recta, derecha. La salida es un entero positivo. Los flotadores están bien.

Casos de prueba

Las entradas se dan en ambos formatos seguidos de sus respectivas salidas.

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

Brain-Flak , 112 bytes

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

Pruébalo en línea!

Este programa usa el teorema de Green para calcular el área

La ubicación actual se almacena en la pila correcta, en un formato que depende de la dirección orientada.

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

En todos los casos, el segundo valor en la pila aumentará en 1, y la integral de línea para el área disminuye a la mitad del valor en la parte superior de la pila. Para compensar, el final del programa divide el total acumulado 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 gracias a @ Adám

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

Pruébalo en línea!

usa trucos con números complejos para calcular las coordenadas

el área es ½Σ (x _i -x _{i + 1} ) (y _i + y _{i + 1} ) o equivalentemente Σ (x _i -x _{i + 1} ) y _i ya que las líneas son solo horizontales o verticales

JavaScript (ES6), 52 50 bytes

Guardado 2 bytes gracias a @Neil

Espera el segundo formato de entrada.

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

Pruébalo en línea!

¿Cómo?

^{Esta descripción se aplica a la versión anterior : x e y desde entonces se han invertido.}

Esto se basa en la fórmula ya mencionada por @ngn : A = Σ (x _i - x _{i + 1} ) y _i , que también se puede escribir como Σdx _i y _i donde dx _i es -1, 0 o 1.

Comenzamos con r = y = 0 .

Realizamos un seguimiento de la dirección de la corriente en un :

          | 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

Se actualiza con a = a + k & 3, donde k es el elemento actual de la matriz de entrada.

Debido a que inicialmente contiene la matriz de entrada, a + k se coacciona a NaN en la primera iteración y luego a 0 cuando se aplica el AND a nivel de bits. Esto significa que el primer cambio de dirección se ignora y siempre comenzamos a dirigirnos hacia el este. No importa porque el área permanece igual, sin importar la orientación de la forma final.

Luego, actualizamos y cony += (2 - a) % 2 .

Finalmente, calculamos -dx con ~-a % 2y restamos y * -dx de r , que - al final del proceso - es nuestro 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

Pruébalo en línea!

Calcula ∑xΔy usando números complejos.

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

Explicación: El teorema de Green da la fórmula para el área: A = ½∑ (x _{k + 1} + x _k ) (y _{k + 1} -y _k ), que se simplifica a A = ½∑ _{Δx = 0} 2x _k Δy + ½∑ _{Δy = 0} (x _{k + 1} + x _k ) * 0 = ∑xΔy cuando los giros son 90 grados a lo largo de los ejes. Tenemos el siguiente pseudocódigo para una función recursiva de giro de globo que realiza un seguimiento de la posición y dirección x:

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

donde la nueva dirección, ΔA y Δx se puede ver en las siguientes tablas. Podemos ver una periodicidad sinusoidal de longitud cuatro en ΔA y Δx a lo largo del eje diagonal dir+turn, que se implementa utilizando en sinlugar de aritmética modular.

  ↔|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

Pruébalo en línea!

Wolfram Language (Mathematica) , 36 30 bytes

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

Si tiene una versión anterior de Mathematica (~ v10) necesitará Most@ frente aAnglePath para evitar cerrar el polígono. (Gracias a @ user202729 por los consejos).

original: ¡ Pruébelo en línea!

actualizado: ¡ Pruébelo en línea!

Jalea , 15 11 bytes

Gracias a @xnor por señalar un paso inútil, ahorrando 2 bytes
Gracias a @dylnan por guardar otro byte

Espera el segundo formato de entrada. Devuelve un flotador.

+\ı*Ḟ_\×ƊĊS

Pruébalo en línea! o ejecutar todos los casos de prueba

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

Pruébalo en línea!

Similar a la solución de Lynn , pero usando algo de aritmética compleja para extraer el componente correcto del número complejo de una vez.

Pyth , 25 bytes

Utiliza el -1, 0, 1formato de entrada.

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

Pruébalo aquí!

Pyth , 14 bytes

_smec^.j)sd2.:

Banco de pruebas

_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

Esto expresa el área como la suma de -1/2 * g(sum(l))todas las sublistas contiguas lsobre la entrada, donde se grealiza la indexación modular [0,1,0,-1]. El código se implementa gcomo g(x)=imag(1j**x). Puede haber un método más corto con indexación modular directa, uso sino una función aritmética activada x%4.