Solution to Valladolid Archive, problem 520: Append.

> import ReaderMonad

Representation of a code.

> data Code = Char Char | BackRef Int Int deriving Show

How to read a code.

> readerCode :: Reader Code
> readerCode = do n <- reader
>                 if n==0
>                    then do c:[] <- Reader lex
>                            return (Char c)
>                    else do m <- reader
>                            return (BackRef n m)

> instance Read Code where
>   readsPrec _ = toReadS readerCode

The number of ways of splitting is the number of safe splitting points.
One can split anywhere except across back-references.

We count these safe splitting points by going through the code list
backwards.  If we see a single character, that's one more safe point.
If we see a back-reference, however, we need to remember a "skip count",
i.e., how many future characters must be skipped before we resume
counting splitting points.

A back-reference "BackRef p n" makes us skip the next p-1 characters
before we resume counting.  Except if we are already in skip mode:

- If the reference points inside the skip region, i.e., p+n <= s, it
  is just like n ordinary characters, so the skip count decreases by
  n.

- If the reference points outside the skip region, i.e., p+n > s, we
  are extending the skip region to accomodate it, so we reset the skip
  count to p-1.
  
> numCuts :: [Code] -> Int
> numCuts codelist = fst (foldr count (-1,0) codelist)
>   where count :: Code -> (Int,Int) -> (Int,Int)
>         count (Char _) (points,skip) | skip==0 = (points+1, 0)
>                                      | otherwise = (points, skip-1)
>         count (BackRef p n) (points,skip) | p+n<=skip = (points, skip-n)
>                                           | otherwise = (points, p-1)

> main :: IO ()
> main = do codelist <- readCodeListIO
>           if null codelist
>              then return ()
>              else do putStrLn (show (numCuts codelist))
>                      main
>   where readCodeListIO = catch (do line <- getLine
>                                    code <- readIO line
>                                    more <- readCodeListIO
>                                    return (code:more))
>                                (\_ -> return [])
>         readCodeListIO :: IO [Code]


I also implemented decompression.  It is not used for this problem,
but I wrote it and I don't want to throw it away.

The main idea is to maintain a stack of the decompressed data.  Then
back references can refer to it, and new characters can add to it.
This function does exactly that: take a code and a stack, decode the
code, add it to the stack.

> append :: Code -> String -> String
> append (Char c) s = c:s
> append (BackRef p n) s = drop (p-n) (take p s) ++ s

Then decompression is simply the reverse of the ending stack.  So we
just scan the codes with append and build the stack.

> decompress :: [Code] -> String
> decompress = reverse . (foldl (flip append) [])