21
\$\begingroup\$

Introduction

The arena is a flatland dotted with skyscrapers, which your enemies use for cover. You and your enemies shoot each other with lasers. All of you carry jet packs, allowing flight.

Which enemies can you hit with your laser, and which are hiding?

Problem

First, the size of an arena is given by an integer n on a single line. The following n lines contain n integers per line separated by a space. Each integer represents the height of the building at that location. Each building is a rectangular solid, 1 unit by 1 unit by height units.

Next, your location is given on a single line as three floating point numbers x, y, z.

Finally, the number of enemies are given by an integer m on a single line. The following m lines contain three floating point numbers per line separated by a space. These represent the x, y, and z coordinates of an enemy. The coordinate system is defined as follows:

  • x is measured from left to right in the city input
  • y is measured from top to bottom
  • z is measured from the ground up

For each enemy, if an unobstructed line can be drawn from you to that enemy, output a positive integer. Otherwise, output a negative integer. Separate outputs with a new line.

Sample Input

Comments, denoted by '#', are present to help you quickly see what each line does. They will not be present in the actual input.

5              # Size of the map
0 0 0 0 0      # Buildings
0 0 0 0 0      # Buildings
4 4 4 4 4      # Buildings
0 0 0 0 0      # Buildings
0 0 0 0 0      # Buildings
2.5 0.0 4.0    # Your location
3              # Number of enemies
2.5 5.0 0.1    # Enemy location
2.5 5.0 5.0    # Enemy location
0.0 2.7 4.5    # Enemy location

Sample output

For the sample input above, we output the following:

-1
1
1

Assumptions

  • 0 < n < 100
  • 0 < m < 100
  • 0 <= x <= n
  • 0 <= y <= n
  • 0 <= z < n
  • Players will not be located on or inside of a corner, edge, or side of a building
  • Your line of sight to an enemy will never be tangent to the corner, edge, or side of a building
  • A player is not an obstruction
\$\endgroup\$
  • \$\begingroup\$ Glad to see it out of the sandbox :) \$\endgroup\$ – Timtech May 21 '14 at 14:04
  • 7
    \$\begingroup\$ If I can't destroy an enemy, may I join them? \$\endgroup\$ – John Dvorak May 21 '14 at 14:13
  • \$\begingroup\$ @user80551 Sorry, I had to roll back your edit to the title because the mispelling was intentional. Google it. \$\endgroup\$ – Rainbolt May 22 '14 at 13:42
  • \$\begingroup\$ @Rusher Oh , sorry, IDK that \$\endgroup\$ – user80551 May 22 '14 at 15:22
  • 4
    \$\begingroup\$ Related: youtube.com/watch?v=NKTpWi5itOM \$\endgroup\$ – qwr May 22 '14 at 21:39
5
\$\begingroup\$

Perl, 301 296 282

Edit 2: Actually, competition or not, there is no reason not to golf it a little further. Test it online.

Edit: Couple of parentheses gone, simpler regex to check for non-zero integer.

With newlines and indentation for readability:

sub i{<>=~/\S+/g}
@b=map[i],@r=0..<>-1;
print.1<=>(map{
    @a[1,0,2,4,3]=@a;
    @b=map{$i=$_;[map$b[$_][$i],@r]}@r;
    grep$a[3]
        &&($k=(($x=$_)-$a[0])/$a[3])**2<=$k
        &&pop[sort map@{$b[$_]}[$x-!!$x,$x],
                   ($_=$a[1]+$k*$a[4]),$_-/^\d+$/]
           >=$a[2]+$k*$a[5]
    ,@R=@r
}@a=map$_-shift@v,i,@u=@v=@$_),$/for([i])x<>

It requires 5.14 because of scalar (array reference) argument to pop.

