Marching Squares ist ein Algorithmus aus der Computergrafik, mit dem 2D-Isokonturen aus einem Raster von Stichproben wiederhergestellt werden (siehe auch den großen Bruder Marching Cubes für 3D-Einstellungen). Die Idee ist, jede Zelle des Gitters unabhängig zu verarbeiten und die Konturen, die durch diese Zelle verlaufen, basierend auf den Werten an ihren Ecken zu bestimmen.

Der erste Schritt in diesem Prozess besteht darin, zu bestimmen, welche Kanten durch Konturen verbunden sind, basierend darauf, ob die Ecken über oder unter dem Wert der Kontur liegen. Der Einfachheit halber werden nur Konturen entlang des Werts berücksichtigt 0, sodass wir daran interessiert sind, ob die Ecken positiv oder negativ sind. Es gibt Fälle zu unterscheiden:24 = 16

^{Bildquelle: Wikipedia}

Die Identifizierung von Weiß und Schwarz spielt hier keine Rolle, aber für die Bestimmtheit sagen wir, dass Weiß positiv und Schwarz negativ ist. Wir werden Fälle ignorieren, in denen eine der Ecken genau ist 0.

Die Sattelpunkte (Fälle 5 und 10) bieten eine zusätzliche Schwierigkeit: Es ist nicht klar, welche Diagonalen verwendet werden sollen, wenn nur die Ecken betrachtet werden. Dies kann gelöst werden, indem der Durchschnitt der vier Ecken ermittelt wird (dh eine Annäherung an den Mittelwert) und die Diagonalen so gewählt werden, dass die Konturen die Mitte von den Ecken mit dem entgegengesetzten Vorzeichen trennen. Wenn der Durchschnitt genau ist 0, kann jeder Fall gewählt werden.

Normalerweise werden diese 16 Fälle einfach in einer Nachschlagetabelle gespeichert. Dies ist sehr effizient, aber wir würden es natürlich vorziehen, wenn der Code hier kurz ist. Ihre Aufgabe ist es also, diesen Suchschritt auszuführen und eine ASCII-Darstellung des Falls in so wenig Code wie möglich zu drucken.

Die Herausforderung

Sie erhalten die Werte der vier Ecken (Ganzzahlen ungleich Null) in einer festen Reihenfolge Ihrer Wahl. Sie sollten dann das richtige Layout der Konturen generieren und die Sattelpunktfälle korrekt auflösen.

Sie können ein Programm oder eine Funktion schreiben, indem Sie Eingaben über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), den Funktionsrückgabewert oder den Funktionsparameter (out) ausgeben.

Die Eingabe kann in einem beliebigen geeigneten Zeichenfolgen- oder Listenformat erfolgen.

Die 16 Fälle werden in ASCII-Grafik mit einem der folgenden 5x5-Blöcke dargestellt:

o---o  o---o  o---o
|   |  |   |  | | |
|   |  |---|  | | |
|   |  |   |  | | |
o---o  o---o  o---o

o---o  o---o  o---o  o---o
|/  |  |  \|  |   |  |   |
|   |  |   |  |   |  |   |
|   |  |   |  |\  |  |  /|
o---o  o---o  o---o  o---o

o---o  o---o
|/  |  |  \|
|   |  |   |
|  /|  |\  |
o---o  o---o

Sie dürfen keine führenden oder nachfolgenden Leerzeichen drucken, dürfen jedoch eine einzelne optionale neue Zeile drucken.

Dies ist Code Golf, daher gewinnt die kürzeste Antwort (in Bytes).

Testfälle

In den Testfällen wird davon ausgegangen, dass die Eingabe in der Reihenfolge oben links , oben rechts , unten links , unten rechts erfolgt . Testfälle werden in 9 Gruppen dargestellt, von denen eine jeder der 9 oben angegebenen Darstellungen entspricht (in derselben Reihenfolge, beginnend mit der leeren Zelle, endend mit den beiden Sattelpunkten).

[1, 2, 1, 3]
[-9, -2, -2, -7]

[4, 5, -1, -2]
[-1, -2, 3, 4]

[7, -7, 7, -7]
[-5, 5, -5, 5]

[1, -6, -4, -1]
[-2, 3, 3, 4]

[-1, 6, -4, -1]
[2, -3, 3, 4]   

[-1, -6, 4, -1]
[2, 3, -3, 4]

[-1, -6, -4, 1]
[2, 3, 3, -4]

[3, -8, -9, 2]
[-3, 8, 9, -2]

[8, -3, -2, 9]
[-8, 3, 2, -9]

Darüber hinaus können die folgenden Testfälle einen der Sattelpunkte (Ihre Wahl) zurückgeben:

[1, -4, -2, 5]
[-1, 4, 2, -5]

