Masz tablicę wejściową o rozmiarze m * n. Każda komórka w tablicy jest wypełniona P lub T. Jedyna operacja, którą możesz wykonać na tablicy, to odwrócenie kolumn. Po odwróceniu kolumny litery we wszystkich komórkach tej kolumny przełączają się (P staje się T i viceversa). Jeśli masz liczbę „x” wierszy z tą samą literą (np. PPPP), otrzymasz punkt. Zaprojektuj algorytm, który pobiera tablicę i zwraca rozwiązanie (które kolumny przerzucić), tak aby powstała tablica miała maksymalną możliwą liczbę punktów.

Uwaga: Jeśli istnieje wiele rozwiązań, które dają najwyższy wynik, wybierz to, które ma najmniejszą liczbę przerzutów. Przykład:

Tablica wejściowa:

PPTPP
PPTPP
PPTTP
PPPTT
PPPTT

Wynik:

3

Objaśnienie:
Rozwiązanie, które daje najwyższe punkty: Odwróć kolumnę nr. 3
Zatem oryginalna tablica wyglądałaby następująco:

PPPPP // 1 point
PPPPP // 1 point
PPPTP
PPTTT
PPTTT

//Total: 2 points

Zauważ, że można również przerzucić kolumny 4 i 5, aby uzyskać wynik dwa, ale to wymaga dodatkowego przewrócenia.

Możesz użyć dowolnego dogodnego formatu wejściowego do przedstawienia dwuwymiarowej tablicy, a także dowolnych dwóch różnych, ale ustalonych wartości do reprezentowania Pi T.

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

APL, 37

{x/1+⍳⍴x←y[↑⍋(+/∘.≠⍨2⊥⍉y),¨+/y←⍵⍪~⍵]}

Przykład:

{x/1+⍳⍴x←y[↑⍋(+/∘.≠⍨2⊥⍉y),¨+/y←⍵⍪~⍵]} 5 5⍴0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1

Testowane tutaj.

Pyth , 28

f@eo+/QN/Qm!dN_osZ^U2lhQTUhQ

Pobiera dane wejściowe w postaci zagnieżdżonej listy, np

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

Daje wynik indeksowany 0, np

[2]

^U2lhQ: Generuje wszystkie możliwe listy zer i 1 o odpowiedniej długości.

_osZ: Porządkuje te listy od większości 1 do najmniej.

+/QN/Qm!dN: Zlicza, ile razy każda lista ( N) i jej odwrotność, zamienione zera i 1s m!dNwystępują na wejściu. Pierwszy odpowiada serii odwrotów, pozostawiając wszystkie zera, drugi - pozostawieniu wszystkich zer.

eo: Porządkuje listę według powyższego klucza i pobiera jej ostatni element, który będzie wynikiem dla najbardziej pasujących kolumn, a wśród nich najmniejszą.

f@ ... TUhQ: Konwertuje tę listę jedynek i zer na listę indeksów, które mają być odwrócone.

W przypadku indeksowania 1 zmień na da k, a następnie umieść mhdna początku.

CJam, 53 51 bajtów

l~z:X,,La\{1$f++}/{,}${X\{_X=:!t}/z{_&,(},,}$0=:)S*

Odczytuje dwuwymiarową tablicę zer i jedynek z STDIN. Np. Przykładem w pytaniu byłoby

[[0 0 1 0 0] [0 0 1 0 0] [0 0 1 1 0] [0 0 0 1 1] [0 0 0 1 1]]

Sprawdź to tutaj.

Najpierw pobiera się wszystkie możliwe podzbiory kolumn, w kolejności rosnącej długości, a następnie wykonuje odwracanie dla każdego podzbioru i sortuje je według liczby wierszy, w których nadal są zarówno 0, jak i 1. Wreszcie zwracamy pierwszy taki podzbiór. Polega to na stabilnym sortowaniu, tak że początkowa kolejność zwiększania długości zajmuje się przerywnikiem.

Haskell, 98

g s=snd$maximum[((sum[1|o<-s,o==r||o==map(1-)r],-sum r),[i|(i,1)<-zip[1..]r])|r<-s++map(map(1-))s]

format wejściowy to lista list int. możesz użyć wersji łańcuchowej do testowania:

gg = g . map (map (\c -> case c of 'T' -> 0 ; _ -> 1) ) . lines

_{o nie, przestrzenie! to boli!}

działa to poprzez iterację po wierszach i obliczanie liczby punktów, które uzyskamy, jeśli odwrócimy kolumny w taki sposób, że ten wiersz zdobędzie punkt.

pierwszą rzeczą, na którą należy zwrócić uwagę, jest to, że odwrócenie wiersza do wszystkich Truelub wszystkich Falsenie ma znaczenia, ponieważ siatki będą dokładnie odwrotne względem siebie, a zatem będą miały dokładnie taki sam wynik.

sposób, w jaki obliczamy liczbę, gdy dany rząd otrzymuje punkt, jest taki: powtarzamy ponownie rzędy i sumujemy punkty, które daje nam każdy rząd, wykorzystując fakt, że robią to dokładnie wtedy, gdy wiersze są identyczne lub dokładnie odwrotne.

na przykład, jeśli wiersz, który przerzucamy, jest, TPPTPa bieżący wiersz, nad którym iterujemy, jest PTTPTlub TPPTPwtedy rząd zyskuje punkt, ale gdy jest to inny rząd, nie daje nam żadnych punktów.

CJam, 37 lat

q~_{:!}%+:T{T1$a-,\0-+}$0={U):U*}%0-`

Format wejściowy:

[[0 0 1 0 0] [0 0 1 0 0] [0 0 1 1 0] [0 0 0 1 1] [0 0 0 1 1]]

Mathematica - 76

{
{P, P, T, P, P},
{P, P, T, P, P},
{P, P, T, T, P},
{P, P, P, T, T},
{P, P, P, T, T}
}/.{P -> 1, T -> 0};
First@MaximalBy[
  Subsets@Range@Length[%],
  MapAt[1-#&,%,{All,#}]~Count~{1..}&
]

Python 2, 234

from itertools import *
A=input()
n=len(A[0])
R=range(n)
S=(0,)
for p in[q for i in R[:-1] for q in combinations(R,i)]:
    s=[sum([(l[q]+(q in p))%2 for q in R])for l in A]
    m=s.count(n)+s.count(0)
    if m>S[0]:S=(m,p)
print S[1]

Dane wejściowe to lista list:

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

Dane wyjściowe to krotek flipów przy użyciu indeksowania python od 0:

(2,)

Jeśli dane wyjściowe muszą być indeksowane od 1, wówczas kod ma 272 znaki, przy czym 0 oznacza brak przewrotów:

print 0 if len(S[1])==0 else [p+1 for p in S[1]]