Air ditahan dalam scuplture batang heksagonal

22

Saya memiliki banyak batang heksagonal yang direkatkan menjadi sebuah patung aneh. Batang memiliki panjang 1 hingga 99 sentimeter (cm) dan 1 cm persegi pada luas penampang. Semua batang direkatkan pada permukaan heksagonal ke setidaknya satu batang lainnya. Semua batang disejajarkan di tepi bawah.

Setelah hujan lebat, patung itu penuh air. Berapa banyak air yang ditampungnya?

Memasukkan

Program Anda harus membaca dalam (melalui stdin atau file) sejumlah baris yang terdiri dari pasangan spasi dan pasangan digit yang menentukan panjang batang dalam format ini:

  aa  bb
cc  dd  ee
  ff  gg

Setiap batang (seperti dd di sini) direkatkan hingga maksimum 6 batang di sekitarnya seperti yang ditunjukkan dalam contoh. Batang yang hilang adalah lubang dan tidak mengumpulkan air. Misalnya input

  04  04
04  01  03
  04  04

akan mewakili patung berikut:

masukkan deskripsi gambar di sini

Batang tengah adalah tinggi 1(saya tidak menemukan sudut yang bagus di mana batang itu juga terlihat). Sekarang kolom di atas batang itu bisa menampung 2 cm air, sebelum itu akan meluap di atas 3batang di sebelah kanan. Karena tidak ada batang lain yang dapat menahan air di atasnya, jawabannya adalah 2. Berikut adalah dua contoh yang lebih kompleks:

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

Keluaran

Program Anda harus menghasilkan bilangan bulat tunggal yang memberikan volume air dalam sentimeter kubik.

Skor

Skor Anda adalah jumlah byte dari kode sumber Anda. Kemenangan terendah.

Celah standar dilarang seperti biasa.

Teka-teki ini terinspirasi oleh Pertanyaan SPOJ .

Ksatria Logika
sumber
4
Saya mengalami kesulitan memvisualisasikan ini dua kali pertama saya membacanya, jadi saya mengambil kebebasan menambahkan diagram dan sedikit lebih banyak penjelasan untuk contoh pertama. Semoga kamu tidak keberatan.
Martin Ender
Ini sangat mirip dengan tantangan lain yang melibatkan pengisian bentuk dengan air.
FUZxxl
2
@ FuZxxl kita punya tantangan lain seperti itu?
Pengoptimal
1
@ FUZxxl Saya hanya mengingat tantangan ini , yang sangat berbeda.
Martin Ender
@Optimizer Yang ini agak mirip.
Zgarb

Jawaban:

4

Python 2, 222 byte

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

Membaca input melalui STDIN dan menulis hasilnya ke STDOUT.

Penjelasan

Kami mulai dari nol dan secara bertahap meningkatkan ketinggian air sebagai berikut: Misalkan ketinggian air h , dan kami ingin menambahkan 1 sentimeter air. Kami akan menyebut segi enam ketinggian h atau kurang, yang akan (atau sudah) ada di bawah air, " terendam ." Air akan tumpah melalui setiap segi enam terendam yang tidak dikelilingi oleh enam tetangga. Kami menghilangkan semua segi enam seperti itu; tentu saja, sekarang beberapa segi enam yang terendam mungkin memiliki kurang dari enam tetangga, dan mereka perlu dihilangkan juga. Kami melanjutkan cara ini sampai konvergensi, yaitu, sampai semua segi enam yang tersisa memiliki tepat enam tetangga. Pada titik ini kami menambahkan jumlah segi enam yang terendam (volume air yang diperoleh) ke jumlah total, dan meningkatkan level air.

Akhirnya, semua segi enam akan dihilangkan dan kami berhenti.

Elo
sumber
Anda harus dapat mencukur karakter dengan menggunakan -3<c-b<3 alih-alih 3>abs(c-b).
DLosc
@Doscosc Ah, tapi mereka bilangan kompleks;)
Ell
Menarik. Tidak menangkap itu.
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 :+}

Penjelasan singkat tentang algoritma:

  • mem-parsing input, dan untuk setiap batang menyimpan array dua elemen dari bentuk [rod_height, water_height]
  • batang ditempatkan dalam hash dan diindeks oleh koordinat x, y
  • bagian yang bocor air memperhitungkan ketinggian batang / air tetangga terdekat

Versi yang sedikit lebih mudah dibaca tersedia di sini: http://ideone.com/cWkamV

Jalankan versi golf secara online dengan tes: http://ideone.com/3SFjPN

Cristian Lupascu
sumber
scanmengambil argumen blokir. Anda hanya dapat melakukan scan(/../){...}. Bukan 'scan (/../) map {| v | ...} . (You don't need the | v | `karena Di dalam scanblok Anda bisa $&, $1, dll)
Jordan
@ Jordan Pengamatan hebat! Terima kasih!
Cristian Lupascu