|
Задачка про остров
|
|||
---|---|---|---|
#18+
В море находится шестиугольный остров, сотворенный из вертикальных 6-угольных плит, плотно подогнанных друг к другу. Площадь горизонтального сечения каждой плиты равна 1, а высота верхней грани над уровнем моря - некоторое целое число больше 0, отдельно указывается для каждой плиты (на рисунке обозначено цифрами). Есть массив со всеми высотами. Во время прилива остров полностью уходит под воду. Найти суммарный объем воды, который останется в лужах на острове, после отлива. На рисунке оный объем равен 3, вода останется в центральной ячейке и ячейке сверху-справа от неё. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 11:51 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Ограничения на сложность или что-то типа есть? Можно просто решение в лоб: 0) Обозначем "плиты море" = 0 1) Для каждой плиты находим все возможные пути к морю (с условием a[n] > a[n+1]). Для каждой плиты сохраняем массив плит, которые участвовали в путях к морю 2) Находим локальные минумы 3) Для каждого локального минимум рекурсивно обходим его соседей с проверкой, находятся ли они в "чьем-то пути" из первого пункта. Если нет, то добавляем его в лужу. 4) В итоге в лужах находятся группы плит. У каждой лужы находим минимального соседа 5) Объем = Сумма всех групп по (минимальный сосед - высота плиты) ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 12:20 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
SpringMan Ограничения на сложность или что-то типа есть? ну а так - чем меньше, тем лучше) ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 12:24 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Переусложним в первом решении, можно чуть проще: 0) Обозначем "плиты море" = 0 1) Для каждой плиты находим все возможные пути к морю (с условием a[n] > a[n+1]). Для каждой плиты сохраняем флаг "есть или нет выход к морю" 2) Находим локальные минумы 3) Для каждого локального минимум рекурсивно обходим его соседей с проверкой есть ли у него выход к морю. Если выхода к морю тоже нет, то добавляем эту плиту в лужу 4) В итоге в лужах находятся группы плит. У каждой лужы находим минимального соседа 5) Объем = Сумма всех групп по (минимальный сосед - высота плиты) ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 12:32 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Нудно описывать исходные данные. Обычно сотовый порядок узлов хорошо намапливается на матрицу где мы (условно) считаем каждую ячейку 6 связной. Типа Код: sql 1. 2. 3. 4. 5.
... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 12:54 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Если для настоящей картинки (нужна матрица по трем линиям?): рассуждения идут из центра если по шести направлениям высоты выше, то "хорошо". если по одному из направлений высота меньше, переходим на это направление. и снова перебираем пять (или три) направлений. как-то так ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 13:11 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Просто прогаммировать структуры данных с графами - нудотство. Обычно мы пытаемся применять сначала коллекции. Потом hashmaps, потом деревья. Графы идут в самом конце по степени популярности использования. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 15:18 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Просто прогаммировать структуры данных с графами - нудотство. +1 Предлагаю шестигранник сделать квадратным ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 15:27 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Dima T mayton Просто прогаммировать структуры данных с графами - нудотство. +1 Предлагаю шестигранник сделать квадратным ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 15:55 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1 можно и так, только уточнить, что касание углами плотное и воду не пропускает ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 16:12 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Basil A. Sidorov Имя пользователя1 можно и так, только уточнить, что касание углами плотное и воду не пропускает ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 16:32 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1 в шестиугольнике касание сторонами ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 16:49 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Dima T mayton Просто прогаммировать структуры данных с графами - нудотство. +1 Предлагаю шестигранник сделать квадратным +1 В комьютерных играх типа Panzer General игровая поверхность так и задана. Более того там хитрость есть как на квадрате больше ячеек впихнуть. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 17:26 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Перебираем для каждого островка соседей. Если все 6 выше - тут лужа. Все. Всем спасибо все свободны. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 17:31 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Хотя погорячился да.. Все не так.. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 17:33 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Basil A. Sidorov, касание любой пары шестиугольников никому не мешает. а у квадратов, в реальном мире, не может так быть, чтобы А касался D, и в то же время B касался С (см. картинку). Потому отдельное пояснение про углы. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 17:35 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Это копи-паста с одной из олимпиадных задач. Только там дождь капал на квадратные столбы и надо было посчитать высоту луж после дождя. Границы столбов по краям уходили в минус бесконечность тоесть по краям вода стекала вниз. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 17:37 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Хотя погорячился да.. Все не так.. Это в любом случае рекурсия. Изюминка будет в условии выхода. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 17:40 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Мне кажется надо пытаться представить все с точки зрения воды - где она упрется не в море , стекая. А когда эти самые области уже конечное число - вот тут применять сравнение высот и прочее и прочее. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 17:46 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
1. Крайние hexxagons которые упираются в море - надо приравнять к некому минимальному числу типа MIN_INTEGER. 2. Далее должен быть некий цикл по всем оставшимся hexxagons, где мы просто делаем min(x,y) по уровню воды между всеми соседями. 3. Завершаем алгорим когда уровни воды перестали понижаться. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 17:52 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Или я не понял, или 51325 лужу с двумя минимумами вы пропустите. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 18:30 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Так же крайние клетки могут быть разной высоты. Не все так просто. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 18:31 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Что-то типа по капле упало на каждый хекс. И множится она деревом на все клетки, которые ниже текущей. Уплыла в море - вычеркиваем, нет - ищем минимумы. Нашли все минимумы. В каждом минимуме - поднимаем уровень на один. - соответсвенно на все граничные хексы пуляем очередную каплю. И так далее и тому подобное. Куча граничных условий, а если еще и на язык переклывать, не кислая такая программа выйдет. Изящного решения мне не видно пока. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 18:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Хм.. может инвертировать поле - самая высокая клетка становится самой низкой, тогда все локальный максимумы - потенциальные точки для дна лужи. А вот как ее края посчитать, вот это задачка. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 18:40 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1, Можно пойти от противного, закрашивая ячейки сливающиеся в океан цветом "Океан". В лоб: верхний ряд 1,4,3 - "Океан" второй ряд 1, 5, , 5 - "Океан", 1 - нет выхода в океан "Лужа" (все окружающие выше или "Лужа") третий ряд 2, 3, 6 - "Океан", 2 - нет выхода в океан "Лужа" (все окружающие выше или "Лужа"), 4 - неизвестно четвертый ряд 2, 6, 2 - "Океан", 4 - неизвестно пятый ряд 3, 1, 2 - "Океан" обрабатываем оставшиеся, остались две 4-ки, обе получаются "Океан". Можно идти по спирали сначала внутрь, потом наружу, по идее должны закрыть даже сложные случаи, но не уверен. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 18:43 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Первым проходом красим все что смогли, дальше проходим по оставшимся начиная с низших номеров, каждый проход уменьшая количество оставшихся до тех пор пока не останется ни одной ячейки не имеющей статуса "Океан" или "Лужа". ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 18:46 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev второй ряд 1, 5, , 5 - "Океан", 1 - нет выхода в океан "Лужа" (все окружающие выше или "Лужа") но в целом да, к волновому алгоритму (от краёв) дело идет, судя по всему. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 18:50 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1 скорее, предполагаемая лужа. Все площадки вокруг выше, это Лужа определяемая однозначно, также лужа определяется однозначно, если все вокруг выше, либо уже определены однозначно как Лужа. Вопрос только в количестве проходов по оставшимся не определенным на момент итерации площадкам. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 18:55 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Или же умудриться нарезать на круги. Я что имею ввиду с самого верха идем. Отрезали слой, смотрим на него, есть ли там замкнутая фигура (т.е. все точки фигуры выше или такой же высоты и внутри есть область (не важно какая , главное чтобы не пусто было). Все что в замкнутой фигуре, исключаем из последующей итерации. Итого получим группу "Окружностей", которые будут содержать лужи. А там уже для каждой считать объем. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 18:57 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Первым проходом красим все что смогли закрашенная клетка - это не океан, но и не лужа, это клетка, с которой вода утечет. Закрасили клетку, закрашиваем все соседние с ней, которые выше неё или равны ей (как в волновом алгоритме). Тогда всё незакрашенное будет лужами, но среди луж могут возвышаться островки, внутри которых снова могут быть лужи (но это уже другая история). Определим сначала лужи первого порядка, уровень воды в них, а далее доберемся до островов, и т.д. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 18:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Но в реализации это ни разу не просто. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 18:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1 но в целом да, к волновому алгоритму (от краёв) дело идет, судя по всему. неа, после первой "покраски", гоняем циклы по оставшимся неопределенным, начиная с минимальных по высоте, часть площадок на каждой итерации будет переходить из неопределенной в определенное состояние, поэтому каждая следующая итерация будет иметь меньшее количество неопределенных, так до тех пор пока неопределенных не останется. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 18:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Но в реализации это ни разу не просто. эээ, проще некуда. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:00 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Ну если это просто со всякими граничными условиями, то мой алгоритм наиболее оптимальный как мне кажется. Хотя посмотрел бы я на короткую реализацию этого действия. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:01 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Или вы про свой вариант? Мой прочитайте, может понравится. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, Я про свой квадратно-гнездовой алгоритм, на счет как реализовать твой не знаю)) ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Или вы про свой вариант? Мой прочитайте, может понравится. под внешним слоем может оказаться не одна сплошная лужа, а разделенная на несколько секторов, причем эти разделители уходят вглубь, и хрен знает, что там дальше делается... постепенно срезать слои не получится. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:14 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Это копи-паста с одной из олимпиадных задач. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:17 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Или вы про свой вариант? Мой прочитайте, может понравится. На большом поле количество комбинаций кругов будет сравнимо с количеством отдельных площадок, пройти по спирали с внешнего периметра к центру, а потом добивать оставшиеся неопределенные на мой взгляд более оптимально, чем нарезать срезы с кучей кругов. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:17 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Не не. Смотри - первый попавшийся не пустой овал - уже лужа. Просто по определению - внутри него есть клетки ниже и они никак не соединены с морем , потому как отсечены овалом. Для наглядности - найдите здесь какой-то граничный случай (тут горы, а у вас будет наоборот - лужи) http://www.vertikal-pechatniki.ru/bibl/images/clip_image004.jpg Было у тебя поле из 100 хексов, не пустой овал отрезал 10 (его границы). На следующем слое тебе уже придется анализировать 90 хексов. И так далее. Идем сверху а не снизу. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:18 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
На картинке - первый замкнутый овал от края, который попадется - одна большая лужа. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:20 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Если принять жирную черту (реку или что она там значит, за море) то на картинке всего 2 овала. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:21 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Не не. Смотри - первый попавшийся не пустой овал - уже лужа. Просто по определению - внутри него есть клетки ниже и они никак не соединены с морем , потому как отсечены овалом. Для наглядности - найдите здесь какой-то граничный случай (тут горы, а у вас будет наоборот - лужи) http://www.vertikal-pechatniki.ru/bibl/images/clip_image004.jpg Было у тебя поле из 100 хексов, не пустой овал отрезал 10 (его границы). На следующем слое тебе уже придется анализировать 90 хексов. И так далее. Идем сверху а не снизу. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:21 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Сложность алгоритма как раз распонать карту овалов, а нарезать - нет ничего проще. Овал образовался, выкидываем все что внутри овала из следующей итерации, это уже лужа. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:22 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторто есть копать изнутри и находить замкнутые контуры, внутри которых углубления? Но эти контуры нельзя выкидывать, они могут оказаться глубокими впадинами более обширной лужи. Этот контур лужа. Все в нем лужа. Есть конечно вариант что в данном овале 2 лужи. 5343437. Но это вычисляется уже когда объем лужи считать будешь. Я почему ратую за этот алгоритм. Он более нагляден, а оценить предоженный ОраклДевом мысленно не так просто на наличие граничных условий. Кстати способом рекурсии лужа в луже - вычисляется роно тем же алгоритмом как и для начального определения. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:29 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вообще задача детская. Объем моря начальный V1. Объем дождя V2. В лужах осталось = Vморя результирующее - V1 - V2. Всем спасибо все свободны :D ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:33 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
соберу сюда свой вариант, основанный на идеях iOracleDev этапы: 1) закрашиваем все ячейки, с которых вода сливается в море. Сначала все крайние, потом по принципу заражения - если у закрашенной клетки соседняя не ниже, то закрашиваем эту соседнюю. Похоже на волновой алгоритм, только "наизнанку". 2) Остались незакрашенные области - кандидаты в лужи. Обходим по краю, выясняем, где самая низкая стенка (высота Н). Оттуда начинаем закрашивать лужу, по соседним ячейкам, но только такие, которые ниже чем Н. Закрасили лужу, заодно посчитали объем, занесли в копилку. Всё, это отработанные клетки, если их засыпать песком до высоты Н, то они будут как клетки из п.1. Если клетки данной лужи касаются незакрашенных на п.2, то те незакрашенные - остров или полуостров, работаем с ними по п.1. Иначе обрабатывает другую лужу, которая осталась. таким образом мы последовательно добираемся до всех клеток. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:42 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1 1) закрашиваем все ячейки, с которых вода сливается в море. Сначала все крайние, потом по принципу заражения - если у закрашенной клетки соседняя не ниже, то закрашиваем эту соседнюю. Похоже на волновой алгоритм, только "наизнанку". Обход по какому правилу? По правилу поиска выхода из лабиринта? ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:52 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
На словах , на первый взгляд должно работать. А вот с реализацией мне кажется наплачетесь. Ветвистые деревья придется отрабатывать. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 19:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Имя пользователя1 1) закрашиваем все ячейки, с которых вода сливается в море. Сначала все крайние, потом по принципу заражения - если у закрашенной клетки соседняя не ниже, то закрашиваем эту соседнюю. Похоже на волновой алгоритм, только "наизнанку". Обход по какому правилу? По правилу поиска выхода из лабиринта? ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 20:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1 iOracleDev пропущено... Обход по какому правилу? По правилу поиска выхода из лабиринта? ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 20:04 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник На словах , на первый взгляд должно работать. А вот с реализацией мне кажется наплачетесь. Ветвистые деревья придется отрабатывать. всё время так - идея норм., в реализации костыли и подпорки ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 20:05 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Поэтому слезно прошу - посмотрите на мой вариант. Алгоритм один послойный. Тупой как пробка. Самое сложное - найти таки эти окружности, что опять же решается в двумерном пространстве. На каждую лужу - заряжаем опять ровно этот же алгоритм в рекурсии, пока не дойдем до вариант - что луж в остатке нет. Я же не просто так написал, закрашивание оно игтуитивно понятно было с самого начала. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 20:08 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, А чего на него смотреть? mayton кодить хочет постоянно, предложи ему реализовать все три алгоритма и сравнить)) ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 20:12 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, ну вот, например, кейс - где-то посреди острова несколько смежных ячеек 5, окруженных 6-ками и 7-ками. Нашли эту лужу, записали объем, залили цементом. Дальше снова ищем лужи? ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 20:14 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
мой вариант, если выгорит, то тянет на O(N) по вспомогательной памяти - закраска, очередь для поиска и т.д., - и где-то O(5N) по времени - каждую клетку отрабатываем один раз, ничего не ищем. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 20:18 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
автору вот, например, кейс - где-то посреди острова несколько смежных ячеек 5, окруженных 6-ками и 7-ками. Нашли эту лужу, записали объем, залили цементом. Дальше снова ищем лужи? Да не так же. Вы прошли слоями сверху 1 раз. У вас после этого прохода остались скажем 10 луж. Вам надо натравить данный алгоритм на каждую из луж, просто чтобы убедиться, что нет такого что лужа в луже. Пример лужи в луже с кольцевым островком:5393935. Для такого крайнего случая чуть усложнятся вычисления объема. Ну как карты рисуют с высотами, умозрительно срезают слои и сразу видно - здесь пустота здесь земля. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 20:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Вы прошли слоями сверху 1 раз. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 21:21 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
ну сверху в низ вы идете. Грубо у вас скажем набор высот хексов такой 5 7 8 9. Тут получается что есть по уровням для нарезки 4 слоя + нуль (море). На первом слое вы получите двухмерный срез (смотреть сверху на остров). Там будет только один хекс к пример (вершина). Следующий слой - 8. Там уже будет другая картинка на срезе. И так далее. Каждый срез надо посмотреть на наличие замкнутых фигур внутри среза (дырка в бублике или подобное). Дырка в бублике - лужа. Ее выкидываем из последующего расмсотрения (т.е. уменьшаем количество хексов для анализа). Представьте что вы смотрите сверху 2 горы, одна простая , вторая вулкан с жерлом. Если срезать по слою то получится что -то типа картинки внизу. Я уже не знаю как еще объяснить. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 21:54 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
По этой картинке вы на третем шагу вычислите одну лужу (жерло вулкана). Если бы это был не замкнутый контур, то овала внутреннего не было бы. Был бы надгрызенный бублик (прогрызенный до дырки) Типа так ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 21:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вроде как исходные данные. Код: sql 1. 2. 3. 4. 5.
... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 22:00 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Грубо у вас скажем набор высот хексов такой 5 7 8 9. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 22:05 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Вроде как исходные данные. Код: sql 1. 2. 3. 4. 5.
тогда соседние ячейки как раз 22076725 ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 22:09 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторесли что, выбор высот может быть охренительный, сравнимый с количеством ячеек может быть не спорю. Только как это принципиально отличается от слоев в вашем случае? В частности в моем - на каждой итерации уменьшение требуемых обсчетов. И для большинства островов не из фантастики - вполне себе разумно распределяет нагрузку. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 22:15 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
В исходных данных мой алгоритм найдет дырку на 5ом слое. Код: c# 1. 2. 3. 4. 5.
Тут как раз возвращаемся к слабому месту в моем варианте - как эти кольца выявлять. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 22:20 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вобщем закругляясь на сегодня - и Ваш алгоритм вполне себе работоспособен, так же будете крестиками слои закрашивать, ну вернее не слои, и то, куда вода с моря при поднятии постепенном заливается. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 22:24 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник В исходных данных мой алгоритм найдет дырку на 5ом слое. Код: c# 1. 2. 3. 4. 5.
если я правильно понял, то эту дырку выявить на слое, высота которого равна 1, и он срезает всё, кроме 1. но должен быть ещё предыдущий слой высотой 2, который выявит такое: Код: c# 1. 2. 3. 4. 5.
тут у нас бассейн площадью 2, объемом 2 , потому что до этого шел слой высотой 3, который сделал так Код: c# 1. 2. 3. 4. 5.
но тут, и в слоях выше, замкнутых озер не было. итого сколько разных высот, столько и слоёв, правильно? ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 22:42 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev АСУ ТПшник, А чего на него смотреть? mayton кодить хочет постоянно, предложи ему реализовать все три алгоритма и сравнить)) Нет уж. Я не такой всеядный. Позвольте мне все таки самому выбирать что кодить. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 22:42 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, в общем, если при переходе к очередному слою быстро вычислять замкнутые контуры (их площади), то вполне жизненно. Пока не совсем понимаю, как это делать. ну и предварительно надо обойти весь массив ячеек, для каждого слоя наколбасить коллекцию ячеек, которые будут закрашиваться. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 22:51 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторно должен быть ещё предыдущий слой высотой 2, который выявит такое Да все праваильно я упустил, что там тоже 2-ка окружена. А так да - вы правильно ход моих мыслей поняли. Выявится дыра окруженная x состоящая из двух клеток 1 и 2 Код: c# 1. 2. 3. 4. 5.
А на последующей итерации этот кусок уже вывалится из анализа, т.е. он не будет анализировать единичку во второй строке. После прохождения по слоям у вас получится что есть одна лужа. Как ее объем вычислить - разговор отдельный, но вы легко можете тупо почитать вес каждого хекса в данной луже. Но предположим что что-то сложное в луже. /\/\ /\/ \/\ / \ Натравите алгоритм на сию лужу, представив что это такой остров в море (рекурсия). Алгоритм выделит опять лужу. Т.е. в первом проходе выделится слой /\* что между ними пока непонятно* /\ А после рекурсии на этом "новом острове"вы увидите /\/\ ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 22:54 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вообще имхо ваш пример как раз лучше решается вашим способом, но реализация не наглядна и не очевидна будет (куча массиов, подмассивов и так далее). Но вот на больших площадях мой ИМХО нагляднее. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 23:05 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Но предположим что что-то сложное в луже. Код: plaintext 1. 2. 3.
тут самый верхний слой дает маленькую лужу, второй слой даёт большую лужу с островом (если это гора с симметрией вокруг центра). и вот опять же, как быстро считать площади дырок на каждом срезе. ну а мой вариант закрасит внешнюю стену, потом большую лужу и с неё доберется до внутренней горы, которую тоже закрасит, и озеро вверху. Как раз та самая рекурсия. ... |
|||
:
Нравится:
Не нравится:
|
|||
10.02.2020, 23:15 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Я бы еще попробовал классифицировать острова по виду рельефа. - шумящие (решаем только методом грубой силы) - террасы (классифицируем близкие поверхности (плато)) и рассматриваем как 1 узел высоты вершины графа. - лабиринты (где вода физическая может вытекать достаточно долго. Можно попробовать алгоритм "Волны"). ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 00:05 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Сорян. Не смог приаттачить сразу под кат. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 00:06 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Кто захочет поразвлекаться, исходные данные в массиве, списком и графом Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49.
Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75.
... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 01:27 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
автори вот опять же, как быстро считать площади дырок на каждом срезе. Когда у тебя есть массив луж, посчитать мне кажется сравнительно легко. Перебираешь высоты всех хексов, которые лужу окружают, берешь высоту самого маленького (Скажем X). V воды в луже единичного хекса = (X-высота этого хекса)*1 //*1 потому как площадь хекса равна условной единице. Повторить для всех хексов которые в этой луже (т.е. исключить подсписок, который будет после рекурсии - т.е. исключить вложенную лужу, бортики этой лужи сами исключатся, потому что они выше X). ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 02:12 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Задачу можно решать по разному. Можно - как олимпиадную - такими деревянными матрциами и хардкодом топологии. Давайте ее сведем хотя-бы к уровню постнаовки и решения на теории графов. Есть моё предположение что детектирование мостов и связности упрощает эту задачу. Опять-же для некого подмножества исходных данных. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 10:16 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, я их всего этого набора слов гед-то слышал только матрица и графы :) Разверни свой вариант. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 11:53 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Окажи содействие. Преобразуй этот кусок шлака в графовое представление хотя-бы в формате GraphViz. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9.
Я согласен помогать и задачки на графы - интересны но мне часто лень тратить своё время на пустяки. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 11:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Я тоже в сторонке постою, мне не то что лень, но с этими фокусами я мало знаком, а учить ради единоразового представления пятисотую по счету технологию, это только за деньги на работе. Хотя что эт отакое посмотрю конечно, интересно же. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 12:03 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Как будет угодно. Я вообще хотел поднять отдельный топик. В продолжение моих Java Graph Libraries поисковых вопросов. Primary Goal : на посмотреть параллельные алгоритмы на графах (к сожалению еще не выбрал какие). Secondary Goal : java, atomic, locks, не-блокирующие коллекции и структуры данных. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 12:13 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Окажи содействие. Преобразуй этот кусок шлака в графовое представление хотя-бы в формате GraphViz Объекты Hexagon - ноды графа, каждая нода связана с другими (грань связана с другой нодой или null), для реализации алгоритма на жаве самое то. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 12:26 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev mayton Окажи содействие. Преобразуй этот кусок шлака в графовое представление хотя-бы в формате GraphViz Объекты Hexagon - ноды графа, каждая нода связана с другими (грань связана с другой нодой или null), для реализации алгоритма на жаве самое то. Я согласен но я говорю про обобщенные алгоритмы которые могут работать не для хексагонов а для плиток любой геометрии. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 12:28 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Хм. А оказалось ничего сложного осваивать не надо, осталось понять как каждой ноде вес присвоить. http://www.webgraphviz.com Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43.
... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 12:55 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Подправил 41 и 42ую связи "de"->"ce" "ca"->"da" Блин вот красивая картинка. digraph G { "aa"->"ab" "aa"->"ba" "aa"->"bb" "ab"->"bb" "ab"->"bc" "ab"->"ac" "ac"->"bc" "ac"->"bd" "ba"->"ca" "ba"->"cb" "ba"->"bb" "bb"->"cb" "bb"->"cc" "bb"->"bc" "bc"->"cc" "bc"->"cd" "bc"->"bd" "bd"->"cd" "bd"->"ce" "ca"->"cb" "cb"->"cc" "cb"->"da" "cb"->"db" "cc"->"dc" "cc"->"db" "cc"->"cd" "cd"->"de" "cd"->"ce" "cd"->"dc" "da"->"db" "da"->"ea" "db"->"ea" "db"->"eb" "db"->"dc" "dc"->"de" "dc"->"eb" "dc"->"ec" "ea"->"eb" "eb"->"ec" "de"->"ec" "ce"->"de" "ca"->"da" } ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:01 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
нули точно нужны? вся картинка слетит - будет почти от каждого узла в ноль стрелка ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:08 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, я не вижу картинок с хостинга https://d.radikal.ru/ Пожалуйста перепость их куда-то в другое место. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:09 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Сами напросились нуль добавлен. digraph G { "aa"->"ab" "aa"->"ba" "aa"->"bb" "ab"->"bb" "ab"->"bc" "ab"->"ac" "ac"->"bc" "ac"->"bd" "ba"->"ca" "ba"->"cb" "ba"->"bb" "bb"->"cb" "bb"->"cc" "bb"->"bc" "bc"->"cc" "bc"->"cd" "bc"->"bd" "bd"->"cd" "bd"->"ce" "ca"->"cb" "cb"->"cc" "cb"->"da" "cb"->"db" "cc"->"dc" "cc"->"db" "cc"->"cd" "cd"->"de" "cd"->"ce" "cd"->"dc" "da"->"db" "da"->"ea" "db"->"ea" "db"->"eb" "db"->"dc" "dc"->"de" "dc"->"eb" "dc"->"ec" "ea"->"eb" "eb"->"ec" "de"->"ec" "ce"->"de" "ca"->"da" "aa"->"null" "ab"->"null" "ac"->"null" "ba"->"null" "bd"->"null" "ca"->"null" "ce"->"null" "da"->"null" "de"->"null" "ea"->"null" "eb"->"null" "ec"->"null" } https://jpegshare.net/][img=https://jpegshare.net/images/86/d0/86d03158ddfb4e11defdb7c989bae08c.jpg[/img] ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:16 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
[quot АСУ ТПшник#22077547]Сами напросились нуль добавлен. digraph G { "aa"->"ab" "aa"->"ba" "aa"->"bb" "ab"->"bb" "ab"->"bc" "ab"->"ac" "ac"->"bc" "ac"->"bd" "ba"->"ca" "ba"->"cb" "ba"->"bb" "bb"->"cb" "bb"->"cc" "bb"->"bc" "bc"->"cc" "bc"->"cd" "bc"->"bd" "bd"->"cd" "bd"->"ce" "ca"->"cb" "cb"->"cc" "cb"->"da" "cb"->"db" "cc"->"dc" "cc"->"db" "cc"->"cd" "cd"->"de" "cd"->"ce" "cd"->"dc" "da"->"db" "da"->"ea" "db"->"ea" "db"->"eb" "db"->"dc" "dc"->"de" "dc"->"eb" "dc"->"ec" "ea"->"eb" "eb"->"ec" "de"->"ec" "ce"->"de" "ca"->"da" "aa"->"null" "ab"->"null" "ac"->"null" "ba"->"null" "bd"->"null" "ca"->"null" "ce"->"null" "da"->"null" "de"->"null" "ea"->"null" "eb"->"null" "ec"->"null" } посоветуйте такой жу удобный как радикал картинкохранилище без регистраций и прочего... https://jpegshare.net/86/d0/86d03158ddfb4e11defdb7c989bae08c.jpg.html ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:17 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Увы увы. Либо амазон либо гуглдрайв. Последник шарится через веб или нет я не помню. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:24 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Я согласен но я говорю про обобщенные алгоритмы которые могут работать не для хексагонов а для плиток любой геометрии. Не любые плитки могут сложиться также как шестигранники, да и проблем особых нет, я забил константой количество граней, но можно сделать инициализацию массива граней на требуемую размерность и работай себе с любым количеством граней. Другой вопрос в каком формате загонять тестовые данные, для простого примера с обычного плоского массива (который ты сам и предложил))) высот самый оптимальный вариант, сложный пример желательно в чем то рисовать, скидывать в файл и засасывать файл в свою структуру для обсчета. В рисовалках подобных вещей не силен, тем более в их сопряжении с жавой, вообще жавист у нас ты один)) PS: у нас пока вменяемого алгоритма нет даже для шестигранников. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, Ориентация дуг графа у тебя неправильная, каждая дуга будет иметь направление от более высокой плитки к более низкой (путь по которому сливается вода с более высокой плитки), если смотреть со стороны нод то вес дуги для нод к примеру 3 и 9 будет для тройки 6 для девятки -6. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:42 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Поэтому слезно прошу - посмотрите на мой вариант. Алгоритм один послойный. Тупой как пробка. Самое сложное - найти таки эти окружности, что опять же решается в двумерном пространстве. На каждую лужу - заряжаем опять ровно этот же алгоритм в рекурсии, пока не дойдем до вариант - что луж в остатке нет. Я же не просто так написал, закрашивание оно игтуитивно понятно было с самого начала. Ты совершенно прав, идти нужно сверху, также как идет вода при отливе с каждой ступенькой оставляя либо залитые либо сухие плитки. Задача на самом деле несколько сложнее чем показалась сначала, для тестирования нужны случаи, когда есть как минимум три концентрические секции океан - стена - ров - стена - ров - ... - стена - центральное озеро и возможно сухой выступ в середине озера, ведь в каждой луже могут быть выступающие над уровнем незалитые водой плитки. Две концентрические системы должны быть связаны разными кольцами на разном уровне (сообщающиеся сосуды), чтобы вода перетекала из одной системы в другую и глубина заполнения одного из рвов определялась соседней системой, рвы могут быть незамкнутыми кольцами, третья концентрическая система должна быть независимой. В общем задача найти все сухие и все залитые плитки совсем не тривиальная. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:50 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторТы совершенно прав, идти нужно сверху, также как идет вода при отливе с каждой ступенькой оставляя либо залитые либо сухие плитки. Задача на самом деле несколько сложнее чем показалась сначала, для тестирования нужны случаи, когда есть как минимум три концентрические секции океан - стена - ров - стена - ров - ... - стена - центральное озеро и возможно сухой выступ в середине озера, ведь в каждой луже могут быть выступающие над уровнем незалитые водой плитки. Две концентрические системы должны быть связаны разными кольцами на разном уровне (сообщающиеся сосуды), чтобы вода перетекала из одной системы в другую и глубина заполнения одного из рвов определялась соседней системой, рвы могут быть незамкнутыми кольцами, третья концентрическая система должна быть независимой. В общем задача найти все сухие и все залитые плитки совсем не тривиальная. Да все это учтено в моем алгоритме. Посчитать количество воды в луже любой конфигурации не трудно, как только ты знаешь, что внутри лужи другой лужи нет - бублика. Основная сложность найти главные лужи, вот это я и предложил за один проход высчитать. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:54 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторОриентация дуг графа у тебя неправильная, каждая дуга будет иметь направление от более высокой плитки к более низкой Это не ставилось целью мной какбы. Вот вам исходник, делайте что хотите. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:55 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Да все это учтено в моем алгоритме. Посчитать количество воды в луже любой конфигурации не трудно, как только ты знаешь, что внутри лужи другой лужи нет - бублика. Основная сложность найти главные лужи, вот это я и предложил за один проход высчитать. Количество воды не интересно. Вложенных бубликов может быть сколько угодно, ров это тоже лужа, внутри луж могут быть выступы, поэтому я и говорю, задача найти все сухие и все затопленные плитки весьма нетривиальная. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 13:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Это не ставилось целью мной какбы. Вот вам исходник, делайте что хотите. Исходник для расчета я сделал немного выше, шестисвязный список Hexagon, к нему можно итератор приделать, чтобы можно было переходить с ноды на ноду, посмотреть высоту ноды и высоты соседних уже можно сейчас, дело только за алгоритмом, которого пока нет. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:00 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Хммм... Еще раз подумайте над моим алгоритмом, все учтено. И сосуды и прочее. Режем по слоям - где нет замкнутой фигуры - вода польется куда то еще. Ров уровня 0 - будет резать люой бублик и в него уходить будет вода. Кляксу в кляке нарисуйте, соедините их рвом, алгоритм все равно сжует это и не поперхнется - бублики будут рисоваться на срезе рва (т.е. самой низкой точки берега рва)). Если их нет замкнутых - ваша вода утекла в море. Чего уже проще - если фигура замкнута, никуда ничего из нее не потечет. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, Алгоритм поиска всех "замыканий" на уровне, в том числе множественных независимых есть? ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:06 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник digraph G { "aa"->"ab" "aa"->"ba" "aa"->"bb" "ab"->"bb" "ab"->"bc" "ab"->"ac" "ac"->"bc" "ac"->"bd" "ba"->"ca" "ba"->"cb" "ba"->"bb" "bb"->"cb" "bb"->"cc" "bb"->"bc" "bc"->"cc" "bc"->"cd" "bc"->"bd" "bd"->"cd" "bd"->"ce" "ca"->"cb" "cb"->"cc" "cb"->"da" "cb"->"db" "cc"->"dc" "cc"->"db" "cc"->"cd" "cd"->"de" "cd"->"ce" "cd"->"dc" "da"->"db" "da"->"ea" "db"->"ea" "db"->"eb" "db"->"dc" "dc"->"de" "dc"->"eb" "dc"->"ec" "ea"->"eb" "eb"->"ec" "de"->"ec" "ce"->"de" "ca"->"da" } Я сначала тоже стал заполнять шестисвязный список таким образом, но сразу понял что это полный мрак и можно сделать кучу ошибок, взял массив предложенный майтоном и залил с него циклами, к тому же у тебя нет высот (весов) нод. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:10 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Алгоритм поиска всех "замыканий" на уровне, в том числе множественных независимых есть? Что значит замыкания? 1. Первый проход. Определяем резервуары не связаные с морем (изолированные). Выроженный слоучай - тонкая стенка по краям острова, тогда все что внутри один большой резервуар не связанный с морем. То что внутри резервуара, определяется на вотором и последующих шагах в рекурсии. Если ваш резервуар ЛЮБОЙ связан с морем - на одном из разрезов обязательно объявится картинка - связаны - бублика/изолированной фигуры , да хоть кляксы изолированной - не получится. 2. Рекурсией пускаем алгоритм на каждый из резервуаров, представив что этот резервуар и есть новое море, а все что внутри - острова с возможными лужами. Рекурсия нужна как раз для многовложенных случаев. Я просто не знаю как прорисовать что я имею ввиду. авторЯ сначала тоже стал заполнять шестисвязный список таким образом, но сразу понял что это полный мрак угу. Я тоже как начал пытаться что-то придумать, понял что таким образом для 1000 скажем ячеек по 8 сторон - проще застрелиться будет. Как это автоматизировать, не придумал. Как раз сделал, может Майтон чего подскажет по переводу таких веще в графы более легким способом. Сдается мне что такого способа нет. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:20 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Мой алгоритм не срабоает как мне кажется при подземных туннелях между лужами на разные уровни. Во всех остальных случаях должен сработать КМК, ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:24 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Хммм... Еще раз подумайте над моим алгоритмом, все учтено. И сосуды и прочее. Режем по слоям - где нет замкнутой фигуры - вода польется куда то еще. Ров уровня 0 - будет резать люой бублик и в него уходить будет вода. Кляксу в кляке нарисуйте, соедините их рвом, алгоритм все равно сжует это и не поперхнется - бублики будут рисоваться на срезе рва (т.е. самой низкой точки берега рва)). Если их нет замкнутых - ваша вода утекла в море. Чего уже проще - если фигура замкнута, никуда ничего из нее не потечет. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:25 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Определяем резервуары не связаные с морем (изолированные). ... То что внутри резервуара, определяется на вотором и последующих шагах в рекурсии. Имя пользователя1 соберу сюда свой вариант, основанный на идеях iOracleDev этапы: 1) закрашиваем все ячейки, с которых вода сливается в море. Сначала все крайние, потом по принципу заражения - если у закрашенной клетки соседняя не ниже, то закрашиваем эту соседнюю. Похоже на волновой алгоритм, только "наизнанку". 2) Остались незакрашенные области - кандидаты в лужи. Обходим по краю, выясняем, где самая низкая стенка (высота Н). Оттуда начинаем закрашивать лужу, по соседним ячейкам, но только такие, которые ниже чем Н. Закрасили лужу, заодно посчитали объем, занесли в копилку. Всё, это отработанные клетки, если их засыпать песком до высоты Н, то они будут как клетки из п.1. Если клетки данной лужи касаются незакрашенных на п.2, то те незакрашенные - остров или полуостров, работаем с ними по п.1. Иначе обрабатывает другую лужу, которая осталась. таким образом мы последовательно добираемся до всех клеток. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:27 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Хм. Сейчас на свежую голову прикинул. В принципе да... Твой тоже рабочий, но меня что-то смущает, не пойму что. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:34 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Не. Ваш точно должен работать для определения главных луж на острове. Как ни крутил не придмал ситуации где не сработает. PS Предлагаю все таки обсуждать на квадратно гнездовом (суть не меняется, а лишние детали отсекаются) 99999999 95553451 99967899 ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:48 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1соберу сюда свой вариант, основанный на идеях iOracleDev этапы: 1) закрашиваем все ячейки, с которых вода сливается в море. Сначала все крайние, потом по принципу заражения - если у закрашенной клетки соседняя не ниже, то закрашиваем эту соседнюю. Похоже на волновой алгоритм, только "наизнанку". 2) Остались незакрашенные области - кандидаты в лужи. Обходим по краю, выясняем, где самая низкая стенка (высота Н). Оттуда начинаем закрашивать лужу, по соседним ячейкам, но только такие, которые ниже чем Н. Закрасили лужу, заодно посчитали объем, занесли в копилку. Всё, это отработанные клетки, если их засыпать песком до высоты Н, то они будут как клетки из п.1. Если клетки данной лужи касаются незакрашенных на п.2, то те незакрашенные - остров или полуостров, работаем с ними по п.1. Иначе обрабатывает другую лужу, которая осталась. таким образом мы последовательно добираемся до всех клеток. До кодинга руки не дошли, изображу схематично) 0) Рис. 1 - исходная позиция. 1) Рис. 2 - этапом 1, от краев, закрасили в зеленый все клетки, с которых вода сливается. Остались незакрашенные области (иначе выход). И у нас на руках есть граничные ячейки. 2) Рис. 3 - берем область, обходим по периметру, находим самую низкую точку ограды, у неё высота h 3) Рис. 4 - от этой точки закрашиваем те ранее незакрашенные клетки, у которых высота меньше или равна h. С каждой ячейки добавляем в копилку разницу (h - h(ячейки)). Закрасили лужу, вышли к острову, и к тем коричневым областям, с которых вода сливается в эту лужу, и начинаем с ними работать как с береговыми ячейками на старте. ---- закрашивание плоскости - "поиск в ширину", выглядит как распространение огня. обход береговой линии в поисках красной точки - тоже понятно. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:49 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Что значит замыкания? Замкнутые контуры, ноды граничащие с внутренним контуром "замыкания" ниже нод "замыкания". АСУ ТПшник Я просто не знаю как прорисовать что я имею ввиду. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:49 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1, Идти также как идет отлив, т.е. сверху практичнее будет, каждый шаг от воды освобождается новый ярус, вопрос как найти все замкнутые контуры на ярусе. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 14:53 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Согласен с алгоритмом ТС, в таком разрезе он не сложен, будет работать. Как бы в двухмерном мире весь анализ для каждого шага алгоритма. Аплодирую. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 15:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Представим себе, что в каждом ярусе есть ложбинка в которой будет оставаться вода, причем не обязательно замкнутая по всему ярусу, а наверху центральная лужа из которой есть множетственные выступы ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 15:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Давайте усложним задачу. Изначально остров - сухой. Прилив - поднимается до высоты заданной height. Потом - отлив. И надо посчитать какие кратеры и полыньи останутся заполнены. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 15:04 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, Мы эту задачу и решаем, какие плитки отсанутся сухими, какие затопленными, неполное затопление частный случай, мы еще не решили в виде пригодном для реализации базовую задачу. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 15:07 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Представим себе, что в каждом ярусе есть ложбинка в которой будет оставаться вода, причем не обязательно замкнутая по всему ярусу, а наверху центральная лужа из которой есть множетственные выступы Главное, ничего не надо искать. Вся закраска начинается от краёв и переходит ТОЛЬКО на соседние клетки. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 15:10 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Давайте усложним задачу. Изначально остров - сухой. Прилив - поднимается до высоты заданной height. Потом - отлив. И надо посчитать какие кратеры и полыньи останутся заполнены. только останавливаемся в закраске, если наткнулись на ячейку, которая высокая и не скроется приливом. Тут без разницы. Поиск в ширину зайдет куда угодно. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 15:13 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Считаю что задачу на correctness мы уже решили. Она не очень сложная. Давайте на performance. И уйдем от hex-представления в сторону декартова. Какие-бы алгоритмы мы не придумывали всё равно мы оперируем ячейкой (Cell) и ее соседями (Neigbours). Тогда базовым элементом вашего алгоритма будет Код: sql 1. 2. 3. 4. 5. 6. 7.
Для hex-поля количество соседей будет 6. Для пиксельного рисунка что приведен выше - 4. Далее. Тестовые данные. Предлагаю искать картинки с т.н. "картами высот" Их полно в интернетах. Подойдут даже синтетически картики высот из игр. Нам нужен размер хотя-бы от 512х512 пикселов. На картинке должна быть гора или остров с кратерами. Можно брать и ямку но тогда неочевидно будет откуда пойдет океан. Я предполагаю что с краёв картинки. Заодно протестируем рекурсию и потенциальный stackoveflow если таковой вы туда захардкодили. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 15:31 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, я правильно понимаю, что если у ячейки все 4 соседей выше, то вода не выливается? т.е. касание углов плотное и задерживает воду ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 15:35 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Квадратная сетка. Пиксели. 4 соседа. 4х связность. Некуда воде выливаться. Все четко. Ну и треугольная сетка - 3 соседа. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 15:44 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вот образец карты высот. Светлые пиксели - высота выше. Темны - ниже. Где-то в центре картинки находится вершина горы. Для удобства - картинку можно смасштабировать чуть поменьше. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 15:46 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
чтобы затестить алгоритм, нужны не только данные, но и правильные ответы для них ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 16:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
А что разве в топике еще не решили? ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 16:12 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Буду наблюдать за темой. Из чего-то осязаемого, потенциально полезного, уплывает в стороны высоких материй, не имеющих "практического" применения. Есть более приземленная задача (она как бы сплав задач на самом деле, но остальные в силу специфики - нудно и бесполезно объяснять). По идее тоже теория графов. Итак. Дано: резервуарный парк , скажем 200 разного номинала резервуаров с разными продуктами. Они обвязаны задвижками, насосами, флажками блокировки (насос сломан, задвижка не может быть открыта). Куча хитросплетений труб между собой. Задача - написать алгоритм поиска пути для перекачки между двумя резервуарами. Т.е. нужно чтобы путь обязательно проходил через насос и не перекрывал другие открытые пути (параллельная перекачка многих). С виду - алгоритм А* использовать и не парится. Узлы графа могут уметь состояния и так далее (проходной не проходной в данный момент) - качаем по кратчайшему пути через мощнейший насос при прочих равных. Хитрость в том, чтобы минимизировать смешение продуктов (т.е. не использовать насос скажем для ДТ а в следующий момент для бензина - только в крайних случаях). ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 18:40 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, хорошо бы простенький пример, где все нюансы проявятся. и расставить приоритеты, например, что хуже - пустить через более слабый насос, через более длинный путь, или со смешиванием продуктов. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 19:25 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, Вроде такие задачи решаются вот этим инструментом - Динамическое программирование , будущим АСУ ТПшникам в вузах точно преподается)) ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 19:36 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Каюсь. Каждый раз, когда мне эта задача встречается - у заказчика руки опускаются , он даже не может приоритеты важности расставить (привет менеджерам, это технолог делает, когда его в процесс включают, а не пилят ком. пердложения, торговые сделки). Самое примитивное. Оператор тыкает - пустить закачку из Р1 в Р5. Р1-Н2-Р5 (завдвижки я не рисовал) перекроет работу всего остального, а вот если пустить через насос Н1, то Н2 еще можно испльзовать для Р3 Н2 Р6. Р1--|___Н1--|___Р4 Р2--|___Н2--|___Р5 Р3--| |___Р6 Это комплексаная проблема, которую долго можно жевать. Пока никто даже системного подхода не описал народе: 1 Опишите в схеме потсоянные маршруты, котрые будут использоваться всегда. 2 Максимальную длину и так далее и тому подобное. Все сейчас сводится к проверке линий (аля не потекет ли бензин в ДТ, потому что задвижку забыли закрыть или не тот насос запустили). ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 20:24 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
В тему графов. Предложу 2 инварианта. Для данной сущности. Код: java 1. 2. 3. 4. 5. 6. 7.
1) Каков-бы не был уровень воды - уровень земли меньше либо равен уровню воды в этой ячейке. Код: sql 1.
2) Все соседние ячейки с одинаковым уровнем земли (и соседние по отношению к соседним) всегда имеют одинаковый уровень воды. (он может быть неодинаковым в вашем алгоритме на какой-то итерации. Но после достижения стационарного состояния алгоритма в целом - это будет так) Отсюда вытекает интересное преобразование. Группу связных вершин графа имеющих одинаковый параметр height мы можем заменить на 1 единственную вершину топологически связную с соседями данной группы. С точки зрения картинки - не меняется ничего. Но алгоритм упрощается. Мы выбрасываем целое "плато" столбиков с одинаковой высотой и заменяем его на 1 виртуальный столбик который имеет neightbours() существенно больше чем 4 или 6. Но для нас это неважно. Тоесть для ландшафтов с большим количеством плато объем вычислений прилиовов и отливов может быть существенно сокращен за счет такого топологического преобразования. ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 20:51 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
На сколько моих способностей хватило изобразил пример для тестирования ... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 22:24 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Четырехсвязный узел для графа Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51.
... |
|||
:
Нравится:
Не нравится:
|
|||
11.02.2020, 22:48 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник ... Р1--|___Н1--|___Р4 Р2--|___Н2--|___Р5 Р3--| |___Р6 Это комплексаная проблема, которую долго можно жевать. ... Что в задаче навроде переменных (флажки ...), а что навроде относительно статических "справочников" (содержимое Р(i) )?.............. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 00:20 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 АСУ ТПшник ... Р1--|___Н1--|___Р4 Р2--|___Н2--|___Р5 Р3--| |___Р6 Это комплексаная проблема, которую долго можно жевать. ... Что в задаче навроде переменных (флажки ...), а что навроде относительно статических "справочников" (содержимое Р(i) )?.............. Что-то вроде Форда Фалкерсона по расчету потока. Если вентили - неуправляемые. Если управляемые - то неясна цель управления? Максимальная загрузка? Загрузка чего? Насосов? Или всей сети? Тут нельзя так вот небрежно бросаться заданиями. Это-ж неуважение к читающему. Тут люди рады решать головоломки но зачем-же их заставлять додумывать ? ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 00:35 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Задачи в головах. Забейте. Не тратьте время. Было бы все прописано , я бы уже озолотился. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 12:40 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Как будет угодно. Ты если захочешь ее поставить - лучше отдельным топиком. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 12:43 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Четырехсвязный узел для графа Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51.
Тут лучше всё таки не класс а интерфейс. Чтобы иметь разные реализации. Ябы предложил так. Код: java 1. 2. 3.
Что это дает. Это даёт обобщенный алгоритм. И возможность оптимизаций по памяти. +Шаблон Flyweight. Как оптимизация системы хранения. Нам не обязательно хранить Node для каждого пиксела картинки. Достаточно к картинке предоставлять INode интерфейс. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 16:45 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
задаем V = 0; 1) строим ориентированный граф у которого вершины - шестиугольники, а каждое ребро ведет от одной вершины к другой если соответствующие шестиугольники примыкают и высота первого больше чем высота второго. 2) ищем любую вершину которая не примыкает к морю и имеет только входящие ребра, причем хотя бы одно 3) если на 2 вершина не найдена, то результат в V 4) к найденной вершине добавляем к высоте 1 и увеличиваем V на 1 5) повторяем все начиная с шага 1 Можно, конечно, еще оптимизировать, если вместе с найденной вершиной захватывать все которые достижимы из неё (не по нашему графу, а просто по граням шестиугольников) и у которых текущая высота такая же как у найденной и увеличивать не на 1, а на большее значение анализируя прилегающие к ним. ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 21:52 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
fkthat 1) строим ориентированный граф у которого вершины - шестиугольники, а каждое ребро ведет от одной вершины к другой если соответствующие шестиугольники примыкают и высота первого больше чем высота второго. 2) ищем любую вершину которая не примыкает к морю и имеет только входящие ребра, причем хотя бы одно ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 22:08 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1 fkthat 1) строим ориентированный граф у которого вершины - шестиугольники, а каждое ребро ведет от одной вершины к другой если соответствующие шестиугольники примыкают и высота первого больше чем высота второго. 2) ищем любую вершину которая не примыкает к морю и имеет только входящие ребра, причем хотя бы одно Да, точно, не учел. Ну что же буду думать дальше. :) ... |
|||
:
Нравится:
Не нравится:
|
|||
12.02.2020, 23:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
fkthat задаем V = 0; 1) строим ориентированный граф у которого вершины - шестиугольники, а каждое ребро ведет от одной вершины к другой если соответствующие шестиугольники примыкают и высота первого больше чем высота второго. Орграф нас ограничивает IMHO. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 12:34 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
fkthat Можно, конечно, еще оптимизировать, если вместе с найденной вершиной захватывать все которые достижимы из неё (не по нашему графу, а просто по граням шестиугольников) и у которых текущая высота такая же как у найденной и увеличивать не на 1, а на большее значение анализируя прилегающие к ним. Смотрите. По поводу любых идей оптимизирующих или трансформирующих сам граф. Вы должны доказать что ваше преобразование по complexity будет дешевле чем "лобовое" решение задачи сходу. Сюда-же до кучи моё предложение по свёртке одинаковых высот в кучу. Тоесть 2 варианта. 1) Решение задачи 1 раз в лоб любым алгоритмом. 2) Оптимизация ландшафта до некого упрощенного графа. И многокраное решение задачи прилива-отлива. Только я не уверен что автор топика такое многократное решение прилива заказывал. Понимаете да? Это как построение индекса по таблице в БД. Одноразово - неэффективно. А эффективно при периодических использованиях. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 12:47 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Итак, еще один вариант решения. 1) Находим максимальную высоту шестиугольников 2) Каждому шестиугольнику присваиваем число (назовем его "теущей высотой", в отличии от просто "высоты" заданной в условиях задачи) равное максимальной высоте из п.1 3) Начало цикла 4) Ищем любой шестиугольник который имеет "текущую высоту" больше своей "высоты" и либо: а) Граничит с морем б) Имеет хоть один соседний шестиугольник с меньшей "текущей высотой" 5) Если на п.4. мы такого шестиугольник не нашли, то выходим из цикла 6) Иначе, Если на п.4. найден шестиугольник который граничит с морем, то устанавливаем его "текущую высотуо" равную его "высоте" 7) Иначе устанавливаем значение его "текущей высоты" в значение максимальное из его "высоты" и минимальной "текущей высоты" всех его соседей. 8) Возвращаемся в начало цикла 9) Здесь мы вышли из цикла 10) Суммируем по всем шестиугольникам разницы между их "текущей высотой" и "высотой" - это и будет результат (объем луж). ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 13:41 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
вроде верно. Кстати, на определенных этапах корректировка "текущей высоты" будет распространяться от краёв, как тут 22077648 ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 14:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
похоже на вариант с "текущей высотой" - сортируем ячейки по высоте, затем последовательно наполняем каждую дельту высот: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129.
... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 16:37 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Хорошая портянка, мне вот трудно читать, ибо не приучен. А суть в чем? Есть идея - а можно ли перепрыгнуть с точек и их уровней, на наклоны соединений между клетками? Ну т.е. простейший случай - 8657. Два выхода к морю в двухмерном пространстве. 8->6 наклон отрицательный. 6->5 отрицательный.7->5 отрицательный. Наклон может быть суммирующимся. Подозреваю что можно , через суммирование весов каждого наклона типа 8 против 5 - вода не вытечет, но не уверен в целессобразности. Т.е. идея какая - кратчайший путь от центра к низинам или от моря к самой высокой точке по А алгоритму с правилом каким-то, а потом веса наклонов считать. Был пьян, вспылил :D ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 18:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Для всех ячеек и их ближних соседей. Инвариант - вода течет вниз. Ивариант вода не ниже чем дно. Инвариант. Любая вода - не ниже чем океан. Всё остальное - только имплементация этих правил в виде кода + эвристики и предположения. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 19:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторИнвариант - вода течет вниз. Ивариант вода не ниже чем дно. Инвариант. Любая вода - не ниже чем океан. ТЗ какбы само собой (не очень понял при чем тут инвариант). Но вот лужа никогда не нижу уровня моря - "искусственно" несколько, почему бы и нет? Разовью мысль. "Практическое" решение уже нашлось. В области теории всего обо всем,42, оно как бы отсекает абсолютно нейтральный подход - мы не знаем чего будем анализировать. Т.е. получается уже искусственные ограничения для искусственной же задачи. Зачем? Очень уверен, что лужа глубже уровня моря может быть без значительного усложнения. Задача так-то вырождается вообще в простой вопрос. Определить области, откуда при неизменности силы притяжения и барьеров (чтобы вода не текла), остров, вынутый за ручку вверх сможет сохранить часть воды , как-то алгоритмически проанализировать и решить как можно более простым способом. наиболее понятным способом. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 19:23 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Хорошая портянка, мне вот трудно читать, ибо не приучен. А суть в чем? Извини, не смог уложиться в 5 строк. Суть, как сказано в преамбуле перед портянкой, в том, что мы будем вместо одной сложной задачи последовательно решать более простые задачи, по одной для каждого изменения высоты ячейки. АСУ ТПшник Есть идея - а можно ли перепрыгнуть с точек и их уровней, на наклоны соединений между клетками? Ну т.е. простейший случай - 8657. Два выхода к морю в двухмерном пространстве. 8->6 наклон отрицательный. 6->5 отрицательный.7->5 отрицательный. Наклон может быть суммирующимся. Подозреваю что можно , через суммирование весов каждого наклона типа 8 против 5 - вода не вытечет, но не уверен в целессобразности. Т.е. идея какая - кратчайший путь от центра к низинам или от моря к самой высокой точке по А алгоритму с правилом каким-то, а потом веса наклонов считать. Был пьян, вспылил :D С нетерпением жду реализации в 5 строк этой замечательной идеи. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 19:27 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторС нетерпением жду реализации в 5 строк этой замечательной идеи. Вода должна оставаться в луже :D А серьезно - куча реализаций может быть. Но суть в том, что ваш код даже без комментариев. Чего он там и зачем делает, концептуально непонятно, реверс инжиниринг - ну извините, лень. Тут как-то на интуитивно понятном языке обходились пока не влез ОраклДевелопер, который приделал к переменным геттеры и сеттеры ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 19:32 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторчто мы будем вместо одной сложной задачи последовательно решать более простые задачи, Не уследил за изложением в сообщениях. По утру попробую. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 19:36 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник авторС нетерпением жду реализации в 5 строк этой замечательной идеи. Вода должна оставаться в луже :D А серьезно - куча реализаций может быть. Но суть в том, что ваш код даже без комментариев. Чего он там и зачем делает, концептуально непонятно, реверс инжиниринг - ну извините, лень... Их есть у меня: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26.
... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 19:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
У меня где-то была своя имплементация алгоритма diamong-square на С++. Потерял код к сожалению. Но она не для решения этой задачи а просто для генерации реалистичных карт островов. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.02.2020, 23:00 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Портянка немного увеличилась, сделаны 2 изменения: 1) Теперь правильно вычисляется объем среза, когда он содержит сливающиеся ручейки. Чтобы при этом не пострадала скорость, пришлось расширить структуру ячейки. 2) Изменены параметры функции CountCells, чтобы не повторять в ней ранее сделанные вычисления Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148.
... |
|||
:
Нравится:
Не нравится:
|
|||
14.02.2020, 13:41 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
закодю свой вариант, как время будет) ... |
|||
:
Нравится:
Не нравится:
|
|||
14.02.2020, 14:27 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Ой ой ой. ТЗ со входными и выходными данными отсутствует. Предлагаю взять картинку Мэйтона и как-то визуализировать результаты. А то получается как всегда. Классы и мы, тупые АСУТПшники с геттерами сеттреами можем. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.02.2020, 16:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Рекурсивный вариант получился немного короче. Здесь процедуры ReadCells и Neighbour те же, что и в нерекурсивном варианте 22079993 . Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38.
... |
|||
:
Нравится:
Не нравится:
|
|||
14.02.2020, 17:22 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Ой ой ой. ТЗ со входными и выходными данными отсутствует. Предлагаю взять картинку Мэйтона и как-то визуализировать результаты. А то получается как всегда. Классы и мы, тупые АСУТПшники с геттерами сеттреами можем. Предлагаю закрасить синим цветом где океан. Ну и картинку - побольше. На весь экран. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.02.2020, 17:25 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Предлагаю закрасить синим цветом где океан. Ну и картинку - побольше. На весь экран. Океан - ненужная деталь в этой задаче. Есть квадратный остров, за его пределами - минус бесконечность. Результат будет тем же. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.02.2020, 17:36 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Можно взять и нарисовать картинку такого плана 22077903 как и предлагал mayton пиксели-квадраты с четырьмя сторонами, 256 градаций серого, 0-океан, 1-255 разные высоты чем темнее тем выше, хотя можно и инвертировать, кому как нравится, перегнать ее в массив и обработать алгоритмом закрасив в 0 плитки оставшиеся под водой, потом обратно в картинку и сравнивать что получилось. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.02.2020, 17:36 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Если лень формировать графику - воспользуйтесь псевдо-текстовым форматом (PPM) графики. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.02.2020, 17:51 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Мимо проходил, вопрос возник. Соседство такое: - 4 5 это типа м-ца для сотовых ячеек? 2 (ху) 3 - 0 1 Никто не пробовал в полярных координатах мыслить? мне показалось соседство натуральнее будет, а то в матрице вроде прыгает туда-сюда, хотя бы уж по кругу пустили как в полярных. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.02.2020, 20:50 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 Мимо проходил, вопрос возник. Соседство такое: - 4 5 это типа м-ца для сотовых ячеек? 2 (ху) 3 - 0 1 Никто не пробовал в полярных координатах мыслить? мне показалось соседство натуральнее будет, а то в матрице вроде прыгает туда-сюда, хотя бы уж по кругу пустили как в полярных. Я иногда. Рассеяно разглядывая глобус думаю что полярная сетка координат - хреновая идея. Вот если взять икосаэдр. И натянуть его на глобус. А потом образующие его треугольники разбить еще на 4 треугольника. И т.д рекурсивно. То мы получаем вполне себе красивую систему координат икосаэдральной системы. Где нет дефекта искажения координат как на полюсах. Равномерно по всей поверхности треугольнички будут примерно равны. Хотя где-то в узловых точках искосаэдра где сходятся в 1 точке 5 треугольников они будут не совсем равносторонние. Но это пустяк ИМХО. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.02.2020, 21:01 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
В задаче как раз "нет дефекта искажения координат", всё на плоскости. Соседи только по окружности ( а это номер угла) и по радиусу (это вообще +-1). Ещё по прямым (квазикасательные к окружностям == секущие их в 2-х точках). Вот и все 6 направлений. Всё очень естественно. Лежит в той же м-це только по кругу, но я не навязываю. Может автор матрицы так и мыслил, из матрице только не скажешь. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.02.2020, 21:28 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Остров мог быть не шестиугольный. Могла быть система островов с изломанной береговой линией. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.02.2020, 22:53 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov Рекурсивный вариант получился немного короче. Здесь процедуры ReadCells и Neighbour те же, что и в нерекурсивном варианте 22079993 . Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38.
Давайте поставим более широко задачу. Допустим наш остров имеет очень мелкую и точную детализацию высот. Даже не 1000х1000 пикселов а давайте зададим в 1млн на 1 млн. Вобщем давайте подумаем о параллелизме основного алгоритма. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.02.2020, 23:45 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторЕсть квадратный остров, за его пределами - минус бесконечность. Как бы абсолютно согласен, но есть просьба, без кода на словах. Потому как концептуально обсуждаем все же. Никаких утилитарных применений не предвидится. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 00:04 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Давайте поставим более широко задачу. Допустим наш остров имеет очень мелкую и точную детализацию высот. Даже не 1000х1000 пикселов а давайте зададим в 1млн на 1 млн. Вобщем давайте подумаем о параллелизме основного алгоритма. Зачем? Теоретически высота одного угла может влиять на решение в другом. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 00:13 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Параллелизм на графовых задачах - это сложная тема. Это - челендж. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 10:05 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, если на пальцах, то: Рекурсивный алгоритм 22080232 работает со "срезающими" ячейками. Так мы назовем те ячейки, которые срезают уровень воды в соседних ячейках до своей высоты или своего уровня воды (до того, что выше). После всех возможный срезаний сложим объем воды в каждой ячейке и получим ответ. Чтобы уменьшить объем вычислений и обезопаситься от зацикливания, мы предварительно отсортируем ячейки по высоте. Сначала объявим срезающими все граничные ячейки и ячейку максимальной высоты. Множество срезающих ячеек может пополняться в ходе вычислений. Основной цикл перебирает ячейки в отсортированном массиве и для каждой срезающей ячейки вызывает процедуру среза, которая, перебирая ее соседей, делает следующее: 1) если уровень воды в соседе ниже или равен срезу, то пропускаем соседа, 2) если высота соседа выше среза, то объявляем соседа срезающей ячейкой, 3) иначе срезаем уровень воды в соседе и для него вызываем процедуру среза. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 11:41 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov, Соседних? Замкнутые контуры он как отработает? ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 15:07 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Все таки самый правильный вариант идти сверху срезая по слоям, и разделяя ячейки на сухие и затопленные, начинаем с максимальной высоты острова (если начинать не с максимальной, то замкнутые контуры на первом шаге будут сухими), ВСЕ площадки не имеющие статуса и равные текущему срезу объявляются сухими сразу, далее мы должны найти все замкнутые контуры на срезе равные по высоте срезу, ячейки внутри контуров, которым не присвоен статус сухие, получают статус затопленные. Опускаемся на уровень ниже и проделываем ту же процедуру, ячейки со статусом затопленные в рассмотрение не принимаются, ячейки со статусом сухие могут образовывать контур, статусы установленные на предыдущих уровнях изменению не подлежат, они окончательные. Вопрос только в том как искать замкнутые контуры на уровнях, т.е. контуры у которых высота равна высоте среза или они уже имеют статус сухие. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 15:29 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Проходим по текущему срезу по периметру и ставим временный статус под водой на данном этапе отлива, всем ячейкам до которых сможем добраться проходя от периметра вглубь, ячейки с высотой равной срезу не переходим, таким образом у нас будут три градации на уровне, ячейки у которых ранее поставлен статус сухие и ячейки равные по высоте срезу - сухие окончательно и бесповоротно, ячейки до которых смогли добраться от периметра на данном срезе - временный статус под водой на данном этапе, на следующих шагах этот статус не учитывается, все оставшиеся без статуса ячейки это ячейки внутри контуров и ниже высоты среза, присваиваем им окончательный статус - под водой. Нужен хороший алгоритм обхода от периметра в глубину всех связанных ячеек имеющих уровень ниже уровня среза. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 15:47 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Поиск в ширину для каждого среза, для каждой точки периметра которая не имеет статус сухая и не была найдена в поиске для предыдущих точек, перед обработкой следующего среза временный статус под водой сбрасывается. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 15:56 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Здесь под спойлером исправленный рекурсивный алгоритм, он заметно быстрее нерекурсивного. Оба алгоритма выдают одинаковый результат на больших массивах случайных данных, что, по-видимому, означает, что в них одинаковое количество одинаковых ошибок ) Для больших массивов имеет смысл переписать процедуру SortCells, заменив сортировку вставками на быструю сортировку. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41.
... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 16:44 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Соседних? Замкнутые контуры он как отработает? Все ячейки по границе контура станут срезающими и срежут уровень внутри контура. iOracleDev Все таки самый правильный вариант идти сверху срезая по слоям. Это приведет к лишней работе по многократному срезу уровня в ячейках. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 16:54 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Остров мог быть не шестиугольный. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 17:56 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov Все ячейки по границе контура станут срезающими и срежут уровень внутри контура. Внутри контура не обязательно все ниже, там могут быть дургие контуры, а в них еще контуры, не совсем понимаю каким образном наружные срежут все внутри, глубина лужи может быть маленькой, а лужа при этом очень высоко. iOracleDev Это приведет к лишней работе по многократному срезу уровня в ячейках. Мы не будем рассматривать ячейки статус которых уже точно определен, по крайней мере описанный алгоритм логически понятен и даст верный результат, алгоритм с сортировкой по высоте меня сразу настораживает, каким образом он обработает многократно вложенные замкнутые контуры? ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 20:15 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Aleksandr Sharahov Все ячейки по границе контура станут срезающими и срежут уровень внутри контура. Внутри контура не обязательно все ниже, там могут быть дургие контуры, а в них еще контуры, не совсем понимаю каким образном наружные срежут все внутри, глубина лужи может быть маленькой, а лужа при этом очень высоко. iOracleDev Это приведет к лишней работе по многократному срезу уровня в ячейках. Мы не будем рассматривать ячейки статус которых уже точно определен, по крайней мере описанный алгоритм логически понятен и даст верный результат, алгоритм с сортировкой по высоте меня сразу настораживает, каким образом он обработает многократно вложенные замкнутые контуры? Для внутренних контуров будет все то же самое: когда срезание дойдет до ячейки внутреннего контура, эта ячейка будет помечена как срезающая. А сортировка по высоте значительно ускоряет работу. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 20:31 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Рекурсивный алгоритм можно еще упростить. Специальный признак срезающей ячейки не требуется, Вместо него можно использовать проверку на равенство высоты ячейки и высоты уровня воды в этой ячейке. Завтра приведу окончательный вариант. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.02.2020, 23:57 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Здесь оптимизированный вариант решения: 1. Сортировка вставками заменена на сортировку подсчетом массива координат ячеек, теперь сортировка почти не влияет на время работы. 2. Рекурсия заменена циклом, для возврата в прежнее состояние запоминаем 1-байтовое направление, теперь нам не грозит переполнение стека на больших N. 3. Вычисление координат соседей выполняется непосредственно в теле процедуры SetLevel с использованием массива констант, стало считать чуть быстрее. 4. Размеры структур уменьшены, чтобы можно было оценить время работы с ростом N, теперь остров размером 10000х10000 считается за 6 сек. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.02.2020, 21:46 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov теперь остров размером 10000х10000 считается за 6 сек. Осталось узнать правильно или нет)) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.02.2020, 22:10 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev, оно совпало с предыдущими ) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.02.2020, 22:14 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov оно совпало с предыдущими ) А с правильными совпало?)) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.02.2020, 22:19 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton правильную вещь предлагал, упростить до квадратов и использовать 22080256 . ... |
|||
:
Нравится:
Не нравится:
|
|||
17.02.2020, 22:21 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev, предыдущие были проверены на двух небольших примерах, посчитанных вручную. Было здорово сравнить с другим автором, но где ж его взять ) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.02.2020, 22:24 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev mayton правильную вещь предлагал, упростить до квадратов и использовать 22080256 . 1) нафига упрощать до квадратов? что мешает посто сдвинуть четные строки вправо и решать в шестиугольниках? тут изюминка в громадной рекурсии, от которой надо избавиться. 2) чем это лучше случайных данных или специального маленького замудренного примера? все равно придется эту хрень считать независимым способом. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.02.2020, 22:30 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov, а можешь выложить карты и результаты к ним в виде файликов. Я планирую на неделе докодить свой вариант 22077648 и сразу сравнить. У тебя ведь 6-угольники? Надо утвердить формат карты ) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.02.2020, 22:41 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1, через часок выложу ... |
|||
:
Нравится:
Не нравится:
|
|||
17.02.2020, 22:43 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov, Декартова система координат с прямоугольной сеткой - легче визуализируется. А визуализация даёт вам возможность контроля. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.02.2020, 22:56 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, шестиугольники тоже нормально визуализируются и контролируются вот реальные результаты для острова 10х10 Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.02.2020, 23:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1, кстати я подумал, зачем передавать файлы? Гораздо проще сравнивать результаты для 3х параметров, с помощью которых генерируем карту: RandSeed, RandRange, XCount (YCount=XCount). Процедура генерации карты: Код: pascal 1. 2. 3. 4. 5. 6. 7.
Связность ячеек понятна из моего предыдущего сообщения 22081766 ... |
|||
:
Нравится:
Не нравится:
|
|||
17.02.2020, 23:48 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Код датчика случайных чисел в Delphi Код: pascal 1. 2. 3. 4. 5.
... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 00:08 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov кстати я подумал, зачем передавать файлы? кстати, твой алгоритм сможет проглотить добавку от Майтона? 22077662 ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 00:19 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1 Aleksandr Sharahov кстати я подумал, зачем передавать файлы? кстати, твой алгоритм сможет проглотить добавку от Майтона? 22077662 Чтобы сверить результаты, достаточно передать 3 параметра, которые полностью определяют сгенерированный файл. Добавку от Майтона он не проглотит, придется модифицировать одну строчку. Ну и неясность некоторая имеется: волна высотой 3 перевалит через гору высотой 3 или нет? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 00:25 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov кстати я подумал, зачем передавать файлы? Чтобы визуально оценить результат глядя на сгенерированную картинку, например загоняем файл с теми вариантами которые хотим проверить, обсчитываем, генерим результирующую картинку и сравниваем. Пример картинки 160x120 256 бит ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 00:45 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Aleksandr Sharahov кстати я подумал, зачем передавать файлы? Чтобы визуально оценить результат глядя на сгенерированную картинку У нас нет такой задачи как "визуально оценить". Ну, оценил визуально: вроде похоже на то, что ожидается. А что дальше: верно или неверно? У нас 2 другие задачи. 1) отладить программу на заранее точно просчитанных примерах. 2) сравнить результаты участников. Обе задачи можно решить, передавая параметры алгоритма генерации карты и ответ. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 09:49 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Как будет угодно. Но чем бы вы не занимались и что-бы вы не программировали. А визуальная оценка корректности резульатата нужна постоянно. И я сильно сомневаюсь что все из присутствующих пишут модульные тесты. А битмап я предлагал в совокупности с оптимизацией "островной задачи" с учотом возможностей параллелизма. Вы же не собираетесь оценивать параллелизм на этих мелких текстовых файлах? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 10:08 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Как будет угодно. Но чем бы вы не занимались и что-бы вы не программировали. А визуальная оценка корректности резульатата нужна постоянно. И я сильно сомневаюсь что все из присутствующих пишут модульные тесты. А битмап я предлагал в совокупности с оптимизацией "островной задачи" с учотом возможностей параллелизма. Вы же не собираетесь оценивать параллелизм на этих мелких текстовых файлах? Опять же: зачем пытаться параллелить все подряд? Эта задача и параллелится плохо и ее решение в одном потоке в максимальной размерности займет примерно 1 мин. Тут это ни к чему. Кстати есть мысли, как еще ускорить, как будет время попробую реализовать. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 10:18 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
За способность чего-то "распараллелится" - платят деньги. Собственно ... это тренд нашего десятилетия. Хотя внутренне - я с вами согласен. Графовые задачи вообще плохо параллелятся. В этом и челлендж. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 10:29 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov У нас нет такой задачи как "визуально оценить". Ну, оценил визуально: вроде похоже на то, что ожидается. А что дальше: верно или неверно? У нас 2 другие задачи. 1) отладить программу на заранее точно просчитанных примерах. 2) сравнить результаты участников. Обе задачи можно решить, передавая параметры алгоритма генерации карты и ответ. Где взять заранее точно просчитанные примеры нужной сложности и имеющие именно тот рельеф который нужно проверить? Параметры генерации карты не дадут карту нужного рельефа, нам не нужна случайная карта, нужна карта со специально нарисованным рельефом реализующим различные сложные случаи, тестирование не делается случайным образом, при тестировании проверяют вполне конкретные ситуации. Визуализация даст и вам и остальным понять правильно ли отработал алгоритм конкретно заданный случай. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 15:12 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Где взять заранее точно просчитанные примеры нужной сложности и имеющие именно тот рельеф который нужно проверить? Хороший вопрос. У вас есть ответ? iOracleDev Параметры генерации карты не дадут карту нужного рельефа, нам не нужна случайная карта, нужна карта со специально нарисованным рельефом реализующим различные сложные случаи, тестирование не делается случайным образом, при тестировании проверяют вполне конкретные ситуации. Разумеется. iOracleDev Визуализация даст и вам и остальным понять правильно ли отработал алгоритм конкретно заданный случай. Можно пример? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 15:42 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov Можно пример? Выше нарисован. Было бы очень неплохо чтобы можно было скормить на обработку графический или ppm файл 256 градаций серого и получить на выходе файл у которого все пиксели оставшиеся под водой имеют белый цвет. mayton, Нет примера, как в java получить двумерный байт-массив из битмапа или ppm, второй наверное даже лучше? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 15:51 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Выше нарисован. цветастый он какой-то ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 15:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov цветастый он какой-то сохранял как 256 градаций серого в свойствах 8 бит и по размеру похоже, не знаю почему он цветастый, в графике не разбираюсь)) ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 16:06 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
С ppm очень просто. Это текстовый файл. В бинарными форматами - вот образец. Записывает шум. И пытается прочитать. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Для серого - будет тоже самое наверное только тип картинки поставить в TYPE_BYTE_GRAY. Но я с ним не работал. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 16:07 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
PPM хорошо описан тут https://ru.wikipedia.org/wiki/Portable_anymap ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 16:08 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Было бы очень неплохо ... получить на выходе файл у которого все пиксели оставшиеся под водой имеют белый цвет. При отладке без графической визуализации я получаю даже больше, выводя в мемо количество воды, которое набрал каждый шестиугольник матрицы. В общем, каждый отлаживается на свой вкус и цвет. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 16:34 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Как будет угодно. Я просто в этой задаче увидел элемент технологии из game-dev. Поэтому художнику по дизайну ландшафтов будет очень презентативно увидеть результат как его показывают такие приложения как CorelBryce, RealWorldTerran e.tc. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.02.2020, 16:44 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov Имя пользователя1 Добавку от Майтона он не проглотит, придется модифицировать одну строчку. Ну и неясность некоторая имеется: волна высотой 3 перевалит через гору высотой 3 или нет? ... |
|||
:
Нравится:
Не нравится:
|
|||
19.02.2020, 10:51 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1 Aleksandr Sharahov пропущено... Добавку от Майтона он не проглотит, придется модифицировать одну строчку. Ну и неясность некоторая имеется: волна высотой 3 перевалит через гору высотой 3 или нет? Тогда рассмотрим оба варианта, при условии, что вода поднимается до уровня 3. 1. Когда перевалит. Заливаем всю карту водой без ограничений. Если теперь мы просуммируем воду по всем ячейкам, то получим решение исходной задачи, а если просуммируем по ячейкам, в которых уровень воды равен 3 и ниже, то получим решение для Майтон-1. Ведь в этом варианте ячеек с уровнем воды 4 и выше просто не может быть. 2. Когда не перевалит. Рассуждаем аналогично. Если просуммируем по ячейкам, в которых уровень воды равен 2 и ниже, то получим решение для Майтон-2. Ведь в этом варианте ячеек с уровнем воды 3 и выше просто не может быть. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.02.2020, 11:25 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov, В словесном описании есть алгоритм? ... |
|||
:
Нравится:
Не нравится:
|
|||
19.02.2020, 13:53 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Aleksandr Sharahov, В словесном описании есть алгоритм? Попробую суммировать здесь. Данные ячейки: H=высота, L=уровень воды. 1. Инициализация. Читаем карту высот, присваивая H. В каждой ячейке на границе карты полагаем L:=H, в остальных L:=+бесконечность 2. Заполнение водой. Обходим все ячейки в цикле в порядке возрастания H. Для задачи в формулировке Майтона обход заканчиваем досрочно при встрече первой ячейки с H=M (уровень прилива). Если в процессе обхода обнаружим, что у ячейки L=H, то вызываем процедуру среза, передавая эту ячейку параметром. 3. Подсчет объема воды. Для задачи в исходной формулировке суммируем все разности (L-H), для формулировки Майтона суммируем только те разности, у которых L<M. Процедура среза. Устанавливаем уровень среза C=L ячейки-параметра. Для всех ячеек-соседей, у которых L>C, делаем одно из двух: а) если H>C, то устанавливаем L:=H б) иначе устанавливаем L:=C и вызываем для этого соседа процедуру среза. Понятно, что от рекурсии в процедуре среза можно избавиться. Доказательство корректности алгоритма оставляю читателю ) ... |
|||
:
Нравится:
Не нравится:
|
|||
19.02.2020, 14:49 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Я думаю о параллелизме острова. Пока - мысли. Даже не тезисы а просто мысли. 1. Чтоб эффективно параллелить обработку матрицы высот (HeightMatrix) мне нужна гарантия что каждый процесс (поток) владеет своей частичкой матрицы. 2. Если остров представлен квадратной матрицей - то мы его можем разделить на 4 квадранта. Как разделить? Провести искусственную высоту равную +MAX_INT по вертикали и по горизонтали через центр. 3. Можно применить алгортм заливки водой каждого квадратнта одновременно (4 процесса запроцессят каждый свою матрицу данных). 4. После финала 4х процессов я убираю искусственные стенки. Я их понижаю до исходного уровня. И повторяю 1 общий алгоритм для всего острова. 5. Моя идея базируется на предположении что 80% работы по переливанию воды уже выполнены на шаге (3) и осталось только слегка подкорректировать водичку в "кратерах" и "ямках". ... |
|||
:
Нравится:
Не нравится:
|
|||
19.02.2020, 16:01 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
По визуализации. Та чёрно-белая картинка которую я запостил - неудачна. Она представляет собой гору. А мне нужно архипеллаг островов. И желательно с ямками. Побольше ямок. Для визуализации алгорима желательно Grayscale картинку трансформировать в географическую. С цветовой маркировкой как принято в картографии. Потом если океан залить синим цветом поверх такой карты - то будет очевидно где мы залили. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.02.2020, 16:08 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Я думаю о параллелизме острова... Идея очевидная, и легко реализуемая. Но отсутствует гарантия ускорения, можно нарваться на полный пересчет. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.02.2020, 16:34 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov mayton Я думаю о параллелизме острова... Идея очевидная, и легко реализуемая. Но отсутствует гарантия ускорения, можно нарваться на полный пересчет. Ну это то о чем я говорил. Графовые алгоритмы вообще *уево параллелятся. Но нам повзло. У нас есть некая пространственная когерентность. Тоесть группа вершин может быть легко разделена или сгруппирована по декартовому признаку. В полно-связном графе например это сделать нельзя. А в для 6-связного (хексагоны) или для 4 связной вершины (пиксели) - очень даже удобно. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.02.2020, 16:39 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov iOracleDev Aleksandr Sharahov, В словесном описании есть алгоритм? Попробую суммировать здесь. Данные ячейки: H=высота, L=уровень воды. 1. Инициализация. Читаем карту высот, присваивая H. В каждой ячейке на границе карты полагаем L:=H, в остальных L:=+бесконечность 2. Заполнение водой. Обходим все ячейки в цикле в порядке возрастания H. Для задачи в формулировке Майтона обход заканчиваем досрочно при встрече первой ячейки с H=M (уровень прилива). Если в процессе обхода обнаружим, что у ячейки L=H, то вызываем процедуру среза, передавая эту ячейку параметром. 3. Подсчет объема воды. Для задачи в исходной формулировке суммируем все разности (L-H), для формулировки Майтона суммируем только те разности, у которых L<M. Процедура среза. Устанавливаем уровень среза C=L ячейки-параметра. Для всех ячеек-соседей, у которых L>C, делаем одно из двух: а) если H>C, то устанавливаем L:=H б) иначе устанавливаем L:=C и вызываем для этого соседа процедуру среза. Понятно, что от рекурсии в процедуре среза можно избавиться. Доказательство корректности алгоритма оставляю читателю ) 1) основное отличие от 22079233 - там каждый раз ищется подходящая ячейка на п.4 и далее обрабатывается, а у тебя в процедуре среза в пункте (б) начинается рекурсия с обработкой соседних ячеек? 2) рекурсия заменена либо на "поиск в ширину" (с очередью), либо на "поиск в глубину" (со стеком)? ... |
|||
:
Нравится:
Не нравится:
|
|||
19.02.2020, 16:45 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1 Aleksandr Sharahov пропущено... Попробую суммировать здесь. Данные ячейки: H=высота, L=уровень воды. 1. Инициализация. Читаем карту высот, присваивая H. В каждой ячейке на границе карты полагаем L:=H, в остальных L:=+бесконечность 2. Заполнение водой. Обходим все ячейки в цикле в порядке возрастания H. Для задачи в формулировке Майтона обход заканчиваем досрочно при встрече первой ячейки с H=M (уровень прилива). Если в процессе обхода обнаружим, что у ячейки L=H, то вызываем процедуру среза, передавая эту ячейку параметром. 3. Подсчет объема воды. Для задачи в исходной формулировке суммируем все разности (L-H), для формулировки Майтона суммируем только те разности, у которых L<M. Процедура среза. Устанавливаем уровень среза C=L ячейки-параметра. Для всех ячеек-соседей, у которых L>C, делаем одно из двух: а) если H>C, то устанавливаем L:=H б) иначе устанавливаем L:=C и вызываем для этого соседа процедуру среза. Понятно, что от рекурсии в процедуре среза можно избавиться. Доказательство корректности алгоритма оставляю читателю ) 1) основное отличие от 22079233 - там каждый раз ищется подходящая ячейка на п.4 и далее обрабатывается, а у тебя в процедуре среза в пункте (б) начинается рекурсия с обработкой соседних ячеек? 2) рекурсия заменена либо на "поиск в ширину" (с очередью), либо на "поиск в глубину" (со стеком)? 1) Отличий много, и да, у меня начинается рекурсия. 2) Пофигу, у меня цикл в глубину с запоминанием направления возврата. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.02.2020, 17:12 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Взял картинку 22077693 , инвертировал (у меня чем более темный пиксель тем больше высота, так воспринимать картинку лучше), обработка с параметрами 30 - уровень океана после отлива, 100 - уровень до которого поднималась вода. Картинку для форума пережал в jpg меньшего размера, на ней много артефактов сжатия. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.02.2020, 22:13 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev, визуально) но из-за сжатия невозможно оценить правильность работы ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 00:00 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov, Погонял по высотам и по своим картинкам с концентрическими системами, вполне себе адекватно работает, правда медленно. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 00:20 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Aleksandr Sharahov, Погонял по высотам и по своим картинкам с концентрическими системами, вполне себе адекватно работает, правда медленно. у меня 22083065 самый быстрый из 3х проверенных, его гонял? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 10:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov iOracleDev Aleksandr Sharahov, Погонял по высотам и по своим картинкам с концентрическими системами, вполне себе адекватно работает, правда медленно. у меня 22083065 самый быстрый из 3х проверенных, его гонял? Хвастун. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 12:08 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, ты не понял: имелось в виду из 3х *моих* проверенных ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 12:19 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov mayton, ты не понял: имелось в виду из 3х *моих* проверенных Ладно не обижайся. Я шучу. Пятница все таки. Над параллелизмом думал? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 12:27 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov у меня 22083065 самый быстрый из 3х проверенных, его гонял? Нет конечно, гонял свой с последовательными срезами сверху, правда считал не на массиве а на связном списке узлов, внутри узла массив из соседей и геттер, плюс очередь использовал, просто на массиве должно быть намного быстрее. Сложность алгоритма K*N, где K - количество уровней, N - количество плиток, распарралелить думаю не получится, следующий уровень зависит от предыдущего, хотя надо подумать, наверное можно посчитать каждый срез как будто он единственный, а потом последовательно наложить начиная сверху, тогда распараллелится очень хорошо. Твой я не понимаю, за счет чего он должен выбираться из кратеров? Ты для каждой плитки ищешь выход в океан? Как определяешь что не попал в loop по плиткам? Как выходишь за пределы стены кратера, при условии неограниченной вложенности кратеров и их уровней? Сколько проходов по каждой плитке и от чего зависит, какая временная сложность алгоритма? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 12:31 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov ты не понял: имелось в виду из 3х *моих* проверенных Берешь картинку и вперед)) картинка от mayton-а не очень хорошая для проверки, она большая но сложных случаев, чтобы было сразу видно ошибки, на ней нет. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 12:34 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Над параллелизмом думал? А что там думать, трясти надо. Если на 4 части резать, то: 1) для каждого из 4 квадратов решаем немного измененную задачу со срезающими ячейками только по 2 внешним сторонам (результат не подсчитываем), 2) объединяем соседние решения по 2, запуская процедуру среза и примыкающих ячеек, 3) объединяем половинки, запуская процедуру среза и примыкающих ячеек. 4)считаем результат Но мне интереснее отжать текущую реализацию без разрезаний. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 12:42 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov 3) объединяем половинки, запуская процедуру среза и примыкающих ячеек. Если ячейка из середины одной секции имеет выход в океан через пару других секций? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 12:47 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov mayton Над параллелизмом думал? А что там думать, трясти надо. Если на 4 части резать, то: 1) для каждого из 4 квадратов решаем немного измененную задачу со срезающими ячейками только по 2 внешним сторонам (результат не подсчитываем), 2) объединяем соседние решения по 2, запуская процедуру среза и примыкающих ячеек, 3) объединяем половинки, запуская процедуру среза и примыкающих ячеек. 4)считаем результат Но мне интереснее отжать текущую реализацию без разрезаний. Хорошо. Отжимай. Я попробую на этих выходных что-то написать. Неделька выдалась бешеная. Этой задаче я мог эпизодически уделять по 5 мин времени в сутки. +У меня еще штук 5 интересов "около" этого. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 12:49 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Твой я не понимаю, за счет чего он должен выбираться из кратеров? Ты для каждой плитки ищешь выход в океан? Как определяешь что не попал в loop по плиткам? Как выходишь за пределы стены кратера, при условии неограниченной вложенности кратеров и их уровней? Сколько проходов по каждой плитке и от чего зависит, какая временная сложность алгоритма? 1. Выход из кратера за счет того, что его "берега" выше "долины", значит, они будут помечены как точки среза, от которых потом будут образованы новые срезы. 2. Зацикливания нет, т.к. мы все время идем в сторону увеличения уровня при вызове процедуры среза и внутри нее. 3. Выход за пределы стены с помощью стены, т.к. новый срез образуется из нее. 4. Один проход по каждой плитке (1 срезание), хотя проверок от соседей может быть больше. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 12:56 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov А что там думать, трясти надо. Если на 4 части резать, то: 1) для каждого из 4 квадратов решаем немного измененную задачу со срезающими ячейками только по 2 внешним сторонам (результат не подсчитываем), 2) объединяем соседние решения по 2, запуская процедуру среза и примыкающих ячеек, 3) объединяем половинки, запуская процедуру среза и примыкающих ячеек. 4)считаем результат 3 четвертинки придется пересчитывать по уровню затопления, когда будем объединять. То есть ничего не выигрываем в данном случае. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 13:00 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Aleksandr Sharahov 3) объединяем половинки, запуская процедуру среза и примыкающих ячеек. Если ячейка из середины одной секции имеет выход в океан через пару других секций? Для моего алгоритма это не важно. Все возможные срезы для каждой части были сделаны независимо, теперь надо выполнить их диффузию в соседние части. Я не утверждаю, что это быстро, но это даст правильный результат. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 13:01 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Сколько проходов по каждой плитке и от чего зависит, какая временная сложность алгоритма? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 13:04 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1, а я и утверждаю, что будет выигрыш. Например, со спиралькой ваще кранты ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 13:04 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Давайте я в топике, как архивариус соберу различные маргинальные тест кейсы "острова". Мы подыщем для них картинки и будеем использовать как 1. Синтетические тесты.
При любых профилях карты океан всегда омывает и затапливает крайние пиксели по бордюру. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 14:29 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Со ссылкой на голосование У кого какое разрешение моника . Большинство мембером имеют моник Full-HD и я надеюсь что они нормально отображают на скрине картинку с разрешением 1024х1024 на уровне пиксельной точности. Выше создавать нет смысла т.к. она будет либо не кратная степени двойки либо будет отфильтрована фильтрами низкой частоты что сведет на нет ваши усилия по расчету конкретных отдельно стоящик пикселов. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 15:41 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Имя пользователя1 iOracleDev Сколько проходов по каждой плитке и от чего зависит, какая временная сложность алгоритма? Не совсем так. O(n*ln(n)) - это только на этапе сортировки сравнениями. Если подойдет подсчет или радикс, то O(n). На остальных этапах - O(n), т.к. количество заходов в каждую ячейку фиксировано. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 15:49 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov Имя пользователя1, а я и утверждаю, что будет выигрыш. Например, со спиралькой ваще кранты а я и НЕ утверждаю, что будет выигрыш. Например, со спиралькой ваще кранты ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 15:53 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Более упрощенная задача проскакивала на хабре, более того, там было решение в 1 проход, сдесь немного сложнее, как минимум грани и мерность другая https://habr.com/ru/post/200190/ ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 17:23 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Мда. Монотонность "слева". Пересекается с монтонностью "справа". И получаем ответ для 1-мерного массива высот. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 17:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov 2. Зацикливания нет, т.к. мы все время идем в сторону увеличения уровня при вызове процедуры среза и внутри нее. 3. Выход за пределы стены с помощью стены, т.к. новый срез образуется из нее. Площадка ниже остаточного уровня воды в кратере который ниже уровня подъема воды, однако этот кратер внутри дургого кратера, т.е. сначала подъем на стену, потом спуск и снова подъем, который уже выше уровня подъема воды, т.е. все что внутри должно оказаться сухим. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 18:16 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton При любых профилях карты океан всегда омывает и затапливает крайние пиксели по бордюру. Я бы делал не так, собственно и сделал не так, остров имеет высоту от 0 до 255, при этом остаточный уровень воды может быть выше 0, т.е часть острова может остаться затопленной полностью. Ячейки на одном уровне с уровнем океана после отлива сухие. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 18:19 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev mayton При любых профилях карты океан всегда омывает и затапливает крайние пиксели по бордюру. Я бы делал не так, собственно и сделал не так, остров имеет высоту от 0 до 255, при этом остаточный уровень воды может быть выше 0, т.е часть острова может остаться затопленной полностью. Ячейки на одном уровне с уровнем океана после отлива сухие. Я не то имел в виду. Если вы пойдете на хитрость и создадите "куб" c высотой 255 и размерами например 1024х1024 а уровень океана поднимем на высоту например 300 то по идее ваш куб должен быть затоплен сверху. Эдакий себе всемирный потоп. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 18:28 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Aleksandr Sharahov 2. Зацикливания нет, т.к. мы все время идем в сторону увеличения уровня при вызове процедуры среза и внутри нее. 3. Выход за пределы стены с помощью стены, т.к. новый срез образуется из нее. Площадка ниже остаточного уровня воды в кратере который ниже уровня подъема воды, однако этот кратер внутри дургого кратера, т.е. сначала подъем на стену, потом спуск и снова подъем, который уже выше уровня подъема воды, т.е. все что внутри должно оказаться сухим. Алгоритм пометит высокие ячейки как новые точки среза, но срезать по ним не будет, так как обход будет завершен досрочно на ячейке с высотой меньше уровня прилива. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 18:29 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
[quot mayton#22084832] iOracleDev Я не то имел в виду. Если вы пойдете на хитрость и создадите "куб" c высотой 255 и размерами например 1024х1024 а уровень океана поднимем на высоту например 300 то по идее ваш куб должен быть затоплен сверху. Эдакий себе всемирный потоп. В исходной постановке и был всемирный потоп, потом добавили произвольный уровень максимального подъема воды, а я еще добавил и уровень океана, который после отлива может быть выше какой то части острова. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 18:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Я хотел достигнуть договоренностей о краевых условиях алгоритма. Тоесть когда океану нет места на карте - океан считается пограничными пикселями с координанами например (-1,-1), (+1024,+1024) для моей карты. Иначе алгорим может не сработать или вам придётся вводить в него кучу поправок на края. Это - нудотсво. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 18:42 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, Остров ограничен краями прямоугольника, снаружи только океан, внутри все считается островом, но он может быть под водой, например уровень океана 1, минимальная высота плитки острова 0, часть острова навсегда останется под водой. Т.е. я к тому что уровень океана тоже можно двигать, как и уровень наводнения. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 18:49 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
[quot iOracleDev#22084843] mayton пропущено... В исходной постановке и был всемирный потоп, потом добавили произвольный уровень максимального подъема воды, а я еще добавил и уровень океана, который после отлива может быть выше какой то части острова. На мой взгляд, уровень отлива - лишнее условие, т.к. оно равносильно тому, что все "краевые" точки острова и их соседи (и соседи соседей...) приподнимаются до уровня отлива, если их не считать точками острова. А если считать, то и дно океана надо считать. К тому же это можно свести к разности 2х задач с 2 разными приливами. В общем, пусть при отливе вода уходит туда, откуда пришла - в минус бесконечность. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 18:52 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Я вообще не понимаю зачем вы различаете уровень океана и прилива или наводнения. По мне это - одно и тоже в топике. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 18:53 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Я вообще не понимаю зачем вы различаете уровень океана и прилива или наводнения. По мне это - одно и тоже в топике. Ну ты склеротик: 22077662 )) ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 19:06 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Ладно забей. Проехали. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.02.2020, 19:23 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Еще несколько мыслей - дополнений по условию наших тестов. 1. Одна и та-же карта. И один и тото-же инстанс алгоритма могут быть (и должны) использоваться несколько раз за сеанс. Тоесть наш алгоритм это автомат с состоянием. 2. Приливы и отливы на острове должны иметь колебательный характер с неким повышением среднего. (Помните постановку с кратером внутри кратера?) 3. Для диапазона географических высот от 0 до 255 условных единиц мы 4. Остров с круглыми стенами (Колизей или цирк) который предложил Имя пользователя1 я тоже включаю в коллекцию синтетических ландшафтов. Он пригодится для краш-тестов. 5. Исходные данные островов будут представлены как картинками (PNG) так и Comma-Separated файлами для удобства модульных тестов или каких-то проверок. Отпишите ваши каменты если вы с чем-то не согласны. Возможно к выходным я выкачу свой алгоритм. Но... я попробую написать его на Rust. А от этого моя чортова эффективность как кодера понизится Увы. Придется спешить с справочником в одной руке. Для наглядности наши карты должны иметь хоть какой-то 3D вид. Кто из участников знает Blender или 3DMax чтоб хотя-бы визуализировать их внешний вид в изометрии. И не в сереньком виде а в виде географической раскраски высот. КМК гео-палитра наиболее наглядна. Да и привыкли мы к ней все. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2020, 00:53 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вот такая вот коллекция вулканических островов есть. Пока главные недостаток - разные размеры и разные форматы. И есть анизотропность. Не все имеют пропорции 1:1. Но это я пофикшу в оффлайне. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2020, 13:23 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Это - технические данные. Как видите - зоопарк форматов. Для общности я сделаю копию PPM для каждого и эту копию положу в gzip чтоб легче качат. Код: plsql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
Синтетические картинки (пирамиды и бассейны и плато) я нагенерирую быстро. Однако спираль и лабиринт - отдельная тема. Спираль напрямую у меня не получается. Вида функция f(x,y). Надо делать параметрически. Лабиринт - скорее всего найду готовый. Главное чтоб разрешение было хорошее. Думаю что лабиринт будет самым суровым краш-тестом по времени на наши алгоритмы. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2020, 13:29 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Лабиринт - скорее всего найду готовый. Главное чтоб разрешение было хорошее. Думаю что лабиринт будет самым суровым краш-тестом по времени на наши алгоритмы. Не думаю. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2020, 14:03 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вот типа такого. Он слегка шумит в центре. Там была надпись водяным знаком. Я ее выгонял цветовыми кривыми вроде выгнал но остался шум. Я добалю ее в каталог рельефов. А если такой лабиринт процедурально наложить на конус такого-же радиуса - то мы получим такую себе Вавилонскую башню куда вода будет затекать последовательно по всему лабиринту. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2020, 16:28 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, то что там есть немало серого даже добавит интереса ... |
|||
:
Нравится:
Не нравится:
|
|||
22.02.2020, 17:40 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Мой вариант, он конечно не оптимален в плане реализации, зато квадратно-гнездовой и по нему можно проверять более оптимальные варианты. Площадка: Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51.
Превращение картинки в массив и обратно Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85.
Сам расчет, на входе массив, на выходе тоже массив Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162.
Использование: Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
... |
|||
:
Нравится:
Не нравится:
|
|||
24.02.2020, 16:04 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Приаттачь картинки. До потопа. И после. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.02.2020, 16:13 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, Сам можешь поиграться, ты же жавист, или давай картинку и параметры - уровень океана после отлива и уровень наводнения. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.02.2020, 16:43 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Шикарно. А время мерял? Учитывая что java имеет фазу прогрева методов надо сделать штук 20 вызовов при поднятом приложении чтоб гарантировать что JIT поднялся и собрал методы в нативный код. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.02.2020, 17:50 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, Java и скорость инженерных расчетов несовместимые вещи, ели нужна скорость, нужно убирать ноды, убирать очередь и делать ее самописную на обычном одномерном массиве, в общем делать монолит без дерганья объектов и функций, тогда можно говорить о скорости. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.02.2020, 18:00 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Асимптоматику я могу глазами увидеть и в VisualBasic и в Assembler. Мне только нужно 3-4 точки измерений алгоритма с разным объемом N и отклики по времени. Тоесть наличие или отсуствие в стеке Java никак не влияет на форму этого графика. Здесь конечно Шарахову удобнее. У него - статически компилируемый язык. Но топик ведь посвящен алгоритмизации. Поэтому хороший алгоритм на Java может быть быстрее чем плохой на Delphi. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.02.2020, 18:14 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, O(K*N), один срез считается за O(N), недостаток - зависимость от количества уровней, хотя благодаря этому недостатку его можно распараллелить, можно посчитать срезы, а потом просто последовательно наложить один на другой начиная сверху. Можно пройтись срезами снизу вверх складывая каждый срез в файл, потом сверху вниз, сделать из этого гифку, получится анимированный прилив и отлив)) ... |
|||
:
Нравится:
Не нравится:
|
|||
24.02.2020, 18:26 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Попробуй сделать просто последовательность *png файлов. А дальше можно из нее сделать анимацию. У меня где-то был скриптик с ffmpeg для этого. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.02.2020, 18:28 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Асимптоматику я могу глазами увидеть и в VisualBasic и в Assembler. Мне только нужно 3-4 точки измерений алгоритма с разным объемом N и отклики по времени. Тоесть наличие или отсуствие в стеке Java никак не влияет на форму этого графика. Здесь конечно Шарахову удобнее. У него - статически компилируемый язык. Но топик ведь посвящен алгоритмизации. Поэтому хороший алгоритм на Java может быть быстрее чем плохой на Delphi. Это вряд ли. Плохой алгоритм на Delphi завсегда быстрее )) ... |
|||
:
Нравится:
Не нравится:
|
|||
24.02.2020, 20:28 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Моя картинка mypict ... |
|||
:
Нравится:
Не нравится:
|
|||
24.02.2020, 20:48 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov mayton Асимптоматику я могу глазами увидеть и в VisualBasic и в Assembler. Мне только нужно 3-4 точки измерений алгоритма с разным объемом N и отклики по времени. Тоесть наличие или отсуствие в стеке Java никак не влияет на форму этого графика. Здесь конечно Шарахову удобнее. У него - статически компилируемый язык. Но топик ведь посвящен алгоритмизации. Поэтому хороший алгоритм на Java может быть быстрее чем плохой на Delphi. Это вряд ли. Плохой алгоритм на Delphi завсегда быстрее )) Хвастун. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.02.2020, 22:36 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Aleksandr Sharahov пропущено... Это вряд ли. Плохой алгоритм на Delphi завсегда быстрее )) Хвастун. Да не, ты опять не въехал: это я так твою активность стимулирую )) ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2020, 09:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov mayton пропущено... Хвастун. Да не, ты опять не въехал: это я так твою активность стимулирую )) Уж спасибо. Я как нибудь сам себя простимулирую. Пока я погряз в изучение Rust - предлагаю развивать идею параллелизма. ... |
|||
:
Нравится:
Не нравится:
|
|||
25.02.2020, 10:25 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Моя картинка ... mypict Как понимаю вы все у финиша. Вопрос у меня теперь. Я слышал, выговорили про срезы. Основа алгоритма какая? Делать попикселные срезы, в каждом искать замкнутые контуры, затем просуммировать внутренности контуров, границы не считать, так? Без никаких деревьев или графов, да? ... |
|||
:
Нравится:
Не нравится:
|
|||
26.02.2020, 19:01 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Пока я погряз в изучение Rust - предлагаю развивать идею параллелизма планеризма....то не Чкалов, это - Руст(цэ) ... |
|||
:
Нравится:
Не нравится:
|
|||
26.02.2020, 19:06 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Увы мне увы. Хотел успеть везде. Из хороших новостей. Тестовый сет я полностью подготовил. Куда его запаблишить? Github? Amazon? ... |
|||
:
Нравится:
Не нравится:
|
|||
26.02.2020, 19:50 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Моя хотел бы доставать это из облака-мыл-ру-публик. Как выше iOracleDev в Моя картинка ... mypict ... |
|||
:
Нравится:
Не нравится:
|
|||
26.02.2020, 19:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 iOracleDev Моя картинка ... mypict Как понимаю вы все у финиша. Вопрос у меня теперь. Я слышал, выговорили про срезы. Основа алгоритма какая? Делать попикселные срезы, в каждом искать замкнутые контуры, затем просуммировать внутренности контуров, границы не считать, так? Без никаких деревьев или графов, да? Финиш пройден, проверил 3 варианта (графы идут лесом): 1) Нарезаем слоями по высоте и заполняем водой каждый слой по отдельности. Отладил не сразу из-за проблемы слияния ручейков. Работает, но медленно. Плюс в том, что результаты можно использовать для отладки. 2) Ставим по периметру бесконечной высоты стены, заливаем все это водой под завязку, а потом срезаем лишнюю воду, проходя по высотам снизу вверх. Простейшая рекурсия. Работает быстрее т.к. каждая ячейка считается 1 раз. 3) Тот же вариант без рекурсии. Чуть быстрее. Скорость всех вариантов заметно зависит от организации данных. ... |
|||
:
Нравится:
Не нравится:
|
|||
26.02.2020, 20:14 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Конвертировал PNG/jpg картинки с ландшафтами в полу-текстовый pgm с помошью Линуксового convert. Хм... странно получается только заголовок текстовый. А туловище битмапы не-текстовый (не принтабельный вид). Оно вроде-бы не страшно но я хотел сохранить эту текстовую природу. Это поможет в топике легче разбирать различные ситуации. Пришлось потратить еще час времени чтоб написать на java пару утилит для PPM(цветные) PGM(черно белые) конвертеры с чисто текстовым представлением. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2020, 00:05 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 Забавно, ужели вот так диффузно вода порсачивается сквозь точечное облако? Как понимаю вы все у финиша. Вопрос у меня теперь. Я слышал, выговорили про срезы. Основа алгоритма какая? Делать попикселные срезы, в каждом искать замкнутые контуры, затем просуммировать внутренности контуров, границы не считать, так? Без никаких деревьев или графов, да? Мой вариант простой, иду сверху срезая высоты, например пусть будет полное затопление и максимальная высота острова 255, тогда первый срез будет на высоте 255, при этом плитки на том же уровне считаются для среза сухими. Провожу поиск в ширину от периметра, все плитки до которых добрался получают временный статус под водой, плитки того же уровня не доступны, в замкнутые контуры ограниченные плитками того же уровня поиск в ширину пробраться не может. Отработал уровень, в итоге для 255 уровня получаю плитки с временным статусом и плитки которые статус не получили, далее прохожу по всем плиткам и снимаю временный статус, если временный статус не был установлен ставлю постоянный статус, если плитка имеет ту же высоту что и обрабатываемый срез (255), то она получает постоянный статус "сухая", если плитка имеет меньшую высоту и не имела временный статус она получает постоянный статус "под водой". Таким образом все плитки того же уровня получили статус "сухая", плитки имеющие уровень ниже и оказавшиеся в замкнутых контурах получили статус "под водой". Считаем следующий уровень 254, точно также поиском в ширину от периметра, плитки получившие постоянный статус на предыдущих уровнях недоступны (не зависимо от того сухие они или под водой, их статус уже постоянный), точно также получаем плитки с временным статусом - те до которых поиск смог добраться, плитки того же уровня и замкнутые контуры ограниченные плитками того же уровня или плитками имеющими постоянный статус недоступны для поиска, он не может в них пробраться. Далее повторяем процедуру, снимаем временный статус и для плиток того же уровня ставим статус "сухая", для остальных не имевших временного статуса ставим статус "под водой", постоянные статусы полученные на предыдущих уровнях уже неизменны до конца расчета. Если наводнение не полное и не покрывает остров целиком, то для самого верхнего уровня все плитки не получившие временный статус получают постоянный статус "сухая", даже если их уровень ниже уровня наводнения, поскольку вода не имела к ним доступа. Картинки подъема воды делал просто считая последовательно по одному срезу, задавая уровень подъема воды и уровень океана после отлива одинаковым. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2020, 01:15 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov 1) Нарезаем слоями по высоте и заполняем водой каждый слой по отдельности. Отладил не сразу из-за проблемы слияния ручейков. Работает, но медленно. Плюс в том, что результаты можно использовать для отладки. Откуда ты там ручейки взял? ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2020, 01:16 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98, Мой вариант здесь: 22077648 Пока не заводил, нет времени. Там никаких срезов, сплошной поиск в ширину, правда, для обработки озёр хочу вместо оного сделать построчный floodfill, это даст ускорение на кейсах с большими лужами, особенно в виде лабиринтов. В общем, говнокодить придётся много ) ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2020, 01:29 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Aleksandr Sharahov 1) Нарезаем слоями по высоте и заполняем водой каждый слой по отдельности. Отладил не сразу из-за проблемы слияния ручейков. Работает, но медленно. Плюс в том, что результаты можно использовать для отладки. Откуда ты там ручейки взял? начни реализовывать floodfill, сразу поймешь ) ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2020, 09:27 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Саш. А твои сорцы где-то опубликованы в последней версии? ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2020, 10:45 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Саш. А твои сорцы где-то опубликованы в последней версии? Сорцы 22081712 . Пример карты и результат 22081766 . Там же чуть ниже еще, если надо, процедура генерации случайной карты и датчик случайных чисел. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2020, 11:05 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov Я смогу воспроизвести его под Linux Free Pascal (fpc) правда с твоей помошью и если аккуратно выкосить создание формочек. Потом я сделаю некий сравнительный тест твоего сорца и iOracleDev-s. И еще особо меня интересовали эвристики основанные на предварительном анализе карты. Например шум и пики - один подход. Множество горизонтальных плато - другой. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2020, 12:51 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov начни реализовывать floodfill, сразу поймешь ) Закраска области ограничена областью, при этом если эта область внутри концентрической системы, то без костылей она будет закрашена не в тот цвет, потому что нужный цвет лежит за границей доступной области в общем я не вижу других логичных алгоритмов кроме поиска в ширину по срезам или без срезов, но для каждой точки, что в плане производительности тоже не очень. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2020, 16:11 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вавилонскую башню (спираль) я так и неосилил. Подниму в топике Программинга - отдельно. ... |
|||
:
Нравится:
Не нравится:
|
|||
27.02.2020, 16:15 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
это типа такого, только с градиентной беговой дорожкой внутри? И ... забыл спросить, у вас пикселы 6-угольные в сечении? ... |
|||
:
Нравится:
Не нравится:
|
|||
28.02.2020, 21:48 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 И ... забыл спросить, у вас пикселы 6-угольные в сечении? Мы упростили для визуализации, хотя если у вас на мониторе и в графических файлах пиксели шестиугольные, то мы идем к вам)) ... |
|||
:
Нравится:
Не нравится:
|
|||
28.02.2020, 23:17 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Не совсем. Не стенки. А спиральная дорога вокруг горы. Я искал формулу вида z = f(x,y) ... |
|||
:
Нравится:
Не нравится:
|
|||
28.02.2020, 23:17 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev exp98 И ... забыл спросить, у вас пикселы 6-угольные в сечении? Мы упростили для визуализации, хотя если у вас на мониторе и в графических файлах пиксели шестиугольные, то мы идем к вам)) Топик стартовал как решение графовых задач с 6й степенью вершин. Но для визуализации что 4 что 6 степени одинаковы. ... |
|||
:
Нравится:
Не нравится:
|
|||
28.02.2020, 23:20 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Спсб за пояснения. Искал способ примазаться к чужой славе, но здесь всё схвачено) mayton формулу вида z = f(x,y) Предлагаю брутальный способ закраски (даже танцуя не от пикселов к цвету, а лучами как получится, с перекрытиями). Спираль - это точки радиуса, а будет полуоткрытый ]отрезок], не идеальный асфальт на дороге, конечно, с камешками. Раз уж ввязался. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.02.2020, 12:44 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
параметрически ? Как f(R,phi) ... |
|||
:
Нравится:
Не нравится:
|
|||
29.02.2020, 13:00 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
По поводу Rust. Я был неправ. Завяз в мелочах. Задача чуть более широкая а мелкие технические вопросы постоянно меня блокируют. Я попробую реализовать на Java. А потом уже с экспериментами. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.02.2020, 13:04 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov Не удалось мне собрать на FPC под Linux твой исходник. Надо что-то добавить. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
Я не знаток и не могу за 10 минут пофиксить языковые недочеты. Больше тратить время не хочется. Демотивирует. 96 строка - это конец исходника. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.02.2020, 15:10 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, просто вызывалку нужно добавить в конец Что-то вроде Код: pascal 1. 2. 3. 4. 5.
. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.02.2020, 15:21 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Уже лучше. Бинарник собрался. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.
Работает секунд 10 потом выдает число Код: pascal 1. 2.
Не вижу функционала загрузки картинок. Насколько я понимаю Саша решил генерить карты белым шумом. Это несоклко сужает поле для экспериментов. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.02.2020, 15:27 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вобщем нужно доработать. Переделать HEX ячейки в пикселы. И заргужать вот с таких вот картинок. https://people.sc.fsu.edu/~jburkardt/data/pgma/pgma.html Без этого мы не сможем сравнивать алгоритмы. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.02.2020, 15:29 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Кто захочет поразвлекаться, исходные данные в массиве, списком и графом Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49.
Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75.
iOracleDev. Это последняя версия твоего исходника? ... |
|||
:
Нравится:
Не нравится:
|
|||
29.02.2020, 18:32 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, Нет, вот исходник: iOracleDev Мой вариант, он конечно не оптимален в плане реализации, зато квадратно-гнездовой и по нему можно проверять более оптимальные варианты. Площадка: Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51.
Превращение картинки в массив и обратно Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85.
Сам расчет, на входе массив, на выходе тоже массив Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162.
Использование: Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
... |
|||
:
Нравится:
Не нравится:
|
|||
29.02.2020, 21:03 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton параметрически ? Как f(R,phi) Написал сюда словесный алгоритм, но .... браузер, козёл розово-голубой(( Короче, нахрапом не успел, правки,правки ... надо строго по бумажке. А завтра времни почти не останется. Если никто не спешит, надеюсь ко вторнику, во всяк черновую картинку для замечаний. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.02.2020, 21:43 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 mayton параметрически ? Как f(R,phi) Написал сюда словесный алгоритм, но .... браузер, козёл розово-голубой(( Короче, нахрапом не успел, правки,правки ... надо строго по бумажке. А завтра времни почти не останется. Если никто не спешит, надеюсь ко вторнику, во всяк черновую картинку для замечаний. Не спеши. Синтетические ландшафты у меня еще не готовы. Время есть. Спираль надо сделать качественно чтоб между витками не было рандомных пиков или шума. Или ступенек квантизации там где должен быть градиент. Неплохой вариант - сделать суб-пиксельный рендеринг. Тоесть параметрически сделать спираль в разрешении 2048х2048 а потом уменьшить разрешение в 4 раза с усреднением. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.02.2020, 21:50 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
iOracleDev Нет, вот исходник: Вместе с двумя файлами Node, GrayRgbBmpArray вы приложили два фрагмента кода которые непонятно к чему относятся. Что мне с ними делать? Это недооформленные части проекта. И вы ставите меня в сложное положение. Очевидно я должен сам придумать куда или положить. С одной стороны это - пустяк. С другой стороны вы как-будто самоустранились от этой разработки и считаете что кто-то ее закончит. ... |
|||
:
Нравится:
Не нравится:
|
|||
01.03.2020, 15:07 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, Один непонятный фрагмент, это сам расчет и он вполне себе изолирован и даже с комментами, второй это то как их все вместе использовать, тоже с комментами, если есть более конкретные вопросы могу расписать заложенную мысль. Я не решал задачу создать продуктовое решение, мне интересно было опробовать работу алгоритма, я ее опробовал, для тех кто захочет разобраться выложил и снабдил комментариями, не хочешь разбираться не разбирайся, хочешь продуктовое решение можешь сделать, мне не надо, я своей цели в данном вопросе достиг. PS: расчет поместить в статический класс Island, а следующий кусок в main Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13.
... |
|||
:
Нравится:
Не нравится:
|
|||
01.03.2020, 16:56 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Можно было-бы хоть создать maven-based проект и довести его до стадии компилляции. Впрочем я не настаиваю. Как будет угодно. ... |
|||
:
Нравится:
Не нравится:
|
|||
01.03.2020, 20:16 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Для этого нужны морфологические процедуры. А я делаю простой математикой умножить-разделить. mayton Спираль надо сделать качественно чтоб между витками не было рандомных пиков или шума. Или ступенек квантизации там где должен быть градиент. Показываю сегодняшнее хреновое состояние. Реальный азмер 200х200, а это зум. И наврное надо градиент наоборот, иначе это будет яма. Есть сейчас фигня - криволинейный конус и его окрестности - это явная ошибка. Сначала хотел спросить идей насчёт его, теперь предполагаю, что это ошибка при делении на R~0. ... |
|||
:
Нравится:
Не нравится:
|
|||
01.03.2020, 23:56 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Это ... просто шикарный остров. Вавилонская башня еще и острые пики. По сабжу - понятия не имею как такой эффект может произойти. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.03.2020, 00:04 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Дай мне формулу твоей спирали. Похоже это архимедова. Коэффициенты и прочее. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.03.2020, 00:20 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Так и есть. А дорожка - это уже эклектика нахрапная, голимая. Обычная формула спирали, запись только в векторном виде: Код: plaintext 1. 2. 3. 4. 5.
Спираль на рисунке я по центру дорожки поместил и подсветил, чтоб видеть её. В матрице потом её центрирую. Потом ещё матрицу перевернуть надо, чтобы оси направить как у людей, а не как у прогеров. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.03.2020, 13:21 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98, ок спасибо. Вечером попробую сделать. Для начала хоть начертить ее корректно. Заполнять думаю надо трапециями. Ступеньками башни по сути. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.03.2020, 13:39 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Да я вообще брутально щас считаю. Для каждой непустой точки матрицы (т.е. не на спирали) вычисляю, к какому углу (из дискретных fig() ) она ближе, затем -- ближе к какой именно точке на найденном луче. Так получается, что сами витки посередь дорожки. А думал всё время, что притягиваю дорожку к краю бордюра (башка думала одно, руки делали другое). Это тоже надо будет фиксить. Затем ещё углы матрицы тоже не трогать. Собсно и весь алгоритм. Трапеции замучаешься считать. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.03.2020, 13:57 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Трапеция - это просто 4 точки по твоему алгоритму. Не? Хотя да. Закраска трапеции это нудоство еще то. Надо поискать коробочные алгоритмы. А там я еще закраску Гуро хотел свою. Для треугольников. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.03.2020, 16:05 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вот и я о том же. И я вначале так же думал. Но суровая дискретность матрицы ... Подводный камень в том, что R у меня хоть и растет линейно углу, но при завёртывании, чем дальше, тем чаще дыры. Поэтому дополнительное дробление в виде множителя dk не лишнее. С ростом dk дыр на периферии станет меньше, а в центральной области будет сильная избыточность точек R. Ещё камень в том, что при dk= 6*t получим шаг=t*360 град. Очеь заманчиво для формирования лучей. Но снова вмешивается суровая дискретность, и там выходит точность плюс-минус. Пока решил додавливать подход как есть. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.03.2020, 17:45 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Ну вот, главный косяк ликвидировал, получилось такое зрелище (со сдвигом пока и не перевёрнутое). Ошибка была не там ,где предполагал - забыл центрировать в одном месте. n=400 dk=18 готовилось 5 минут Вопрос теперь: продолжать дальше или уже не нужно? И кстати, ступеньки там сами по себе присутствуют, их видно при большом зуме. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.03.2020, 20:30 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вообще шикарно. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.03.2020, 20:51 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Теперь смотри. Я тут ещё оставил не крашенными углы квадрата. Но для простоты сделал это ВНЕ ОКРУЖНОСТИ, к-рая описана вокруг спирали. Иначе надо на каждом луче сравнивать и т.д. или другие хитрости. Центр спирали немного динамичен в зависиомти от размерности. Неожиданно оказалось, что самый большой радиус от центра - вертик вверх, а не гориз вправо, как мне хотелось верить. Придётся разбираться. То ли смещение при преобразовании коорд-т, то ли не знаю что. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.03.2020, 21:36 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вот вам вариант центрированный со спиралью, вписанный в окружность, + бордюр вокруг рисунка 400х400. n=400 dk=12 Пока могу выдохнуть. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.03.2020, 23:12 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Надо бы ещё ширину дорожки сделать поменьше. Чтоб вода затекла не так быстро. ... |
|||
:
Нравится:
Не нравится:
|
|||
02.03.2020, 23:20 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Как понять Уже? могу больше витков задать, они и станут уже. Кстати заочно понял, в матрице масштаб разный по вертикали и горизонтали. Можно поправить, можно нет, картинка слегка видоизменится, особенно в части "описанной" окружности. Это ещё один довод к тому, что нельзя прогать навалом - лишние проблемы потом вычищать. И функции/методы для преобразования координат - тогда не забудется центровка. Вот только набитая техника выполнения здесь и выручала. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 10:07 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Хм.. 1-я картинка была более правильной. Вавилонская башня. Правильная такая. То вторая картинка это скорее - Ад - Сандро Ботичелли Либо башня построенная в яме. Смотря как мапить цвета на высоты. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 10:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Речь о 2-х последних? Задуман был как раз 2-й вариант, 1-й случился по ошибке. Если в 1-м тоже не красить углы будет тот же Ботичелли. И вообще, оба - Вавилонская яма. Может такой адок нужен? ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 11:53 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Причём во 2-м всё по ТЗ: дорожка внутри спирали, забор по краям. В 1-м спираль-забор как разделительная линия, при этом с одно краю дороги пропасть, с другого стена. Вы начальник, вам виднее(цэ) Готовьте ТЗ. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 11:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Базовое ТЗ было в 1 посту. Я предложил - уйти от хексагональной сетки и подойти к квадратной. Расширить объем исходных данных. По сути процессить растровые картинки высот. Изучить возможности параллелизма. Сделать дополнительное условие. Океан затапливает остров на высоту X а потом оступает на высоту Y. Я также предложил ввести тестовый сет данных. Я почему-то предполагаю что среди алгоритмов не будет абсолютных победителей а будут локальные победы на определенных типах карт. Например имеющие плато. Александр кажется тоже писал об этом. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 12:06 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Э, нет, то другое ТЗ, вопрос был лишь про Вавилонскую башню (в расширенной трактовке и про дыру). Ничего более я и не задумывал, речь шла об изготовлении картинки. И вопрос прежний, годится в таком духе, что и как изменить/подправить? Нет - так нет, я прекращу. Кол-во образцов (да даже 2 только) немало, чтобы выдвинуть продуманные требования. Эти образцы, имхо, следует подправить: а) масштабирование сделать одинаковое по Х и У; б) наконец уже, перевернуть матрицы, чтобы спираль крутилась из центра против солнца в нашем полушарии. Да, и плато здесь не предусматривалось, они кое-где имеются в виде ступенек благодаря тому, что спираль в матрице не гладкая, а ступенчатая. Если дискредитировать палитру грубее, то ступеньки станут длиннее и выше. Здесь и ниже утренние варианты с исправленным п. (а) ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 13:30 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
спирарь по краю (и оба, забыл сказать, возрастают из центра) ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 13:37 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Ой, при правке исчезает вложение. возрастающая спираль как срединная разметка. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 13:40 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Базовое ТЗ было в 1 посту. Я предложил - уйти от хексагональной сетки и подойти к квадратной. Зачем уходить? Чтобы понизить связность, рассматривая только 4х соседей? Так в этом и состоит одна из проблем, которую требуется преодолеть решающему эту задачу. Тогда уж давайте рассматривать 8 соседей на квадратной сетке. А еще лучше решить задачу и для квадратов с 8 соседями, и для хексов с 6 соседями (мы программисты или где). mayton Расширить объем исходных данных. По сути процессить растровые картинки высот. Изучить возможности параллелизма. Это как бы боковая ветка. Не особенно интересная. mayton Сделать дополнительное условие. Океан затапливает остров на высоту X а потом оступает на высоту Y. На сколько оступает - не интересно, это не усложняет задачу. Давайте считать, что вода всегда приходит из минус бесконечности и уходит в минус бесконечность. Таким образом, для каждой карты давайте решать 256 задач, с уровями прилива 0..255. mayton Я также предложил ввести тестовый сет данных. Я почему-то предполагаю что среди алгоритмов не будет абсолютных победителей а будут локальные победы на определенных типах карт. Например имеющие плато. Александр кажется тоже писал об этом. Уточнение - давайте для единообразия карты в градациях серого формате 24-бит *.bmp ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 14:12 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
вот, кстати, интересная карта ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 14:16 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov mayton Базовое ТЗ было в 1 посту. Я предложил - уйти от хексагональной сетки и подойти к квадратной. Зачем уходить? Чтобы понизить связность, рассматривая только 4х соседей? Так в этом и состоит одна из проблем, которую требуется преодолеть решающему эту задачу. Тогда уж давайте рассматривать 8 соседей на квадратной сетке. А еще лучше решить задачу и для квадратов с 8 соседями, и для хексов с 6 соседями (мы программисты или где). Я собственно первый и предложил генерализировать алгоритм через графы. Просто мне хотелось иметь быстрый старт для всех участников. Поэтому я и предложил не 6-связную ячейку а 4-связную. А параллелизм на графах - это ожидаемая мной вишенка на торте. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 14:22 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov mayton Сделать дополнительное условие. Океан затапливает остров на высоту X а потом оступает на высоту Y. На сколько оступает - не интересно, это не усложняет задачу. Давайте считать, что вода всегда приходит из минус бесконечности и уходит в минус бесконечность. Таким образом, для каждой карты давайте решать 256 задач, с уровями прилива 0..255. Хорошо. Принято. Пускай будет 256 приливов океана с постепенным повышением максимума до 255. Но я также заметил что многие учебные образцы карт не нормированы от 0 до 256. Поэтому некоторые итерации для них будут вырожденные. Искусственно нормировать их не хотелось-бы. Тк. это вносит эффект квантизации. Появляются искусственные пики на гистограмме частот которых изначально не было. Тоесть надо решить что например делать с островом который изначально был задан высотами например от 100 до 150 ? ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 14:26 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, делать то же, что и со всеми другими - решать все 256 задач, пускай некоторые решения совпадут. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 14:29 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov Уточнение - давайте для единообразия карты в градациях серого формате 24-бит *.bmp Я вообще не против любого графического формата. Можно и BMP. PGM я предлагал опираясь на опыт других хакатонов. Чем проще и демократичнее формат графики - тем быстрее будет вхождение разработчика. PGM - текстовый и ни у кого не должно быть проблем с его парсингом. Для просмотра PGM под Windows возможно надо установить какой-то тул. IrfanView например. По поводу BMP. Для данного конкретного требования (24bit-bmp) надо гарантировать что формула получения цветовой яркости (уровня серого) с 3х каналов RGB у нас у всех - одинаковая. Я использовал обычно такую. Общепринятые весовые коэфициенты для цветов. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9.
... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 14:33 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, можно просто использовать зеленый канал, остальные игнорировать, чтобы не было различий из-за преобразований ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 14:35 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Ну ОК. Бери вобщем любую формулу. Главное чтоб результат алгоритма по перформансу можно было сравнивать для 2х и более алгоритмов. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 16:02 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
здесь результаты для зеленого канала картинки 22091638 пикселы шестиугольные, четные ряды сдвинуты вправо как здесь 22081766 Loaded ShaImg512_01.bmp Water=0 Volume=0 Water=1 Volume=0 Water=2 Volume=0 Water=3 Volume=0 Water=4 Volume=0 Water=5 Volume=0 Water=6 Volume=0 Water=7 Volume=0 Water=8 Volume=0 Water=9 Volume=0 Water=10 Volume=0 Water=11 Volume=0 Water=12 Volume=0 Water=13 Volume=0 Water=14 Volume=0 Water=15 Volume=0 Water=16 Volume=0 Water=17 Volume=0 Water=18 Volume=0 Water=19 Volume=0 Water=20 Volume=0 Water=21 Volume=0 Water=22 Volume=0 Water=23 Volume=0 Water=24 Volume=0 Water=25 Volume=0 Water=26 Volume=0 Water=27 Volume=0 Water=28 Volume=0 Water=29 Volume=0 Water=30 Volume=0 Water=31 Volume=0 Water=32 Volume=0 Water=33 Volume=0 Water=34 Volume=0 Water=35 Volume=0 Water=36 Volume=0 Water=37 Volume=0 Water=38 Volume=0 Water=39 Volume=0 Water=40 Volume=0 Water=41 Volume=0 Water=42 Volume=0 Water=43 Volume=0 Water=44 Volume=0 Water=45 Volume=0 Water=46 Volume=0 Water=47 Volume=0 Water=48 Volume=0 Water=49 Volume=0 Water=50 Volume=0 Water=51 Volume=0 Water=52 Volume=0 Water=53 Volume=0 Water=54 Volume=0 Water=55 Volume=0 Water=56 Volume=0 Water=57 Volume=0 Water=58 Volume=0 Water=59 Volume=0 Water=60 Volume=0 Water=61 Volume=0 Water=62 Volume=0 Water=63 Volume=0 Water=64 Volume=0 Water=65 Volume=0 Water=66 Volume=0 Water=67 Volume=0 Water=68 Volume=0 Water=69 Volume=0 Water=70 Volume=0 Water=71 Volume=0 Water=72 Volume=0 Water=73 Volume=0 Water=74 Volume=0 Water=75 Volume=0 Water=76 Volume=0 Water=77 Volume=0 Water=78 Volume=0 Water=79 Volume=0 Water=80 Volume=0 Water=81 Volume=0 Water=82 Volume=0 Water=83 Volume=0 Water=84 Volume=0 Water=85 Volume=0 Water=86 Volume=0 Water=87 Volume=0 Water=88 Volume=0 Water=89 Volume=0 Water=90 Volume=0 Water=91 Volume=3822408 Water=92 Volume=3826266 Water=93 Volume=4054286 Water=94 Volume=4069682 Water=95 Volume=4078860 Water=96 Volume=4084798 Water=97 Volume=4092854 Water=98 Volume=4100668 Water=99 Volume=4109408 Water=100 Volume=4115094 Water=101 Volume=4118297 Water=102 Volume=4122321 Water=103 Volume=4126679 Water=104 Volume=4133205 Water=105 Volume=4139389 Water=106 Volume=4140981 Water=107 Volume=4144421 Water=108 Volume=4148723 Water=109 Volume=4150103 Water=110 Volume=4151779 Water=111 Volume=4152281 Water=112 Volume=4328265 Water=113 Volume=4341611 Water=114 Volume=4368740 Water=115 Volume=4373696 Water=116 Volume=4379677 Water=117 Volume=4391969 Water=118 Volume=4398657 Water=119 Volume=4406226 Water=120 Volume=4413522 Water=121 Volume=4430303 Water=122 Volume=4437483 Water=123 Volume=4443877 Water=124 Volume=4449125 Water=125 Volume=4452753 Water=126 Volume=4462669 Water=127 Volume=4466359 Water=128 Volume=4471931 Water=129 Volume=4473113 Water=130 Volume=4474185 Water=131 Volume=4477017 Water=132 Volume=4527569 Water=133 Volume=4531572 Water=134 Volume=4542319 Water=135 Volume=4552712 Water=136 Volume=4554796 Water=137 Volume=4555839 Water=138 Volume=4557583 Water=139 Volume=4558344 Water=140 Volume=4558846 Water=141 Volume=4611850 Water=142 Volume=4612574 Water=143 Volume=4613462 Water=144 Volume=4614156 Water=145 Volume=4615818 Water=146 Volume=4615970 Water=147 Volume=4616232 Water=148 Volume=4616712 Water=149 Volume=4618930 Water=150 Volume=4619512 Water=151 Volume=4620262 Water=152 Volume=4620524 Water=153 Volume=4620936 Water=154 Volume=4621992 Water=155 Volume=4622784 Water=156 Volume=4623676 Water=157 Volume=4623782 Water=158 Volume=4623920 Water=159 Volume=4624238 Water=160 Volume=4624632 Water=161 Volume=4625982 Water=162 Volume=4627312 Water=163 Volume=4627386 Water=164 Volume=4627754 Water=165 Volume=4628294 Water=166 Volume=4628678 Water=167 Volume=4629346 Water=168 Volume=4629714 Water=169 Volume=4629934 Water=170 Volume=4630366 Water=171 Volume=4630962 Water=172 Volume=4631090 Water=173 Volume=4631728 Water=174 Volume=4632232 Water=175 Volume=4632876 Water=176 Volume=4632940 Water=177 Volume=4632940 Water=178 Volume=4633472 Water=179 Volume=4634270 Water=180 Volume=4635496 Water=181 Volume=4635704 Water=182 Volume=4636352 Water=183 Volume=4636850 Water=184 Volume=4636918 Water=185 Volume=4637212 Water=186 Volume=4637478 Water=187 Volume=4637876 Water=188 Volume=4637876 Water=189 Volume=4637876 Water=190 Volume=4637876 Water=191 Volume=4637892 Water=192 Volume=4637896 Water=193 Volume=4637896 Water=194 Volume=4637896 Water=195 Volume=4637896 Water=196 Volume=4637896 Water=197 Volume=4637896 Water=198 Volume=4637896 Water=199 Volume=4637896 Water=200 Volume=4637896 Water=201 Volume=4637896 Water=202 Volume=4637896 Water=203 Volume=4637896 Water=204 Volume=4637896 Water=205 Volume=4637896 Water=206 Volume=4637896 Water=207 Volume=4637896 Water=208 Volume=4637896 Water=209 Volume=4637896 Water=210 Volume=4637896 Water=211 Volume=4637896 Water=212 Volume=4637896 Water=213 Volume=4637896 Water=214 Volume=4637896 Water=215 Volume=4637896 Water=216 Volume=4637896 Water=217 Volume=4637896 Water=218 Volume=4637896 Water=219 Volume=4637896 Water=220 Volume=4637896 Water=221 Volume=4637896 Water=222 Volume=4637896 Water=223 Volume=4637896 Water=224 Volume=4637896 Water=225 Volume=4637896 Water=226 Volume=4637896 Water=227 Volume=4637896 Water=228 Volume=4637896 Water=229 Volume=4637896 Water=230 Volume=4637896 Water=231 Volume=4637896 Water=232 Volume=4637896 Water=233 Volume=4637896 Water=234 Volume=4637896 Water=235 Volume=4637896 Water=236 Volume=4637896 Water=237 Volume=4637896 Water=238 Volume=4637896 Water=239 Volume=4637896 Water=240 Volume=4637896 Water=241 Volume=4637896 Water=242 Volume=4637896 Water=243 Volume=4637896 Water=244 Volume=4637896 Water=245 Volume=4637896 Water=246 Volume=4637896 Water=247 Volume=4637896 Water=248 Volume=4637896 Water=249 Volume=4637896 Water=250 Volume=4637896 Water=251 Volume=4637896 Water=252 Volume=4637896 Water=253 Volume=4637896 Water=254 Volume=4637896 Water=255 Volume=4637896 Water=256 Volume=4637896 Total time=1890 ms ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 20:12 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 спирарь по краю (и оба, забыл сказать, возрастают из центра) Вот эта красивая. Заберу к себе в коллекцию. Жаль только что форум толстые картинки конвертит в jpg автоматически. Хотел заказать еще 1024х1024. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 20:36 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov Саш. Да тут-бы не помешало время работы алгоритма посмотреть в милисекундах. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 20:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton там снизу вывел общее - 1.8 с ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 21:35 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Создал репку. Вот тут будут лежать синтетические тестовы данные https://github.com/Mark-Kovalyov/islands/tree/master/heightmap-synthetic ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 23:48 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Сюда я положу данные по картографии приближенные к реальным. https://github.com/Mark-Kovalyov/islands/tree/master/heightmap Ради экономии места я решил хранить данные в сжатых форматах png/jpg Но в обоих каталогах я положил скриптик наподобие Код: python 1.
Он конветит все файлы в нужный вам формат. Если заменить pgm на bmp то соответсвтенно будет сделана конверсия в тот формат который удобен. Кто хочет конвертить под Windows - должен установить комплект утилит ImageMagic https://imagemagick.org/index.php Реальные данные я буду потихоньку улучшать. Сейчас там есть некоторые образцы картинок которые имеют не-квадратную форму. Я думаю как их красиво кропнуть или скейльнуть. Есть также одна картинка PNG которая имеет глубину цвета 16 бит на канал что меня озадачило. Я пока не знаю что с ней делать и думаю какую выгоду с этого можно получить для теста. ... |
|||
:
Нравится:
Не нравится:
|
|||
03.03.2020, 23:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Заберу к себе в коллекцию. Жаль только что форум толстые картинки конвертит в jpg автоматически. Хотел заказать еще 1024х1024. Пока есть n=1000. Однако возникли проблемы. а) себе в коллекцию -- заметил, что забор по краю дороги при возрастании вверх берётся из "нижнего" по уровню витка (т.е. это вовсе и не забор, а тонкий пандус по краю обрыва достаточно сильно ниже уровня дороги в этом месте). Исправлено элементарно. б) n=1000 -- плотность шпиральных точек падает с ростом радиуса, под увеличением легко находятся точечные дырочки в "правлиьном" заборе, через к-рые будет стекать вода, если это башня, а не дыра. Казалось бы фиг с ним, но не по ТЗ. Пока в процессе придумывания как залатать дыры (с учётом п.(в)). в) n=1000 -- время работы! "гадский папа"(цэ), всегда надо "вовремя заткнуть фонтан идей"(цэ) Вечером замерял при k=5(кол-во витков) dk=18(кол-во точек ~1/плотность вдоль витка - ), 50 100 200 400 1000. 1000 за 760 сек. Ок. Навёл марафет с мини оптимизацией. В ходе марафета производительность просела в 4 раза и 1000 теперь за 45 мин, и это фигово. Не помогли даже контекстные сравнения с предыдущими версиями и перезапуски системы. Это что-то специфичное в МЛ. План оптимизации. Надо сделать плотность точек переменной (сделаю уменьшение тт от витка к витку ). Расчёт плотности примерно такой. Периметр квадрата =4n пиксов. Теоретически такого кол-ва лучей в большом витке должно хватить на покрытие всех тт квадрата. Уменьшить можно из оценки 2pi*(n/2)==3146 -- так для каждого витка. А пока для 1000 имеется 5400/3=1800 точек, т.к. витки на одном расстоянии, их радиусы условно 0.2 0.4 0.6 0.8 1, Сумма==3. Дефицит имеющихся точек неохота ликвидировать только пропорциональным наращиванием их числа повсюду. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.03.2020, 13:40 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton какую выгоду с этого можно получить для теста ... |
|||
:
Нравится:
Не нравится:
|
|||
04.03.2020, 13:42 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторЗачем уходить? Чтобы понизить связность, рассматривая только 4х соседей? Для наглядности. До меня тоже не сразу дошло, но помучавшись с представлениями таки да - утилитарно то же самое, а даже на форуме изобразить в виде 2342345646 гораздо легче. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.03.2020, 18:30 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник авторЗачем уходить? Чтобы понизить связность, рассматривая только 4х соседей? Для наглядности. До меня тоже не сразу дошло, но помучавшись с представлениями таки да - утилитарно то же самое, а даже на форуме изобразить в виде 2342345646 гораздо легче. Уменьшая количество соседей, мы резко снижаем вычислительную сложность задачи. Надо наоборот увеличивать, как я уже писал выше. Например, 8 клеток-соседей для одной квадратной клетки не менее наглядно. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.03.2020, 23:01 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 б) n=1000 -- плотность шпиральных точек падает с ростом радиуса, под увеличением легко находятся точечные дырочки в "правлиьном" заборе, через к-рые будет стекать вода, если это башня, а не дыра. Казалось бы фиг с ним, но не по ТЗ. Если на самых крайних поворотах с большим радиусом где-то проскочит пиксель-ямка то вся картинка от этого станет испорчена. Но стоит-ли из за 1 пикселя удесятерять объем работ по вычислению? Думаю не стоит. Если ты прогонишь фильтр "Медиана" то он 100% этот битый пиксель закроет а общие характеристики Вавилонской башни не изменятся. Не парься долго. Отфильтруй и все. Photoshop любой версии и Gimp всегда имеют этот фильтр в комплекте. ... |
|||
:
Нравится:
Не нравится:
|
|||
04.03.2020, 23:31 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 mayton какую выгоду с этого можно получить для теста Я не парюсь, а устраняю баги,глазами разве искать буду? Мадиану да, попробовать можно. Только не в картинке, а в исходном линейном массиве. При плотности до dk=18 уже в 3-м витке есть дыры даже для n=400. А вот для 1024 последний виток - каждая вторая дырка, и ты ещё хочешь 7 витков вместо 5. Так что плотность всё равно увеличивать. Но теперь это быстро как прежде. Но не сегодня уже. ... |
|||
:
Нравится:
Не нравится:
|
|||
05.03.2020, 20:16 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Я ещё вот что скажу. Гр. редакторы - это путь к не повторямости эксперимента. Помимо того, что потом надо будет растр внедрять в массивы, хоть и не так это важно для забора, что массив будет в хаотическом порядке и необработкоспособен. И мне это сейчас не интересно. В принципе мне осталось дожать вариант с кусочно-постоянным шагом спирали. Но также любопытен и вариант - не накладыват забор на закрашенную дорогу (как сейчас), а пройтись вдоль края из центра как по лабиринту и по ходу ставить забор. Он будет немного извилистым, но это менее эклектично. Перепад высот по краю дороги большой, должно получиться. Но надо это проверять. Мы достаточно обрисовали подводных камней и вариантов. Вы вольны воспользоваться помощью более умелых и быстрых умельцев. Потому что меня сейчас задерживает только забор. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2020, 13:08 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Фильтр медиана достаточно простой. Я могу описать алгоритм. Или даже сделаю имплементацию. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2020, 14:35 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Я знаю, что такое медиана. Но здесь случай, когда нужно на плоскости сгладить линию. Предлагаетется вместо забора насыпь, а потом совместить насыпь и дорогу. Нехорошие случаи когда линия в конце вида (110001000011100000 ...). Только в несколько проходов. Могу эту дорогу без забора закинуть сюда зипом , 1024 матрицу 7 витков, иотдельно файл спирали. А можно, как перед этим написал, модифицировать алгоритм жука под задачу и проползти вдоль дороги без забора. Ещё проще подождать лишний час рассчётов. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2020, 18:19 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Это твой MatLab такой медленный? ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2020, 18:31 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Или даже сделаю имплементацию. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2020, 18:32 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton ...такой медленный? n=1к*1к, 7 кругов, 60*24 точки - 1400 сек, не напрягает, легко и 48*60. Просто десятикратное наложение в самом центре суперизбыточно. Вспомнил ещё вариант экстраполяции, отложил в конец очереди. Веду массив координат спирали для матрицы. В нём конечно нет никаких пустот) ЗАто есть и массив координат, где происходят скачки через пустоты. Т.о. каждая пара соседних коод-т в нём определяет отрезок/прям-к. Заполняешь диагональ и добавляешь в основной массив. Всё, пустот нет. Самый детерминированный и простой в реализации алгоритм. Так что, кидать обещанныедва файла? ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2020, 20:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Кидай. Можешь pull-request сделать. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2020, 21:42 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Я так не умею. А как раз и файлы готовы. Но это зип, в нём два пинга и бонус. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2020, 21:49 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
От же зараза, 77 одиночных дырочек в заборе(( хоть руками замазывай ... n=1K, 7 кругов, плотность точек 60*48 на круг, 2890 сек. Дырки начинаются в последней 3/4 круга, тяготеют к гориз-ным и вертик-м участкам. У еня чувство, что будь округление к целому иное, дырок могло бы и не быть. ... |
|||
:
Нравится:
Не нравится:
|
|||
06.03.2020, 23:30 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 Я так не умею. А как раз и файлы готовы. Но это зип, в нём два пинга и бонус. Добавил в коллекцию синтетических карт https://github.com/Mark-Kovalyov/islands/tree/master/heightmap-synthetic ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 01:21 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Хм. А я не могу найти Median Blur в редакторе Gimp. Помнится мне что он там был в старых версиях? Удалили? Кому он мешал. Точно уж патент на него не нужен. Алгоритм тупой до безобразия. Кстати предлагаю подумать над его оптимизацией. Медиана считает яркость 8 соседних пикселов. Сортирует. Вычисляет медиану (среднюю величину которая делит эти 8 яркостей на две группы. И ставит это среднее значение вместо пиксела. (Я могу ошибаться учитывается ли сам пиксел? ХЗ. Но можно учитывать. Хуже не будет). Фильтр - дешевый и жлобский но очень хорошо удаляет с фоток случайные битые пикселы и яркие всплески. В отличие от матричных фильтров - не имеет ярко выраженного эффекта фильтра низкой частоты. Тоесть картинка в целом не теряет деталей. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 01:36 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вот я и подумал что Медиана замечательно уберет эти концетрические борозды по центру дорожек Вавилонской башни. В и других картинках где есть резкая трещина или ямка - будет все красиво замазано. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 01:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, я пробовал раньше медианное сглаживание, для моих данных оно не подходило. Вспоминаю, в каком- то редакторе однажды на пробу посмотрел результат такого фильтра. Может и путаю, но не понравилась ступенчатость. На временных рядах - это мне однозначно не подходило. Не вообще, а мне. Центральную т. ИМХО включать следует, по смыслу преобладания "правильных" значений. Насчёт одиночных дырочек. (Чуть позже вернусь к координатам в матрице.) Имеем специфическую графику - спир-ную дорожку. Выпуклость (теоретическая) в одну сторону. При убывании цвета к краю медианный квадрат имеет большую часть пустых значений (вне самой спирали). Предполагаю, что одиночная дурка в заборе закрасится пустым цветом из следующей дорожки ==> дырка останется. Но ... ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 19:50 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
И я не понял, о концентрических бороздах. Это что ли самые первые варианты? тогда это были заведомые примеры неудачных результатов. Показать, что процесс идёт, и всё под контролем. Подумал, а может вместо рисунка лучше дать датовый файл? координаты в double/exp формате. Кажется он в exp. Придётся оставить только уникальные точки. Однако повод, по к-рому я пишу другой. Почему мне никто раньше не подсказал, что в моём случае дублирование точек спирали в матрице следует устранить, до начала обработки? Всё приходится самому. Это особенно актуально в первых кругах, ибо в них большая избыточность при равномерной сетке углов. Скорострельность ~O(n^2 * T), где Т= кол-во точек в спирали. Три вложенных цикла - это теоретическая основа. И по крайней мере запуски с n= 50 100 200 400 1000 1024 и с разной плотностью давали такую же динамику. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 20:05 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 При убывании цвета к краю медианный квадрат имеет большую часть пустых значений (вне самой спирали). Когда дорожки без забора, нужно что-то типа барельефа. Так что стоит ли вообще? для желающих. Лучше как уже сказал: оставить только уникальные и нарастить спираль за счёт "дыр". ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 20:18 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Астанавитесь! (с) Спираль готова. Я ее добавил в коллекцию синтетических тестов. По спирали работы закончены. Еще я сделаю пирамиду и бассейн. И всё и можно приступать к разработке с тестами скорости. Кстати я на клеточной тетради нарисовал свою идею топологического затопления острова. Но это только для местности особого свойства. Где есть большие плато. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 20:48 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Мэйтон, так ничего и не понятно. Вы можете потрудиться , и разжевать простым языком для простых смертных, что и как и какие плюшки от вашей технологии и/или реализации. Очень хотелось бы освятить прикладную тематику. Для изначальной постановки вопросов (намеренно укрупненной) , решение замечательно сочетается с прикладными задачами. Можно придумать задачу - где нефть при прорыве скважины (фонтанировании) затопила некий регион - куда чего потечет по геодезическим картам, сколько кубов откачать и куда надо слать технику. Масштабируемо. У вас же просто теоретический интерес? Или вы копаете в область чистой математики для баз данных и всякого такого? ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 21:06 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
В топике есть основная цель. Ее озвучил автор. И ее реализовал Саша Шарахов. На этом топик можно закрыть. Остались только скучающие завсегдатаи которые чего-то себе придумывают. И я в том числе. Но вы - можете не беспокоиться по этому поводу. Многие топики sql.ru текут в таком режиме. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 21:11 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Спасибо за ответ. И за сокрытие вашего глубокого интереса к максимально абстрактным вещам. Хотя бы понятно, что если есть прикладной уровень, то он мне в силу понимания недоступен или его не разглашают. Но как жуткий зануда и практик - скажу вам одну вещь, которая обломает любые начинания на корню. Ваши выкладки просто сразу убиваются об интерфейс с исполнителями хотя бы сбора начальной информации и ее стандартизации. Надеюсь вы понимаете теперь, почему я так "восторженно" отношусь к этой ветке после третей страницы. Хотя на базах данных всякого наверное можно применить.... ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 21:15 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
А какой из этих пунктов был непонятен 22091467 ? Я догадываюсь что я иногда бываю слишком краток. Но никто - не спрашивает. И я думаю что все в теме. Или всем пофиг. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 21:17 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторБазовое ТЗ было в 1 посту. Я предложил - уйти от хексагональной сетки и подойти к квадратной. согласен, не принципиально Расширить объем исходных данных. По сути процессить растровые картинки высот. Не согласен, интерфейс не описан а главное задача, ударились в интерфейсы Изучить возможности параллелизма. Не согласен, зачем без прикладной задачи? На уже определенных растровых картинках которые не определены Сделать дополнительное условие. Океан затапливает остров на высоту X а потом оступает на высоту Y. Согласен, может иметь практическое применение, но скорее это описание граничных дел, в этой задаче как раз граничные дела самые главные. Как только ты математически безошибочно создашь алгоритм, последний рубеж проверки будет как раз размывание начальных условий - вроде не так друг друга поняли Я также предложил ввести тестовый сет данных. Согласен Я почему-то предполагаю что среди алгоритмов не будет абсолютных победителей а будут локальные победы на определенных типах карт. Какую задачу решаем? Я почему то предполагаю, после очередного дня с паяльником что одно жало лучше другого. Абсолютно не формализовано. Хочется как лучше.... Ну.. Для мира... Чтобы был безоговорчный лидер . Например имеющие плато. Александр кажется тоже писал об этом. Взгляд со стороны, вы чего то чувствуете, но никак не можете определить где грань между идеями и реальным миром. Я слабо верю что такое даже в реальных базах данных делается. Вердикт - невиновен, спустись на землю. Материализм и прикладное в крови, а все остальное измышления на тему в попытках обобщить :D ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 21:25 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Я предложил - уйти от хексагональной сетки и подойти к квадратной. согласен, не принципиально Да это непринципиально. Браузеру тоже непринципиально было что поддерживать HTML5 или XML. XML даже выгоднее. Строгий и однозначный парсер. Но люди подвели. Не умеют они писать в XML. Такие они несовершенные. А по сабжу. 100% данных по высотам (реальная картография или искусственная украденная из комьютерных игр или созданная на Corel Bryce) всегда экспортируется в растровом формате. Не в графовом. И я когда ставил задачу - исходил из предположения что найти такие данные будет легко. В противоположность если вы решили играться с хексагональной сеткой то вы будете постоянно терпеть неудобства конвертации из обще-принятого формата в свой собсвтвенный. Опять-же я исходил из возможностей людей а не из мощности вершин графа. В некотором вырожденном случае мы могли вытянуть остров в одно-мерный. Математика тут и там будет одинакова. Против графов я не имею ничего против даже более того. Моя идея основана на том что остров даже меняя уровень затопления - имеет фиксированную топологию высот. И эта топология может (и должна быть задана в виде графа). Это облегчит алгоритм затопления (особенно на итерациях). ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 21:44 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Какую задачу решаем? Я почему то предполагаю, после очередного дня с паяльником что одно жало лучше другого. Абсолютно не формализовано. Хочется как лучше.... Ну.. Для мира... Чтобы был безоговорчный лидер. Я вам предлагаю ... просто отдохнуть от этого топика. Ну рано вы сюда зашли. Вообще всё что было написано вами выше про стандартизацию и интерфейс исполнителей - это никому не нужно я уже понял. Люди не хотят ничего делать под чужой интерфейс (я кстати его предлагал в самом начале). Чтобы провести бенчмарк или сравнение алгоритмов - должны быть установлены одинаковые правила игры. Тоесть - одинаковые исходные данные (остров). И одинаковое железо (это значит я должен взять алгоритм Саши и адаптировав его (боже упаси делать мне нечего) - заставить его (алгоритм) работать с квадратной сеткой высот чтобы просто сравнить его с алгоритмом пользователя iOracle, который писал код на Java и использовал растровые картинки как исходные данные. Боже упаси сравнивать Делфи с Java, где на коротких дистанциях (меньше секунды) Делфи побеждает сразу. Вобщем нету времени на причёсывание чужого кода. Когда я публиковал задачу на бенчмарк трассирующего луча на разных компилляторах - Тяпничный бенчмарк CPU (part-1) я понял что там так и не решена главная задача. Стандартизация отчотов о бенчмарках и формализация процедуры деплоя (я хотел это сделать через Docker но руки не дошли). Вобщем к чему я все это. Рук не хватает. Некому делать. Понимаете? Опенсорц - это такая ненадежная штука. Нет договорных отношений - результат можно ждать завтра а можно ждать 100 лет и все равно никто не сделает. Я просил некоторых мемберов с этим помочь но никто не взялся. По поводу целей. Я уже писал где-то что для меня многие топики - вторичны. Цели у меня на самом деле могут быть другие. Например мне интересно изучать Rust и Haskell и пытаться применить их где-то в задачах .. ну если не продуктовых то хотя-бы здесь. В форумных. Мне интересно искать различные способы распараллеливания алгоритмов с целью запуска их в Amazon EMR (Spark/Hadoop). Опять-же. Графы - это челлендж. Графы - сопротивляются параллелизму. Они липнут к блокировкам. Их трудно сегментировать для независимого процессинга сегментов. Мне также было интересно погонять OptimisticTimestamped locks (Java) на графах только для этого нужно было мясо. Много мяса. Я имею в виду алгоритмы и цель - минимизации времени. Мне также было интересно понять как Haskell обходится вообще без переменных и конкуренции решая сверх сложные задачи. Вы там что-то писали про геологию и бурение нефти. Прекрасная постановка. Но я о ней вообще не думал. Но если вы наполните этот (безумный) топик материальным и физическим смыслом (расчет объемов залежей) или скорость затопления долины в случае аварии на дамбе - то я буду не против и очень даже рад. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 22:07 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Я прочитал. Спасибо за развернутый ответ. Надо переварить. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 23:04 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Эк вас обоих ...)) mayton, вопрос к вашей картинке теперь. Как вы проверяли, что в заборе нет дыр? на глаз? Действительно, предметники всегда действует по принципу бери больше, кидай дальше. Особенно хозяевА. Понаучали, панимаишь ли, в прошлом кучу народа, теперь она с жиру бесится, ерундой занимается - нет, чтобы ток давать в недоразвитые районы. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 23:05 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98, Нас нормально, одного уровня абстракций обсуждения с попыткой понять хотя бы и в лучшем случае реализовать как-то. Я еще не ушел спать, но 99% сообщений на скл ру полный бред/или не бред, но для узкого круга лиц. Тут глобальное :) ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 23:14 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Представьте меня тех директором (именно тех)ю ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 23:15 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Вот набросок. Моей мысли по топологичесому "затоплению". Матрица 8х8 высот представляет собой микро остров (слева) и справа ей соответсвующий граф высок. Для расчета затопления нам достаточно графа. Остальные дейтвия - публикация картинки с водой сугубо сервисная. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 23:45 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Буквой Z обозначен океан. Степень этой вершины будет повыше чем у других. Кстати на данной задаче мы можем пройтись по теории 4 красок на карте. ... |
|||
:
Нравится:
Не нравится:
|
|||
07.03.2020, 23:47 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Только щас заметил. На картинке ошибки. Где-то рёбер не хватает. Где-то высота номер 8 не свазана с буквой H. Но думаю что идеи это достаточно. ... |
|||
:
Нравится:
Не нравится:
|
|||
08.03.2020, 13:09 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
авторСаши и адаптировав его (боже упаси делать мне нечего) - заставить его (алгоритм) работать с квадратной сеткой высот чтобы просто сравнить его с алгоритмом пользователя iOracle, который писал код на Java и использовал растровые картинки как исходные данные. Вы никак не находите принципиальных проблем? Ну я подскажу. Под конкретный алгоритм с КОНКРЕТНЫМ островом безусловно будет определен лидер. Но чуть отойдите вдаль и посмотрите с издалека. А издалека видно, что острова разные и решения будут в принципе как O(N). Изящество хромает. Дельфи / Ява. Я крамолу скажу - дельфи программист скорее всего поймет чего там ява программист написал. Такие дела. Кокретезируйте задачу и от это уже... Ваш остров влегкую решается без графов (решения из первых 3-ех страниц). Вы именно к графам хотите привязаться? Ноу проблем. Как только задачу формализуете. Что за хождение вдоль да около. Пока видно что вы даже больше чем просто на бумаге циферки не сподобились, как пророк, времени нет у него, нарисуйте за него. ЗАДАЧА и ее оценка вот что интересно было в этом топике. ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2020, 10:59 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
ладно ладно удаляюсь из топика. Посмотрим что будет. Но мой вам совет - чем четче поставлена задача, тем быстрее вы ее решите. ... |
|||
:
Нравится:
Не нравится:
|
|||
09.03.2020, 11:14 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton Чтобы провести бенчмарк или сравнение алгоритмов - должны быть установлены одинаковые правила игры. Тоесть - одинаковые исходные данные (остров). И одинаковое железо (это значит я должен взять алгоритм Саши и адаптировав его (боже упаси делать мне нечего) - заставить его (алгоритм) работать с квадратной сеткой высот чтобы просто сравнить его с алгоритмом пользователя iOracle, который писал код на Java и использовал растровые картинки как исходные данные. Боже упаси сравнивать Делфи с Java, где на коротких дистанциях (меньше секунды) Делфи побеждает сразу. Вобщем нету времени на причёсывание чужого кода. Здесь "адаптированный" алгоритм на все случаи жизни: для 4-, 6- и 8-угольных пикселей и произвольных размеров карты. Он умеет работать как со случайно сгенерированной картой, так и с картой из файла 24bpp *.bmp (берет зеленый канал). Он немного быстрее предыдущего за счет того, что при инициализации карта обрамляется рамкой в 1 ячейку и поэтому в основной процедуре не нужно проверять выход за границу массива. Функция FillWater(aLinkCount, aWater) теперь имеет 2 параметра: связность ячеек и уровень прилива. Перед тем как ее вызывать необходимо прочитать карту высот из bmp-файла функцией ReadMap или сгенерировать процедурой GenerateMap. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. 195. 196. 197. 198. 199. 200. 201. 202. 203. 204. 205. 206. 207. 208. 209. 210. 211. 212. 213. 214. 215. 216. 217. 218. 219. 220. 221. 222. 223. 224. 225. 226. 227. 228. 229. 230. 231. 232. 233. 234. 235. 236. 237. 238. 239. 240. 241. 242. 243. 244. 245. 246. 247. 248. 249. 250. 251. 252. 253. 254. 255. 256. 257. 258. 259. 260. 261. 262. 263. 264.
... |
|||
:
Нравится:
Не нравится:
|
|||
11.03.2020, 22:35 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
маловато отпущено времени на исправление ошибок, не успел заменить в ReadMap константу '..\bmp\ShaImg512_01.bmp' на параметр aFileName ... |
|||
:
Нравится:
Не нравится:
|
|||
11.03.2020, 22:49 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Так, мальчики! Решаем глобальные проблемы, быстренько посчитайте мне водоизмещение синей цистерночки. Файл приложен, чёрный цвет предлагаю игнорировать, белый - типа высота до небес. ... |
|||
:
Нравится:
Не нравится:
|
|||
13.03.2020, 21:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98, Чтобы каждый не изобретал свой способ конвертирования, неплохо было бы убрать с картинки лишнюю хрень, перевести в градации серого и сохранить в bmp. Опять же неясно, какие пикселы в задаче 4, 6 или 8-угольные? ... |
|||
:
Нравится:
Не нравится:
|
|||
13.03.2020, 23:46 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Используем 4 связность. Вода по диагонали не протекает. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.03.2020, 07:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Aleksandr Sharahov, будет сделано! - Пиксы в сечении квадратные. - Разрешите оставить чёрные точки на предмет игнорирования?! или ... и их тоже, ликвидировать? - Белый цвет вокруг мира сего?.. (А всё потому, что нет единого стандарта.) ... |
|||
:
Нравится:
Не нравится:
|
|||
14.03.2020, 12:22 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Саша ты не против если я твои исходники буду копипастить в свой репозиторий? Мне так удобнее и вносить изменения и тестить. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.03.2020, 12:24 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, да, конечно, для этого и привел ... |
|||
:
Нравится:
Не нравится:
|
|||
14.03.2020, 13:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 Aleksandr Sharahov, будет сделано! - Пиксы в сечении квадратные. - Разрешите оставить чёрные точки на предмет игнорирования?! или ... и их тоже, ликвидировать? - Белый цвет вокруг мира сего?.. (А всё потому, что нет единого стандарта.) Черные (0) - это эквивалент нулевой высоты, белые(255) - макс. высота. Все точки карты принадлежат острову. Поэтому, чтобы вода не задерживалась по краям карты, достаточно их сделать одинаковой нулевой высоты. ... |
|||
:
Нравится:
Не нравится:
|
|||
14.03.2020, 13:43 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Палитра bmp какая? 256 индексная или 24b r=g=b ? ... |
|||
:
Нравится:
Не нравится:
|
|||
15.03.2020, 09:26 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98 Палитра bmp какая? 256 индексная или 24b r=g=b ? 24bpp: r=g=b а если 24bpp r<>g<>b, то просто считаем по зеленому каналу. т.е. всегда берем зеленый ... |
|||
:
Нравится:
Не нравится:
|
|||
15.03.2020, 09:52 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Когда я предлагал ppm/pgm - я хотел избавить вас от обсуждения стандартов кодирования графики. Их много. Я вы закопаетесь. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.03.2020, 10:35 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Не удалось собрать. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27.
... |
|||
:
Нравится:
Не нравится:
|
|||
15.03.2020, 12:21 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
я Вообще могу матрицу дать, а эти ППМ и т.п. ещё не повсеместны. Про зелёный раньше надо было. Короче зип-файл 24b, серый. Не обошлось без вмешательства ручками. В основном в Канадине и где-то на Филлипинах, что ли. Претензии принимаются только к формату. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.03.2020, 12:22 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
PPM это достаточно старый формат. Для поддержки его просмотра под Windows надо установить эту штуку https://www.irfanview.com/ Под Linux - он достаточно коробочный и интегрирован лучше. Собственно если-бы вы были участниками бенчмарка от 2015 года где мы по этим техническим нюансам прошлись, то вы бы сейчас не тратили время на поиски кодеков и файловых форматов а просто делали бы алгоритм как таковой. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.03.2020, 12:27 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, не закопаемся) мы используем 1 устоявшийся стандарт: bmp 24bpp, а в нем берем зеленый канал это проще, чем перегонять bmp во что-то другое, невизуальное, а потом это что-то загружать. P/S/ визуализацию заказывали? - распишитесь в получении ) ... |
|||
:
Нравится:
Не нравится:
|
|||
15.03.2020, 12:28 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Как будет угодно. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.03.2020, 12:34 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, утруждать заказчика усилиями по визуализации как бы моветон, а обработка "гео"-данных без предварительной визуализации - это, с чем бы сравнить,.. как поцелуи через платочек. З.Ы. я пропустил, целоваться ещё не запретили в связи с новыми бяками? а то рукопожатия уже чуть ли не уголовка ... ... |
|||
:
Нравится:
Не нравится:
|
|||
15.03.2020, 12:54 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Я не против визуализации. Я говорю о том что вы несколько страниц потратили на обсуждение как получить яркость из RGB в то время как для меня это решенная задача давно. Вы тратите время на обсуждение разрядности и свойств bmp и это не приближает решения а просто его кастомизирует. ... |
|||
:
Нравится:
Не нравится:
|
|||
15.03.2020, 13:31 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Работает? Не трогай! Я тоже не против более удобных форматов в плане АПИ, только ... Достала уже эта низкоуровневость кодёрства. Раз попробовал изготовить в ППМ (нечто вроде Хэллоу, воулд). Оказалась у меня пара прог, к-рые ППМ знают. Обе грязно выругались. Поэтому хотел бы знать на примере, как ППМ облегчает изготовление яркости (либо почему делает это изготовление ненужным)? ХМЛ облегчает формовку данных? и ведь тоже все хотят плагинов, апишек и фреймворков. Вот когда мне понадобится сделать файл малочитаемым другими (подобно ПДФу), наверное тогда возьму ППМ. Но я против несовместимостей и всевозможных нововведений ради нововведений. Видимо стабильность в программировании кому-то не даёт покоя,браузеры тоже: тот работает, этот уже нет и т.д. Вавилонская башня. Вот зачем цепляются за сохранность синтаксиса оператора свитч (срр)? ради совместимости с одним единственным нестандартным применением 40лет назад? кому этот приём щас наф нужен ... ... |
|||
:
Нравится:
Не нравится:
|
|||
15.03.2020, 18:48 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
С яркостью, кстати, секрет Полишенеля. Ещё в МС ДОС из демок КуБэ формулу стянул. Но и книжек об этом тогда хватало. Где-то записано, там ~0.11 R вроде. Не важно ... ... |
|||
:
Нравится:
Не нравится:
|
|||
15.03.2020, 18:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
exp98, как будет угодно. Я просто добавлю что BMP- это один из самых неудачных графических форматов. Его вертикальна организация скан-линий такова что началу файла соответствует конец видеопамяти. Это вкратце. А в частности чтобы прочитать тебе файл - на уровне диска - тебе надо читать его сзаду-наперед. И заполнять банки видеопамяти (это я говорю в терминах VGA/SVGA) в прямом порядке. Либо наоборот. Читать файл прямо и писать в память от младших адресов к старшим. Технически - это неудачная идея. И хотя данные внутри одной строки лежат более менее последовательно в общем работать с фрагментом крупной картинки частями - неудобно. И алгоритмы сжатия для bmp были реализованы только для индексного (палитрового режима). True-color-же остался толстым и несжатым. Хотя поджать его с помощью дифференциального кодека было очень легко. Благо бесплатный gzip всегда существовал. Я также встречал экзоточески редкие под-виды BMP с разрядностью 16 бит на 3 цвета. Они на 80% несовместимы с большей частью ПО. Я гарантирую что под Линуксом вы скорее всего такой файл не откроете. Тоесть вроде оно и стандартно но покрытие совместимости закрыло лишь самые популярные его разрядности цвета. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.03.2020, 15:24 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
mayton, вспомнила бабка как девкой была: палитра давно в прошлом, а зеркальность по вертикали абсолютно пофигу, на результат не влияет. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.03.2020, 15:38 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Палитра в прошлом говоришь? А как ты серый bmp сделаешь? Продублируешь 3 одинаковых канала. 3 одинаковых матрицы. Или (хопа!) - создаешь 256 цветный индексированный палитровый bmp. Что в целом меньше по курсу рубля аж в 3 раза и имеет профит для промышленности и народного хозяйства. Вот так вот дедушка. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.03.2020, 16:43 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
А ты не путай свою шерсть с государственной (c) Тебе, может, лучше подойдет другой формат. А мне эти bmp только для тестов нужны, и формат выбран исключительно для удобства отладки и тестирования. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.03.2020, 17:49 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Да развеж я могу запретить? ... |
|||
:
Нравится:
Не нравится:
|
|||
16.03.2020, 17:51 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Когда-то и РСХ пришлось самому распаковывать. А когда потом всё появилось, он не нужен стал. И тем е менее, обходя тупые углы БМП, его использование нами, виндусятами , стало типа стандартным в АПИ (ну, одним из ...) А описанное выше неудобство относится к низкому уровню, от к-рого хочется шарахнуться (ненароком скаламбурил). И тут возникает ППМ, для к-рого нетути АПИ, и нафига тогда текстовый формат нужен?.. Поэтому лучше послушать преимущества ППМ, ускоряющие и облегчающие работу прогера. Пусть не в гигантских конторах, а как мы, факультативно, хобби и т.п. В общем, получился "островной" трёп, но я согласен слушать, не перебивая, без дискуссии. ... |
|||
:
Нравится:
Не нравится:
|
|||
16.03.2020, 22:07 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Мистер Мэйтон так и не предоставил свой чудесный вариант. Так... за спасибо массами руководит :D Мэйтон, колись уже , чего затеял, ты вроде обещал. Я запомнил ;) ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2020, 11:34 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
0) а) VOLUME = 0 б) Все крайние плиты обозначаем как сухие 1) Идем в цикле CURRENT_LEVEL = от MIN_LEVEL = 1 до MAX_LEVEL = 6 2) Применяем следующий алгоритм а) Если рядом с сухой плитой, есть плита не ниже её (>=), обозначаем её как сухую б) повторяем (а) пока мы можем обозначить хоть одну новую (ранее не помеченную) плиту сухой в) Находим все мокрые (не сухие) плиты чей уровень равен CURRENT_LEVEL и для каждой VOLUME += 1, также увеличиваем уровень этих плит на 1 (== CURRENT_LEVEL+1) 3) уходим на цикл из 1 и повторяем п (2) (маркировку плит как сухих оставляем как есть с предыдущего витка цикла). Если все плиты стали сухими, то цикл из п1 можно прервать (break) ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2020, 14:13 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, ладно. Расскажу. Следующая моя гипотеза оптимизации основана на MipMapping https://ru.wikipedia.org/wiki/MIP-текстурирование Только вместо функции avg я планировал сделать min/max. И протестировать решение этой задачи на цепочке карт высот меньшего размера. Моя гипотеза основана на том что для средней карты (не белый шум и не вырожденная гора) мы быстрее будем отсекать варианты затекания воды в те квадраты где подходящих высот нет. В силу своего перфекционизма я немножко застрял на новом языке Rust в котором я пока начинающий и там... пошло-поехало (аж на 20 топиков вопросов хватит). Так што берите мою гипотезу если хотите и проверяйте. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2020, 14:30 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
А я пока буду нубствовать в Rust. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2020, 15:50 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
И в BigData. Отвлекли меня... черти. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2020, 19:58 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Я подозреваю, что вы чертями назвали всех как канальями Боярский :) Но никак не сходится - что вы выкатите рещение, этож про алгоритмы а не про языки. Алгоритмически можно разжевать для недалеких? :) ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2020, 20:28 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Не.. серьезно уже и без шуток, что вы затеяли? Алгоритмически все примерно одинаково, но столь пристальное внимание навевает мысли что что-то проглядели. Что именно? Без языков, человеческими словами. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2020, 20:33 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Алгоритмически - все просто. 1) Дана карта высот. H(x,y). 2) Строим множество mip-карт. Пускай это будет H(i)(x,y) по формуле = min(....) короче каждый следующий уровень содержит в 1 элементе минимум от четырех элементов предыдущего уровня. 3) Решаем задачу циклического затопления острова. Начиная с самых мелких mip-карт. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2020, 20:35 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник Я подозреваю, что вы чертями назвали всех как канальями Боярский :) Но никак не сходится - что вы выкатите рещение, этож про алгоритмы а не про языки. Алгоритмически можно разжевать для недалеких? :) Я прошу прощения. Черти - это не к вам. Это мои дорогие кастомеры меня отвлекают. Им щас нужна автоматизация тестирования на технологиях которые тестировщики не знают. Вот просят меня помогать. А я в гробу видел все эти Spark/EMR. ... |
|||
:
Нравится:
Не нравится:
|
|||
29.03.2020, 20:37 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
автор1) Дана карта высот. H(x,y). 2) Строим множество mip-карт. Пускай это будет H(i)(x,y) по формуле = min(....) короче каждый следующий уровень содержит в 1 элементе минимум от четырех элементов предыдущего уровня. 3) Решаем задачу циклического затопления острова. Начиная с самых мелких mip-карт. Не ясно :) Для каких вы целей прикручиваете. Как сказал один человек давно кому-то, если кто-то может объяснить самому тупому, то тогда он точно дока в этом вопросе. Мне кажется мы в разных каких то плоскостях говорим. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.03.2020, 13:18 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Да выкатите свое решение в конце концов, тогда будет предметно! ... |
|||
:
Нравится:
Не нравится:
|
|||
30.03.2020, 13:20 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
АСУ ТПшник, да забей уже на этот топик. Я может выкачу. Но у меня перед этим форумом - минимальные обязательства. Напиши сам своё. Вижу что скучаешь. ... |
|||
:
Нравится:
Не нравится:
|
|||
30.03.2020, 13:27 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Пока остров еще не сдох. Выложу свой рисунок mip-map. ... |
|||
:
Нравится:
Не нравится:
|
|||
26.04.2020, 10:45 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Не понял, это что-то вроде стягивания графа в точку? ... |
|||
:
Нравится:
Не нравится:
|
|||
26.04.2020, 15:09 |
|
Задачка про остров
|
|||
---|---|---|---|
#18+
Нет. Внизу нарисовано как остров 8х8 я привожу к 4х4 и 2х2. Далее я планировал для некоторых типов ландшафтов использовать такое представление для оптимизации поисков. А граф - просто приведен как пример топологии (это по моему первому предложению в начале топика). ... |
|||
:
Нравится:
Не нравится:
|
|||
26.04.2020, 16:48 |
|
|
start [/forum/topic.php?all=1&fid=16&tid=1339799]: |
0ms |
get settings: |
9ms |
get forum list: |
13ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
63ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
310ms |
get tp. blocked users: |
2ms |
others: | 12ms |
total: | 430ms |
0 / 0 |