import Data.List
{-
一只青蛙正在过河。河被分成了x段并且每一段都可能存在或不存在一个石头。这只青蛙可以跳至石头上，但不能跳进水里。
 
现有一个石头位置的升序列表，判断这只青蛙能否能够跳至最后一个石头，从而过河。最初青蛙在第一块石头上并且假定第一跳只能跳一段。
 
如果这只青蛙之前一次跳了k段，那么它的下一跳必须是k-1、k或k+1段。注意该青蛙只能向前跳。
-}
 
-- jump 函数 k 表示前一次跳的步数，xs为剩下的list，
-- [ v + x | v <- [k-1,k,k+1], v > 0 ] 表示下一次可以有几种跳法 
-- ys 表示合法的跳法，如果余下的数里没有可以允许的跳法，则结束过滤掉这种。
-- concatMap 将所有合法跳法分别开跳后，合并在一个列表里
-- map (n:) 将合法的跳法放入到返回list中，继续下一跳：jump n ns
-- ns = dropWhile (/=x+n) xs 即将余下的列表掐掉刚好跳到的那一段。
jump k xs = case xs of
    [] -> [[]] 
    [x] -> [[]]
    (x:xs) -> concatMap (\n -> map (n:) (jump n (dropWhile (/=x+n) xs))) ys 
                where ys = map (subtract x) $ intersect [ v + x | v <- [k-1,k,k+1], v > 0 ] xs
 
-- frogjump 为最终的蛙跳函数，第一步必须是1，所以不为一的则返回空
-- 如果可以，则第一步1需要加入到最终的所有步骤里面                            
-- frogjump :: (Ord a, Num a) => [a] -> [[a]]
frogjump [] = []
frogjump [x] = []
frogjump (x:y:xs) 
    | y - x == 1 =  let ys = jump 1 (y:xs) in if null ys then ys else map (1:) ys 
    | otherwise = []
 
main = do
    -- print $ jump 1 [1,3,5]
    -- print $ jump 1 [1,3,4,5,6,8,12,17]
    print $ frogjump [0, 1, 3, 5, 6, 8, 12, 17]
    print $ frogjump [0, 1, 2, 3, 4, 8, 9, 11]

