Area enclosed by perimeter loop

Question

Find the area of a region of unit cells given its perimeter loop as a sequence of 90-degree turns.

For example, take the three-cell region

XX
X

whose perimeter loop we draw

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

Each turn is marked as left (L), straight (S), or right (R). Starting from the R, the turns are RLLSLSLL. So, given input RLLSLSLL, we should output 3 for the area.

The input sequence is guaranteed to trace out a loop enclosing a single region on its left.

• The path ends back at the start point, facing the initial direction, forming a loop.
• The loop does not cross or touch itself.
• The loop goes counterclockwise around a region.

I/O

You can take input as a list or string of characters LSR, or as numbers -1, 0, 1 for left, straight, right. Output is a positive integer. Floats are OK.

Test cases

The inputs are given in both formats followed by their respective outputs.

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

Answer 1

Brain-Flak, 112 bytes

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

Try it online!

This program uses Green's theorem to compute the area

The current location is stored on the right stack, in a format that depends on the direction faced.

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

In all instances, the second value on the stack will increase by 1, and the line integral for the area decreases by half the value on the top of the stack. To compensate, the end of the program divides the running total by -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
({()<({}()())>}{})

Answer 2

APL (Dyalog Classic), 30 28 19 bytes

-2 thanks to @Adám

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

Try it online!

uses tricks with complex numbers to compute the coordinates

the area is ½Σ(x_i-x_i+1)(y_i+y_i+1) or equivalently Σ(x_i-x_i+1)y_i as the lines are only horizontal or vertical

Answer 3

JavaScript (ES6), 52 50 bytes

Saved 2 bytes thanks to @Neil

Expects the second input format.

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

Try it online!

How?

^{This description applies to the previous version: x and y have since been inverted.}

This is based on the formula already mentioned by @ngn: A = Σ(x_i - x_i+1)y_i, which can also be written as Σdx_iy_i where dx_i is either -1, 0 or 1.

We start with r = y = 0.

We keep track of the current direction in a:

          | 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

It is updated with a = a + k & 3, where k is the current element of the input array.

Because a initially contains the input array, a + k is coerced to NaN on the first iteration and then to 0 when the bitwise AND is applied. This means that the first direction change is actually ignored and we always start heading to East. It doesn't matter because the area remains the same, no matter the orientation of the final shape.

Then, we update y with y += (2 - a) % 2.

Finally, we compute -dx with ~-a % 2 and subtract y * -dx from r, which -- at the end of the process -- is our final result.

Answer 4

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

Try it online!

Computes ∑xΔy using complex numbers.

Answer 5

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

Explanation: Green's Theorem gives the formula for the area : A = ½∑(x_k+1+x_k)(y_k+1-y_k), which simplifies to A = ½∑_Δx=02x_kΔy + ½∑_Δy=0(x_k+1+x_k)*0 = ∑xΔy when turns are 90 degrees along the axes. We have the following pseudocode for a recursive turn-globbing function that keeps track of the x position and direction:

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

where the new direction, ΔA and Δx can be seen from the following tables. We can see a sinusoidal periodicity of length four in both ΔA and Δx along the diagonal axis, dir+turn, which is implemented using sin instead of modular arithmetic.

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

Try it online!

Answer 6

Wolfram Language (Mathematica), 36 30 bytes

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

If you have an older version of Mathematica (~v10) you'll need Most@ in front of AnglePath to avoid closing the polygon. (Thanks to @user202729 for the tips).

original: Try it online!

updated: Try it online!

Answer 7

Jelly, 15 11 bytes

Thanks to @xnor for pointing out a useless step, saving 2 bytes
Thanks to @dylnan for saving another byte

Expects the second input format. Returns a float.

+\ı*Ḟ_\×ƊĊS

Try it online! or run all test cases

Commented

+\ı*Ḟ_\×ƊĊ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

Answer 8

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

Try it online!

Similar to Lynn's solution, but using some complex arithmetic to extract the right component of the complex number in one go.

Answer 9

Pyth, 25 bytes

Uses the -1, 0, 1 input format.

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

Try it here!

Answer 10

Pyth, 14 bytes

_smec^.j)sd2.:

Test suite

_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

This expresses the area as the sum of -1/2 * g(sum(l)) over all contiguous sublists l over the input, where g does modular indexing into [0,1,0,-1]. The code implements g as g(x)=imag(1j**x). There may be a shorter method with direct modular indexing, using sin, or an arithmetic function on x%4.