{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import Control.Monad             (guard, mfilter)\n",
    "import Control.Monad.Trans.State\n",
    "import Data.List                 (foldl', delete)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "select :: [a] -> [(a, [a])]\n",
    "select []     = []\n",
    "select (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- select xs]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "selectThis :: (Eq a) => a -> [a] -> [((), [a])]\n",
    "selectThis x xs \n",
    "    | x `elem` xs = [((), delete x xs)] \n",
    "    | otherwise = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "asNumber :: [Int] -> Int\n",
    "asNumber = foldl' (\\t o -> t*10 + o) 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "main :: IO ()\n",
    "main = print . flip evalStateT [0..9] $ do\n",
    "    s <- StateT select\n",
    "    e <- StateT select\n",
    "    n <- StateT select\n",
    "    d <- StateT select\n",
    "    m <- StateT select\n",
    "    o <- StateT select\n",
    "    r <- StateT select\n",
    "    y <- StateT select\n",
    "    guard $ s /= 0 && m /= 0\n",
    "    let send  = asNumber [s,e,n,d]\n",
    "        more  = asNumber [m,o,r,e]\n",
    "        money = asNumber [m,o,n,e,y]\n",
    "    guard $ send + more == money\n",
    "    return (send, more, money)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(9567,1085,10652)]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "main"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "--   a b c\n",
    "--  d e f g\n",
    "-- h i j k l\n",
    "--  m n o p\n",
    "--   q r s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "main1 :: IO ()\n",
    "main1 = print . flip evalStateT [1..19] $ do\n",
    "    a <- StateT select\n",
    "    b <- StateT select\n",
    "    c <- StateT select\n",
    "    guard $ c > a\n",
    "    let rowSum = a + b + c\n",
    "    \n",
    "    d <- StateT select\n",
    "    e <- StateT select\n",
    "    f <- StateT select\n",
    "    g <- StateT select\n",
    "    guard $ d + e + f + g == rowSum\n",
    "    \n",
    "    h <- StateT select\n",
    "    guard $ h > a\n",
    "    guard $ h < c\n",
    "    i <- StateT select\n",
    "    j <- StateT select\n",
    "    k <- StateT select\n",
    "    l <- StateT select\n",
    "    guard $ l > a\n",
    "    guard $ h + i + j + k + l == rowSum\n",
    "    guard $ a + d + h == rowSum\n",
    "    guard $ c + g + l == rowSum\n",
    "    \n",
    "    m <- StateT select\n",
    "    n <- StateT select\n",
    "    o <- StateT select\n",
    "    p <- StateT select\n",
    "    guard $ m + n + o + p == rowSum\n",
    "    guard $ b + e + i + m == rowSum\n",
    "    guard $ b + f + k + p == rowSum\n",
    "    \n",
    "    q <- StateT select\n",
    "    r <- StateT select\n",
    "    s <- StateT select\n",
    "    guard $ q > a\n",
    "    guard $ s > a\n",
    "    guard $ c + f + j + n + q == rowSum\n",
    "    guard $ a + e + j + o + s == rowSum\n",
    "    guard $ g + k + o + r == rowSum\n",
    "    guard $ d + i + n + r == rowSum\n",
    "    guard $ h + m + q == rowSum\n",
    "    guard $ l + p + s == rowSum\n",
    "    guard $ q + r + s == rowSum\n",
    "    \n",
    "    return [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "main2 :: IO ()\n",
    "main2 = print . flip evalStateT [1..19] $ do\n",
    "    a <- StateT select\n",
    "    b <- StateT select\n",
    "    c <- StateT select\n",
    "    guard $ c > a\n",
    "    let rowSum = a + b + c\n",
    "    \n",
    "    d <- StateT select\n",
    "    e <- StateT select\n",
    "    f <- StateT select\n",
    "    let g = rowSum - (d + e + f)\n",
    "    StateT (selectThis g)\n",
    "    \n",
    "    let h = rowSum - (a + d)\n",
    "    guard $ h > a\n",
    "    guard $ h < c\n",
    "    StateT (selectThis h)\n",
    "    let l = rowSum - (c + g)\n",
    "    guard $ l > a\n",
    "    StateT (selectThis l)\n",
    "    i <- StateT select\n",
    "    j <- StateT select\n",
    "    k <- StateT select\n",
    "    guard $ h + i + j + k + l == rowSum\n",
    "\n",
    "    let m = rowSum - (b + e + i)\n",
    "    StateT (selectThis m)\n",
    "    n <- StateT select\n",
    "    o <- StateT select\n",
    "    let p = rowSum - (b + f + k)\n",
    "    guard $ m + n + o + p == rowSum\n",
    "    StateT (selectThis p)\n",
    "    \n",
    "    let q = rowSum - (h + m)\n",
    "    guard $ q > a\n",
    "    guard $ c + f + j + n + q == rowSum\n",
    "    StateT (selectThis q)\n",
    "    let r = rowSum - (g + k + o)\n",
    "    guard $ d + i + n + r == rowSum\n",
    "    StateT (selectThis r)\n",
    "\n",
    "    let s = rowSum - (q + r)\n",
    "    guard $ s > a\n",
    "    guard $ a + e + j + o + s == rowSum\n",
    "    guard $ l + p + s == rowSum\n",
    "    StateT (selectThis s)\n",
    "    \n",
    "    return [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "-- main1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[3,17,18,19,7,1,11,16,2,5,6,9,12,4,8,14,10,13,15]]"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "main2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Haskell",
   "language": "haskell",
   "name": "haskell"
  },
  "language_info": {
   "codemirror_mode": "ihaskell",
   "file_extension": ".hs",
   "name": "haskell",
   "version": "8.0.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}