-- we'll need these later
import Data.MemoCombinators (memo2, integral) 
import Data.Monoid (mempty) 

data Operation = Append | Delete | Copy | Paste
  deriving (Eq,Show)

type Length = Int
type Ticks  = Int
type Chain  = [ Operation ]

opCost :: Operation -> Int
opCost Append = 1
opCost Delete = 1
opCost Copy   = 3
opCost Paste  = 2

chainCost :: Chain -> Int
chainCost = sum . map opCost

-- find all the pairs that multiply to the given value
divisors :: Int -> [ (Int, Int) ]
divisors = integral $ \n -> [ (d,q) | d <- [1..n], let (q,r) = n `quotRem` d, r == 0 ]

-- figure out how to get a string of the given length
-- in exactly the given amount of ticks
chainsToIn :: Length -> Ticks -> [ Chain ]
chainsToIn = memo2 integral integral $ \n t -> case (n,t) of
    (0,0) ->  return []
    (_,t) | t <= 0 -> mempty
    (c,_) | c <= 0 -> mempty
    _     ->  -- helper function to extend chains that generate
              -- the given length by the given suffix
              -- to create chains to the current location
              let moveFrom :: Length -> Chain -> [ Chain ]
                  moveFrom n' c = map (++c) . chainsToIn n' $ t - chainCost c
              -- find all the ways to get to the current location
              in concat [ moveFrom (n-1) [Append]
                        , moveFrom (n+1) [Delete]
                        , do
                            (d,q) <- divisors n
                            moveFrom d $ Copy : replicate (q-1) Paste
                        ]

-- find the optimal chain to e
optimalChainsTo :: Length -> [ Chain ]
optimalChainsTo = integral $ \n ->
  head . dropWhile null $ map (chainsToIn n) [ 0.. ]

-- our solution only has chains with a Delete in it
solution :: Length
solution = head $ filter (all (elem Delete) . optimalChainsTo) [ 0.. ]

solution

optimalChainsTo solution

map chainCost it

-- need a few more libraries
import Text.Printf (printf)
import Control.Monad (forM_)

putStrLn "num ticks chains"
forM_ [ 0 .. 64 ] $ \i ->
  let cs@(c:_) = optimalChainsTo i
  in printf " %2d    %2d %s\n" i (chainCost c) (unwords $ map (map $ head . show) cs)