Интересная задачка

[Igors]

Добрый день

Увидел задачку, и очень она мне понравилась

Дано поле, на котором случайным образом разбросаны пища (мощность 1-10), капканы (мощность 1-10), камни и пустые поля. Транспортер должен обойти максимально возможное число полей за минимальное количество ходов. При этом, если он входит на клетку с пищей, то мощность у него прибавляется на заданное количество единиц, но не более, чем на 100. Если транспортер попадает в капкан, его энергии убавляется (если достигнет нуля - транспортер уничтожен). Камни пройти нельзя.

Правда совсем нет мыслей как делать А у Вас?

Спасибо

[Bepec]

Нет данных о видимости.

На сколько клеток есть данные? Или всё поле сразу дано? Или же транспортер слепой и знает только  можно в том направлении ехать или нельзя?/* Что будет при столкновение с камнем? мало данных.*/

update: увидел про камень.

Если нет видимости, то простой алгоритм обхода. Если есть - более сложные алгоритмы.

[CuteBunny]

Мне кажется алгоритм Прима здесь применим.

[Странник]

уточните следующее:
- начальное поле
- начальная мощность
- требует ли перемещение затрат мощности?
- может ли транспортер перемещаться по диагонали?
- после первого посещения клетки с пищей или капканом она становится пустой?
- должен ли транспортер выжить?

[Bepec]

Если будут усложнения получится маленький ботик для этой игры (задачи).
 

PS Я в принципе ничего другого от Igors не жду Отсутствие конкретизированных требований и ограничений и неясная задача :-D Стандарт.

[Old]

Можно сделать арену и гонять там ботов, боты делать на javascript. Нужно только определится с API.

[Majestio]

Если будут усложнения получится маленький ботик для этой игры (задачи).
PS Я в принципе ничего другого от Igors не жду Отсутствие конкретизированных требований и ограничений и неясная задача :-D Стандарт.

• Если "видимость" - с алгоритмом проблем нет. Задача решается обходом дерева перемещений-возвратов, с оценкой весов путей.
• Если видимости нет - сложнее. Можно попробовать обучающиеся нейронные сети, но это сработает только в том случае, если разброс "сущностей" на поле - случайный-неравномерный или закономерный

ИМХО конечно.

[Bepec]

В принципе несложная задачка, решаемая простыми алгоритмами. НО... Но Igors мастер таких вот размытых задач

[Igors]

уточните следующее:
- начальное поле
...
- должен ли транспортер выжить?

Нет данных о видимости.

