Estoy en la posición (0, 0) de una ciudad bidimensional infinita, que está perfectamente dividida en bloques centrados en cada punto de la red, algunos de los cuales contienen edificios. Un edificio en un cierto punto (x, y) ocupa todo el cuadrado con esquinas opuestas en (x-.5, y-.5) y (x + .5, y + .5) , incluido su borde. Un edificio es visible si hay algún segmento de línea desde (0, 0) hasta un punto en el edificio que no se cruza con ningún otro edificio.

Por ejemplo, yo (el @) puedo ver 6 edificios ( *) en la siguiente ciudad:

  *
 *
*
*@
x**
 *  y

No puedo ver el edificio marcado con un x, en (-1, -1) porque está obstruido por los dos adyacentes; o el marcado con un yat (3, -2) porque está obstruido por el borde del edificio (1, -1) .

Entrada

Una cadena de varias líneas, o una lista de líneas, opcionalmente rellenadas con espacios en un rectángulo. Contendrá solo:

• una sola @(mi posición)
• Espacios
• *, que representan edificios.

Siempre habrá al menos un edificio y, por lo tanto, al menos un edificio visible.

Salida

El número de edificios visibles.

Casos de prueba

*@
1

* *******
 @     * 
7

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

   *
  **
@ **
2

*      *
 *    * 
@
4

@
 *
  ***
1

_{Gracias a @Geobits por el título .}

Unidad + C #, 589 bytes

Este es probablemente el peor lenguaje para hacer un código de golf (léase: peor que Java), pero Unity viene con muchas características útiles para este desafío.

EDITAR: perdió un par de espacios, devuelve la longitud de la lista, no el contador

Golfizado:

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;}}

Sin golf:

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;
    }
}

Utilicé 3600 raycasts porque falla el quinto caso de prueba con menor. Todavía podría fallar para casos de prueba aún más grandes / más precisos.

Desafortunadamente, las compilaciones de webgl y de escritorio parecen romperse, por lo que todo lo que tengo es el código fuente para probar en github .

Java 8 lambda, 1506 1002 972 942 caracteres

Quería superar este desafío, ya que es muy interesante. El resultado (no muy golfista) se puede ver aquí:

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;}

Por supuesto, esto también existe en la versión sin golf:

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;
    }
}

Por lo tanto, parece muy difícil, pero es mucho más fácil de lo que uno podría pensar. Mi primera idea fue usar un algoritmo de intersección para verificar si una línea desde mi posición hasta el edificio se puede hacer sin intersecciones. Para hacer esto, decidí usar el algoritmo Cohen-Sutherland y dibujar líneas en las cuatro esquinas del edificio. Esto funcionó bastante bien para las primeras pruebas, pero la última falló. Pronto descubrí que es un caso en el que no se pueden ver las esquinas, sino una parte de un borde. Así que pensé en algún tipo de casting de rayos como @Blue lo hizo. Dejé de lado ese desafío, ya que no obtuve algún progreso. Entonces vi la respuesta de Blue y me vino a la mente la siguiente idea simple: cada edificio bloquea algún ángulo en el que no se puede ver nada más. Solo necesito hacer un seguimiento de lo que se puede ver y lo que ya está oculto por otros edificios. ¡Eso es!

El algoritmo funciona de la siguiente manera: determina el edificio con la menor distancia a la persona. Luego imaginamos cuatro líneas dibujadas desde la persona a las esquinas del edificio. Dos de estos tienen un valor extremo: el ángulo mínimo y máximo en el que se puede ver el edificio. Los tomamos como un rango y los comparamos con otros edificios de los cuales sabemos que se pueden ver (ninguno al principio). Los rangos pueden superponerse, incluirse entre sí o no tocarse en absoluto. Comparo los rangos y obtengo algunos nuevos rangos del edificio que no están ocultos por los edificios visibles. Si queda algo después de compararlo con los edificios a la vista, el edificio también es visible. Agregamos el rango de ángulo restante a la lista de rangos para comparar y comenzar con el próximo edificio con la siguiente distancia más larga.

A veces, los rangos pueden superponerse de una manera que termino con un rango de 0 grados. Estos rangos se filtrarán para no agregar por error un edificio que ni siquiera se puede ver.

Espero que alguien haya entendido esta explicación :)

Sé que este código no se juega mucho, lo haré lo antes posible.

Esa fue una tarea realmente desafiante. Pensaste que encontraste una solución que funciona, pero aún estás lejos. Creo que esta solución funciona bastante bien. No es muy rápido, pero al menos funciona;) ¡Gracias por ese rompecabezas!

Actualizar

Encontré el tiempo para jugar golf todo en una sola función, que por lo tanto se puede convertir en una lambda. Todas las funciones solo se llamaron una vez y, por lo tanto, se pueden poner en un solo método. Cambié de listas a conjuntos ya que esto guarda algunos caracteres adicionales. Las declaraciones se han reunido. Las comparaciones se han reunido y los caracteres fueron reemplazados por su valor ascii. La comparación de rango se puede expresar como muchos ternaries. Algunos trucos aquí y allá para evitar expresiones largas como Double.NEGATIVE_INFINITY se hicieron. Siempre que sea posible, se realizan asignaciones en línea. Para ahorrar un poco más, pasé de comparar los ángulos en grados a comparar los radianes. Todo el cambio salvó más de 500 caracteres, aunque espero tenerlo todo por debajo de 1000;)

Eliminé los genéricos cuando fue posible y acorté la comparación de retorno creando una matriz de un elemento y verifiqué su valor. También reemplacé el Double.NEGATIVE_INFINITY con PI2 y -PI2 ya que estos son los límites superior e inferior de los ángulos. ¡Ahora finalmente tiene menos de 1000 caracteres!

Fusioné los bucles para encontrar la ubicación de las personas y el iterador del edificio para guardar algunos personajes. Desafortunadamente, esto nos obliga a mover el retorno fuera del ciclo y aún usar un descanso, pero esta vez sin una etiqueta. Fusioné maxy distanceSquared, y min, y newDistanceSquared, ya que no se requieren al mismo tiempo. He cambiado Integer.MAX_VALUEa 2e31-1. También creé una constante half = 0.5que se usa para calcular las esquinas del edificio. Esto es más corto en la versión de golf. ¡En general, salvamos otros 30 caracteres!