22
\$\begingroup\$

I have bunch of hexagonal rods glued together into an odd sculpture. The rods are 1 to 99 centimetres (cm) long and 1 square cm in cross-section area. All rods are glued on a hexagonal face to at least one other rod. The rods are all aligned at their bottom edge.

After some heavy rain, the sculpture is full of water. How much water does it hold?

Input

Your program should read in (via stdin or a file) a number of lines consisting of pairs of spaces and pairs of digits specifying the length of the rods in this format:

  aa  bb
cc  dd  ee
  ff  gg

Each rod (like dd here) is glued to a maximum of 6 surrounding rods as shown in the examples. Missing rods are holes and do not gather water. For example, the input

  04  04
04  01  03
  04  04

would represent the following sculpture:

enter image description here

The centre rod is height 1 (I didn't find a good angle where that rod is also visible). Now the column above that rod could hold 2 cm of water, before it would overflow over the 3 rod on the right. Since none of the other rods can hold any water above them, the answer would be 2. Here are two more complex examples:

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

Output

Your program should output a single integer giving the volume of water in cubic centimetres.

Score

Your score is the byte count of your source code. Lowest wins.

The standard loopholes are prohibited as usual.

This puzzle was inspired by a SPOJ Question.

\$\endgroup\$
  • 4
    \$\begingroup\$ I had trouble visualising this the first two times I read it, so I took liberty of adding a diagram and a bit more explanation for the first example. Hope you don't mind. \$\endgroup\$ – Martin Ender Mar 2 '15 at 13:36
  • \$\begingroup\$ This is really similar to the other challenges involving shapes filling with water. \$\endgroup\$ – FUZxxl Mar 2 '15 at 13:36
  • 2
    \$\begingroup\$ @FUZxxl we have other challenges like that ? \$\endgroup\$ – Optimizer Mar 2 '15 at 13:38
  • 1
    \$\begingroup\$ @FUZxxl I only recall this challenge, which is very different. \$\endgroup\$ – Martin Ender Mar 2 '15 at 13:42
  • \$\begingroup\$ @Optimizer This one is somewhat similar. \$\endgroup\$ – Zgarb Mar 2 '15 at 13:53
4
\$\begingroup\$

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

Reads input through STDIN and writes the result to STDOUT.

Explanation

We start at zero and incrementally increase the water level as follows: Suppose that the water level is h, and we want to add 1 centimeter of water. We'll call hexagons of height h or less, ones that are about to go (or already are) underwater, "submerged." The water will spill through any submerged hexagon that isn't surrounded by six neighbors. We eliminate all such hexagons; of course, now some other submerged hexagons might have less than six neighbors, and they need to be eliminated as well. We continue in this fashion until convergence, i.e., until all remaining submerged hexagons have exactly six neighbors. At this point we add the number of submerged hexagons (the gained water volume) to the total count, and increment the water level.

Eventually, all the hexagons will have been eliminated and we halt.

\$\endgroup\$
  • \$\begingroup\$ You should be able to shave a character by using -3<c-b<3 instead of 3>abs(c-b). \$\endgroup\$ – DLosc Mar 4 '15 at 2:51
  • \$\begingroup\$ @DLosc Ah, but they're complex numbers ;) \$\endgroup\$ – Ell Mar 4 '15 at 14:59
  • \$\begingroup\$ Fascinating. Did not catch that. \$\endgroup\$ – DLosc Mar 4 '15 at 17:19
2
\$\begingroup\$

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

Brief description of the algorithm:

  • parses the input, and for each rod saves a two-element array of the form [rod_height, water_height]
  • rods are placed in a hash and indexed by their x,y coordinates
  • the water leaking part takes into account the rod/water heights of the immediate neighbors

A slightly more readable version is available here: http://ideone.com/cWkamV

Run the golfed version online with tests: http://ideone.com/3SFjPN

\$\endgroup\$
  • \$\begingroup\$ scan takes a block argument. You can just do scan(/../){...} instead of 'scan(/../).map{|v|...}. (You don't need the |v|` because Inside the scan block you can $&, $1, etc.) \$\endgroup\$ – Jordan Sep 2 '16 at 12:40
  • \$\begingroup\$ @Jordan Great observations! Thanks! \$\endgroup\$ – Cristian Lupascu Sep 3 '16 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.