Ich befinde mich an der Position (0, 0) einer unendlichen zweidimensionalen Stadt, die perfekt in Blöcke unterteilt ist, die an jedem Gitterpunkt zentriert sind, von denen einige Gebäude enthalten. Ein Gebäude an einem bestimmten Punkt (x, y) nimmt das gesamte Quadrat mit gegenüberliegenden Ecken bei (x-.5, y-.5) und (x + .5, y + .5) einschließlich seiner Begrenzung ein. Ein Gebäude ist sichtbar, wenn es ein Liniensegment von (0, 0) zu einem Punkt im Gebäude gibt, der kein anderes Gebäude schneidet.

Zum Beispiel kann ich (die @) 6 Gebäude ( *) in der folgenden Stadt sehen:

  *
 *
*
*@
x**
 *  y

Ich kann das Gebäude, das mit einem x, bei (-1, -1) markiert ist, nicht sehen , da es von den beiden angrenzenden Gebäuden blockiert wird. oder die mit einem ybei (3, -2) markierte , weil sie durch den Rand des (1, -1) Gebäudes blockiert ist.

Eingang

Eine mehrzeilige Zeichenfolge oder Liste von Zeilen, die optional mit Leerzeichen in einem Rechteck aufgefüllt werden. Es wird nur enthalten:

• eine einzelne @(meine Position)
• Räume
• *, die Gebäude darstellen.

Es wird immer mindestens ein Gebäude geben und daher mindestens ein sichtbares Gebäude.

Ausgabe

Die Anzahl der sichtbaren Gebäude.

Testfälle

*@
1

* *******
 @     * 
7

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

   *
  **
@ **
2

*      *
 *    * 
@
4

@
 *
  ***
1

_{Vielen Dank an @Geobits für den Titel .}

Einheit + C #, 589 Bytes

Dies ist wahrscheinlich die schlechteste Sprache, in der man Codegolf spielen kann (lesen Sie: schlechter als Java), aber Unity bietet viele hilfreiche Funktionen für diese Herausforderung.

BEARBEITEN: Einige Leerzeichen verpasst, Länge der Liste zurückgegeben, kein Zähler

Golf gespielt:

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

Ich habe 3600 Raycasts verwendet, weil es den 5. Testfall mit niedrigerem nicht schafft. Bei noch größeren / genaueren Testfällen kann es immer noch scheitern.

Leider scheinen sowohl Webgl- als auch Desktop-Builds zu brechen. Ich habe also nur den Quellcode, mit dem ich auf Github testen kann .

Java 8 Lambda, 1506 1002 972 942 Zeichen

Ich wollte diese Herausforderung bestehen, da sie sehr interessant ist. Das Ergebnis (nicht sehr golfen) ist hier zu sehen:

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

Natürlich gibt es das auch in der 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;
    }
}

Es sieht also sehr schwierig aus, ist aber viel einfacher als man denkt. Meine erste Idee war, mit einem Kreuzungsalgorithmus zu prüfen, ob eine Linie von meiner Position zum Gebäude ohne Kreuzungen hergestellt werden kann. Zu diesem Zweck habe ich mich für den Cohen-Sutherland-Algorithmus entschieden und Linien zu allen vier Ecken des Gebäudes gezogen. Dies hat bei den ersten Tests ziemlich gut funktioniert, aber der letzte ist fehlgeschlagen. Ich habe schnell herausgefunden, dass man die Ecken nicht sehen kann, sondern nur einen Teil einer Kante. Also dachte ich über eine Art Raycasting nach, wie es @Blue gemacht hat. Ich habe diese Herausforderung weggeräumt, da ich keine Fortschritte gemacht habe. Dann sah ich die Antwort von Blue und die folgende einfache Idee kam mir in den Sinn: Jedes Gebäude blockiert einen Winkel, in dem nichts anderes zu sehen ist. Ich muss nur verfolgen, was zu sehen ist und was bereits von anderen Gebäuden verborgen wird. Das ist es!

