24
\$\begingroup\$

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.
  • X if 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 , so the shortest solution wins.

\$\endgroup\$
  • 2
    \$\begingroup\$ The terminology used here tripped me up initially. I believe laser normally refers to a device that produces laser beams. What you're representing here are really the beams, right? This is not supposed to be a representation of the actual laser, which would be the device generating the beams? \$\endgroup\$ – Reto Koradi Jun 12 '15 at 13:51
  • 2
    \$\begingroup\$ The last test case looks wrong. A size 4 laser should be 9 pixels wide. The vertical track should be at least that wide, but in fact is narrower. \$\endgroup\$ – Level River St Jun 12 '15 at 13:51
  • 1
    \$\begingroup\$ @steveverrill Size 4 is 7 pixels wide. The width in pixels is 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\$ – Reto Koradi Jun 14 '15 at 2:02
  • 2
    \$\begingroup\$ I don't see how Schrodinger is related to this challenge. \$\endgroup\$ – ace Jun 14 '15 at 21:54
  • 1
    \$\begingroup\$ @JonasDralle Again, the time limit is mostly just a sanity check, and almost every submission is expected to complete in far less time than that. \$\endgroup\$ – Doorknob Jun 16 '15 at 13:08
5
\$\begingroup\$

C, 291 280 277 265 bytes

x,y,A,C,B,D,a,c,b,d,w,s,t;T(i){return abs(i)<2*w-1;}U(j,k){s+=T(j-k)*T(j)*T(k);t*=T(j-k)*j*k<1;}main(){for(scanf("%i%i%i%i%i",&a,&b,&c,&d,&w);y<20;y+=!x)s=0,t=1,U(A=a-x,C=c-x),U(B=b-y,D=d-y),U(A-B,C-D),U(A+B,C+D),putchar((x=++x%21)?".?#x"[!!s+t+(!A*!B+!C*!D)]:10);}

Can be compiled/run using:

gcc laser.c -o laser && echo "10 10 11 10 3" | ./laser

Below, the same code with whitespace and explanatory comments:

// Integers...
x,y,A,C,B,D,a,c,b,d,w,s,t;

// Is true if i is in range (of something)
T(i){return abs(i)<2*w-1;}

// Tests if lasers (horizontal, vertical, diagonal, etc) can/must exist at this point
// T(j-k) == 0 iff the laser of this direction can exist
// s += 1 iff this laser direction can pass through this point
// t *= 1 iff this laser direction must pass through this point
U(j,k){
    s+=T(j-k)*T(j)*T(k);
    t*=T(j-k)*j*k<1;
}

main(){ 
    // Read input; p0=(a,b), p1=(c,d)
    for(scanf("%i%i%i%i%i",&a,&b,&c,&d,&w); y<20; y+=!x)

        // A, B, C and D represent delta-x and delta-y for each points
        // e.g.: if we're processing (2,3), and p0=(4,5), A=4-2, B=5-3
        // s != 0 iff (x,y) can have some laser through it
        // t == 1 iff all lasers pass through (x,y)
        // (!A*!B+!C*!D) == 1 iff (x,y) is either p0 or p1  
        s=0,t=1,U(A=a-x,C=c-x),U(B=b-y,D=d-y),U(A-B,C-D),U(A+B,C+D),
        putchar((x=++x%21)?".?#x"[!!s+t+(!A*!B+!C*!D)]:10);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ U(int j,int k) --> U(j,k); '\n' --> 10. \$\endgroup\$ – ace Jun 14 '15 at 21:42
  • 1
    \$\begingroup\$ k<=0 --> k<1 \$\endgroup\$ – ace Jun 18 '15 at 17:34
  • \$\begingroup\$ Good points. I'd upvote if I could! \$\endgroup\$ – André Harder Jun 21 '15 at 16:27
4
\$\begingroup\$

C, 302 bytes

b[400],x,y,s,t,w,d,e,g,k;f(u,v){d=u*x+v*y;e=u*s+v*t;if(e<d)k=e,e=d,d=k;for(k=0;k<400&d+w>e;++k)g=k%20*u+k/20*v,b[k]|=g>e-w&g<d+w|(g<d|g>e)*2;}main(){scanf("%d%d%d%d%d",&x,&y,&s,&t,&w);w=2*w-1;f(1,0);f(0,1);f(1,1);f(1,-1);b[y*20+x]=4;b[t*20+s]=4;for(k=0;k<400;)putchar(".#.?X"[b[k]]),++k%20?0:puts("");}

Input is taken from stdin, reading the 5 numbers in the defined order.

Before final size reduction step:

#include <stdio.h>
#include <stdlib.h>

int b[400], x, y, s, t, w, d, e, g, k;

void f(int u, int v) {
  d = u * x + v * y;
  e = u * s + v * t;
  if (e < d) k = e, e = d, d = k;
  if (d + w > e) {
    for (k = 0; k < 400; ++k) {
      g = u * (k % 20) + v * (k / 20);
      if (g > e - w && g < d + w) b[k] |= 1;
      if (g < d || g > e) b[k] |= 2;
    }
  }
}

int main() {
  scanf("%d%d%d%d%d", &x, &y, &s, &t, &w);
  w = 2 * w - 1;
  f(1, 0); f(0, 1); f(1, 1); f(1, -1);
  b[y * 20 + x] = 4;
  b[t * 20 + s] = 4;
  for (k = 0; k < 400; ) {
     putchar(".#.?X"[b[k]]);
     ++k % 20 ? 0 : puts("");
  }
}

Some explanation of key steps:

  • Array b holds the state/result. Bit 0 will be set for all pixels that can be reached by a beam. Bit 1 will be set for all pixels that are not covered by all beams.
  • Function f is called for all 4 directions (vertical, horizontal, both diagonals). Its arguments specify the normal vector of the direction.
  • In function f:
    • The distance of both input points relative to the direction is calculated (d and e) as the dot product of the point with the normal vector passed in.
    • The distances are swapped if necessary so that d is always less than or equal to e.
    • If the difference between d and e is larger than the width of the beam, no beams are possible in this direction.
    • Otherwise, loop over all pixels. Set bit 0 if the pixel is reachable by any beam, and bit 1 if it is not covered by all beams.
  • Mark the two input points with value 4. Since we used bits 0 and 1 to track the state, which results in values 0 to 3, this is the smallest unused value.
  • Loop over the pixels in b, and convert the values in the range 0 to 4 to their corresponding character while printing them out.
\$\endgroup\$
  • \$\begingroup\$ you can likely save a little by putting the last line of code into the incrementer in that for loop \$\endgroup\$ – Not that Charles Jun 16 '15 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.