Ответы пользователя по тегу JavaScript
  • Когда использовать ООП?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    ООП - это не только, когда вы берете какие-то сущности из предметной области и оборачиваете каждую в объект, который что-то умеет делать. Это больше подход к организации кода. Вы делите задачу на подзадачи, а данные на обособленные части, абстрагируете детали внутри объектов. Это позволяет снижать сложность архитектуры. Теоретически любую программу можно написать внутри одной огромной функции с кучей goto. Но так никто не делает, потому что это невозможно поддерживать и невероятно сложно написать. ООП - это логическое продолжение процедур. Теперь вы не только какие-то части программы абстрагируете в одном месте, но теперь еще и данные вмести с ними.

    Мне нужен объект, который будет хранить состояние/данные, и есть общие операции над этим состоянием?


    Вопрос: что значит нужен? Всегда можно взять глобальную переменную, написать функции, которые это состояние принимают и что-то с ним делают. Но довольно часто организация в виде объекта просто удобнее.
    Ответ написан
  • Как перенести строку в двумерном массиве, если количество элементов больше определенного количества?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Тут не важно, что массив двумерный. Фактически, вам надо вывести один массив символов с переносами. Только надо решить эту задачу отдельно для каждой строки двумерного массива.

    Самое простое решение - в цикле вывода символов выводить '\n', если текущий символ 20-ый, 40-ой и т.д. Например, можно проверять (i+1) % 20 == 0.
    Ответ написан
  • Содержит ли массив определенные числа?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вариант простой - перебрать все участки 3x3 (смотрите левый верхний угол - это 2 цикла от 0 до width-3 и от 0 до height-3) и проверить, что они хорошие.

    Для проверки можно или 1) проверить, что все числа от 1 до 9 и разные, или 2) проверить, что там ровно один раз каждая из цифр встречается. Второй вариант короче и быстрее, но для него вам придется завести массив счетчиков от 0 до 9. Перед каждой проверкой он занулен. Обойдите ваш 3x3 блок и увеличьте соответствующий счетчик (что-то типа count[a[beg_x+i][beg_y+j]]++). Только не забудьте проверить, что число от 1 до 9, чтобы не вылезать за границы массива. Потом пройдитесь по массиву счетчиков циклом от 1 до 9 и проверьте, что там везде стоят единицы.
    Ответ написан
  • Можно ли как-то оптимизировать/ускорить этот код?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Как я уже писал в другом вопросе - вам не нужны касательные из каждой точки на все полигоны. Нужны лишь общие касательные к каждой паре полигонов. Если полигоны не пересекаются, то таких всего 4 штуки. Если же они пересекаются, то их может быть сколько угодно.

    Как-то сильно ускорить мне не удалось, но можно брать каждую точку одного полигона, строить 2 касательные на другой полигон и оставлять только те, которые одновременно являются касательными к первому полигону.
    Это проверяется через векторные произведения веторов-сторон и вектора отрезка между полигонами. Отрезок между полигонами должен быть между двумя векторами сторон (если они ориентированны в одну сторону, скажем, против часовой стрелки). Это должно уже в почти в 4 раза уменьшить количество отрезков у вас.

    Еще, возможно, тут проблема не в касательных. Вот у вас 20 полигонов, в каждом по 8 точек - это 160 точек начал. Для нахождения касательных к полигону можно перебрать все вершины. Это еще раз по 20*8=160. Итого, получается 160^2=25600 операций. Операции сложные (найти 3 вектора, взять векторные произведения), да. Но жаже если умножить это на 50, получается 1,280,000 элементарных операций. Современные процессоры выполняют миллиарды таких операций в секунду. Т.е по этой грубой прикидке - построение всех касательных занимает считанные миллисекунды.

    У вас очень тормозит проверка на пересечения возможных кандидатов с полигонами.
    Во-первых, как только вы нашли пересечение - можно дальше не проверять. Разделите циклы по intersect_any_1 и intersect_any_2 и останавливайтесь, как только нашли пересечение. Во-вторых, вы для каждой касательной заново строите объекты turf.js. Это, возможно, очень медленно.

    Ну и, похоже turf.js слишком тормозной. Моя демка на C++ для 100 полигонов находит все хорошие касательные без пересечений за 30мс. А если отсекать полигоны по bounding box, то 16-20мс. Ну в 10 раз javascript медленнее. У вас явно что-то совсем не то делается где-то.
    Ответ написан
  • Как реализовать поиск в глубину не рекурсией и если много кольцевых связей?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Если рекурсия валится, то делайте не обход в глубину, а обход в ширину (с очередью).
    Ответ написан
  • Как перебрать из массива до тех пор, пока совпадают даты?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Во-первых, массив надо отсортировать по датам, если он у вас уже не упорядочен. В любом языке программирования есть какая-то функция sort(), которой можно как-то задать, как сравнивать сортируемые объекты (тут вам надо сравнивать только даты).

    Ваше условие не очень понятно, но вот, как сгрупировать массив по датам:
    st = 0; 
    end = 0;
    while (st < a.length) {
      end = st + 1;
      while(end < a.length && a[end].date == a[end-1].date) end++;
      console.log(a[st].date);
      for (st = st; st < end; st++) {
        console.log(a[st].id);
      }
    }


    Тут мы просто откусываем от массива кусок с одинаковыми датами, пока массив не кончится. Если вам нужна только последняя группа, то можно откусить только один раз с конца:
    end = a.length - 1;
    st = end - 1;
    while (st >= 0 && a[st].date == a[st+1].date) st--;
    console.log(a[end].date);
    for (st = st+1; st <= end; ++st) 
      console.log(a[st].id);


    Только учтите, этот код не работает на пустом массиве. Надо отдельно проверить этот случай.
    Ответ написан
  • Как получить ветвь дерева?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Если, как у вас в примере, вам дан текст с отступами, то можно делать так:

    Читайте построчно и разбивайте строку на число и сколько пробелов перед ним стоит.
    Заведите массив, в котором будете хранить "активных" предков для всех уровней.
    Перезаписывайте значение по индексу "сколько пробелов в начале строки".
    При нахождении вашего искомого индекса выводите этот массив (до текущего числа)
    Фактически, этот массив - это стек в котором вы храните текущую ветвь.

    Вот пример:
    1
     2
     3
      4


    Допустим, вам нужны предки для id=4.
    Прочли "1". Массив {1,0,0...}. Прочли " 2". Массив {1, 2, 0...}. Прочли " 3". Массив {1, 3, 0...}. Прочли " 4". Массив стал {1, 3, 4}. 4 - искомый элемент выводим ветку 1-3-4.

    Если у вас отступы длины 2, то делите количество пробелов на 2 для получения индекса. Или у вас там могут быть символы табуляции - считайте их. Решение не работает, если формат не постоянен и разные уровни могут иметь разные отступы. Но тут можно считать текущую глубину. Надо так же в массиве хранить сколько пробелов в начале каждого уровня. Если новая строка имеет больше отступов, чем строка на текущем уровне, то увеличиваем глубину и кладем строку в массив. Если имеет меньше, то уменьшаем глубину, пока отступы не станут такими же, как и у строки на этом уровне.

    Если надо делать эту операцию быстро и много раз, то лучше один раз переведите эту строковую запись в настоящее дерево, со ссылками на родителя для каждого id: каждый раз при записи id в массив делайте ссылку на предыдущий id в массиве, как родителя.
    Ответ написан
  • Как реализовать алгоритм преследования игрока с учётом препятствий-полигонов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Если боты должны обходить полигоны на каком-то расстоянии (не могут их касаться, как у вас на картинке), то раздуйте все полигоны на этот радиус (для каждой вершины найдите 2 внешние нормали к соседним сторонам, сдвиньте стороны на r вдоль этих нормалей и пересеките). Можно вывести формулу на бумажке через косинусы/синусы между нормалями (т.е. векторное/скалярное произведения нормалей). Надо будет к точке прибавить обе нормали, умноженные на 1/(cos(a/2)*sqrt(2+2cos(a))), где a - угол между нормалями.

    Теперь можно считать ботов точками и они могут касаться полигонов.

    Постройте граф. Вершины в графе - вершины полигонов, боты и игрок. Для каждой вершины и другого полигона найдите 2 касательные с точки на полигон - можно перебрать все отрезки из вершины на другой полигон и отбросить те, относительно которых 2 стороны второго многоугольника лежат по разные стороны. Также все эти касательные проверьте на пересечение со всеми остальными полигонами и удалите те, которые пересекаются (проверьте каждую сторону полигона, и пересеките сторону с известным отрезком-касательной).

    Теперь у вас остались только касательные, по которым имеет смысл ходить. Добвьте их в граф (длины ребер равны длине отрезков).
    Также добавьте в граф все ребра многоугольников. Все кратчайшие пути мужду всеми точкаим идут в этом графе. Вы или идете вдоль полигона, или идете из текущей точки по касательной к какому-то полигону. Очевидно, что это любой другой путь можно улучшать, пока он не станет состоять из этих кусков.

    Теперь, для каждого бота и игрока сделайте то же самое - постройте касательные на все многоугольники, удалите те, которые пересекаются с другими полигонами. Также добавтье прямые пути игрок-бот, если нет пересечений с полигонами. В этом графе нужно найти кратчайшие пути (лучше Дейкстрой от игрока до всех ботов).

    Обход других ботов делается так - у ботов есть подсчитанные пути. Боты пытаются сделать маленькие шаги вдоль пути. Если они пересекаются с другим ботом, то можно пропустить ход, или попытаться толкнуть другого бота. Расствьте ботам случайные приоритеты и, если бот с большим приоритетом хочет пересечься с ботом с меньшим приоритетом, то второй делает шаг назад.

    Они будут толпиться в узких проходах, но в итоге выстроятся шеренгой и пойдут друг за другом. Но это если игрок один. Тогда боты идут в одну сторону. Если они могут ходить против друг друга, то будет хуже. Они могут запереть друг друга в узком проходе и долго выталкивать друг друга.

    Теперь - пересчет при движении игрока. Переодически надо пересчитывать пути для ботов. Для этого надо перестроить касательные от игрока и ботов на полигоны и снова прогнать Дейкстру.

    Теперь про скорость. Можно делать просто, как я описал выше. Все что надо - это уметь проверять, что 2 отрезка пересекаются, и что полигон лежит по одну сторону от луча. Ну и алгоритм Дейкстры.

    Касательные между препятствиями вы строите только один раз, тут скорость не так важна. Хуже с точками ботами и игроком. Тут касательные надо искать часто. Если полигоны очень большие, то можно искать точки пересечения и касательные за логарифм, но это очень заумные алгоритмы, через троичный поиск. Могу потом написать, если надо.

    Самое медленное, это для каждой касательной проверять на пересечения со всеми полигонами (это n^2 проверок, если у вас n полигонов). Тут можно тоже очень хитро ускорить до n log n проверок, если все касательные отсортировать по углу и потом сделать что-то вроде алгоритма заметающей прямой, но вращать ваш взгляд вокруг точки. Это совсем сложно даже описать, не говоря уж о реализации. Надо складывать полигоны в что-то вроде сбалансированного дерева поиска, которое будет поддерживать их в отсортированном порядке относительно расстояния до точки. Каждая касательная или добавляет полигон, или удаляет его. Вы добавляете касательную только если при добавлении или удалении полигона он был самым ближайшим. Тут нужно будет уметь определять расстояние от точки до полигона вдоль прямой. Опять же, можно сделать тернарным поиском по точкам полигона.

    Еще есть вариант через BSP (как в Думe. Дейстивительно эта задача, фактически, узнать, какие полигоны видны из любой точки. Очень близкро к компьютерной графике). Надо разбить всю плоскость на области и для каждой области хранить, на какие полигоны есть касательные из нее. Для этого надо все стороны полигонов продлить до прямых. Все со всем персечь, выделить области. Потом для любой точки в каждой области построить касательные и сохранить. Потом все эти области объеденить в BSP. Это очень хорошее ускорение, но оно работет только если у вас карта статичная. Можно предподсчитать и записывать в файл уже BSP.

    Поиск пути в графе тоже можно подускорить. Без добавления ботов и игрока в граф найдите все кратчайшие пути методом Флойда. Теперь, когда вы построили все касательные, для каждого бота переберите касательную его и касательную из игрока. Вы можете моментально подсчитать кратчайший путь через эти касательные, ведь часть пути внутри графа на полигонах уже предподсчитана из алгоритма Флойда. Это будет заметно быстрее, чем гнать дейкстру каждый раз, ибо касательныйх сильно меньше, чем вершин всего в графе.
    Ответ написан
  • Как определить наличие разрыва рисунка?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Алгоритм обхода в ширину или в глубину. Еще его называют алгоритм заливки. Гуглите. Если за одну заливку вы закрасили все черные пиксели, то фигура одна. Иначе, если компонент взязности несколько - разрыв есть.
    Ответ написан
  • Найти алгоритм подсчета количеств множественного перекрытия интервалов, а также длительность таких интервалов?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Мне лень разбираться в вашем коде. Вот правильное решение:

    Для всех интервалов добавить в массив точек пары {время начала, +1} и {время конца+1, -1}. Это массив точек - границ вакансий на оси времени (прибавляем 1 к времени конца, потому что последняя секунда включена в интервал). Потом сортируем этот массив. Теперь одиним проходом можно выделить из массива все отрезки времени и сколько на них было открыто вакансий.

    Для этого заведите счетчик, изначально равный нулю и пройдитесь по массиву прибавляя текущее второе значение в парек счетчику в конце цикла.
    Перед этим, если текущая точка лежит правее предыдущей, то отрезок от предыдущей точки до текущей имеет ровно столько открытых вакансий, сколько записано в счетчике.

    Для простоты советую сначла одним циклом выделить все отрезки и сложить их в отдельный массив (опять пара - длина отрезка, количество вакансий). Потом пройтись по массиву (или во время складывания) найти максимальное количество вакансий. Потом пройтись еще раз и просуммировать времена для всех отрезков с данным количеством вакансий.

    Еще можете посмотреть предыдущий ответ вашему товарищу по курсу: В чем ошибка в алгоритме поиска количества интервалов?
    Ответ написан
  • Как преобразовать слова?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Ответ "можно" если
    1) Каждому символу первой строки соответствует один и тот же символ второй строки
    2) Если есть замены в виде цикла (вроде а->б, б->в, в->а), то нужна хотя бы одна свободная буква (та, которая не стоит справа в замене).

    Решается так:
    1) Проверить, что строки равны. Это особый случай
    2) Проверить, что длина одинаковая?
    3) Завести мап символ->символ, пройтись по строкам параллельно и записывать мап[строка1[i]] = строка2[i], если там пусто. Иначе - проверить, что там уже записано то же самое.
    4) Проверить, что различных символов во второй строке меньше 33. Можно с помощью сета, который наполняется в том же цикле, что и в шаге 3.
    Ответ написан
  • Как с помощью регулярного выражения определить регистр?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Подсказка: все большие буквы подпадают под "[A-Z]" (надеюсь, вопрос не про русский язык?). Теперь вам надо проверить, есть ли в строке хоть одна буква подпадающая под эту регулярку.
    Ответ написан
  • Создать массив строк случайной длины из предложенных строк?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Нужен генератор случайных чисел. в JS есть Math.random();

    Далее, чтобы сгенерировать один массив пройдитесь по всему массиву строк и добавляйте текущую строку к ответу, если random() < kThreshold. kThreshold подбирайте исходя из того, какой длины вам нужны случайные массивы. В среднем в ответе будет kThreshold*array.length() элементов. Т.е. при kThreshold=0.5, в среднем сгенерированные массивы будут содержать по половине всех строк.

    Минус этого метода, что чаще всего сгенерированные массивы будут средней длины. Массив из всех строчек или из одной единственной строчки будут маловероятны, но это может и не минус - зависит от того, зачем вам это надо.
    Ответ написан
  • Наиболее подходящий алгоритм для поиска цены?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Чтобы сделать бинарный поиск, вам нужен массив объектов с ценами и названиями. Что-то вроде
    [1=>{cost:1, name:"name1"} .... 117=>{cost:55233, name:"name555"}]
    (не уверен, что правильно описал на js).

    Но, по идее, все нормальные языки умеют что-то вроде lower_bound для ассоциативных массивов. Именно эту функцию и надо вызвать. А дальше выбрать лучший из текущего и предыдущего или следующего элемента (в зависимости, как в вашем языке lower_bound работает).

    Можно поискать какие-нибудь js библиотеки с нормальным ассоциативным массивом, который это умеет.
    Будет также работать за логарифм.
    Ответ написан
  • Где у меня ошибка?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Проблема в том, что числа повторений в задаче ОЧЕНЬ большие.
    Правильное решение должно не строить строку, а хранить ее в виде пар (символ, количество), как в RLE.
    Самое быстрое решение - хранить список таких пар (или 2 списка). Но проще, и должно проходить по времени другое решение: Можно просто хранить массив этих пар (или 2 массива, один для символов, другой - для количества повторения).

    Позиция курсора тут будет храниться двумя числами - в какой группе в массиве он сейчас и где он внутри группы. При перемещении сначала увеличьте или уменьшите позицию внутри группы. Если стало -1 или слишком большим, то переходите к следующей или предыдущей группе. Если таких нет, откатывайтесь на границу.

    При вставке надо разбить текущую группу на 2 (если вы не на границе между группами) и добавить новую группу. Это вставка в центр массива двух элементов. Не знаю, как это на js реализуется, но точно можно. На худой конец, вставляете пустые элементы в конец массива и перемещаете нужные элементы на 1-2 позиции циклом с конца к началу. Но скорее всего, есть какая-то встроенная конструкция.

    Есть оптимизация - если вставляемый символ такой же, как текущая группа (или предыдущая, если вы на границе), то просто прибавляйте новое количество к повторениям в группе.

    В конце нужно для каждой позиции пройтись по массиву групп, пока не отсчитаете нужное количество символов. Если слишком медленно, то можно M чисел отсортировать и потом одним проходом по массиву групп с указателем в массиве запросов найти все ответы (если текущая позиция-запрос левее текущей группы, переходим к следующей позиции, если текущая позиция в текущей группе - мы нашли ответ).
    Ответ написан
  • Как понять и реализовать битовую карту?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    | - это побитовое ИЛИ. & - побитовое И. Т.е. каждый разряд отдельно обрабатывается и, в случае ИЛИ, если хоть одно число имеет единицу в данном разряде, то и результат будет 1. Соответственно, 00001 | 00010 = 00011.

    Степени двойки - это числа, где единица стоит только в одном бите. Если несколько таких чисел про-ИЛИ-ть - то получится число, где стоят единицы во всех нужных разрядах. Фактически, вы назначаете каждому состоянию свой разряд. Потом, где в числе стоят единицы - те состояния и есть.

    Чтобы проверить, что бит в числе установлен, надо взять побитовое И и убедиться, что результат не 0 (он может быть либо 0 либо какой-то степенью двойки.
    Ответ написан
  • Как перемешать массив одинаково для всех?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Вот алгоритм для перемешивания массива, если у вас есть детерминированная функция rand(), которую вы каким-то seed проинициализровали.
    for (i = 1; i<arr.length; ++i) {
     let j = floor(rand()*(i+1));
     let tmp = arr[i];
     arr[i] = arr[j];
     arr[j] = tmp;
    }


    Можно использовать что-то вроде функции, предложенной twobomb, но именно той функцией пользоваться не советую - она выдаст максимум 67 различных вариантов, а на самом деле сильно меньше. Используйте, например, параметры отсюда:
    function rand(){
     	seed = (16,807*seed) % 2,147,483,647;
     	return seed/2,147,483,647;
    }
    Ответ написан
  • Предложение алгоритма решения тестового задания?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, гуглер, экс-олимпиадник.
    Ваше решение не работает на примере "аб аа".

    Надо чтобы разные или одинаковые буквы были на тех же местах в обоих словах. Вы же проверяете только, то нет такого, что в первом слове буквы равны, а во втором - нет. Надо еще проверять и наоборот.

    Но в ваше решение еще не рассматривает крайний случай - использованы все 33 буквы алфавита и есть надо что-то менять. Тут ответ 0, потому что замены делать никак не получится - после любой замены 2 разные типа букв станут одинаковыми и перемешаются. Разделить их после этого уже не получится.

    Если вы эти косяки исправите, ваше решение может не пройти по времени, потому что оно у вас за квадрат. Лучшее решение - пройтись по строкам одновременно одним циклом и запоминать в массиве, индексированном символами, (или мапе), какая буква алфавита во втором слове соответствует букве алфавита в первом слове. Если встречаете противоречие (в массиве уже что-то записано не такое как вы видите сейчас), то ответ 0.

    И еще. Не надо разбивать строки через .split(''). В JavaScript можно узнать длину строк и обратиться к i-ому символу не преобразуя в массив.
    Ответ написан
  • Комбинаторика в Java Script, как добавить точку во всех возможных комбинациях массива?

    wataru
    @wataru
    Разработчик на С++, гуглер, экс-олимпиадник.
    Делайте рекурсивную функцию, которая решает вашу задачу. Если символ на входе 1 - просто его и возвращает. Если входных символов несколько - то откусывает последний символ и вызывается рекурсивно, потом к возвращенному массиву к каждому элементу дописывает последний символ и точку-последний символ (новый массив с удвоенным количеством элементов).

    Так для 3 символов "abc" будет вызвана функция для "ab", которая вернет [ab, a.b], дописав "c" и ".c" к каждому элементу мы получим [abc, ab.c, a.bc, a.b.c].
    Ответ написан