[Community Puzzle] Dead men's shot

Puzzles
1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

2

Hi i am running into problems. I can solve the triangle and the square, but i run into problems with the other shapes.
since i was able to solve the triangle I thought I will split the polygon into many triangles and then check on them, but i always fail. then i decided to also check on the lines of the triangles since i was not sure if they are included in the insideTriangle.

....
bool runPolygonAsTriangle(List polygon, List shot){
    bool hit = false;
    for (var i = 0, len = polygon.length; i+2 < len; ++i) {
      List point1 = polygon[0];
      List point2 = polygon[i+1];
      List point3 = polygon[i+2];
      List polygonTriangle = [point1,point2,point3];
      bool inside = isInside(polygonTriangle, polygonTriangle.length, shot);    
      bool onLine = isOnLineOfTriangle(point1,point2,point3,shot);
      stderr.writeln('shot $shot hit $inside inside triangle  on lines $onLine of $polygonTriangle');
      if(inside || onLine){
          hit = true;
         break;
          
       }
    }
    return hit;
}
bool isOnLineOfTriangle(List p1,List p2,List p3, List shot){
    bool value = false;
    if(isOnLine(p1,p2,shot) || isOnLine(p1,p3,shot) || isOnLine(p2,p3,shot)){
        value = true;
    }
    return value;
}
bool isOnLine(List p1,List p2,List shot){
    return getDistance(p1, shot) + getDistance(p2, shot) == getDistance(p1, p2);
}

num getDistance(List p1, List p2) {
  return sqrt(pow((p2[0] - p1[0]), 2) + pow((p2[1] - p1[1]), 2));
}
....

love any help :slight_smile:

3

Yo,

You can’t just take every 3 vertices make a triangle and expect to cover the whole polygon.
See https://rechneronline.de/pi/img/w/hexagon-short-diagonals.png
You’re missing out like 50% of the space

It could work if you were testing every possible triplet.
But you can also find a better solution

4

Hey,

thank you! actuially with the hexagon, my code would work haha
but not with complex polygon.

thanks for pointing that out!

:slight_smile:

5

Thinking it’s a safe bet that you’ve already solved it, but just in case for anyone still working on this, I can give my solution.

I was able to solve this using triangles I left the first vertice as a static point and cycled through the entire polygon creating triangles in each subsequent line. Only took one pass, wasn’t inefficient.

For each triangle created, I identified the mark and created 3 triangles from that triangle based on where the mark was located. If the area of those 3 triangles equal the triangle subsection then the mark was in the target and it’s a hit.

Hope this helps, enjoyed throwing around a little math here as most of the puzzles have been mainly logic.

6

For this puzzle, the input corners should be given in a more random order.

7

hey folks,
I stuck at Validator 3, although all remaining validators and tests are successful. My solution is based on ray casting algorithm in wiki.
any suggestions?

8

Poor test cases!
My initial solution which passes all the validators fails on a custom test case:

IN:
3
0 10
10 0
0 -10
1
0 0

OUT:
hit

9

I use vectors determinant to solve easily this problem.