## Solve the pcp instance with 24 line’s of code

I’m deeply impressed again by Haskell this afternoon. I was thinking about and sovling an install of PCP problem.
To find a sequence (i1,i2,i3…,in) such that s[i1]s[i2]…s[in] is the same as t[i1]t[i2]…t[in]. where
—————————–
| s | 001 | 01  | 01  | 10  |
| t | 0   | 011 | 101 | 001 |
—————————–
Here comes the solution in Haskell.

module Main where

import Data.List(isPrefixOf)

gS = ["001","01","01","10"]
gT = ["0","011","101","001"]

bfs :: (a->[a])->a->[a]
bfs f x = bfs’ [x]
where bfs’ [] = []
bfs’ xs = xs ++ bfs’ (xs >>= f)

expand (s,t) = [(s ++ fst x, t ++ snd x) | x<-zip gS gT, valid (s ++ fst x) (t ++ snd x)]
where valid x y = isPrefixOf x y || isPrefixOf y x

main = let seq = bfs expand ("","")
result = head \$ filter ((s,t) -> s==t) (tail seq)
in putStrLn (show result)

This piece of code can solve this problem in 5 seconds, but unfortunately with over 70MB memory. What worth mentioning is clean way of expressing the breadth first search(the function bfs).

### 2 Responses to Solve the pcp instance with 24 line’s of code

1. yuanzu说道：

恩，在wiki上看了一下这个pcp problem，不过你的程序肯定看不懂…要是有空的话我再去看看其他的语言写出来的是什么样子的

2. 佳森说道：