Wasser in einem Sechskantstab

22

Ich habe ein paar Sechskantstangen zu einer seltsamen Skulptur zusammengeklebt. Die Stäbe sind 1 bis 99 cm lang und haben eine Querschnittsfläche von 1 cm². Alle Stäbe sind sechseckig mit mindestens einem anderen Stab verklebt. Die Stangen sind alle an ihrer Unterkante ausgerichtet.

Nach einem heftigen Regen ist die Skulptur voller Wasser. Wie viel Wasser hält es?

Eingang

Ihr Programm sollte (über stdin oder eine Datei) eine Anzahl von Zeilen einlesen, die aus Leerzeichenpaaren und Ziffernpaaren bestehen und die Länge der Stäbe in diesem Format angeben:

  aa  bb
cc  dd  ee
  ff  gg

Jeder Stab (wie hier dd) wird wie in den Beispielen gezeigt mit maximal 6 umgebenden Stäben verklebt. Fehlende Stangen sind Löcher und sammeln kein Wasser. Zum Beispiel die Eingabe

  04  04
04  01  03
  04  04

würde die folgende Skulptur darstellen:

Bildbeschreibung hier eingeben

Die Mittelstange ist hoch 1(ich habe keinen guten Winkel gefunden, in dem diese Stange auch sichtbar ist). Jetzt konnte die Säule über diesem Stab 2 cm Wasser aufnehmen, bevor es 3rechts über den Stab lief. Da keine der anderen Stangen Wasser über sich halten kann, wäre die Antwort 2. Hier sind zwei komplexere Beispiele:

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

Ausgabe

Ihr Programm sollte eine einzelne Ganzzahl ausgeben, die das Wasservolumen in Kubikzentimetern angibt.

Ergebnis

Ihre Punktzahl ist die Byteanzahl Ihres Quellcodes. Niedrigste Gewinne.

Die üblichen Regelungslücken sind wie gewohnt verboten.

Dieses Puzzle wurde von einer SPOJ-Frage inspiriert .

Logik-Ritter
quelle
4
Ich hatte Probleme, mir das die ersten beiden Male vorzustellen, als ich es las, also nahm ich mir die Freiheit, ein Diagramm und ein bisschen mehr Erklärungen für das erste Beispiel hinzuzufügen. Ich hoffe es macht dir nichts aus.
Martin Ender
Dies ähnelt den anderen Herausforderungen, bei denen Formen mit Wasser gefüllt werden.
FUZxxl
2
@FUZxxl haben wir noch andere herausforderungen?
Optimierer
1
@FUZxxl Ich erinnere mich nur an diese Herausforderung , die ganz anders ist.
Martin Ender
@Optimizer Dieser ist etwas ähnlich.
Zgarb

Antworten:

4

Python 2, 222 Bytes

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

Liest die Eingabe über STDIN und schreibt das Ergebnis in STDOUT.

Erläuterung

Wir beginnen bei Null und erhöhen den Wasserstand schrittweise wie folgt: Angenommen, der Wasserstand ist h , und wir möchten 1 Zentimeter Wasser hinzufügen. Wir bezeichnen Sechsecke mit einer Höhe von h oder weniger als "unter Wasser ". Das Wasser wird durch alle untergetauchten Sechsecke fließen, die nicht von sechs Nachbarn umgeben sind. Wir eliminieren alle diese Sechsecke. Natürlich könnten jetzt einige andere untergetauchte Sechsecke weniger als sechs Nachbarn haben, und sie müssen ebenfalls beseitigt werden. Wir fahren auf diese Weise bis zur Konvergenz fort, dh bis alle verbleibenden untergetauchten Sechsecke genau sechs Nachbarn haben. Zu diesem Zeitpunkt addieren wir die Anzahl der eingetauchten Sechsecke (das gewonnene Wasservolumen) zur Gesamtzahl und erhöhen den Wasserstand.

Irgendwann sind alle Sechsecke beseitigt und wir halten an.

Ell
quelle
Sie sollten in der Lage sein, einen Charakter zu rasieren, indem Sie -3<c-b<3 anstelle von verwenden 3>abs(c-b).
DLosc
@ DLosc Ah, aber sie sind komplexe Zahlen;)
Ell
Faszinierend. Habe das nicht verstanden.
DLosc
2

Ruby 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 :+}

Kurzbeschreibung des Algorithmus:

  • analysiert die Eingabe und speichert für jede Stange ein Array mit zwei Elementen der Form [rod_height, water_height]
  • Stäbe werden in einem Hash platziert und durch ihre x, y-Koordinaten indiziert
  • Der wasserleckende Teil berücksichtigt die Stab- / Wasserhöhen der unmittelbaren Nachbarn

Eine etwas besser lesbare Version finden Sie hier: http://ideone.com/cWkamV

Führen Sie die Golfversion online mit Tests aus: http://ideone.com/3SFjPN

Cristian Lupascu
quelle
scanNimmt ein Blockargument. Sie können einfach tun scan(/../){...}. Anstelle von ‚Scan (/../) Karte {| v | ...} . (You don't need the | v |` weil Innerhalb des scanBlock möglich $&, $1etc.)
Jordan
@Jordan Tolle Beobachtungen! Vielen Dank!
Cristian Lupascu