Created
September 5, 2015 20:16
-
-
Save chitoge/a3dafbfa2deefd2740b9 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from functools import lru_cache | |
from math import sqrt | |
from itertools import product | |
from collections import defaultdict, deque | |
size = 4 | |
def gcd(x, y): | |
if (y == 0): return x | |
else: return gcd(y, x%y) | |
def sqr(x): return x*x | |
def popcnt(x): return bin(x).count('1') | |
def pack(x, y): return (1 << x*size+y) | |
# get points between two point | |
@lru_cache(maxsize=None) | |
def getBetween(p1, p2): | |
if (p1 == p2): return [] | |
res = [] | |
x1, y1 = p1 | |
x2, y2 = p2 | |
# vector between two points | |
dx, dy = x2 - x1, y2 - y1 | |
g = gcd(abs(dx), abs(dy)) | |
dx, dy = dx // g, dy // g | |
# check for points lie between them | |
x, y = x1 + dx, y1 + dy | |
while not ((x == x2) and (y == y2)): | |
res.append((x, y)) | |
x += dx | |
y += dy | |
return res | |
dp = defaultdict(float) | |
q = deque() | |
res = -1.0 | |
# init base cases | |
for x, y in product(range(size), repeat=2): | |
dp[(pack(x, y), x, y)] = 0 | |
q.append((pack(x, y), x, y)) | |
enqueued = set() | |
while (q): | |
mask, x, y = q.popleft() | |
# check second condition | |
if (popcnt(mask) >= 4): res = max(res, dp[(mask, x, y)]) | |
for i, j in product(range(size), repeat=2): | |
if (mask & pack(i, j)): continue | |
# check third condition | |
req = 0 | |
for u, v in getBetween((x, y), (i, j)): | |
req = req | pack(u, v) | |
if ((req & mask) != req): continue | |
dp[(mask | pack(i, j), i, j)] = max(dp[(mask | pack(i, j), i, j)], dp[mask, x, y] + sqrt(sqr(i-x) + sqr(j-y))) | |
if ((mask | pack(i, j), i, j) not in enqueued): | |
q.append((mask | pack(i, j), i, j)) | |
enqueued.add((mask | pack(i, j), i, j)) | |
print('%04f' % res) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment