Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Bats Bunker by kurosawa4434
from math import sqrt, modf
from decimal import Decimal, ROUND_HALF_UP
WALL = 'W'
BAT = 'B'
ALPHA = 'A'
EMPTY = '.'
def checkio(bunker):
def round_half_up(number):
return int(Decimal(number).quantize(Decimal('1.'), rounding=ROUND_HALF_UP))
def search_obstacle(a, b):
min_y = min(a[0], b[0])
min_x = min(a[1], b[1])
max_y = max(a[0], b[0])
max_x = max(a[1], b[1])
dx = a[1] - b[1]
dy = a[0] - b[0]
ob_cells = []
delta = dy / dx if dx else 0
if abs(dy) >= abs(dx):
# scan vertical
for y in range(min_y, max_y):
d = (y - min_y + 0.5) / delta if delta else 0
mod_x = round_half_up(d)
decimal, integer = modf(d)
if delta > 0:
ob_cells.extend([(y, min_x + mod_x), (y + 1, min_x + mod_x)])
if abs(decimal) == 0.5:
ob_cells.extend([(y + 1, min_x + mod_x - 1)])
else:
ob_cells.extend([(y, max_x + mod_x), (y + 1, max_x + mod_x)])
if abs(decimal) == 0.5:
ob_cells.extend([(y + 1, max_x + mod_x + 1)])
else:
# scan horizontal
for x in range(min_x, max_x):
d = (x - min_x + 0.5) * delta
mod_y = round_half_up(d)
decimal, integer = modf(d)
if delta > 0:
ob_cells.extend([(min_y + mod_y, x), (min_y + mod_y, x + 1)])
if abs(decimal) == 0.5:
ob_cells.extend([(min_y + mod_y - 1, x + 1)])
else:
ob_cells.extend([(max_y + mod_y, x), (max_y + mod_y, x + 1)])
if abs(decimal) == 0.5:
ob_cells.extend([(max_y + mod_y + 1, x + 1)])
return set(ob_cells)
# objects list
bats = []
walls = set()
alpha = ()
for i, row in enumerate(bunker):
for j, cell in enumerate(row):
if cell in (BAT, ALPHA):
bats.append((i, j))
if cell in WALL:
walls.add((i, j))
if cell == ALPHA:
alpha = (i, j)
# make edges
edges = []
for i, b1 in enumerate(bats):
for b2 in (bats[i + 1:]):
if not walls & search_obstacle(b1, b2):
edges.append((b1, b2, sqrt((abs(b1[0] - b2[0]))**2 + (abs(b1[1] - b2[1]))**2)))
# search min route
def search_route(goal=alpha, start=(0, 0), rest=edges, route=0, min_route=999):
if min_route and route >= min_route:
return min_route
if start == goal:
return min(route, min_route)
for i, rt in enumerate(rest):
if start in (rt[0], rt[1]):
next_start = rt[0] if start == rt[1] else rt[1]
min_route = search_route(next_start, goal, rest[:i]+rest[i + 1:], route+rt[2], min_route)
return min_route
return search_route()
July 18, 2016
Comments:
