Pengecualian Manhattan Kasus Terburuk

20

Bayangkan sebuah kotak W oleh H kotak yang membungkus toroidally. Item ditempatkan ke kisi sebagai berikut.

Item pertama dapat ditempatkan pada kotak apa saja, tetapi item berikutnya tidak boleh berada dalam jarak Manhattan R dari item sebelumnya (juga dikenal sebagai lingkungan Von Neumann dari rentang R ). Dengan hati-hati memilih posisi memungkinkan pas sejumlah besar item ke grid sebelum tidak ada lagi posisi yang valid. Namun, pertimbangkan tujuan sebaliknya: Berapakah jumlah item terendah yang dapat ditempatkan dan tidak meninggalkan posisi yang valid lebih lanjut?

Berikut adalah zona pengecualian radius 5:

Radius 5 zona pengecualian

Berikut ini adalah zona pengecualian radius 5 lainnya, kali ini di dekat tepi sehingga perilaku pembungkus terlihat:

Membungkus radius 5 zona pengecualian

Memasukkan

Tiga bilangan bulat:

  • W : lebar kotak (bilangan bulat positif)
  • H : tinggi kotak (bilangan bulat positif)
  • R : radius zona pengecualian (bilangan bulat non-negatif)

Keluaran

Bilangan bulat N , yang merupakan jumlah item terkecil yang dapat ditempatkan mencegah penempatan lebih lanjut yang valid.

Detail

  • Jari-jari nol memberikan zona eksklusi 1 kuadrat (yang ditempatkan pada item).
  • Jari-jari N tidak termasuk zona yang dapat dicapai dalam langkah-langkah ortogonal N (ingat tepi membungkus toroidally).

Kode Anda harus berfungsi untuk kasus sepele dari R = 0, tetapi tidak perlu bekerja untuk W = 0 atau H = 0.

Kode Anda juga harus berurusan dengan kasus di mana R > W atau R > H .

Batas waktu dan uji kasus

Kode Anda harus dapat menangani semua kasus uji, dan setiap kasus uji harus selesai dalam 5 menit. Ini harus mudah (contoh, solusi JavaScript membutuhkan beberapa detik untuk setiap kasus uji). Batas waktu terutama untuk mengecualikan pendekatan brute force yang ekstrim. Contoh pendekatannya masih cukup brute force.

Jika kode Anda selesai dalam waktu 5 menit pada satu mesin tetapi tidak pada yang lain yang akan cukup dekat.

Uji kasus dalam bentuk input: keluaran sebagaiW H R : N

5 4 4 : 1
5 4 3 : 2
5 4 2 : 2
5 4 1 : 5

7 5 5 : 1
7 5 4 : 2
7 5 3 : 2
7 5 2 : 4

8 8 8 : 1
8 8 7 : 2
8 8 6 : 2
8 8 5 : 2
8 8 4 : 2
8 8 3 : 4

 7  6  4 : 2
 7  6  2 : 4
11  7  4 : 3
11  9  4 : 4
13 13  6 : 3
11 11  5 : 3
15 14  7 : 2
16 16  8 : 2

Cuplikan untuk membantu memvisualisasikan dan bermain-main dengan ide

Tampilkan cuplikan kode

Contoh solusi (ungolfed)

Hanya contoh untuk output kecil (dihasilkan dari jari-jari tidak jauh lebih kecil dari lebar dan tinggi). Dapat menangani salah satu kasus uji tetapi akan kehabisan waktu dan menyerah untuk sebagian besar kasus yang lebih besar.

Tampilkan cuplikan kode

code-golf geometry grid packing trichoplax
sumber
4
Cuplikan kode luar biasa!
Stretch Maniac
@StretchManiac terima kasih :) Saya mencoba belajar JavaScript sehingga umpan balik diterima
trichoplax
1
Itu potongan yang cukup bagus. Saya suka skema warna itu juga. Apakah itu dari palet?
miles
@miles terima kasih - warnanya hanya ditebak dan kemudian ditala sedikit (tapi tidak banyak - semuanya masih 3 kode warna karakter daripada 6). Anda dapat melihat warna yang digunakan di blok ketiga baris dalam kode snippet.
trichoplax

Jawaban:

5

Python 2, 216 182 byte

def f(W,H,R):L={(i%W,i/W)for i in range(W*H)};M={(x,y)for x,y in L if min(x,W-x)+min(y,H-y)>R};g=lambda s:min([1+g(s-{((a+x)%W,(b+y)%H)for x,y in L-M})for a,b in s]or[1]);return g(M)

Masukan seperti f(16,16,8). Menggunakan hampir sama algoritma dengan sampel @ trichoplax , tetapi dengan set. Awalnya saya tidak menempatkan item pertama (0, 0), tetapi ini membuatnya tersedak pada beberapa kasus terakhir.

