To wyzwanie w Internecie zadane przez Palantir Technologies w wywiadach .
Grupa rolników ma pewne dane dotyczące wysokości, a my pomożemy im zrozumieć, w jaki sposób opady deszczu przepływają przez ich pola uprawne. Będziemy reprezentować ziemię jako dwuwymiarowy układ wysokości i zastosujemy następujący model, oparty na pomyśle, że woda spływa w dół:
Jeśli wszystkie cztery sąsiadujące komórki komórki mają wyższe wysokości, nazywamy tę komórkę zlewem; woda zbiera się w zlewach. W przeciwnym razie woda przepłynie do sąsiedniej komórki o najniższej wysokości. Jeśli komórka nie jest zlewem, możesz założyć, że ma unikalny najniższy sąsiad i że ten sąsiad będzie niższy niż komórka.
Mówi się, że komórki, które spływają do tego samego zlewu - bezpośrednio lub pośrednio - są częścią tego samego basenu.
Twoim wyzwaniem jest podzielenie mapy na baseny. W szczególności, biorąc pod uwagę mapę rzędnych, twój kod powinien podzielić mapę na baseny i wyświetlać rozmiary basenów, w kolejności malejącej.
Załóżmy, że mapy wysokości są kwadratowe. Wprowadzanie rozpocznie się od linii z jedną liczbą całkowitą, S, wysokością (i szerokością) mapy. Każda kolejna linia S będzie zawierała wiersz mapy, każda z liczbami całkowitymi S - rzędnymi komórek S w rzędzie. Niektórzy rolnicy mają małe działki, takie jak poniższe przykłady, a niektórzy mają większe działki. Jednak w żadnym przypadku rolnik nie będzie posiadał działki większej niż S = 5000.
Twój kod powinien wyświetlać rozdzieloną spacjami listę rozmiarów umywalek, w kolejności malejącej. (Końcowe spacje są ignorowane).
Kilka przykładów znajduje się poniżej.
Wejście:
3
1 5 2
2 4 7
3 6 9
Wynik:
7 2
Umywalki oznaczone jako A i B to:
A A B
A A B
A A A
Wejście:
1
10
Wynik:
1
W tym przypadku jest tylko jeden basen.
Wejście:
5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4 2
3 3 5 2 1
Wynik:
11 7 7
Umywalki oznaczone jako A, B i C to:
A A A A A
A A A A A
B B A C C
B B B C C
B B C C C
Wejście:
4
0 2 1 3
2 1 0 4
3 3 3 3
5 5 2 1
Wynik:
7 5 4
Umywalki oznaczone jako A, B i C to:
A A B B
A B B B
A B B C
A C C C
źródło
Odpowiedzi:
Matematyka
Listę rozmiarów umywalek można zdobyć
gdzie
m
są podane dane wejściowe. Aby wyświetlić macierz, jak te w pytaniu może zastąpić jeden// Reverse@Sort@Part[Tally[Flatten@#], All, 2] &
z/. {1 -> "A", 2 -> "B", 3 -> "C"} // MatrixForm
lub można wyświetlić go jako obraz zamiast korzystania//ImageAdjust//Image
.źródło
JavaScript - 673
707730751e=[],g=[],h=[],m=[],q=[];function r(){a=s,b=t;function d(d,A){n=a+d,p=b+A;c>e[n][p]&&(u=!1,v>e[n][p]&&(v=e[n][p],w=n,k=p))}c=e[a][b],u=!0,v=c,w=a,k=b;0!=a&&d(-1,0);a!=l&&d(1,0);0!=b&&d(0,-1);b!=l&&d(0,1);g[a][b]=w;h[a][b]=k;return u}function x(a,b,d){function c(a,b,c,k){g[a+b][c+k]==a&&h[a+b][c+k]==c&&(d=x(a+b,c+k,d))}d++;0!=a&&c(a,-1,b,0);a!=l&&c(a,1,b,0);0!=b&&c(a,0,b,-1);b!=l&&c(a,0,b,1);return d}y=$EXEC('cat "'+$ARG[0]+'"').split("\n");l=y[0]-1;for(z=-1;z++<l;)e[z]=y[z+1].split(" "),g[z]=[],h[z]=[];for(s=-1;s++<l;)for(t=-1;t++<l;)r()&&m.push([s,t]);for(z=m.length-1;0<=z;--z)s=m[z][0],t=m[z][1],q.push(x(s,t,0));print(q.sort(function(a,b){return b-a}).join(" "));
Wyniki testu (przy użyciu Nashorn):
Prawdopodobnie wystąpiłyby problemy ze stosem dla map wielkości 5000 (ale to szczegół implementacji :).
Niezminimalizowane źródło w całej swej kruchości:
Lepsze wyniki minimalizacji uzyskałem, dzieląc obiekty elementów na osobne tablice, globalizując wszędzie, gdzie to możliwe, i obejmując skutki uboczne. NSFW.
Skutki minimalizacji kodu:
Mógłbym osiągnąć blisko 700 bajtów bez edycji zminimalizowanego kodu, gdybym chciał zmodyfikować oryginalne źródło. Ale nie zrobiłem tego, ponieważ myślę, że pozostawienie go takim, jakim jest, daje ciekawy widok od samego początku.
źródło
var e=[],g=[],h=[],l,m=[],q=[]
doe=g=h=l=m=q=[]
. Prawdopodobnie możesz również pozbyć się innych zastosowań tegovar
słowa kluczowego, jeśli nie ukrywasz żadnych zmiennych globalnych.Python: 276
306 365bajtówTo moja pierwsza próba golfa. Sugestie są mile widziane!
edycja: importowanie i zamykanie plików zajmuje zbyt wiele znaków! Podobnie jest z przechowywaniem plików w zmiennych i interpretacją listy zagnieżdżonej.
w pełni skomentowane (2130 bajtów ...)
źródło
open('a').read()
Myślę, że powinieneś być w stanie to zrobić .JavaScript (ECMAScript 6) - 226 znaków
Wyjaśnienie
Poprzednia wersja - 286 znaków
Zakłada, że dane wejściowe są w zmiennej
S
;Wyjaśnienie
Test
Wyjścia:
[7, 2]
Wyjścia:
[11, 7, 7]
Wyjścia:
[5, 7, 4]
źródło
Julia, 315
Wystarczy funkcja rekurencyjna, która określa, że bieżąca komórka jest zlewem lub znajduje odpływ, a następnie wywołuje ją na każdym zestawie wskaźników. Nie zawracałem sobie głowy wykonaniem części wejściowej, ponieważ i tak nie zamierzałem wygrać, a ta część nie jest fajna.
źródło
Haskell, 271
286Być może nadal będzie jakiś kod do gry w golfa.
Wyjaśnienie
Podstawowy pomysł: dla każdej komórki (i, j) znajdź najniższą komórkę w „sąsiedztwie”. Daje to wykres [ (i, j) → (mi, mj) ]. Jeśli komórka jest samą najniższą komórką, to (i, j) == (mi, mj) .
Ten wykres można iterować: Dla każdego a → b na wykresie zastąp go a → c, gdzie b → c jest na wykresie. Gdy ta iteracja nie przyniesie więcej zmian, wówczas każda komórka na wykresie wskazuje najniższą komórkę, do której przepłynie.
Aby to zrobić, wprowadzono kilka zmian: Po pierwsze, współrzędne są reprezentowane jako lista długości 2, a nie pary. Po drugie, po znalezieniu sąsiadów komórki są reprezentowane przez ich indeks w liniowym układzie komórek, a nie we współrzędnych 2D. Po trzecie, ponieważ istnieje n * n komórek, po n * n iteracjach wykres musi być stabilny.
Ungolf'd
źródło
Ruby, 216
Jest to nieco inne podejście, które wywołuje „przepływ” tylko na każdym kwadracie (wydajność zależy od wydajności Array :: index). Przechodzi od najwyższego wzniesienia do najniższego, opróżniając pojedynczo komórkę do swojego najniższego sąsiada i zaznaczając komórkę jako wykonaną (dodając 1 do rzędnej), gdy jest zrobiona.
Skomentowane i rozmieszczone:
Dziennik zmian:
216 - lepszy sposób na odznaczenie wskaźników spoza zakresu
221 - okazuje się, że „11” pojawia się przed „2” ... powróć do
to_i
, ale zaoszczędź trochę miejsca na naszychgets
es.224 - Po co w ogóle deklarować
s
? Ieach
=>map
229 - masywna gra w golfa - najpierw posortuj elewacje w
s
(i w ten sposób upuśćwhile
klauzulę), użyjmin_by
zamiastsort_by{...}[0]
, nie zawracaj sobie głowyto_i
wysokościami, użyjflat_map
i zmniejszselect{}
blok271 - przeniesiono rozmiar zlewu do nowej tablicy i użyto sort_by
315 - przeniesiono wyniki do tablicy, która dawała różnego rodzaju korzyści, i skrócono listę indeksów sąsiadów. również zyskał jeden znak w indeksie lambda
355 - pierwsze zatwierdzenie
źródło
Python -
470 447 445 393 392 378 376 375 374369 bajtówNie mogę się powstrzymać!
Nie jest to zwycięskie rozwiązanie, ale miałem dużo zabawy z jego tworzeniem. Ta wersja nie zakłada, że dane wejściowe mają być przechowywane w dowolnym miejscu i zamiast tego odczytuje je ze standardowego wejścia. Maksymalna głębokość rekurencji = największa odległość od punktu do zlewu.
Nie mam dzisiaj czasu, aby to wyjaśnić, ale oto niepoznany kod:W rzeczywistości jest zupełnie inny niż oryginalny kod. Czytam linie S ze standardowego, podzielonego, mapującego na int i spłaszczam listy, by uzyskać spłaszczone pole. Następnie raz przewijam wszystkie płytki (nazwijmy je kafelkami). Funkcja przepływu sprawdza sąsiadujące kafelki i wybiera tę o najmniejszej wartości. Jeśli jest mniejsza niż wartość bieżącego kafelka, przejdź do niego i wróć. Jeśli nie, bieżący kafelek jest umywalką i tworzona jest nowa umywalka. Zwracana wartość rekurencji to identyfikator basenu.
źródło
JavaScript (ES6) 190
203Edytuj Trochę więcej ES6ish (1 rok później ...)
Zdefiniuj funkcję z wierszami wejściowymi jako ciągiem znaków, w tym znakami nowej linii, zwracaj dane wyjściowe jako ciąg znaków ze spacjami końcowymi
źródło
Perl 6,
419404Dodano nowe linie dla przejrzystości. Możesz je bezpiecznie usunąć.
Stare rozwiązanie:
A jednak mnie biją rozwiązania Python i JavaScript.
źródło