На сколько клеток есть данные? Или всё поле сразу дано? Или же транспортер слепой и знает только  можно в том направлении ехать или нельзя?/*

"Ну Вы блин даете" Зачем говорить о некой "видимости" если условие начинается со слов "дано поле"? Наверное пока дочитали до конца - уже забыли начало И прекрасный вопрос "должен ли транспортер выжить?" - а сами-то как думаете? Или "начальное поле" - типа нет, сначала он на вертолете летает, а потом уж....    

Другие вопросы имеют смысл

- начальная мощность
- требует ли перемещение затрат мощности?
- может ли транспортер перемещаться по диагонали?
- после первого посещения клетки с пищей или капканом она становится пустой?

(особенно последний). Но ответы на них мне неизвестны (задача не моя). Поэтому мы имеем право принять такие соглашения

- да, есть начальный запас топлива, напр 100 (максимальный)
- нет, перемещение не требует затрат, только капкан уменьшает энергию
- нет, перемещение по диагонали запрещено
- нет, после посещения пищи/капкана они не исчезают.

Хотя я в упор не вижу что это меняет - с этими условиями или др - все равно ни одной мысли нет  

Если "видимость" - с алгоритмом проблем нет. Задача решается обходом дерева перемещений-возвратов, с оценкой весов путей.

Как только я слышу что-то типа "проблем нет" - мгновенно в голове проносится фразв "це дiлa не буде". Максимум человек отпихнется ссылкой на нечто (часто вообще не имеющее отношения) - и все. Или я ошибаюсь ?    

Если видимости нет - сложнее. Можно попробовать обучающиеся нейронные сети, но это сработает только в том случае, если разброс "сущностей" на поле - случайный-неравномерный или закономерный

Ну пошли понты  

В принципе несложная задачка, решаемая простыми алгоритмами. НО...

Но могут взять за жопу и предложить ответить за свою похвальбу  

[Bepec]

Видимость я спрашивал.

Дано поле 40 на 40.

Оно закрыто как в сапёре, ИЛИ мы имеем данные о том, что находится в каждой клетке данного поля?

PS ваша (или скопированная) формулировка имеет двоякое значение. То ли мы имеем все данные, то ли мы имеем только размеры поля.

PPS про выживание вопрос интересный, а не глупый. Открытие последней клетки с капканом (-10hp) убьёт транспортёр (10hp) и что будет? победа или поражение? В простых играх этот момент меня иногда выбешивал Когда всё, босса завалил, счастливый стоишь и оп - яд тебя добивает И вместо "Вы прошли игру" -> "Ты сдох мерзкий герой"

[Igors]

Видимость я спрашивал.

Отвечаю - весь расклад известен, все клетки "открыты"

[Old]

- да, есть начальный запас топлива, напр 100 (максимальный)

Ok

- нет, перемещение не требует затрат, только капкан кмкньшает энергию

Не согласен. Перемещение требует -1 энергии.

- нет, перемещение по диагонали запрещено

Ok

- нет, после посещения пищи/капкана они не исчезают.

Тоже не согласен. По мне, так и первое и второе должно исчезнуть после контакта.

Хотя я в упор не вижу что это меняет - с этими условиями или др - все равно ни одной мысли нет  

А здесь интересно экспериментировать. Описал логику, запустил в арене, посмотрел результат. Поменял карту, запустил, посмотрел.
Для начала лобовая логика: двигаться по линии вправо, пока не дойдешь до конца карты -> опуститься вниз на одну клетку и двигаться влево, до начала карты. А потом можно пробовать варианты с обходом препятствий.
Или второй вариант, двигаться по спирали от стартовой точки.
Много всего можно придумать, но интересно будет когда будет арена и визуально можно будет смотреть на действия бота.

[Old]

Отвечаю - весь расклад известен, все клетки "открыты"

Здесь тоже не соглашусь. По мне интересней, если бот будет иметь ограниченную видимость.

[Majestio]

Дано поле, на котором случайным образом разбросаны пища (мощность 1-10), капканы (мощность 1-10), камни и пустые поля. Транспортер должен обойти максимально возможное число полей за минимальное количество ходов. При этом, если он входит на клетку с пищей, то мощность у него прибавляется на заданное количество единиц, но не более, чем на 100. Если транспортер попадает в капкан, его энергии убавляется (если достигнет нуля - транспортер уничтожен). Камни пройти нельзя.

Учитывая последующие "уточнения" - я бы предложил алгоритм, похожий на "обойти ходом шахматного коня поле". Идея "правильности" алгоритма - планировать так последующий ход, чтобы как можно плотнее прижиматься к краям поля. Иными словами - сужающаяся спираль. Я бы пробовал именно так.

[Igors]

нет,
...
Тоже не согласен. По мне, так и первое и второе должно исчезнуть после контакта.
...
Здесь тоже не соглашусь.
...

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

А здесь интересно экспериментировать. Описал логику, запустил в арене, посмотрел результат. Поменял карту, запустил, посмотрел.
Для начала лобовая логика: двигаться по линии вправо, пока не дойдешь до конца карты -> опуститься вниз на одну клетку и двигаться влево, до начала карты. А потом можно пробовать варианты с обходом препятствий.
Или второй вариант, двигаться по спирали от стартовой точки.
Много всего можно придумать, но интересно будет когда будет арена и визуально можно будет смотреть на действия бота.

Я тоже думал об этих вариантах (других не было), но они не имеют никакой разумной "стратегии". Напр встретив камень мы его обошли (пусть пока не знаю как) но при этом наш порядок обхода пострадал - напр остались клетки позади камня. И что дальше? Продожать сканирование в данном порядке - а как потом вернуться к пропущенным? Примерно то же когда много капканов