Площадь многоугольника ASCII

31

Вы должны написать программу или функцию, которая получает в качестве входных данных строку, представляющую полигон ascii-art, а выходные данные возвращают площадь полигона.

Ввод представляет собой строку, состоящую из символов _ / \ L V spaceи newlineопределяющую простой многоугольник (что означает отсутствие лишних сегментов, отсутствие самоприкосновения и самопересечения).

Площадь ячейки одного символа 2

  • _разбивает ячейку на размеры 0и2
  • \разбивает ячейку на размеры 1и1
  • /разбивает ячейку на размеры 1и1
  • Lразбивает ячейку на размеры 0и2
  • Vразбивает ячейку на размеры 1и 1(две стороны Vвсегда будут на одной стороне многоугольника, поэтому они рассматриваются вместе в листинге.)

Каждый персонаж соединяет два угла своей ячейки персонажа, которые вы ожидаете (например, верхний левый и верхний правый в случае V).

Пример с площадью 7 ( 1+2+1во втором ряду и 1+1+1в третьем):

 _
/ \
V\/

вход

  • Ввод будет образовывать прямоугольник, т.е. между символами новой строки будет одинаковое количество символов.
  • На любой стороне многоугольника могут быть дополнительные пробелы.
  • Трейлинг новой строки не является обязательным.

Выход

  • Единственное положительное целое число, площадь многоугольника.

Примеры

Выходы идут после последнего ряда их входов.

  _  
  V  

1

/L
\/

3



    /VV\
    L  /
     L/
14

  ____/\ 
  \    /
/\/   /
\____/

32  

   /V\
  /   \__ 
  \     /
/\/   /V
L____/

45

Это код-гольф, поэтому выигрывает самый короткий вход.

randomra
источник
ваш третий пример должен быть 14
Оптимизатор
@Optimizer Спасибо, исправлено.
randomra
Является ли отсутствие ^ намеренно?
RobAu
@RobAu Да, это выглядит недостаточно хорошо.
randomra

Ответы:

5

CJam, 48 43 29 байт

qN-{i_9%2%U!^:U;J%D%1U2*?}%:+

Обновление : много играл в гольф, используя математику и трюк состояния * 2 из ответа orlp.

Как это работает (устарело, скоро обновится)

Мы разделяем ввод на новую строку, а затем для каждой части мы поддерживаем счетчик появлений граничных символов L\/. Этот счетчик% 2 сообщит нам, какой из двух разделов можно выбрать для всех символов. Затем мы находим индекс каждого символа в строке L _. \/Vдаст -1ссылку на последний элемент в массиве. Получив индекс, мы используем его 4558Zb2/для создания массива, [[2 0] [0 2] [0 2] [1 1]]а затем выбираем правильное значение счетчика с помощью счетчика.

qN/0f{                                  }      e# Split the input on newline and for each
      \{                             }/        e# swap the 0 to back and for each char in
                                               e# the line, run this loop
        _"L _"#                                e# Copy the char and get index of it in
                                               e# this string "L _"
               4558Zb                          e# This is basically 4558 3base
                                               e# which comes to be [2 0 0 2 0 2 1 1]
                     2/=                       e# Group into pairs of 2 and choose the
                                               e# correct one.
                        2$=                    e# Based on the counter, choose the correct
                                               e# partition amount
                           @@"\/L"&,+          e# Increment the counter if the char is one
                                               e# of \, / and L
                                       ;       e# Pop the counter after each line loop
                                         :+    e# Sum all the numbers to get area

Попробуйте онлайн здесь

оптимизатор
источник
22

Pyth, 47 46 45 36 30

FNs.zx=Z}N"\/L"aY|}N"\/V"yZ;sY

Объяснение:

FNs.z            For every character in input, except newlines...
  x=Z}N"\/L"     Swap state if /, \, or L.
  aY|}N"\/V"yZ;  Append 1 if /, \, or V, else 2 times the state to Y.
sY               Sum Y and print.

У нас есть два состояния: «в многоугольнике» и «вне многоугольника». Следующие символы каждый делает следующее при чтении их сверху слева внизу справа:

/ \     swap state, add one to area
V                   add one to area
_ space             if in polygon, add two to area
L       swap state, if in polygon, add two to area

Обратите внимание, что «добавить один в область» и «если в полигоне добавить два в область» являются взаимоисключающими.

orlp
источник
Я действительно запутался в том, как x=работает. Это где-то задокументировано?
Якуб
@Jakube Это расширенное задание.
orlp
@Jakube Это как +=или *=или что-то еще. В этом случае xиспользуется как xor, так что он точно такой же, как и в Python ^=.
Исаак
14

