謎解き色が強くなってきたので、コードは載せません。6は強敵だった。つーかPythonで解きました。
Lv4
文字列で示されたURIをたどる
ex. "http://www.pythonchallenge.com/***/***?***=12345"というページの内容が
"*** *** **** *** 67890"であれば、
"http://www.pythonchallenge.com/***/***?***=67890"を開く。これを繰り返す。
Haskell HTTP packageを使う。ここのexample、test/get.hsをちょっと改変。
main = do
id <- getLine
getLinkedList id
getLinkedList id = case parseURI $ urip ++ filter (/= '\n') id of
Nothing -> err "Could not parse URI"
Just uri -> do
cont <- get uri
putStrLn cont
getLinkedList $ head $ reverse $ words cont
where
urip = "http://www.pythonchallenge.com/***/***?****="
ここ以外はtest/get.hsをそのまま。実行して末尾の数字を入れると動くけど……。getのたびにpythonchallenge.comに接続しなおしてるっぽいので遅い。Networkパッケージ本体を使えばもっと低レベルなところから作れるようだ。
The Glorious Glasgow Haskell Compilation System User's Guide: 4.8. Packages
Network Libraryをインストールしてみる。
Cabalというパッケージ管理ツールがghcに付属している。圧縮ファイルを落して解凍すると、Setup.hsというものができる。これがhaskell版makeみたいなものなのかな。ディレクトリに移動して
$ runhaskell Setup.hs configure $ runhaskell Setup.hs build # runhaskell Setup.hs install
これだけ。最後のはスーパーユーザで。
インストールしたLibraryのリストは
ghc-pkg list
で確認できる。
このとき、()に囲まれているものは不可視になっており、単にimportしただけだとコンパイル時に認識されないので、
$ ghc -package packagename filename.hs
と引数で指定してやるか、
# ghc-pkg expose packagename
として可視にする必要がある。
interact :: (String -> String) -> IO()
interact f = do x <- getContents
putStr (f x)
文字列をとって文字列を返す関数fを引数とし、fを入力に適用したものを出力する。これは便利。
Python Challenge(1)
import Char
shift :: Char -> Char
shift a
| a == 'z' = 'a'
| isLower a = chr $ ord a + 1
| otherwise = a
main :: IO()
main = do x <- getContents
putStr $ last $ take 3 $ iterate (map shift) x
↓
main :: IO() main = interact $ last . take 3 . iterate (map shift)
Python Challenge(3)
import Text.ParserCombinators.Parsec
bodyguards :: Parser String
bodyguards = try ( do { upper; upper; upper ; c <- lower
; upper; upper; upper; many1 lower; return [c] })
<|> do { skipMany1 upper ; skipMany1 lower ; return ""}
bg :: Parser String
bg = do { many lower ; r <- many1 (try bodyguards)
; many upper ; eof ; return $ concat r }
readBdGrs :: String -> String
readBdGrs input = case parse bg "" input of
Left err -> "No match: " ++ show err
Right val -> show val
main :: IO()
main = do x <- getContents
putStrLn $ readBdGrs $ filter (/= '\n') x
↓
main :: IO() main = interact $ readBdGrs . filter (/= '\n')
Lv3
アルファベットのみからなる文字列中から、大文字ちょうど三つにはさまれた小文字を抜き出す
ex. "aPQRbVWXcYZABd" -> "b"
import Text.ParserCombinators.Parsec
bodyguards :: Parser String
bodyguards = try ( do { upper; upper; upper ; c <- lower
; upper; upper; upper; many1 lower; return [c] })
<|> do { skipMany1 upper ; skipMany1 lower ; return ""}
bg :: Parser String
bg = do { many lower ; r <- many1 (try bodyguards)
; many upper ; eof ; return $ concat r }
readBdGrs :: String -> String
readBdGrs input = case parse bg "" input of
Left err -> "No match: " ++ show err
Right val -> show val
main :: IO()
main = do x <- getContents
putStrLn $ readBdGrs $ filter (/= '\n') x
Haskellに正規表現は似合わない、と思ったものの、いまいちParsecが使いこなせなくて困る。skipManyやconcatのあたりとか、もうちょっと恰好よくできないものか。
Lv2
文字列中に一度しか出現しない文字を抜き出す。
ex. "aabcccd" -> "bd"
rareCharFilter :: String -> String
rareCharFilter [] = []
rareCharFilter (x:xs)
| any (x ==) xs = rareCharFilter $ filter (/= x) xs
| otherwise = x : rareCharFilter xs
main :: IO()
main = do x <- getContents
putStrLn $ rareCharFilter x
rareCharFilter内で再帰しているため、^DでEOFを送ってやるかファイルからリダイレクトする必要がある。
入力から一文字とって、その文字が以降の文字列に出現していれば削除、出現していなければ残して次、と繰り返すだけ。
を空き時間にちょこちょこやっている。趣旨としてはPythonを使って問題にチャレンジ、というものなんだろうけど、ここは敢えてHaskellで攻めたいと思う。僕のHaskellレベルはたぶん1.5くらい。
Lv1
アルファベット小文字列を二文字循環シフトする。
ex. "x ( yz )" -> "z ( ab )"
import Char
shift :: Char -> Char
shift a
| a == 'z' = 'a'
| isLower a = chr $ ord a + 1
| otherwise = a
main :: IO()
main = do x <- getContents
putStr $ last $ take 3 $ iterate (map shift) x
一昨日のエントリはひどいものだった。僕はこれをPythonでやりたかったんだ。
foldl(op, v, [a, b, c, d]) = (((v op a) op b) op c) op d
foldr(op, v, [a, b, c, d]) = a op (b op (c op (d op v)))
そしてこう書いた。
def foldl(proc, elem, lis):
lis.insert(0, elem)
return reduce(proc, lis)
def foldr(proc, elem, lis):
lis.append(elem)
lis.reverse()
return reduce(lambda x, y : apply(proc, [y, x]), lis)
fl = foldl(lambda x, y : x / y, 2.0, [1.0, 2.0, 4.0, 8.0])
fr = foldr(lambda x, y : x / y, 2.0, [1.0, 2.0, 4.0, 8.0])
>>> fl
0.03125
>>> fr
0.5
こんなアホみたいなことをする必要なんて全くなかったんだ……。もう少し考えるべきだった、Pythonがこんな不便なはずはないって。
import operator
def foldl(proc, elem, l):
lis = l[:]
lis.insert(0, elem)
return reduce(proc, lis)
def foldr(proc, elem, l):
lis = l[::-1]
lis.insert(0, elem)
return reduce(lambda x, y : proc(y, x), lis)
fl = foldl(operator.truediv, 2, [1, 2, 4, 8])
fr = foldr(operator.truediv, 2, [1, 2, 4, 8])
>>> fl
0.03125
>>> fr
0.5
これでよかったんじゃないか……。そして忘れていた、普通の言語にはループってものがあるってことを。
def foldl_loop(proc, elem, l):
lis = l[:]
for x in lis:
elem = proc(elem, x)
return elem
def foldr_loop1(proc, elem, l):
lis = l[::-1]
for x in lis:
elem = proc(x, elem)
return elem
def foldr_loop2(proc, elem, l):
lis = l[:]
while lis:
elem = proc(lis.pop(),elem)
return elem
時間を計ってみよう。largelist = range(10000000)として、リストの整数を全て足しあわせてみる。
foldl(operator.add, 0, largelist) 3.36605238934 foldl_loop(operator.add, 0, largelist) 5.12172161546 foldr(operator.add, 0, largelist) 7.88937811929 foldr_loop1(operator.add, 0, largelist) 5.67820882263 foldr_loop2(operator.add, 0, largelist) 8.93474310282
reduceはえー。そして気づいた、こんなことしたってHaskellの勉強にはならないって。
foldl,foldr
Hugs.Base> foldl (/) 2 [1, 2, 4, 8] 0.03125 Hugs.Base> foldr (/) 2 [1, 2, 4, 8] 0.5
foldl (/) 2 [1, 2, 4, 8] は、(((2 / 1) / 2) / 4) / 8
foldr (/) 2 [1, 2, 4, 8] は、1 / (2 / (4 / (8 / 2)))ということですね。
Hugs.Base> foldl (/) 3 [1, 3, 5, 7, 2, 1] 0.0142857142857143 Hugs.Base> foldr (/) 3 [1, 3, 5, 7, 2, 1] 1.42857142857143
Schemeで書いてみる。Schemeのライブラリ、SRFIのfoldは
> (fold / 2 '(1 2 4 8)) 8
これは8 / (4 / (2 / (1 / 2)))になってしまう。自分で書くしかない。
(define (foldl proc elem list)
(define (foldl-iter list ans)
(cond ((null? list) ans)
(#t (foldl-iter (cdr list) (proc ans (car list))))))
(foldl-iter list elem))
(define (foldr proc elem list)
(define (foldr-rec list)
(cond ((null? list) elem)
(#t (proc (car list) (foldr-rec (cdr list))))))
(foldr-rec list))
> (foldl / 2.0 '(1 2 4 8))
0.03125
> (foldr / 2.0 '(1 2 4 8))
0.5
> (foldl / 3.0 '(1 3 5 7 2 1 ))
0.014285714285714287
> (foldr / 3.0 '(1 3 5 7 2 1 ))
1.4285714285714284
いい感じに頭がこんがらがってきました。
次は Pythonで。
def foldl(proc, elem, lis):
lis.insert(0, elem)
return reduce(proc, lis)
def foldr(proc, elem, lis):
lis.append(elem)
lis.reverse()
return reduce(lambda x, y : apply(proc, [y, x]), lis)
fl = foldl(lambda x, y : x / y, 2.0, [1.0, 2.0, 4.0, 8.0])
fr = foldr(lambda x, y : x / y, 2.0, [1.0, 2.0, 4.0, 8.0])
>>> fl
0.03125
>>> fr
0.5
>>> print foldl(lambda x, y : x / y, 3.0, [1.0, 3.0, 5.0, 7.0, 2.0, 1.0])
0.0142857142857
>>> print foldr(lambda x, y : x / y, 3.0, [1.0, 3.0, 5.0, 7.0, 2.0, 1.0])
1.42857142857
Pythonて絶対こんな書き方をする言語ではないと思った。
