Tantangan ini didasarkan pada teka-teki berikut: Anda diberi noleh ngrid dengan nsel ditandai. Tugas Anda adalah mempartisi kisi-kisi menjadi nbagian - bagian di mana setiap bagian terdiri dari nsel-sel persis , masing-masing berisi persis satu sel yang ditandai.

Contoh

Berikut adalah teka-teki di sebelah kiri dan solusi (unik) di sebelah kanan:

Tantangan

Anda akan diberikan satu set nkoordinat tanpa indeks dalam format apa pun yang masuk akal.

[(0,0), (0,3), (1,0), (1,1), (2,2)]

Dan tugas Anda adalah menulis sebuah program yang mengembalikan setiap partisi yang valid (sekali lagi, dalam format apa pun yang masuk akal).

[
  [(0,0), (0,1), (0,2), (1,2), (1,3)],
  [(0,3), (0,4), (1,4), (2,4), (3,4)],
  [(1,0), (2,0), (3,0), (4,0), (4,1)],
  [(1,1), (2,1), (3,1), (3,2), (4,2)],
  [(2,2), (2,3), (3,3), (4,3), (4,4)]
]

Jika puzzle tidak memiliki solusi, program harus menunjukkan bahwa dengan melemparkan kesalahan atau mengembalikan solusi kosong.

Contoh Input / Output

[(0,0)]               => [[(0,0)]]

[(0,0), (1,1)]        => [
                          [(0,0), (1,0)], 
                          [(0,1), (1,1)]
                         ]

[(0,0), (0,1), (1,0)] => [] (no solution)

[(0,0), (0,1), (0,2)] => [
                          [(0,0), (1,0), (2,0)], 
                          [(0,1), (1,1), (2,1)],
                          [(0,2), (1,2), (2,2)],
                         ]

[(0,0), (0,2), (1,2)] => [
                          [(0,0), (1,0), (2,0)], 
                          [(0,1), (0,2), (1,1)],
                          [(1,2), (2,1), (2,2)],
                         ]

Mencetak gol

Ini kode-golf , jadi kode terpendek menang.

code-golf combinatorics grid set-partitions Peter Kagey
sumber

Ini terinspirasi oleh pertanyaan Math Stack Exchange ini .

Peter Kagey

@Arnauld, sepertinya untuk teka-teki Shikaku, "tujuannya adalah untuk membagi kotak menjadi potongan persegi dan persegi". Dalam hal ini, tidak ada kendala seperti itu.

Peter Kagey

Maaf bila membingungkan. Saya pikir mungkin ada tantangan Shikaku di suatu tempat di kotak pasir, atau mungkin saya berencana untuk membuat sendiri di beberapa titik - saya tidak ingat pasti. Either way, saya pikir itu adalah hal yang sama pada pandangan pertama.

Arnauld

Mengapa hasilnya berupa array koordinat 2d? Saya tidak mengerti apa yang diungkapkan di sana ... Tidak bisakah itu menjadi array 2d dari indeks array? Misalnya baris 3, kolom 2 berisi partisi dengan koordinat pada indeks 4?

Olivier Grégoire

Bolehkah kita mengasumsikan bahwa setiap area dapat digambar dengan mulai dari koordinat referensi, seperti contoh yang disarankan? Saya baru sadar bahwa saya secara tidak sadar menganggap ini sebagai hal yang wajar.

Arnauld

JavaScript (ES7), 166 byte

$false$

a=>(m=a.map(_=>[...a]),g=(n,X,Y,j=0,i)=>a[n]?a[j]?m.some((r,y)=>r.some((v,x)=>++v|(X-x)**2+(Y-y)**2-1?0:g(r[x]=n,x,y,j+1,i|x+[,y]==a[n])?1:r[x]=v)):i&&g(n+1):1)(0)&&m

Cobalah online!

Bagaimana?

$m$ $N\times N$ $N$

m = a.map(_ => [...a])

$m$ $N$ $m$ ++

$g$ $n$ $(X,Y)$ $j$ $i$

g = (n, X, Y, j = 0, i) => a[n] ? a[j] ? ... : i && g(n + 1) : 1

$a[n]$ $a[j]$ untuk mengetahui apakah sel-sel yang cukup telah diisi di daerah saat ini.

$g$ $m$

m.some((r, y) =>          // for each row r[] at position y in m[]:
  r.some((v, x) =>        //   for each cell of value v at position x in r[]:
    ++v |                 //     if this cell is already filled (i.e. v is numeric)
    (X - x) ** 2 +        //     or the squared Euclidean distance between
    (Y - y) ** 2 -        //     (X, Y) and (x, y)
    1 ?                   //     is not equal to 1:
      0                   //       this is an invalid target square: do nothing
    :                     //     else:
      g(                  //       do a recursive call to g:
        r[x] = n,         //         pass n unchanged and fill the cell with n
        x, y,             //         pass the coordinates of the current cell
        j + 1,            //         increment j
        i |               //         update i:
        x + [,y] == a[n]  //         set it if (x, y) = a[n]
      ) ?                 //       if the result of the call is truthy:
        1                 //         return 1
      :                   //       else:
        r[x] = v          //         reset the cell to NaN
  )                       //   end of inner map()
)                         // end of outer map()

Arnauld
sumber

Partisi kisi persegi menjadi bagian-bagian dengan luas yang sama