Menstabilkan Struktur Bata

Batasan Batu Bata dan Stabilitas

Pertanyaan ini menggunakan definisi bata dan stabilitas yang sama dengan Apakah struktur bata stabil?

Biarkan [__]mewakili batu bata dan

         .
         .
         .
  BRK?BRK?BRK?BRK?  
BRK?BRK?BRK?BRK?BRK?
  BRK?BRK?BRK?BRK?  
BRK?BRK?BRK?BRK?BRK? . . .
  BRK?BRK?BRK?BRK?  
BRK?BRK?BRK?BRK?BRK?

mewakili pengaturan atau struktur batu bata yang sewenang-wenang ini, dengan setiap baris lainnya diimbangi dengan setengah batu bata, seperti biasa dalam konstruksi batu bata. Struktur dapat meluas ke atas dan ke kanan tanpa batas, tetapi representasi string akan selalu menjadi blok teks persegi panjang sempurna (memiliki spasi tambahan jika diperlukan) yang lebarnya dapat dibagi 4.

Masing-masing BRK?dalam struktur dapat berupa bata ( [__]) atau ruang kosong (4 spasi).

Sebagai contoh, satu kemungkinan struktur (tidak stabil - baca terus) adalah

[__]    [__]    [__]
  [__]        [__]  
[__][__]    [__]

Stabilitas struktur itu penting, dan struktur itu hanya stabil jika setiap batunya stabil.

Ada tiga cara batu bata individu menjadi stabil:

Setiap bata di tanah (garis bata terendah) stabil.

Batu bata yang memiliki dua batu bata tepat di bawahnya stabil:

  [__]   <- this brick is stable
[__][__] <- because these bricks hold it up

Setiap bata yang memiliki bata di atas dan di bawahnya di sisi yang sama stabil:

  [__]  [__]
[__]      [__] <- these middle bricks are stable
  [__]  [__]      because the upper and lower bricks clamp them in

[__]          [__]
  [__]      [__]   <- these middle bricks are NOT stable
    [__]  [__]

(Ya, saya tahu aturan ini tidak akurat secara fisik.)

The Tantangan terakhir adalah tentang menentukan jika struktur stabil. Yang ini tentang menstabilkan yang tidak.

Tantangan

Tulis program yang menghasilkan susunan batu bata yang berpotensi tidak stabil dan tambahkan batu bata baru ke dalam ruang kosong untuk membuat semuanya stabil, mencetak hasilnya. Ini harus dilakukan tanpa meningkatkan dimensi keseluruhan blok teks input.

Tujuannya adalah untuk membuat algoritma yang membuat struktur stabil dengan menambahkan batu bata sesedikit mungkin.

JSFiddle ( sumber ) ini memungkinkan Anda menghasilkan pengaturan bata secara acak untuk digunakan saat menguji program Anda. (Berharap saya bisa menumpuk potongan sebagai gantinya.) WidthAdalah jumlah batu bata pada lapisan dasar, Heightadalah jumlah lapisan batu bata, dan Densitymerupakan fraksi ruang batu bata yang diisi.

Misalnya, dengan Width = 5, Height = 3, Density = 0.6output yang mungkin

....[__]....[__]....
..[__]....[__]......
[__]............[__]

Cara untuk menstabilkan ini dengan 4 batu bata baru adalah

....[__]....[__]....
..[__][__][__][__]..
[__][__]....[__][__]

Program Anda harus dapat menstabilkan struktur bata apa pun yang dapat dihasilkan JSFiddle.

