Ключи и замки II — Справочник

Описание задачи

Дан "мастер-ключ" (keyTpl). Нужно найти все производные ключи, которые открывают нужное количество замков.

Правило генерации

У производного ключа каждый "зубчик" (символ) должен быть ≤ символу в keyTpl (по алфавиту).

Из D можно сделать: A, B, C, D
Из A можно сделать: только A
Из E можно сделать: A, B, C, D, E

Формат входных данных

keyTpl: шаблон_ключа
locks: массив замков
minLocks: минимум замков для открытия

Пример

Условие

keyTpl: "DCB"
locks: ["A-B", "-CB"]
minLocks: 2

Анализ

Позиция 0: keyTpl='D', можно A,B,C,D
Позиция 1: keyTpl='C', можно A,B,C
Позиция 2: keyTpl='B', можно A,B

Замок "A-B": нужно [A][любой][B] → A?B
Замок "-CB": нужно [любой][C][B] → ?CB

Для обоих замков:
  Позиция 0: A (из A-B) ∩ {A,B,C,D} = A
  Позиция 1: C (из -CB) ∩ {A,B,C} = C
  Позиция 2: B (общее) ∩ {A,B} = B

Ключ: "ACB"

Результат

countKeys → 1
findKeys → ["ACB"]

Ключевые моменты

Вместо 5^N перебираем только валидные "спиленные" комбинации
Количество вариантов для позиции i = ord(keyTpl[i]) - ord('A') + 1
Проверка замков стандартная (- совпадает с любым)