aW1wb3J0IERhdGEuTGlzdAp7LQrkuIDlj6rpnZLom5nmraPlnKjov4fmsrPjgILmsrPooqvliIbmiJDkuoZ45q615bm25LiU5q+P5LiA5q616YO95Y+v6IO95a2Y5Zyo5oiW5LiN5a2Y5Zyo5LiA5Liq55+z5aS044CC6L+Z5Y+q6Z2S6JuZ5Y+v5Lul6Lez6Iez55+z5aS05LiK77yM5L2G5LiN6IO96Lez6L+b5rC06YeM44CCCgrnjrDmnInkuIDkuKrnn7PlpLTkvY3nva7nmoTljYfluo/liJfooajvvIzliKTmlq3ov5nlj6rpnZLom5nog73lkKbog73lpJ/ot7Poh7PmnIDlkI7kuIDkuKrnn7PlpLTvvIzku47ogIzov4fmsrPjgILmnIDliJ3pnZLom5nlnKjnrKzkuIDlnZfnn7PlpLTkuIrlubbkuJTlgYflrprnrKzkuIDot7Plj6rog73ot7PkuIDmrrXjgIIKCuWmguaenOi/meWPqumdkuibmeS5i+WJjeS4gOasoei3s+S6hmvmrrXvvIzpgqPkuYjlroPnmoTkuIvkuIDot7Plv4XpobvmmK9rLTHjgIFr5oiWaysx5q6144CC5rOo5oSP6K+l6Z2S6JuZ5Y+q6IO95ZCR5YmN6Lez44CCCi19CgotLSBqdW1wIOWHveaVsCBrIOihqOekuuWJjeS4gOasoei3s+eahOatpeaVsO+8jHhz5Li65Ymp5LiL55qEbGlzdO+8jAotLSBbIHYgKyB4IHwgdiA8LSBbay0xLGssaysxXSwgdiA+IDAgXSDooajnpLrkuIvkuIDmrKHlj6/ku6XmnInlh6Dnp43ot7Pms5UgCi0tIHlzIOihqOekuuWQiOazleeahOi3s+azle+8jOWmguaenOS9meS4i+eahOaVsOmHjOayoeacieWPr+S7peWFgeiuuOeahOi3s+azle+8jOWImee7k+adn+i/h+a7pOaOiei/meenjeOAggotLSBjb25jYXRNYXAg5bCG5omA5pyJ5ZCI5rOV6Lez5rOV5YiG5Yir5byA6Lez5ZCO77yM5ZCI5bm25Zyo5LiA5Liq5YiX6KGo6YeMCi0tIG1hcCAobjopIOWwhuWQiOazleeahOi3s+azleaUvuWFpeWIsOi/lOWbnmxpc3TkuK3vvIznu6fnu63kuIvkuIDot7PvvJpqdW1wIG4gbnMKLS0gbnMgPSBkcm9wV2hpbGUgKC89eCtuKSB4cyDljbPlsIbkvZnkuIvnmoTliJfooajmjpDmjonliJrlpb3ot7PliLDnmoTpgqPkuIDmrrXjgIIKanVtcCBrIHhzID0gY2FzZSB4cyBvZgogICAgW10gLT4gW1tdXSAKICAgIFt4XSAtPiBbW11dCiAgICAoeDp4cykgLT4gY29uY2F0TWFwIChcbiAtPiBtYXAgKG46KSAoanVtcCBuIChkcm9wV2hpbGUgKC89eCtuKSB4cykpKSB5cyAKICAgICAgICAgICAgICAgIHdoZXJlIHlzID0gbWFwIChzdWJ0cmFjdCB4KSAkIGludGVyc2VjdCBbIHYgKyB4IHwgdiA8LSBbay0xLGssaysxXSwgdiA+IDAgXSB4cwoKLS0gZnJvZ2p1bXAg5Li65pyA57uI55qE6JuZ6Lez5Ye95pWw77yM56ys5LiA5q2l5b+F6aG75pivMe+8jOaJgOS7peS4jeS4uuS4gOeahOWImei/lOWbnuepugotLSDlpoLmnpzlj6/ku6XvvIzliJnnrKzkuIDmraUx6ZyA6KaB5Yqg5YWl5Yiw5pyA57uI55qE5omA5pyJ5q2l6aqk6YeM6Z2iICAgICAgICAgICAgICAgICAgICAgICAgICAgIAotLSBmcm9nanVtcCA6OiAoT3JkIGEsIE51bSBhKSA9PiBbYV0gLT4gW1thXV0KZnJvZ2p1bXAgW10gPSBbXQpmcm9nanVtcCBbeF0gPSBbXQpmcm9nanVtcCAoeDp5OnhzKSAKICAgIHwgeSAtIHggPT0gMSA9ICBsZXQgeXMgPSBqdW1wIDEgKHk6eHMpIGluIGlmIG51bGwgeXMgdGhlbiB5cyBlbHNlIG1hcCAoMTopIHlzIAogICAgfCBvdGhlcndpc2UgPSBbXQoKbWFpbiA9IGRvCiAgICAtLSBwcmludCAkIGp1bXAgMSBbMSwzLDVdCiAgICAtLSBwcmludCAkIGp1bXAgMSBbMSwzLDQsNSw2LDgsMTIsMTddCiAgICBwcmludCAkIGZyb2dqdW1wIFswLCAxLCAzLCA1LCA2LCA4LCAxMiwgMTddCiAgICBwcmludCAkIGZyb2dqdW1wIFswLCAxLCAyLCAzLCA0LCA4LCA5LCAxMV0=