Água retida em uma escava de haste hexagonal

22

Tenho um monte de hastes hexagonais coladas em uma escultura estranha. As hastes têm 1 a 99 centímetros (cm) de comprimento e 1 cm quadrado na área da seção transversal. Todas as hastes são coladas em uma face hexagonal a pelo menos uma outra haste. As hastes estão todas alinhadas na borda inferior.

Depois de algumas chuvas fortes, a escultura está cheia de água. Quanta água contém?

Entrada

Seu programa deve ler (via stdin ou um arquivo) um número de linhas que consistem em pares de espaços e pares de dígitos, especificando o comprimento das barras neste formato:

  aa  bb
cc  dd  ee
  ff  gg

Cada haste (como dd aqui) é colada a um máximo de 6 hastes circundantes, como mostrado nos exemplos. As hastes ausentes são orifícios e não coletam água. Por exemplo, a entrada

  04  04
04  01  03
  04  04

representaria a seguinte escultura:

insira a descrição da imagem aqui

A haste central é a altura 1(não encontrei um bom ângulo em que a haste também seja visível). Agora, a coluna acima dessa barra podia conter 2 cm de água, antes que ela transbordasse sobre a 3barra à direita. Como nenhuma das outras varas pode reter água acima delas, a resposta seria 2. Aqui estão dois exemplos mais complexos:

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

Saída

Seu programa deve produzir um único inteiro, fornecendo o volume de água em centímetros cúbicos.

Ponto

Sua pontuação é a contagem de bytes do seu código fonte. Vitórias mais baixas.

As brechas padrão são proibidas como de costume.

Este quebra-cabeça foi inspirado em uma pergunta da SPOJ .

Cavaleiro Lógico
fonte
4
Eu tive problemas para visualizar isso nas duas primeiras vezes que li, então tomei a liberdade de adicionar um diagrama e um pouco mais de explicação para o primeiro exemplo. Espero que você não se importe.
Martin Ender
Isso é realmente semelhante aos outros desafios que envolvem formas que se enchem de água.
FUZxxl
2
@FUZxxl temos outros desafios assim?
Optimizer
1
@FUZxxl Só me lembro desse desafio , que é muito diferente.
Martin Ender
@ Optimizer Este é um pouco semelhante.
Zgarb

Respostas:

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

Lê a entrada através de STDIN e grava o resultado em STDOUT.

Explicação

Começamos do zero e aumentamos incrementalmente o nível da água da seguinte maneira: Suponha que o nível da água seja h e desejemos adicionar 1 centímetro de água. Vamos chamar hexágonos de altura h ou menos, aqueles que estão prestes a ir (ou já estão) para a água, " submersos ". A água derramará através de qualquer hexágono submerso que não esteja cercado por seis vizinhos. Eliminamos todos esses hexágonos; é claro, agora alguns outros hexágonos submersos podem ter menos de seis vizinhos e precisam ser eliminados também. Continuamos dessa maneira até a convergência, ou seja, até que todos os hexágonos submersos restantes tenham exatamente seis vizinhos. Neste ponto, adicionamos o número de hexágonos submersos (o volume de água ganho) à contagem total e aumentamos o nível da água.

Eventualmente, todos os hexágonos serão eliminados e paramos.

Ell
fonte
Você deve conseguir barbear um personagem usando em -3<c-b<3 vez de 3>abs(c-b).
DLosc
@DLosc Ah, mas eles são números complexos;) #
Ell Ell
Fascinante. Não entendi isso.
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 :+}

Breve descrição do algoritmo:

  • analisa a entrada e, para cada haste, salva uma matriz de dois elementos no formato [haste_ altura, altura_água]
  • hastes são colocadas em um hash e indexadas por suas coordenadas x, y
  • a parte com vazamento de água leva em consideração as alturas da haste / água dos vizinhos imediatos

Uma versão um pouco mais legível está disponível aqui: http://ideone.com/cWkamV

Execute a versão online com os testes: http://ideone.com/3SFjPN

Cristian Lupascu
fonte
scanleva um argumento de bloco. Você pode apenas fazer scan(/../){...}. Em vez de 'varredura (/../) mapear {| v | ...} . (You don't need the | v | `porque dentro do scanbloco que você pode $&, $1etc.)
Jordan
@ Jordan Grandes observações! Obrigado!
Cristian Lupascu