ネタ記録庫/SEND+MORE=MONEY のバックアップ差分(No.7)

• バックアップ一覧
• 現在との差分 を表示
• ソース を表示
• バックアップ を表示
• ネタ記録庫/SEND+MORE=MONEY へ行く。
  • 1 (2007-08-20 (月) 22:47:38)
  • 2 (2007-08-20 (月) 22:48:24)
  • 3 (2007-09-18 (火) 18:57:42)
  • 4 (2007-09-20 (木) 05:15:49)
  • 5 (2007-09-20 (木) 10:10:25)
  • 6 (2007-09-20 (木) 13:25:01)
  • 7 (2007-09-20 (木) 18:19:42)
  • 8 (2007-09-20 (木) 20:12:28)
  • 9 (2007-11-27 (火) 14:40:06)
  • 10 (2007-12-23 (日) 19:56:24)
  • 11 (2007-12-28 (金) 03:45:14)

• 追加された行はこの色です。
• 削除された行はこの色です。

[[ネタ記録庫/数独]]

#contents

   S E N D
 + M O R E
 ----------
 M O N E Y
 (S,M != 0)
- 10/18の OCaml講義第3回 by ガリグ先生で、授業の課題として出ました。
- 授業では、search関数はガリグ先生のお手本があって、生徒はcheck関数を書くだけでしたが。
- 計算量が苦しいなら、M=1はOKにしましょう。 - げんま
* 授業の課題 [#w55b6646]
 let toint (li : int list) =
   List.fold_left (fun a b -> (a * 10 + b)) 0 li;;
 
 let check (d : (char * int) list) =
   let f l = (toint (List.map (fun a -> List.assoc a d) l)) in
   ((List.assoc 'S' d != 0) &&
    (List.assoc 'M' d != 0) &&
    ((f ['S'; 'E'; 'N'; 'D']) + (f ['M'; 'O'; 'R'; 'E']) = (f ['M'; 'O'; 'N'; 'E'; 'Y'])));;
 
 let rec search dict letters numbers =
   match letters with
     [] -> if check dict then [dict] else []
   | a :: letters ->
       let rec choose tried numbers =
	 match numbers with
	   [] -> []
	 | n :: numbers ->
	     let sols = search ((a, n) :: dict) letters (tried @ numbers) in
	     sols @ choose (n::tried) numbers
       in
       choose [] numbers ;;
 
 let rec interval m n =
   if m > n then [] else m :: interval (m+1) n;;
 
 let solve () =
   search [] ['S';'E';'N';'D';'M';'O';'R';'Y'] (interval 0 9);;
 
 solve();;
* Gauche [#if874cf2]
ライブラリに、順列組み合わせのpermutationなどがあったので、かなり楽ができました。見つかったらreturnラベルで大域脱出。2.6Ghzで13秒。 - げんま
 (use srfi-1)
 (use util.combinations)
 (use util.match)
 
 (define return #f)
 
 (define (eval-poly li x)
   (fold (lambda (a b) (+  a (* b x))) 0 li))
 
 (define (check li)
   (match li
     ((S E N D M O R Y)
      (if
       (and
        (not (= S 0))
        (not (= M 0))
        (= (+ (eval-poly (list S E N D) 10)
 	       (eval-poly (list M O R E) 10))
 	    (eval-poly (list M O N E Y) 10)))
       (return (list S E N D '+ M O R E '= M O N E Y))))))
 
 (define (solve)
   (combinations-for-each
    (lambda (a) (permutations-for-each check a))
    (iota 10) 8))
 
 (print
  (call/cc
   (lambda (cc)
    (set! return cc)
    (solve))))
*Haskellで解いてみる [#n5f2521d]
(''追記''：[[nobsunさんのコード:http://haskell.g.hatena.ne.jp/nobsun/20061019/alphametic]]のほうがスマート。)
([[らくがきえんじん:http://d.hatena.ne.jp/syd_syd/20061018]]にも書いた。)

何も考えてない。15分くらいででけた。こういう問題にはリストモナドがめっぽう強い。（けいご）
Showのインスタンスが必要なのはご愛嬌。
 import Control.Monad.State
 
 ten = [0..9]
 
 -- StateT [Int] [] Intが何であるかを考えるより、単に [Int]->[(Int,[Int])] だと思えばよい 
 -- (「リストlを貰って、その中のどれかの要素eと、lからeを取った残りl'の対(e,l')を返す」という非決定的な関数)
 getNum :: StateT [Int] [] Int
 getNum = StateT $ ?ns -> do{n <- ns; return (n, filter (n/=) ns)}
 
 sendmory = do
   s <- getNum
   if s==0 then lift [] else return ()
   m <- getNum
   if m==0 then lift [] else return ()
   e <- getNum
   n <- getNum
   d <- getNum
   o <- getNum
   r <- getNum
   y <- getNum
   if s*1000+e*100+n*10+d+m*1000+o*100+r*10+e==m*10000+o*1000+n*100+e*10+y then return (s,e,n,d,m,o,r,y) else lift []
 
 instance (Show s, Show e, Show n, Show d, Show m, Show o, Show r, Show y)=>
   Show (s,e,n,d,m,o,r,y) where
   show (s,e,n,d,m,o,r,y) = "("++show s++","++show e++","++show n++","++
                                 show d++","++show m++","++show o++","++
                                 show r++","++show y++")"
   
 main = print (evalStateT sendmory ten)

 sydney$ ghc -package mtl Desktop/hoge.hs -o a.out
 sydney$ time ./a.out 
 [(?,?,?,?,?,?,?,?)]
 
 real    0m4.544s
 user    0m4.341s
 sys     0m0.076s

体感5秒位 (PPC, 2.3GHz dual) ただし今インタプリタ(ghci)で試したら25秒くらいかかった。

*そっちがMonadなら、こっちはamb<<改訂版>> [#rad040bb]
- 48秒@2.6GHz- げんま
 (use srfi-1)
 
 ;; stack of cc.
 (define fail '())
 
 ;; nondeterminsm operator
 (define (amb li)
   (if (null? li)
       ((pop! fail))
       (call/cc
        (lambda (cc)
 	 (push! fail (lambda ()
 		       (cc (amb (cdr li)))))
 	 (car li)))))
 
 (define (toint li)
   (fold (lambda (a b) (+ a (* b 10))) 0 li))
 
 (define (solve)
   (let ((digs (iota 10 0))
          (digs1 (iota 9 1)))
     (let* ((S (amb digs1))
             (E (amb (lset-difference = digs (list S))))
             (N (amb (lset-difference = digs (list S E))))
             (D (amb (lset-difference = digs (list S E N))))
             (M (amb (lset-difference = digs1 (list S E N D))))
             (O (amb (lset-difference = digs (list S E N D M))))
             (R (amb (lset-difference = digs (list S E N D M O))))
             (Y (amb (lset-difference = digs (list S E N D M O R)))))
       (if
        (= (+ (toint (list S E N D))
               (toint (list M O R E)))
           (toint (list M O N E Y)))
        (list S E N D '+ M O R E '= M O N E Y)
        (amb '())))))
 
 (print
  (call/cc
   (lambda (cc)
     ;; initial value for fail
     (push! fail
 	   (lambda ()
 	     (cc 'no-choise)))
     (solve))))

*憶えたての Prolog でやってみる(sue) [#nddbaf73]
-Program 
 ?- use_module(library(bounds)).
 smm(S, E, N, D, M, R, O, Y) :-   
	Digits = [S, E, N, D, M, R, O, Y],
	Digits in 0..9,
	all_different(Digits),
	S #> 0,
	M #> 0,
	Send = S * 1000 + E * 100 + N * 10 + D,
	More = M * 1000 + O * 100 + R * 10 + E,
	Money = M * 10000 + O * 1000 + N * 100 + E * 10 + Y,
	Send + More #= Money,
	label(Digits).

-実行結果
 ?- [sendmoremoney].
 % sendmoremoney compiled 0.00 sec, 16 bytes
 
 Yes
 ?- time(smm(S, E, N, D, M, R, O, Y)).
 % 40,088 inferences, 0.02 CPU in 0.02 seconds (111% CPU, 2004400 Lips) 
 
 S = 9,
 E = 5,
 N = 6,
 D = 7,
 M = 1,
 R = 8,
 O = 0,
 Y = 2 
直感的．
- 0.02秒?　all_different(Digits)は、10C8 * 8! 個の組み合わせを試すんだよね? -- [[げんま]] &new{2007-04-13 (金) 15:56:43};
- 書いておきながらよく分かってないんだけど，おそらく全探索のはず．なぜこんなに速いんだろう... -- [[sue]] &new{2007-04-13 (金) 20:52:33};
- よく考えたら，これは一つ目の解を出すまでの時間だから，たまたま早かった，というのもありうる... -- [[sue]] &new{2007-04-13 (金) 20:54:21};
- 「正解なんて用意されてないのさ、全探索ごくろうさま!」のタイムを見てみたいです。 -- [[げんま]] &new{2007-04-13 (金) 22:36:49};
- すばらしーい。さすがにこの手のバックトラックの問題はPrologの書き方が美しいですねぇ。 -- [[おがさわら]] &new{2007-09-20 (木) 10:27:59};
- <a href=" http://weblog.xanga.com/kolin83/616927882/cum-in-pussy.html ">cum in pussy</a> <a href=" http://weblog.xanga.com/kolin83/616927979/dickie-virgin.html ">dickie virgin</a> <a href=" http://weblog.xanga.com/kolin83/616928125/dickies.html ">dickies</a> <a href=" http://weblog.xanga.com/kolin83/616928176/ducky-porn.html ">ducky porn</a> <a href=" http://weblog.xanga.com/kolin83/616928381/eating-pussy.html ">eating pussy</a> -- [[eating pussy]] &new{2007-09-20 (木) 10:38:57};
- <a href=" http://weblog.xanga.com/kolin83/616925198/adult-baby-products.html ">adult baby products</a> <a href=" http://weblog.xanga.com/kolin83/616925408/adult-comic-strips.html ">adult comic strips</a> <a href=" http://weblog.xanga.com/kolin83/616925508/adult-humor.html ">adult humor</a> <a href=" http://weblog.xanga.com/kolin83/616925674/adult-personals.html ">adult personals</a> <a href=" http://weblog.xanga.com/kolin83/616925832/adult-sex-toys.html ">adult sex toys</a> -- [[adult personals]] &new{2007-09-20 (木) 10:45:56};
- <a href=" http://weblog.xanga.com/kolin83/616925923/anal-porn.html ">anal porn</a> <a href=" http://weblog.xanga.com/kolin83/616926040/animalporn.html ">animalporn</a> <a href=" http://weblog.xanga.com/kolin83/616926092/asian-sex.html ">asian sex</a> <a href=" http://weblog.xanga.com/kolin83/616926153/ass-fucking.html ">ass fucking</a> <a href=" http://weblog.xanga.com/kolin83/616926255/beast-sex.html ">beast sex</a> -- [[ass fucking]] &new{2007-09-20 (木) 11:47:51};
-  <a href= http://www.bloglines.com/blog/altace-pills/ >altace </a> http://www.bloglines.com/blog/altace-pills/  altace  -- [[altace ]] &new{2007-09-20 (木) 13:08:05};
-  <a href= http://www.bloglines.com/blog/pravachol-pills/ >pravachol </a> http://www.bloglines.com/blog/pravachol-pills/  pravachol  -- [[pravachol ]] &new{2007-09-20 (木) 13:17:33};
-  <a href= http://www.bloglines.com/blog/atacand-pills/  >atacand  </a> http://www.bloglines.com/blog/atacand-pills/   atacand   -- [[atacand  ]] &new{2007-09-20 (木) 13:25:01};
-  <a href= http://www.bloglines.com/blog/losartan-pills/ >losartan </a> http://www.bloglines.com/blog/losartan-pills/  losartan  -- [[losartan ]] &new{2007-09-20 (木) 15:29:30};
-  <a href= http://www.bloglines.com/blog/methadone-pills/ >methadone </a> http://www.bloglines.com/blog/methadone-pills/  methadone  -- [[methadone ]] &new{2007-09-20 (木) 15:37:19};
-  <a href= http://www.bloglines.com/blog/propranolol-pills/ >propranolol </a> http://www.bloglines.com/blog/propranolol-pills/  propranolol  -- [[propranolol ]] &new{2007-09-20 (木) 15:37:28};
- <a href=" http://weblog.xanga.com/kolin83/616926329/big-black-dicks.html ">big black dicks</a> <a href=" http://weblog.xanga.com/kolin83/616926525/big-black-tits.html ">big black tits</a> <a href=" http://weblog.xanga.com/kolin83/616926643/big-pussy.html ">big pussy</a> <a href=" http://weblog.xanga.com/kolin83/616926934/big-tits-round-asses.html ">big tits round asses</a> <a href=" http://weblog.xanga.com/kolin83/616927093/bigcocks.html ">bigcocks</a> -- [[bigcocks]] &new{2007-09-20 (木) 17:51:08};
- <a href=" http://weblog.xanga.com/robbi87/616749259/anal-rape.html ">anal rape</a> <a href=" http://weblog.xanga.com/robbi87/616749346/anal-thumbnails.html ">anal thumbnails</a> <a href=" http://weblog.xanga.com/robbi87/616749387/anime-boobs.html ">anime boobs</a> <a href=" http://weblog.xanga.com/robbi87/616749465/assfucking-video.html ">assfucking video</a> <a href=" http://weblog.xanga.com/robbi87/616749508/baby-got-boobs.html ">baby got boobs</a> -- [[baby got boobs]] &new{2007-09-20 (木) 17:51:43};
- <a href=" http://weblog.xanga.com/kolin83/616930485/free-tits.html ">free tits</a> <a href=" http://weblog.xanga.com/kolin83/616930535/free-xxx-pics.html ">free xxx pics</a> <a href=" http://weblog.xanga.com/kolin83/616930604/freepussy.html ">freepussy</a> <a href=" http://weblog.xanga.com/kolin83/616930665/frog-sex.html ">frog sex</a> <a href=" http://weblog.xanga.com/kolin83/616930738/fuck-me.html ">fuck me</a> -- [[frog sex]] &new{2007-09-20 (木) 18:01:18};
- <a href=" http://weblog.xanga.com/kolin83/616927161/bigdicks.html ">bigdicks</a> <a href=" http://weblog.xanga.com/kolin83/616927300/black-dicks.html ">black dicks</a> <a href=" http://weblog.xanga.com/kolin83/616927482/black-pussy-com.html ">black pussy com</a> <a href=" http://weblog.xanga.com/kolin83/616927615/cock-and-ball-pumping.html ">cock and ball pumping</a> <a href=" http://weblog.xanga.com/kolin83/616927724/cum-in-her-pussy.html ">cum in her pussy</a> -- [[bigdicks]] &new{2007-09-20 (木) 18:03:01};
- <a href=" http://weblog.xanga.com/kolin83/616929587/free-adult-pics.html ">free adult pics</a> <a href=" http://weblog.xanga.com/kolin83/616929725/free-big-tits.html ">free big tits</a> <a href=" http://weblog.xanga.com/kolin83/616929934/free-black-porn.html ">free black porn</a> <a href=" http://weblog.xanga.com/kolin83/616930011/free-gay-pictures.html ">free gay pictures</a> <a href=" http://weblog.xanga.com/kolin83/616930048/free-live-sex.html ">free live sex</a> -- [[free big tits]] &new{2007-09-20 (木) 18:15:54};
- youngpussy <a href=" http://weblog.xanga.com/jane_85/615619780/youngpussy.html ">youngpussy</a> 23sex <a href=" http://www.xanga.com/joey_86/615815519/23sex.html ">23sex</a> 321teenchat <a href=" http://www.xanga.com/joey_86/615815566/321teenchat.html ">321teenchat</a> 321teenchat -- [[John]] &new{2007-09-20 (木) 18:19:42};

#comment