Двощ - борда мамкиных школопиздунов, а потому призыв погромистов за 300 попытка №2.Это не задачки на проверку ваших скиллов, мне нужны ответы.1. Алгоритм ануса. В прошлый раз никто не осилил, так что повтор.Есть черно-белая картинка ануса. Нужно используя циклы и проверки (основу любого яп без фич и допов), обойти его по кругу по границе, как на пике.Начальная координата (x,y) рандомна, но на границе ануса. Это белая точка. Можно получать цвет любой точки по координатам от текущей точки через x,y +смещения. То есть, x,y-1 вернет цвет точки выше, а x+1,y той что правее. Смысл в том как сделать оптимизацию, чтобы считывать как можно меньше точек и нагородить как можно меньше проверок.2. Как работает ёксель в говнокоде? Есть ячейки, в которых может быть либо число, либо сумма других ячеек. Когда меняем значение первой ячейки,меняется результат всех зависимых. Как это реализовать в говнокоде? Сделать некое жалкое подобие ёкселя.Можно тупо после каждого ввода пересчитать всё. Но проблема в том, что их овердохуя и это неэффективно. Каким образом можно пересчитывать лишь то, что связано с изменяемой переменной/ячейкой? Говнокодим всё так же на основных элементах, без подключения баз данных и никаких селектов. Сам говнокод не нужен, надо лишь понять принцип, алгоритм так сказать, как оптимизируется и работает всё это говно.
>>206256105 (OP)Очевидно, что можно картинку на четыре квадрата разбить, и в зависимости от квадрата выбирать пиксели, которые в первую очередь проверяются. Можно сделать две основные проверки, впереди и сбоку, их будет достаточно для большинства случает, и только если они не прокатывают, выполнять проверки дальше.
>>206256718Ты мне подробнее опиши.>впереди и сбокуЭто куда? Тут как бы лево право верх низ, 2д плоскость. И жёпь получается когда надо поворачивать. Лесенкой оно недолго идет. Трещины анусая могут быть и глубже и вот как в неё заходишь, то всё херится. Потому разбивка на квадраты тебе ещё и похерить может целостность. Или я не пони что-то.
>>206256105 (OP)Выбираешь клетки контура (если одна из посьми соседних клеток - белая, то текущая клетка — часть контура), идешь по контуру простым и очевидным алгоритмом, пока вдруг не поймешь, что общее решение задачи лежит в плоскости NP-полных задач, но на простых случаях без подъебов будет работать и вариант обхода, который пятиклассник за пару уроков придумает.
Алсо, можешь вдохновляться чем-то таким: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4813928/Либо грызи задачки на поиск путей до просветления.
>>206257488>идешь по контуру простым и очевидным алгоритмомКаким? Я как бы не погромист совсем и мне это нихуя не очевидно.>который пятиклассник за пару уроков придумаетНу вот и тред о том, что борда погромистов пятиклашек, придумайте мне решение, а то у меня херь одна выходит...>>206257633>на поиск путейТам сложно и жопа полная. Да и куча математики уже, а это совсем пиздец.
>>206256105 (OP)Про анус можно в прологе оформить, только наверное через пизду получится с проверкой сразу по 4 точкам, но похуй либо по 2, Ноя забыл как.
>>206257796Я тебе говорю, что простое, но хуевое и сильно неточное/нестабильное решение можно без особых страданий будет. Твоя задача не такая простая, как тебе кажется, и общее и точное решение тебе никто просто так не будет делать.> Каким?Идти в рандомную соседнюю клетку контура, на которой еще не был.> Сам говнокод не нужен, надо лишь понять принципЯ тебе уже сказал, как отсечь только клетки контура и как выбирать следующую клетку. Ты если не совсем баран, то уже хотя бы прототип накидал.
>>206257904Я забыл как там все делается...Суть в том, что надо описать все 16 положений предикатами, типа huy(white,white,white,white), huy(white, white,white,black) и тд, то есть, например, в общем виде huy(лево,право,верх,низ) и для каждого там ещё что-то добавить, я забыл в общем, чтобы считались переходы из конкретных положений в другие. Ну и потом запускаешь, и он сам все считает, алгоритма не надо. Сложность не ебу.
>>206258173>Твоя задача не такая простая, как тебе кажетсяНу так ясен хуй. Была бы простая, я бы загуглил готовый ответ.>и точное решение тебе никто просто так не будет делать.Мне понять надо, сделать я и сам потом смогу на костылях.>Ты если не совсем баран,Давай предположим что я совсем баран. Чем проще поясняете, тем быстрее до меня дойдет.>Идти в рандомную соседнюю клетку контура, на которой еще не был.Но там есть развилки тогда. Нижнюю похуй, но вот выше можно проебать 2 пикселя на квадратике скакнув вправо, а не вверх, а ещё выше все 4. Как это фиксить?
>>206258506> Как это фиксить?Значит, ты уже видишь проблему у тупого алгоритма. Добро пожаловать в теорию графов, тебе нужен алгоритм коммивояжера. Его вообще без изменений можно использовать — тебе просто каждую точку контура обойти надо, а я уже пояснил тебе, что вообще в твоем случае контуром считается. Можешь даже не разбираться особо, как оно работает, а просто скопипастить код студентов с говнофорума и костылями и изолентой к своему анусу его прикрепить, но поебаться придется. За сим удаляюсь.
>>206256105 (OP)Первым ходом проверяет клетку справа и выше. Если две черная чекает клетку выше. Если белае двигается вверх. Если черная чекает клетку слева выше. Черная чекает клетку слева.белая двигается по координате. Если первая проверенная клетка справа сверху белая то чекает клетку сверху и если она черная чекает слева сверху и тд. А если она белая то двигается вверх и вправо и скрипт меняется на симетричный где клетка чекается снизу справа.
>>206258785>уже видишь проблему у тупого алгоритмаНу так не было бы её, было бы всё просто.>алгоритм коммивояжераЗагуглю потом. Всё равно уже много непонятного пишут, надо всё это читать. Ну хоть направлений наберу.>>206258982Бля, это надо переварить...
>>206258982Бля. Очень криво написал.Короче говоря я предлагаю тупо заскриптовать все ситуации. Сначала чекается клетка верх-право. В зависимости от результата чекаются другие клетки по очереди. Школоререшение через иф ду.
Хранишь позицию в объекте. Пробуешь шагнуть вверхЕсли чёрное, то пробуешь влевоЕсли чёрное то внизЕсли черное то вправоЕсли после чёрного белое, шагаешь, возвращаешь к попыткам, запоминаешь путь. Когда координата совпала с начальной - ты обошёл анус по контуру. Можно оптимизировать с запоминанием направления обхода
>>206256105 (OP)2. Запоминаешь значение изменяемой ячейки и работаешь с ним. Там было 5 стало 3, значит вычитаешь из пяти три, получаешь два. Из ячеек с результатом вычитаешь 2.
>>206259445>Школоререшение через иф ду.Ну типа того и делаем, но надо оптимизировать, а то оно будет думать там полчаса.>>206259472Оно зациклится на ямках и трещинах.
>>206259592Тут всё несколько сложнее. Как вообще из говна и палок сделать бд с ячейками. Вот есть у тебя переменные или массив. От них и плясать. >>206259866Одинаковые должны быть, не учитывай если укосило при зуме.>>206259894>с запоминанием направления обходаКак?
>>206260010Массив уже бд, что тебе нужно то?direction myDirection(Up). >запоминанием направления обходаМожно легко реализовать, но на самом деле то нинужно. Он не зациклится, если всегда будет поворачивать последовательно.
>>206260536Рандом. Это фотка после фильтра будет. Не более 55x55 пикселей.>>206260564Ну бля, я не погромист же, а разбираюсь тут понемногу.К слову, можете подкинуть книжек на русском, но не херь как задать переменную и сделать цикл, это я уже знаю. Вот такую всякую интересную поеботу бы с решениями и пояснениями, для чайников.>Он не зациклитсяВ следующий раз заготовлю говнокод. Из треда пару идей отметил и читаю херь в переводе про контурную трассировку пока.
>>206261021>Рандом. Это фотка после фильтра будет. Не более 55x55 пикселей.Тогда перебор. Смотрим на два пикселя впереди:(при обходе по часовой стрелке)- черный, черный - идем влево;- белый, белый - вправо;- б, ч - прямо.Для первой точки нужно смотреть на четыре пикселя вокруг точки и исходить из выбранного направления обхода
>>206261021Кароч у нас тут 21 век, все сидят на рязани и мы будем ебашить потоки. Создаёшь пул на оптимальное количество, и генерируешь обходчиков для каждого потока. Обходчики генерируются по краям карты, пикрилейтед и двигаются от края. Когда достигают ануса, обходят вправо до точки следующего обходчика. Как такая идея?
Или можно ронять обходчиков на анус, и соединять линиями. Есть соединение? Заебись, сойдёт, мы же не ракету на марс запускаем, примерный результат, тоже результат. Нет соединения, тогда от точки соприкосновения рисуем новую линиюПолучится примерный анус.
>>206261985>Как такая идея?Сложно. И разве это не дольше чем по контуру ползти? Ты же по сути считаешь все точки и даже дважды местами. И оно на 1 хуёвом ядре будет пердеть, когда запилю, а не на современном проце.>>206262162>обходчиков Опять какие-то фичи? Надо на примитиве сделать.>>206261904>Смотрим на два пикселя впереди:Обведи пример, не понял почему 2 впереди.
>>206262243На однопотоке будет чуть медленнее, зато в 2 и более потоков будет выигрыш. Точки не перекроются. >Опять какие-то фичи? Надо на примитиве сделать.Да эт я траллю немножк.
>>206262243>Обведи пример, не понял почему 2 впереди.Потому что те, которые сзади, мы уже прошли: сзади всегда будет "б,ч" при обходе по часовой стрелке, и "ч,б" при обходе против часовой стрелки
>>206262413>будет выигрышДа пока вообще надо переварить суть и сделать похуй как. А там уже допиливать чтобы за 3 сек успевало.Я когда скрипты делал первые версии тупили, а потом в процессе до 10 раз ускорялись. А всё потому, что алгоритмов не знаю. И вроде бы кажется что первое или второе похуй же(говноскан), а нет, иногда можно было сократить время в разы просто поменяв местами 2 ёбаные процедуры. К тому и тред, смотрю о чем пишут, гуглю и размышляю. А уже потом страдать.>>206262687>Бляага.
>>206262328Ты тролишь?1.У каждой точки на контуре всегда будет только две ближайших точки-соседа.2.Сортируешь их по этому соседству.Хз насколько это оптимально.
>>206263021>Ты тролишь?Нет. >Сортируешь Так уже лучше. Хз как сделать сортировку, особенно быстро, но если перебрать их в другой массив и они по порядку +-1 на корду будут, то можно и проверить на замкнутость ануса в итоге получив корды контура или стрелочки через подмену. Надо обдумать, это тоже вариант.
>>206256105 (OP)> 2. Как работает ёксель в говнокоде?> Можно тупо после каждого ввода пересчитать всё. Но проблема в том, что их овердохуя и это неэффективно. Каким образом можно пересчитывать лишь то, что связано с изменяемой переменной/ячейкой? Сохраняешь зависимости одних ячеек от других, при обновлении ячейки обновляешь все зависимые ячейки. Порядок обновления зависимых ячеек важен, так как одни могут зависеть от других. Чтобы не войти в луп, нужно находить циклические зависимости и показывать ошибку
>>206264057>Сохраняешь зависимости одних ячеек от другихПрост))) Мне для тупых надо, как это сделать? Вам то всё просто, но я не погромист и туплю.
>>206264155> я не погромистТогда идешь и нанимаешь программиста и он тебе делает твою хуйнюA=5 (при обновлении должен поменять C, B)B=A+C+4 (при обновлении должен поменять D)C=A+3 (при обновлении должен поменять B)D=B+1 (при обновлении ничего не меняет)
>>206256105 (OP)Решал похожую задачу когда-то на codingame.Я хуй знает что там в экселе ты делаешь и как это будет там работать, но напишу как я это делал на обычном языке программирования.В общем смотри, надо для каждого направления написать приоритет поворота, так, что бы стенка была все время с одной стороны. Представь что по пути идет человек и все время касается стены правой рукой и не может оторвать ее.Для направления вверх:Если человек идет вверх и впереди стена, то поворачивает направо. Если там тоже стена, то налево (налево от положения вверх). Если и слева стена, то идет назад.Теперь этот алгоритм надо прописать для каждого направления (вниз, влево и вправо), соответственно изменяя приоритет поворота относительно локального направления человека. Например, когда чел будет идти вправо, то поворотом направо стенет направление вниз.Ну и собственно все. Теперь нужно выбирать приоритет поворота относительно текущего направления - идешь вверх, поворачиваешь согласно приоритетам прописаных для движения вверх. Ну и в данном случае еще нужно определить в первой точке, куда начинать двигаться. В моем алгоритме этого небыло, т.к. я двигал чела внутри черной зоны, а не снаружи и не мог выйти за пределы лабиринта. Общая суть в том что бы идти вдоль стены, всегда касаясь ее правой рукой.
>>206264563>идешь и нанимаешь программистаМне надо понять как оно работает, а не готовое одноразовое решение. >при обновлении должен поменять C, BБаза разбухнет же в разы, если к каждой ячейке ещё и приписать все, где она упоминается. В примере по 2шт, на деле до 50и может быть на каждую. И несколько миллионов таких.>>2062651691 и 2 не связаны напрямую. Это разные куски с разными задачамси. Второе хранение данных, которые могут меняться.>приоритет поворотаНе вышло оно в прошлый раз и зависало в некоторых трещинах. >куда начинать двигатьсяЭто похуй. По или против значения не имеет. Выберется всё равно то, что нужно от этой операции.>внутри черной зоныЭто тоже похуй. Внешний или внутренний контур без разницы.Можно под любой сделать нужное.- - - - - - Оп-хуй отошел на пару часов. Тред пусть тонет. В этот раз и так вышло продуктивнее, чем в прошлый. Есть над чем подумать и что погуглить. Но если кто что ещё вбросит, я прочитаю потом.
>>206265613Если зависало, значит где-то был косяк. У меня этот алгоритм полностью обходил лабиринт с пика.
>>206263021>1.У каждой точки на контуре всегда будет только две ближайших точки-соседа.Хотя, может быть и три, если где-то толщина контура 1 пиксель. Так что не пойдет.
>>206265613> Мне надо понять как оно работает, а не готовое одноразовое решение.Возьми листочек, нарисуй формулы с зависимостями в виде графа. Дальше думай как оно должно обновлять другие ячейки при изменении формулы> База разбухнет же в разы, если к каждой ячейке ещё и приписать все, где она упоминается.У тебя два стула, либо пересчитывать каждый раз все ячейки, либо знать какие пересчитывать. Возможно над вторым даже не стоит запариваться, если у тебя и так все быстро считается
>>206267198Сейчас понял, что в таком виде этот алгоритм не сработает, потому что челик может упереться не только в стену, но и в пустоту на повороте. Надо будет на каждый шаг добавлять проверку, не улетит ли чел в космос следующим шагом. Возможно поэтому у них в прошлый раз и зависало.
>>206256105 (OP)Именно эта пикча? В питоне четыре строчки scikit и интеграл. Хуй я за тебя буду код писать, двоечник.
>>206256105 (OP)1. Алгоритм прохождения лабиринта2. Реактивное программирование (на основе событий, куда же без них, всё это с GUI связано)мимопогромизд
>>206270470Не, здесь, как раз все сработает.Идет вниз, упирается в стену. Пробует вправо, пробует влево, идет назад. Направление меняется на "вверх", соответственно приоритеты поворота тоже меняются относительно его. Упершись в верхнюю стену пробует вправо - не получается, пробует влево - получается. А вот слева он ни во что не упирается. А мой алгоритм, расчитан только на повороты, когда утыкаешься в стену.
>>206268613> scikit> интеграл> дискретная картинка с ОГРОМНЫМИ блокамиТак вот из-за кого у меня с двумя гигами лиса иногда подтормаживает!Ты ещё и МЛ-щик поди? Поди прочь, он программистов спрашивал.
>>206271747По границе формы. Собственно, прохода во внутреннюю дырку нет. Если по условию задачи можно ходить по диагонали, перепрыгивая углы, то это в корне меняет всю задачу и подход к ее решению, значительно усложняя все.Даже фотошоп, умным выделением эту дырку не выделяет. Пикрилейтед.
>>206256105 (OP)>>206271747ЕбанатКуча ошибок скорее всего, а ещё видимо стиль поплывёт, но я хотя бы попытался, в отличии от некоторых чмонь.(Короч Начальная-Точка (Ячейка Хэ Зэ))(Короч Текущая-Точка (Ячейка Хэ Зэ))(Короч Старая-стенка НИЧО)(Короч Чекни-Цвет (Хэ Зэ) "Тут ты сам напишеш")(Короч Шаг-В (Сторона) (Сделай-если ((Совпало Сторона Право) (Присвой Текущая-точка (Ячейка (Плюс-одын (Первый Текущая-точка)) (Остальное Текущая-точка)))) ((Совпало Сторона Лево) (Присвой Текущая-точка (Ячейка (Минус-одын (Первый Текущая-точка)) (Остальное Текущая-точка)))) ((Совпало Сторона Низ) (Присвой Текущая-точка (Ячейка (Первый Текущая-точка) (Плюс-одын (Остальное Текущая-точка))))) ((Совпало Сторона Верх) (Присвой Текущая-точка (Ячейка (Первый Текущая-точка) (Минус-одын (Остальное Текущая-точка)))))))(Короч Где-Стена () (Сделай-если ((Совпало Чёрный (Чекни-цвет (Плюс-одын (Первый Текущая-точка)) (Остальное Текущая-точка))) Право) ((Совпало Чёрный (Чекни-цвет (Первый Текущая-точка) (Плюс-одын (Остальное Текущая-точка)))) Низ) ((Совпало Чёрный (Чекни-цвет (Минус-одын (Первый Текущая-точка)) (Остальное Текущая-точка))) Лево) ((Совпало Чёрный (Чекни-цвет (Первый Текущая-точка) (Минус-одын (Остальное Текущая-точка)))) Верх) (ЧЁТКО НИЧО)))(Короч Сделай-шаг (Старая-сторона) (Давай ((Сторона (Где-стена))) (Если (Совпало сторона НИЧО) (Если (Совпало Старая-сторона НИЧО) (ПИЗДЕЦ РАСПИДОРАСИЛО) (Куча-всего (Шаг-в Старая-сторона) НИЧО)) (Сделай-если ((Совпало Сторона Верх) (Шаг-в Лево)) ((Совпало Сторона Право) (Шаг-в Верх)) ((Совпало Сторона Лево) (Шаг-в Низ)) ((Совпало Сторона Низ) (Шаг-в Право)))) Сторона))(Вообщем-цикл Пока-не (Вместе (Совпало (Первый Текущая-точка) (Первый Ничальная-точка)) (Совпало (Остальное Текущая-точка) (Остальное Ничальная-точка))) Делай (Присвой Старая-стенка (Сделай-шаг Старая-стенка)))
>>206273536>>206273582Да, кстт, не решает проблему "кармана", когда стены с нес сторон. Но без среды писать такое текстом наголо я ебал.
>>206256105 (OP)1. Оптимизация не имеет смысла, так как кэш-промахи разных строк внесут больший вклад, чем твое координатодрочерство. Если бы нужна была реально скорость, то там бы все хранилось в битовых массивах, тебе не понять.2. Евенты на изменение.>Это не задачки на проверку ваших скиллов, мне нужны ответы.Пашел нахуй, бесплатно решать за тебя домашки, чтобы ты потом устроился 300к/сек
>>206266053Закинь код своего бота для лабиринта.>>206267143Уже понял что всё херня, надо что-то другое думать туда.>>206267317Мне не надо готовое решение, так как это лишь кусок. Остальное то кто будет делать.>>206268613Нет, разные. Ради одной то какой смысл вообще был бы. >>206272440Такого не должно встречаться. Можно забить на эту дырочку.>>206272978>волновой алгоритмКак будто я знаю что это.>>206273582Надо переваривать этот текст чем-то похожий на код... Блять, лучше бы на своём яп писал, чем так.>>206274549>тебе не понять.Есть такое. >домашкиЭто не домашка. Это нечто типа бота на скрипте.
>>206275031>Как будто я знаю что это.Ты даун? Тебе сложно википедию открыть? Делаешь волновой для всего пространства, а потом оптимизируешь разбивая на квадраты.>>206277183Ах-ха, индексы не вычитаешь, а только в + ходишь.
>>206277412Не закончил же еще, там чем больше просчетов тем существенней зависимость в очередности. Я вообще прихуел когда он начал сам ходить туда сюда, перепрыгивать.
>>206256105 (OP)супер ультра не оптимальное решение с асимптотической сложностью O(n*n)идешь по всем пикселям изображение и если пиксель черный, то все белые пиксели вокруг него (если они есть) 100% контур.res = []for x in image.width: for y in image.height: if image[x, y] == black: if image[x+1, y] == white: res += point(x+1, y) elif image[x-1, y] == white: res += point(x-1, y) elif image[x, y+1] == white: res += point(x, y+1) elif image[x, y-1] == white: res += point(x, y-1) # еще 4 варианта для диагональных пикселей добавишь сам # еще в каждое условие нужно добавить проверку на выход за границы изображения res = set(res) # что бы удалить дубликатына хабре пару лет назад была статья о поисках контруров и алгебре над контурами, за 1 минуту не нашел, но ты можешь поискать. В статье использовали контуры для распознавания текста кажется. Еще как вариант ты можешь найти производную от твоего изображения и контуром будут пиксели, где производная не равна нулю. https://habr.com/ru/post/114452/
