Podziel kwadratową siatkę na części o równej powierzchni

17

To wyzwanie jest oparta na następującej układanki: Jesteś podawany był nprzez nsiatki z nkomórek oznaczonych. Twoim zadaniem jest podzielenie siatki na nczęści, z których każda składa się z dokładnie nkomórek, z których każda zawiera dokładnie jedną zaznaczoną komórkę.

Przykład

Oto łamigłówka po lewej stronie i jej (unikalne) rozwiązanie po prawej:

puzzle rozwiązanie

Wyzwanie

Otrzymasz zestaw nwspółrzędnych zerowanych w dowolnym rozsądnym formacie.

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

Twoim zadaniem jest napisanie programu, który zwraca dowolną prawidłową partycję (ponownie, w dowolnym rozsądnym formacie).

[
  [(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)]
]

Jeśli układanka nie ma rozwiązania, program powinien to zaznaczyć, zgłaszając błąd lub zwracając puste rozwiązanie.

Przykłady wejścia / wyjścia

[(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)],
                         ]

Punktacja

To jest , więc wygrywa najkrótszy kod.

Peter Kagey
źródło
Inspiracją było pytanie Math Stack Exchange .
Peter Kagey
@Arnauld, wygląda na to, że dla puzzli Shikaku „celem jest podzielenie siatki na prostokątne i kwadratowe elementy”. W takim przypadku nie ma takiego ograniczenia.
Peter Kagey
Przepraszam za zamieszanie. Wydaje mi się, że gdzieś w piaskownicy może być wyzwanie Shikaku, a może sam planowałem w pewnym momencie - nie pamiętam na pewno. Tak czy inaczej, na pierwszy rzut oka myślałem, że to samo.
Arnauld
Dlaczego wynikiem jest tablica 2d współrzędnych? Nie rozumiem, co tam jest wyrażane ... Czy to nie może być tablica 2D indeksu tablicy? Na przykład wiersz 3, kolumna 2 zawiera partycję ze współrzędnymi o indeksie 4?
Olivier Grégoire
Czy możemy założyć, że każdy obszar można narysować, zaczynając od współrzędnych odniesienia, jak sugeruje przykład? Właśnie zdałem sobie sprawę, że nieświadomie wziąłem to za pewnik.
Arnauld

Odpowiedzi:

11

JavaScript (ES7), 166 bajtów

fazalsmi

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

Wypróbuj online!

W jaki sposób?

mN.×N.N.

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

mN.m++

soln(X,Y)jotja

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

za[n]za[jot]

solm

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
źródło