Skip to content

Instantly share code, notes, and snippets.

@alexnum

alexnum/cruz.py

Last active August 30, 2017 02:57
Show Gist options
  • Save alexnum/f92d0aa977c97e2420cc86c70fce43df to your computer and use it in GitHub Desktop.
Save alexnum/f92d0aa977c97e2420cc86c70fce43df to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment