-- ******************************************************************************************
-- * POH6+ (パイザ オンライン ハッカソン) *
-- * 単語リストの単語を用いて作ることができる最長の回文のうち辞書順(昇順)最小の回文を求める *
-- ******************************************************************************************
module Main where
wordlist <- getWordList n
printPalindrome (makeMaximumSizeAndMinimumOrderPalindrome (sortSringList wordlist) [] "" [])
-- 結果を表示する
printPalindrome
(wordlist
_head:wordlist
_tail
) = do putStr wordlist
_head
printPalindrome wordlist_tail
-- リストの先頭の要素を抽出する
headOfList :: [anytype] -> anytype
-- リスト同士を繋ぐ
concatList :: [anytype] -> [anytype] -> [anytype]
concatList [] [] = []
concatList front [] = front
concatList [] end = end
concatList [element] end = element : end
concatList (front_head:front_tail) end = front_head : concatList front_tail end
-- 標準入力から単語リストを読み込む
getWordList n
= do front
<- getLine end <- getWordList (n - 1)
-- 文字列を反転する
reverseString "" = ""
reverseString (str_head:str_tail) = concatList (reverseString str_tail) [str_head]
-- 文字列リストの並び順を反転する
reverseStringList [] = []
reverseStringList (strlist_head:strlist_tail) = concatList (reverseStringList strlist_tail) [strlist_head]
-- 文字列を辞書順(昇順)で比較する
compareString "" "" = 0
compareString left "" = 1
compareString "" right = -1
compareString (left_head:left_tail) (right_head:right_tail) = if left_head < right_head
then -1
else if left_head == right_head
then compareString left_tail right_tail
else 1
-- ソート用の内部関数。文字列リストからキーワードより辞書順で小さい文字列をリストアップする
underPartition keyword [] = []
underPartition keyword (wordlist_head:wordlist_tail) = if compareString keyword wordlist_head > 0
then wordlist_head : (underPartition keyword wordlist_tail)
else underPartition keyword wordlist_tail
-- ソート用の内部関数。文字列リストからキーワードと一致する文字列をリストアップする
sameWordPartition keyword [] = []
sameWordPartition keyword (wordlist_head:wordlist_tail) = if compareString keyword wordlist_head == 0
then wordlist_head : (sameWordPartition keyword wordlist_tail)
else sameWordPartition keyword wordlist_tail
-- ソート用の内部関数。文字列リストからキーワードより辞書順で大きい文字列をリストアップする
upperPartition keyword [] = []
upperPartition keyword (wordlist_head:wordlist_tail) = if compareString keyword wordlist_head < 0
then wordlist_head : (upperPartition keyword wordlist_tail)
else upperPartition keyword wordlist_tail
-- 文字列リストの先頭の文字列を抽出する
headOfStringList [] = ""
headOfStringList (strlist_head:strlist_tail) = strlist_head
-- 文字列リスト内の文字列を辞書順(昇順)でソートする
sortSringList [] = []
sortSringList (strlist_head:strlist_tail) = concatList (concatList (concatList (sortSringList (underPartition strlist_head strlist_tail)) [strlist_head]) (sortSringList (sameWordPartition strlist_head strlist_tail))) (sortSringList (upperPartition strlist_head strlist_tail))
-- 文字列リスト内にキーワードが存在するか判定する
findKeywordInWordList keyword [] = False
findKeywordInWordList keyword (wordlist_head:wordlist_tail) = if compareString keyword wordlist_head == 0 then True else findKeywordInWordList keyword wordlist_tail
-- 文字列リスト内にキーワードが存在する場合に文字列リストで始めに出てきたキーワードを取り除いた文字列リストを作る
deleteKeywordInWordList keyword [] = []
deleteKeywordInWordList keyword (wordlist_head:wordlist_tail) = if compareString keyword wordlist_head == 0 then wordlist_tail else wordlist_head : deleteKeywordInWordList keyword wordlist_tail
-- POH6+の問題を解くための関数。ソートされた単語リストから最長回文のうち辞書順昇順で最小のものを生成する。
-- 引数の初期値には、第一引数にはソートされた単語リスト。第二~第四引数はには空リストを指定すること。
-- 第二引数には回文の前部に並ぶ単語が逆順でリストアップされる。
-- 第三引数には回文の中央部に位置する単語が格納される。
-- 第四引数には回文の後部に並ぶ単語がリストアップされる。
-- 戻り値は最長回文で辞書順(昇順)最小になるように並べられた単語のリストである。
makeMaximumSizeAndMinimumOrderPalindrome [] front center end = concatList (concatList (reverseStringList front) [center]) end
makeMaximumSizeAndMinimumOrderPalindrome (wordlist_head:wordlist_tail) front center end = if findKeywordInWordList (reverseString wordlist_head) wordlist_tail
then makeMaximumSizeAndMinimumOrderPalindrome (deleteKeywordInWordList (reverseString wordlist_head) wordlist_tail) (wordlist_head : front) center ((reverseString wordlist_head) : end)
else if compareString wordlist_head (reverseString wordlist_head) == 0 && (compareString "" center == 0 || compareString wordlist_head center < 0)
then makeMaximumSizeAndMinimumOrderPalindrome wordlist_tail front wordlist_head end
else makeMaximumSizeAndMinimumOrderPalindrome wordlist_tail front center end
-- End Of File --