Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
sets + recursion solution in Clear category for Landing Site by ogoro
from typing import Set
from collections import deque
CLOCKWISE_EVEN = (0, -1), (1, -1), (1, 0), (0, 1), (-1, 0), (-1, -1)
CLOCKWISE_ODD = (0, -1), (1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0)
def get_circle(center_cells, radius=1):
circle_cells = set()
for a in center_cells:
ax = ord(a[0]) - 65
ay = int(a[1:])
# shift of deltas for even column
if ax % 2:
deltas = CLOCKWISE_ODD
else:
deltas = CLOCKWISE_EVEN
for dx, dy in deltas:
bx = ax + dx
by = ay + dy
b = chr(bx + 65) + str(by)
circle_cells.add(b)
if radius == 0:
return center_cells
else:
return center_cells | get_circle(circle_cells, radius-1)
def landing_site(obstacles: Set[str]) -> Set[str]:
print('Obstacles:', *sorted(obstacles))
landing_sites = dict()
for i in range(65, 77):
for j in range(1, 10):
a = chr(i) + str(j)
# print('A:', a)
radius = 1
while True:
circle_cells = get_circle({a}, radius)
is_in_grid = not any(cell[0] in '@M' or cell[1:] in ('0', '10') for cell in circle_cells)
is_without_obstacles = not any(cell in obstacles for cell in circle_cells)
is_suitable = is_in_grid and is_without_obstacles
# print(' Radius:', radius)
# print(' Circle cells:', *sorted(circle_cells))
# print(' In grid?', is_in_grid)
# print(' Is without obstacles?', is_without_obstacles)
# print(' Suitable?', is_suitable)
if not is_suitable:
break
landing_sites[a] = circle_cells
radius += 1
# if radius > 1:
# print('Landing site:', *sorted(landing_sites[a]))
# print()
if len(landing_sites) == 0:
print('Unfortunately, no sites found')
return set()
print('All sites:')
for center, cells in landing_sites.items():
print(center + ': ', *sorted(cells))
max_area = len(max(landing_sites.values(), key=len))
print('Maximum area:', max_area)
best_sites = {center for center, cells in landing_sites.items() if len(cells) == max_area}
print('Best sites:', best_sites)
print()
return best_sites
if __name__ == '__main__':
assert landing_site({'E5', 'E7', 'F4', 'F6', 'G4', 'G6', 'H3', 'H5'}) == {'C3', 'J7'}, 'crevasse'
assert landing_site({'A4', 'C2', 'C6', 'C9', 'D4', 'D7', 'F1', 'F5',
'F8', 'G4', 'H7', 'I2', 'I5', 'I9', 'K3', 'K8', 'L5'}) == {'B7', 'E3', 'J6'}, 'stones'
assert landing_site({'D3', 'D4', 'D5', 'D6', 'E3', 'E7', 'F2', 'F7', 'G2',
'G8', 'H2', 'H7', 'I3', 'I7', 'J3', 'J4', 'J5', 'J6'}) == {'G5'}, 'crater'
assert landing_site(set()) == {'E5', 'F5', 'G5', 'H5'}, 'plane'
assert landing_site({chr(c+65)+str(r+1) for c in range(12) for r in range(9)}) == set(), 'wasteland'
print('The local tests are done. Click on "Check" for more real tests.')
Dec. 4, 2020
