wlesavo: все таки видимо есть прогресс :slight_smile:
gybson_samara: забавно, завтра опробую
wlesavo: а, и прикол, там есть опубликованное хардкодное решение, чувак подобрал валидаторы просто перебором, не знаю зачем он опубликовал правда это
wlesavo: он когда то пазлом недели был, помню что я так хорошенько себе могзг поломал тогда, а сейчас прямо сел и решил сходу
Uljahn: совсем недавно решал похожий пазл :/
Uljahn: чё-т сложновато, надо тоже мозги поломать и отложить, а потом взять и зарешать сразу)
Uljahn: работа подсознания
Uljahn: часто замечал такое, что спустя некоторое время задача решается как бы сама собой - т.е. всё это время в фоне подсознание её решало, собирало инфу, возможно даже направляло какие-то действия под предлогом решения других задач :scream_cat:
Uljahn: проблема в том, что с одним человеком нельзя провести слепое тестирование: либо ты уже пробовал решать, либо нет, т.е. нельзя сделать вывод, есть прогресс или нет на основе решения такой задачи :confused:
Uljahn: возможно, дело в избирательности восприятия, т.е. осознаётся только определённая часть поступающей информации (феномен Баадера-Майнхоф и т.п.), но не известно, что с остальной частью инфы происходит :relieved:
mihei: божечки, поехала эпидемия клэш фолловеров
Uljahn: я петицию на форуме накатал, ставь лайк
https://www.codingame.com/forum/t/feature-request-ability-to-reject-incoming-follow/58429/4
Uljahn: а, ты уже поставил
Uljahn: спс
mihei: видел, лайкнул, это даже топик мой :)
Uljahn: ахах, точно
Uljahn: странно, что никто ещё не создал тред с этой проблемой, твоя тема - самое релевантное, что нашлось
Uljahn: в чатике-то давно недовольства, но админы чатик не очень читают
inoryy: It’s been a while since we’ve seen Uljahn — their last post was 3 years ago.
Uljahn: im a chat
735487: прогресс полюбому есть. я прямо вижу как я со временем могу выше в топ заходить. единственное что остановился пока и не решаю новые задачи и новых алгоритмов не выучил за последние полгода
vrabosh: решил написать всетаки определение где противник находится для окиана.. каряво получилось кнечно.. не гибко.
vrabosh: вот думаю, что на будущее подучить, может numpy почитать, через него может лучше будет, чем через масивы
vrabosh: какие инструменты советуете почитать новичку полному по питону, чтоб подготовиться к контесту?
735487: на numpy это Uljahn сможет больше рассказать. он давно вроде в него вникает. но как я понял там далеко не каждый контест получится его использовать и не всегда это просто
735487: а вообще привыкай к тому что на питоне далеко не во всех контестах можно до леги дойти
735487: разница по скорости с плюсами очень заметная
Uljahn: всё так
Uljahn: numpy имеет смысл учить, если собираешься заниматься машинным обучением или другими научными расчётами, вообще это интересная штука - как мини-язык внутри питона с расширенным контролем памяти и типов данных
vrabosh: как вы в океане ищете противника? как и я тупо перебором каждой клетки и смотрю врезается он встенку или себя или нет?
Uljahn: полному новичку можно начинать со структур данных (базовые + модули collections, heapq, json и т.д. - хотя бы знать, что есть такое), базовые алгоритмы (например, floodfill, voronoi, dijkstra)
Uljahn: ну да, каждую потенциальную позицию надо проверять, наверное
vrabosh: для меня это не базовые алгоритмы, а сложные.. мне надо с основ математики начать)
Uljahn: в программировании математики не так уж много, сначала изучаешь кубики (структуры данных), потом как строить башенки из кубиков (алгоритмы) :)
vrabosh: это уже изучил.. я до серебра дохожу. Дальше уже больше хочется грамотно делать.
Uljahn: тогда можно к ООП переходить и ФП
vrabosh: Как бы я решал подругому задачу океана.. во первых бы понял алгоритм поиска максимального пути.. я думаю он есть как раз дикста наверно отвечает на это. Чтобы меньше циклы крутить.
vrabosh: Потом поиск противника я бы одну матрицу сделал, где 1 - это сюда уже противник ходить не может.. и 0 где может.. и вторая матрица его ходы WSEитд.. и накладывал матрицу ходов на основную и смотрел сумму 0 равняется или больше.. если нулю, то тут он может ходить.
vrabosh: я думаю такая возможность простая есть сравнивать матрицы.. а не тупо перебор... одной матрцы в цикле с другой.
Uljahn: поиск максимального пути - это поиск Hamiltonian path, матрицами проще всего в numpy ворочать
vrabosh: и код бы стал короткий. и легче спроектировать тогда логику..
vrabosh: у меня даже простая вещь как стрельнуть, не попав в себя и захватив как можно больше пространства противника громозкой получается.. а только что увидел в нампи это проще делать
Uljahn: я делал так - сдвигал матрицу положений противника в сторону его хода, а потом через AND с картой суши отсекал невозможные положения
BorisZ: поиск пративника - это шаг в правильном направлении, даже плохой поиск продвинет бота сильно выше чем вымораживание лишнего хода в наидлиннейшем пути
vrabosh: я уже сделал поиск.. но мне он так не нравится как сделан, такой громозкий и я завтра уже в нем не разберусь
BorisZ: если можешь - пиши сразу так чтобы можно было поиск себя так же легко сделать с точки зрения врага - это понадобится потом
vrabosh: главное, что понял.. в чем дальше двигаться
735487: vrabosh: чтобы не попасть в себя достаточно простого условия
vrabosh: я уже океан не буду воротить. там код запутаный
vrabosh: условия то простые но они громоские
vrabosh: coorTorp = [(-4,0),(-3,0),(-2,0),(2,0),(3,0),(4,0),(0,-4),(0,-3),(0,-2),(0,2),(0,3),(0,4), http://chat.codingame.com/pastebin/0d133fba-eb80-45d6-82ef-49a2d8881d3d
vrabosh: вот как я это написал. - эо просто жесть
BorisZ: следующий шаг который сильно продвинет - поиск возможного убийства за 1 ход - со всплытием и прыжком
BorisZ: фаталити как его обозвали с легкой руки влесаво )
735487: чего там громоздкого, например такое if abs(x1-x2) <=1 && abs(y1-y2) <=1
Uljahn: ещё можно на первом ходе просчитать для всех клеток моря все доступные соседние клетки, все клетки эскпложенов и достижимых торпедой как BorisZ подсказал на контесте, сильно сократит вычисления потом
735487: а куда дострельнет торпеда проще в цикле сделать
735487: ты переусложняешь
Uljahn: я просто флудфил сделал с контролируемой глубиной
735487: да тоже норм идея
735487: я циклом смотрел все клетки в квадратном радиусе вокруг и доп условием проверял расстояние
Uljahn: как-то так: http://chat.codingame.com/pastebin/366c1f0f-aa98-4d66-b5e9-566396eba308
BorisZ: amurushkin связность же нужна еше, клетка может быть в радиусе но недоступна
BorisZ: уголком по диагонали острова бывают
BorisZ: Uljahn для очереди лучше deque - вроде она быстрее должна быть
BorisZ: from collections import deque
Uljahn: быстрее, если из начала забирать
Uljahn: а так - одинаково, вроде
735487: BorisZ: не ну у меня проверялось еще что это не остров
Uljahn: у меня стек по сути, а не дека
BorisZ: я не знаю что там под капотом, может двусвязный список или типа того, тогда пофиг с какого конца
Uljahn: лень было профилировать, да и не критичный кусок это
735487: стек от деки же отличается тем что в одном FIFO в другом FILO или как там абревиатура
Uljahn: если pop(0) делаешь, то конечно дека нужна
BorisZ: amurushkin 0-0 - ты, 1-0 и 0-1 острова, в 1-1 нельзя стрельнуть
BorisZ: я такое расположение имел ввиду
Uljahn: или если в начало добавляешь элементы
735487: BorisZ: ну так у меня через bfs проверялась доступность
Uljahn: у меня уже соседи посчитаны
StepanSmirnov: Привет. не подстажете, где можно почитать про модули out the box на codingame? или numpy единственное исключение?
Uljahn: https://www.codingame.com/faq
Uljahn: привет
wlesavo: ого меня до 27 просадили в океане
735487: ну это обычное дело. когда сабмитят те кто ниже тебя то обычно пушат вверх. если топы то в низ
wlesavo: у меня фильтр выстрелов был нумпайный
wlesavo: gamma = 0.9
distances = Game.dist_fill(x, y, Game.grid, gamma)
c = gamma**4
return np.logical_and(distances > c, distances < 1.5)
wlesavo: def get_possible_shoots(x, y): http://chat.codingame.com/pastebin/0c8cd595-ff6e-40eb-a6e4-ff0a2b9b4bee
Uljahn: что за гамма?
Uljahn: какой-то дисконт?
Uljahn: эвристика для перевода из манхеттена в условные единицы длины? :thinking:
wlesavo: да, я делаю заполнение с дискаунтом, удобно потом сравнивать
wlesavo: потом в троне так делал диаграммы, в две строчки считай
wlesavo: ну я говорю я это попробовал для поиска пути сначала, и как то понравилось что вместо бфса везде пользую
Uljahn: нипанятна
YurkovAS: заполнение с дискаунтом - здесь? можно подробнее?
distances = Game.dist_fill(x, y, Game.grid, gamma)
Uljahn: dist_fill надо смотреть
wlesavo: ну заполнение идет только в те клетки где значение строго меньше чем в текущей, и значение там становится текущее на гамму, так получается что не нужно лишних проверок
wlesavo: и расстояние строго определено
wlesavo: тогда минимальный путь это тоже спуск такой что в каждой следующей точке строго меньше чем в текущей
wlesavo: def dist_fill(x, y, grid, gamma): http://chat.codingame.com/pastebin/ab68185b-02b1-4aac-9098-8dbcb983f88c
Uljahn: рекурсивненько
wlesavo: можно еще дополнительным параметром передавать чтобы не все заполнялось, а на определенную глубину, но вроде особо смысла не видел
wlesavo: Uljahn почему то у меня с рекурсией быстрее работало, может я криво цикл писал
wlesavo: наверное потом перепишу на while еще раз, ато копипащу кусок этот обычно
Uljahn: погоди, ты каждый раз рассчитываешь при стрельбе или только один раз в начале?
wlesavo: ну я один раз за ход при стрельбе рассчитываю, это не затратно
wlesavo: у меня за 5мс без поиска пути не выходило, поэтому я не парился, тут есть где оптимизировать конечно
Uljahn: вообще, идея интересная, и где-нибудь может здорово выручить, но в данном случае имхо лучше в начале всё посчитать
Uljahn: карта же не меняется, вот если бы менялась - то да
Uljahn: к тому же не известно, как оценивать затраты по времени - если профилировать только этот сниппет, то может и небольшие, но если смотреть в совокупности с учётом инвалидации кэшей (хаха, в питоне-то), то может и сильно влиять
wlesavo: ну я говорю, наверняка не самый оптимальный способ, просто более менее удобно было, и я не видел больших затрат в производительности на это, зато хорошо инкорорировалось с другими фишечками какими
YurkovAS: return np.logical_and(distances > c, distances < 1.5)
а здесь вернется список точек, с растоянием от 0.9^4=0.6561 до 1.5?
Uljahn: это да, удобства часто перевешивают производительность
Uljahn: вернётся numpy array, наверное
wlesavo: вернется bool массив
Uljahn: и тут вроде наоборот, от 0 до 1.5 и более 0.9^4
Uljahn: jq
Uljahn: ой
wlesavo: 1.5 это чтобы отсечь острова, острова двойки у меня на той же карте
Uljahn: я попутал чё-т
wlesavo: ну и это был первый раз когда я чтото из нумпая пытался сделать, так что не судите строго :slight_smile:
Uljahn: а зачем на карте смешивать разные сущности?
Uljahn: и суши, и расстояния?
BorisZ: это чтобы расстояния не считать что ли?
wlesavo: ну чтобы в острова не стрелять
wlesavo: BorisZ ну это и есть рассчет расстояний, просто чуть нетривиальнее
Uljahn: да нормально для первого раза, у меня намного хуже было)
wlesavo: расстояние здесть будет логарифмот значения с основанием 0.9 :grinning:
BorisZ: как-то это все называется, опять из головы вылетело (
Uljahn: оверинжиниринг
BorisZ: поля вроде
Uljahn: потенциальные?
BorisZ: ага )
BorisZ: оверинжиниринг наверное тоже, да )
BorisZ: но потенциальные поля круче
wlesavo: вообще алгоритм поиска пути Bellman-Ford method называется, я украл из той книги что ульян скидывал, а рассчет расстояний таким образом сам собой получается уже
wlesavo: но там конечно у них красивее само заполнение было, на самом деле нумпайное
Uljahn: эта книга? https://www.labri.fr/perso/nrougier/from-python-to-numpy/
wlesavo: https://www.labri.fr/perso/nrougier/from-python-to-numpy/#path-finding
wlesavo: хех
Uljahn: ага, топчик
BorisZ: я так пробовал тоже в каком-то из платинум рифтов, заполнил карту коофицициентами и все юниты потом просто скользят вниз - все автоматом
YurkovAS: в общем я не понял, как это работает.
если без этого коэффициента, можно объяснить?
Uljahn: сначала надо понять, что такое grid, там какие-то расстояния и суша, вроде
YurkovAS: у меня сделано так: для всех потенциальных положений противника стреляю в них + 8 соседей вокруг. если можно стрельнуть по предрасчитанной матрице
inoryy: зачем BF рассчитывать
inoryy: поиск пути в пару строчек питона предсчитывается на 1м ходу
inoryy: хинт: scipy.sparse.csgraph.shortest_path
Uljahn: а, ну да, юзал такое в GitS
YurkovAS: там же можно плыть только по еще не занятым.
куда можно стрельнуть - это можно расчитать при старте
inoryy: ну это фильтруется махом в нумпи
wlesavo: ну я для фильтрации и делал, просто первое что в голову пришло
inoryy: еще из той же оперы scipy.ndimage.binary_dilation для подсчета радиусов взрыва в 1 заход
inoryy: scipy.ndimage.measurements.label для связных компонентов
BorisZ: inoryy
csgrapharray, matrix, or sparse matrix, 2 dimensions
The N x N array of distances representing the input graph.
BorisZ: выходит ему надо матрицу расстояний дать
BorisZ: то есть ее надо самому сначала посчитать )
wlesavo: BorisZ я вот думаю может тоже за спрингфилд поучаствовать? еще кого нибудь возьмем чтобы в рейтинг компаний попасть хоть, ато так не интересно
BorisZ: причем просто connectivity matrix - подойдет или нет хз, чем заполнять все расстояния кроме соединений
BorisZ: wlesavo ты имеешь ввиду прописать одну компанию в профиле?
YurkovAS: Top 3 schools and top 3 companies
Personalized glass awards
wlesavo: BorisZ ну да, просто твоя чем хороша что очевидно фейковая
YurkovAS: Персональные стеклянные награды
wlesavo: правда там только за топ 3 максимум можно бороться, первые две слишком уж много народу
BorisZ: не знаю, как-то не очень, вдруг это против правил каких-нибудь, поднимут шум
wlesavo: ну просто учитывая что очевидно фейковая компания захотят просто не будут учитывать, мыж не придумываем подставную
BorisZ: да я и у меня неделя напряженная будет, только в выходные смогу посидеть толком, вряд ли с таким подходом заберусь куда-то
wlesavo: хотя мож и нет смысла особого, будем за школы драться
wlesavo: я сам тоже не знаю че будет, работы много
BorisZ: тут как я понимаю логика такая - они надеются что участники будут реальных коллег подтягивать, увеличивать посещаемость, если бы хотели командное соревнование - так и сделали бы
BorisZ: уже был командный контест давно как-то
BorisZ: но видимо не взлетело что-то
BorisZ: https://www.codingame.com/leaderboards/contests/klee-completely-hidden-gdpr/global
BorisZ: он был как бы открытый, но о нем нигде не объявляли
BorisZ: и команду чтоб сделать нужно было вручную поменять свой ник - добавить префикс команду в скобочках
BorisZ: там даже игру не придумывали новую - взяли ghost Busters и переделали правила немного
inoryy: X: HWxHW матрицу даёшь на вход где X[i, j, k, l] == 1 если сосед и проходимый
BorisZ: а если нет то можно NaN видимо
BorisZ: тогда да, проще согдасен
BorisZ: просто если уже вручную делаешь матрицу расстояний, то кратчайший путь по дороге легко строится
inoryy: дак не делаешь руками
inoryy: только между соседями надо
inoryy: и это можно через binary_dilation тоже сделать
inoryy: давайте всем ручатом в атомный реактор на работу пойдем
BorisZ: кто будет Монти Бернс? )
BorisZ: https://www.youtube.com/watch?v=n_A3T0UcAJc
wlesavo: атомный руактор :slight_smile:
wlesavo: а что, я учился на факультете проблем физики и энергетики, подходит так то
MadKnight: inoryy
MadKnight: go v discord
VulpesCorsac: Добрый вечер. Кто-нибудь может подсказать, насколько вообще на сервере хорошо работает многопоточный код. Вроде и компилируется всё с -lpthread, судя по faq, но чёткого понимания как-то всё равно нет, насколько это хорошая мысль
MadKnight: тебе одно ядро дают
Uljahn: с гипертредингом?
MadKnight: похоже на то
VulpesCorsac: Вот, да, одно ядро - это формально "плохо", но ещё не гарант, что "совсем плохо"
MadKnight: одно ядро вроде как 2 потока может тянуть
MadKnight: но доступ к памяти всё равно один
Uljahn: а ты где-то уже упёрся в производительность? или просто фанат преждевременных оптимизаций? :smirk:
MadKnight: Uljahn я тут либу на питон установил
MadKnight: она легла куда-то в програм файлс
MadKnight: в виде .pyd
VulpesCorsac: У меня немного не сервере не влезает в 2 секунды Code of the Rings в случае более-менее хорошего ДП. Т.е. я понимаю, что, видимо, это не обязательно, но всё же, других илей всё равно не было
MadKnight: как её подключить в код Uljahn ?
MadKnight: VulpesCorsac а ты на плюсах?
VulpesCorsac: Когда как, конкретно там - да
Uljahn: VulpesCorsac: посмотри в сторону AVX
Uljahn: MadKnight: через что установил? pip?
MadKnight: не
MadKnight: установщик скачал
MadKnight: ехе
Uljahn: через import не импортирует?
MadKnight: плюс я в вижуалке питон юзаю
MadKnight: чё с этим pyd делать?
Uljahn: скопируй в питонячьи либы и попробуй импортнуть
MadKnight: так скомпилено же
MadKnight: как теперь импортнуть?
Uljahn: через import
MadKnight: DLL load failed: %1 не является приложением Win32.
Uljahn: питон будет искать модуль с этим именем, у меня скомпиленные pyd лежат в DLLs
Uljahn: а он под винду скомпилен? с той же версией vc что и питон?
MadKnight: где этот DLLs?
Uljahn: в папке питона
MadKnight: а погоди, я случайно х86 взял
MadKnight: DLL load failed: Не найден указанный модуль.
MadKnight: эту ошибку для 64 выдаёт
Uljahn: может, там ещё зависимости какие-то
MadKnight: ну там только эти 2 pyd
MadKnight: я их перекопировал рядом с моим кодом
Uljahn: почему они через экзешник распространяются? проприетарщина с обфускацией?
MadKnight: ага
MadKnight: плюс изначально это с++ библиотека
MadKnight: они скорее всего просто с++ скомпилили под питон
MadKnight: там в include/ лежат .h'ники
Uljahn: ну так многие модули для питона так сделаны
MadKnight: а в lib/ - pyd
MadKnight: это fbx importer
MadKnight: FBX SDK от Autodesk
MadKnight: а в питоне от вижуалки есть pip ?
Uljahn: у тебя питон вместе с вижуалкой установился?
MadKnight: аг
MadKnight: а
Uljahn: а версия подходит под этот модуль?
735487: читай readme секцию Installation ))
735487: неужели доки нет?
MadKnight: ща попробую скачать ещё python binding
MadKnight: с их сайта
MadKnight: чё-то в нём ничего интересного
Uljahn: вот это что ли?
http://help.autodesk.com/view/FBX/2020/ENU/?guid=FBX_Developer_Help_scripting_with_python_fbx_installing_python_fbx_html
MadKnight: ага
Uljahn: Platforms supported: Python33
ahah
MadKnight: Copy the contents of <yourFBXPythonSDKpath>\<version>\lib\<Pythonxxxxx>\ into: http://chat.codingame.com/pastebin/fe6d0243-60ba-418b-bd7e-98d4489fc019
MadKnight: чё ахах?)
Uljahn: да он древний сильно, для XP
MadKnight: ну так вот
MadKnight: если кладу в site-packages, то он вообще его не находит
MadKnight: а если рядом с кодом - пишет Message=DLL load failed: Не найден указанный модуль.
Uljahn: я бы начал с того, что попытался установить python3.3 и прочитал все доки на сайте
MadKnight: ну у меня 3.7
Uljahn: очень сомневаюсь, что либа, скомпиленная под 3.3 заработает где-то ещё
MadKnight: что, 3.3 не заработает на 3.7 ?
Uljahn: сомневаюсь
MadKnight: а почему такая странная ошибка?
Uljahn: from fbx import * так импортируешь?
Uljahn: http://help.autodesk.com/view/FBX/2020/ENU/?guid=FBX_Developer_Help_scripting_with_python_fbx_using_python_fbx_with_eclipse_html
Uljahn: вот тут степ-бай-степ мануал, правда, сильно устаревший
Uljahn: чё-т у меня подозрения, что оно вообще работает, а не просто рудимент какой-то, который удалить забыли
Uljahn: кто-то вообще пользуется этой либой? у кого-то работает?
MadKnight: ну по идее
MadKnight: это же fbx sdk
Uljahn: а зачем тебе питон там?
Uljahn: https://github.com/jochasinga/py-fbx
MadKnight: а, я нашёл не тот site-packages
MadKnight: в sys.path посмотрел какой надо
MadKnight: скинул туда
MadKnight: теперь выдаёт DLL load failed уже из site-packages
MadKnight: Uljahnj так этож wrapper
Uljahn: ну тогда хз
Lopear: один манул
foxbel: два манула
inoryy: пять, больше не просите
MadKnight: inoryy go v discord
metahom: почему в дискорд?
Lopear: три манула
inoryy: там кони в вакууме
metahom: зашел, там как-то мертвенько
MadKnight: metahom так ты на сервер подключись
MadKnight: какой-нить живой сервер
MadKnight: и будет живенько
Lopear: один манул