Сетчатка , 293 + 15 = 308 314 385 байт

;`\s
_
;`\\
/
;`.+
o$0iio
;+`(o(?=/.*(i)|L.*(ii)|V.*(io)|_)|i(?=/.*(io)|L.*(o)|_.*(ii)|V.*(i))).
$1$2$3$4$5$6$7$8
;`o
<empty>
;`ii$
#:0123456789
;+`^(?=i)(i*)\1{9}(?=#.*(0)|i#.*(1)|ii#.*(2)|iii#.*(3)|iiii#.*(4)|iiiii#.*(5)|iiiiii#.*(6)|iiiiiii#.*(7)|iiiiiiii#.*(8)|iiiiiiiii#.*(9))
$1#$2$3$4$5$6$7$8$9$10$11
:.*|\D
<empty>

Каждая строка идет в отдельном файле, поэтому я добавил 13 к числу байтов. Кроме того, вы можете поместить все это в один файл как есть и использовать -sфлаг. <empty>Стенд на самом деле пустые файлы или строки.

К сожалению, мне нужно 187 байтов, чтобы преобразовать результат из унарного в десятичное. Я думаю, что я действительно должен реализовать это в ближайшее время .

объяснение

Retina - это язык на основе регулярных выражений (который я написал именно для того, чтобы иметь возможность делать подобные вещи с помощью регулярных выражений). Каждая пара файлов / строк определяет этап замены, причем первая строка является шаблоном, а вторая строка - строкой замены. `Шаблонам может предшествовать строка конфигурации -delimited, которая может содержать обычные модификаторы регулярных выражений, а также некоторые специфичные для Retina параметры. Для вышеприведенной программы применимы соответствующие параметры ;, которые подавляют вывод этого этапа и +применяют замену в цикле, пока результат не перестанет изменяться.

Идея решения состоит в том, чтобы посчитать каждую строку отдельно, потому что мы всегда можем решить по символам, с которыми уже столкнулись, находимся ли мы внутри или вне полигона. Это также означает, что я могу объединить все это в одну линию, потому что начало и конец линии всегда находятся за пределами многоугольника. Также можно отметить, что _и пробел полностью идентичны для алгоритма развертки строки, а также \и /. Поэтому в качестве первого шага я заменяю все символы новой строки и пробелы на _все \, /чтобы потом немного упростить код.

Я отслеживаю текущее состояние внутри / снаружи с помощью символов iи o, в то же время, использую is для подсчета области. Для этого я начинаю с добавления oк соединенной линии, чтобы отметить, что мы находимся за пределами многоугольника. Я также добавляю iioв самый конец ввода, который я буду использовать для поиска новых персонажей.

Затем первая большая замена просто заменяет iили oсопровождается одним из /V_Lследующего набора символов, тем самым затопляя и подсчитывая всю вещь. Таблица замены выглядит следующим образом, где столбцы соответствуют последнему символу в этой строке, а строки - следующему символу (где Sдля пробела и <>для пустой строки). Я включил все символы ввода, чтобы показать эквивалентности, которые я уже использовал:

     i     o

/    io    i
\    io    i
L    o     ii
V    i     io
_    ii    <>
S    ii    <>

Обратите внимание, что последний символ всегда указывает, находится ли после символа внутри или вне многоугольника, а число is соответствует области, которую необходимо добавить в многоугольник. В качестве примера здесь приведены результаты первых четырех итераций на последнем входном примере (это было сгенерировано старой версией, которая фактически заливала каждую строку отдельно, но принцип все тот же):

o   /V\
o  /   \___
o  L     _/
o/\/   /V
oL__ _/
o   V

o  /V\
o /   \___
o L     _/
oi\/   /V
oii__ _/
o  V

o /V\
o/   \___
oL     _/
oiio/   /V
oiiii_ _/
o V

o/V\
oi   \___
oii     _/
oiioi   /V
oiiiiii _/
oV

oiV\
oiii  \___
oiiii    _/
oiioiii  /V
oiiiiiiii_/
oio

Наконец, я просто избавляюсь от всех os и разрывов строк, удаляя все, что соответствует [^i], а остаток - десятичное в унарное преобразование, которое довольно скучно.

Мартин Эндер
источник
4

Perl, 65 58 байт

