Fläche eines ASCII-Polygons

31

Sie sollten ein Programm oder eine Funktion schreiben, die eine Zeichenfolge empfängt, die ein ASCII-Polygon als Ein- und Ausgabe darstellt, um den Bereich des Polygons zurückzugeben.

Die Eingabe ist eine Zeichenfolge, die aus den Zeichen besteht _ / \ L V spaceund newlineein einfaches Polygon definiert (dh keine zusätzlichen Segmente, keine Selbstberührung und keine Selbstüberschneidung).

Die Fläche einer einzelnen Zeichenzelle beträgt 2

  • _teilt die Zelle in Größen 0und2
  • \teilt die Zelle in Größen 1und1
  • /teilt die Zelle in Größen 1und1
  • Lteilt die Zelle in Größen 0und2
  • VUnterteilt die Zelle in Größen 1und 1(Die beiden Seiten des Vwerden immer auf der gleichen Seite des Polygons sein, sodass sie in der Auflistung zusammen behandelt werden.)

Jedes Zeichen verbindet die beiden Ecken seiner erwarteten Zeichenzelle (z. B. oben links und oben rechts bei V).

Ein Beispiel mit einer Fläche von 7 ( 1+2+1in der zweiten und 1+1+1dritten Reihe ):

 _
/ \
V\/

Eingang

  • Die Eingabe bildet ein Rechteck, dh zwischen den Zeilenumbrüchen befindet sich die gleiche Anzahl von Zeichen.
  • Auf jeder Seite des Polygons kann sich ein zusätzliches Leerzeichen befinden.
  • Der Zeilenumbruch ist optional.

Ausgabe

  • Eine einzelne positive Ganzzahl, die Fläche des Polygons.

Beispiele

Die Ausgaben stehen nach der letzten Zeile ihrer Eingaben.

  _  
  V  

1

/L
\/

3



    /VV\
    L  /
     L/
14

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

32  

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

45

Dies ist Code-Golf, also gewinnt der kürzeste Einstieg.

randomra
quelle
Ihr drittes Beispiel sollte 14 sein
Optimizer
@Optimizer Danke, korrigiert.
Randomra
Ist der Mangel ^ absichtlich?
RobAu
@RobAu Ja, das sieht nicht gut genug aus.
Randomra

Antworten:

5

CJam, 48 43 29 Bytes

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

Update : Viel Golf gespielt mit Mathe und dem State * 2-Trick von Orlps Antwort.

Wie es funktioniert (veraltet, bald aktualisiert)

Wir teilen die Eingabe in Zeilenumbrüche auf und führen dann für jeden Teil einen Zähler für das Auftreten von Grenzzeichen L\/. Dieser Zähler% 2 teilt uns mit, welcher der beiden Partitionsbeträge für alle Zeichen ausgewählt werden soll. Dann finden wir den Index jedes Zeichens in der Zeichenfolge L _. \/VGibt an, dass -1auf das letzte Element in einem Array verwiesen wird. Nachdem wir den Index erhalten haben, 4558Zb2/erstellen wir das Array [[2 0] [0 2] [0 2] [1 1]]und wählen anhand des Zählers die korrekte Anzahl aus.

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

Probieren Sie es hier online aus

Optimierer
quelle
22

Pyth, 47 46 45 36 30

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

Erläuterung:

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.

Wir haben zwei Zustände, "im Polygon" und "außerhalb des Polygons". Die folgenden Zeichen tun jeweils Folgendes, wenn sie von links oben nach rechts unten gelesen werden:

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

Beachten Sie, dass sich "Einer zur Fläche hinzufügen" und "Wenn Sie sich in einem Polygon befinden, fügen Sie zwei zur Fläche hinzu" gegenseitig ausschließen.

orlp
quelle
Ich bin wirklich verwirrt darüber, wie es x=funktioniert. Ist das irgendwo dokumentiert?
Jakube
@Jakube Es ist eine erweiterte Aufgabe.
Orlp
@ Jakube Es ist wie +=oder *=oder was auch immer. In diesem Fall xwird es als xor verwendet, es ist also genau das gleiche wie bei 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>

Jede Zeile wird in einer eigenen Datei abgelegt, daher habe ich die Bytezahl um 13 erhöht. Alternativ können Sie alles in einer einzigen Datei speichern und das -sFlag verwenden. Die <empty>stehen für tatsächlich leere Dateien oder Zeilen.