Ruby, 201 180 176

Dies ist eine anonyme Lambda-Funktion, die auf die im Beispiel ohne Wolf gezeigte Weise aufgerufen wird.

Dies enthält keine Variable s. In der ungolfed Version wird der sKlarheit halber ein komplexer Ausdruck zugewiesen , bevor er verwendet wird. In der Golfversion werden 4 Bytes gespeichert, indem sie inline gesetzt werden. Der einzige andere Unterschied zwischen den Versionen ist das Leerzeichen und die Kommentare.

Wenn es akzeptabel ist, die Ausgabe als Array aus fünf Zeichenfolgen mit jeweils fünf Zeichen zurückzugeben, kann ein weiteres Byte gespeichert werden, anstatt auf stdout zu drucken.

->a{p=t=0
4.times{|i|t+=a[i]*=a[3];p+=a[i]>>9&1<<i}
q=p==6&&t>0?19:'@AC@P*10'[p].ord
puts c='o---o',(0..2).map{|i|b=p*i==3?'|---|':'|   |';b[q%4]='|/|\|/'[q%4+(i&2)];q/=4;b},c}

Ich bin mit dem Parsen des Arrays zufrieden, aber ich denke, es gibt möglicherweise kürzere Möglichkeiten, die Ausgabe zu bilden.

Alle vier Elemente des Eingabearrays werden mit dem letzten Element multipliziert. Dies garantiert, dass das letzte Element positiv ist, und reduziert die Anzahl der Fälle von 16 auf 8. Die Elemente werden um 9 Stellen nach rechts verschoben, sodass alle positiven Zahlen zu 0 und alle negativen Zahlen zu -1 werden (zumindest im Eingabebereich) in den Testfällen angegeben.) Sie werden dann durch UND-verknüpft 1<<array index, um eine 3-Bit-Binärzahl zu erhalten, die das Muster angibt (tatsächlich 4-Bit, aber da das letzte Element immer positiv ist, ist das 4. Bit immer Null.)

Diese Zahl von 0..7 wird dann einer (Seufzer-) Nachschlagetabelle zugeführt, um zu bestimmen, welche Zeichen jeder Zeile keine Leerzeichen sind. In diesem Stadium werden die zwei verschiedenen Anzeigen für den Sattelkoffer behandelt, wobei eine Alternative zu der Zahl in der Nachschlagetabelle verwendet wird, wenn die Summe positiv ist (die Frage besagt, dass der "Durchschnitt" berücksichtigt werden soll, aber so wie wir es sind interessiert an dem Zeichen, spielt es keine Rolle, ob wir stattdessen die Summe betrachten.)

Die Art und Weise, wie die Anzeige der Ausgabe funktioniert, geht hoffentlich aus den Kommentaren im Code hervor.

ungolfed im Testprogramm

f=->a{p=t=0
  4.times{|i|                      #for each number in the input
    t+=a[i]*=a[3];                   #multiply each number by a[3]; totalize the sum in t
    p+=a[i]>>9&1<<i                  #shift right to find if negative; AND with 1<<i to build index number for pattern 
  }                                #q is a 3-digit base 4 number indicating which character of each line is non-whitespace (if any). 
  q=p==6&&t>0?19:'@AC@P*10'[p].ord #It's encoded in the magic string, except for the case of saddles with a positive total, which is encoded by the number 19.
  s=(0..2).map{|i|                 #build an array of 3 strings, indexes 0..2
    b=p*i==3?'|---|':'|   |';        #IF p is 3 and we are on row 1, the string is |---| for the horizontal line case. ELSE it is |   |.
    b[q%4]='|/|\|/'[q%4+(i&2)];      #The numbers in q indicate which character is to be modified. The characters in the string indicate the character to replace with.
    q/=4;                            #If q%4=0, the initial | is replaced by | (no change.) i&2 shifts the string index appropriately for the last row.
    b                                #divide q by 4, and terminate the loop with the expression b so that this is the object loaded into array s.  
  }
puts c='o---o',s,c}                #print the array s, capped with "o---o" above and below.


[[1, 2, 1, 3],
[-9, -2, -2, -7],

[4, 5, -1, -2],
[-1, -2, 3, 4],

[7, -7, 7, -7],
[-5, 5, -5, 5],

[1, -6, -4, -1],
[-2, 3, 3, 4],

[-1, 6, -4, -1],
[2, -3, 3, 4],

[-1, -6, 4, -1],
[2, 3, -3, 4],

[-1, -6, -4, 1],
[2, 3, 3, -4],

[3, -8, -9, 2],
[-3, 8, 9, -2],

[8, -3, -2, 9],
[-8, 3, 2, -9],

[1, -4, -2, 5],
[-1, 4, 2, -5]].each{|k|f.call(k)}