Haskellでpaiza - arletan’s blog

すごいH本でいうと11章まできたが、先に進むより現時点の知識でHaskellコードたくさん書いた方がいいと思ったのでpaizaでもやってみる。ここでは繰り返し現れる入力データの処理についてまとめる（閏年の練習問題でいきなり躓いたのだ…）。

基本

do構文でゴリっていくのはHaskell使ってる意義が薄れるため、入力文字列→出力文字列の変換を行う関数を定義する形で解いていきたい。まず、入力をそのまま結果として出力する場合は：

main = interact id

同じechoの動作だけど、行単位の[String]に分解してから改行でjoinしてStringに戻して出力する場合は：

import Data.List
main = interact (unlines . lines)

頻出パターンのパース

paizaの入力データは、データ数→各データが改行区切りで渡されるパターンが多い。例えば最初に4組の2次元座標、次に3個の単語が入力として渡されるならこんな感じ：

4
10 20
45 60
2 3
76 8
3
red
yellow
blue

この入力データを、手始めとして次の形に整形したい：

[["10 20", "45 60", "2 3", "76 8"], ["red", "yellow", "blue"]]

各行についてさらにスペースで分割したり、整数に変換したりは問題ごとの要件となる。

カウンタを更新しながら順次データを取り込む方法にちょっと悩んだが、タプルをアキュムレーターとして畳み込むことでうまくいった。また、リストは先頭に追加する方が簡単なので、逆順でリスト化してからreverseする方法をとった。

import Data.List
 
type DataSet = [String] -- 思考整理のために型シノニムを積極的に利用
 
parsePaizaLine :: (Int, [DataSet]) -> String -> (Int, [DataSet])
parsePaizaLine (0, ys)   x = (read x, []:ys) -- データ数の行なので、カウンタを設定して新たなリストを用意する
parsePaizaLine (n, y:ys) x = (n - 1, (x:y):ys) -- データ行はカウンタを減らしつつリストの末尾に取り込んでいく
 
parsePaizaInput :: String -> [DataSet]
parsePaizaInput = reverse . map reverse . snd . foldl parsePaizaLine (0, []) . lines
 
main = interact (unlines . solve . parsePaizaInput)

雛形はこんな感じで、問題解決の本体としてsolve関数を定義する。

例題

与えられた数字が7ならばLUCKY SEVEN!!、7以外ならNOT LUCKY...を出力せよ。

入力例（最初の行は与えられるデータ数を表す）

入力例に対する期待出力

NOT LUCKY...
LUCKY SEVEN!!
NOT LUCKY...
NOT LUCKY...
LUCKY SEVEN!!

回答例

import Data.List

type DataSet = [String]

parsePaizaLine :: (Int, [DataSet]) -> String -> (Int, [DataSet])
parsePaizaLine (0, ys)   x = (read x, []:ys)
parsePaizaLine (n, y:ys) x = (n - 1, (x:y):ys)

parsePaizaInput :: String -> [DataSet]
parsePaizaInput = reverse . map reverse . snd . foldl parsePaizaLine (0, []) . lines

sayLucky :: Int -> String
sayLucky 7 = "LUCKY SEVEN!!"
sayLucky _ = "NOT LUCKY..."

solve :: [DataSet] -> [String]
solve = map (sayLucky . read) . head

main = interact (unlines . solve . parsePaizaInput)

こんなノリでいいのかなHaskell？

おまけ

generatePaizaInput :: Int -> String
generatePaizaInput n = unlines . map show $ n : take n [1..]

main = print . length . head . parsePaizaInput $ generatePaizaInput 1000000

パース関数が大量データに耐えうるか実験してみた。2000000ではタイムアウト。この場合検証用データの生成にも時間かかってるので、パース関数のパフォーマンスについてはひとまず大丈夫そうか。

目標は「嘘つき探し」の攻略ということで。