\$\endgroup\$
  • \$\begingroup\$ Can you explain your solution a little bit? I haven't tested it and I haven't leant Perl, yet, so some comments would be nice. \$\endgroup\$ – WorldSEnder Jun 25 '14 at 21:50
  • \$\begingroup\$ @WorldSEnder, outline of the algorithm is as follows. Straight line PE connects two points in 3-D space, "Player" (X1Y1Z1) and "Enemy" (X2Y2Z2). Its projection on (XY) plane intersects some of the grid-lines i.e. integers x = const or y = const such as X1 < x < X2 or Y1 < y < Y2 (assuming here that e.g. X1 < X2, but it's not important). Coordinates x y of these intersections can easily be found, and therefore z coordinate of a point on PE line, too. \$\endgroup\$ – user2846289 Jun 27 '14 at 11:09
  • \$\begingroup\$ (continued) On the other hand, for any x y coordinates, we know height h of the building (rather, maximum height of up to 4 buildings which share x y point). Enemy can be shot if (and only if) h < z for all "intersection points" mentioned above. Implementation is some basic arithmetics, as well as several tricks with Perl for the purpose of golfing. Decyphering the details of how I did it a month ago will take some time now :-). \$\endgroup\$ – user2846289 Jun 27 '14 at 11:10
  • \$\begingroup\$ Argh, as I see there is a bug in the last (5th) revision: indices to the elements of @a array in grep expression should appear in the order 0,3,0,4,1,5,2 instead of 3,0,3,1,4,2,5 - sorry. \$\endgroup\$ – user2846289 Jun 28 '14 at 12:00
  • \$\begingroup\$ OK, better late than never, and to finish with this all, here is commented version. \$\endgroup\$ – user2846289 Jul 3 '14 at 15:15
3
\$\begingroup\$

Python 2.7 - 429 420 308 308 chars

I thought of this challenge more of as a math problem than a code golf problem, so don't be too harsh to me if I missed some obvious optimizations. Anyways, here is the code:

b=lambda:raw_input().split()
m=map
d=range(input())
h=[m(int,b())for _ in d]
x,y,z=m(float,b())
for e,f,g in[m(float,b())for _ in[1]*input()]:o=lambda x,y,u,v,i,j:i<=x+u/v*(j+1-y)<=i+1<[]>z+(g-z)/v*(j+1-y)<=max(h[i][j:j+2])if v else 0;print 1-2*any(o(x,y,e-x,f-y,j,i)+o(y,x,f-y,e-x,i,j)for j in d for i in d)

This should work for edge and corner cases (pun unintended) and is pretty solid. Ouput for the provided example:

-1
1
1

And here is a "short" explanation:

fast_read = lambda : raw_input().split() # define a helper
# m = map another helper
grid_range = range(input())
houses = [map(int, fast_read()) for _ in grid_range]
# 'map(int,...)' is a shorter version of '[int(a) for a in ...]'
pos_x,pos_y,pos_z = map(float, fast_read()) # read the player position
# the following loops through all enemy coordinates
for ene_x, ene_y, ene_z in [map(float,fast_read()) for _ in[1]*input()]:
    vec_z = ene_z - pos_z
    # is_hit macro uses vector math to detemine whether we hit a specific wall
    # wallhit -> 1
    # no wallhit -> 0
    is_hit = lambda pos_x, pos_y, vec_x, vec_y, co_x, co_y:\
        (co_x <= pos_x + vec_x/vec_y * (co_y + 1 - pos_y) <= co_x + 1 # check if hit_x is good
        < [] > # an effective and
        pos_z + (ene_z - pos_z)/vec_y * (co_y + 1 - pos_y) <= max(houses[co_x][co_y:co_y + 2]) # check if hit_z is good
        if vec_y else 0) # if vec_y is 0 we can't hit the wall parallel to y
    print (.5 - # can hit -> 0.5 - 0 = 0.5, hit -> 0.5 - 1 = -0.5
            any( # if we hit any wall
                # we swap x and y-coordinate because we read them "incorrect"
                is_hit(pos_x, pos_y, ene_x-pos_x, ene_y-pos_y, cur_y, cur_x) # check for hit in x-direction
                + # effective 'or'
                is_hit(pos_y, pos_x, ene_y-pos_y, ene_x-pos_x, cur_x, cur_y) # check for hit in y-direction
                    for cur_y in grid_range # loop y
                for cur_x in grid_range)) # loop x

I guess this is full of flaws. Btw I saved chars at nesting (first level is one space, second one tab, then one tab and a space...). I hope after all this answer can point to the way to do it.

\$\endgroup\$
  • \$\begingroup\$ I just realized that the sample input was invalid because one of the enemies was located directly on the ground, which is technically the top of a zero height building, which I promised would not happen. Your submission passes the corrected test case, but it fails this one - ideone.com/8qn3sv . Can you check my test case? I might be missing something or maybe my coordinate system is unclear. \$\endgroup\$ – Rainbolt May 22 '14 at 13:23
  • \$\begingroup\$ No, it's just that the vector is going right through the corners... now I know why you promised Assumption 6&7 :) \$\endgroup\$ – WorldSEnder May 22 '14 at 17:41
  • \$\begingroup\$ btw, I output a negative float but that can be fixed with 2 extra chars (print 1-2*... instead of print.5-...) So it's not that big of a difference I guess \$\endgroup\$ – WorldSEnder May 22 '14 at 19:54
  • \$\begingroup\$ You passed the few tests I came up with. Nice job! You should still go ahead and make it print integers to keep in line with the spec. \$\endgroup\$ – Rainbolt May 22 '14 at 20:07
  • 1
    \$\begingroup\$ Accepting your answer until someone comes up with a better solution. I don't think they will. Very rarely does anyone revisit old solved challenges. You should golf more! It looks like you know your stuff. :) \$\endgroup\$ – Rainbolt May 28 '14 at 13:01
