Сегодня решил последнюю задачу в разделе Home на checkio. Самой интересной была задача про лабиринт. По сути, именно она заставила меня поменять подход к решению задач.
Начало
Зарегистрировавшись там два года назад, я успешно забыл о ресурсе, с головой уйдя только в работу над проектами. Несколько месяцев назад мне снова стало интересно заниматься решением задач по программированию. Первым делом перерешал всё, что нашёл в Elementary, потом взялся за Home. Первые задачи решал одну за одной, просто потому, что они были очень простыми. В Home делал всё ровно тоже самое, пока не взялся за задачу с пирамидой. Не скажу, что она была сложной, но она мне понравилась. Потом был лабиринт. И вот на этой задаче я остановился надолго.
Другой подход
Начав заниматься на checkio, я никогда не ставил себе цель обогнать всех или перерешать все задачи в кратчайшие сроки. Моими целями были развлечение и самообразование. Решать задачи одну за одной, не ковыряясь с ними, было не очень весело, а самообразованием это тоже сложно назвать. Поэтому, взявшись за лабиринт, я не стал искать сравнение алгоритмов поиска в графе и выбирать один из них, чтобы затем быстро его реализовать. Вместо этого взял с полки "Искусственный интеллект" Питера Норвига и стал не спеша читать главу про неинформированный поиск. Потом уже выбрал двунаправленный поиск, просто потому что мне он показался интересным и достаточно оптимальным (хотя о какой оптимальности можно говорить при лабиринте 10 на 10 клеток). Но и тут я не стал сразу же писать код. Где-то 4 дня (все майские праздники) просто в свободное время делал в блокноте наброске о способе обхода дерева, прикидывал, как хранить переферию и в какие структуры данных положить граф. Набрал 4 разных способа реализации. Было интересно. Ну а вчера вечером уже доделал решение в коде, а сегодня, перечитав его, опубликовал. Вот это было интересно. Когда только прочёл задание, то просто хотел взять A* и по-быстрому накидать решение, хорошо, что сделал иначе.
Решение
Решение доступно только тем, кто сам уже решил эту задачу. Мой код доступен по ссылке - Open Labyrinth.