Я нахожусь в положении (0, 0) бесконечного двумерного города, который идеально разделен на блоки, центрированные в каждой точке решетки, некоторые из которых содержат здания. Здание в определенной точке (x, y) занимает весь квадрат с противоположными углами в точках (x -.5, y-.5) и (x + .5, y + .5) , включая его границу. Здание является видимым, если существует некоторый отрезок от (0, 0) до точки в здании, которая не пересекает никакое другое здание.

Например, я (the @) могу видеть 6 зданий ( *) в следующем городе:

  *
 *
*
*@
x**
 *  y

Я не вижу здание, помеченное знаком x, в (-1, -1), потому что оно закрыто двумя соседними с ним; или тот, который отмечен символом yat (3, -2), потому что он закрыт краем здания (1, -1) .

вход

Многострочная строка или список строк, необязательно дополненный пробелами в прямоугольник. Он будет содержать только:

• сингл @(моя позиция)
• пространства
• *, которые представляют собой здания.

Всегда будет хотя бы одно здание и, следовательно, хотя бы одно видимое здание.

Выход

Количество видимых зданий.

Контрольные примеры

*@
1

* *******
 @     * 
7

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

   *
  **
@ **
2

*      *
 *    * 
@
4

@
 *
  ***
1

_{Спасибо @Geobits за название .}

Unity + C #, 589 байт

Вероятно, это худший язык для игры в гольф (читай: хуже, чем на Java), но Unity предлагает множество полезных функций для решения этой задачи.

РЕДАКТИРОВАТЬ: пропустил пару пробелов, возвращает длину списка, а не счетчик

Golfed:

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

Я использовал 3600 raycast, потому что он не прошел 5-й тестовый случай с более низким. Это все еще может потерпеть неудачу для еще больших / более точных тестовых случаев.

К сожалению, как webgl, так и настольные сборки, похоже, ломаются, поэтому все, что у меня есть, это исходный код для тестирования на github .

Java 8 лямбда, 1506 1002 972 942 знаков

Я хотел побить этот вызов, так как он очень интересный. Результат (не очень удачный) можно увидеть здесь:

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

Конечно, это также существует в негольфированной версии:

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

Так что это выглядит очень сложно, но это намного проще, чем можно подумать. Моя первая идея состояла в том, чтобы использовать некоторый алгоритм пересечения, чтобы проверить, можно ли провести линию от моей позиции до здания без каких-либо пересечений. Для этого я решил использовать алгоритм Коэна-Сазерленда и рисовать линии для всех четырех углов здания. Это сработало довольно хорошо для первых тестов, но последний провалился. Вскоре я обнаружил, что это тот случай, когда вы видите не углы, а часть края. Так что я подумал о каком-то лучевом отбрасывании, как это сделал @Blue. Я отложил этот вызов, так как не получил никакого прогресса. Затем я увидел ответ Блю, и мне пришла в голову следующая простая идея: каждое здание блокирует некоторый угол, в котором больше ничего не видно. Мне просто нужно следить за тем, что можно увидеть и что уже скрыто другими зданиями. Это оно!

Алгоритм работает следующим образом: он определяет здание с наименьшим расстоянием до человека. Затем мы представляем четыре линии, проведенные от человека к углам здания. Два из них имеют экстремальное значение: минимальный и максимальный угол обзора здания. Мы берем их в качестве диапазона и сравниваем их с другими зданиями, о которых мы знаем, что их можно увидеть (ни одного в начале). Диапазоны могут перекрываться, включать друг друга или вообще не касаться. Я сравниваю диапазоны и получаю новые диапазоны зданий, которые не скрыты видимыми зданиями. Если после сравнения зданий и сооружений в поле зрения остается что-то, здание также можно увидеть. Мы добавляем оставшийся диапазон углов в список диапазонов для сравнения и начинаем со следующего здания со следующим более длинным расстоянием.

Иногда диапазоны могут перекрываться таким образом, что я получаю диапазон 0 градусов. Эти диапазоны будут отфильтрованы, чтобы по ошибке не добавить здание, которое даже нельзя просмотреть.

Я надеюсь, что кто-то понял это объяснение :)

Я знаю, что этот код не очень хороший, я сделаю это как можно скорее.

Это была действительно сложная задача. Вы думали, что нашли решение, которое работает, но вместо этого вы все еще далеко. Я думаю, что это решение работает довольно хорошо. Это не очень быстро, но, по крайней мере, это работает;) Спасибо за эту загадку!

Обновить

Я нашел время для игры в гольф в единую функцию, которую можно превратить в лямбду. Все функции были вызваны только один раз и поэтому могут быть объединены в один метод. Я переключился со списков на наборы, так как это сохраняет некоторые дополнительные символы. Декларации были составлены. Сравнения были собраны вместе, и символы были заменены на значение ascii. Диапазон сравнения можно выразить как множество троичных. Некоторые приемы для предотвращения длинных выражений типа Double.NEGATIVE_INFINITY были сделаны. Где возможно встроенные назначения сделаны. Чтобы сэкономить немного больше, я переключился со сравнения углов в градусах на сравнение радианов. Все изменения сэкономили более 500 символов, но я надеюсь получить все до 1000, хотя;)

Я удалил обобщения, где это было возможно, и сократил возвращаемое сравнение, создав массив из одного элемента и проверив его значение. Я также заменил Double.NEGATIVE_INFINITY на PI2 и -PI2, так как это верхняя и нижняя границы углов. Теперь это наконец менее 1000 символов!

Я объединил циклы поиска местоположения людей и итератор здания, чтобы сохранить некоторые символы. К сожалению, это требует, чтобы мы переместили возврат из цикла и все еще использовали разрыв, но на этот раз без метки. Я слил maxи distanceSquaredи так minи так newDistanceSquaredкак они не требуются одновременно. Я изменился Integer.MAX_VALUEна 2e31-1. Также я создал константу, half = 0.5которая используется для вычисления углов здания. Это короче в версии для гольфа. В целом мы сохранили еще 30 символов!