Je suis à la position (0, 0) d'une ville bidimensionnelle infinie, qui est parfaitement divisée en blocs centrés à chaque point du réseau, dont certains contiennent des bâtiments. Un bâtiment à un certain point (x, y) occupe la place entière avec des coins opposés en (x-0,5, y-0,5) et (x + 0,5, y + 0,5) , y compris sa bordure. Un bâtiment est visible s'il existe un segment de ligne allant de (0, 0) à un point du bâtiment qui ne coupe aucun autre bâtiment.

Par exemple, je (le @) vois 6 bâtiments ( *) dans la ville suivante:

  *
 *
*
*@
x**
 *  y

Je ne vois pas le bâtiment marqué d'un x, à (-1, -1) car il est obstrué par les deux adjacents; ou celui marqué d'un yat (3, -2) car il est obstrué par le bord du bâtiment (1, -1) .

Contribution

Une chaîne multiligne, ou liste de lignes, éventuellement complétée par des espaces dans un rectangle. Il ne contiendra que:

• un seul @(ma position)
• Les espaces
• *, qui représentent des bâtiments.

Il y aura toujours au moins un bâtiment, et donc au moins un bâtiment visible.

Production

Le nombre de bâtiments visibles.

Cas de test

*@
1

* *******
 @     * 
7

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

   *
  **
@ **
2

*      *
 *    * 
@
4

@
 *
  ***
1

_{Merci à @Geobits pour le titre .}

Unity + C #, 589 octets

C'est probablement le pire langage pour faire un golf de code (lire: pire que Java), mais Unity est livré avec beaucoup de fonctionnalités utiles pour ce défi.

EDIT: manque quelques espaces, renvoie la longueur de la liste, pas le compteur

Golfé:

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

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

J'ai utilisé 3600 raycasts car il échoue au 5ème cas de test avec inférieur. Il peut encore échouer pour des cas de test encore plus grands / plus précis.

Malheureusement, les versions webgl et desktop semblent ne pas fonctionner, donc tout ce que j'ai est le code source avec lequel tester sur github .

Java 8 lambda, 1506 1002 972 942 caractères

Je voulais battre ce défi, car il est très intéressant. Le résultat (pas très golfique) peut être vu ici:

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

Bien sûr, cela existe également dans la version non golfée:

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

Cela semble donc très difficile, mais c'est beaucoup plus facile qu'on ne pourrait le penser. Ma première idée a été d'utiliser un algorithme d'intersection pour vérifier si une ligne de ma position au bâtiment peut être faite sans intersection. Pour ce faire, j'ai décidé d'utiliser l'algorithme de Cohen-Sutherland et de tracer des lignes aux quatre coins du bâtiment. Cela a plutôt bien fonctionné pour les premiers tests, mais le dernier a échoué. J'ai vite découvert que c'est un cas où vous ne pouvez pas voir les coins mais une partie d'un bord. J'ai donc pensé à une sorte de lancer de rayons comme le faisait @Blue. J'ai mis ce défi de côté, car je n'avais pas progressé. Puis j'ai vu la réponse de Blue et l'idée simple suivante m'est venue à l'esprit: chaque bâtiment bloque un angle dans lequel rien d'autre ne peut être vu. J'ai juste besoin de garder une trace de ce qui peut être vu et de ce qui est déjà caché par d'autres bâtiments. C'est ça!

L'algorithme fonctionne comme suit: Il détermine le bâtiment avec la plus petite distance à la personne. Ensuite, nous imaginons quatre lignes tracées de la personne aux coins du bâtiment. Deux d'entre eux ont une valeur extrême: l'angle minimum et maximum sous lequel le bâtiment peut être vu. Nous les prenons comme une gamme et les comparons avec d'autres bâtiments dont nous savons qu'ils peuvent être vus (aucun au début). Les plages peuvent se chevaucher, s'inclure ou ne pas se toucher du tout. Je compare les plages et j'obtiens de nouvelles plages du bâtiment qui ne sont pas cachées par les bâtiments visibles. S'il reste quelque chose après l'avoir comparé aux bâtiments en vue, le bâtiment est également visible. Nous ajoutons la plage d'angles restante à la liste des plages à comparer et commençons par le bâtiment suivant avec la distance plus longue suivante.

Parfois, les plages peuvent se chevaucher d'une manière que je me retrouve avec une plage de 0 degrés. Ces plages seront filtrées pour ne pas ajouter par erreur un bâtiment qui n'est même pas visible.

J'espère que quelqu'un a compris cette explication :)

Je sais que ce code n'est pas beaucoup joué, je vais le faire dès que possible.

C'était une tâche vraiment difficile. Vous pensiez avoir trouvé une solution qui fonctionne, mais vous êtes encore loin. Je pense que cette solution fonctionne plutôt bien. Ce n'est pas très rapide mais au moins ça marche;) Merci pour ce puzzle!

Mise à jour

J'ai trouvé le temps de jouer au golf en une seule fonction, qui peut donc être transformée en lambda. Toutes les fonctions n'ont été appelées qu'une seule fois et peuvent donc être regroupées dans une seule méthode. Je suis passé de listes à ensembles car cela enregistre quelques caractères supplémentaires. Les déclarations ont été rassemblées. Les comparaisons ont été rassemblées et les caractères ont été remplacés par leur valeur ascii. La plage de comparaison peut être exprimée en nombre de ternaires. Quelques astuces ici et là pour empêcher les expressions longues comme Double.NEGATIVE_INFINITY ont été effectuées. Dans la mesure du possible, des affectations en ligne sont effectuées. Pour économiser un peu plus, je suis passé de la comparaison des angles en degrés à la comparaison des radians. L'ensemble du changement a sauvé plus de 500 caractères, j'espère tout de même moins de 1000;)

J'ai supprimé les génériques dans la mesure du possible et raccourci la comparaison de retour en créant un tableau à un élément et en vérifiant sa valeur à la place. J'ai également remplacé le Double.NEGATIVE_INFINITY par PI2 et -PI2 car ce sont les limites supérieures et inférieures des angles. Maintenant, c'est enfin moins de 1000 caractères!

J'ai fusionné les boucles pour trouver l'emplacement des personnes et l'itérateur du bâtiment pour enregistrer certains personnages. Malheureusement, cela nous oblige à sortir le retour de la boucle et à utiliser toujours une pause, mais cette fois sans étiquette. J'ai fusionné maxet distanceSquaredet minet newDistanceSquaredcomme ils ne sont pas requis en même temps. J'ai changé Integer.MAX_VALUEpour 2e31-1. J'ai également créé une constante half = 0.5qui est utilisée pour calculer les coins du bâtiment. C'est plus court dans la version golfée. Dans l'ensemble, nous avons enregistré 30 autres caractères!