Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Monte Carlo solution in Uncategorized category for Colder-Warmer by Rounin
import random
def clamp(minn, maxn, n):
return max(minn, min(maxn, n))
def distance(candidate, step):
return (candidate[0]-step[0])**2+(candidate[1]-step[1])**2
def nextNode(acceptableSquares):
acceptableNodes = []
for row in range(len(acceptableSquares)):
for col in range(len(acceptableSquares[0])):
if acceptableSquares[row][col] == True:
acceptableNodes.append([row,col])
return random.choice(acceptableNodes)
def filtercandidate(steps, candidate, acceptableSquares):
if acceptableSquares[candidate[0]][candidate[1]] == True:
for i in range(1, len(steps)):
if clamp(-1, 1, distance(candidate, steps[i-1])-distance(candidate, steps[i])) != steps[i][2]:
acceptableSquares[candidate[0]][candidate[1]] = False
# A variation on a binary search. Searches rows first, and then columns.
def checkio(steps):
seencandidates = {}
acceptableSquares = eval(str([[True]*10]*10))
for row in range(len(acceptableSquares)):
for col in range(len(acceptableSquares[0])):
filtercandidate(steps,[row, col], acceptableSquares)
while True:
nextstep = nextNode(acceptableSquares)
seencandidates[str(nextstep)] = seencandidates.get(str(nextstep), 0) + 1
if seencandidates[str(nextstep)] <= 1 and acceptableSquares[nextstep[0]][nextstep[1]]:
return nextstep
if __name__ == '__main__':
# This part is using only for self-checking and not necessary for auto-testing
from math import hypot
MAX_STEP = 12
def check_solution(func, goal, start):
prev_steps = [start]
for step in range(MAX_STEP):
row, col = func([s[:] for s in prev_steps])
if [row, col] == goal:
return True
if 10 <= row or 0 > row or 10 <= col or 0 > col:
print("You gave wrong coordinates.")
return False
prev_distance = hypot(prev_steps[-1][0] - goal[0], prev_steps[-1][1] - goal[1])
distance = hypot(row - goal[0], col - goal[1])
alteration = 0 if prev_distance == distance else (1 if prev_distance > distance else -1)
prev_steps.append([row, col, alteration])
print("Too many steps")
return False
assert check_solution(checkio, [7, 7], [5, 5, 0]), "1st example"
assert check_solution(checkio, [5, 6], [0, 0, 0]), "2nd example"
July 22, 2017