Weźmy pod uwagę macierze bloków binarnych po przekątnej, które mają kwadratowe bloki 1s na głównej przekątnej, i wszędzie są 0. Nazwijmy takie macierze „prawidłowymi” macierzami.

Na przykład, oto kilka prawidłowych macierzy 4x4:

1 0 0 0     1 1 0 0     1 0 0 0     1 0 0 0     1 1 0 0    1 1 1 1
0 1 0 0     1 1 0 0     0 1 1 0     0 1 1 1     1 1 0 0    1 1 1 1
0 0 1 0     0 0 1 0     0 1 1 0     0 1 1 1     0 0 1 1    1 1 1 1
0 0 0 1     0 0 0 1     0 0 0 1     0 1 1 1     0 0 1 1    1 1 1 1

Zauważ, że alternatywnym sposobem opisywania takich macierzy jest łańcuch kwadratowych bloków 1 od lewego górnego do prawego dolnego rogu, dotykających od rogu do rogu, a wszędzie indziej jest 0.

Dla kontrastu, oto niektóre nieprawidłowe matryce 4x4:

1 0 1 0     1 0 1 0     1 1 0 0     0 1 1 1     1 1 0 0    0 0 0 0
0 1 1 1     0 1 0 1     1 1 0 0     0 1 1 1     1 1 0 0    0 0 0 0
1 0 0 1     1 0 1 0     0 0 0 0     0 1 1 1     1 1 0 0    0 0 0 0
0 0 1 0     0 1 0 1     0 0 0 1     1 0 0 0     0 0 1 1    0 0 0 0

Będzie podawany był nprzez nbinarnej macierzy jako wejście - jaka jest minimalna liczba 0bitów trzeba do zestawu 1, aby uzyskać prawidłową matrycę?

Możesz napisać funkcję lub biorąc programu w dowolnym dogodnym strun listy lub macierzy formacie reprezentujący nprzez nmatrycę 0 i 1 (o ile nie jest ona wstępnie przetworzone). Wiersze muszą być w jakiś sposób wyraźnie oddzielone, więc formaty takie jak tablica 1D bitów nie są dozwolone.

To jest golf golfowy , więc celem jest zminimalizowanie liczby bajtów w twoim programie.

Przykłady

Na przykład, jeśli dane wejściowe to

0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1

odpowiedź brzmi 5, ponieważ można ustawić pięć 0bitów, 1aby uzyskać:

1 0 0 0 0
0 1 1 0 0
0 1 1 0 0
0 0 0 1 0
0 0 0 0 1

i jest to minimalna wymagana liczba. Jednak jeśli dane wejściowe były

0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

wtedy odpowiedź brzmi 24, ponieważ jedyną prawidłową macierzą 5x5, w której prawym górnym rogu jest 1macierz wszystkich 1s.

Przypadki testowe

Testy są tu reprezentowane jako tablica liczb całkowitych 2D.

[[0]] -> 1
[[1]] -> 0
[[0,1],[0,0]] -> 3
[[1,0],[0,0]] -> 1
[[0,0,0],[0,1,0],[0,0,0]] -> 2
[[0,1,0],[0,0,0],[0,1,0]] -> 7
[[0,1,0],[1,0,0],[0,0,1]] -> 2
[[1,1,1],[1,1,1],[1,1,1]] -> 0
[[0,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,0]] -> 4
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,0,1]] -> 8
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,0,1,0]] -> 14
[[0,0,1,0],[0,0,0,0],[0,0,0,0],[0,1,0,0]] -> 14
[[0,0,0,0,0],[0,0,0,0,0],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 7
[[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,0,0]] -> 11
[[0,0,0,0,0],[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1]] -> 5
[[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 24
[[0,0,0,1,0],[0,0,0,0,1],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]] -> 23
[[0,1,0,0,0],[1,0,0,0,0],[0,0,1,0,0],[0,0,0,0,1],[0,0,0,1,0]] -> 4
[[0,1,1,1,0],[0,1,1,0,1],[0,1,1,1,0],[0,1,0,0,1],[0,0,0,0,0]] -> 14

Notatki

• Powiązane wyzwanie: wydrukuj macierz blokową
• Inspiracja: Freedom Factory, Google Code Jam 2016 Problem 2D

MATL , 46 43 bajtów

nX^tQt:qZ^!tsb=Z)"@!"@1$l]@n$YdG-Q?6MG>zvX<

Dane wejściowe to tablica 2D z średnikiem jako separatorem wierszy. Na przykład dane wejściowe dla ostatniego przypadku testowego to

[0,1,1,1,0;0,1,1,0,1;0,1,1,1,0;0,1,0,0,1;0,0,0,0,0]

Wypróbuj online! Lub zweryfikuj wszystkie przypadki testowe (nieznacznie zmodyfikowano kod, aby uwzględnić wszystkie dane wejściowe; wyniki pojawiają się po kilku sekundach)

Wyjaśnienie

Niech wejście będzie macierzą N × N. Kod najpierw oblicza wszystkie ( N +1) wielkości bloków, które dają odpowiedni rozmiar matrycy. Na przykład, dla N = 4 krotki jest 0 0 0 0 4, 0 0 0 1 3, ..., 4 0 0 0 0. Dla każdej krotki buduje macierz blokowo-diagonalną o tych rozmiarach bloku. Następnie sprawdza, czy macierz obejmuje wszystkie 1wpisy na wejściu, a jeśli tak, bierze pod uwagę liczbę 1wpisów, które nie były obecne na wejściu. Ostateczny wynik to minimum wszystkich uzyskanych liczb.

