Chat:Ru/2020-08-15

From CG community
Revision as of 11:26, 15 June 2021 by Chat Log (talk | contribs) (Created page with "<img src=/a/25714480415254> tutubalin: в Code of the Ring набрал 6001 без хардкода и 4577 с хардкодом <img src=/a/25714480415254> tutubalin: на...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

tutubalin: в Code of the Ring набрал 6001 без хардкода и 4577 с хардкодом

tutubalin: надо будет потом попробовать генетикой порешать

Default avatar.png gtj: tutubalin видел как я модно обхожу лабиринт?

Default avatar.png gtj: я до этого додумался сам!

Default avatar.png gtj: логически потомучто все в дереве и нет 0 в дереве

Default avatar.png gtj: в дереве одни 1

Default avatar.png gtj: попробуй это клево

tutubalin: во-первых, не дерево, а граф

tutubalin: во-вторых, логично, что в невзвешенном графе все веса равны единице

tutubalin: тебе про это говорили, тыщу лет назад

Default avatar.png gtj: ну значит я евнух не понимал это нормально потом осенило как ни свет не заря

Default avatar.png gtj: зато теперь рекурсия долбит любой путь, а бфс опять вылавливать и править ту же ошибку

tutubalin: может быть нужно просто внимательно прислушиваться к тому, что тебе говорят вместо того, чтобы писать портянки текста?

Default avatar.png gtj: слушай я уже верил до последнего пока бфс просто не заработал что я просто не свидетель бфс

Default avatar.png gtj: но я вот засвидетельствовал его

Default avatar.png gtj: я думал чото что это какойто единственный алгоритм

tutubalin: если у тебя рекурсия, то скорее всего это не бфс, а дфс

Default avatar.png gtj: где в рекурсии?

Default avatar.png gtj: во уже все знает

Default avatar.png gtj: да ладно откуда ты взял что дфс

Default avatar.png gtj: есть рекурсивный бфс

tutubalin: предположение. я не знаю, зачем рекурсия в бфс

Default avatar.png gtj: от него и пошел твой бфс с очередью очередь убирает опасность рекурсии

Default avatar.png gtj: https://github.com/richkirl/learnincgame/blob/master/graphkirk4.cpp

tutubalin: чем отличается бфс от дфс?

Default avatar.png gtj: я не исследовал дфс

Default avatar.png gtj: я пока исследовал бфс

Default avatar.png gtj: и сделал проще некуда бфс

Default avatar.png gtj: ток рекурсией

tutubalin: посмотрел код, подтверждаю. ты сделал дфс

Default avatar.png gtj: а как ты это понял?

tutubalin: покури мануалы, чем они отличаются

Default avatar.png gtj: да не буду надоело покури то почитай то чо тебе сказать сложно вот я буду еще голову ломать

tutubalin: у тебя голова чтобы в неё есть?

Default avatar.png gtj: бфс это проход в ширину делает рекурсивно

Default avatar.png gtj: посмотри внимательно

Default avatar.png gtj: посмотри внимательно в бфс

Default avatar.png gtj: хочешь скину?

Default avatar.png gtj: он пока не отдебажен

tutubalin: с тобой бесполезно разговаривать. досвидос

Default avatar.png gtj: http://chat.codingame.com/pastebin/c719123f-0665-49cc-b679-84493f2cce92

Default avatar.png gtj: я искал ночью отличия но их нет

Default avatar.png gtj: так что это фс

Default avatar.png gtj: бфс

Default avatar.png gtj: но имеет структуру < nodevector<pair<int,int>>>

Default avatar.png gtj: в каждой ноде есть инфа в паре в первом елементе ссылка на следующий

Default avatar.png gtj: но следующий находится в дереве в ширине по дальности от текущей ноды потому мы и поиском занимаемся и рекурсивно бьем в дерево

Default avatar.png gtj: прыгаем по дереву по нужному нам маршруту и смотрим что находится в парах в нашей ноде слово по ссылкам

Default avatar.png gtj: тоесть если переписать на дерево структурой где 4 ссылки по нейману то будет изи рекурсия по идее

Default avatar.png gtj: то что тут на рекурсии я еще проверял ночью на стоимость

Default avatar.png gtj: это очень дорогие операции

Default avatar.png gtj: потомучто в пути могут быть точки ссылающиеся на очень дальних предков другой части дерева еще я заметил что пол дерева просто отключается при обходе собсно как и в бфс

Default avatar.png gtj: в текущей ситуации изза таких нод это бфс к сожалению

Default avatar.png gtj: просто ты сначало заходишь в потом берешь какойто нод для прыжка и прыгаешь либо назад либо вперед на ту ноду которая в узле

Default avatar.png gtj: кароче я фиг знает

gsomix: gtj, и ради бфс ты забросил рисование? :)

