Área de un polígono ASCII

31

Debería escribir un programa o función que reciba una cadena que represente un polígono ascii-art como entrada y salida ot devuelve el área del polígono.

La entrada es una cadena que consta de los caracteres _ / \ L V spacey newlinedefine un polígono simple (lo que significa que no hay segmentos adicionales, ni auto-toque ni auto-intersección).

El área de una celda de un solo carácter es 2

  • _divide la celda en tamaños 0y2
  • \divide la celda en tamaños 1y1
  • /divide la celda en tamaños 1y1
  • Ldivide la celda en tamaños 0y2
  • Vdivide la celda en tamaños 1y 1(los dos lados del Vsiempre estarán en el mismo lado del polígono para que se traten juntos en la lista).

Cada personaje conecta las dos esquinas de su celda de caracteres que espera (por ejemplo, arriba a la izquierda y arriba a la derecha en caso de V).

Un ejemplo con área de 7 ( 1+2+1en la segunda fila y 1+1+1en la tercera):

 _
/ \
V\/

Entrada

  • La entrada formará un rectángulo, es decir, habrá el mismo número de caracteres entre las nuevas líneas.
  • Puede haber espacios en blanco adicionales en cualquier lado del polígono.
  • La nueva línea final es opcional.

Salida

  • Un solo entero positivo, el área del polígono.

Ejemplos

Las salidas son posteriores a la última fila de sus entradas.

  _  
  V  

1

/L
\/

3



    /VV\
    L  /
     L/
14

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

32  

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

45

Este es el código de golf, por lo que gana la entrada más corta.

randomra
fuente
su tercer ejemplo debería ser 14
Optimizer
@Optimizer Gracias, corregido.
randomra
Es la falta de ^ intencionalmente?
RobAu
@RobAu Sí, eso no se ve lo suficientemente bien.
randomra

Respuestas:

5

CJam, 48 43 29 bytes

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

Actualización : Golfé mucho usando las matemáticas y el truco del estado * 2 de la respuesta de orlp.

Cómo funciona (desactualizado, se actualizará pronto)

Dividimos la entrada en nueva línea y luego para cada parte mantenemos un contador de ocurrencias de caracteres de límite L\/. Este contador% 2 nos dirá cuál de las dos particiones equivale a elegir para todos los personajes. Luego encontramos el índice de cada carácter en la cadena L _. \/Vdará -1referencia al último elemento en una matriz. Después de obtener el índice, usamos 4558Zb2/para crear la matriz [[2 0] [0 2] [0 2] [1 1]]y luego elegimos el recuento correcto usando el contador.

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

Pruébalo en línea aquí

Optimizador
fuente
22

Pyth, 47 46 45 36 30

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

Explicación:

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.

Tenemos dos estados, "dentro del polígono" y "fuera del polígono". Cada uno de los siguientes caracteres hace lo siguiente cuando los lee de arriba a la izquierda a la derecha:

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

Tenga en cuenta que "agregar uno al área" y "si está en el polígono, agregar dos al área" son mutuamente excluyentes.

orlp
fuente
Estoy realmente confundido sobre cómo x=funciona. ¿Está esto documentado en alguna parte?
Jakube
@Jakube Es una asignación aumentada.
orlp
@Jakube Es como +=o *=o lo que sea. En este caso xse está utilizando como xor, por lo que es exactamente lo mismo que Python ^=.
isaacg
14

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>

Cada línea va en un archivo separado, así que agregué 13 al conteo de bytes. Alternativamente, puede poner todo eso en un solo archivo tal como está y usar la -sbandera. El <empty>soporte para archivos o líneas realmente vacías.

Desafortunadamente, necesito 187 bytes solo para convertir el resultado de unario a decimal. Creo que realmente debería implementar esto pronto .

Explicación