nX^      % Implicit input  an N×N matrix. Get N
t        % Duplicate N
Qt:q     % Vector [0 1 ... N]
Z^       % Cartesian power. Gives 2D array
!ts      % Transpose, duplicate, sum of each column
b=       % Logical vector that equals true if the sum is N
Z)       % Filter columns according to that. Only keep columns that sum to N. Each 
         % column is the size of one block
"        % For each column
  @      %   Push that column
  "      %   For each entry of that column
    @    %     Push that entry
    1$l  %     Square matrix with that size, filled with 1
  ]      %   End
  @n     %   Column size. This is the number of blocks in the block-diagonal matrix
  $Yd    %   Build block-diagonal matrix from those blocks
  G-Q    %   Subtract input matrix element-wise, and add 1
  ?      %   If all entries are nonzero (this means each that entry that is 1 in the
         %   block-diagonal matrix is also 1 in the input matrix)
    6M   %   Push block-diagonal matrix again
    G>   %   For each entry, gives 1 if it exceeds the corresponding entry of the
         %   input, that is, if the block-diagonal matrix is 1 and the input is 0
    z    %   Number of 1 entries
    v    %   Concatenate vertically with previous values
    X<   %   Take minimum so far
         %   Implicit end
         % Implicit end
         % Implicit display

Python z numpy, 102

from numpy import*
lambda M:sum(diff([k for k in range(len(M)+1)if(M|M.T)[:k,k:].any()-1])**2)-M.sum()

Wydajny algorytm. Znajduje „punkty szyi” na przekątnej, które mogą rozdzielać bloki. Wszystkie mają zero powyżej i po prawej stronie, a także poniżej i po lewej stronie. Minimalne bloki to te między punktami szyi.

??000
??000
00???
00???
00???

Długość bloku jest różnicą między kolejnymi punktami szyjnymi, a więc ich całkowitą powierzchnią sumy kwadratów z nich. Odjęcie sumy oryginalnej macierzy daje liczbę potrzebnych przerzutów od 0 do 1.

Pyth, 45 bajtów

[email protected]^+LsYN2d+0._ds.pM./lQss

Trudne zadanie, więc jest dość długie.

Wypróbuj online: pakiet demonstracyjny lub testowy

Wyjaśnienie:

s.pM./lQoblicza wszystkie partycje całkowite z len(matrix). ms.b^+LsYN2d+0._dkonwertuje je na pary współrzędnych. Na przykład przegroda [1, 2, 2]od 5jest przekształcany [[0,0], [1,1], [1,2], [2,1], [2,2], [3,3], [3,4], [4,3], [4,4].

[email protected]następnie filtruje partycje, które całkowicie pokrywają się z macierzą ( .DRlQx1sQoblicza wszystkie pary współrzędnych aktywnych komórek w macierzy).

-hSlM...ss zlicza komórki każdej pozostałej partycji, wybiera tę z najmniejszą liczbą komórek i odejmuje już aktywne komórki.

Matryce , 180 bajtów (niekonkurencyjne)

Matricks to nowy esolang, który niedawno stworzyłem, aby radzić sobie z problemami matrycowymi (takimi jak ten), mając tylko 2 typy danych: zmiennoprzecinkowe i matematyczne. Nie jest jeszcze w pełni funkcjonalny i wciąż brakuje wielu operacji (musiałem dodać trochę funkcji do tego wyzwania). W każdym razie oto kod:

il=1:j3;:bdx;;;s1::L;j1;;
b{q:1;mgr:c;|gc:r;|(r=c)|(gr-1:c;|gr:c+1;)&(rec)|(gr+1:c;|gr:c-1;)&(cer):l:L;};z:(l-1)/2;B1;s1::g1:;-1;ig1:;=0:j2;:j1;;
s1::d{q:1;};;kg1:;-g:;;
kg:;*-1+1;

Wyjaśnienie

Pierwsza część il=1:j3;:...;sprawdza, czy tablica ma rozmiar 1. Jeśli tak, przeskakuje do ostatniej linii kg:;*-1+1;, która jest prostą 0 <-> 1funkcją.

W przeciwnym razie kontynuuje pracę z resztą kodu. bdx;;;ustawia komórkę 0,0na bieżącą sumę i s1::L;j1;tworzy licznik w komórce w wierszu poniżej.

Następny wiersz jest nieco bardziej skomplikowany. Jest to pętla, która działa nrazy, nbędąc wielkością matrycy. Wykorzystam trzeci przypadek testowy jako przykład. Kiedy po raz pierwszy przechodzimy do drugiej linii, macierz wygląda następująco:

1 0 1
2 0 0

Najpierw przechodzimy do zrozumienia macierzy {q:1;m...;}. To sprawia, że ​​przekątna, i stara się oczyścić 0, które wymagają wypełnienia. Wszystko to odbywa się za pomocą prostych operatorów boolowskich. Następnie dodajemy go do bieżącej macierzy, dając to:

    V--data we want to keep
1 1 1 0 1 <-|
1 1 2 0 0 <-- old matrix

Następnie wycinamy starą matrycę za pomocą z:(l-1)/2;i obracamy całą matrycę w lewo za pomocą B1;. To daje nam matrycę gotową do następnej iteracji, wyglądającą jak:

1 1 1
2 1 1

Na koniec zmniejszamy licznik, sprawdzamy i kontynuujemy ig1:;=0:j2;:j1;;

Gdy pętla zostanie przerwana, znajdujemy nową sumę i ustawiamy stare miejsce licznika s1::d{q:1;};;. Wreszcie bierzemy różnicę i wracamy kg1:;-g:;;. kustawia bieżącą tablicę na wartość i drukowanie jest niejawne.

...

Jak widać, Matricks jest dość gadatliwy i niezbyt dobrym językiem golfowym. Ale do diabła, chciałem się tym pochwalić.