Fed up with experimenting on tiny domestic animals, Nobel prize-winning Erwin Schrödinger has decided to find the nearest laser and shoot it at things instead. Because... science!
Description
You will be given two points that the laser passes through and the size of a laser beam, and you must determine where the laser beam must have gone, could have gone, and could not have gone.
The laser beam can be horizontal, vertical, or diagonal. For a size 1 laser beam, they look like this respectively:
# #
# #
##### # #
# #
# #
The diagonal laser beam can also be flipped. Size 2 laser beams look like this:
### ##
##### ### ###
##### ### ###
##### ### ###
### ##
In general, to get a laser beam of size (n), simply take the laser beam of size (n-1) and add a laser beam of size (1) on both sides. As a final example, here are all possible laser beams of size 3, shown on the same "board":
###.....#####.....##
####....#####....###
#####...#####...####
.#####..#####..#####
..#####.#####.#####.
...###############..
....#############...
.....###########....
####################
####################
####################
####################
####################
.....###########....
....#############...
...###############..
..#####.#####.#####.
.#####..#####..#####
#####...#####...####
####....#####....###
This "board" will always have dimensions of 20x20 (in characters).
Input
Your program will be given five integers as input. They are, in order, x1, y1, x2, y2, and the size of the laser beam. They must be taken exactly in that order. If you wish, you may take the ordered (x, y) pairs as an array, tuple, list, or other built-in data type that stores two values.
Both of the two points given as input will be within the board, and they are guaranteed to be distinct (i.e. the two points will never be the same). The size of the laser beam is bound to 1 ≤ size < 20. There will always be at least one possible laser beam that passes through both of the points.
Output
Your program must output a 20x20 grid of the following characters:
#if every possible laser beam that passes through the two points also passes through this point..if there is no laser beam that passes through the two points and this point.?if some, but not all, of the possible laser beams pass through this point.Xif this is one of the two original input points (this overrides the#).
Test cases
7, 7, 11, 3, 1
..............#.....
.............#......
............#.......
...........X........
..........#.........
.........#..........
........#...........
.......X............
......#.............
.....#..............
....#...............
...#................
..#.................
.#..................
#...................
....................
....................
....................
....................
....................
18, 18, 1, 1, 2
#??.................
?X??................
??#??...............
.??#??..............
..??#??.............
...??#??............
....??#??...........
.....??#??..........
......??#??.........
.......??#??........
........??#??.......
.........??#??......
..........??#??.....
...........??#??....
............??#??...
.............??#??..
..............??#??.
...............??#??
................??X?
.................??#
10, 10, 11, 10, 3
?????..????????..???
??????.????????.????
????????????????????
????????????????????
.???????????????????
..??????????????????
????????????????????
????????????????????
????????????????????
????????????????????
??????????XX????????
????????????????????
????????????????????
????????????????????
????????????????????
..??????????????????
.???????????????????
????????????????????
????????????????????
??????.????????.????
3, 3, 8, 10, 4
??????????..........
??????????..........
??????????..........
???X??????..........
???##?????..........
???###????..........
????###????.........
.????###????........
..????###????.......
..?????##?????......
..??????X??????.....
..??????????????....
..???????????????...
..????????????????..
..?????????????????.
..??????????????????
..??????????????????
..????????.?????????
..????????..????????
..????????...???????
The test cases were generated with the following Ruby script, located inside a Stack Snippet to conserve vertical space.
/*
#!/usr/bin/ruby
$w = $h = 20
class Point
attr_reader :x, :y
def initialize x, y
@x = x
@y = y
end
def inspect
"(#{@x}, #{@y})"
end
def == p
@x == p.x && @y == p.y
end
alias eql? ==
def hash
@x * $h + @y
end
def valid?
@x >= 0 && @y >= 0 && @x < $w && @y < $h
end
end
module Angle
HORIZONTAL = Point.new(1, 0)
VERTICAL = Point.new(0, 1)
DIAG1 = Point.new(1, 1)
DIAG2 = Point.new(1, -1)
end
def line_points point, angle, size
points = [point]
while points[-1].valid?
points.push Point.new(points[-1].x + angle.x, points[-1].y + angle.y)
end
points.pop
while points[0].valid?
points.unshift Point.new(points[0].x - angle.x, points[0].y - angle.y)
end
points.shift
if size == 1
points
elsif size > 1
a2 = case angle
when Angle::HORIZONTAL then Angle::VERTICAL
when Angle::VERTICAL then Angle::HORIZONTAL
else Angle::VERTICAL # HORIZONTAL also works
end
(size-1).times do |n|
np1 = Point.new(point.x + a2.x*(n+1), point.y + a2.y*(n+1))
np2 = Point.new(point.x - a2.x*(n+1), point.y - a2.y*(n+1))
points.concat line_points np1, angle, 1 if np1.valid?
points.concat line_points np2, angle, 1 if np2.valid?
end
points
else
throw 'something is very wrong'
end
end
def generate_grid x1, y1, x2, y2, size
p1 = Point.new(x1, y1)
p2 = Point.new(x2, y2)
lasers = []
points = [Point.new((p1.x + p2.x) / 2, (p1.y + p2.y) / 2)] # midpoint
while points.length > 0
point = points.pop
new_lasers = Angle.constants
.map{|angle| line_points point, Angle.const_get(angle), size }
.select {|laser| laser.include?(p1) && laser.include?(p2) } -
lasers
if new_lasers.length > 0
lasers.concat new_lasers
points.push Point.new(point.x+1, point.y) if point.x+1 < $w
points.push Point.new(point.x, point.y+1) if point.y+1 < $h
points.push Point.new(point.x-1, point.y) if point.x-1 > 0
points.push Point.new(point.x, point.y-1) if point.y-1 > 0
end
end
grid = Array.new($h) { ?. * $w }
lasers.each do |laser|
laser.each do |point|
grid[point.y][point.x] = ??
end
end
lasers.reduce(:&).each do |point|
grid[point.y][point.x] = ?#
end
grid[p1.y][p1.x] = 'X'
grid[p2.y][p2.x] = 'X'
grid
end
testcases = [
[7, 7, 11, 3, 1],
[18, 18, 1, 1, 2],
[10, 10, 11, 10, 3],
[3, 3, 8, 10, 4]
]
testcases.each do |test|
puts test * ', '
puts
puts generate_grid(*test).map{|line| ' ' + line }
puts
end
*/Rules
Your program must be able to solve each of the test cases in under 30 seconds (on a reasonable machine). This is more of a sanity check, as my test Ruby program solved all of the test cases near-instantaneously.
This is code-golf, so the shortest solution wins.
2 * size - 1. Size 1 is 1 pixel, size 2 is 3 pixels, size 3 is 5 pixels (see example above), size 4 is 7 pixels. \$\endgroup\$