Marching Squares to algorytm z grafiki komputerowej, który służy do odzyskiwania izokonturów 2D z siatki próbek (patrz także jego starszy brat Marching Cubes dla ustawień 3D). Chodzi o to, aby przetwarzać każdą komórkę siatki niezależnie i określać kontury przechodzące przez tę komórkę na podstawie wartości w jej rogach.

Pierwszym krokiem w tym procesie jest określenie, które krawędzie są połączone konturami, w oparciu o to, czy rogi znajdują się powyżej czy poniżej wartości konturu. Dla uproszczenia weźmiemy pod uwagę tylko kontury wzdłuż wartości 0, tak że interesuje nas, czy narożniki są dodatnie czy ujemne. Istnieją przypadki, aby odróżnić:24 = 16

^{Źródło obrazu: Wikipedia}

Identyfikacja bieli i czerni tak naprawdę nie ma tutaj znaczenia, ale dla pewności powiedz, że biel jest dodatnia, a czerń ujemna. Zignorujemy przypadki, w których jeden z rogów jest dokładnie 0.

Punkty siodełka (przypadki 5 i 10) stanowią dodatkową trudność: nie jest jasne, z których przekątnych należy korzystać, patrząc tylko na rogi. Można to rozwiązać, znajdując średnią z czterech rogów (tj. Przybliżenie wartości środkowej) i wybierając przekątne w taki sposób, że kontury oddzielają środek od narożników o przeciwnym znaku. Jeśli średnia jest dokładnie 0, można wybrać dowolny przypadek.

Zazwyczaj te 16 przypadków jest po prostu przechowywane w tabeli odnośników. Jest to świetne pod względem wydajności, ale oczywiście wolelibyśmy, aby kod był tutaj krótki . Twoim zadaniem jest wykonanie tego kroku wyszukiwania i wydrukowanie reprezentacji sprawy w formacie ASCII przy możliwie najmniejszym kodzie.

Wyzwanie

Otrzymasz wartości czterech rogów (niezerowe liczby całkowite) w ustalonej kolejności. Następnie należy wygenerować prawidłowy układ konturów, poprawnie rozwiązując przypadki punktów siodłowych.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Dane wejściowe mogą być pobierane w dowolnym dogodnym formacie ciągu lub listy.

16 przypadków będzie reprezentowanych w sztuce ASCII przy użyciu jednego z następujących bloków 5x5:

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

Nie wolno drukować żadnych początkowych ani końcowych białych znaków, ale można wydrukować jedną opcjonalną nową linię.

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

Przypadki testowe

Przypadki testowe zakładać, że wejście jest podana w kolejności od góry w lewo , prawym górnym , dolnym rogu , w prawym dolnym rogu . Przypadki testowe są przedstawione w 9 grupach, po jednej odpowiadającej każdemu z 9 przedstawionych powyżej przedstawień (w tej samej kolejności, zaczynając od pustej komórki, kończąc na dwóch punktach siodłowych).

[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]

Ponadto następujące przypadki testowe mogą zwrócić jeden z punktów siodełka (do wyboru):

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

Ruby, 201 180 176

Jest to anonimowa funkcja lambda, którą można wywołać w sposób pokazany na przykładzie bez golfa.

Nie zawiera żadnej zmiennej s. W wersji bez golfa do wyrażenia złożonego przypisywane jest wyrażenie s, zanim zostanie użyte. 4 bajty są zapisywane w wersji golfowej, umieszczając je w linii. Jedyna inna różnica między wersjami to białe znaki i komentarze.

Jeśli dopuszczalne jest zwrócenie wyniku jako tablicy pięciu ciągów pięciu znaków, zamiast drukowania na standardowe wyjście, można zapisać jeszcze jeden bajt.

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

Jestem zadowolony z parsowania tablicy, ale myślę, że mogą istnieć krótsze sposoby na utworzenie wyniku.

Wszystkie cztery elementy tablicy wejściowej są mnożone przez ostatni element. Gwarantuje to, że ostatni element jest dodatni, i zmniejsza liczbę przypadków z 16 do 8. Elementy są przesunięte w prawo o 9 miejsc, dzięki czemu wszystkie liczby dodatnie stają się 0, a wszystkie liczby ujemne stają się -1 (przynajmniej w zakresie danych wejściowych podane w przypadkach testowych.) Następnie są one ANDowane przez, 1<<array indexaby dać 3-bitową liczbę binarną wskazującą wzorzec (właściwie 4-bitowy, ale ponieważ ostatni element jest zawsze dodatni, czwarty bit jest zawsze zerowy.)

Ta liczba od 0..7 jest następnie podawana do tabeli wyszukiwania (westchnienia) w celu ustalenia, które znaki w każdym wierszu nie są spacjami. Na tym etapie obsługiwane są dwa różne wyświetlacze dla siodełka, z alternatywą dla liczby w tabeli odnośników, jeśli suma jest dodatnia (pytanie mówi o rozważeniu „średniej”, ale ponieważ jesteśmy tylko zainteresowany znakiem, nie ma znaczenia, jeśli weźmiemy pod uwagę sumę).

Sposób wyświetlania danych wyjściowych jest, mam nadzieję, jasny z komentarzy w kodzie.

nie wziął udziału w programie testowym

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