4

введите сюда описание изображения

Есть два круга, образующих в сумме 10 камешков. При поворачивании первого круга, меняются два камешка во втором и наоборот. Они могут кружиться по часовой оси и против. Нужно, чтобы красные камешки были в красном кругу а зеленые в зеленом. Красные камешки имеют число 0, а зеленые камешки число 1. С экрана вводится два списка чисел, первый список чисел это красный круг, второй список это второй круг. Нужно найти наикратчайший путь, при котором будет правильная комбинация, т.е

1 0 0 0 0 0
1 1 0 1 1 1

Например, для кругов

1 0 1 0 0 0
1 1 1 0 1 1

Вывод

('red',m)('green',m)

m - это поворот в направлении +1, а p - это поворот в направлении -1

4
  • Перебором или динамикой?
    – Qwertiy
    28 дек 2021 в 1:09
  • через динамику было бы по понятней
    – Khimer
    28 дек 2021 в 4:45
  • 1
    Я не обдумывал решение, но состояние с 12-битной маской и 4 перехода скорее всего могут подойти. Надо попасть в 0, значит можно запустить обход из 0 с ленивой динамикой.
    – Qwertiy
    28 дек 2021 в 9:50
  • Не 12 битная, а 10 битная, т.к. две ячейки - общие. А вообще задача из области теории групп. Подгруппа симметрической группы S10.
    – Alex Alex
    5 янв 2022 в 16:33

1 ответ 1

2

Граф содержит не более 1024 вершин. Поиск в ширину без всяких оптимизаций.

import collections


R0, R1, R2, R3, R4, R5 = 0, 1, 2, 3, 4, 5
G0, G1, G2, G3, G4, G5 = 0, 6, 2, 7, 8, 9
SIZE = 10


def r_m(p):
    p[R0], p[R1], p[R2], p[R3], p[R4], p[R5] = \
    p[R1], p[R2], p[R3], p[R4], p[R5], p[R0]


def r_p(p):
    p[R1], p[R2], p[R3], p[R4], p[R5], p[R0] = \
    p[R0], p[R1], p[R2], p[R3], p[R4], p[R5]


def g_m(p):
    p[G0], p[G1], p[G2], p[G3], p[G4], p[G5] = \
    p[G1], p[G2], p[G3], p[G4], p[G5], p[G0]


def g_p(p):
    p[G1], p[G2], p[G3], p[G4], p[G5], p[G0] = \
    p[G0], p[G1], p[G2], p[G3], p[G4], p[G5]


def done(p):
    return \
        all(p[r] == 'r' for r in (R1, R3, R4, R5)) and \
        all(p[g] == 'g' for g in (G1, G3, G4, G5))


def solve(start):

    def bfs(start):
        visited = set()
        queue = collections.deque()

        queue.append((start, None, None))
        visited.add(start)

        while queue:
            item = queue.popleft()
            p, _, _ = item
            yield item
            for op in r_m, r_p, g_m, g_p:
                q = list(p)
                op(q)
                q = tuple(q)
                if q not in visited:
                    queue.append((q, op, item))
                    visited.add(q)

    def moves(path):
        names = {
            r_m: ('red', 'm'),
            r_p: ('red', 'p'),
            g_m: ('green', 'm'),
            g_p: ('green', 'p')
        }

        def moves(path):
            while path is not None:
                _, op, path = path
                if op is None:
                    break
                yield names[op]

        return tuple(moves(path))[::-1]

    for p in bfs(start):
        if done(p[0]):
            return moves(p)
    return None


def main():
    start = [None] * SIZE
    start[R0] = 'r'
    start[R1] = 'g'
    start[R2] = 'r'
    start[R3] = 'g'
    start[R4] = 'r'
    start[R5] = 'r'
    start[G1] = 'g'
    start[G3] = 'r'
    start[G4] = 'g'
    start[G5] = 'g'
    print(solve(tuple(start)))


main()

Анализ всех 1024 стартовых позиций показывает что самая длинная последовательность ходов до выигрыша - 8 ходов. Например для

start[R0] = 'r'
start[R1] = 'g'
start[R2] = 'r'
start[R3] = 'g'
start[R4] = 'g'
start[R5] = 'g'
start[G1] = 'r'
start[G3] = 'g'
start[G4] = 'r'
start[G5] = 'g'
(('red', 'm'), ('red', 'm'), ('green', 'p'), ('green', 'p'), ('red', 'm'), ('green', 'm'), ('red', 'p'), ('red', 'p'))
5
  • Что-то код не работает как надо. Выдает (('red', 'm'), ('green', 'm')). Может в done ошибка?(не 4 точки, а 5).
    – TigerTV.ru
    6 авг 2022 в 18:46
  • 1
    @TigerTV.ru, восемь - это самая длинная возможная последовательность ходов. Больше восьми ходов решений нет. Если решения меньше - например ноль ходов. Больше нет. 6 авг 2022 в 18:49
  • 1
    @TigerTV.ru, код приведён для примера из вопроса. Там решение в два хода. 6 авг 2022 в 18:53
  • Спасибо за разъяснения :)
    – TigerTV.ru
    6 авг 2022 в 18:55
  • 1
    @TigerTV.ru, в последней фразе вопроса символы m и p перепутаны. Что запутывает. :) 6 авг 2022 в 18:56

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.