这是一份 Python 解决方案,共有 18203 个字符,可以:
- 处理在“房间”外的镜子
- 基于二维限制计算无“房间”时的轨迹(规范说明了“房间”中必须有什么,但没有说明“房间”是否存在)
- 报告错误
它还需要进一步整理,而且我不知道二维物理学是否要求光线不能穿过自身...
"""
The shortest code by character count to input a 2D representation of a board,
and output 'true' or 'false' according to the input.
The board is made out of 4 types of tiles:
# - A solid wall
x - The target the laser has to hit
/ or \ - Mirrors pointing to a direction (depends on laser direction)
v, ^, > or < - The laser pointing to a direction (down, up, right and left
respectively)
There is only one laser and only one target. Walls must form a solid rectangle
of any size, where the laser and target are placed inside. Walls inside the
'room' are possible.
Laser ray shots and travels from it's origin to the direction it's pointing. If
a laser ray hits the wall, it stops. If a laser ray hits a mirror, it is bounces
90 degrees to the direction the mirror points to. Mirrors are two sided, meaning
both sides are 'reflective' and may bounce a ray in two ways. If a laser ray
hits the laser (^v><) itself, it is treated as a wall (laser beam destroys the
beamer and so it'll never hit the target).
"""
SOLID_WALL, TARGET, MIRROR_NE_SW, MIRROR_NW_SE, LASER_DOWN, LASER_UP, \
LASER_RIGHT, LASER_LEFT = range(8)
MIRRORS = (MIRROR_NE_SW, MIRROR_NW_SE)
LASERS = (LASER_DOWN, LASER_UP, LASER_RIGHT, LASER_LEFT)
DOWN, UP, RIGHT, LEFT = range(4)
LASER_DIRECTIONS = {
LASER_DOWN : DOWN,
LASER_UP : UP,
LASER_RIGHT: RIGHT,
LASER_LEFT : LEFT
}
ROW, COLUMN = range(2)
RELATIVE_POSITIONS = {
DOWN : (ROW, 1),
UP : (ROW, -1),
RIGHT: (COLUMN, 1),
LEFT : (COLUMN, -1)
}
TILES = {"#" : SOLID_WALL,
"x" : TARGET,
"/" : MIRROR_NE_SW,
"\\": MIRROR_NW_SE,
"v" : LASER_DOWN,
"^" : LASER_UP,
">" : LASER_RIGHT,
"<" : LASER_LEFT}
REFLECTIONS = {MIRROR_NE_SW: {DOWN : LEFT,
UP : RIGHT,
RIGHT: UP,
LEFT : DOWN},
MIRROR_NW_SE: {DOWN : RIGHT,
UP : LEFT,
RIGHT: DOWN,
LEFT : UP}}
def does_laser_hit_target(tiles):
"""
Follows a lasers trajectory around a grid of tiles determining if it
will reach the target.
Keyword arguments:
tiles --- row/column based version of a board containing symbolic
versions of the tiles (walls, laser, target, etc)
"""
laser_pos = get_laser_pos(tiles)
laser = get_tile(tiles, laser_pos)
beam_pos = list(laser_pos)
beam_dir = LASER_DIRECTIONS[laser]
number_of_rows = len(tiles)
while True:
axis, offset = RELATIVE_POSITIONS[beam_dir]
beam_pos[axis] += offset
try:
tile = get_tile(tiles, beam_pos)
except IndexError:
row_pos = beam_pos[ROW]
if axis == ROW:
if row_pos == -1:
beam_pos[ROW] = number_of_rows - 1
elif row_pos == number_of_rows:
beam_pos[ROW] = 0
elif axis == COLUMN:
row = tiles[row_pos]
number_of_cols = len(row)
col_pos = beam_pos[COLUMN]
if col_pos == -1:
beam_pos[COLUMN] = number_of_cols - 1
elif col_pos == number_of_cols:
beam_pos[COLUMN] = 0
tile = get_tile(tiles, beam_pos)
if tile in LASERS \
or tile == SOLID_WALL:
return False
if tile == TARGET:
return True
if tile in MIRRORS:
beam_dir = reflect(tile, beam_dir)
def get_laser_pos(tiles):
"""
Returns the current laser position or an exception.
Keyword arguments:
tiles --- row/column based version of a board containing symbolic
versions of the tiles (walls, laser, target, etc)
"""
number_of_rows = len(tiles)
for row_pos in range(number_of_rows):
row = tiles[row_pos]
number_of_cols = len(row)
for col_pos in range(number_of_cols):
tile = row[col_pos]
if tile in LASERS:
return row_pos, col_pos
def get_tile(tiles, pos):
"""
Retrieves a tile at the position specified.
Keyword arguments:
pos --- a row/column position of the tile
tiles --- row/column based version of a board containing symbolic
versions of the tiles (walls, laser, target, etc)
"""
row_pos = pos[ROW]
col_pos = pos[COLUMN]
row = tiles[row_pos]
tile = row[col_pos]
return tile
def get_wall_pos(tiles, reverse=False):
"""
Keyword arguments:
tiles --- row/column based version of a board containing symbolic
versions of the tiles (walls, laser, target, etc)
reverse --- whether to search in reverse order or not (defaults to no)
"""
number_of_rows = len(tiles)
row_iter = range(number_of_rows)
if reverse:
row_iter = reversed(row_iter)
for row_pos in row_iter:
row = tiles[row_pos]
number_of_cols = len(row)
col_iter = range(number_of_cols)
if reverse:
col_iter = reversed(col_iter)
for col_pos in col_iter:
tile = row[col_pos]
if tile == SOLID_WALL:
pos = row_pos, col_pos
if reverse:
offset = -1
else:
offset = 1
for axis in ROW, COLUMN:
next_pos = list(pos)
next_pos[axis] += offset
try:
next_tile = get_tile(tiles, next_pos)
except IndexError:
next_tile = None
if next_tile != SOLID_WALL:
raise WallOutsideRoomError(row_pos, col_pos)
return pos
def identify_tile(tile):
"""
Returns a symbolic value for every identified tile or None.
Keyword arguments:
tile --- the tile to identify
"""
try:
return TILES[tile]
except KeyError:
return
def main():
"""
Takes a board from STDIN and either returns a result to STDOUT or an
error to STDERR.
Called when this file is run on the command line.
"""
import sys
board = sys.stdin.read()
try:
result = shoot_laser(board)
except (MultipleLaserError, MultipleTargetError) as error:
sys.stderr.write("%s\n" % str(error))
for symbol in error.symbols:
board = board.replace(symbol, "\033[01;31m%s\033[m" % symbol)
sys.stderr.write("%s\n" % board)
sys.exit(1)
except (NoLaserError, NoTargetError) as error:
sys.stderr.write("%s\n" % str(error))
sys.stderr.write("%s\n" % board)
sys.exit(1)
except (OutsideRoomError, WallNotRectangleError) as error:
sys.stderr.write("%s\n" % str(error))
lines = board.split("\n")
line = lines[error.row_pos]
before = line[:error.col_pos]
after = line[error.col_pos + 1:]
symbol = line[error.col_pos]
line = "%s\033[01;31m%s\033[m%s" % (before, symbol, after)
lines[error.row_pos] = line
board = "\n".join(lines)
sys.stderr.write("%s\n" % board)
sys.exit(1)
except WallNotSolidError as error:
sys.stderr.write("%s\n" % str(error))
lines = board.split("\n")
line = lines[error.row_pos]
before = line[:error.col_pos]
after = line[error.col_pos + 1:]
symbol = line[error.col_pos]
line = "%s\033[01;5;31m#\033[m%s" % (before, after)
lines[error.row_pos] = line
board = "\n".join(lines)
sys.stderr.write("%s\n" % board)
sys.exit(1)
else:
result_str = str(result)
lower_result = result_str.lower()
sys.stdout.write("%s\n" % lower_result)
def parse_board(board):
"""
Interprets the raw board syntax and returns a grid of tiles.
Keyword arguments:
board --- the board containing the tiles (walls, laser, target, etc)
"""
tiles = list()
for line in board.split("\n"):
row = [identify_tile(tile) for tile in line]
tiles.append(row)
return tiles
def reflect(mirror, direction):
"""
Returns an updated laser direction after it has been reflected on a
mirror.
Keyword arguments:
mirror --- the mirror to reflect the laser from
direction --- the direction the laser is travelling in
"""
try:
direction_lookup = REFLECTIONS[mirror]
except KeyError:
raise TypeError("%s is not a mirror.", mirror)
try:
return direction_lookup[direction]
except KeyError:
raise TypeError("%s is not a direction.", direction)
def shoot_laser(board):
"""
Shoots the boards laser and returns whether it will hit the target.
Keyword arguments:
board --- the board containing the tiles (walls, laser, target, etc)
"""
tiles = parse_board(board)
validate_board(tiles)
return does_laser_hit_target(tiles)
def validate_board(tiles):
"""
Checks an board to see if it is valid and raises an exception if not.
Keyword arguments:
tiles --- row/column based version of a board containing symbolic
versions of the tiles (walls, laser, target, etc)
"""
found_laser = False
found_target = False
try:
n_wall, w_wall = get_wall_pos(tiles)
s_wall, e_wall = get_wall_pos(tiles, reverse=True)
except TypeError:
n_wall = e_wall = s_wall = w_wall = None
number_of_rows = len(tiles)
for row_pos in range(number_of_rows):
row = tiles[row_pos]
number_of_cols = len(row)
for col_pos in range(number_of_cols):
tile = row[col_pos]
if ((row_pos in (n_wall, s_wall) and
col_pos in range(w_wall, e_wall))
or
(col_pos in (e_wall, w_wall) and
row_pos in range(n_wall, s_wall))):
if tile != SOLID_WALL:
raise WallNotSolidError(row_pos, col_pos)
elif (n_wall != None and
(row_pos < n_wall or
col_pos > e_wall or
row_pos > s_wall or
col_pos < w_wall)):
if tile in LASERS:
raise LaserOutsideRoomError(row_pos, col_pos)
elif tile == TARGET:
raise TargetOutsideRoomError(row_pos, col_pos)
elif tile == SOLID_WALL:
if not (row_pos >= n_wall and
col_pos <= e_wall and
row_pos <= s_wall and
col_pos >= w_wall):
raise WallOutsideRoomError(row_pos, col_pos)
else:
if tile in LASERS:
if not found_laser:
found_laser = True
else:
raise MultipleLaserError(row_pos, col_pos)
elif tile == TARGET:
if not found_target:
found_target = True
else:
raise MultipleTargetError(row_pos, col_pos)
if not found_laser:
raise NoLaserError(tiles)
if not found_target:
raise NoTargetError(tiles)
class LasersError(Exception):
"""Parent Error Class for all errors raised."""
pass
class NoLaserError(LasersError):
"""Indicates that there are no lasers on the board."""
symbols = "^v><"
def __str__ (self):
return "No laser (%s) to fire." % ", ".join(self.symbols)
class NoTargetError(LasersError):
"""Indicates that there are no targets on the board."""
symbols = "x"
def __str__ (self):
return "No target (%s) to hit." % ", ".join(self.symbols)
class MultipleLaserError(LasersError):
"""Indicates that there is more than one laser on the board."""
symbols = "^v><"
def __str__ (self):
return "Too many lasers (%s) to fire, only one is allowed." % \
", ".join(self.symbols)
class MultipleTargetError(LasersError):
"""Indicates that there is more than one target on the board."""
symbols = "x"
def __str__ (self):
return "Too many targets (%s) to hit, only one is allowed." % \
", ".join(self.symbols)
class WallNotSolidError(LasersError):
"""Indicates that the perimeter wall is not solid."""
__slots__ = ("__row_pos", "__col_pos", "n_wall", "s_wall", "e_wall",
"w_wall")
def __init__(self, row_pos, col_pos):
self.__row_pos = row_pos
self.__col_pos = col_pos
def __str__ (self):
return "Walls must form a solid rectangle."
def __get_row_pos(self):
return self.__row_pos
def __get_col_pos(self):
return self.__col_pos
row_pos = property(__get_row_pos)
col_pos = property(__get_col_pos)
class WallNotRectangleError(LasersError):
"""Indicates that the perimeter wall is not a rectangle."""
__slots__ = ("__row_pos", "__col_pos")
def __init__(self, row_pos, col_pos):
self.__row_pos = row_pos
self.__col_pos = col_pos
def __str__ (self):
return "Walls must form a rectangle."
def __get_row_pos(self):
return self.__row_pos
def __get_col_pos(self):
return self.__col_pos
row_pos = property(__get_row_pos)
col_pos = property(__get_col_pos)
class OutsideRoomError(LasersError):
"""Indicates an item is outside of the perimeter wall."""
__slots__ = ("__row_pos", "__col_pos", "__name")
def __init__(self, row_pos, col_pos, name):
self.__row_pos = row_pos
self.__col_pos = col_pos
self.__name = name
def __str__ (self):
return "A %s was found outside of a 'room'." % self.__name
def __get_row_pos(self):
return self.__row_pos
def __get_col_pos(self):
return self.__col_pos
row_pos = property(__get_row_pos)
col_pos = property(__get_col_pos)
class LaserOutsideRoomError(OutsideRoomError):
"""Indicates the laser is outside of the perimeter wall."""
def __init__ (self, row_pos, col_pos):
OutsideRoomError.__init__(self, row_pos, col_pos, "laser")
class TargetOutsideRoomError(OutsideRoomError):
"""Indicates the target is outside of the perimeter wall."""
def __init__ (self, row_pos, col_pos):
OutsideRoomError.__init__(self, row_pos, col_pos, "target")
class WallOutsideRoomError(OutsideRoomError):
"""Indicates that there is a wall outside of the perimeter wall."""
def __init__ (self, row_pos, col_pos):
OutsideRoomError.__init__(self, row_pos, col_pos, "wall")
if __name__ == "__main__":
main()
一个用于展示彩色错误报告的Bash脚本:
declare -a TESTS
test() {
echo -e "\033[1m$1\033[0m"
tput sgr0
echo "$2" | ./lasers.py
echo
}
test \
"no laser" \
" ##########
# x #
# / #
# /#
# \\ #
##########"
test \
"multiple lasers" \
" ##########
# v x #
# / #
# /#
# \\ ^ #
##########"
test \
"no target" \
" ##########
# v #
# / #
# /#
# \\ #
##########"
test \
"multiple targets" \
" ##########
# v x #
# / #
# /#
# \\ x #
##########"
test \
"wall not solid" \
" ##### ####
# v x #
# / #
# /#
# \\ #
##########"
test \
"laser_outside_room" \
" ##########
> # x #
# / #
# /#
# \\ #
##########"
test \
"laser before room" \
" > ##########
# x #
# / #
# /#
# \\ #
##########"
test \
"laser row before room" \
" >
##########
# x #
# / #
# /#
# \\ #
##########"
test \
"laser after room" \
" ##########
# x #
# / #
# /#
# \\ #
########## >"
test \
"laser row after room" \
" ##########
# x #
# / #
# /#
# \\ #
##########
> "
test \
"target outside room" \
" ##########
x # v #
# / #
# /#
# \\ #
##########"
test \
"target before room" \
" x ##########
# v #
# / #
# /#
# \\ #
##########"
test \
"target row before room" \
" x
##########
# v #
# / #
# /#
# \\ #
##########"
test \
"target after room" \
" ##########
# v #
# / #
# /#
# \\ #
########## x"
test \
"target row after room" \
" ##########
# v #
# / #
# /#
# \\ #
##########
x "
test \
"wall outside room" \
" ##########
# # v #
# / #
# /#
# \\ x #
##########"
test \
"wall before room" \
" # ##########
# v #
# / #
# /#
# \\ x #
##########"
test \
"wall row before room" \
" #
##########
# v #
# / #
# /#
# \\ x #
##########"
test \
"wall after room" \
" ##########
# v #
# / #
# /#
# \\ x #
########## #"
test \
"wall row after room" \
" ##########
# v #
# / #
# /#
# \\ x #
##########
#"
test \
"mirror outside room positive" \
" ##########
/ # / \\ #
# #
# \\ x#
# > / #
########## "
test \
"mirrors outside room negative" \
" ##########
\\ # v x #
# / #
# /#
# \\ #
##########"
test \
"mirror before room positive" \
" \\ ##########
# / \\ #
# #
# \\ x#
# > / #
########## "
test \
"mirrors before room negative" \
" / ##########
# v x #
# / #
# /#
# \\ #
##########"
test \
"mirror row before room positive" \
" \\
##########
# / \\ #
# #
# \\ x#
# > / #
########## "
test \
"mirrors row before room negative" \
" \\
##########
# v x #
# / #
# /#
# \\ #
##########"
test \
"mirror after row positive" \
" ##########
# / \\ #
# #
# \\ x#
# > / #
########## / "
test \
"mirrors after row negative" \
" ##########
# v x #
# / #
# /#
# \\ #
########## / "
test \
"mirror row after row positive" \
" ##########
# / \\ #
# #
# \\ x#
# > / #
##########
/ "
test \
"mirrors row after row negative" \
" ##########
# v x #
# / #
# /#
# \\ #
##########
/ "
test \
"laser hitting laser" \
" ##########
# v \\#
# #
# #
#x \\ /#
##########"
test \
"mirrors positive" \
" ##########
# / \\ #
# #
# \\ x#
# > / #
########## "
test \
"mirrors negative" \
" ##########
# v x #
# / #
# /#
# \\ #
##########"
test \
"wall collision" \
" #############
# # #
# > # #
# # #
# # x #
# # #
#############"
test \
"extreme example" \
" ##########
#/\\/\\/\\ #
#\\\\//\\\\\\ #
#//\\/\\/\\\\#
#\\/\\/\\/x^#
##########"
test \
"brian example 1" \
"##########
# / \\ #
# #
#/ \\ x#
#\\> / #
##########"
test \
"brian example 2" \
"##########
# / \\#
# / \\ #
#/ \\ x#
#\\^/\\ / #
##########"
开发中使用的单元测试:
import unittest
from lasers import *
class TestTileRecognition(unittest.TestCase):
def test_solid_wall(self):
self.assertEqual(SOLID_WALL, identify_tile("#"))
def test_target(self):
self.assertEqual(TARGET, identify_tile("x"))
def test_mirror_ne_sw(self):
self.assertEqual(MIRROR_NE_SW, identify_tile("/"))
def test_mirror_nw_se(self):
self.assertEqual(MIRROR_NW_SE, identify_tile("\\"))
def test_laser_down(self):
self.assertEqual(LASER_DOWN, identify_tile("v"))
def test_laser_up(self):
self.assertEqual(LASER_UP, identify_tile("^"))
def test_laser_right(self):
self.assertEqual(LASER_RIGHT, identify_tile(">"))
def test_laser_left(self):
self.assertEqual(LASER_LEFT, identify_tile("<"))
def test_other(self):
self.assertEqual(None, identify_tile(" "))
class TestReflection(unittest.TestCase):
def setUp(self):
self.DIRECTION = LEFT
self.NOT_DIRECTIO