Woda trzymana w sześciokątnej scuplture prętowej

22

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

wprowadź opis zdjęcia tutaj

Ś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 3prę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 .

Logic Knight
źródło
4
Miałem problem z wizualizacją tego za pierwszym razem, kiedy go czytałem, więc mogłem dodać schemat i trochę więcej wyjaśnień dla pierwszego przykładu. Mam nadzieję, że nie masz nic przeciwko.
Martin Ender
Jest to bardzo podobne do innych wyzwań związanych z wypełnianiem kształtów wodą.
FUZxxl,
2
@FUZxxl mamy inne podobne wyzwania?
Optymalizator
1
@FUZxxl Pamiętam tylko to wyzwanie , które jest zupełnie inne.
Martin Ender
@Optimizer Ten jest nieco podobny.
Zgarb

Odpowiedzi:

4

Python 2, 222 bajty

import sys
y=h=v=0;B={}
for l in sys.stdin:
 z=y;y+=2j
 while l:
    if"0"<l:B[z]=int(l[:2])
    l=l[2:];z+=1
while B:C=B;B={b:B[b]for b in B if(h<B[b])+sum(3>abs(c-b)for c in B)/7};a=C==B;h+=a;v+=a*sum(h>B[b]for b in B)
print v

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ę.

Łokieć
źródło
Powinieneś być w stanie ogolić postać za pomocą -3<c-b<3 zamiast 3>abs(c-b).
DLosc
@DLosc Ah, ale to liczby zespolone;)
Ell
Fascynujący. Nie złapałem tego.
DLosc
2

Rubin 299

f=->i{s={}
l=i.lines
y=0
l.map{|r|x=0
r.scan(/../){s[[x,y]]=[v=$&.to_i,v<1?0:99];x+=1}
y+=1}
loop{break if s.map{|c,r|x,y=c
m = [[-1,-1],[1,-1],[-2,0],[2,0],[1,-1],[1,1]].map{|w,z|s[[x+w,y+z]]}.map{|n|n ?n[0]+n[1]:0}.min
r[1]=[0,m-r[0]].max if r[0]+r[1]>m&&r[1]>0}.none?}
s.map{|c,r|r[1]}.reduce :+}

Krótki opis algorytmu:

  • analizuje dane wejściowe i dla każdego pręta zapisuje tablicę dwuelementową o postaci [rod_height, water_height]
  • pręty są umieszczane w haszu i indeksowane według ich współrzędnych x, y
  • część wyciekająca z wody uwzględnia wysokość pręta / wody bezpośrednich sąsiadów

Nieco bardziej czytelna wersja jest dostępna tutaj: http://ideone.com/cWkamV

Uruchom wersję golfową online z testami: http://ideone.com/3SFjPN

Cristian Lupascu
źródło
scanprzyjmuje argument blokowy. Można po prostu zrobić scan(/../){...}. Zamiast „scan (/../) map {| v | ...} . (You don't need the | v |` bo Wewnątrz scanbloku można $&, $1itp)
Jordan
@Jordan Świetne obserwacje! Dzięki!
Cristian Lupascu,