#
# [798] Transform to Chessboard
#
# https://leetcode.com/problems/transform-to-chessboard/description/
#
# algorithms
# Hard (30.52%)
# Total Accepted:    338
# Total Submissions: 1.1K
# Testcase Example:  '[[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]'
#
# An N x N board contains only 0s and 1s. In each move, you can swap any 2 rows
# with each other, or any 2 columns with each other.
# 
# What is the minimum number of moves to transform the board into a
# "chessboard" - a board where no 0s and no 1s are 4-directionally adjacent? If
# the task is impossible, return -1.
# 
# 
# Examples:
# Input: board = [[0,1,1,0],[0,1,1,0],[1,0,0,1],[1,0,0,1]]
# Output: 2
# Explanation:
# One potential sequence of moves is shown below, from left to right:
# 
# 0110     1010     1010
# 0110 --> 1010 --> 0101
# 1001     0101     1010
# 1001     0101     0101
# 
# The first move swaps the first and second column.
# The second move swaps the second and third row.
# 
# 
# Input: board = [[0, 1], [1, 0]]
# Output: 0
# Explanation:
# Also note that the board with 0 in the top left corner,
# 01
# 10
# 
# is also a valid chessboard.
# 
# Input: board = [[1, 0], [1, 0]]
# Output: -1
# Explanation:
# No matter what sequence of moves you make, you cannot end with a valid
# chessboard.
# 
# 
# Note:
# 
# 
# board will have the same number of rows and columns, a number in the range
# [2, 30].
# board[i][j] will be only 0s or 1s.
# 
# 
#
import collections
class Solution(object):
    def movesToChessboard(self, board):
        N = len(board)
        ans = 0
        print (collections.Counter(map(tuple, board)))
        print (collections.Counter(zip(*board)))
        #print (*board)
        # For each count of lines from {rows, columns}...
        for count in (collections.Counter(map(tuple, board)),
                      collections.Counter(zip(*board))):
            #print (count)
            # If there are more than 2 kinds of lines,
            # or if the number of kinds is not appropriate ...
            if len(count) != 2 or sorted(count.values()) != [N//2, (N+1)//2]:
                return -1

            # If the lines are not opposite each other, impossible
            line1, line2 = count
            #print (line1, line2)
            # for x, y in zip(line1, line2):
            #     print (x,y,x^y)
            if not all(x ^ y for x, y in zip(line1, line2)):
                return -1

            # starts = what could be the starting value of line1
            # If N is odd, then we have to start with the more
            # frequent element
            starts = [+(line1.count(1) * 2 > N)] if N%2 else [0, 1]
            
            # To transform line1 into the ideal line [i%2 for i ...],
            # we take the number of differences and divide by two
            print (line1, starts)
            ans += min(sum((i-x) % 2 for i, x in enumerate(line1, start))
                       for start in starts) // 2
            #print (ans)

        return ans
