Life Goes On

まあまあだけど楽しんでる方です

Google Code Jam Round 1B

Dashboard - Round 1B 2009 - Google Code Jam
終わりました。
A と B の Small と Large をそれぞれ通して 56 点。とりあえず先には進めるようですが、860位というイマイチな成績でした。
今回は C が難しくて上位陣でも解いている人は少なかったので、点数が足りなかったというより時間かかりすぎたのが敗因です。速い人はだいたい1時間くらいで A と B を片づけて残りの時間で C を進めてましたが、僕は B を解き終わった時点で 1 時間、その後 A を解くのに丸々1時間半かかってしまいました。
まぁ、でも実力相応かな。

  • A : またまたパーサを書く問題。二分木を作るパーサを書ければ終了。Parsec を使おうと思ったものの、使い方を全く覚えておらず、hoogle や自分の過去のコードを眺めながら必死で書く。残り10分を切ってから Small と Large をまとめて Submit。
  • B : 1〜9 の数字を決められた回数使って数を生成する。足りなくなったら 0 も使ってよい。次の数がどうなるかという規則を見つければ簡単。
  • C : 0〜9 の数字と(+)(-)の記号を正方形のマスに並べてあって、そこを辿って決められた数字を作る。後戻り可という条件があるために、計算を終了させる条件が思いつかず、手つかず。時間があっても解けなかったと思う。

以下に載せた A のコードなのですが、Parsec で <|> を使ってパーサを繋げるとき、インデントがだんだん深くなってしまいます。「または」という並列の条件なのでインデントも揃えたいのですが、何とかならないものでしょうか?
あと tree 関数の二つのパーサは共通部分がとても多いのですが、まとめて書けないものでしょうか?

急いで書きなぐったコードなので、他にもすっきり書けるポイントがあれば、ぜひ指摘をお願いします。

A のコード

import Numeric
import Text.ParserCombinators.Parsec

data Tree = L Double | T Double String Tree Tree deriving Show

number :: Parser Double
number = do
  dec <- many digit
  char '.'
  rest <- many digit
  return $ read $ dec++"."++rest

treeCore :: Parser Tree
treeCore = try (do
  n <- number
  spaces
  f <- many lower
  spaces
  t1 <- tree
  spaces
  t2 <- tree
  return $ T n f t1 t2)
  <|> (do
    n <- number
    return $ L n)

tree :: Parser Tree
tree = do
  spaces
  char '('
  spaces
  t <- treeCore
  spaces
  char ')'
  spaces
  return t

solve :: (Tree, [[String]]) -> [Double]
solve (t, as) = map (solve' 1 t) as
solve' d (L m) fs = d*m
solve' d (T n f t1 t2) fs
  | elem f fs = solve' (d*n) t1 fs
  | otherwise = solve' (d*n) t2 fs

read' :: [String] -> [(Tree, [[String]])]
read' [] = []
read' (l':s0) = (t, animals) : read' s2
  where
  l = read l'
  (tree',a':s1) = splitAt l s0
  Right t = parse tree "" $ concat tree'
  a = read a'
  (animals',s2) = splitAt a s1
  animals = map (drop 2.words) animals'

show' :: Int -> [Double] -> [String]
show' n ds = ("Case #" ++ show n ++ ":") : map (\d -> showFFloat (Just 7) d "") ds

main :: IO()
main = do
  input <- getContents
  let (c:cs) = lines input
  let n = read c
  putStr $ unlines $ concat $ zipWith show' [1..] $ map solve $ take n $ read' cs

B のコード

import Data.Char
import Data.List

solve :: [Int] -> [Int]
solve ns
  | null is = solve $ 0:ns
  | otherwise = ns0 ++ n':ns1'
  where
  ds = zipWith (-) ns $ tail ns
  is = findIndices (<0) ds
  (ns0,n:ns1) = splitAt (last is) ns
  n' = minimum $ filter (>n) ns1
  ns1' = sort $ n : delete n' ns1

show' :: Int -> [Int] -> String
show' n a = "Case #" ++ show n ++ ": " ++ map intToDigit a

main :: IO()
main = do
  input <- getContents
  let (c:cs) = lines input
  let n = read c
  putStr $ unlines $ zipWith show' [1..] $ map (solve.map digitToInt) $ take n cs