Tiene una matriz de entrada de tamaño m * n. Cada celda de la matriz se llena con P o T. La única operación que puede hacer en la matriz es voltear columnas. Cuando voltea una columna, las letras en todas las celdas de esa columna cambian (P se convierte en T y viceversa). Si tiene 'x' número de filas con la misma letra (por ejemplo, PPPP), obtendrá un punto. Diseñe un algoritmo que tome la matriz y devuelva una solución (qué columnas voltear) de modo que la matriz resultante tenga el máximo número de puntos posibles.

Nota: En caso de que haya múltiples soluciones que produzcan la puntuación más alta, elija la que tenga el menor número de vueltas. Ejemplo:

Matriz de entrada:

PPTPP
PPTPP
PPTTP
PPPTT
PPPTT

Salida:

3

Explicación:
Una solución que produce los puntos más altos: Voltear la columna no. 3
Entonces la matriz original sería:

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

//Total: 2 points

Tenga en cuenta que también se pueden voltear las columnas 4 y 5 para obtener una puntuación de dos, pero eso necesita un giro adicional.

Puede utilizar cualquier formato de entrada conveniente para representar la matriz bidimensional, y también puede representar dos valores distintos, pero fijos, para representar Py T.

Este es el código de golf, por lo que gana la respuesta más corta (en bytes).

APL, 37

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

Ejemplo:

{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

Probado aquí.

Pyth , 28

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

Toma datos en forma de una lista anidada, por ejemplo

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

Da salida indexada 0, por ejemplo

[2]

^U2lhQ: Genera todas las listas posibles de 0 y 1 de la longitud correcta.

_osZ: Ordena estas listas de la mayoría de los 1s a los menos.

+/QN/Qm!dN: Cuenta cuántas veces cada lista ( N) y su inverso, 0s y 1s intercambiados ( m!dN) ocurren en la entrada. El primero corresponde a una serie de volteos dejando todos los ceros, el último a dejar todos los ceros.

eo: Ordena la lista por la tecla anterior y toma su último elemento, que será el resultado con las columnas más coincidentes, y entre ellas la que tenga menos.

f@ ... TUhQ: Convierte esta lista de 1s y 0s en una lista de índices para voltear.

Para la indexación 1, cambie el da a k, luego coloque mhdal principio.

CJam, 53 51 bytes

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

Esto lee una matriz bidimensional de 0s y 1s de STDIN. Por ejemplo, el ejemplo en la pregunta sería

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

Pruébalo aquí.

Este primero obtiene todos los subconjuntos posibles de columnas, en orden de longitud creciente, luego realiza los volteos para cada subconjunto y los ordena por la cantidad de filas que aún tienen 0s y 1s en ellos. Finalmente, solo devolvemos el primer subconjunto de este tipo. Esto depende de que la clasificación sea estable, de modo que el orden inicial de aumentar la longitud se encargue del desempate.

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]

El formato de entrada es una lista de la lista de entradas. puedes usar una versión de cadena para probar:

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

_{oh no los espacios! ¡duele!}

esto funciona iterando sobre las filas y calculando el número de puntos que obtendremos si volteamos las columnas de manera que esta fila nos gane un punto.

Lo primero que debe notar es que cambiar la fila a todo Trueo a todos Falseno importa, porque las cuadrículas serán exactamente inversas entre sí y, por lo tanto, tendrán exactamente el mismo puntaje.

la forma en que calculamos el recuento cuando una fila determinada gana un punto es así: iteramos sobre las filas nuevamente y sumamos los puntos que cada fila nos da, usando el hecho de que lo hacen exactamente cuando las filas son idénticas o exactamente al revés.

por ejemplo, si la fila que estamos volteando es TPPTPy la fila actual sobre la que estamos iterando es PTTPTo TPPTPentonces la fila nos gana un punto, pero cuando es cualquier otra fila, no nos gana ningún punto.

CJam, 37

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

Formato de entrada:

[[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..}&
]

Pitón 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]

La entrada es una lista de listas:

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

La salida es una tupla de volteos usando la indexación de Python desde 0:

(2,)

Si la salida debe indexarse ​​desde 1, entonces el código tiene 272 caracteres con 0 que indica que no hay volteos:

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