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).

Advertisements
此条目发表在Project分类目录。将固定链接加入收藏夹。

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

  1. yuanzu说道:

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

  2. 佳森说道:

    我一开始用Haskell写的也用花了100多行,还没能求出答案来…于是就用c++写了一个,也是100多行,能求答案了,就是花了30s,估计是因为写c++程序我已经生疏了。最后看到一个日本人的bfs这个函数,突然就想到原来只要24行的Haskell就可以搞定了…而且5s求出答案..一下子觉得豁然开朗

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s