Cities: Sightlines

Question

I'm at position (0, 0) of an infinite two-dimensional city, which is perfectly divided into blocks centered at each lattice point, some of which contain buildings. A building at a certain point (x, y) takes up the entire square with opposite corners at (x-.5, y-.5) and (x+.5, y+.5), including its border. A building is visible iff there is some line segment from (0, 0) to a point in the building which does not intersect any other building.

For example, I (the @) can see 6 buildings (*) in the following city:

  *
 *
*
*@
x**
 *  y

I can't see the building marked with an x, at (-1, -1) because it's obstructed by the two adjacent to it; or the one marked with a y at (3, -2) because it's obstructed by the edge of the (1, -1) building.

Input

A multiline string, or list of lines, optionally padded with spaces into a rectangle. It will contain only:

• a single @ (my position)
• Spaces
• *, which represent buildings.

There will always be at least one building, and therefore at least one visible building.

Output

The number of visible buildings.

Test cases

*@
1

* *******
 @     * 
7

*****
**@**
*****
4

   *
  **
@ **
2

*      *
 *    * 
@
4

@
 *
  ***
1

_{Thanks to @Geobits for the title.}

Answer 1

Unity + C#, 589 bytes

This is probably the worst language to do a code golf in (read: worse than Java), but Unity comes with a lot a helpful features for this challenge.

EDIT: missed a couple of spaces, returns list length, not counter

Golfed:

using UnityEngine;using System.Collections;public class c:MonoBehaviour{public int h(string[]i){ArrayList k=new ArrayList();for(int y=0;y<i.Length;y++){char[]l=i[y].ToCharArray();int x=0;foreach(char c in l){if(c=='*'){GameObject b=GameObject.CreatePrimitive(PrimitiveType.Cube);b.transform.position=new Vector3(x,y);}if(c=='@')transform.position=new Vector3(x,y);x++;}}for(int n=0;n<3600;n++){RaycastHit h;Physics.Raycast(transform.position,Quaternion.Euler(0,0,n/10)*Vector3.up,out h);if(h.collider!=null){GameObject o=h.collider.gameObject;if(!k.Contains(o))k.Add(o);}}return k.Count;}}

Ungolfed:

using UnityEngine;
using System.Collections;

public class citiessightlines : MonoBehaviour {

    public ArrayList todelete;   // Anything concerning this array just has to do with cleanup of 
                                 //objects for testing, and doesn't contribute to the byte count.
    void Start()
    {
        todelete = new ArrayList();
    }
    public int calcSight(string[]input)
    {
        todelete = new ArrayList();
        int total = 0;
        ArrayList check = new ArrayList();
        for (int y=0;y < input.Length; y++)
        {
            char[] line = input[y].ToCharArray();
            for (int x = 0; x < line.Length; x++)
            {
                char c = line[x];
                if (c == '*')
                {
                    GameObject cube = GameObject.CreatePrimitive(PrimitiveType.Cube);
                    cube.transform.position = new Vector3(x, y);
                    todelete.Add(cube);
                }
                if (c == '@')
                {
                    transform.position = new Vector3(x, y);
                }
            }
        }
        for (int angle=0; angle < 3600; angle++)
        {
            RaycastHit hit;
            Physics.Raycast(transform.position, Quaternion.Euler(0, 0, angle/10) * Vector3.up, out hit);
            if (hit.collider!=null)
            {
                GameObject hitObject = hit.collider.gameObject;
                if (!check.Contains(hitObject)&&hitObject!=this)
                {
                    total += 1;
                    check.Add(hitObject);
                }
           }
        }
        return total;
    }
}

I used 3600 raycasts because it fails the 5th test case with lower. It still might fail for even larger/more precise test cases.

Unfortunately, both webgl and desktop builds seem to break, so all I have is the source code to test with on github.

Answer 2

Java 8 lambda, 1506 1002 972 942 characters

I wanted to beat this challenge, as it is very interesting. The result (not very golfy) can be seen here:

