Posts Tagged ‘coin’

Programming Praxis – Coin Change, Part 1

May 17, 2013

In today’s Programming Praxis exercise, our goal is to list all of the ways in which a target amount can be reached given a list of coin denominations. Let’s get started, shall we?

`import Data.List`

We check the first remaining coin to see if it’s not bigger than the remaining target amount. If so, subtract it from the target amount and call the algorithm recursively. If not, delete it from the list of remaining coins and continue. When the remaining amount reaches 0, we have found a valid combination.

```coins :: (Num a, Ord a) => [a] -> a -> [[a]]
coins _  0 = [[]]
coins xs n = [c:r | (c:cs) <- tails xs, c <= n, r <- coins (c:cs) (n-c)]```

Since the logic for counting the total number of options and generating the options is nigh identical, we simply ask for the length of the resulting list.

```count :: (Num a, Ord a) => [a] -> a -> Int
count xs = length . coins xs```

Some tests to see if everything is working properly:

```main :: IO ()
main = do print \$ count [1,5,10,25] 40 == 31
mapM_ print \$ coins [1,5,10,25] 40```

Programming Praxis – MindCipher

May 10, 2013

In today’s Programming Praxis exercise, our goal is to solve two exercises from the MindCipher website (technically three, but the third one can be solved without programming). Let’s get started, shall we?

```import Control.Monad
import Data.List
import System.Random```

The first exercise is to see which pattern, on average, takes longer to come up when flipping a coin: heads, tails, heads or heads, tails, tails. First, we define a function to simulate single series of flips, counting the number of flips before the desired pattern is produced. Heads and tails are represented as booleans for the sake of convenience.

```flipUntil :: [Bool] -> IO Int
flipUntil pattern = fmap (length . takeWhile (not . isPrefixOf pattern) .
tails . randomRs (False, True)) newStdGen```

Next, we simulate an entire day by repeating this process 10000 times and taking the average.

```day :: [Bool] -> IO Double
day pattern = fmap (\cs -> fromIntegral (sum cs) / fromIntegral (length cs)) .
replicateM 10000 \$ flipUntil pattern```

For the second exercise, we need to find the first year for which the sum of both groups of two digits is equal to the middle two digits. This is easily achieved via a simple brute-force search.

```sumDay :: Maybe Integer
sumDay = find (\d -> div d 100 + mod d 100 == div (mod d 1000) 10) [1979..]```

Running our two algorithms shows that monday’s pattern takes longer on average and that the first year that satisfies the criteria is 2307.

```main :: IO ()
main = do print =<< liftM2 compare (day [False, True, False])
(day [False, True, True])
print sumDay```