cruz.py

import random
import time
from collections import Counter
import matplotlib.pyplot as plt
import math

x = 0;
y = 1;
EULER = math.exp(1)
BETA = 1
pointsSquare = [(1.00,4.00), (2.00,4.00), (3.00,4.00), (4.00,4.00), (1.00,3.00), (2.00,3.00), (3.00,3.00), (4.00,3.00), (1.00,2.00), (2.00,2.00), (3.00,2.00), (4.00,2.00), (1.00,1.00), (2.00,1.00), (3.00,1.00), (4.00,1.00)]

def getRigthMostPoint(points):
  smallerX = 99999
  for i in range(len(points)):
      if points[i][0] < smallerX:
          smallerX = points[i][x]
  higherY = -9999
  for i in range(len(points)):
      if points[i][x] == smallerX and points[i][y] > higherY:
          higherY = points[i][y]
  return (smallerX, higherY)

def hasX(xToSearch, points):
    for i in range(len(points)):
        if points[i][x] == xToSearch:
            return True
    return False

def getNextX(currentX, originalPoints):
    points = list(originalPoints)
    points.sort(key=lambda point: point[x])
    for i in range(len(points)):
        if points[i][x] > currentX:
            return points[i][x]
    return currentX + 1

def isRectangle(pointSet):
    rigthMostPoint = getRigthMostPoint(pointsSquare)
    firstLinePoints = []

    for i in range(len(pointSet)):
        if pointSet[i][x] == rigthMostPoint[x]:
            firstLinePoints.append(pointSet[i])
    firstLineLen = len(firstLinePoints)
    firstLinePoints.sort(key=lambda point: point[y])
    nextX = getNextX(rigthMostPoint[x], pointSet)
    while hasX(nextX, pointSet):
        currentLine = []
        for i in range(len(pointSet)):
            if(pointSet[i][x] == nextX):
                currentLine.append(pointSet[i])
        if(len(currentLine) != firstLineLen):
            return False
        currentLine.sort(key=lambda point: point[y])
        for i in range(len(currentLine)):
            if(currentLine[i][y] != firstLinePoints[i][y]):
                return False
        nextX = getNextX(nextX, pointSet)
    return True

def getSurrounding(point):
    x = point[0]
    y = point[1]
    return [(x-1, y), (x+1, y), (x, y+1), (x, y-1), (x+1, y+1), (x+1, y-1), (x-1, y+1), (x-1, y-1)]

def getEmptySurroundings(point, cross):
    sur = getSurrounding(point)
    ret = []
    for p in sur:
        if p not in cross:
            ret.append(p)
    return ret

def getCrossSurrounding(point):
    x = point[0]
    y = point[1]
    return [(x-1, y), (x+1, y), (x, y+1), (x, y-1)]

# def getPointsInBorder2(pointSet):
#     ret = []
#     for p in pointSet:
#         surrounds = getCrossSurrounding(p)
#         for sur in surrounds:
#             if sur not in pointSet:
#                 ret.append(p)
#                 break
#     return ret


def getPointsInBorder(pointSet):
    maxes = getMaxes(pointSet)
    maxX = maxes['maxX']+1
    minX = maxes['minX'] - 1
    maxY = maxes['maxY'] + 1
    minY = maxes['minY'] -1
    ret = []
    for currentY in range(minY, maxY+1):
        xRange = range(minX, maxX+1)
        for currentX in xRange:
            if(currentX, currentY) in pointSet:
                if (currentX, currentY) not in ret:
                    ret.append((currentX, currentY))
                break
        xRange.reverse()
        for currentX in xRange:
            if((currentX, currentY) in pointSet):
                if (currentX, currentY) not in ret:
                    ret.append((currentX, currentY))
                break
    for currentX in range(minX, maxX+1):
        yRange = range(minY, maxY+1)
        for currentY in yRange:
            if(currentX, currentY) in pointSet:
                if (currentX, currentY) not in ret:
                    ret.append((currentX, currentY))
                break
        yRange.reverse()
        for currentY in yRange:
            if((currentX, currentY) in pointSet):
                if (currentX, currentY) not in ret:
                    ret.append((currentX, currentY))
                break
    return ret

def isValidCross(pointSet):
    maxes = getMaxes(pointSet)
    maxX = maxes['maxX'] + 1
    minX = maxes['minX'] - 1
    maxY = maxes['maxY'] + 1
    minY = maxes['minY'] - 1
    for currentY in range(minY, maxY + 1):
        xRange = range(minX, maxX + 1)
        started = False
        hasBase = False
        for currentX in xRange:
            currentPoint = (currentX, currentY)
            if currentPoint not in pointSet and not started:
                continue
            elif currentPoint not in pointSet and started:
                if hasBase:
                    hasBase = False
                    started = False
                    continue;
                else:
                    return False
            elif currentPoint in pointSet:
                started = True
                if((currentX, currentY + 1) in pointSet or (currentX, currentY - 1) in pointSet):
                    hasBase = True
    for currentX in range(minX, maxX + 1):
        yRange = range(minY, maxY + 1)
        started = False
        hasBase = False
        for currentY in yRange:
            currentPoint = (currentX, currentY)
            if currentPoint not in pointSet and not started:
                continue
            elif currentPoint not in pointSet and started:
                if hasBase:
                    hasBase = False
                    started = False
                    continue;
                else:
                    return False
            elif currentPoint in pointSet:
                started = True
                if ((currentX + 1, currentY) in pointSet or (currentX - 1, currentY) in pointSet):
                    hasBase = True
    return True

