{"id":282,"date":"2016-05-25T23:27:23","date_gmt":"2016-05-25T14:27:23","guid":{"rendered":"http:\/\/mitsuji.org\/?p=282"},"modified":"2016-05-25T23:32:39","modified_gmt":"2016-05-25T14:32:39","slug":"haskell-%e3%81%a7-%e8%a6%86%e9%9d%a2%e7%ae%97","status":"publish","type":"post","link":"https:\/\/mitsuji.org\/?p=282","title":{"rendered":"Haskell \u3067 \u8986\u9762\u7b97"},"content":{"rendered":"<p>Haskell \u3067 <a href=\"https:\/\/en.wikipedia.org\/wiki\/Verbal_arithmetic\" target=\"_blank\">\u8986\u9762\u7b97<\/a> \u3092\u3084\u3063\u3066\u307f\u305f\u3002<\/p>\n<p>DEBT + STAR = DEATH \u304c\u4e0e\u3048\u3089\u308c\u305f\u3068\u304d\u3001\u7b49\u5f0f\u304c\u6210\u7acb\u3059\u308b\u306b\u306f<br \/>\nD = 1, E = 0, B = 8, T = 5, S = 9, A = 6, R = 7, H = 2<br \/>\n\u3068\u306a\u3089\u306a\u3051\u308c\u3070\u306a\u3089\u306a\u3044\u3001\u3068\u3044\u3046\u554f\u984c\u3092\u89e3\u304f\u3082\u306e\u3067\u3042\u308b\u3002<br \/>\n\u5148\u65e5\u3068\u3042\u308b\u8131\u51fa\u30b2\u30fc\u30e0\u3067\u51fa\u984c\u3055\u308c\u305f\u304c\u624b\u8a08\u7b97\u3067\u306f\u307e\u3063\u305f\u304f\u89e3\u3051\u306a\u304b\u3063\u305f\u3002<\/p>\n<p>\u30bd\u30fc\u30b9\u30b3\u30fc\u30c9\u306f\u3053\u3061\u3089\u3002<br \/>\n<a href=\"https:\/\/github.com\/mitsuji\/verbal-arithmetic\" target=\"_blank\">https:\/\/github.com\/mitsuji\/verbal-arithmetic<\/a><\/p>\n<h2>1. \u7279\u6b8a\u89e3<\/h2>\n<p>\u307e\u305a\u306f\u3001\u7279\u6b8a\u30b1\u30fc\u30b9\u3068\u3057\u3066 &quot;DEBT + STAR = DEATH&quot; \u3060\u3051\u3092\u89e3\u304f\u3053\u3068\u3092\u8003\u3048\u308b\u3002<br \/>\n\u30ea\u30b9\u30c8\u306e\u8981\u7d20\u3092\u6307\u5b9a\u3055\u308c\u305f\u6570\u3060\u3051\u4f7f\u7528\u3057\u305f\u5168\u3066\u306e\u9806\u5217\u306b\u8a55\u4fa1\u3055\u308c\u308b\u95a2\u6570<br \/>\npermutation \u3092 \u4f5c\u308b\u3068\u3001\u4e0b\u8a18\u306e\u3088\u3046\u306b\u7dcf\u5f53\u308a\u3067\u89e3\u304f\u3053\u3068\u304c\u3067\u304d\u308b\u3002<\/p>\n<p>\u5358\u8a9e\u306e\u5148\u982d\u306e\u6570\u5b57\u306f\u30bc\u30ed\u306b\u306a\u3089\u306a\u3044\u306e\u3067\u3001D != 0 \u3068 S != 0 \u3092\u6761\u4ef6\u306b\u8ffd\u52a0\u3057\u3066\u3044\u308b\u3002<\/p>\n<pre class=\"lang:shell\">\n\nmatchDeath :: [Int] -> Bool\nmatchDeath (a:b:d:e:h:s:t:r:[]) =\n  d\/=0 && s\/=0 && debt + star == death\n  where\n    debt  =             d * 1000 + e * 100 + b * 10 + t\n    star  =             s * 1000 + t * 100 + a * 10 + r\n    death = d * 10000 + e * 1000 + a * 100 + t * 10 + h\n\nfilterDeath =\n  map (zip \"abdehstr\") $ filter matchDeath  $ permutation 8 [0,1,2,3,4,5,6,7,8,9]\n\n<\/pre>\n<p>\u307e\u305f\u3001\u7e70\u308a\u4e0a\u304c\u308a\u3092\u8003\u3048\u308b\u3068\u7b49\u5f0f\u3092\u898b\u305f\u3060\u3051\u3067 D = 1 \u304c\u660e\u3089\u304b\u306a\u306e\u3067\u3001<br \/>\n\u3053\u308c\u3092\u6761\u4ef6\u306b\u52a0\u3048\u308b\u3068\u3001\u8a66\u884c\u56de\u6570\u304c\u6fc0\u6e1b\u3057\u3066\u5b9f\u884c\u6642\u9593\u3092\u77ed\u7e2e\u3067\u304d\u308b\u3002<\/p>\n<pre class=\"lang:shell\">\n\nmatchDeath' :: [Int] -> Bool\nmatchDeath' (a:b:e:h:s:t:r:[]) =\n  debt + star == death\n  where\n    debt  =             d * 1000 + e * 100 + b * 10 + t\n    star  =             s * 1000 + t * 100 + a * 10 + r\n    death = d * 10000 + e * 1000 + a * 100 + t * 10 + h\n    d = 1\n\nfilterDeath' =\n  map (zip \"abehstr\")  $ filter matchDeath' $ permutation 7 [0,2,3,4,5,6,7,8,9]\n\n<\/pre>\n<h2>2. \u4e00\u822c\u5316<\/h2>\n<p>\u3053\u3053\u304b\u3089\u304c\u672c\u756a\u3060\u3002<\/p>\n<p>\u8131\u51fa\u30b2\u30fc\u30e0\u306b\u52dd\u3064\u305f\u3081\u306b\u306f\u3001\u308f\u3056\u308f\u3056\u95a2\u6570\u3092\u66f8\u304b\u306a\u304f\u3066\u3082\u3001<br \/>\n\u4f8b\u3048\u3070\u4e0b\u8a18\u306e\u3088\u3046\u306b\u8a18\u8ff0\u3057\u305f\u3089\u89e3\u7b54\u3092\u8868\u793a\u3057\u3066\u304f\u308c\u308b\u30e9\u30a4\u30d6\u30e9\u30ea\u304c\u5fc5\u8981\u3060\u3002<\/p>\n<pre class=\"lang:shell\">\n\ntest1 = print $ findConditions $ \"debt\" + \"star\" == \"death\"\n\ntest2 = print $ findConditions $ \"debt + star = death\"\n\n<\/pre>\n<p>\u307e\u305f\uff64\u3053\u306e\u3088\u3046\u306a\u95a2\u6570\u3092\u3042\u3089\u304b\u3058\u3081\u30b3\u30f3\u30d1\u30a4\u30eb\u3057\u3066\u304a\u3051\u3070\uff64<\/p>\n<pre class=\"lang:shell\">\n\nmain = do\n  equ:_ <- getArgs\n  print $ findConditions $ fromString equ\n\n<\/pre>\n<p>\u3053\u306e\u3088\u3046\u306b\uff64\u30b3\u30de\u30f3\u30c9\u306b\u30d1\u30e9\u30e1\u30fc\u30bf\u3092\u6e21\u3059\u3060\u3051\u3067\u89e3\u7b54\u3092\u5f97\u308b\u3053\u3068\u304c\u3067\u304d\u308b\u3060\u308d\u3046\uff61<\/p>\n<pre class=\"lang:shell\">\n\n$ verbal-arithmetic-general-exe \"debt + star = death\"\n\n<\/pre>\n<h2>3. \u5f0f\u306e\u30c7\u30fc\u30bf<\/h2>\n<p>\u307e\u305a\u306f\u3001\u5165\u529b\u3068\u306a\u308b\u6570\u5f0f(\u6587\u5b57\u5f0f?)\u3092\u8868\u73fe\u3059\u308b\u305f\u3081\u306e\u30c7\u30fc\u30bf\u578b\u3092\u8003\u3048\u3066\u307f\u308b\u3002<br \/>\n\u4eca\u56de\u306f\u5f0f(VExp)\u3068\u7b49\u5f0f(VEqu)\u3092\u5225\u306e\u578b\u3068\u3057\u3066\u5b9a\u7fa9\u3057\u3066\u307f\u305f\uff61<\/p>\n<pre class=\"lang:shell\">\n\ndata VExp = Val [Char]\n          | Add VExp VExp\n          deriving(Show)\n\ndata VEqu = Equals VExp VExp\n          deriving(Show)\n\n<\/pre>\n<p>\u3053\u306e\u30c7\u30fc\u30bf\u578b\u3092\u4f7f\u7528\u3059\u308b\u3068\uff64<br \/>\n\u5f0f DEBT + STAR = DEATH \u306f\u4e0b\u8a18\u306e\u3088\u3046\u306a\u30c7\u30fc\u30bf\u306b\u306a\u308b\u3002<br \/>\n\u30dd\u30fc\u30e9\u30f3\u30c9\u8a18\u6cd5\u3068\u304b\u3044\u3046\u3084\u3064\u3060\uff61<\/p>\n<pre class=\"lang:shell\">\n\nequ1 = Equals (Add (Val \"debt\") (Val \"star\")) (Val \"death\")\n\n<\/pre>\n<p>\u95a2\u6570\u3092\u6f14\u7b97\u5b50\u3068\u3057\u3066\u4f7f\u3048\u3070\u3001\u4e0b\u8a18\u306e\u3088\u3046\u306b\u66f8\u304f\u3053\u3068\u3082\u3067\u304d\u308b\u3002<\/p>\n<pre class=\"lang:shell\">\n\nequ2 = Val \"debt\" `Add` Val \"star\" `Equals` Val \"death\"\n\n<\/pre>\n<p>\u3053\u3053\u3067\u3001\u4e0b\u8a18\u306e\u95a2\u6570\u3092\u5b9a\u7fa9\u3057\u3066\u307f\u308b\u3068\u3001<\/p>\n<pre class=\"lang:shell\">\n(+)  = Add\n(==) = Equals\n<\/pre>\n<p>\u4e0b\u8a18\u306e\u3088\u3046\u306a\u8a18\u8ff0\u304c\u53ef\u80fd\u306b\u306a\u308b\u3002\u3060\u3044\u3076\u898b\u3084\u3059\u304f\u306a\u3063\u3066\u304d\u305f\u3002<\/p>\n<pre class=\"lang:shell\">\n\nequ3 = Val \"debt\" + Val \"star\" == Val \"death\"\n\n<\/pre>\n<p>\u305d\u3057\u3066\u3001VExp \u3092 IsString \u578b\u30af\u30e9\u30b9\u306e\u30a4\u30f3\u30b9\u30bf\u30f3\u30b9\u306b\u3057\u3066\u3001<\/p>\n<pre class=\"lang:shell\">\n\ninstance IsString VExp where\n  fromString xs = Val xs\n  \n<\/pre>\n<p>\u30bd\u30fc\u30b9\u30b3\u30fc\u30c9\u306e\u5148\u982d\u306b {-# LANGUAGE OverloadedStrings #-} \u3092\u66f8\u304f\u3068<br \/>\n\u4e0b\u8a18\u306e\u3088\u3046\u306a\u8a18\u8ff0\u304c\u53ef\u80fd\u306b\u306a\u308b\u3002<br \/>\n\u3053\u308c\u306f\u3001\u30b3\u30fc\u30c9\u4e0a\u306b\u6587\u5b57\u5217\u30ea\u30c6\u30e9\u30eb\u304c\u3042\u308a\u3001VExp\u578b\u306b\u63a8\u8ad6\u3055\u308c\u308b\u3068\u304d\u306f<br \/>\nVExp \u306e fromString \u3092\u4f7f\u3063\u3066\u3001VExp\u578b\u306e\u30c7\u30fc\u30bf\u3092\u4f5c\u308a\u306a\u3055\u3044\u3068\u3044\u3046\u610f\u5473\u3067\u3042\u308b\uff61<br \/>\n\u30b3\u30fc\u30c9\u4e0a\u3067\u5f0f\u3092\u6271\u3046\u306b\u306f\u3001\u307e\u305a\u306f\u3053\u308c\u3067\u5145\u5206\u3060\u308d\u3046\u3002<\/p>\n<pre class=\"lang:shell\">\n\nequ4 = \"debt\" + \"star\" == \"death\"\n\n<\/pre>\n<h2>4. \u4e00\u822c\u89e3<\/h2>\n<p>\u7279\u6b8a\u89e3\u306e\u95a2\u6570\u3092\u53c2\u8003\u306b\u3057\u3066\u4f5c\u6210\u3057\u305f\u95a2\u6570\u304c\u4e0b\u8a18\u3067\u3042\u308b\uff61<br \/>\nchars \u95a2\u6570\u3067\u5f0f\u5185\u306e\u30e6\u30cb\u30fc\u30af\u306a\u6587\u5b57\u3092\u62bd\u51fa\u3057\u3001\u7dcf\u5f53\u308a\u306e\u5834\u5408\u306e\u6570\u3092\u6c7a\u3081\u3066\u3044\u308b\u3002<br \/>\n\u307e\u305f\u3001firstChars \u95a2\u6570\u3067\u5f0f\u5185\u306e\u5358\u8a9e\u306e\u5148\u982d\u306e\u6587\u5b57\u3092\u62bd\u51fa\u3057\u3001!= 0 \u6761\u4ef6\u3092\u8ffd\u52a0\u3057\u3066\u3044\u308b\u3002<\/p>\n<pre class=\"lang:shell\">\n\nfindConditions :: VEqu -> [[(Char,Int)]]\nfindConditions equ =\n  let\n    cs = chars equ\n  in\n   filter (match equ) $ map (zip cs) $ permutation (length cs) [0..9]\n\n\nmatch :: VEqu -> [(Char,Int)] -> Bool\nmatch equ xs = (and $ map f $ firstChars equ) && evaluate equ xs\n  where\n    f x =\n      let Just y = lookup x xs\n      in  y \/= 0\n\n<\/pre>\n<p>match \u95a2\u6570\u306b\u6e21\u3055\u308c\u305f\u6570\u5b57\u3092\u5143\u306b\u5b9f\u969b\u306b\u8a08\u7b97\u3092\u884c\u3046\u95a2\u6570\u306f\u4e0b\u8a18\u306e\u3088\u3046\u306b\u306a\u3063\u305f\u3002<br \/>\nlistToInt \u95a2\u6570\u306f\u3001\u6570\u5b57\u306e\u30ea\u30b9\u30c8\u309210\u9032\u6570\u3067\u6570\u5024\u306b\u5909\u63db\u3059\u308b\u95a2\u6570\u3067\u3042\u308b\u3002<\/p>\n<pre class=\"lang:shell\">\n\nevaluate :: VEqu -> [(Char,Int)] -> Bool\nevaluate (Equals exp1 exp2) xs = expEvaluate exp1 xs P.== expEvaluate exp2 xs \n  where\n    expEvaluate :: VExp -> [(Char,Int)] -> Int\n    expEvaluate (Add exp1 exp2) xs = expEvaluate exp1 xs P.+ expEvaluate exp2 xs\n    expEvaluate (Val cs) xs = listToInt $ map f cs\n      where\n        f x =\n          let Just y = lookup x xs\n          in  y\n\n<\/pre>\n<h2>5. \u30d1\u30fc\u30b5\u30fc<\/h2>\n<p>\u3053\u3053\u307e\u3067\u3067\u8a08\u7b97\u81ea\u4f53\u306f\u3067\u304d\u308b\u3088\u3046\u306b\u306a\u3063\u305f\u304c\u3001\u30b3\u30de\u30f3\u30c9\u30e9\u30a4\u30f3\u306b\u5f0f\u3092\u6e21\u305b\u308b\u3088\u3046\u306b\u3059\u308b\u306b\u306f\u3001<br \/>\n\u5f0f\u5168\u4f53\u3092\u6587\u5b57\u5217\u3068\u3057\u3066\u53d7\u3051\u53d6\u3063\u3066\u3001\u5f0f\u306e\u30c7\u30fc\u30bf\u306b\u5909\u63db\u3059\u308b\u30d1\u30fc\u30b5\u30fc\u3092\u66f8\u304f\u5fc5\u8981\u304c\u3042\u308b\u3002<\/p>\n<p>\u3053\u3093\u306a\u611f\u3058\u306e\u30d1\u30fc\u30b5\u30fc\u306b\u306a\u3063\u305f\u3002\u30b9\u30da\u30fc\u30b9\u306e\u6271\u3044\u30671\u65e5\u304f\u3089\u3044\u30cf\u30de\u3063\u305f\uff61<\/p>\n<pre class=\"lang:shell\">\n\npVal :: PS.Parser VExp\npVal = do\n  xs <- PS.many1 $ PS.letter <|> PS.alphaNum\n  return $ Val xs\n\npAdd :: PS.Parser (VExp -> VExp -> VExp)\npAdd = PS.char '+' >> return Add\n\npExp :: PS.Parser VExp\npExp = pValS `PS.chainl1` pOpS\n  where\n    pValS = do\n      val <- pVal\n      PS.spaces\n      return val\n    pOpS = do\n      op <- pAdd <|> mzero\n      PS.spaces\n      return op\n\npEquals :: PS.Parser VEqu\npEquals = do\n  exp1 <- pExp\n  PS.char '='\n  PS.spaces\n  exp2 <- pExp\n  return $ Equals exp1 exp2\n\n<\/pre>\n<p>\u6700\u5f8c\u306b VEqu \u3092 IsString \u306e\u30a4\u30f3\u30b9\u30bf\u30f3\u30b9\u306b\u3057\u3066<br \/>\n\u5f0f\u5168\u4f53\u3092\u6587\u5b57\u5217\u3068\u3057\u3066\u8a18\u8ff0\u3057\u3001\u76f4\u63a5\u5f0f\u306e\u30c7\u30fc\u30bf\u3068\u3057\u3066\u6271\u3048\u308b\u3088\u3046\u306b\u3057\u305f\u3002<\/p>\n<pre class=\"lang:shell\">\n\ninstance IsString VEqu where\n  fromString xs =\n    case PS.parse pEquals \"verbal\" xs of\n      Right equ -> equ\n      Left  err -> error (show err)\n\n<\/pre>\n<h2>6. \u307e\u3068\u3081\u30fb\u611f\u60f3<\/h2>\n<ul>\n<li>\u5b9f\u884c\u5f62\u5f0f\u30d0\u30a4\u30ca\u30ea\u306b\u30b3\u30f3\u30d1\u30a4\u30eb\u3059\u308c\u3070Haskell\u3067\u3082\u305d\u3053\u305d\u3053\u901f\u304b\u3063\u305f\u3002<\/li>\n<li>IsString \u578b\u30af\u30e9\u30b9\u3092\u4f7f\u3046\u3068\u3001\u3044\u308d\u3093\u306a\u578b\u306e\u30c7\u30fc\u30bf\u3092\u6587\u5b57\u5217\u30ea\u30c6\u30e9\u30eb\u304b\u3089\u4f5c\u308c\u308b\u3002<\/li>\n<li>\u30d1\u30fc\u30b5\u30fc\u3092\u66f8\u304f\u3068\u304d\u306f\u30b9\u30da\u30fc\u30b9\u306e\u51e6\u7406\u304c\u91cd\u8907\u3057\u306a\u3044\u3088\u3046\u306b\u6ce8\u610f\u3057\u306a\u3044\u3068\u30cf\u30de\u308b\u3002<\/li>\n<li>\u5f0f\u306e\u8868\u73fe\u306f\u5b8c\u74a7\u306a\u306e\u3067\u3001\u8a08\u7b97\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u6539\u5584\u3057\u3066\u307f\u305f\u3044\u3002\u975e\u7dcf\u5f53\u308a\u3068\u304b\u3002<\/li>\n<li>\u5f15\u304d\u7d9a\u304d\u3001\u639b\u3051\u7b97\u3068\u5f15\u304d\u7b97\u304f\u3089\u3044\u307e\u3067\u306f\u5bfe\u5fdc\u3057\u3066\u307f\u305f\u3044\u3002<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Haskell \u3067 \u8986\u9762\u7b97 \u3092\u3084\u3063\u3066\u307f\u305f\u3002 DEBT + STAR = DEATH \u304c\u4e0e\u3048\u3089\u308c\u305f\u3068\u304d\u3001\u7b49\u5f0f\u304c\u6210\u7acb\u3059\u308b\u306b\u306f D = 1, E = 0, B = 8, T = 5, S = 9, A = 6, R = 7,  &hellip; <a href=\"https:\/\/mitsuji.org\/?p=282\" class=\"more-link\">\u7d9a\u304d\u3092\u8aad\u3080 <span class=\"screen-reader-text\">Haskell \u3067 \u8986\u9762\u7b97<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/mitsuji.org\/index.php?rest_route=\/wp\/v2\/posts\/282"}],"collection":[{"href":"https:\/\/mitsuji.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mitsuji.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mitsuji.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mitsuji.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=282"}],"version-history":[{"count":12,"href":"https:\/\/mitsuji.org\/index.php?rest_route=\/wp\/v2\/posts\/282\/revisions"}],"predecessor-version":[{"id":294,"href":"https:\/\/mitsuji.org\/index.php?rest_route=\/wp\/v2\/posts\/282\/revisions\/294"}],"wp:attachment":[{"href":"https:\/\/mitsuji.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=282"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mitsuji.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=282"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mitsuji.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=282"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}