31
\$\begingroup\$

You should write a program or function which receives a string representing an ascii-art polygon as input and outputs ot returns the area of the polygon.

The input is a string consisting of the characters _ / \ L V space and newline defining a simple polygon (which means no extra segments, no self-touch and no self-intersect).

The area of a single character cell is 2

  • _ splits the cell into sizes 0 and 2
  • \ splits the cell into sizes 1 and 1
  • / splits the cell into sizes 1 and 1
  • L splits the cell into sizes 0 and 2
  • V splits the cell into sizes 1 and 1 (The two sides of the V will always be on the same side of the polygon so they are treated together in the listing.)

Every character connects the two corners of its character cell which you expect (e.g. top left and top right in case of V).

An example with area of 7 (1+2+1 in the second row and 1+1+1 in the third one):

 _
/ \
V\/

Input

  • Input will form a rectangle, i.e. there will be the same number of characters between newlines.
  • There can be extra whitespace on any side of the polygon.
  • Trailing newline is optional.

Output

  • A single positive integer, the area of the polygon.

Examples

Outputs are after the last row of their inputs.

  _  
  V  

1

/L
\/

3



    /VV\
    L  /
     L/
14

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

32  

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

45

This is code-golf so the shortest entry wins.

\$\endgroup\$
4
  • \$\begingroup\$ your third example should be 14 \$\endgroup\$
    – Optimizer
    Apr 27, 2015 at 11:00
  • \$\begingroup\$ @Optimizer Thanks, corrected. \$\endgroup\$
    – randomra
    Apr 27, 2015 at 11:58
  • \$\begingroup\$ Is the lack of ^ intentionally? \$\endgroup\$ Apr 28, 2015 at 11:41
  • \$\begingroup\$ @RobAu Yes, that doesn't look good enough. \$\endgroup\$
    – randomra
    Apr 28, 2015 at 12:07

8 Answers 8

22
\$\begingroup\$

Pyth, 47 46 45 36 30

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

Explanation:

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.

We have two states, "in the polygon", and "out of the polygon". The following characters each do the following when reading them from top-left to bottom-right:

/ \     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

Note that "add one to area" and "if in polygon, add two to area" are mutually exclusive.

\$\endgroup\$
3
  • \$\begingroup\$ I'm really confused on how x= works. Is this documented somewhere? \$\endgroup\$
    – Jakube
    Apr 28, 2015 at 10:17
  • \$\begingroup\$ @Jakube It's augmented assignment. \$\endgroup\$
    – orlp
    Apr 28, 2015 at 10:32
  • \$\begingroup\$ @Jakube It's like += or *= or whatever. In this case x is being used as xor, so it's exactly the same as Python's ^=. \$\endgroup\$
    – isaacg
    Apr 29, 2015 at 18:25
14
\$\begingroup\$

Retina, 293 + 15 = 308 314 385 bytes

;`\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>

Each line goes in a separate file, so I've added 13 to the byte count. Alternatively, you can put that all in a single file as is and use the -s flag. The <empty> stand for actually empty files or lines.

Unfortunately, I need 187 bytes just to convert the result from unary to decimal. I guess I really should implement this some time soon.

Explanation

Retina is a regex-based language (which I wrote exactly for being able to do stuff like this with regex). Each pair of files/lines defines a replacement stage, with the first line being the pattern and the second line the replacement string. Patterns can be preceded by a `-delimited configuration string, which may contain the usual regex modifiers, as well as some Retina-specific options. For the above program, the relevant options are ;, which suppresses output of that stage and +, which applies the replacement in a loop until the result stops changing.

The idea of the solution is to count each line separately, because we can always decide by the characters already encountered whether we're inside or outside the polygon. This also means I can join the entire thing into a single line, because going the beginning and end of a line are always outside the polygon. We can also note that _ and space are completely identical for a line sweep algorithm, as well as \ and /. So as a first step I replace all newlines and spaces by _ and all \ by / to simplify some code later on.

I'm keeping track of the current inside/outside state with the characters i and o, while also using the is to tally the area. To do so I start by prepending an o to the joined line to mark that we're outside the polygon. I'm also adding an iio to the very end of the input, which I'll use as a lookup to generate new characters.

Then, the first large replacement simply replaces an i or o followed by one of /V_L with the next set of characters, thereby flooding and tallying the entire thing. The replacement table looks as follows, where the columns correspond to the last character in that line and the rows to the next character (where S is for space and <> for an empty string). I've included all characters of the input to show the equivalences I've already made use of:

     i     o

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

Note that the final character then always indicates whether after the character we're inside or outside the polygon, while the number of is corresponds to the area that needs to be added to the polygon. As an example here are the results of the first four iterations on the last example input (this was generated by an old version which actually flooded each line separately, but the principle is still the same):

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

