Enotstvo & Lorenso
Enotstvo
Слышал про новый конкурс по программированию? Там головоломки и таблица лидеров, как соцсеть. Может, вместе попробуем?
Lorenso
Конечно, звучит как идеальное сочетание ума и заслуг! Давай скоординируемся, подработаем наши профили и вместе выберемся наверх в рейтинге — представь, сколько полезных знакомств и классных рекомендаций мы получим. И кто знает, какие спонсорские контракты или совместные проекты могут появиться? Сейчас скину тебе ссылку, и мы вместе подумаем, с чего начать. Готов сделать из этого отличную возможность для нетворкинга?
Enotstvo
Отлично, но мне больше по головоломкам, чем по общению. Давай сначала посмотрим, что они там придумали.
Lorenso
Отличный разговор – сначала головоломки, потом нетворкинг. Я уже пролистал страницу конкурса; топ-три задания – смесь логических загадок и кодовых головоломок. Задачки непростые, зато как раз для прокачки навыков – и чтобы резюме выглядело круто. Дай знать, какое тебе приглянулось, и разберём его вместе, а потом похвастаемся на табло!
Enotstvo
Я смотрю на это задание с кодом – там надо реализовать рекурсивный решатель для игры в блоки. Кажется, самое интересное упражнение, чтобы отточить логику и навыки рекурсии. Начнём с него.
Lorenso
Отличный выбор! Рекурсия сдвигающими блоками — это классика, мозги взрывает. Представь себе мини-лабиринт: каждый ход – узел, и ты ищешь кратчайший путь к конечному состоянию. Начни с определения хэша состояния (положение всех блоков) и рекурсивного поиска в глубину с откатом, когда натыкаешься на тупик. Не забудь вести список посещенных состояний, чтобы не зацикливаться. Как только достигнешь цели, восстанавливай последовательность ходов и возвращай её. Если застрянешь, добавь простое эвристическое правило — например, посчитай, сколько блоков не на своих местах — чтобы сужать область поиска. Уже есть код, который используешь, или я быстро набросаю шаблон?
Enotstvo
Привет, вот небольшой набросок на Python, чтобы начать рекурсию. Он запоминает состояние доски, использует DFS с откатом и простую эвристику для отсечения. Можешь потом поменять эвристику или добавить мемоизацию, если хочешь. Сейчас код:
```python
import copy
# Пример доски: 0 — пусто, остальные числа — блоки
start = [
[1, 2, 3],
[4, 0, 5],
[6, 7, 8]
]
goal = [
[1, 2, 3],
[4, 5, 0],
[6, 7, 8]
]
def board_hash(board):
"""Преобразует двумерный список в кортеж для хэширования."""
return tuple(tuple(row) for row in board)
def find_zero(board):
for i, row in enumerate(board):
for j, v in enumerate(row):
if v == 0:
return i, j
def moves(board):
"""Генерирует все допустимые ходы как (новая_доска, имя_хода)."""
i, j = find_zero(board)
dirs = [(-1, 0, 'U'), (1, 0, 'D'), (0, -1, 'L'), (0, 1, 'R')]
for di, dj, name in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < len(board) and 0 <= nj < len(board[0]):
new_board = copy.deepcopy(board)
new_board[i][j], new_board[ni][nj] = new_board[ni][nj], new_board[i][j]
yield new_board, name
def heuristic(board):
"""Простая оценка количества неверно расположенных блоков."""
return sum(1 for i in range(len(board))
for j in range(len(board[0]))
if board[i][j] != 0 and board[i][j] != goal[i][j])
def dfs(board, visited, path, depth_limit):
h = heuristic(board)
# Если эвристика равна 0, мы достигли цели
if h == 0:
return path
if depth_limit <= 0:
return None
key = board_hash(board)
if key in visited:
return None
visited.add(key)
for nb, move in moves(board):
res = dfs(nb, visited, path + [move], depth_limit - 1)
if res is not None:
return res
visited.remove(key)
return None
# Запуск с ограничением глубины (например, 20 ходов)
solution = dfs(start, set(), [], 20)
print("Solution:", solution)
```
Lorenso
Отлично начинаешь – чистый и понятный код, нравится трюк с хешем и цикл DFS! Вот пара идей для доработки: веди глобальный словарь с хешем доски, чтобы хранить максимальную достигнутую глубину; это сильно сэкономит время. И попробуй заменить эвристику на манхэттенское расстояние – тоже дёшево, но более информативно, чем просто подсчёт расстановки, так что ты будешь обрезать ветви раньше. А если лимит глубины кажется слишком маленьким, увеличь его или добавь запасной шаг BFS, когда DFS затормозит. Попробуй и скажи, какая структура решения получится – скоро получишь заслуженный значок "Я решил!
Enotstvo
Добавлю заметку и переключусь на расстояние Мэнхэттен. DFS все равно откатывается, но перестанет посещать состояния на большей глубине. Эвристика стала проще в вычислениях, но более избирательна – теперь она отсекает ветки раньше. Подниму лимит глубины до 25 пока что; если застрянет – переключусь на BFS. Путь к решению должен состоять из последовательности ходов U, D, L, R, когда цель будет достигнута. Запущу и отчитаюсь о количестве шагов и пути. Посмотрим, сколько он найдёт.