# The idea of this project is that there will be an n by n matrix representing
# a grid. Then there will be g genders and k people of each gender
# placed more or less randomly around the grid.
# A space with a 0 (or a dot in the output representation) is empty.
# A space with an integer k (where 0 < k <= g) represents a person of gender k.
# In a parallel step, a client process sends a set of moves each consisting
# of a quadruple (i1, j1, i2, j2) where (i1, j1) is the original grid position 
# of a person and i2, j2 is the place where that person moves in the step.
# The rules about the moves are that a person may move only once in a step.
# The move must be one position vertically or horizontally but not both.
# No two people may end up in the same spot.
# If any of these rules are violated, the team loses.
# The game is complete when there are k disjoint line segments each 
# containing one person of every gender though the order of genders
# does not matter.

# Functions in this file:
# Function genmat generates the initial matrix 
# Function printmat prints out the matrix. 
# Function onestep takes a matrix and a set of moves and either determines that
# they are illegal or changes the matrix appropriately.
# Function alldone determines whether there are k line segments with all
# g genders. There could be more if they are lined up properly though this
# is hard to do if there are three or more genders.
# Function rightstep creates the moves to cause
# the non-zeroes in the matrix to move one position to
# the right (under certain conditions). It should go in the client 
# in the code we give to the students as a standin function for what they
# should change.

# In the competition, all teams will get the same initial matrix
# and each team will communicate moves using zeromq until that team make an
# illegal move (in which case they lose) or that team completes. 

import random
import copy


# generate a square matrix of size n
# having g kinds of genders
# and k of each gender
# We want k*g << n*n
# In the output, 0 represents space and the genders are number 1 through g
# inclusive
def genmat(n,g,k):
  i = 0
  mat = []
  for i in range(n):
    x = [0 for j in range(n)]
    mat.append(x)
  tot = k * g
  i = 0
  gender = 1
  while (i < tot):
    mypair = findpair(mat)
    mat[mypair[0]][mypair[1]] = gender
    if (gender == g):
      gender = 1
    else: 
      gender+= 1
    i+=1
  return mat

# Randomly choose a random place that is still 0
def findpair(mat):
  while True:
    i = random.randint(0,len(mat)-1)
    j = random.randint(0,len(mat)-1)
    if (mat[i][j] == 0):
      return([i,j])
    


# Output a matrix as a set of strings
def printmat(mat):
  for line in mat:
    s = ""
    for num in line:
      if num == 0:
        s+="."
      else:
        s+=str(num)
    print(s)

# mat is the current matrix
# moves is a set of moves.
# Each move is a quadruple that moves a non-zero to
# a neighbor. If a move doesn't go to a neighbor or 
# if two moves end up in the same square,
# that will be an automatic loss.
def onestep(mat, moves):
  outmat = copy.deepcopy(mat)
  destcoords = []
  for move in moves:
    totdist = abs(move[0] - move[2]) + abs(move[1]-move[3])
    if totdist == 1:
      destcoords.append(str(move[2]) + "_" + str(move[3]))
      outmat[move[2]][move[3]] = mat[move[0]][move[1]]
      if (str(move[0]) + "_" + str(move[1])) not in destcoords:
        outmat[move[0]][move[1]] = 0
    else:
      print("Bad move from [" + str(move[0]) + "," + str(move[1]) + "] to [" + str(move[2]) + "," + str(move[3]) + "]")
      return([False, []])
  seen = set()
  for mystring in destcoords:
    if mystring not in seen:
      seen.add(mystring)
    else:
      print("This destination location is a duplicate: " + mystring) 
      return([False, []])
  return([True, outmat])


# See whether a matrix has k line segments of g genders,
# either vertical or horizontal.
# Return True if successful and False otherwise.
def alldone(mat,g,k):
  segmentcount = 0
  for line in mat:
    genders_collected =set()
    for n in line:
      if  n > 0:
        genders_collected.add(n)
        if len(genders_collected) == g:
          segmentcount+=1
          genders_collected =set()
      else: # reset to empty
        genders_collected =set()
  numcols = len(mat)
  for i in range(numcols):
    line = [val[i] for val in mat]
    genders_collected =set()
    for n in line:
      if  n > 0:
        genders_collected.add(n)
        if len(genders_collected) == g:
          segmentcount+=1
          genders_collected =set()
      else: # reset to empty
        genders_collected =set()
  numcols = len(mat)
  print("segmentcount is ", str(segmentcount))
  return(segmentcount >= k)
    
  
# rightstep just moves elements right unless there is some danger
# of pushing off the right side.
# Outputs a set of quadruples representing starting and ending
# positions
# THIS IS A STAND-IN FUNCTION FOR WHAT THE STUDENTS WILL DO
def rightstep(mat):
  moves = []
  for i in range(len(mat) ):
    for j in range(len(mat[0]) - 1):
      # if (mat[i][j] > 0) and (mat[i][j+1] == 0):
      if (mat[i][j] > 0) and (mat[i][len(mat[0]) - 1] == 0):
        moves.append([i,j,i,j+1])
  return(moves)
      

# DATA

n = 8 # n by n matrix
g = 3 # number of genders
k = 3 # number of instances of each gender

# SAMPLE SINGLE PROCESS RUN

matout = genmat(n,g,k)
printmat(matout)
alldone(matout,g,k)

mymoves = rightstep(matout)
print("mymoves = ", mymoves)
pair = onestep(matout, mymoves)
if pair[0] == True:
  matout = copy.deepcopy(pair[1])
printmat(matout)
alldone(matout,g,k)