Lastly, I just get rid of all the os and the line breaks by removing everything that matches [^i], and the remainder is the decimal-to-unary conversion which is rather boring.

\$\endgroup\$
5
\$\begingroup\$

CJam, 48 43 29 bytes

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

Update: Golfed a lot using maths and the state*2 trick from orlp's answer.

How it works (Outdated, updating soon)

We split the input on newline and then for each part we maintain a counter of occurrences of boundary characters L\/. This counter % 2 will tell us which of the two partitions amounts to choose for all of the characters. Then we find the index of each character in the string L _. \/V will give -1 referring to the last element in an array. After getting the index, we use 4558Zb2/ to create the array [[2 0] [0 2] [0 2] [1 1]] and then choose the correct of the count using the counter.

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

Try it online here

\$\endgroup\$
4
\$\begingroup\$

Perl, 65 58 bytes

map{map{$b^=2*y,/\\L,,;$a+=y,/\\V,,||$b}split//}<>;print$a
  • Toggle $b between 0 and 2 upon seeing / \ or L.
  • Add 1 to $a upon seeing / \ or V.
  • Add $b to $a upon seeing anything else.
\$\endgroup\$
2
  • \$\begingroup\$ Nice solution, Perl is surprisingly compact. \$\endgroup\$
    – orlp
    Apr 28, 2015 at 5:00
  • 1
    \$\begingroup\$ Input processing can be simplified for some more gains: $/=\1;$-^=2*y,/\\L,,,$a+=y,/\\V,,||$-for<>;print$a \$\endgroup\$
    – nutki
    Apr 28, 2015 at 13:52
4
\$\begingroup\$

GNU sed, 290 + 1

The + 1 is to account for the -r switch passed to sed. Comments and additional whitespace not counted in the score.

I haven't looked in great detail, but I think this is probably similar to Martin's Retina answer:

:                      # 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

Overview

  • Replace each unit of area with a colon :
  • Count the number of colons

Notes

  • sed is line oriented so needs some work to process multiple lines at once. The N command does this by appending a newline then the next line to the current pattern space. The difficulty with N is that once it gets to the input stream EOF, it quits sed completely without any option to do further processing. To get around this, we count the current set of colons at the end of each line, just before reading in the next line.

Output:

$ echo '   /V\
  /   \__ 
  \     /
/\/   /V
L____/' |sed -rf polyarea.sed
45
$
\$\endgroup\$
3
\$\begingroup\$

C, 93 96 108 bytes

Edit: Took into account suggestions in the comments, converted the while into a single-statement for loop, and removed the "i" variable entirely.

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);}

Original post:

This looked like a fun and simple enough problem to finally get me to create an account here.

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);}

The polygon text should be passed as the first command-line argument; this should work with or without any amount of newlines / whitespace.

This just reads in the polygon one character at a time, s switches whether currently in or outside of the polygon on '/', 'L', or '\', and t increases by 1 on '/', 'V', and '\', or by 2 if inside / 0 if outside on 'L', '_', space and newline.

This is my first time trying my hand at any sort of "golfing" (or C, to the extent it differs from C++), so any criticisms are appreciated!

\$\endgroup\$
3
  • \$\begingroup\$ Welcome and good job! You may be able to skip the i=t=s=0; I think C initializes all ints to 0 anyway. Also, see if you can turn the while loop into a for loop; that often saves a few bytes. \$\endgroup\$
    – Ypnypn
    Apr 28, 2015 at 3:58
  • \$\begingroup\$ Using the idea of the for loop above I think you can do something like this: ...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;... which should save 4 bytes; one {, one } and two ; \$\endgroup\$ Apr 28, 2015 at 11:28
  • \$\begingroup\$ Also as mentioned above, apparently global variables are automatically set to 0, so if int i,t,v; was to be put in front of main instead of inside we could get rid of i=t=s=0 altogether saving another 7 bytes. \$\endgroup\$ Apr 28, 2015 at 11:38
3
\$\begingroup\$

POSIX sed, 245 244

POSIX sed, no extensions or extended regexps. Input is limited to the maximum hold space size of sed - POSIX mandates at least 8192; GNU manages more. This version assumes that there will be no blank lines before or after the shape; an extra 10 bytes of code, indicated in the expansion, can accommodate that if it's a requirement (original question doesn't specify).

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
}

Expanded and annotated

#!/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
\$\endgroup\$
1
\$\begingroup\$

C, 84 bytes

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

We switch sides whenever we see \, / or L; we always add one for \\, / or V, but add 2 (if inside) or 0 (if outside) for space, newline, L or _.

The variables a and i are assumed to be zero on entry - they must be reset if the function is to be called more than once.

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;
}

Test program:

#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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.