Leider brauche ich nur 187 Bytes, um das Ergebnis von unär in dezimal umzuwandeln. Ich denke, ich sollte es wirklich tun das bald umsetzen .

Erläuterung

Retina ist eine auf Regex basierende Sprache (die ich genau geschrieben habe, um solche Dinge mit Regex machen zu können). Jedes Paar von Dateien / Zeilen definiert eine Ersetzungsstufe, wobei die erste Zeile das Muster und die zweite Zeile die Ersetzungszeichenfolge ist. `Mustern kann eine durch -begrenzte Konfigurationszeichenfolge vorangestellt werden , die die üblichen Regex-Modifikatoren sowie einige Retina-spezifische Optionen enthalten kann. Für das obige Programm sind die relevanten Optionen ;, die die Ausgabe dieser Stufe und unterdrücken+ die Ersetzung in einer Schleife anwenden, bis sich das Ergebnis nicht mehr ändert.

Die Idee der Lösung ist, jede Zeile einzeln zu zählen, da wir immer anhand der Zeichen entscheiden können, ob wir innerhalb oder außerhalb des Polygons sind. Dies bedeutet auch, dass ich das Ganze zu einer einzigen Linie zusammenfügen kann, da der Anfang und das Ende einer Linie immer außerhalb des Polygons liegen. Wir können auch feststellen, dass _und der Raum für einen Linien-Sweep-Algorithmus ebenso wie \und völlig identisch sind /. Als ersten Schritt ersetze ich also alle Zeilenumbrüche und Leerzeichen durch _und durch\ nach /, um später den Code zu vereinfachen.

Ich verfolge den aktuellen Innen- / Außenstatus mit den Zeichen iund verwende ogleichzeitig das is, um den Bereich zu erfassen. Dazu beginne ich mit einem vorangestellteno , der verbundenen Linie um zu markieren, dass wir außerhalb des Polygons sind. Außerdem füge ich iioganz am Ende der Eingabe ein hinzu, das ich zum Nachschlagen verwenden werde, um neue Zeichen zu generieren.

Dann ersetzt der erste große Ersatz einfach einen ioder ogefolgt von einem /V_Lder folgenden Zeichensätze, wodurch das Ganze überflutet und gezählt wird. Die Ersetzungstabelle sieht wie folgt aus: Die Spalten entsprechen dem letzten Zeichen in dieser Zeile und die Zeilen dem nächsten Zeichen (wobei SLeerzeichen und <>eine leere Zeichenfolge verwendet werden). Ich habe alle Zeichen der Eingabe eingefügt, um die Entsprechungen anzuzeigen, die ich bereits verwendet habe:

     i     o

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

Beachten Sie, dass das letzte Zeichen dann immer gibt an, ob nach dem Charakter , wir sind innerhalb oder außerhalb des Polygons, während die Zahl der is entspricht der Fläche , dass der Bedarf an dem Polygon hinzugefügt werden. Als Beispiel hier sind die Ergebnisse der ersten vier Iterationen der letzten Beispieleingabe (diese wurde von einer alten Version generiert, die tatsächlich jede Zeile separat geflutet hat, aber das Prinzip ist immer noch dasselbe):

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

Zuletzt oentferne ich einfach alle s und die Zeilenumbrüche, indem ich alles entferne, was passt [^i], und der Rest ist die Umwandlung von Dezimal zu Unär, die ziemlich langweilig ist.

Martin Ender
quelle
4

Perl, 65 58 Bytes

map{map{$b^=2*y,/\\L,,;$a+=y,/\\V,,||$b}split//}<>;print$a
  • Schalte $ b zwischen 0 und 2 um, wenn du / \ oder L siehst.
  • Addiere 1 zu $ ​​a, wenn du / \ oder V siehst.
  • Fügen Sie $ b zu $ ​​a hinzu, wenn Sie etwas anderes sehen.
Helios
quelle
Schöne Lösung, Perl ist überraschend kompakt.
Orlp
1
Die $/=\1;$-^=2*y,/\\L,,,$a+=y,/\\V,,||$-for<>;print$a
Eingabeverarbeitung
4

GNU sed, 290 + 1

Die +1 ist für die Rechnung -r Schalter an sed übergeben wird. Kommentare und zusätzliches Leerzeichen werden in der Partitur nicht berücksichtigt.

Ich habe nicht sehr detailliert geschaut, aber ich denke, das ähnelt wahrscheinlich Martins Retina-Antwort :

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

Überblick

  • Ersetzen Sie jede Flächeneinheit durch einen Doppelpunkt :
  • Zählen Sie die Anzahl der Doppelpunkte

Anmerkungen

  • sedDa es zeilenorientiert ist, sind einige Arbeiten erforderlich, um mehrere Zeilen gleichzeitig zu verarbeiten. Der NBefehl fügt dazu eine neue Zeile und dann die nächste Zeile an den aktuellen Musterbereich an. Die Schwierigkeit Nbesteht darin, dass der EOF-Eingabestream sedvollständig beendet wird, ohne dass eine weitere Verarbeitung möglich ist. Um dies zu umgehen, zählen wir die aktuellen Doppelpunkte am Ende jeder Zeile, bevor wir die nächste Zeile einlesen.

Ausgabe:

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

C 93 96 108 Bytes

Bearbeiten: Berücksichtigte Vorschläge in den Kommentaren, wandelte die while-Anweisung in eine Einzelanweisung für eine Schleife um und entfernte die Variable "i" vollständig.

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

Ursprünglicher Beitrag:

Das sah nach einem lustigen und recht einfachen Problem aus, um mich endlich dazu zu bringen, hier ein Konto zu erstellen.

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

Der Polygontext sollte als erstes Befehlszeilenargument übergeben werden. Dies sollte mit oder ohne Zeilenvorschub / Leerzeichen funktionieren.

Dabei wird jeweils nur ein Zeichen in das Polygon eingelesen, es wird gewechselt, ob sich das Polygon gerade in oder außerhalb von '/', 'L' oder '\' befindet, und t wird bei '/', 'V' um 1 erhöht. und '\' oder um 2, wenn innen / 0, wenn außen auf 'L', '_', Leerzeichen und Zeilenumbruch.

Dies ist mein erstes Mal, dass ich mich in irgendeiner Art von "Golfen" (oder C, soweit es sich von C ++ unterscheidet) versuche. Kritik ist also willkommen!

Jonathan Aldrich
quelle
Herzlich willkommen und gute Arbeit! Möglicherweise können Sie die i=t=s=0;I think C-Initialisierungen intohnehin alle s auf 0 überspringen . Überprüfen Sie auch, ob Sie die whileSchleife in eine forSchleife verwandeln können . das spart oft ein paar bytes.
Ypnypn
Mit der Idee der for - Schleife oben Ich denke , Sie so etwas tun kann: ...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;...die 4 Bytes speichern sollte; eins {, eins} und zwei;
DaedalusAlpha
Wie bereits erwähnt, werden anscheinend globale Variablen automatisch auf 0 gesetzt. Wenn Sie int i,t,v;also vor mainstatt nach innen stellen, können Sie i=t=s=0insgesamt weitere 7 Byte sparen.
DaedalusAlpha
3

POSIX sed, 245 244

POSIX sed, keine Erweiterungen oder erweiterte reguläre Ausdrücke. Die Eingabe ist auf die maximale Speicherplatzgröße von sed-POSIX-Mandaten von mindestens 8192 beschränkt. GNU schafft mehr. In dieser Version wird davon ausgegangen, dass vor oder nach der Form keine Leerzeilen vorhanden sind. Weitere 10 Byte Code, die in der Erweiterung angegeben sind, können dies berücksichtigen, wenn dies erforderlich ist (die ursprüngliche Frage wird nicht angegeben).

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
}

Erweitert und kommentiert

#!/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
quelle
1

C 84 Bytes

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

Wir wechseln die Seiten, wann immer wir sehen \, /oder L; wir addieren immer eins für \\, /oder V, aber addieren 2 (wenn innen) oder 0 (wenn außen) für Leerzeichen, Zeilenumbruch,L oder_ .

Die Variablen a undi werden bei der Eingabe als Null angenommen - sie müssen zurückgesetzt werden, wenn die Funktion mehrmals aufgerufen werden soll.

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

Testprogramm:

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