Mam kilka sześciokątnych prętów sklejonych ze sobą w dziwną rzeźbę. Pręty mają od 1 do 99 centymetrów (cm) i 1 cm kwadratowy w przekroju. Wszystkie pręty są przyklejone na sześciokątnej powierzchni do co najmniej jednego innego pręta. Wszystkie pręty są wyrównane na dolnej krawędzi.
Po ulewnym deszczu rzeźba jest pełna wody. Jak dużo wody to trzyma?
Wkład
Twój program powinien wczytać (przez stdin lub plik) kilka wierszy składających się z par spacji i par cyfr określających długość prętów w tym formacie:
aa bb
cc dd ee
ff gg
Każdy pręt (jak tutaj dd) jest przyklejony do maksymalnie 6 otaczających prętów, jak pokazano w przykładach. Brakujące pręty to dziury i nie zbierają wody. Na przykład dane wejściowe
04 04
04 01 03
04 04
będzie reprezentować następującą rzeźbę:
Środkowy pręt ma wysokość 1
(nie znalazłem dobrego kąta, w którym ten pręt również jest widoczny). Teraz kolumna nad tym prętem może pomieścić 2 cm wody, zanim będzie mogła przelać się nad 3
prętem po prawej stronie. Ponieważ żaden z pozostałych prętów może posiadać żadnej wody nad nimi, będzie odpowiedź 2
. Oto dwa bardziej złożone przykłady:
Example 2:
55 34 45 66
33 21 27
23 12 01 77
36 31 74
answer = 35 ( 2 on top of 21
+11 on top of 12
+22 on top of 01, before everything overflows over 23)
Example 3:
35 36 77 22 23 32 54 24
33 07 02 04 21 54 07 07 07 76
20 04 07 07 01 20 54 11 81 81 07 76
20 67 67 22 07 01 78 54 07 81 07 81 09 76
20 67 07 67 22 22 07 44 55 54 07 81 07 07 61 07 20
67 57 50 50 07 07 14 03 02 15 81 99 91 07 81 04
67 07 50 50 87 39 45 41 34 81 07 07 89 07 81 79
67 07 50 50 07 07 07 27 07 27 81 07 07 79 81 78
20 67 67 07 07 07 07 99 33 46 02 81 07 07 81 01 20
33 07 07 01 05 01 92 20 02 81 07 81 15 32
22 07 20 20 07 20 63 02 80 81 15 32
45 20 01 20 39 20 15 07 15 32
23 20 20 29 43 21 18 41 20 66 66 43 21
90 99 47 07 20
50 20 02 48
70 56 20
90
answer = 1432
Wydajność
Twój program powinien wypisać jedną liczbę całkowitą podającą objętość wody w centymetrach sześciennych.
Wynik
Twój wynik to liczba bajtów kodu źródłowego. Najniższe wygrane.
Standardowe luki są jak zwykle zabronione.
Ta łamigłówka została zainspirowana pytaniem SPOJ .
źródło
Odpowiedzi:
Python 2, 222 bajty
Odczytuje dane wejściowe przez STDIN i zapisuje wynik do STDOUT.
Wyjaśnienie
Zaczynamy od zera i stopniowo zwiększamy poziom wody w następujący sposób: Załóżmy, że poziom wody wynosi h , i chcemy dodać 1 centymetr wody. Będziemy nazywać sześciokąty o wysokości h lub mniejszej, te, które mają zamiar zejść (lub już są) pod wodą, „ zanurzone ”. Woda wyleje się przez każdy zanurzony sześciokąt, który nie jest otoczony przez sześciu sąsiadów. Eliminujemy wszystkie takie sześciokąty; oczywiście teraz niektóre inne zanurzone sześciokąty mogą mieć mniej niż sześciu sąsiadów i należy je również wyeliminować. Kontynuujemy w ten sposób, aż do zbieżności, tj. Dopóki wszystkie pozostałe zanurzone sześciokąty nie będą miały dokładnie sześciu sąsiadów. W tym momencie dodajemy liczbę zanurzonych sześciokątów (uzyskaną objętość wody) do całkowitej liczby i zwiększamy poziom wody.
W końcu wszystkie sześciokąty zostaną wyeliminowane i zatrzymamy się.
źródło
-3<c-b<3
zamiast3>abs(c-b)
.Rubin 299
Krótki opis algorytmu:
Nieco bardziej czytelna wersja jest dostępna tutaj: http://ideone.com/cWkamV
Uruchom wersję golfową online z testami: http://ideone.com/3SFjPN
źródło
scan
przyjmuje argument blokowy. Można po prostu zrobićscan(/../){...}
. Zamiast „scan (/../) map {| v | ...}. (You don't need the
| v |` bo Wewnątrzscan
bloku można$&
,$1
itp)