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] -> [[]]
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
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=