等差数列(2013.5.17の過去問)

1日1個 @nabetani さんの作った問題を解く、どう書くAdventCalendarの3日目です。

今日の問題は http://nabetani.sakura.ne.jp/hena/ord11arithseq/ にあります。

module Doukaku.Tousa (solve) where

import Data.Char (isDigit, ord)
import Data.List (tails)

solve :: String -> String
solve = show . maximum . map maxSeqLen . tails . parse

parse :: String -> [Int]
parse = map parse'
  where
    parse' c
      | isDigit c = ord c - ord '0'
      | otherwise = ord c - ord 'a' + 10

maxSeqLen :: [Int] -> Int
maxSeqLen [] = 0
maxSeqLen (_:[]) = 1
maxSeqLen (x:y:ys) = maximum [2 + maxSeqLen' (y + n) ys, maxSeqLen (x:ys)]
  where
    n = y - x
    maxSeqLen' next xs = if null left then 0 else 1 + maxSeqLen' (next + n) (tail left)
      where (_, left) = break (== next) xs

一度Haskellで解いた問題を再チャレンジしてみました。割とハマりどころがある問題のようで、今回もちょっとハマりました。maxSeqLenは与えたリストの先頭要素から始まる等差数列の長さを求める関数だったのですが、二番目以降の要素を飛ばすパターンを考慮してなかったのでテストが通らず、急遽再帰させて二番目以降の要素を飛ばす実装に書き換えました。

以前の自分の回答は https://gist.github.com/hiratara/5786734 にあるのですが、似た方法な上にどちらかと言えば過去に書いたものの方が洗練されていることに驚きます。人間って退化するものなのですね！

http://qiita.com/Nabetani/items/c206fbc645c255cb7de6 に他の方の回答もありますので、見ると参考になるでしょう。