Semua case di atas selesai dalam 10 detik, jauh di bawah batas. Faktanya, kasingnya cukup kecil sehingga saya mempunyai sedikit ruang agar kurang efisien, memungkinkan saya untuk menghapus cek yang memeriksa keadaan duplikat.

(Terima kasih kepada @trichoplax untuk bantuan bermain golf)

Diperluas:

def f(W,H,R):
  # All cells
  L={(i%W,i/W)for i in range(W*H)}                 

  # Mask: Complement of exclusion zone around (0, 0) 
  M={(x,y)for x,y in L if min(x,W-x)+min(y,H-y)>R}

  # Place recursively
  g=lambda s:min([1+g(s-{((a+x)%W,(b+y)%H)for x,y in L-M})for a,b in s]or[1])
  return g(M)
Sp3000
sumber
2

Python 3, 270 262 260 251 246 226

(Terima kasih kepada Sp3000 untuk:

  • -~ alih-alih +1 , yang membuat saya kehilangan tempat setelah return di baris terakhir.
  • kehilangan tanda kurung berlebihan di sekitar W*H .
  • lambda ...
  • menempatkan semuanya pada satu baris.
  • python modulo %memberikan hasil positif untuk angka negatif, untuk menghemat 20 byte lainnya)

Ini adalah jawaban contoh JavaScript dari pertanyaan yang diangkut ke Python 3.

Untuk menghindari keharusan melewati begitu banyak argumen fungsi di sekitar, saya telah memindahkan dua fungsi pendukung di dalam fungsi kalkulasi sehingga mereka berbagi ruang lingkupnya. Saya juga menyingkat masing-masing fungsi ini menjadi satu baris untuk menghindari biaya indentasi.

Penjelasan

Pendekatan kekuatan yang cukup kasar ini menempatkan item pertama di (0, 0), dan kemudian menandai semua kotak yang dikecualikan. Itu kemudian secara rekursif menempatkan item di semua kotak yang tersisa sampai semua kotak dikeluarkan, dan mengembalikan jumlah item minimum yang diperlukan.

Kode golf:

def C(W,H,R):r=range;M=lambda g:min([M(G(g,x,y))for x in r(W)for y in r(H)if g[x+W*y]]or[-1])+1;G=lambda g,x,y:[g[a+W*b]if min((x-a)%W,(a-x)%W)+min((y-b)%H,(b-y)%H)>R else 0for b in r(H)for a in r(W)];return-~M(G([1]*W*H,0,0))

Kode tidak dikunci:

def calculate(W, H, R):
    starting_min = W * H + 1
    cells = [0] * (W * H)
    grid_state = grid_with_item_added(cells, 0, 0, W, H, R)
    return min_from_here(grid_state, starting_min, W, H, R) + 1

def min_from_here(grid_state, starting_min, W, H, R):
    no_cells = True
    min = starting_min
    for x in range(W):
        for y in range(H):
            if grid_state[x + W * y] == 0:
                no_cells = False
                new_grid_state = grid_with_item_added(grid_state, x, y, W, H, R)
                m = min_from_here(new_grid_state, starting_min, W, H, R)
                if m < min:
                    min = m

    if no_cells:
        return 0
    else:
        return min + 1

def grid_with_item_added(grid_state, x, y, W, H, R):
    grid = grid_state[:]
    for a in range(W):
        for b in range(H):
            if manhattan_distance(a, b, x, y, W, H) <= R:
                grid[a + W * b] = 1

    return grid

def manhattan_distance(a, b, c, d, W, H):
    horizontal = min(abs(W + c - a) % W, abs(W + a - c) % W)
    vertical = min(abs(H + d - b) % H, abs(H + b - d) % H)
    return horizontal + vertical


if __name__ == '__main__':
    import sys
    arguments = sys.argv[1:]
    if len(arguments) < 3:
        print('3 arguments required: width, height and radius')
    else:
        print(calculate(int(arguments[0]), int(arguments[1]), int(arguments[2])))

Kode ungolfed mendefinisikan fungsi dan juga menyertakan kode untuk memungkinkannya dipanggil dari baris perintah. Kode golf hanya mendefinisikan fungsi, yang cukup untuk pertanyaan golf kode standar .

Jika Anda ingin menguji kode golf dari baris perintah, ini dia termasuk penanganan baris perintah (tetapi tidak golf):

Baris perintah kode golf dapat diuji

def C(W,H,R):r=range;M=lambda g:min([M(G(g,x,y))for x in r(W)for y in r(H)if g[x+W*y]]or[-1])+1;G=lambda g,x,y:[g[a+W*b]if min((x-a)%W,(a-x)%W)+min((y-b)%H,(b-y)%H)>R else 0for b in r(H)for a in r(W)];return-~M(G([1]*W*H,0,0))

if __name__ == '__main__':
    import sys
    arguments = sys.argv[1:]
    if len(arguments) < 3:
        print('3 arguments required: width, height and radius')
    else:
        print(C(int(arguments[0]), int(arguments[1]), int(arguments[2])))
trichoplax
sumber