Решение головоломки с хабра на Haskell

На днях на хабре проскочила заметка с одной простой, но изящной головоломкой.
Суть вкратце такова. Имеется автомат с пятью барабанами, где каждый барабан может принимать значение одной из карточных мастей (то есть, всего 4 положения). Каждый барабан руками можно вращать только в одну сторону на один шаг, при этом автоматически также могут вращаться остальные 4 барабана. Матрица таких вращений-сдвигов представлена ниже:
===

     1  2  3  4  5
    --------------
1:  +1 -1 +1  0  0
2:  +1 +1  0  0 -1
3:   0 -1 +1 -1  0
4:  -1  0  0 +1 +1
5:   0  0 -1 +1 +1

===
То есть, например, при вращении барабана N1 на один шаг (примем это направление за положительное), барабан N2 автоматически будет повернут на 1 шаг в обратном направлении, барабан N3 - так же как и барабан N1 - будет повернут на 1 шаг вперед, а положения барабанов N4 и N5 не изменятся.

Задача в следующем. Имеется начальное положение всех барабанов - 0 2 0 3 1, то есть, первый барабан в положении 0, второй - в 2, третий - в 0 и т.д.
Требуется найти такую последовательность поворотов барабанов, чтобы в итоге их положения приняли значения 0 0 2 0 0. Мы эту задачу чуть усложним и будем искать не просто последовательность, а последовательность минимальной длины.

Для решения будем использовать Haskell.

Итак, очевидно, что операции поворотов барабанов коммутативны, то есть, если повернуть один барабан на N шагов, а затем другой на K шагов, то операции, выполненные в обратном порядке, приведут к точно такому же результату.
Таким образом, у нас имеется 4^5 комбинаций всех состояний барабанов (5 автоматов по 4 масти на каждый). Нам достаточно перебрать их все и, применяя к начальному состоянию системы, посмотреть, какое конечное состояние они дают. Отберем из них все те комбинации поворотов, которые приводят к требуемому конечному состоянию, а затем из полученной последовательности оставим наиболее короткое.

Итак, приступаем к кодированию.
Сначала определим константные значения: количество барабанов, количество состояний у каждого барабана, матрицу сдвигов, начальное и конечное состояния системы.
===

wheelCnt = 5
wheelStatesCnt = 4

m = [[ 1,-1, 1, 0, 0], 
     [ 1, 1, 0, 0,-1],
     [ 0,-1, 1,-1, 0],
     [-1, 0, 0, 1, 1],
     [ 0, 0,-1, 1, 1]]

start = [0,2,0,3,1]
end   = [0,0,2,0,0]

===

Генерацию состояний барабанов будем осуществлять следующим образом: мы будем просто перебирать все число от 0 до 4^5 и для каждого из них генерировать список длины 5, который представляет очередное состояние барабанов. В дальнейшем будем применять полученное состояние на каждом шаге к стартовому состоянию системы.
Итак.
===

-- дополнение списка l нулями в количестве n слева
addZero l 0 = l
addZero l n = addZero (0:l) (n-1)

-- формирование состояния барабанов по заданному числу n
mkState 0 acc = addZero acc (wheelCnt - length acc)
mkState n acc = mkState (n `div` wheelStatesCnt) 
                (n `mod` wheelStatesCnt : acc)

===

Далее идет функция getState, которая "применяет" текущее состояние барабанов к стартовому состоянию системы и возвращает новое состояние системы. Обратите внимание на внутреннюю функцию canonize, которая приводит состояние системы к каноническому виду, когда все индексы приводятся к диапазону от 0 до 3 включительно.

===

-- получить состояние системы
getState st = f st 0 start
   where 
     step i n st = zipWith (\x y -> x * n + y) 
                           (m !! i) st 
     canonize st = map (\x -> x `mod` wheelStatesCnt) st 
     f st i acc = if null st then canonize acc
                  else f (tail st) (i+1) 
                         (step i (head st) acc) 

====

Затем идет функция - "сердце" программы, которая выполняет основную работу.
====

task n acc = 
    let st = mkState n [] in
    let sums = getState st in
    if n < wheelStatesCnt ^ wheelCnt then
       if sums == end then task (n+1) ((st,sums):acc)     
       else task (n+1) acc
    else reverse acc

==== Она принимает на вход значение текущего счетчика n и изначально пустой список-аккумулятор, в который мы будем накапливать отобранные элементы. Сохранять будем для наглядности туплы, где первым элементом будет текущее состояние барабанов, а вторым - полученное состояние системы. Ну и заключительным шагом нам необходимо из полученного списка туплов (если он не пустой) отобрать значение, которое даст нам минимальное количество поворотов барабанов (понятно, что это будет просто сумма всех элементов списка состояний барабанов, то есть, нам нужно найти то значение, где она минимальна). ===

-- выборка "наименьшего" элемента списка
getMin [] res = res
getMin (h:t) res =
    if sum (fst h) < sum (fst res) then getMin t h
    else getMin t res

main = 
    let r = task 0 [] in
    if null r then print "Result not found..."
    else print $ getMin r (head r)       

===

Функция main, по сути, просто вызывает выводит на экран найденное значение, или сообщение "Result not found...", если ничего не найдено.
Результатом решения задачи я получил состояние барабанов [0,3,1,3,3], то есть, для перехода из начального в конечное состояние системы необходимо повернуть 3 раза второй барабан (нумеруем их здесь с единицы), 1 раз третий и по 3 раза четвертый и пятый. Итого, нам требуется 10 поворотов барабанов.

Вот и всё. Надеюсь, вам было интересно )