La retina es un lenguaje basado en expresiones regulares (que escribí exactamente para poder hacer cosas como esta con expresiones regulares). Cada par de archivos / líneas define una etapa de reemplazo, siendo la primera línea el patrón y la segunda línea la cadena de reemplazo. Los patrones pueden estar precedidos por una `cadena de configuración delimitada, que puede contener los modificadores de expresiones regulares habituales, así como algunas opciones específicas de Retina. Para el programa anterior, las opciones relevantes son ;, que suprime la salida de esa etapa y +, que aplica el reemplazo en un bucle hasta que el resultado deja de cambiar.

La idea de la solución es contar cada línea por separado, porque siempre podemos decidir por los caracteres ya encontrados si estamos dentro o fuera del polígono. Esto también significa que puedo unir todo en una sola línea, porque ir al principio y al final de una línea siempre está fuera del polígono. También podemos observar que _y el espacio son completamente idénticos para un algoritmo de barrido de línea, así como \y /. Por lo tanto, como primer paso sustituyo todos los saltos de línea y espacios por _y todo \por /simplificar algo de código más adelante.

Estoy realizando un seguimiento del estado actual interno / externo con los caracteres iy o, al mismo tiempo, uso el is para registrar el área. Para hacerlo, empiezo anteponiendo una oa la línea unida para marcar que estamos fuera del polígono. También estoy agregando un iioal final de la entrada, que usaré como una búsqueda para generar nuevos caracteres.

Luego, el primer reemplazo grande simplemente reemplaza uno io oseguido por uno de /V_Llos siguientes caracteres, inundando y contando todo. La tabla de reemplazo se ve de la siguiente manera, donde las columnas corresponden al último carácter en esa línea y las filas al siguiente carácter (donde Ses para el espacio y <>para una cadena vacía). He incluido todos los caracteres de la entrada para mostrar las equivalencias que ya utilicé:

     i     o

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

Tenga en cuenta que el carácter final siempre indica si después del carácter estamos dentro o fuera del polígono, mientras que el número de is corresponde al área que debe agregarse al polígono. Como ejemplo, aquí están los resultados de las primeras cuatro iteraciones en la última entrada de ejemplo (esto fue generado por una versión anterior que en realidad inundó cada línea por separado, pero el principio sigue siendo el mismo):

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

Por último, me deshago de todos los os y los saltos de línea eliminando todo lo que coincide [^i], y el resto es la conversión de decimal a unario, que es bastante aburrida.

Martin Ender
fuente
4

Perl, 65 58 bytes

map{map{$b^=2*y,/\\L,,;$a+=y,/\\V,,||$b}split//}<>;print$a
  • Cambie $ b entre 0 y 2 al ver / \ o L.
  • Agregue 1 a $ a al ver / \ o V.
  • Agregue $ b a $ a al ver algo más.
Helios
fuente
Buena solución, Perl es sorprendentemente compacta.
orlp
1
El procesamiento de entrada se puede simplificar para obtener más ganancias:$/=\1;$-^=2*y,/\\L,,,$a+=y,/\\V,,||$-for<>;print$a
nutki
4

GNU sed, 290 + 1

El + 1 es para tener en cuenta el -rcambio pasado a sed. Comentarios y espacios en blanco adicionales no contados en la puntuación.

No he mirado con gran detalle, pero creo que esto es probablemente similar a la respuesta de Martin 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

Visión general

  • Reemplace cada unidad de área con dos puntos :
  • Cuenta la cantidad de dos puntos

Notas

  • sedestá orientado a líneas, por lo que necesita algo de trabajo para procesar varias líneas a la vez. El Ncomando hace esto agregando una nueva línea y luego la siguiente línea al espacio de patrón actual. La dificultad Nes que una vez que llega al flujo de entrada EOF, se cierra por sedcompleto sin ninguna opción para realizar un procesamiento adicional. Para evitar esto, contamos el conjunto actual de dos puntos al final de cada línea, justo antes de leer en la siguiente línea.

Salida:

$ echo '   /V\
  /   \__ 
  \     /
/\/   /V
L____/' |sed -rf polyarea.sed
45
$
Trauma digital
fuente
3

C, 93 96108 bytes

Editar: Tomó en cuenta las sugerencias en los comentarios, convirtió el while en una sola declaración para el bucle y eliminó por completo la variable "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);}

Publicación original:

Esto parecía un problema bastante divertido y simple como para finalmente lograr que creara una cuenta aquí.

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

El texto del polígono debe pasarse como el primer argumento de línea de comandos; Esto debería funcionar con o sin ninguna cantidad de líneas nuevas / espacios en blanco.

Esto solo lee en el polígono un carácter a la vez, s cambia si actualmente está dentro o fuera del polígono en '/', 'L' o '\', y t aumenta en 1 en '/', 'V', y '\', o por 2 si está dentro / 0 si está afuera en 'L', '_', espacio y nueva línea.

Esta es la primera vez que pruebo mi mano en cualquier tipo de "golf" (o C, en la medida en que difiere de C ++), por lo que cualquier crítica es apreciada.

Jonathan Aldrich
fuente
Bienvenido y buen trabajo! Es posible que pueda omitir el i=t=s=0;Creo que C inicializa todos los ints a 0 de todos modos. Además, vea si puede convertir el whilebucle en un forbucle; eso a menudo ahorra unos pocos bytes.
Ypnypn
Usando la idea del bucle for anterior, creo que puede hacer algo como esto: ...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;...que debería ahorrar 4 bytes; uno {, uno} y dos;
DaedalusAlpha
Además, como se mencionó anteriormente, las variables aparentemente globales se configuran automáticamente en 0, por lo que si int i,t,v;se pusiera delante y mainno dentro, podríamos deshacernos de i=t=s=0guardar otros 7 bytes.
DaedalusAlpha
3

POSIX sed, 245 244

POSIX sed, sin extensiones o expresiones regulares extendidas. La entrada está limitada al tamaño máximo de espacio de retención de sed: POSIX exige al menos 8192; GNU logra más. Esta versión asume que no habrá líneas en blanco antes o después de la forma; un extra de 10 bytes de código, indicado en la expansión, puede acomodar eso si es un requisito (la pregunta original no especifica).

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
}

Ampliado y anotado

#!/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
Toby Speight
fuente
1

C, 84 bytes

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

Cambiamos de lado cada vez que vemos \, /o L; siempre agregamos uno para \\, /o V, pero agregamos 2 (si está dentro) o 0 (si está afuera) para espacio, nueva línea Lo _.

Las variables ay ise supone que son cero en la entrada: deben restablecerse si la función se llama más de una vez.

Sin golf:

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

Programa de prueba:

#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;
}
Toby Speight
fuente