map{map{$b^=2*y,/\\L,,;$a+=y,/\\V,,||$b}split//}<>;print$a
  • Переключите $ b между 0 и 2, когда увидите / \ или L.
  • Прибавьте 1 к $ a, увидев / \ или V.
  • Добавьте $ b к $ a, увидев что-нибудь еще.
Helios
источник
Отличное решение, Perl удивительно компактен.
orlp
1
Обработка ввода может быть упрощена для еще большего выигрыша:$/=\1;$-^=2*y,/\\L,,,$a+=y,/\\V,,||$-for<>;print$a
nutki
4

GNU sed, 290 + 1

+1 должен учитывать -rпереключение, переданное в sed. Комментарии и дополнительные пробелы не учитываются в счете.

Я не выглядел очень подробно, но я думаю, что это, вероятно, похоже на ответ Retina Мартина :

:                      # label to start processing next (or first) line
s/[0-9]//g             # remove the count of colons from previous lines
H                      # append the current line to the hold space
g                      # copy the hold space to the pattern space
y^_\\^ /^              # Replace '_' with ' ' and replace '\' with '/'
s/(\n| +$)//g          # strip newlines and trailing space
:o                     # start of "outside loop"
s/(^|:) *V/\1:/        # replace leading spaces and "V" with ":"
to                     #   if the above matches, stay outside
s/(^|:) *[|/]/\1:/     # replace leading spaces and "|" or "/" with ":"
ti                     #   if the above matches, go inside
s/(^|:) *L/\1::/       # replace leading spaces and "L" with "::"
:i                     # start of "inside" loop
s/: /:::/              # replace space with "::"
ti                     #   if the above matches, stay inside
s/:V/::/               # replace "V" with ":"
ti                     #   if the above matches, stay inside
s/:[|/]/::/            # replace "|" or "/" with ":"
to                     #    if the above matches, go outside
s/:L/:/                # remove "L"
to                     #    if the above matches, go outside
h                      # copy current string of colons to hold buffer
:b                     # start of colon count loop
s/:{10}/</g            # standard sed "arithmetic" to get string length
s/<([0-9]*)$/<0\1/
s/:{9}/9/
s/:{8}/8/
s/:{7}/7/
s/:{6}/6/
s/:{5}/5/
s/::::/4/
s/:::/3/
s/::/2/
s/:/1/
s/</:/g
tb                     # once arithmetic done, pattern buffer contains string length
N                      # append newline and next line to pattern buffer
b                      # loop back to process next line

обзор

  • Замените каждую единицу области двоеточием :
  • Подсчитайте количество двоеточий

Заметки

  • sedориентирован на строки, поэтому требуется некоторая работа для обработки нескольких строк одновременно. Команда Nделает это, добавляя новую строку, а затем следующую строку в текущее пространство шаблона. Сложность в Nтом, что, как только он попадает во входной поток EOF, он sedполностью завершает работу без какой-либо возможности дальнейшей обработки. Чтобы обойти это, мы подсчитываем текущий набор двоеточий в конце каждой строки, непосредственно перед чтением в следующей строке.

Выход:

$ echo '   /V\
  /   \__ 
  \     /
/\/   /V
L____/' |sed -rf polyarea.sed
45
$
Цифровая травма
источник
3

C 93 96 108 байт

Редактировать: учел предложения в комментариях, преобразовал while в цикл с одиночным оператором и полностью удалил переменную «i».

int s,t;main(c,v)char**v;{for(;c=*v[1]++;t+=s+(c>46^!(c%19)^s))s^=c>13^c%9>4;printf("%d",t);}

Исходное сообщение:

Это выглядело как забавная и достаточно простая проблема, чтобы наконец-то заставить меня создать аккаунт здесь.

main(c,v)char**v;{int i,t,s;i=t=s=0;while(c=v[1][i++]){s^=c>13^c%9>4;t+=s+(c>46^!(c%19)^s);}printf("%d",t);}

Текст многоугольника должен быть передан в качестве первого аргумента командной строки; это должно работать с или без какого-либо количества новых строк / пробелов.

Это просто читает в многоугольнике по одному символу за раз, s переключается ли в настоящее время внутри или за пределами многоугольника на '/', 'L' или '\', и t увеличивается на 1 на '/', 'V', и '\', или на 2, если внутри / 0, если снаружи на 'L', '_', пробел и символ новой строки.

Я впервые пробую свои силы в любом виде «игры в гольф» (или C, в той степени, в которой он отличается от C ++), поэтому любая критика приветствуется!

Джонатан Олдрич
источник
Добро пожаловать и хорошая работа! В любом случае, вы можете пропустить, i=t=s=0;я думаю, C инициализирует все ints до 0. Также посмотрите, сможете ли вы превратить whileпетлю в forпетлю; это часто экономит несколько байтов.
Ypnypn
Используя вышеприведенную идею цикла for, я думаю, что вы можете сделать что-то вроде этого: ...int i,t,s;for(i=t=s=0;c=v[1][i++];t+=s+(c>46^!(c%19)^s))s^=c>13^c%9>4;...что должно сохранить 4 байта; один {, один} и два;
DaedalusAlpha
Также, как упоминалось выше, очевидно, что глобальные переменные автоматически устанавливаются в 0, поэтому, если бы их int i,t,v;нужно было помещать перед, mainа не внутри, мы могли бы избавиться от i=t=s=0общей экономии еще 7 байтов.
DaedalusAlpha
3

POSIX сед, 245 244

POSIX sed, без расширений или расширенных регулярных выражений. Вход ограничен максимальным размером пространства хранения sed - мандаты POSIX не менее 8192; GNU управляет больше. Эта версия предполагает, что до или после фигуры не будет пустых строк; дополнительные 10 байтов кода, указанного в расширении, могут соответствовать этому требованию (в оригинальном вопросе это не уточняется).

H
/^\([L\\]_*\/\|V\| \)*$/!d
x
s/[_ ]/  /g
s/^/!/
s/$/!/
:g
s/\([^V]\)V/V\1/
tg
y/V/ /
s/L/!  /g
s,[/\\], ! ,g
s/![^!]*!//g
:d
/ /{
s/     /v/g
s/vv/x/g
/[ v]/!s/\b/0/2
s/  /b/g
s/bb/4/
s/b /3/
s/v /6/
s/vb/7/
s/v3/8/
s/v4/9/
y/ bvx/125 /
td
}

Расширено и аннотировано

#!/bin/sed -f

# If leading blank lines may exist, then delete them
# (and add 8 bytes to score)
#/^ *$/d

# Collect input into hold space until we reach the end of the figure
# The end is where all pieces look like \___/ or V
H
/^\([L\\]_*\/\|V\| \)*$/!d

x

# Space and underscore each count as two units
s/[_ ]/  /g

# Add an edge at the beginning and end, so we can delete matching pairs
s/^/!/
s/$/!/
# Move all the V's to the beginning and convert each
# to a single unit of area
:gather
s/\([^V]\)V/V\1/
tgather
y/V/ /

# L is a boundary to left of cell; / and \ in middle
s/L/!  /g
s,[/\\], ! ,g

# Strip out all the bits of outer region
s/![^!]*!//g

# Now, we have a space for each unit of area, and no other characters
# remaining (spaces are convenient because we will use \b to match
# where they end).  To count the spaces, we use roman numerals v and x
# to match five and ten, respectively.  We also match two (and call
# that 'b').  At the end of the loop, tens are turned back into spaces
# again.
:digit
/ /{
s/     /v/g
s/vv/x/g
/[ v]/!s/\b/0/2
s/  /b/g
s/bb/4/
s/b /3/
s/v /6/
s/vb/7/
s/v3/8/
s/v4/9/
y/ bvx/125 /
tdigit
}

# If trailing blank lines may exist, then stop now
# (and add 2 bytes to score)
#q
Тоби Спейт
источник
1

C, 84 байта

a;i;f(char*s){for(;*s;a+=strchr("\\/V",*s++)?1:i+i)i^=!strchr("\nV_ ",*s);return a;}

Мы переходим на другую сторону, когда видим \, /или L; мы всегда добавляем один для \\, /или V, но добавляем 2 (если внутри) или 0 (если снаружи) для пробела, новой строки Lили _.

Переменные aи iпредполагаются равными нулю при входе - они должны быть сброшены, если функция должна вызываться более одного раза.

Ungolfed:

int a;                          /* total area */
int i;                          /* which side; 0=outside */
int f(char*s)
{
    while (*s) {
        i ^= !strchr("\nV_ ",*s);
        a += strchr("\\/V",*s++) ? 1 : i+i;
    }
    return a;
}

Тестовая программа:

#include <stdio.h>
int main()
{
    char* s;
    s = "  _  \n"
        "  V  \n";
    printf("%s\n%d\n", s, f(s));
    a=i=0;

    s = "/L\n"
        "\\/\n";
    printf("%s\n%d\n", s, f(s));
    a=i=0;


    s = "    /VV\\\n"
        "    L  /\n"
        "     L/";
    printf("%s\n%d\n", s, f(s));
    a=i=0;

    s = "  ____/\\ \n"
        "  \\    /\n"
        "/\\/   /\n"
        "\\____/";
    printf("%s\n%d\n", s, f(s));
    a=i=0;

    s = "   /V\\\n"
        "  /   \\__ \n"
        "  \\     /\n"
        "/\\/   /V\n"
        "L____/";
    printf("%s\n%d\n", s, f(s));
    a=i=0;

    return 0;
}
Тоби Спейт
источник