Площадь огорожена петлей по периметру

14

Найти площадь области единичных ячеек с учетом ее петли по периметру в виде последовательности поворотов на 90 градусов.

Например, возьмем трехклеточную область 

XX
X

чей контур периметра мы рисуем

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

Каждый поворот отмечен как левый (L), прямой (S) или правый (R). Начиная с R, повороты RLLSLSLL. Таким образом, учитывая входные данные RLLSLSLL, мы должны вывести 3 для области.

Входная последовательность гарантированно отследит петлю, охватывающую одну область слева.

  • Путь заканчивается обратно в начальной точке, лицом к начальному направлению, образуя петлю.
  • Петля не пересекает и не касается себя.
  • Цикл идет против часовой стрелки вокруг области.

I / O

Вы можете принять ввод в виде списка или строки символов LSRили в виде чисел -1, 0, 1слева, справа и справа. Выход является положительным целым числом. Поплавки в порядке.

Контрольные примеры

Входные данные даны в обоих форматах, сопровождаемые их соответствующими выходными данными.

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
code-golf geometry grid XNOR
источник

Ответы:

10

Brain-Flak , 112 байт

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

Попробуйте онлайн!

Эта программа использует теорему Грина для вычисления площади

Текущее местоположение хранится в правом стеке в формате, который зависит от направления.

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

Во всех случаях второе значение в стеке будет увеличиваться на 1, а линейный интеграл для области уменьшается на половину значения в верхней части стека. Чтобы компенсировать это, конец программы делит промежуточный итог на -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
({()<({}()())>}{})
Nitrodon
источник
7

APL (Dyalog Classic) , 30 28 19 байтов

-2 благодаря @ Adám

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

Попробуйте онлайн!

использует трюки со сложными числами для вычисления координат

площадь равна ½Σ (x i -x i + 1 ) (y i + y i + 1 ) или эквивалентно Σ (x i -x i + 1 ) y i, поскольку линии являются только горизонтальными или вертикальными

СПП
источник
Сохранить в преобразование в tradfn тело.
Адам
@ Adám верно, я надеялся на поезд и почему-то забыл это сделать ...
ngn
@ Адам ах! Я нашел поезд :)
НГН
6

JavaScript (ES6), 52 50 байт

Сохранено 2 байта благодаря @Neil

Ожидается второй формат ввода.

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

Попробуйте онлайн!

Как?

Это описание относится к предыдущей версии : x и y с тех пор были инвертированы.

Это основано на формуле, уже упомянутой @ngn : A = Σ (x i - x i + 1 ) y i , которая также может быть записана как Σdx i y i, где dx i равно либо -1, 0, либо 1.

Начнем с r = y = 0 .

Мы продолжаем отслеживать направления тока в :

          | 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

Он обновляется с помощью a = a + k & 3, где k - текущий элемент входного массива.

Поскольку изначально содержит массив ввода, а + к принуждается к NaN на первой итерации , а затем в 0 , когда побитовое И применяется. Это означает, что первое изменение направления фактически игнорируется, и мы всегда начинаем двигаться на восток. Это не имеет значения, потому что область остается той же самой, независимо от ориентации окончательной формы.

Затем мы обновляем у с y += (2 - a) % 2.

Наконец, мы вычисляем -dx с ~-a % 2и вычитаем y * -dx из r , что - в конце процесса - наш конечный результат.

Arnauld
источник
1
a=>a.map(k=>r+=(2-(a=a+k&3))%2*(y+=~-a%2),r=y=0)|rэкономит 2 байта.
Нил
3

Haskell , 71 70 69 байт

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

Пояснение: Теорема Грина дает формулу для области: A = ½∑ (x k + 1 + x k ) (y k + 1 -y k ), которая упрощается до A = ½∑ Δx = 0 2x k Δy + ½∑ Δy = 0 (х k + 1 + x k ) * 0 = ∑xΔy, когда повороты на 90 градусов вдоль осей. У нас есть следующий псевдокод для рекурсивной функции поворота, которая отслеживает положение и направление x:

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

где новое направление ΔA и Δx видно из следующих таблиц. Мы можем видеть синусоидальную периодичность длины четыре в ΔA и Δx вдоль диагональной оси,dir+turn , которая реализуется с использованием sinвместо модульной арифметики.

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

Попробуйте онлайн!

Angs
источник
2

Wolfram Language (Mathematica) , 36 30 байт

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

Если у вас более старая версия Mathematica (~ v10), вам понадобится Most@ перед ней, AnglePathчтобы избежать закрытия многоугольника. (Спасибо @ user202729 за советы).

оригинал: попробуйте онлайн!

обновлено: попробуйте онлайн!

Келли Лоудер
источник
#.5Piпохоже на работу.
user202729
Похоже, что тоже можно отбросить Most.
user202729
2

Желе , 15 11 байт

Спасибо @xnor за указание на бесполезный шаг, сохранение 2 байта.
Спасибо @dylnan за сохранение другого байта.

Ожидается второй формат ввода. Возвращает поплавок.

+\ı*Ḟ_\×ƊĊS

Попробуйте онлайн! или запустите все тесты

комментарии

+\ı*Ḟ_\×ƊĊ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
Arnauld
источник
Нужно ли хранить только 2 младших значащих бита?
xnor
+\ı*Ḟ_\×ƊĊSсохраняет байт
dylnan
@xnor and dylnan Спасибо, что помогли мне сыграть в гольф. И еще одно спасибо xnor за награду!
Арно
2

Python 2 , 62 байта

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

Попробуйте онлайн!

Похоже на решение Линн , но использует некоторую сложную арифметику, чтобы извлечь правильный компонент комплексного числа за один раз.

XNOR
источник
0

Pyth , 14 байт

_smec^.j)sd2.:

Тестирование

_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

Это выражает область как сумму -1/2 * g(sum(l))по всем смежным подспискам lна входе, где gвыполняется модульная индексация в [0,1,0,-1]. Код реализуется gкак g(x)=imag(1j**x). Может быть более короткий метод с прямым модульным индексированием, использованием sinили арифметической функцией x%4.

XNOR
источник