-- Cryptarithmetic puzzle implemented with Distinct Choices -- Sergio Antoy & Michael Hanus -- Wed Feb 19 19:31:58 PST 2003 -- Updated Mon Apr 18 09:03:37 PDT 2011 -- Updated Wed Jun 28 13:29:49 PDT 2017 -- This version assumes a priori knowledge of a finite set -- containing the mapped indices of the problem. -- The store is represented by a tree whose nodes are -- decorated by values and indices of the problem. -- The latter are initially unbound variables. import Profile import SetFunctions {- TOO + MUCH + BEER 133 + 4869 = 5002 133 + 4876 = 5009 144 + 2865 = 3009 144 + 6859 = 7003 177 + 3829 = 4006 177 + 4826 = 5003 177 + 4829 = 5006 177 + 4832 = 5009 177 + 5832 = 6009 211 + 3795 = 4006 211 + 5793 = 6004 233 + 4768 = 5001 244 + 8761 = 9005 255 + 8746 = 9001 266 + 8735 = 9001 277 + 4839 = 5116 311 + 4697 = 5008 311 + 7694 = 8005 322 + 4679 = 5001 322 + 4687 = 5009 322 + 4796 = 5118 344 + 8657 = 9001 355 + 8647 = 9002 377 + 8624 = 9001 388 + 4619 = 5007 388 + 4621 = 5009 411 + 2596 = 3007 411 + 2597 = 3008 411 + 5927 = 6338 411 + 6592 = 7003 411 + 7592 = 8003 411 + 7925 = 8336 422 + 6581 = 7003 422 + 7693 = 8115 433 + 1576 = 2009 433 + 7569 = 8002 477 + 1859 = 2336 477 + 8526 = 9003 477 + 8635 = 9112 488 + 2519 = 3007 488 + 6521 = 7009 511 + 2496 = 3007 511 + 2497 = 3008 511 + 6492 = 7003 511 + 7492 = 8003 522 + 6481 = 7003 522 + 6809 = 7331 522 + 6918 = 7440 533 + 1476 = 2009 533 + 6908 = 7441 533 + 7469 = 8002 533 + 7691 = 8224 544 + 1786 = 2330 577 + 1863 = 2440 577 + 8426 = 9003 577 + 8643 = 9220 588 + 2419 = 3007 588 + 6421 = 7009 611 + 2947 = 3558 611 + 4397 = 5008 611 + 4728 = 5339 611 + 7394 = 8005 611 + 7942 = 8553 611 + 8724 = 9335 622 + 4379 = 5001 622 + 4387 = 5009 622 + 4709 = 5331 622 + 7493 = 8115 633 + 7591 = 8224 633 + 7921 = 8554 644 + 2907 = 3551 644 + 8357 = 9001 655 + 1793 = 2448 655 + 8347 = 9002 677 + 8324 = 9001 677 + 8435 = 9112 677 + 8543 = 9220 688 + 4319 = 5007 688 + 4321 = 5009 711 + 3295 = 4006 711 + 4628 = 5339 711 + 5293 = 6004 711 + 8624 = 9335 722 + 4396 = 5118 722 + 4609 = 5331 722 + 4938 = 5660 733 + 4268 = 5001 733 + 4928 = 5661 744 + 1586 = 2330 744 + 1809 = 2553 744 + 8261 = 9005 755 + 1693 = 2448 755 + 1908 = 2663 755 + 8246 = 9001 766 + 8235 = 9001 811 + 2964 = 3775 811 + 4962 = 5773 822 + 6509 = 7331 833 + 4169 = 5002 833 + 4176 = 5009 844 + 1709 = 2553 844 + 2165 = 3009 844 + 6159 = 7003 855 + 3921 = 4776 866 + 2905 = 3771 866 + 3905 = 4771 877 + 1459 = 2336 877 + 1563 = 2440 877 + 3129 = 4006 877 + 4126 = 5003 877 + 4129 = 5006 877 + 4132 = 5009 877 + 4239 = 5116 877 + 5132 = 6009 911 + 2647 = 3558 911 + 2864 = 3775 911 + 4862 = 5773 911 + 5427 = 6338 911 + 7425 = 8336 911 + 7642 = 8553 922 + 4738 = 5660 922 + 6518 = 7440 933 + 4728 = 5661 933 + 6508 = 7441 933 + 7621 = 8554 944 + 2607 = 3551 955 + 1708 = 2663 955 + 3821 = 4776 966 + 2805 = 3771 966 + 3805 = 4771 -} data Store = Leaf | Branch (Int,Char) Store Store insert d Leaf = Branch (d,x) Leaf Leaf where x free insert d (Branch (x,y) s t) | d < x = Branch (x,y) (insert d s) t | d > x = Branch (x,y) s (insert d t) initStore = fill [5,3,1,0,4,2,6,8,9,7] Leaf where fill [] store = store fill (d:ds) store = fill ds (insert d store) check (I,C) (Branch (i,c) s t) | I == i = C =:= c | I < i = check (I,C) s | I > i = check (I,C) t main | equations = "\n" ++ " " ++ show vt ++ show vo ++ show vo ++ "\n" ++ show vm ++ show vu ++ show vc ++ show vh ++ "\n" ++ show vb ++ show ve ++ show ve ++ show vr ++ "\n" where store = initStore -- the digits vt,vo,vm,vu,vc,vh,vb,ve,vr free -- the carries c0 = 0?1 c1 = 0?1 c2 = 0?1 -- the problem's relations, fragmentation is good equations = vm+c2 == vb & vt+vu+c1 == c2*10+ve & vo+vc+c0 == c1*10+ve & vo+vh == c0*10+vr & vm == nzdigit 'M' & vb == nzdigit 'B' & vt == nzdigit 'T' & vu == digit 'U' & ve == digit 'E' & vo == digit 'O' & vc == digit 'C' & vh == digit 'H' & vr == digit 'R' nzdigit token | check (x,token) store = x where x = 1?2?3?4?5?6?7?8?9 digit token | check (x,token) store = x where x = 0?1?2?3?4?5?6?7?8?9 -- 130 solutions in 10.3 secs on 333Mhz laptop benchall = evalTime (set0 main) -- end of program