Jestem na pozycji (0, 0) nieskończonego dwuwymiarowego miasta, które jest doskonale podzielone na bloki wyśrodkowane w każdym punkcie sieci, z których niektóre zawierają budynki. Budynek w pewnym punkcie (x, y) zajmuje cały kwadrat z przeciwległymi narożnikami w (x-.5, y-.5) i (x + .5, y + .5) , łącznie z jego granicą. Budynek jest widoczny, jeśli jest jakiś segment linii od (0, 0) do punktu w budynku, który nie przecina żadnego innego budynku.

Na przykład I (the @) widzę 6 budynków ( *) w następującym mieście:

  *
 *
*
*@
x**
 *  y

Nie widzę budynku oznaczonego x, w (-1, -1), ponieważ jest on zasłonięty przez dwa sąsiadujące z nim budynki ; lub ten oznaczony yat (3, -2), ponieważ jest on zasłonięty przez krawędź budynku (1, -1) .

Wejście

Ciąg wielowierszowy lub lista linii, opcjonalnie wypełnione spacjami w prostokącie. Będzie zawierać tylko:

• singiel @(moja pozycja)
• Przestrzenie
• *, które reprezentują budynki.

Zawsze będzie co najmniej jeden budynek, a zatem co najmniej jeden widoczny budynek.

Wynik

Liczba widocznych budynków.

Przypadki testowe

*@
1

* *******
 @     * 
7

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

   *
  **
@ **
2

*      *
 *    * 
@
4

@
 *
  ***
1

_{Dzięki @Geobits za tytuł .}

Unity + C #, 589 bajtów

Jest to prawdopodobnie najgorszy język do gry w golfa kodowego (czytaj: gorszy niż Java), ale Unity ma wiele przydatnych funkcji do tego wyzwania.

EDYCJA: pominięto kilka spacji, zwraca długość listy, a nie licznik

Gra w golfa:

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

Nie golfowany:

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

Użyłem 3600 raycastów, ponieważ zawiodło w piątym przypadku testowym z niższym. Nadal może zawieść w przypadku jeszcze większych / bardziej precyzyjnych przypadków testowych.

Niestety zarówno kompilacje webgl, jak i pulpity wydają się nie działać, więc mam tylko kod źródłowy do przetestowania na github .

Java 8 lambda, 1506 1002 972 942 znaków

Chciałem pokonać to wyzwanie, ponieważ jest bardzo interesujące. Wynik (niezbyt golfowy) można zobaczyć tutaj:

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

Oczywiście istnieje to również w wersji bez golfa:

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

Wygląda więc bardzo trudno, ale jest o wiele łatwiej, niż mogłoby się wydawać. Moim pierwszym pomysłem było użycie jakiegoś algorytmu skrzyżowania, aby sprawdzić, czy linia od mojej pozycji do budynku może być utworzona bez żadnych skrzyżowań. Aby to zrobić, zdecydowałem się użyć algorytmu Cohena-Sutherlanda i narysować linie do wszystkich czterech narożników budynku. To działało całkiem dobrze w pierwszych testach, ale ostatni nie powiódł się. Wkrótce przekonałem się, że jest to przypadek, w którym nie widać rogów, ale część krawędzi. Pomyślałem więc o jakimś castingu promieniowym, takim jak @Blue. Odłożyłem to wyzwanie, ponieważ nie osiągnąłem żadnego postępu. Potem zobaczyłem odpowiedź Blue i przyszedł mi do głowy następujący prosty pomysł: każdy budynek blokuje pewien kąt, pod którym nic więcej nie widać. Muszę tylko śledzić, co można zobaczyć i co jest już ukryte przez inne budynki. Otóż ​​to!

Algorytm działa w następujący sposób: Określa budynek z najmniejszą odległością od osoby. Następnie wyobrażamy sobie cztery linie narysowane od osoby do narożników budynku. Dwa z nich mają ekstremalną wartość: minimalny i maksymalny kąt, pod którym można zobaczyć budynek. Bierzemy je jako zasięg i porównujemy z innymi budynkami, o których wiemy, że można je zobaczyć (żaden na początku). Zakresy mogą się nakładać, obejmować lub nie dotykać. Porównuję zakresy i otrzymuję nowe zakresy budynku, które nie są ukryte przez widoczne budynki. Jeśli po porównaniu z budynkami pozostanie coś jeszcze, budynek będzie również widoczny. Dodajemy pozostały zakres kątów do listy zakresów, aby porównać i zacząć od następnego budynku o następnej większej odległości.

Czasami zakresy mogą się pokrywać w taki sposób, że kończę na zakresie 0 stopni. Te zakresy zostaną przefiltrowane, aby nie pomyłkowo dodać budynku, który nawet nie jest widoczny.

Mam nadzieję, że ktoś zrozumiał to wytłumaczenie :)

Wiem, że ten kod nie jest bardzo golfowy, zrobię to jak najszybciej.

To było naprawdę trudne zadanie. Myślałeś, że znalazłeś rozwiązanie, które działa, ale zamiast tego wciąż jesteś daleko. Myślę, że to rozwiązanie działa całkiem dobrze. Nie jest bardzo szybki, ale przynajmniej działa;) Dzięki za tę łamigłówkę!

Aktualizacja

Znalazłem czas na grę w golfa w jedną funkcję, którą w ten sposób można przekształcić w lambdę. Wszystkie funkcje zostały wywołane tylko raz, dzięki czemu można je umieścić w jednej metodzie. Przełączyłem się z list na zestawy, ponieważ oszczędza to dodatkowe znaki. Deklaracje zostały zebrane razem. Porównania zostały zebrane, a postacie zastąpiono wartością ascii. Porównywanie zasięgu można wyrazić jako wiele trójskładników. Kilka sztuczek tu i tam, aby zapobiec długim wyrażeniom, takim jak Double.NEGATIVE_INFINITY. Tam gdzie to możliwe, wykonywane są przypisania liniowe. Aby zaoszczędzić trochę więcej, przerzuciłem się z porównywania kątów w stopniach na porównywanie radianów. Cała zmiana pozwoliła zaoszczędzić ponad 500 znaków, ale mam nadzieję, że uda się uzyskać wszystko poniżej 1000;)

Tam, gdzie to możliwe, usunąłem ogólne i skróciłem porównanie zwrotów, tworząc tablicę z jednym elementem i sprawdzając zamiast tego jej wartość. Zamieniłem również Double.NEGATIVE_INFINITY na PI2 i -PI2, ponieważ są to górne i dolne granice kątów. Teraz ma w końcu mniej niż 1000 znaków!

Połączyłem pętle w celu znalezienia lokalizacji osób i iteratora budynku, aby zapisać niektóre postacie. Niestety wymaga to od nas wycofania powrotu z pętli i nadal skorzystania z przerwy, ale tym razem bez etykiety. I połączyły maxi distanceSquareda mini newDistanceSquaredtak nie są one wymagane w tym samym czasie. Zmieniłem się Integer.MAX_VALUEna 2e31-1. Stworzyłem również stałą, half = 0.5która służy do obliczania narożników budynku. Jest to krótsze w wersji golfowej. Ogółem ocaliliśmy kolejne 30 znaków!