Default avatar.png gtj: одно другому не мешает

gsomix: gtj, обновлений на канале давно не было. Я подумал, что забросил ради этой ерунды. :)

Default avatar.png gtj: на каком

gsomix: В ютубе.

Default avatar.png gtj: ну это мой канал

Default avatar.png gtj: посмотри последний ролик

BorisZ: в реализации бфс и нерекурсивного дфс нет отличий кроме типа коллектора, у бфс это очередь fifo у дфс - стек lifo

BorisZ: и флудфил тоже, там коллектор все равно какой

Default avatar.png gtj: да мне пофиг работает и работает

BorisZ: и дейкстра, там добавляется вес ребра и очередь с приоритетом в качестве коллектора

gsomix: gtj, так он январьский. :) Где свежие ролики?

BorisZ: то есть код одинаковый полностью

Default avatar.png gtj: нечего писать

gsomix: gtj, это все из-за бфс.

Default avatar.png gtj: я не пишу уже ничего толку от этого

Default avatar.png gtj: Борь а у меня дфс или бфс?

Default avatar.png gtj: http://chat.codingame.com/pastebin/c719123f-0665-49cc-b679-84493f2cce92

Default avatar.png gtj: я думаю это бфс

BorisZ: std::queue<int> q; значит бфс

BorisZ: но это не точно, я не вчитывался

Default avatar.png gtj: а ноды Борь

Default avatar.png gtj: я так понимаю тут ни то ни то тогда

BorisZ: myNodes.find(temp)->second[0].first != 33

Default avatar.png gtj: это будуший финиш пока захордкоженый

BorisZ: чтоб понть что это надо выпить чего-то с литр )

Default avatar.png gtj: финишь

BorisZ: слишком сложное представление графа на мой взгляд

ivandr: gtj

ivandr: ты просто хочешь написать бфс???

ivandr: если я правильно понимаю

ivandr: ты хочешь вернуть путь к вершине

Default avatar.png gtj: тут помойму нереально бфс написать бфс это обход в ширину в двоичном дереве тут в нодах лежит всякого щас покажу на минимальном примере

Default avatar.png gtj: и причем отрабатывает как редирект

ivandr: для начала скажи что тебе надо

ivandr: и что ты пишешь

Default avatar.png gtj: хотел бфс потом курнул чуть глубже что в нодах и осенило

Default avatar.png gtj: вот погляди

Default avatar.png gtj: http://chat.codingame.com/pastebin/1b746072-1157-4c9f-adc1-d1dbb9385c66

Default avatar.png gtj: я ввожу 9 и парсю ноды чтобы цикла не было

Default avatar.png gtj: а как бфс сделать я не знаю и бфс ли это

Default avatar.png gtj: бфс хотел сделать

Default avatar.png gtj: ([ x ] - нода = [ x ] ) третье число это предок куда прыгаем

ivandr: что это за таблица

ivandr: это у теюя типо такие списки ребер

Default avatar.png gtj: это граф сверху и снизу его ребра в виде ([ x ] - нода = [ x ] ) третье число это предок

ivandr: ага

ivandr: а таблица ка такая строится

ivandr: значения ниже я понимаю

Default avatar.png gtj: распаковываю

Default avatar.png gtj: int vector para int int