2
\$\begingroup\$

C - 2468

Not golfed at all, but hopefully it's a starting point for more interesting implementations. The implementation of intersect is cribbed heavily from Adrian Boeing. His pseudo-code was incomplete, but his explanation of the math was invaluable. The basic idea is that you take a line from the player to the target and clip it against all the walls of each building, updating the length for each wall. The remaining length is the portion inside the building, so if it's zero, there was no intersection.

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

typedef struct
{
    float x;
    float y;
    float z;
} vec3;

float
dot(vec3 a, vec3 b)
{
    return a.x * b.x + a.y * b.y + a.z * b.z;
}

vec3
scale(float s, vec3 a)
{
    vec3 r;
    r.x = s * a.x;
    r.y = s * a.y;
    r.z = s * a.z;
    return r;
}

vec3
add(vec3 a, vec3 b)
{
    vec3 r;
    r.x = a.x + b.x;
    r.y = a.y + b.y;
    r.z = a.z + b.z;
    return r;
}

int
intersect(vec3 a, vec3 b, vec3 *normals, vec3 *points, int nnormals)
{
    vec3 ab = add(b, scale(-1, a));
    float tfirst = 0;
    float tlast = 1;
    int i;
    for(i = 0; i < nnormals; i++)
    {
        float d = dot(normals[i], points[i]);
        float denom = dot(normals[i], ab);
        float dist = d - dot(normals[i], a);
        float t = dist / denom;
        if(denom > 0 && t > tfirst)
        {
            tfirst = t;
        }
        else if(denom < 0 && t < tlast)
        {
            tlast = t;
        }
    }
    return tfirst < tlast ? 1 : 0;
}

const vec3 N = {0,-1,0};
const vec3 S = {0,1,0};
const vec3 W = {-1,0,0};
const vec3 E = {1,0,0};
const vec3 D = {0,0,-1};

int
main(void)
{
    vec3 normals[5];
    vec3 player;
    vec3 *targets;
    int i;
    int j;
    vec3 *buildings;
    vec3 *b;
    int nbuildings = 0;
    int n;
    int m;
    char line[300];
    normals[0] = N;
    normals[1] = S;
    normals[2] = W;
    normals[3] = E;
    normals[4] = D;
    fgets(line, 300, stdin);
    n = atoi(line);
    /*5 sides for each building*/
    buildings = calloc(n * n * 5, sizeof(*buildings));
    b = buildings;
    for(i = 0; i < n; i++)
    {
        char *z;
        fgets(line, 300, stdin);
        for(j = 0; j < n && (z = strtok(j ? NULL : line, " \n")) != NULL; j++)
        {
            vec3 bottom;
            vec3 top;
            if(z[0] == '0') continue;
            nbuildings++;
            bottom.x = j;
            bottom.y = i;
            bottom.z = 0;
            top.x = j + 1;
            top.y = i + 1;
            top.z = atoi(z);
            b[0] = top;
            b[1] = bottom;
            b[2] = top;
            b[3] = bottom;
            b[4] = top;
            b += 5;
        }
    }
    fgets(line, 300, stdin);
    player.x = atof(strtok(line, " "));
    player.y = atof(strtok(NULL, " "));
    player.z = atof(strtok(NULL, " \n"));
    fgets(line, 300, stdin);
    m = atoi(line);
    targets = calloc(m, sizeof(*targets));
    for(i = 0; i < m; i++)
    {
        int hit = 1;
        fgets(line, 300, stdin);
        targets[i].x = atof(strtok(line, " "));
        targets[i].y = atof(strtok(NULL, " "));
        targets[i].z = atof(strtok(NULL, " \n"));
        for(j = 0; j < nbuildings; j++)
        {
            b = &buildings[j * 5];
            if(intersect(player, targets[i], normals, b, 5) == 1)
            {
                hit = 0;
                break;
            }
        }
        printf("%d\n", hit ? 1 : -1);
    }
    free(buildings);
    free(targets);
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Tried a few test cases and you passed all of them. Here is the ideone that anyone else can use to verify - ideone.com/MTXpzF \$\endgroup\$ – Rainbolt May 22 '14 at 15:01

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.