Comments 9
Дочитал до update_constr и остановился. Почему вы выбрали кортеж для хранения данных?
all или any с generator expression хорошо подойдут для реализации satisfied
for direction in ('horizontal','vertical'): for move in (+1,-1):
Можно все четыре варианта прописать руками и тогда будет один цикл вместо двух. Код будет чуть проще.
Я такой цикл предпочитаю заменить на for dir, mov in get_neighboars(...): которая сгенерирует все возможные варианты. Туда же уйдёт фильтрация значений выходящих за границы поля.
В коде очень много отступов, что делает его сложным для чтения. Я бы порекомендовал измерить цикломатичискую сложность и упростить код, чтобы она не превышала 10. Я обычно стараюсь в 5ку уложиться.
Спасибо. Если у тебя есть такая возможность, ты не мог бы показать, как бы ты реализовал подобную программу? Было бы интересно посмотреть.
Вернулся из отпуска, разгрёб дела и вот решение.
Глобальные отличия:
Я предпочитаю координаты хранить в порядке (row, col) , обычно поле это двумерный массив где первый индекс это ряд. value = field[row][col].
Вместо чистой рекурсии, я использую "Поиск с возвратом" (англ. backtracking). Я конечно предпочитаю иммутабл объекты, но в алогитмических задачака стараюсь делать решения O(1) по памяти.
Во втором поле None я земенил 0. Меньше текста и поле визуально выглядит однородным.
Дополнительные требовани которые я предявляю к своему решению:
Проходит все проверки ruff, включая наличие аннотаций, а также проверки mypy
Миниму использование базовых типов. Row, Col, Point, вместо int, int, tuple. Прочитал про "Одержимость элементарными типами" https://refactoring.guru/ru/smells/primitive-obsession и решил попробовать. Добавляет многословности и кучу проблем с mypy. Еще поиграюсь в своих проектах, а вот в рабочии тащить пока не буду. Техника интересная, но я еще не разобрался для каких проектов она будет полезна. Для текущей задачи это перебор.
Цикломатическая сложность меньше или равна 5ти (Больше 10 считается, что код плохой и его сложно поддерживать).
Вот метрики для моего и Вашего кода:
54:4: 'Field.__init__' 1
62:4: 'Field._get_row_side' 2
68:4: 'Field.is_empty' 1
74:4: 'Field._can_move' 1
79:4: 'Field._update' 1
83:4: 'Field._in_field' 1
86:4: 'Field.make_next_move' 5
107:0: 'traverse' 5
127:0: 'find_path' 1
136:0: 'extract_message' 4
1:0: 'search' 2
35:0: 'depth_first_search' 6
81:0: 'update_constr' 1
93:0: 'satisfied' 3
106:0: 'find_adjacent_cells_with_constr' 13
210:0: 'extract_message' 4Чтобы получить низкую сложность я использовал инкапсуляцию.
Логика работы с полем собранна в Field. Там спрятанна и чехарда с двумя частями поля и проверка на потраченные ходы. В самой рекурсии вы просто получаете следующий ход.
Код здесь:
https://gist.github.com/Cjkjvfnby/7766935f710aa9d854cfb4826905d3af
Я примерно в таком же стиле решал бы эту задачу на интервью, только грязнее и вообще без аннотаций.
По количеству строк у меня вышло более короткое решение, обычно это не так. Возможно это из-за массового дублирования кода. У вас нормальные имена переменных им комментарии не нужны. В случае комментирования recrf кода, можно сделать отдельную функцию и использовать комментарий для её имени.
# finish cell
finish = (15, 5)
# next col is inside grid
if next_col >= 0 and next_col < num_cols:
next_row = cell_row
else:
continueВам привет от https://github.com/codespell-project/codespell, ловит, то что сложно заметить глазом.
173: consits ==> consists
292: exctracted ==> extracted
Вот хорошая дискуссия про сложение строк: https://stackoverflow.com/q/39622122/1310066
В контексте решения алгоритмических задач, алгоритмическая сложность предпочтительней читаемости.
Решение головоломки из университетского квеста с помощью Python