Default avatar.png gtj: pair.first -> следущая нода

Default avatar.png gtj: но не ссылка а значение

ivandr: а зачем ты следуйщего нода хранишь

ivandr: храни граф так

ivandr: vector<int> g[N]

ivandr: где g[i] єто веектор вершин связаніх с i

Default avatar.png gtj: вижу вектор спорно хотя кажется и очевидно а дерево это быстро

Default avatar.png gtj: плюс это граф где есть ширина и высота

Default avatar.png gtj: и хранение в дереве

ivandr: подожди каое дерево

ivandr: у тебя граф дерево

ivandr: ?

Default avatar.png gtj: да

Default avatar.png gtj: я забыл написать вся эта бадяга в мапе

ivandr: оооо

ivandr: та подожди

ivandr: что тебе надо

Default avatar.png gtj: да нельзя пройти бфс тут

Default avatar.png gtj: все я уже понял

Default avatar.png gtj: только вот таким макаром

Default avatar.png gtj: бфс это другое

ivandr: а суть задания мы так и не узнаем)

Default avatar.png gtj: я хотел бфс сделать

ivandr: ну

Default avatar.png gtj: потом вспомнил что это дерево и присмотрелся к значениям нод и все

Default avatar.png gtj: и сделал просто обход дерева

Default avatar.png gtj: вот и всё что я понял

ivandr: аа то есть ты просто написал дфс

Default avatar.png gtj: не знаю

ivandr: ибо бфс это тоже верно

ivandr: ну ладно

Default avatar.png gtj: это ни то ни то

Default avatar.png gtj: это обход дерева

ivandr: ладно развлекайся

Default avatar.png gtj: ты лучше свой бфс покажи

Default avatar.png gtj: который как бфс проходит

ivandr: а ну ща подожди

ivandr: кста а как кидать файл сюда)

ivandr: https://pastebin.com/CkzWtswu

Default avatar.png gtj: все я разобрался

Default avatar.png gtj: у меня дфс да

Default avatar.png gtj: вот доказательство

Default avatar.png gtj: https://imgur.com/iZM4BRv

Default avatar.png gtj: Ульян вот как можно еще тора сделать

Default avatar.png gtj: https://youtu.be/yTRzfKh4Tg0

wlesavo: YurkovAS нашел косяк или новый алгоритм?

Default avatar.png gtj: почему автор назвал видео так итеративный обход дерева

Default avatar.png gtj: https://www.youtube.com/watch?v=pcicxEjCPZY

Default avatar.png gtj: итеративный это же дефолтные обходы Iterator iterator = list.iterator(); while (iterator.hasNext()) {

   System.out.println(iterator.next());

}

ilgiocatore: итеративный значит с использованием цикла, а не с использованием рекурсии

ilgiocatore: потому что итерацией называется как раз повторяющееся действие в цикле. То есть в твоем примере "итерация" это строчка "System.out.println(iterator.next());"

Default avatar.png gtj: понял что итерация я думал по итератору типо)

Default avatar.png gtj: щас попробую поменять свой алго на стек и гляну чтото мне подсказывает что в сложноструктурном дереве с путями нет разницы между бфс и дфс

Default avatar.png gtj: тоесть в графе где пути 1 нет разницы как ити я предпологаю

Default avatar.png gtj: он выберет тот же путь что и бфс

Default avatar.png gtj: ну да что стек что очередт по одинаковому маршруту проходят

Default avatar.png gtj: видимо разница будет только на открытой местности

Default avatar.png gtj: поидее дфс должен вперед бежать а бфс по углам искать

Default avatar.png gtj: кароче пофиг

BorisZ: дфс может выбрать какой угодно путь. Он может ответить на вопрос - есть ли путь вообще от а к б, но кратчайший он или нет - как повезет

BorisZ: в случае бфс путь всегда будет кратчайшим - по определению

Default avatar.png gtj: Борь

Default avatar.png gtj: хорошо

Default avatar.png gtj: борь все зависит от дерева

