https://wiki.haskell.org/index.php?title=Haskell_Quiz/Verbal_Arithmetic/Solution_Dolio&feed=atom&action=history
Haskell Quiz/Verbal Arithmetic/Solution Dolio - Revision history
2024-03-28T17:08:41Z
Revision history for this page on the wiki
MediaWiki 1.35.5
https://wiki.haskell.org/index.php?title=Haskell_Quiz/Verbal_Arithmetic/Solution_Dolio&diff=32469&oldid=prev
Newacct at 08:15, 13 December 2009
2009-12-13T08:15:26Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 08:15, 13 December 2009</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 66:</td>
<td colspan="2" class="diff-lineno">Line 66:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>showEqn (Equation ss r) m = intercalate " + " (map showWord ss) ++ " = " ++ showWord r</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>showEqn (Equation ss r) m = intercalate " + " (map showWord ss) ++ " = " ++ showWord r</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> where</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> where</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> showWord = <del class="diffchange diffchange-inline">foldr</del> (\d<del class="diffchange diffchange-inline"> s</del> -> intToDigit (fromJust (M.lookup d m))<del class="diffchange diffchange-inline"> : s</del>)<del class="diffchange diffchange-inline"> []</del></div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> showWord = <ins class="diffchange diffchange-inline">map</ins> (\d -> intToDigit (fromJust (M.lookup d m)))</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>main = mapM_ display . <del class="diffchange diffchange-inline">map (</del>fmap solve . parse equation "foo") . lines =<< getContents</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>main = mapM_ <ins class="diffchange diffchange-inline">(</ins>display . fmap solve . parse equation "foo") . lines =<< getContents</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> where</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> where</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> display (Left _) = putStrLn "Bad parse."</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> display (Left _) = putStrLn "Bad parse."</div></td>
</tr>
</table>
Newacct
https://wiki.haskell.org/index.php?title=Haskell_Quiz/Verbal_Arithmetic/Solution_Dolio&diff=13573&oldid=prev
Dolio: formatting
2007-06-19T00:36:20Z
<p>formatting</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 00:36, 19 June 2007</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 51:</td>
<td colspan="2" class="diff-lineno">Line 51:</td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>-- The overall constraint for solving equations</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>-- The overall constraint for solving equations</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>eqncsp :: Equation -> CSP Int ()</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>eqncsp :: Equation -> CSP Int ()</div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>eqncsp e@(Equation s r@(hr:_)) = go (columns s) (reverse r) 0</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>eqncsp e@(Equation s r@(hr:_)) = go (columns s) (reverse r) 0<ins class="diffchange diffchange-inline"> >> sigfig e</ins></div></td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> >> sigfig e</div></td>
<td colspan="2" class="diff-empty"> </td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> where</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> where</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> go (vs:vss) (r:rs) carry = digitcsp vs carry r >>= go vss rs</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div> go (vs:vss) (r:rs) carry = digitcsp vs carry r >>= go vss rs</div></td>
</tr>
<!-- diff cache key wikidb_haskell:diff:wikidiff2:1.12:old-13570:rev-13573:1.10.0 -->
</table>
Dolio
https://wiki.haskell.org/index.php?title=Haskell_Quiz/Verbal_Arithmetic/Solution_Dolio&diff=13570&oldid=prev
Dolio: category
2007-06-18T20:25:40Z
<p>category</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:25, 18 June 2007</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td>
</tr>
<tr>
<td class="diff-marker">−</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Haskell Quiz <del class="diffchange diffchange-inline">Solutions</del>|Verbal Arithmetic]]</div></td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Haskell Quiz <ins class="diffchange diffchange-inline">solutions</ins>|Verbal Arithmetic]]</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>This solution doesn't do anything particularly special. It parses the equations using a simple Parsec parser, and then searches for solutions using backtracking search via the list monad. However, to make things a bit simpler, I wrapped up the searching into what I called the CSP monad (for constraint satisfaction problem), that automatically handles the remembering of already assigned variables, and branching when attempting to use a previously unassigned variable. It's not a clever solution, algorithmically, but it gets the job done for such a small problem as this.</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>This solution doesn't do anything particularly special. It parses the equations using a simple Parsec parser, and then searches for solutions using backtracking search via the list monad. However, to make things a bit simpler, I wrapped up the searching into what I called the CSP monad (for constraint satisfaction problem), that automatically handles the remembering of already assigned variables, and branching when attempting to use a previously unassigned variable. It's not a clever solution, algorithmically, but it gets the job done for such a small problem as this.</div></td>
</tr>
</table>
Dolio
https://wiki.haskell.org/index.php?title=Haskell_Quiz/Verbal_Arithmetic/Solution_Dolio&diff=13569&oldid=prev
Dolio: category
2007-06-18T20:25:19Z
<p>category</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 20:25, 18 June 2007</td>
</tr><tr>
<td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:Haskell Quiz Solutions|Verbal Arithmetic]]</div></td>
</tr>
<tr>
<td colspan="2" class="diff-empty"> </td>
<td class="diff-marker">+</td>
<td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>This solution doesn't do anything particularly special. It parses the equations using a simple Parsec parser, and then searches for solutions using backtracking search via the list monad. However, to make things a bit simpler, I wrapped up the searching into what I called the CSP monad (for constraint satisfaction problem), that automatically handles the remembering of already assigned variables, and branching when attempting to use a previously unassigned variable. It's not a clever solution, algorithmically, but it gets the job done for such a small problem as this.</div></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>This solution doesn't do anything particularly special. It parses the equations using a simple Parsec parser, and then searches for solutions using backtracking search via the list monad. However, to make things a bit simpler, I wrapped up the searching into what I called the CSP monad (for constraint satisfaction problem), that automatically handles the remembering of already assigned variables, and branching when attempting to use a previously unassigned variable. It's not a clever solution, algorithmically, but it gets the job done for such a small problem as this.</div></td>
</tr>
<tr>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
<td class="diff-marker"> </td>
<td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td>
</tr>
</table>
Dolio
https://wiki.haskell.org/index.php?title=Haskell_Quiz/Verbal_Arithmetic/Solution_Dolio&diff=13568&oldid=prev
Dolio: creation
2007-06-18T20:24:01Z
<p>creation</p>
<p><b>New page</b></p><div>This solution doesn't do anything particularly special. It parses the equations using a simple Parsec parser, and then searches for solutions using backtracking search via the list monad. However, to make things a bit simpler, I wrapped up the searching into what I called the CSP monad (for constraint satisfaction problem), that automatically handles the remembering of already assigned variables, and branching when attempting to use a previously unassigned variable. It's not a clever solution, algorithmically, but it gets the job done for such a small problem as this.<br />
<br />
The problem specific code:<br />
<br />
<haskell><br />
module Main(main) where<br />
<br />
import Control.Monad<br />
<br />
import Data.Char<br />
import Data.List<br />
import Data.Maybe<br />
<br />
import Data.Map (Map)<br />
import qualified Data.Map as M<br />
<br />
import Text.ParserCombinators.Parsec<br />
<br />
import CSP<br />
<br />
data Equation = Equation { summands :: [String], result :: String } deriving Show<br />
<br />
-- A quick parser for the equations in use. I didn't bother trying to cover all<br />
-- eventualities, but it will parse 'word1 + word2 + word3 ... = result'<br />
add = char '+' >> spaces >> return (++)<br />
equ = char '=' >> spaces<br />
vnum = many1 lower >>= \a -> spaces >> return a<br />
<br />
equation = do l <- chainl1 (liftM return vnum) add<br />
equ<br />
r <- vnum<br />
return (Equation l r)<br />
<br />
-- Constraints on individual digits. Digits in a column, plus the carry-in, mod 10<br />
-- must equal the result digit. Returns the carry-out<br />
digitcsp :: [Char] -> Int -> Char -> CSP Int Int<br />
digitcsp vs carry result = do l <- mapM byName vs<br />
let (d, m) = divMod (carry + sum l) 10<br />
byName result >>= guard . (m ==)<br />
return d<br />
<br />
-- Constraint to make sure the left-most digit on any term is not zero. We don't want<br />
-- 'two = 012', for instance.<br />
sigfig :: Equation -> CSP Int ()<br />
sigfig (Equation ss r) = chk r >> foldM_ (const chk) () ss<br />
where<br />
chk (h:_) = byName h >>= guard . (0 /=)<br />
<br />
-- The overall constraint for solving equations<br />
eqncsp :: Equation -> CSP Int ()<br />
eqncsp e@(Equation s r@(hr:_)) = go (columns s) (reverse r) 0<br />
>> sigfig e<br />
where<br />
go (vs:vss) (r:rs) carry = digitcsp vs carry r >>= go vss rs<br />
go [] [r] carry = byName r >>= guard . (carry ==)<br />
go [] [] 0 = return ()<br />
go _ _ _ = mzero<br />
<br />
-- turns a list of terms into a list of letters in each column, to be summed.<br />
columns :: [String] -> [[Char]]<br />
columns = transpose . map reverse<br />
<br />
-- Given an equation, and mappings for all the letters, constructs the numerals<br />
showEqn :: Equation -> Map Char Int -> String<br />
showEqn (Equation ss r) m = intercalate " + " (map showWord ss) ++ " = " ++ showWord r<br />
where<br />
showWord = foldr (\d s -> intToDigit (fromJust (M.lookup d m)) : s) []<br />
<br />
main = mapM_ display . map (fmap solve . parse equation "foo") . lines =<< getContents<br />
where<br />
display (Left _) = putStrLn "Bad parse."<br />
display (Right ss) = mapM_ putStrLn ss<br />
<br />
solve :: Equation -> [String]<br />
solve e = map (showEqn e) ms<br />
where ms = execCSP (eqncsp e) [0..9]<br />
</haskell><br />
<br />
And the CSP monad. There is an auxiliary 'SupplyT' monad which encapsulates selecting non-deterministically from a stored supply.<br />
<br />
<haskell><br />
{-# OPTIONS_GHC -fglasgow-exts #-}<br />
<br />
module CSP where<br />
<br />
import Data.Map (Map)<br />
import qualified Data.Map as M<br />
<br />
import Control.Arrow<br />
import Control.Monad<br />
import Control.Monad.State<br />
import Control.Monad.Reader<br />
import Control.Monad.Trans<br />
<br />
newtype CSP b a = CSP { unCSP :: StateT (Map Char b) (SupplyT b []) a }<br />
deriving (Monad, MonadPlus, MonadState (Map Char b),<br />
MonadSupply b)<br />
<br />
newtype SupplyT s m a = SupplyT { unSupplyT :: StateT [s] m a }<br />
deriving (Monad, MonadPlus, MonadState [s])<br />
<br />
class MonadPlus m => MonadSupply s m where<br />
getSupply :: m s<br />
<br />
instance MonadPlus m => MonadSupply s (SupplyT s m) where<br />
getSupply = do l <- get<br />
(v, l') <- choose (pick l)<br />
put l'<br />
return v<br />
where<br />
pick (h:t) = (h, t) : map (second (h:)) (pick t)<br />
pick [] = mzero<br />
<br />
instance MonadSupply s m => MonadSupply s (StateT r m) where<br />
getSupply = lift getSupply<br />
<br />
runSupplyT :: Monad m => SupplyT s m a -> [s] -> m a<br />
runSupplyT st s = flip evalStateT s . unSupplyT $ st<br />
<br />
runCSP :: CSP b a -> [b] -> [(a, Map Char b)]<br />
runCSP c l = flip runSupplyT l . flip runStateT M.empty . unCSP $ c<br />
<br />
evalCSP :: CSP b a -> [b] -> [a]<br />
evalCSP c l = flip runSupplyT l . flip evalStateT M.empty . unCSP $ c<br />
<br />
execCSP :: CSP b a -> [b] -> [Map Char b]<br />
execCSP c l = flip runSupplyT l . flip execStateT M.empty . unCSP $ c<br />
<br />
byName :: Char -> CSP b b<br />
byName k = gets (M.lookup k) >>= maybe c return<br />
where c = getSupply >>= assign k<br />
<br />
assign :: Char -> a -> CSP a a<br />
assign k a = modify (M.insert k a) >> return a<br />
<br />
choose :: MonadPlus m => [a] -> m a<br />
choose = msum . map return<br />
</haskell></div>
Dolio