def isEmptySpaceEligible(emptySpace, currentPoint, cross):
    crossSurrounding = getCrossSurrounding(emptySpace)
    for neighbour in crossSurrounding:
        if neighbour in cross and neighbour != currentPoint:
            return True
    return False

#Funcao Auxiliar para testes
def buildCross():
    points = []
    for x in [-1, 0, 1]:
        for y in [-4, -3, -2, -1, 0, 1, 2, 3, 4]:
            points.append((x,y))
    for x in [-4, -3, -2]:
        for y in [-1, 0, 1]:
            points.append((x,y))
    for x in [2, 3, 4]:
        for y in [-1, 0, 1]:
            points.append((x,y))
    return points

#Funcao Auxiliar para testes
def buildSmallCross():
    points = []
    for x in [0, 1]:
        for y in [-2, -1, 0, 1]:
            points.append((x, y))
    points.append((2,-1))
    points.append((2,0))
    points.append((-1,-1))
    points.append((-1,0))
    return points

def calcFactor(jumpRate):
    return -1.0*(math.log(1-random.uniform(0, 1))/jumpRate)

def getEligibleSpaces(emptySpaces, currentPoint, cross):
    ret = []
    for emptySpace in emptySpaces:
        if(isEmptySpaceEligible(emptySpace, currentPoint, cross)):
            ret.append(emptySpace)
    return ret

def calculateEnergy(border, cross):
    energy = 0
    for point in border:
        surroundig = getCrossSurrounding(point)
        for sur in surroundig:
            if sur in cross:
                energy += 1
    return energy

def canJump(point, cross):
    return False

def getLowestFactor(border, cross):
    lowestJumpTime = 9999999
    ret = (-999, -999)
    currentEnergy = 0;
    for point in border:
        pointEmptySpaces = getEmptySurroundings(point, cross)
        eligibleSpaces = getEligibleSpaces(pointEmptySpaces, point, cross)
        if(len(eligibleSpaces) > 0):
            currentEnergy = calculateEnergy(border, cross)
        for space in eligibleSpaces:
            crossCopy = cross[:]
            crossCopy.remove(point)
            crossCopy.append(space)
            if not isValidCross(crossCopy): continue;
            newBorder = getPointsInBorder(crossCopy)
            newEnergy = calculateEnergy(newBorder, crossCopy)
            deltaEnergy = newEnergy - currentEnergy
            if deltaEnergy >= 0:
                jumpRate = math.pow(EULER, -1 * BETA* deltaEnergy)
                jumpTime = calcFactor(jumpRate)
                if jumpTime < lowestJumpTime:
                    lowestJumpTime = jumpTime
                    ret = (point, space)
    return ret

def getNeighbours(point, pointSet):
    surroundingPlaces = getCrossSurrounding(point)
    ret = []
    for place in surroundingPlaces:
        if place in pointSet and place != point:
            ret.append(place)
    return ret

def getFreeSpots(point, pointSet, isCross):
    ret = []
    surroundings = getCrossSurrounding(point) if isCross else getSurrounding(point)
    for p in surroundings:
        if p not in pointSet: ret.append(p)
    return ret

def getMaxes(points):
    maxX = -99999999999
    maxY = -99999999999
    minX = 99999999999
    minY = 99999999999
    for p in points:
        if p[x] > maxX: maxX = p[x]
        if p[x] < minX: minX = p[x]
        if p[y] > maxY: maxY = p[y]
        if p[y] < minY: minY = p[y]
    return {
        'maxX' : maxX,
        'minX': minX,
        'minY': minY,
        'maxY': maxY
    }

def plot(points, rng, border, text, newPoint, oldPoint):
    plt.clf()
    X = []
    Y = []
    C = []
    alpha = []
    for p in points:
        X.append(p[x])
        Y.append(p[y])
        if p == newPoint:
            C.append('red')
        elif p in border:
            C.append('orange')
        else:
            C.append('blue')
    X.append(oldPoint[x])
    Y.append(oldPoint[y])
    C.append('#0F0F0F0f')
    plt.scatter(X, Y,  s=100, marker='s', color=C)
    plt.axis(rng)
    plt.savefig('D:\\Cross\\'+text+'.png')

cross = buildCross()
print cross
maxes = getMaxes(cross)
maxX = maxes['maxX'] + 3
minX = maxes['minX'] - 3
maxY = maxes['maxY'] + 3
minY = maxes['minY'] - 3
rng = [minX,maxX,minY,maxY]
plot(cross, rng, [], 'a', (0,0), (0,0))
border = getPointsInBorder(cross)
print getNeighbours((1,2), border)
print border

# print len(cross) - len(border)
# print isRectangle(cross)
# print isRectangle(border)
# print isRectangle(pointsSquare)
# print getLowestFactor(border, cross)
MAX_IT = 10000
it = 0
print "Valid?" + str(isValidCross(cross))

while it < MAX_IT or isRectangle(cross):
    border = getPointsInBorder(cross)
    next = getLowestFactor(border, cross)
    if(next[0] not in cross):
        print "OXXX"
    cross.remove(next[0])
    if(next[1] in cross):
        print 'ERRO1'
        break
    cross.append(next[1])
    it += 1
    #print it
    print(len(cross))
    plot(cross, rng, getPointsInBorder(cross), "IT_"+str(it), next[1], next[0])

print 'done'
print cross
#print getLowestFactor(border)