Default avatar.png gtj: есть мапа в ней ключ, а в данных хранится вектор пар

Default avatar.png gtj: первое поле пары это нода

Default avatar.png gtj: в таком дереве не будет бфс

Default avatar.png gtj: по определению да еще с путевым графом где не пол карты закрыто

Default avatar.png gtj: такое дерево только сканировать

Default avatar.png gtj: и вычленять кратчайший

Default avatar.png gtj: так как ты будешь по такому дереву прыгать а не двигаться

Default avatar.png gtj: 1 16 19 27 32

Default avatar.png gtj: просто у меня строит граф а для дерева щас попробую

BorisZ: я ж не слежу за эволюцией твоих мыслей, если это задача про лабиринт то при чем тут дерево какое-то, не знаю

BorisZ: если я цепляюсь глазом за какой-то осмысленный вопрос - стараюсь ответить как могу

tutubalin: > это ни то ни то > это обход дерева это диагноз

tutubalin: dfs - обход дерева в глубину bfs - обход дерева в ширину gtj - дерево

Default avatar.png gtj: ну все КО пришел

Default avatar.png gtj: лучше бы дал более менее внятный ответ

tutubalin: лучше бы ты задал внятный вопрос

Default avatar.png gtj: стек и очередь делаю одинаковые вещи

Default avatar.png gtj: один путь что на стеке что на очереди

tutubalin: а ещё лучше бы - просто куда-нибудь ушёл

Default avatar.png gtj: покажи лучше свои доводы

tutubalin: как одним словом назвать дилетанта, который не хочет учиться, но всех вокруг учит?

Default avatar.png gtj: покажи свои доводы

Default avatar.png gtj: покажи дерево

tutubalin: ты дерево

Default avatar.png gtj: покажи пути бфс дфс

tutubalin: тук-тук-тук. глухой звук

Default avatar.png gtj: у меня пути совпали

tutubalin: тебя в википедии забанили?

Default avatar.png gtj: ты как ты говоришь диллектанта сравниваешь и зачемто развенчиваешь яж не спорю я понять пытаюсь дело не во мне сейчас

tutubalin: дело именно в тебе

tutubalin: нормальный человек зашёл бы на википедию и почитал

tutubalin: https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83#/media/%D0%A4%D0%B0%D0%B9%D0%BB:Depth-first-tree.svg

tutubalin: https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83#/media/%D0%A4%D0%B0%D0%B9%D0%BB:Breadth-First-Search-Algorithm.gif

tutubalin: Automaton2000 вот из-за упёртого дилетанта пришлось в чат нафлудить длинных ссылок

Automaton2000: или ты имеешь в виду

Default avatar.png gtj: я ваще не спорю что ничего не знаю вот деревья только запомнил но тебе если не интересны эти темы не ведись на них, тема в полне интересная прежде чем это делать я неделю исследовал изучал смотрел другие реализации и сделал как смог, если ты спец лучшеб показал пример почему не так и как ты считаешь так, есть графвиз, методы скинуть могу, есть псевдокод есть много чего тебе просто лень , а лучше сидеть и на вентилятор набрасывать

tutubalin: мне не нужен твой код. он очень плохого качества, как и твои сообщения

Default avatar.png gtj: ну а к тебе тогда как относится?

tutubalin: я тебе дал: http://chat.codingame.com/pastebin/4b2540ff-25b8-4014-a5fa-b1288933e2d9

Default avatar.png gtj: я к конкретике перешел

tutubalin: я в этот чат прихожу пообщаться с умными людьми, а не с тобой

Default avatar.png gtj: потомучто чтобы понять этот вопрос надо иметь код

Default avatar.png gtj: рабочий!

tutubalin: но все умные сообщения смывает твоим никчемным флудом

Default avatar.png gtj: я вот не пойду твоим путем строить о тебе догадки хотя они только что родились

Default avatar.png gtj: чтото мне подсказывает тема деревьев кому то сложна

gsomix: gtj, покажи дерево.

Default avatar.png gtj: пока такой вариант из примера сделал

