Рекурсия с мемоизацией на структуру данных

Question

Я пытаюсь реализовать памятку по следующей проблеме. Структура данных выглядит следующим образом:

ROWS = {368: [247, 257], 257: [368], 2468: [357], 357: [2468], 358: [247], 247: [358, 368]} 

Это словарь, в котором ключи имеют значения в виде списков. В каждом списке каждого ключа элементы содержат цифры, отличные от ключа. Пример: если мы возьмем ключ 368: [247, 257] мы увидим, что 247 не содержит ни одной цифры из своего ключа 368. То же самое с 257 и 368, разные цифры.

Проблема заключается в следующем: Построить стену определенной высоты с числами друг над другом, используя эту структуру данных так, чтобы ни у соседей не было одинаковых цифр. Например стена 4 уровня будет:

1. 368, 247, 358, 247
2. 368, 257, 368, 257 ... and so on.

Вопрос в том, сколько возможных комбинаций высоты n (в нашем случае 4)?

Я сделал базовое рекурсивное и очень неэффективное и не элегантное решение, когда начинал с одного элемента:

ROWS = {368: [247, 257], 257: [368], 2468: [357], 357: [2468], 358: [247], 
247: [358, 368]} 
SUM=0

def count_configurations( elem , rows ) :
   global SUM
   if rows == 1 :
      SUM += len(ROWS[elem])
      return len(ROWS[elem])
   else:
      for k in ROWS[elem] :
         count_configurations( k, rows-1 )

Он отлично работает, но когда мы поднимаемся на большую высоту без Memoization, он остается навсегда. Также, если попытка вернуть count_configurations (k, row-1) , она возвращается к первому элементу и завершается, давая неправильный ответ. Проблема в том, что когда мы имеем дело с этой проблемой, у нас нет возвратов в виде чисел, как в Фибоначчи, но у нас будут возвращаться некоторые другие списки. Пример : Для уровня 4 будет что-то вроде:

(368, 4) : [(247:3), (257:3)]   (composed of 2 elements of level 3, then 
(247:3) :  [(358:2), (368:2)]  and  (257:3) :[(368,2)] (composed of elements of level 2)

и так далее, пока мы не окажемся на уровне 1, где мы можем заменить фактические значения:

(368,1)=2 , (247, 1) = 1 , etc ... 

Может ли в этом случае быть реализована Memoization? Я использовал неправильную структуру данных и перебивал сложные вещи? Можете ли вы дать мне несколько советов о том, как упростить вещи?

Заранее большое спасибо.

Answer 1

Мемоизация здесь работает нормально:

>>> from functools import lru_cache
>>>
>>> @lru_cache(None)
... def count_configurations( elem , rows ) :
...     if rows == 1 :
...         return len(ROWS[elem])
...     else:
...         return sum(count_configurations( k, rows-1 ) for k in ROWS[elem])

Примеры:

>>> count_configurations(247, 30)
2178309
>>> count_configurations(368, 100)
927372692193078999176
>>> count_configurations(357, 100)
1
>>> count_configurations(257, 100)
573147844013817084101