Ini termasuk string kosong (yang dianggap stabil).
Batu bata akan selalu seperti itu [__]. Periode ( .) hanya digunakan untuk kejelasan. Program Anda dapat menggunakan titik atau spasi untuk ruang kosong.
Struktur mungkin sudah stabil, dalam hal ini tidak ada yang perlu dilakukan (selain mencetaknya).
JSFiddle selalu menghasilkan struktur yang dapat distabilkan (dengan menghindari Width = 1dan batu bata di sudut atas). Anda bisa mengandalkan ini. (Mengisi semua kecuali sudut atas pasti akan menstabilkan hal-hal tetapi ini jelas tidak optimal.)
Asumsikan tidak ada input yang tidak valid. Ambil input sebagai string sesuka Anda. Cetak struktur yang distabilkan ke stdout atau serupa.
Ingat bahwa dimensi blok teks tidak boleh mengubah ukuran.
Batu bata yang sudah ada sebelumnya tidak dapat dipindahkan atau dihapus. Penempatan batu bata baru harus mengikuti pola grid offset setiap baris lainnya. Semua batu bata harus sepenuhnya terikat.
Sebaiknya (tetapi tidak diharuskan) agar Anda mencetak batu bata yang sudah ada sebagai [XX]gantinya [__], sehingga orang dapat lebih melihat bagaimana solusi Anda bekerja.

Mencetak gol

Di bagian bawah JSFiddle ada 8 pengaturan bata yang tidak stabil yang telah ditentukan. (Mereka menggunakan [__]dan .dan harus tetap seperti itu kecuali jika Anda menggunakan [XX]dan / atau sebagai gantinya.) Beberapa acak dan beberapa saya buat sendiri. Untuk menghitung skor Anda, jalankan program Anda pada masing-masing secara bergantian dan jumlahkan jumlah batu bata baru yang ditambahkan ke masing-masing.

Semakin sedikit batu bata baru yang Anda tambahkan, semakin baik. Pengajuan dengan skor terendah akan menang. Dalam kasus ikatan, jawaban tertua menang.

Jika ada hal-hal yang diperdebatkan saya dapat menambahkan beberapa kasus yang telah ditentukan dan menilai pemenang berdasarkan pada mereka.

Catatan selanjutnya

Program Anda perlu dijalankan berdasarkan urutan menit pada komputer modern untuk lebar dan tinggi kisi bata kurang dari 100. (Maks 10 menit pada komputer seperti ini .)
Anda tidak boleh meng-hardcode output Anda untuk 8 struktur yang telah ditentukan. Program Anda harus memperlakukan mereka seperti halnya memperlakukan pengaturan lainnya.
Harap sertakan satu atau dua contoh output, atau struktur menarik yang ingin Anda bagikan. :)
Masalah ini agak terkait dengan menemukan pohon spanning minimum .

code-challenge ascii-art Hobi Calvin
sumber

Saya harus menunjukkan bahwa contoh "stabil" di bawah "Tantangan" sebenarnya tidak stabil berdasarkan kriteria yang dinyatakan.

COTO

@COTO Memang. Tetap.

Calvin Hobbies

dalam contoh Anda, bata bawah tengah tidak diperlukan untuk menstabilkan struktur.

John Dvorak

@JanDvorak: Ini menyatakan "cara" untuk menstabilkan, bukan "cara optimal", jadi secara teknis itu bukan kesalahan. Tetapi saya setuju bahwa mengeluarkan batu bata bagian bawah tengah dapat membantu membawa pulang kenyataan bahwa intuisi fisik bukan teman kita dalam masalah ini. ;)

COTO

@JanDvorak COTO benar, tidak masalah itu tidak optimal, tapi saya tetap mengubahnya.

Calvin Hobbies

Jawaban:

Jawa - 5.056 batu bata

20x20, 0,03 - 75
15x81, 0,05 - 431
50x50, 0,20 - 882
99x99, 0,01 - 2,567
Alas Polos - 269
Rumah Sederhana - 129
Menara Criss-Cross - 323
Jembatan Awal - 380

Kode sumber dapat dilihat di sini .

Kode ini berjalan dalam beberapa milidetik untuk salah satu dari 8 input penilaian. Ada beberapa output yang tampak suboptimal, terutama di menara silang dan kasus 99x99. Saya punya beberapa ide tentang cara meningkatkan rutinitas, tetapi ini cukup besar, dan karenanya saya akan membiarkannya sendiri untuk saat ini.