import java.util.*;f->{Set<double[]>B=new HashSet(),r,n;double a,M,m,P=Math.PI*2,z=.5;int x=0,y,v=0,i,j,c[],p,q,l=g.length;for(;x<l;x++)for(y=0;y<g[x].length;y++)if(g[x][y]>63)for(;;){c=new int[]{-1};M=2e31-1;for(i=0;i<l;i++)for(j=0;j<g[i].length;j++)if(g[i][j]==42)if((m=(p=x-i)*p+(q=y-j)*q)<M){M=m;c=new int[]{i,j};}if(c[0]<0)break;g[c[0]][c[1]]=0;double[]A={(a=Math.atan2((c[1]-=y)-z,(c[0]-=x)-z))<0?a+P:a,(a=Math.atan2(c[1]+z,c[0]-z))<0?a+P:a,(a=Math.atan2(c[1]+z,c[0]+z))<0?a+P:a,(a=Math.atan2(c[1]-z,c[0]+z))<0?a+P:a};r=new HashSet();M=-P;m=P;for(double d:A){M=d>M?d:M;m=d<m?d:m;}r.add(new double[]{m,M});for(double[]t:B){n=new HashSet();for(double[]h:r)for(double[]u:t[0]<h[0]?t[1]<h[0]?new double[][]{h}:t[1]<h[1]?new double[][]{{t[1],h[1]}}:new double[0][]:t[0]>h[1]?new double[][]{h}:t[1]>h[1]?new double[][]{{h[0],t[0]}}:new double[][]{{h[0],t[0]},{t[1],h[1]}})if(u[0]<u[1])n.add(u);r=n;}B.addAll(r);if(!r.isEmpty())v++;}return v;}

Of course this also exists in the ungolfed version:

import java.util.*;

public class AngleCheck {

    static int getViewableBuildingsC(char[][] grid) {

        Set<double[]> blocked = new HashSet(), ranges, newRanges;

        double angle, max, min, PI2 = Math.PI * 2, half = 0.5;

        int x = 0, y, viewable = 0, i, j, building[], dX, dY, length = grid.length;

        for (; x < length; x++) {
            for (y = 0; y < grid[x].length; y++) {
                if (grid[x][y] > 63) {
                    for (;;) {
                        building = new int[]{-1};
                        max = 2e31-1;
                        for (i = 0; i < length; i++) {
                            for (j = 0; j < grid[i].length; j++) {
                                if (grid[i][j] == 42) {
                                    if ((min = (dX = x - i) * dX + (dY = y - j) * dY) < max) {
                                        max = min;
                                        building = new int[]{i, j};
                                    }
                                }
                            }   
                        }

                        if (building[0] < 0)
                            break;

                        grid[building[0]][building[1]] = 0;
                        double[] angles = {
                                        (angle = Math.atan2((building[1] -= y) - half, (building[0] -= x) - half)) < 0 ? angle + PI2 : angle,
                                        (angle = Math.atan2(building[1] + half, building[0] - half)) < 0 ? angle + PI2 : angle,
                                        (angle = Math.atan2(building[1] + half, building[0] + half)) < 0 ? angle + PI2 : angle,
                                        (angle = Math.atan2(building[1] - half, building[0] + half)) < 0 ? angle + PI2 : angle};

                        ranges = new HashSet();

                        max = -PI2;
                        min = PI2;
                        for (double d : angles) {
                            max = d > max ? d : max;
                            min = d < min ? d : min;
                        }

                        ranges.add(new double[]{min, max});

                        for (double[] reference : blocked) {
                            newRanges = new HashSet();
                            for (double[] currentRange : ranges) {
                                for (double[] subRange : reference[0] < currentRange[0] ?
                                            reference[1] < currentRange[0] ?
                                                // whole range after referencerange
                                                new double[][]{currentRange}
                                            :
                                                reference[1] < currentRange[1] ?
                                                    // lower bound inside referencerange, but upper bound outside
                                                    new double[][]{{reference[1], currentRange[1]}}
                                                :
                                                    // whole range inside referencerange -> nothing free
                                                    new double[0][]
                                        :
                                            // greater or equal lower bound
                                            reference[0] > currentRange[1] ?
                                                // whole range before referencerange
                                                new double[][]{currentRange}
                                            :
                                                // ranges overlap
                                                reference[1] > currentRange[1] ?
                                                    // range starts before and ends in reference range
                                                    new double[][]{{currentRange[0], reference[0]}}
                                                :
                                                    // referencerange is in the range -> two free parts, one before, one after this
                                                    new double[][]{{currentRange[0], reference[0]}, {reference[1], currentRange[1]}}) {
                                    if (subRange[0] < subRange[1])
                                        newRanges.add(subRange);
                                }
                            }
                            ranges = newRanges;
                        }

                        blocked.addAll(ranges);
                        if (!ranges.isEmpty()) {
                            viewable++;
                        }
                    }
                }
            }
        }
        return viewable;
    }
}

