Source code for tryalgo.laser_mirrors
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Orienting mirrors to allow connectivity by a laser beam
jill-jênn vie et christoph dürr - 2014-2019
"""
# snip{ laser-miroir-preparation
# directions
UP = 0
LEFT = 1
DOWN = 2
RIGHT = 3
# orientations None:? 0:/ 1:\
# destination UP LEFT DOWN RIGHT
reflex = [[RIGHT, LEFT], [DOWN, UP], [LEFT, RIGHT], [UP, DOWN]]
# pylint: disable=unused-variable, unused-argument
[docs]
def laser_mirrors(rows, cols, mir):
"""Orienting mirrors to allow reachability by laser beam
:param int rows:
:param int cols: rows and cols are the dimension of the grid
:param mir: list of mirror coordinates, except
mir[0]= laser entrance,
mir[-1]= laser exit.
:complexity: :math:`O(2^n)`
"""
# build structures
n = len(mir)
orien = [None] * (n + 2)
orien[n] = 0 # arbitrary orientations
orien[n + 1] = 0
succ = [[None for direc in range(4)] for i in range(n + 2)]
L = [(mir[i][0], mir[i][1], i) for i in range(n)]
L.append((0, -1, n)) # enter
L.append((0, cols, n + 1)) # exit
last_r, last_i = None, None
for (r, c, i) in sorted(L): # sweep by row
if last_r == r:
succ[i][LEFT] = last_i
succ[last_i][RIGHT] = i
last_r, last_i = r, i
last_c = None
for (r, c, i) in sorted(L, key=lambda rci: (rci[1], rci[0])):
if last_c == c: # sweep by column
succ[i][UP] = last_i
succ[last_i][DOWN] = i
last_c, last_i = c, i
if solve(succ, orien, n, RIGHT): # exploration
return orien[:n]
return None
# snip}
# snip{ laser-miroir-exploration
[docs]
def solve(succ, orien, i, direc):
"""Can a laser leaving mirror i in direction direc reach exit ?
:param i: mirror index
:param direc: direction leaving mirror i
:param orient: orient[i]=orientation of mirror i
:param succ: succ[i][direc]=succ mirror reached
when leaving i in direction direc
"""
assert orien[i] is not None
j = succ[i][direc]
if j is None: # basic case
return False
if j == len(orien) - 1:
return True
if orien[j] is None: # try both orientations
for x in [0, 1]:
orien[j] = x
if solve(succ, orien, j, reflex[direc][x]):
return True
orien[j] = None
return False
return solve(succ, orien, j, reflex[direc][orien[j]])
# snip}