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!