ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка про остров
25 сообщений из 421, страница 9 из 17
  9  все
Задачка про остров
    #39928051
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
iOracleDev
Выше нарисован.


цветастый он какой-то
...
Рейтинг: 0 / 0
18.02.2020, 15:58
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928060
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Aleksandr Sharahov
цветастый он какой-то

сохранял как 256 градаций серого в свойствах 8 бит и по размеру похоже, не знаю почему он цветастый, в графике не разбираюсь))
...
Рейтинг: 0 / 0
18.02.2020, 16:06
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928061
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
С ppm очень просто. Это текстовый файл. В бинарными форматами - вот образец. Записывает шум.
И пытается прочитать.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
BufferedImage image = new BufferedImage(256, 256, BufferedImage.TYPE_INT_ARGB);
Random rnd = new Random();
for(int y =0;y<image.getHeight();y++) {
    for (int x = 0; x < image.getWidth(); x++) {
        int r = rnd.nextInt(256);
        int g = rnd.nextInt(256);
        int b = rnd.nextInt(256);
        image.setRGB(x,y, 0xFF_000000 | r << 16 | g << 8 | b);
    }
}
ImageIO.write(image, "PNG", new FileOutputStream("test.png"));
BufferedImage image2 = ImageIO.read("test.png");
image.getRGB(0,0); 
// .....



Для серого - будет тоже самое наверное только тип картинки поставить в TYPE_BYTE_GRAY.
Но я с ним не работал.
...
Рейтинг: 0 / 0
18.02.2020, 16:07
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928062
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
PPM хорошо описан тут https://ru.wikipedia.org/wiki/Portable_anymap
...
Рейтинг: 0 / 0
18.02.2020, 16:08
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928077
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
iOracleDev

Было бы очень неплохо ... получить на выходе файл у которого все пиксели оставшиеся под водой имеют белый цвет.


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

В общем, каждый отлаживается на свой вкус и цвет.
...
Рейтинг: 0 / 0
18.02.2020, 16:34
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928082
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Как будет угодно. Я просто в этой задаче увидел элемент технологии из game-dev.

Поэтому художнику по дизайну ландшафтов будет очень презентативно увидеть результат как его показывают
такие приложения как CorelBryce, RealWorldTerran e.tc.
...
Рейтинг: 0 / 0
18.02.2020, 16:44
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928315
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
Aleksandr Sharahov
Имя пользователя1


кстати, твой алгоритм сможет проглотить добавку от Майтона? 22077662


Добавку от Майтона он не проглотит, придется модифицировать одну строчку.

Ну и неясность некоторая имеется: волна высотой 3 перевалит через гору высотой 3 или нет?
нет, не перевалит. Так логичнее, по моему)
...
Рейтинг: 0 / 0
19.02.2020, 10:51
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928333
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Имя пользователя1
Aleksandr Sharahov
пропущено...


Добавку от Майтона он не проглотит, придется модифицировать одну строчку.

Ну и неясность некоторая имеется: волна высотой 3 перевалит через гору высотой 3 или нет?
нет, не перевалит. Так логичнее, по моему)


Тогда рассмотрим оба варианта, при условии, что вода поднимается до уровня 3.

1. Когда перевалит.
Заливаем всю карту водой без ограничений.
Если теперь мы просуммируем воду по всем ячейкам, то получим решение исходной задачи,
а если просуммируем по ячейкам, в которых уровень воды равен 3 и ниже, то получим решение для Майтон-1.
Ведь в этом варианте ячеек с уровнем воды 4 и выше просто не может быть.

2. Когда не перевалит. Рассуждаем аналогично.
Если просуммируем по ячейкам, в которых уровень воды равен 2 и ниже, то получим решение для Майтон-2.
Ведь в этом варианте ячеек с уровнем воды 3 и выше просто не может быть.
...
Рейтинг: 0 / 0
19.02.2020, 11:25
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928423
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Aleksandr Sharahov,

В словесном описании есть алгоритм?
...
Рейтинг: 0 / 0
19.02.2020, 13:53
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928476
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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 и вызываем для этого соседа процедуру среза.

Понятно, что от рекурсии в процедуре среза можно избавиться.
Доказательство корректности алгоритма оставляю читателю )
...
Рейтинг: 0 / 0
19.02.2020, 14:49
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928527
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я думаю о параллелизме острова. Пока - мысли. Даже не тезисы а просто мысли.

1. Чтоб эффективно параллелить обработку матрицы высот (HeightMatrix) мне нужна гарантия
что каждый процесс (поток) владеет своей частичкой матрицы.

2. Если остров представлен квадратной матрицей - то мы его можем разделить на 4 квадранта.
Как разделить? Провести искусственную высоту равную +MAX_INT по вертикали и по горизонтали через центр.

3. Можно применить алгортм заливки водой каждого квадратнта одновременно (4 процесса запроцессят каждый
свою матрицу данных).

4. После финала 4х процессов я убираю искусственные стенки. Я их понижаю до исходного уровня.
И повторяю 1 общий алгоритм для всего острова.

5. Моя идея базируется на предположении что 80% работы по переливанию воды уже выполнены на шаге (3)
и осталось только слегка подкорректировать водичку в "кратерах" и "ямках".
...
Рейтинг: 0 / 0
19.02.2020, 16:01
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928530
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
По визуализации.

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

Для визуализации алгорима желательно Grayscale картинку трансформировать в географическую. С цветовой
маркировкой как принято в картографии.

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

 
...
Рейтинг: 0 / 0
19.02.2020, 16:08
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928542
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton
Я думаю о параллелизме острова...