Der Algorithmus funktioniert wie folgt: Er ermittelt das Gebäude mit der geringsten Entfernung zur Person. Dann stellen wir uns vier Linien vor, die von der Person zu den Ecken des Gebäudes gezogen werden. Zwei davon haben einen extremen Wert: Der minimale und maximale Winkel, in dem das Gebäude gesehen werden kann. Wir nehmen sie als eine Reihe und vergleichen sie mit anderen Gebäuden, von denen wir wissen, dass sie zu sehen sind (keine am Anfang). Die Bereiche können sich überlappen, sich gegenseitig einschließen oder sich überhaupt nicht berühren. Ich vergleiche die Bereiche und erhalte einige neue Bereiche des Gebäudes, die von den sichtbaren Gebäuden nicht verborgen werden. Wenn nach dem Vergleich mit den sichtbaren Gebäuden noch etwas übrig ist, kann das Gebäude auch angezeigt werden. Wir fügen den verbleibenden Winkelbereich der Liste der Bereiche hinzu, die mit dem nächsten Gebäude mit der nächstgrößeren Entfernung verglichen und mit diesem begonnen werden sollen.

Manchmal überlappen sich die Bereiche so, dass ich einen Bereich von 0 Grad erhalte. Diese Bereiche werden gefiltert, um nicht versehentlich ein Gebäude hinzuzufügen, das nicht einmal sichtbar ist.

Ich hoffe jemand hat diese erklärung verstanden :)

Ich weiß, dass dieser Code nicht sehr gut ist. Ich mache das so schnell wie möglich.

Das war eine wirklich herausfordernde Aufgabe. Sie dachten, Sie hätten eine Lösung gefunden, die funktioniert, sind aber noch weit entfernt. Ich denke, diese Lösung funktioniert ziemlich gut. Es ist nicht sehr schnell, aber es funktioniert zumindest;) Danke für das Rätsel!

Aktualisieren

Ich fand die Zeit, das Ganze in eine einzige Funktion zu verwandeln, die sich so in einen Lambda verwandeln lässt. Alle Funktionen wurden nur einmal aufgerufen und können somit in einer Methode zusammengefasst werden. Ich habe von Listen zu Sets gewechselt, da hierdurch einige zusätzliche Zeichen eingespart werden. Die Erklärungen wurden zusammengestellt. Die Vergleiche wurden zusammengestellt und die Zeichen durch ihren ASCII-Wert ersetzt. Der Bereichsvergleich kann als viele Ternären ausgedrückt werden. Hier und da ein paar Tricks, um lange Ausdrücke wie Double.NEGATIVE_INFINITY zu verhindern. Wo möglich werden Inline-Zuordnungen vorgenommen. Um etwas mehr zu sparen, habe ich vom Winkelvergleich in Grad auf den Bogenmaßvergleich umgestellt. Die ganze Änderung sparte über 500 Zeichen, ich hoffe, dass ich alles unter 1000 bekomme;)

Ich habe die Generika entfernt und den Rückgabevergleich verkürzt, indem ich ein Array mit einem Element erstellt und stattdessen dessen Wert überprüft habe. Ich habe auch Double.NEGATIVE_INFINITY durch PI2 und -PI2 ersetzt, da dies die oberen und unteren Grenzen der Winkel sind. Jetzt ist es endlich unter 1000 Zeichen lang!

Ich habe die Schleifen zum Finden des Orts der Person und des Gebäude-Iterators zusammengeführt, um einige Zeichen zu speichern. Leider müssen wir dafür den Return aus der Schleife verschieben und trotzdem eine Pause verwenden, diesmal jedoch ohne Label. Ich habe maxund distanceSquaredund minund zusammengeführt, newDistanceSquaredda sie nicht gleichzeitig benötigt werden. Ich wechselte Integer.MAX_VALUEzu 2e31-1. Außerdem habe ich eine Konstante erstellt half = 0.5, mit der die Ecken des Gebäudes berechnet werden. Dies ist in der Golfversion kürzer. Insgesamt haben wir weitere 30 Zeichen gespeichert!