Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Safe Coasts by jcg
#safe-coasts
def neighbours(cell, regional_map, directions):
# returns the set of coordinates of neighbours of cell (x,y) in map
# in any dir in list of directions (dx,dy)
s = set()
for d in directions:
x, y = cell[0]+d[0], cell[1]+d[1]
if 0 <= x < len(regional_map) and 0 <= y < len(regional_map[x]):
s.add((x, y))
return s
def neighbours_ortho(cell, regional_map):
# returns the set of coordinates of neighbours of cell (x,y) in map
# in orthogonal directions
return neighbours(cell, regional_map, ((0, -1), (0, 1), (1, 0), (-1, 0)))
def neighbours_ortho_diag(cell, regional_map):
# returns the set of coordinates of neighbours of cell (x,y) in map
# in orthogonal or diagonal directions
return (
neighbours_ortho(cell, regional_map)
| neighbours(cell, regional_map, ((-1, -1), (-1, 1), (1, 1), (1, -1)))
)
def search(regional_map,car):
# returns the set of coordinates in map whose value is car
s = set()
for l in range(len(regional_map)):
for c in range(len(regional_map[l])):
if regional_map[l][c] == car:
s.add((l, c))
return s
def connect(cell, regional_map, plusFD):
# updates "plusFD" the set of coordinates of connected flying dutchman cells
# in map. Recursive algorithm
plusFD.add(cell)
for x in neighbours_ortho(cell,regional_map): # for each neighbour
if (x not in plusFD
and all(regional_map[y[0]][y[1]] != 'X'
for y in neighbours_ortho_diag(x,regional_map))):
connect(x, regional_map, plusFD)
def finish_map(regional_map):
# init
regional_map=[list(row) for row in regional_map] # transform in list for update
initFD = search(regional_map, 'D') # first init pos of flying dutchman
plusFD = set() # set of possible flying dutchman cells
# update the possible FD cells
for fd in initFD:
if fd not in plusFD:
connect(fd, regional_map, plusFD)
# mark the connected cells
for x in plusFD:
regional_map[x[0]][x[1]]='D'
# mark the safe cells
initSAFE = search(regional_map,'.')
for x in initSAFE:
regional_map[x[0]][x[1]]='S'
#reconstructs the list of strings
return [''.join(regional_map[l])for l in range(len(regional_map))]
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert isinstance(finish_map(("D..", "...", "...")), (list, tuple)), "List or tuple"
assert list(finish_map(("D..XX.....",
"...X......",
".......X..",
".......X..",
"...X...X..",
"...XXXXX..",
"X.........",
"..X.......",
"..........",
"D...X....D"))) == ["DDSXXSDDDD",
"DDSXSSSSSD",
"DDSSSSSXSD",
"DDSSSSSXSD",
"DDSXSSSXSD",
"SSSXXXXXSD",
"XSSSSSSSSD",
"SSXSDDDDDD",
"DSSSSSDDDD",
"DDDSXSDDDD"], "Example"
assert list(finish_map(("........",
"........",
"X.X..X.X",
"........",
"...D....",
"........",
"X.X..X.X",
"........",
"........",))) == ["SSSSSSSS",
"SSSSSSSS",
"XSXSSXSX",
"SSSSSSSS",
"DDDDDDDD",
"SSSSSSSS",
'XSXSSXSX',
"SSSSSSSS",
"SSSSSSSS"], "Walls"
Aug. 30, 2014