Keluarannya membantai hukum-hukum fisika hingga tingkat komedi. : D

Beberapa sampel ditunjukkan di bawah ini.

20x20, 0,03 Output

................................................................................
..........[XX]..................................................................
........[  ][  ]................................................................
..........[  ]..................................................................
............[  ]................................................................
..........[  ]..................................................................
............[  ]....................[XX]........................................
..........[  ]....................[  ][  ]......................................
....[XX]....[  ]....................[  ]........................................
..[  ][  ][  ][  ]................[  ]..........................................
....[XX]....[  ][XX]................[  ]........................................
..[  ]........[  ]................[XX]..........................................
....[  ]........[  ]............[  ][  ]........................................
..[  ]........[  ]................[  ]..........................................
....[  ]........[  ]............[XX]................................[XX]........
..[  ]........[  ]....[XX]........[  ]................[XX]........[  ][XX][  ]..
....[  ]........[  ][  ][  ]....[  ]....[XX]........[  ][  ]........[  ][  ][XX]
..[  ][  ]....[  ]....[  ]........[XX][  ][  ]........[  ]........[  ]....[  ]..
....[  ]........[  ]....[  ]....[  ]....[  ]............[  ]........[  ]....[  ]
......[XX]....[  ]....[  ]........[  ][  ]............[  ]........[  ]....[  ]..
....[  ]........[  ]....[  ]....[  ]....[  ]....[XX]....[  ]........[  ]....[  ]

Output Rumah Sederhana

................................................................................
................................................................................
................................................................................
......................................[XX]......................................
....................................[XX][XX]....................................
..................................[XX][  ][XX]..................................
................................[XX][  ][  ][XX]................................
..............................[XX][  ]....[  ][XX]..............................
............................[XX][  ]........[  ][XX]............................
..........................[XX][  ]............[  ][XX]..........................
........................[XX][  ]................[  ][XX]........................
......................[XX][  ]....................[  ][XX]......................
....................[XX][  ]........................[  ][XX]....................
..................[XX][  ]............................[  ][XX]..................
................[XX][  ]................................[  ][XX]................
..............[XX][  ]....................................[  ][XX]..............
............[XX][  ]........................................[  ][XX]............
..........[XX][  ]............................................[  ][XX]..........
........[XX][  ]................................................[  ][XX]........
......[XX][  ]................................................[  ][  ][XX]......
....[XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX]....
......[XX][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ][  ]....[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]........[XX]....
......[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]........[XX]....
......[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ]........[XX]....
......[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ][  ][  ]....[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ][  ][  ]........[XX]....
......[XX]....[XX][XX][XX][XX][  ]....[XX][XX][XX][XX][XX][XX]........[XX]......
....[XX]....[  ]....[  ]....[  ]....[  ]....[  ]....[  ][  ]............[XX]....
......[XX]....[XX]....[  ][XX]........[XX]....[  ]....[  ][XX]........[XX]......
....[XX]....[  ]....[  ][  ][  ]....[  ]....[  ]........[  ]............[XX]....
......[XX]....[XX]....[  ][XX]........[XX]....[  ]........[XX]........[XX]......
....[XX]....[  ]........[XX]........[  ]....[  ]........[  ]............[XX]....
......[XX]....[XX]........[XX]........[XX][XX][XX][XX][XX][XX]........[XX]......
....[XX]....[  ]........[  ]........[  ]....[  ][  ][  ][  ]............[XX]....
......[XX]....[XX]........[XX]........[  ]....[  ]....[  ]............[XX]......
....[XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX]....

COTO
sumber

Python, 18992

Ini adalah solusi paling sederhana dan skor terburuk yang mungkin. Ini hanya untuk referensi; hal untuk dikalahkan. Itu mengisi setiap ruang kosong kecuali dua sudut atas dengan batu bata, menjamin stabilitas.