So it looks very difficult but it's way easier than one might think. My first idea was to use some intersection algorithm to check whether a line from my position to the building can be made without any intersections. To do this I decided to use the Cohen-Sutherland algorithm and draw lines to all four corners of the building. This worked pretty well for the first tests, but the last one failed. I soon found out, that it's a case where you can't see the corners but a part of an edge. So I thought about some sort of ray casting like @Blue did it. I put that challenge away, as I didn't got some progress. Then I saw Blue's answer and the following simple idea came to my mind: Each building blocks some angle in which nothing else can be seen. I just need to keep track of what can be seen and what is already hidden by other buildings. That's it!

The algorithm works as follows: It determines the building with the smallest distance to the person. Then we imagine four lines drawn from the person to the corners of the building. Two of these have an extreme value: The minimum and maximum angle in which the building can be seen. We take them as a range and compare them with other buildings of which we know that they can be seen (none at the beginning). The ranges may overlap, include each other or don't touch at all. I compare the ranges and get some new ranges of the building which aren't hidden by the viewable buildings. If there is something remaining after comparing it with the buildings in-sight the building is also viewable. We add the remaining angle range to the list of ranges to compare to and start off with the next building with the next longer distance.

Sometimes the ranges may overlap in a way that I end up with a range of 0 degrees. These ranges will be filtered to don't mistakenly add a building that isn't even viewable.

I hope someone understood this explanation :)

I know this code isn't golfed very much, I'll do this asap.

That was a really challenging task. You thought you found a solution that works but instead you are far away still. I think this solution works pretty good. It isn't very fast but at least it works ;) Thanks for that puzzle!

---

Update

I found the time to golf the whole thing down into a single function, which thus can be turned into a lambda. All functions were only called once and thus can be put into one method. I switched from lists to sets as this saves some additional characters. The declarations have been put together. The comparisons have been put together and characters were replaced by there ascii value. The range comparing can be expressed as many ternaries. Some tricks here and there to prevent long expressions like Double.NEGATIVE_INFINITY got done. Where possible inline assigments are done. To save a bit more I switched from comparing the angles in degrees to comparing the radians. The whole change saved over 500 characters, I hope to get it all under 1000 though ;)

I removed the generics where possible and shortened the return comparison by creating an one element array and check it's value instead. I also replaced the Double.NEGATIVE_INFINITY with PI2 and -PI2 as these are the upper and lower bounds of the angles. Now it's finally under 1000 chars long!

I merged the loops for finding the persons location and the building iterator to save some characters. Unfortunately this requires us to move the return out of the loop and still use a break but this time without a label. I merged max and distanceSquared and min and newDistanceSquared as they aren't required at the same time. I changed Integer.MAX_VALUE to 2e31-1. Also I created a constant half = 0.5 which is used to calculate the corners of the building. This is shorter in the golfed version. Overall we saved another 30 characters!