#!/usr/bin/python
# module puzzles

# Copyright (c) 2021 David Jimenez.
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
#   - Redistributions of source code must retain the above copyright notice,
#     this list of conditions and the following disclaimer.
#   - Redistributions in binary form must reproduce the above copyright notice,
#     this list of conditions and the following disclaimer in the documentation
#     and/or other materials provided with the distribution.
#   - Neither the name of the <organization> nor the names of its contributors
#     may be used to endorse or promote products derived from this software
#     without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL DAVID JIMENEZ BE LIABLE FOR ANY DIRECT,
# INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
# OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
# NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
# EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

# This file contains methods and classes that are not necessarily related to a
# specific puzzle, and could potentially be used in several of them.

###########
# IMPORTS #
###########
import numpy as np
import random
import time
import statistics


###################
###################
###################
###             ###
###             ###
###   METHODS   ###
###             ###
###             ###
###################
###################
###################

def baseLatinSquare(n):
    # This function takes an integer n and returns a NumPy two dimensional
    # matrix containing a very basic latin square.
    #
    # INPUT:
    #  - n: integer, size of the Latin Square to be generated.
    #
    # OUTPUT:
    #  - latinSquare: A nxn NumPy matrix of integers containing the Latin Square
    #                 generated by the function.
    #
    latinSquare = np.zeros((n,n),dtype = int)
    for i in range(n):
        for j in range(n):
            latinSquare[i,j] = (i+j)%n + 1
    return latinSquare


def randomLatinSquare(n):
    # This is a naive approach to generating random Latin Squares of a given
    # size. It is NOT based on the Jacobson and Matthews method. The approach
    # is to generate permutations of the numbers from 1 to n, in such a way that
    # the k-th element of the permuted row has not been used before.
    #
    # INPUT:
    #  - n: integer, size of the Latin Square to be generated.
    #
    # OUTPUT:
    #  - latinSquare: A nxn NumPy matrix of integers containing the Latin Square
    #                 generated by the function.
    #
    # NOTE: Although this algorithm has been tested and has always worked, there
    #       is no guarantee that it will always end. Also, the euristic complexity
    #       of the algorithm seems to be O(n!/2^n). When tested, the generation
    #       of a size 10 Latin Square, takes about 0.25 seconds in average.
    #
    remaining = [[ k+1 for k in range(n)] for i in range(n)]
    latinSquare = np.zeros((n,n),dtype = int)
    k = 0
    while k < n:
        j = 0
        row = []
        tried = [[] for i in range(n)]
        while j < n and j > -1:
            pick = [x for x in remaining[j] if x not in row]
            if len(pick) > 0:
                x = random.choice(pick)
                tried[j].append(x)
                row.append(x)
                remaining[j].remove(x)
                j += 1
            else:
                remaining[j] += tried[j]
                tried[j] = []
                if j > 0:
                    row.pop()
                j-=1
        if len(row) == n:
            latinSquare[k,:] = row
            k += 1
        else:
            # This is the case of failure, tnat I am unsure if will be reached.
            remaining = [[ k+1 for k in range(n)] for i in range(n)]
            latinSquare = np.zeros((n,n),dtype = int)
            k = 0
            # print('Failure')
    return latinSquare


def randomLatinSquareJM(n):
    # This is an implementation of the Jacobson and Matthews method to generate
    # random Latin Square, based on the golang implementation of Paul Hankin.
    #
    # INPUT:
    #  - n: integer, size of the Latin Square to be generated.
    #
    # OUTPUT:
    #  - latinSquare: A nxn NumPy matrix of integers containing the Latin Square
    #                 generated by the function.
    #
    # NOTE: The algorithm has been tested a few times. The time seems to be
    #       above the predicted O(n^3), but still polynomial. For sizes over 10,
    #       seems to be much faster than the naive approach.
    #
    t = time.time()
    # Define the variables we need
    xy = np.zeros((n,n),dtype = int) # frontal array
    xz = np.zeros((n,n),dtype = int) # lateral array
    yz = np.zeros((n,n),dtype = int) # upper array
    minIter = n**3 # number of iterations to consider
    proper = True # flag
    C = 0 # counter
    m = [0,0,0] # temporal container
    mxy = mxz = myz = 0 # temporal variables

    # Initialize the arrays.
    for i in range(n):
        for j in range(n):
            k = (i+j)%n
            xy[i,j] = k
            xz[i,k] = j
            yz[j,k] = i

    # Iteration of the method.
    while C < minIter:
        if proper:
            i,j,k = [random.randrange(n) for a in range(3)]
            while xy[i,j] == k:
                i,j,k = [random.randrange(n) for a in range(3)]
            ii = yz[j,k]
            jj = xz[i,k]
            kk = xy[i,j]
            iii, jjj, kkk = i, j, k
        else:
            i,j,k = m
            ii,iii = randomInversion(yz[j,k],myz)
            jj,jjj = randomInversion(xz[i,k],mxz)
            kk,kkk = randomInversion(xy[i,j],mxy)
        proper = (xy[ii,jj] == kk)
        if proper:
            C += 1
        else:
            m = [ii,jj,kk]
            mxy = xy[ii,jj]
            mxz = xz[ii,kk]
            myz = yz[jj,kk]
        xy[i,j] = kkk
        xy[i,jj] = kk
        xy[ii,j] = kk
        xy[ii,jj] = k
        yz[j,k] = iii
        yz[j,kk] = ii
        yz[jj,k] = ii
        yz[jj,kk] = i
        xz[i,k] = jjj
        xz[i,kk] = jj
        xz[ii,k] = jj
        xz[ii,kk] = j
    print(time.time()-t)
    return xy, xz, yz



def randomInversion(a,b):
    # This is a dumb function that given two imputs in order, a,b, some time
    # returns a,b, and half the time b,a.
    x = random.randrange(2)
    if x == 1:
        return a,b
    else:
        return b,a



























# EOF