Идея очевидная, и легко реализуемая.
Но отсутствует гарантия ускорения, можно нарваться на полный пересчет.
...
Рейтинг: 0 / 0
19.02.2020, 16:34
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928543
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov
mayton
Я думаю о параллелизме острова...


Идея очевидная, и легко реализуемая.
Но отсутствует гарантия ускорения, можно нарваться на полный пересчет.

Ну это то о чем я говорил. Графовые алгоритмы вообще *уево параллелятся. Но
нам повзло. У нас есть некая пространственная когерентность. Тоесть группа вершин
может быть легко разделена или сгруппирована по декартовому признаку.

В полно-связном графе например это сделать нельзя. А в для 6-связного (хексагоны) или для 4 связной вершины
(пиксели) - очень даже удобно.
...
Рейтинг: 0 / 0
19.02.2020, 16:39
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928545
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
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) рекурсия заменена либо на "поиск в ширину" (с очередью), либо на "поиск в глубину" (со стеком)?
...
Рейтинг: 0 / 0
19.02.2020, 16:45
| Ответить | Цитировать | Написать  
Задачка про остров
    #39928571
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Имя пользователя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) Пофигу, у меня цикл в глубину с запоминанием направления возврата.
...
Рейтинг: 0 / 0
19.02.2020, 17:12
| Ответить | Цитировать | Написать  
Задачка про остров
    #39929196
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Взял картинку 22077693 , инвертировал (у меня чем более темный пиксель тем больше высота, так воспринимать картинку лучше), обработка с параметрами 30 - уровень океана после отлива, 100 - уровень до которого поднималась вода. Картинку для форума пережал в jpg меньшего размера, на ней много артефактов сжатия.
...
Рейтинг: 0 / 0
20.02.2020, 22:13
| Ответить | Цитировать | Написать  
Задачка про остров
    #39929230
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
iOracleDev,

визуально)
но из-за сжатия невозможно оценить правильность работы
...
Рейтинг: 0 / 0
21.02.2020, 00:00
| Ответить | Цитировать | Написать  
Задачка про остров
    #39929235
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Aleksandr Sharahov,

Погонял по высотам и по своим картинкам с концентрическими системами, вполне себе адекватно работает, правда медленно.
...
Рейтинг: 0 / 0
21.02.2020, 00:20
| Ответить | Цитировать | Написать  
Задачка про остров
    #39929305
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
iOracleDev
Aleksandr Sharahov,

Погонял по высотам и по своим картинкам с концентрическими системами, вполне себе адекватно работает, правда медленно.


у меня 22083065 самый быстрый из 3х проверенных, его гонял?
...
Рейтинг: 0 / 0
21.02.2020, 10:02
| Ответить | Цитировать | Написать  
Задачка про остров
    #39929382
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov
iOracleDev
Aleksandr Sharahov,

Погонял по высотам и по своим картинкам с концентрическими системами, вполне себе адекватно работает, правда медленно.


у меня 22083065 самый быстрый из 3х проверенных, его гонял?

Хвастун.
...
Рейтинг: 0 / 0
21.02.2020, 12:08
| Ответить | Цитировать | Написать  
Задачка про остров
    #39929388
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
mayton,

ты не понял: имелось в виду из 3х *моих* проверенных
...
Рейтинг: 0 / 0
21.02.2020, 12:19
| Ответить | Цитировать | Написать  
Задачка про остров
    #39929394
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Aleksandr Sharahov
mayton,

ты не понял: имелось в виду из 3х *моих* проверенных

Ладно не обижайся. Я шучу. Пятница все таки.

Над параллелизмом думал?
...
Рейтинг: 0 / 0
21.02.2020, 12:27
| Ответить | Цитировать | Написать  
Задачка про остров
    #39929397
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Aleksandr Sharahov
у меня 22083065 самый быстрый из 3х проверенных, его гонял?

Нет конечно, гонял свой с последовательными срезами сверху, правда считал не на массиве а на связном списке узлов, внутри узла массив из соседей и геттер, плюс очередь использовал, просто на массиве должно быть намного быстрее. Сложность алгоритма K*N, где K - количество уровней, N - количество плиток, распарралелить думаю не получится, следующий уровень зависит от предыдущего, хотя надо подумать, наверное можно посчитать каждый срез как будто он единственный, а потом последовательно наложить начиная сверху, тогда распараллелится очень хорошо.

Твой я не понимаю, за счет чего он должен выбираться из кратеров? Ты для каждой плитки ищешь выход в океан? Как определяешь что не попал в loop по плиткам? Как выходишь за пределы стены кратера, при условии неограниченной вложенности кратеров и их уровней? Сколько проходов по каждой плитке и от чего зависит, какая временная сложность алгоритма?
...
Рейтинг: 0 / 0
21.02.2020, 12:31
| Ответить | Цитировать | Написать  
Задачка про остров
    #39929399
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iOracleDev
Участник
Aleksandr Sharahov
ты не понял: имелось в виду из 3х *моих* проверенных

Берешь картинку и вперед)) картинка от mayton-а не очень хорошая для проверки, она большая но сложных случаев, чтобы было сразу видно ошибки, на ней нет.
...
Рейтинг: 0 / 0
21.02.2020, 12:34
| Ответить | Цитировать | Написать  
25 сообщений из 421, страница 9 из 17
  9  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Задачка про остров
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&startmsg=39928051&tid=1339799]:
 0ms
get settings:
 9ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 166ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 55ms
get tp. blocked users:
 1ms
others: 11ms
total:  272ms
созд. / загр.: 272ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]