Hatena::Groupocaml-nagoya

yoshihiro503の関数的日記

2011-01-30 (Sun)

算数オリンピックの問題をリストモナドで解く

| 19:53 | 算数オリンピックの問題をリストモナドで解く - yoshihiro503の関数的日記 を含むブックマーク はてなブックマーク - 算数オリンピックの問題をリストモナドで解く - yoshihiro503の関数的日記

はてブニュースで話題のあった算数オリンピックの問題をリストモナドで解いてみた。

5×5のマス目に6個の○を次の条件を満たすように書きます。

条件:各行・各列に少なくとも1個は○を書く。同じマスには2個以上の○を書くことはできない。

このとき、6個の○を書く方法は全部で何通りありますか。

http://b.hatena.ne.jp/articles/201101/2261

Haskellはあまり経験が無いのでよくわからない。こんな感じ?

import Control.Monad
type Point = (Int, Int)

main :: IO ()
main = print $ length sol

stone :: [Point]
stone = do
   x <- [1..5]
   y <- [1..5]
   return (x,y)

sol :: [[Point]]
sol = do
  p1 <- stone
  p2 <- stone
  guard (p1 < p2)
  p3 <- stone
  guard (p2 < p3)
  p4 <- stone
  guard (p3 < p4)
  p5 <- stone
  guard (p4 < p5)
  p6 <- stone
  guard (p5 < p6)
  let ps = [p1,p2,p3,p4,p5,p6]
  guard $ all (\i -> any (\(x,_) -> x == i) ps) [1..5]
            && all (\j -> any (\(_,y) -> y == j) ps) [1..5]
  return ps

実行結果

4200

real    0m0.345s
user    0m0.333s
sys     0m0.008s