折って切る 〜 横へな 2014.1.10 問題

（元ネタは http://nabetani.sakura.ne.jp/hena/ord17foldcut/ ）
（解答例は http://qiita.com/Nabetani/items/ebd9d7deb30c57447806 ）

(Ver.1)を書いてる途中で気がついたが`Bool`値でなく`0,1`で
表現して`||`の代わりに`*`を使って、集計は全要素を足し上げる、
という方がシンプルだった。まあでもなにも工夫せずに
愚直に書くとこうなったということで（でも45分かかった…）

(Ver.2)として効率の悪さもあんまりといえばあんまりなので、
もう少しだけマシなやつも書いてみた。でもまああんまり変わらない気もする。

最終的に身も蓋もない(Ver.3)を書いてみた。
多分これが一番速い（20回ほど折り返しても3msとかで計算が終わる）。

穴の数しか考えないバージョン(ver.3)
4隅の切れ込み、4辺の切れ込み、内部の穴の数のみで紙の状態を表現する：

```hs:Fold_and_Cut_Ter.hs
module Main where

import Control.Applicative
import Data.List
import Data.List.Split (splitOn)

-- 4隅4辺の切れ込みの数と内部の穴の数
type Paper = (Int,Int,Int,Int,Int,Int,Int,Int,Int)
type Fold = Char

construct :: String -> Paper
construct str = develop (cut b) (reverse a)
  where [a,b] = splitOn "-" str 

cut :: String -> Paper
cut str = case str of
  "tl" -> (1,0,0,0,0,0,0,0,0)
  "tr" -> (0,1,0,0,0,0,0,0,0)
  "bl" -> (0,0,1,0,0,0,0,0,0)
  "br" -> (0,0,0,1,0,0,0,0,0)

-- 折りを広げると切れ込みと穴の数がどう変化するか
ufold :: Paper -> Fold -> Paper
ufold (tl,tr,bl,br,t,b,l,r,n) c = case c of
  'T' -> (bl,br,bl,br,b,b,2*l+tl,2*r+tr,2*n+t)
  'B' -> (tl,tr,tl,tr,t,t,2*l+bl,2*r+br,2*n+b)
  'L' -> (tr,tr,br,br,2*t+tl,2*b+bl,r,r,2*n+l)
  'R' -> (tl,tl,bl,bl,2*t+tr,2*b+br,l,l,2*n+r)

develop :: Paper -> [Fold] -> Paper
develop p fs = foldl ufold p fs

countHoles :: Paper -> Int
countHoles (tl,tr,bl,br,t,b,l,r,n) = n

solve :: String -> Int
solve = countHoles.construct

main = solve<$>getLine >>= print >> main
```


紙をそのまま表現するヴァージョン(Ver.1)：

```hs:Fold_and_Cut.hs
module Main where
import Control.Applicative
import Data.List
import Data.List.Split (splitOn)

type Cell = Bool
type Paper = [[Cell]]
type Fold = Char

construct str = develop (cut b) (reverse a)
  where [a,b] = splitOn "-" str 

cut str = case str of
  "tl" ->[[False,True],[True,True]] 
  "tr" ->[[True,False],[True,True]] 
  "bl" ->[[True,True],[False,True]] 
  "br" ->[[True,True],[True,False]] 

ufold :: Paper -> Fold -> Paper
ufold p f = case f of
  'T' -> reverse p ++ p
  'B' -> p ++ reverse p 
  'L' -> map (\x -> reverse x ++ x) p
  'R' -> map (\x -> x ++ reverse x) p

develop :: Paper -> [Fold] -> Paper
develop p fs = foldl ufold p fs

reduce :: Paper -> [[Cell]]
reduce [x] = [map (const True) x]
reduce (x:y:xs) = (zipWith (||) x y) : reduce (y:xs)

countHoles = length.filter (==False).concat.reduce.transpose.reduce

solve = countHoles.construct

main = solve<$>getLine >>= print >> main

```

穴の座標だけで紙の状態を表現するヴァージョン(Ver.2)：

```hs:Fold_and_Cut_Bis.hs
module Main where
import Control.Applicative
import Data.List
import Data.List.Split (splitOn)

type Position = (Int,Int)
type Paper = ((Int,Int),[Position])
type Fold = Char

construct :: String -> Paper
construct str = develop (cut b) (reverse a)
  where [a,b] = splitOn "-" str 

cut :: String -> Paper
cut str = case str of
  "tl" -> ((2,2),[(0,0)])
  "tr" -> ((2,2),[(1,0)])
  "bl" -> ((2,2),[(0,1)])
  "br" -> ((2,2),[(1,1)])

ufold :: Paper -> Fold -> Paper
ufold ((w,h),ps) c = case c of
  'T' -> ((w,2*h), dup ps)
           where dup = concat.map (\(x,y) -> [(x,h+y),(x,h-y-1)])
  'B' -> ((w,2*h), dup ps)
           where dup = concat.map (\(x,y) -> [(x,y),(x,2*h-y-1)])
  'L' -> ((2*w, h), dup ps)
           where dup = concat.map (\(x,y) -> [(w+x,y),(w-x-1,y)])
  'R' -> ((2*w, h), dup ps)
           where dup = concat.map (\(x,y) -> [(x,y),(2*w-x-1,y)])

develop :: Paper -> [Fold] -> Paper
develop p fs = foldl ufold p fs

countHoles :: Paper -> Int
countHoles p = length $ intersect poss $ map (\(x,y) -> (x+1,y+1)) poss
  where poss = snd p

solve = countHoles.construct

main = solve<$>getLine >>= print >> main
```