У вас есть входной массив размером m * n. Каждая ячейка в массиве заполняется либо P, либо T. Единственная операция, которую вы можете выполнить над массивом, - это перевернуть столбцы. Когда вы переворачиваете столбец, буквы во всех ячейках этого столбца переключаются (P становится T и наоборот). Если у вас есть «х» количество строк с одинаковыми буквами (например, PPPP), то вы получите точку. Разработайте алгоритм, который принимает массив и возвращает решение (какие столбцы нужно перевернуть) так, чтобы результирующий массив имел максимально возможное количество точек.

Примечание. Если существует несколько решений с наибольшим количеством баллов, выберите вариант с наименьшим количеством сальто. Пример:

Входной массив:

PPTPP
PPTPP
PPTTP
PPPTT
PPPTT

Выход:

3

Объяснение:
Решение, которое дает наивысшие баллы: Flip column no. 3
Тогда исходный массив будет:

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

//Total: 2 points

Обратите внимание, что можно также перевернуть столбцы 4 и 5, чтобы получить оценку два, но это требует дополнительного переворота.

Вы можете использовать любой удобный формат ввода для представления двумерного массива, а также любые два различных, но фиксированных значения для представления Pи T.

Это код гольф, поэтому самый короткий ответ (в байтах) выигрывает.

APL, 37

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

Пример:

{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

Проверено здесь.

Пиф , 28

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

Принимает ввод в виде вложенного списка, например

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

Дает вывод 0-indexed, например

[2]

^U2lhQ: Генерирует все возможные списки 0 и 1 правильной длины.

_osZ: Упорядочивает эти списки от 1 до 1.

+/QN/Qm!dN: Подсчитывает, сколько раз каждый вход ( N) и его обратные, 0 и 1 с заменены ( m!dN) встречаются на входе. Первое соответствует серии переворотов, оставляющих все нули, второе - всем.

eo: Упорядочивает список по указанному выше ключу и берет его последний элемент, который будет результатом с наиболее подходящими столбцами, и среди них - с наименьшим.

f@ ... TUhQ: Преобразует этот список из 1 и 0 в список индексов, которые необходимо перевернуть.

Для 1-индексации измените на da k, затем поставьте mhdв начале.

CJam, 53 51 байт

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

Это читает двумерный массив 0 и 1 из STDIN. Например, пример в вопросе будет

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

Проверьте это здесь.

Сначала он получает все возможные подмножества столбцов в порядке увеличения длины, затем выполняет перевороты для каждого подмножества и сортирует их по количеству строк, в которых по-прежнему есть как 0, так и 1. Наконец, мы просто возвращаем первое такое подмножество. Это зависит от стабильности сортировки, так что начальный порядок увеличения длины заботится о прерывателе связи.

Хаскелл, 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]

Формат ввода представляет собой список списка целых. Вы можете использовать строковую версию для тестирования:

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

_{о нет пробелов! это больно!}

это работает путем итерации по строкам и вычисления количества точек, которые мы получим, если мы перевернем столбцы таким образом, чтобы эта строка получила нам точку.

Первое, на что нужно обратить внимание, это то, что переключение строки на все Trueили на все Falseне имеет значения, потому что сетки будут точно противоположны друг другу и, следовательно, будут иметь одинаковую оценку.

способ, которым мы вычисляем количество, когда заданная строка получает точку, таков: мы снова итерируем по строкам и суммируем точки, которые дает каждая строка, используя тот факт, что они делают именно тогда, когда строки либо идентичны, либо точны обратные.

например, если строка, которую мы переворачиваем, TPPTPи текущая строка, по которой мы перебираем, равна PTTPTили TPPTPтогда строка получает нам точку, но когда это любая другая строка, она не получает нам никаких точек.

CJam, 37

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

Формат ввода:

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

Вход представляет собой список списков:

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

Вывод представляет собой кортеж с использованием индексации Python от 0:

(2,)

Если выходные данные должны быть проиндексированы с 1, то код состоит из 272 символов, причем 0 означает отсутствие переворотов:

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