Default avatar.png gtj: https://imgur.com/iZM4BRv

Default avatar.png gtj: это если кликнуть в лабиринт и несколько вопросиков убрать

gsomix: gtj, это не дерево.

Default avatar.png gtj: понимаю

gsomix: gtj, покажи дерево.

Default avatar.png gtj: тогда щас сек с дотой разберусь

Default avatar.png gtj: там распарсить ноды надо рисует пока так

Default avatar.png gtj: dot

Default avatar.png gtj: так вводу в таком порядке

Default avatar.png gtj: http://chat.codingame.com/pastebin/19a850bf-16dc-465c-bd7d-7847b982336d

gsomix: gtj, давай картинкой.

Default avatar.png gtj: тебе в начальном варианте или обход кого зацепили в пути

gsomix: Давай сначала дерево. :)

Default avatar.png gtj: тогда пошел думать щас придумаю

Default avatar.png gtj: это дерево

Default avatar.png gtj: нарисовать топологию как храниться в мапе отруки только смогу а тут только подходит дерево хафмана

Default avatar.png gtj: сопсно тоже самое

Default avatar.png gtj: просто лепестки будут парные к кому и идут

Default avatar.png gtj: пути

Default avatar.png gtj: построить примерное дерево можно только вов ремя пути

Default avatar.png gtj: ну вглубину но факт в том что через очередь он тоже в глубину строит

Default avatar.png gtj: кароче из хафмана можно построить только в глубину

Default avatar.png gtj: жадный дфс

Default avatar.png gtj: кароче вот код все я хз что это за алгоритм

Default avatar.png gtj: http://chat.codingame.com/pastebin/e89986f8-acf5-4a2d-9074-b44db07f055b

Default avatar.png gtj: не знаю что это за алгоритм моих знаний не хватает умываю руки от этого обсуждения!

Default avatar.png gtj: если кто разбирается с удовольствием попытаюсь понять почему именно эта реализация бфс где и файн и прыжки непойми куда или литературу с удовольствием почитаю на эту тему потомучто бфс все очевидно а тут нет тут поиск в мапе и прыжок

Default avatar.png gtj: вернее в самих реализация бфс дфс все оч очевидно а тут казалось только что очевидно при изменении кода он ведет себя не очевидно

Default avatar.png gtj: написал сам

Default avatar.png gtj: ну не прыжки ок а движекние в соседнюю клетку

vrabosh: tutubalin, а я уже потихоньку забиваю начат из за этого флуда

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

vrabosh: какая здесь тема используется? вроде как норм

tutubalin: даркула скорее всего

tutubalin: открой settings.json, там можешь просто удалить тему, будет дефолтная

tutubalin: либо в настройках просто поиск сделай

vrabosh: нашел, это дефаултная..

vrabosh: но уже и она скажетс не то)

Default avatar.png gtj: Врабошь покажи как ты бфс проходишь

Default avatar.png gtj: tutubalin ты кстати вчера показывал свой алго я не увидел ты сделал без очереди на цикле имитируя цикл и? он тебе все пути возвращает?

Default avatar.png gtj: я мельком смотрел в твой код просто

TeeTeD: господа, а как тут система оценивания работает?

TeeTeD: у меня и у чела по 100 балов, времени он больше затратил, однако он на первом месте

zuko3d: может это гольф?

zuko3d: что за задача?

TeeTeD: хз

TeeTeD: где помотреть?

zuko3d: гольф - это задачи, в которых не кто быстрее, а у кого код короче

TeeTeD: а

TeeTeD: возможно

zuko3d: что за задачу решаешь?

TeeTeD: но он на питоне писал

TeeTeD: там понятное дело код кроче будет

TeeTeD: дан символ и строка, надо нийти сумму индексов элементов строки, которые с символом совпадают

zuko3d: а ссылку прислать можешь?

TeeTeD: я тут впервые, не совсем понимаю как сайт работает

TeeTeD: так что нет

zuko3d: ну вообще обычно всё нормально пашет тут.