Ответы пользователя по тегу JavaScript
  • Каким образом можно сделать рекурсивную функцию кластеризации объектов?

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

    Во первых, тут есть неоднозначность. Может быть так что теги A,B,C попарно несовместимы, но заодно попарно несовместимы теги A,D,E - куда относить тег A, в какую группу?

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

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

    Еще есть Алгоритм Брона — Кербоша. Он перебирает все максимальные клики.
    Ответ написан
  • Алгоритм работает не правильно?

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

    Вы же как-то пытаетесь реализовать это только лишь с переменной mid. Если надо идти влево, то вы делите mid пополам, как будто бы текущий отрезок от начала массива (Но это не всегда так: после первого же шага вправо начало массива будет уже выкинуто из расмотрения), Потом, при переходе вправо, у вас какой-то бред написан.
    Math.floor((arr.length - mid) / 2) - это что вообще должно делать? Если mid=9, length = 10, вы вообще уйдете в начало массива, хотя должны идти вправо. Если вы хотели взять середину между mid и length, то там должен стоять "+" внутри.

    Но так все-равно не получится сделать. Заведите 2 переменные l и r, как во всех реализациях бинпоиска, считайте mid как середину отрезка, и при выбрасывании одной из половин просто переписывайте l или r на mid+1 или mid-1 (потому что сам mid элемет вы уже рассмотрели и он точно не нужен).
    Ответ написан
  • Какова сложность алгоритмов (Big(O)) встроенных JS методов?

    wataru
    @wataru
    Разработчик на С++, экс-олимпиадник.
    Похоже документация не указывает сложность методов. Видимо, никто не ожидает от js кода производительности =)

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

    Возможно, можно нагуглить что-то по конкретным методам.

    По описанию метода concat, он возвращает новую строку не меняя аргументы. Поэтому, скорее всего, он работает за линейную сложность от общей длины операндов. Вряд ли там используется rope.
    Ответ написан
    2 комментария
  • Самая быстрая реализация алгоритма Дейкстры на javascript?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Попробуйте переписать с массивами фиксированной длины. Во всех реализациях по вашим ссылкам вершины нумеруются строками и куча массивов типа distance и visited на самом деле являются словарями, или как это в js называется. Это работает сильно медленнее тупого массива, пронумерованного от 0 до n.

    Вам понадобится один словарь для перенумерации вершин в числа. Потом преобразуйте гарф на массив массивов, вместо этого сложного объекта.

    И уже на нем гоняйте дейкстру. Должно по карйней мере в пару раз ускорится. А то и во все 10.
    Ответ написан
  • Как возвести decimal в степень с плавающей точкой?

    wataru
    @wataru Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Вы что-то напутали.
    1.000001**2**19 тоже возвращает 1.689255227180379. Только что в консоли проверил.

    > costumePow(1.000001, 19)
    1.689255227180379
    > 1.000001**2**19
    1.689255227180379
    Ответ написан
    6 комментариев
  • Когда использовать ООП?

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

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


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

    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 медленнее. У вас явно что-то совсем не то делается где-то.
    Ответ написан
    1 комментарий
  • Как реализовать поиск в глубину не рекурсией и если много кольцевых связей?

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


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

    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 Куратор тега Алгоритмы
    Разработчик на С++, экс-олимпиадник.
    Ответ написан
    Комментировать
  • Как преобразовать слова?

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

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

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

    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 чисел отсортировать и потом одним проходом по массиву групп с указателем в массиве запросов найти все ответы (если текущая позиция-запрос левее текущей группы, переходим к следующей позиции, если текущая позиция в текущей группе - мы нашли ответ).
    Ответ написан
    Комментировать