s = '''
....[__]....[__]....
..[__]....[__]......
[__]............[__]
'''

def brickify(structure):
    structure = filter(lambda x: x, s.replace('__', 'XX').split('\n'))
    if not structure:
        return '', 0
    if len(structure) > 1 and len(structure) % 2:
        structure[0] = '----' + structure[0][4:-4] + '----'
    added = 0
    offset = False
    for i in range(len(structure)-1,-1,-1):
        line = structure[i]
        if offset:
            line = line[2:-2]
        added += line.count('....')
        line = line.replace('....', '[__]')
        if offset:
            line = '..' + line + '..'
        structure[i] = line
        offset = not offset
    structure[0] = structure[0].replace('----', '....')
    return structure, added

s, a = brickify(s)

#print '\nNew bricks:', a

for line in s:
    print line

Untuk menggunakan salin struktur awal ke dalam tanda kutip tiga di bagian atas program.

Ini dijalankan di rumah, menambahkan 609 batu bata:

..[__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__]..
[__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__]
..[__][__][__][__][__][__][__][__][__][XX][__][__][__][__][__][__][__][__][__]..
[__][__][__][__][__][__][__][__][__][XX][XX][__][__][__][__][__][__][__][__][__]
..[__][__][__][__][__][__][__][__][XX][__][XX][__][__][__][__][__][__][__][__]..
[__][__][__][__][__][__][__][__][XX][__][__][XX][__][__][__][__][__][__][__][__]
..[__][__][__][__][__][__][__][XX][__][__][__][XX][__][__][__][__][__][__][__]..
[__][__][__][__][__][__][__][XX][__][__][__][__][XX][__][__][__][__][__][__][__]
..[__][__][__][__][__][__][XX][__][__][__][__][__][XX][__][__][__][__][__][__]..
[__][__][__][__][__][__][XX][__][__][__][__][__][__][XX][__][__][__][__][__][__]
..[__][__][__][__][__][XX][__][__][__][__][__][__][__][XX][__][__][__][__][__]..
[__][__][__][__][__][XX][__][__][__][__][__][__][__][__][XX][__][__][__][__][__]
..[__][__][__][__][XX][__][__][__][__][__][__][__][__][__][XX][__][__][__][__]..
[__][__][__][__][XX][__][__][__][__][__][__][__][__][__][__][XX][__][__][__][__]
..[__][__][__][XX][__][__][__][__][__][__][__][__][__][__][__][XX][__][__][__]..
[__][__][__][XX][__][__][__][__][__][__][__][__][__][__][__][__][XX][__][__][__]
..[__][__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__][__]..
[__][__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][XX][XX][XX][__][__][XX][XX][XX][XX][XX][XX][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][__][__][XX][__][__][XX][__][__][__][__][XX][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][__][__][XX][__][__][XX][__][__][__][__][XX][__][__][XX][__]..
[__][XX][__][__][__][__][XX][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][__][__][XX][__][__][XX][XX][XX][XX][XX][XX][__][__][XX][__]..
[__][XX][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][__][XX][__]
..[__][XX][__][XX][__][__][XX][__][__][__][__][__][__][__][__][__][__][XX][__]..
[__][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][XX][__]

Jumlah batu bata yang ditambahkan untuk masing-masing dari 8 struktur yang telah ditentukan secara berurutan adalah

374 1107 2041 9627 506 609 1088 3640 (sum to 18992)

Hobi Calvin
sumber

Baris 20, bata 19 tidak memiliki braket kiri.

pegolf9338

@ pegolf9338 Terima kasih telah memperhatikan. Diperbaiki di pos dan jsfiddle.

Calvin Hobbies

Bukan untuk membuatnya terlalu pintar, tetapi apakah Anda perlu menambahkan batu bata ke baris atas?

Sparr

@Parr Tidak, kamu tidak. Tapi ini dimaksudkan untuk memberikan skor paling buruk hanya sebagai demonstrasi.

Calvin Hobbies