トップ
新規
単語検索
ヘルプ
ネタ記録庫/SEND+MORE=MONEY
をテンプレートにして作成
開始行:
[[ネタ記録庫/SEND+MORE=MONEY]]
S E N D
+ M O R E
----------
M O N E Y
(S,M != 0)
- 10/18の OCaml講義第3回 by ガリグ先生で、授業の課題とし...
- 授業では、search関数はガリグ先生のお手本があって、生徒...
- 計算量が苦しいなら、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...
((List.assoc 'S' d != 0) &&
(List.assoc 'M' d != 0) &&
((f ['S'; 'E'; 'N'; 'D']) + (f ['M'; 'O'; 'R'; 'E']) ...
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 @...
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 ...
solve();;
* Gauche [#if874cf2]
ライブラリに、順列組み合わせのpermutationなどがあったので...
(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.n...
([[らくがきえんじん:http://d.hatena.ne.jp/syd_syd/2006101...
何も考えてない。15分くらいででけた。こういう問題にはリス...
Showのインスタンスが必要なのはご愛嬌。
import Control.Monad.State
ten = [0..9]
-- StateT [Int] [] Intが何であるかを考えるより、単に [In...
-- (「リストlを貰って、その中のどれかの要素eと、lからeを...
getNum :: StateT [Int] [] Int
getNum = StateT $ ?ns -> do{n <- ns; return (n, filter (...
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*...
instance (Show s, Show e, Show n, Show d, Show m, Show o...
Show (s,e,n,d,m,o,r,y) where
show (s,e,n,d,m,o,r,y) = "("++show s++","++show e++","...
show d++","++show m++","...
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)で...
*そっちが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...
(O (amb (lset-difference = digs (list S E N ...
(R (amb (lset-difference = digs (list S E N ...
(Y (amb (lset-difference = digs (list S E N ...
(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,...
S = 9,
E = 5,
N = 6,
D = 7,
M = 1,
R = 8,
O = 0,
Y = 2
直感的.
- 0.02秒? all_different(Digits)は、10C8 * 8! 個の組み合...
- 書いておきながらよく分かってないんだけど,おそらく全探...
- よく考えたら,これは一つ目の解を出すまでの時間だから,...
- すばらしーい。さすがにこの手のバックトラックの問題はPro...
終了行:
[[ネタ記録庫/SEND+MORE=MONEY]]
S E N D
+ M O R E
----------
M O N E Y
(S,M != 0)
- 10/18の OCaml講義第3回 by ガリグ先生で、授業の課題とし...
- 授業では、search関数はガリグ先生のお手本があって、生徒...
- 計算量が苦しいなら、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...
((List.assoc 'S' d != 0) &&
(List.assoc 'M' d != 0) &&
((f ['S'; 'E'; 'N'; 'D']) + (f ['M'; 'O'; 'R'; 'E']) ...
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 @...
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 ...
solve();;
* Gauche [#if874cf2]
ライブラリに、順列組み合わせのpermutationなどがあったので...
(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.n...
([[らくがきえんじん:http://d.hatena.ne.jp/syd_syd/2006101...
何も考えてない。15分くらいででけた。こういう問題にはリス...
Showのインスタンスが必要なのはご愛嬌。
import Control.Monad.State
ten = [0..9]
-- StateT [Int] [] Intが何であるかを考えるより、単に [In...
-- (「リストlを貰って、その中のどれかの要素eと、lからeを...
getNum :: StateT [Int] [] Int
getNum = StateT $ ?ns -> do{n <- ns; return (n, filter (...
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*...
instance (Show s, Show e, Show n, Show d, Show m, Show o...
Show (s,e,n,d,m,o,r,y) where
show (s,e,n,d,m,o,r,y) = "("++show s++","++show e++","...
show d++","++show m++","...
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)で...
*そっちが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...
(O (amb (lset-difference = digs (list S E N ...
(R (amb (lset-difference = digs (list S E N ...
(Y (amb (lset-difference = digs (list S E N ...
(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,...
S = 9,
E = 5,
N = 6,
D = 7,
M = 1,
R = 8,
O = 0,
Y = 2
直感的.
- 0.02秒? all_different(Digits)は、10C8 * 8! 個の組み合...
- 書いておきながらよく分かってないんだけど,おそらく全探...
- よく考えたら,これは一つ目の解を出すまでの時間だから,...
- すばらしーい。さすがにこの手のバックトラックの問題はPro...
ページ名: