L'eau retenue dans un scuplture tige hexagonale

22

J'ai un tas de tiges hexagonales collées ensemble dans une sculpture étrange. Les tiges mesurent de 1 à 99 centimètres (cm) de long et 1 cm2 de section transversale. Toutes les tiges sont collées sur une face hexagonale à au moins une autre tige. Les tiges sont toutes alignées sur leur bord inférieur.

Après de fortes pluies, la sculpture est pleine d'eau. Combien d'eau contient-elle?

Contribution

Votre programme doit lire (via stdin ou un fichier) un certain nombre de lignes constituées de paires d'espaces et de paires de chiffres spécifiant la longueur des tiges dans ce format:

  aa  bb
cc  dd  ee
  ff  gg

Chaque tige (comme dd ici) est collée à un maximum de 6 tiges environnantes comme indiqué dans les exemples. Les tiges manquantes sont des trous et ne recueillent pas d'eau. Par exemple, l'entrée

  04  04
04  01  03
  04  04

représenterait la sculpture suivante:

entrez la description de l'image ici

La tige centrale est la hauteur 1(je n'ai pas trouvé un bon angle où cette tige est également visible). Maintenant, la colonne au-dessus de cette tige pouvait contenir 2 cm d'eau, avant de déborder sur la 3tige de droite. Puisqu'aucune des autres cannes ne peut contenir d'eau au-dessus d'elles, la réponse serait 2. Voici deux exemples plus complexes:

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

Sortie

Votre programme doit produire un seul entier indiquant le volume d'eau en centimètres cubes.

But

Votre score est le nombre d'octets de votre code source. Victoires les plus faibles.

Les failles standard sont interdites comme d'habitude.

Ce puzzle a été inspiré par une question SPOJ .

Logic Knight
la source
4
J'ai eu du mal à visualiser cela les deux premières fois que je l'ai lu, j'ai donc pris la liberté d'ajouter un diagramme et un peu plus d'explications pour le premier exemple. J'espère que cela ne vous dérange pas.
Martin Ender
Ceci est vraiment similaire aux autres défis impliquant des formes remplies d'eau.
FUZxxl
2
@FUZxxl nous avons d'autres défis comme ça?
Optimizer
1
@FUZxxl Je ne me souviens que de ce défi , qui est très différent.
Martin Ender
@Optimizer Celui-ci est quelque peu similaire.
Zgarb

Réponses:

4

Python 2, 222 octets

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

Lit l'entrée via STDIN et écrit le résultat dans STDOUT.

Explication

Nous commençons à zéro et augmentons progressivement le niveau d'eau comme suit: Supposons que le niveau d'eau soit h , et nous voulons ajouter 1 centimètre d'eau. Nous appellerons des hexagones de hauteur h ou moins, ceux qui sont sur le point de passer (ou qui sont déjà) sous l'eau, « submergés ». L'eau se répandra à travers tout hexagone submergé qui n'est pas entouré de six voisins. Nous éliminons tous ces hexagones; bien sûr, maintenant certains autres hexagones submergés pourraient avoir moins de six voisins, et ils doivent également être éliminés. Nous continuons ainsi jusqu'à la convergence, c'est-à-dire jusqu'à ce que tous les hexagones immergés restants aient exactement six voisins. À ce stade, nous ajoutons le nombre d'hexagones immergés (le volume d'eau gagné) au nombre total et augmentons le niveau d'eau.

Finalement, tous les hexagones auront été éliminés et nous nous arrêterons.

Aune
la source
Vous devriez pouvoir raser un personnage en utilisant -3<c-b<3 au lieu de 3>abs(c-b).
DLosc
@DLosc Ah, mais ce sont des nombres complexes;)
Ell
Fascinant. Je n'ai pas compris ça.
DLosc
2

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

Brève description de l'algorithme:

  • analyse l'entrée, et pour chaque tige enregistre un tableau à deux éléments de la forme [rod_height, water_height]
  • les tiges sont placées dans un hachage et indexées par leurs coordonnées x, y
  • la partie qui fuit d'eau tient compte des hauteurs tige / eau des voisins immédiats

Une version légèrement plus lisible est disponible ici: http://ideone.com/cWkamV

Exécutez la version golfée en ligne avec des tests: http://ideone.com/3SFjPN

Cristian Lupascu
la source
scanprend un argument de bloc. Vous pouvez juste faire scan(/../){...}. Au lieu de « scan (/../) {carte | v | ...} . (You don't need the | v |` parce que l' intérieur du scanbloc , vous pouvez $&, $1etc.)
Jordanie
@Jordan Bonnes observations! Merci!
Cristian Lupascu