Archive for August, 2012

Programming Praxis – Two Random Exercises

August 17, 2012

In today’s Programming Praxis exercise, our goal is to use convert two random number generators to a different range. Specifically, we have to convert an rng that produces numbers in the closed interval [1,3] to one that has the interval [1,9] and one with interval [1,5] to [1,7]. In both cases the resulting rngs must maintain an equal distribution across the interval. Let’s get started, shall we?

Some imports:

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

These are the two functions we can use as imports.

rand3, rand5 :: IO Int
rand3 = randomRIO (1,3)
rand5 = randomRIO (1,5)

To test, we use a distribution function to see how many of each element occur in a sequence.

dist :: (Eq a, Ord a) => [a] -> [(a, Int)]
dist = map (\x -> (head x, length x)) . group . sort

Let’s start with the easiest one. Since 9 = 3 * 3, all we need to do scale up one input by a factor of 3 and “interpolate” using a second one. The reason for taking a source parameter is to facilitate testing: you can either feed it an IO Int for a random result, or you can give it a [Int] to see all possible results. We’ll get to why the testing is important in a bit.

rand9 :: (Applicative f, Num a, Enum a) => f a -> f a
rand9 src = (+) . (*3) . pred <$> src <*> src

The second one is more complicated, since 5*5 is not a multiple of 7. The correct solution is to do the same thing as above using a subrange that is a multiple of 7, i.e. 21 of the 25 numbers and rerolling when one of the four values outside the accepted range is chosen. The problem with this approach is that it isn’t guaranteed to terminate, since there is nothing preventing a true random number generator from generating the number 23 a few trillion times in a row. Granted, we’re only using pseudo-random number generators, so it probably will never come up. Here’s the implementation:

rand7 :: (Applicative m, Monad m, Integral a) => m a -> m a
rand7 src = (+) . (*5) . pred <$> src <*> src >>= \n -> 
    if n > 21 then rand7 src else return (mod n 7 + 1)

Since I didn’t like the chance of a non-terminating algorithm I came up with the following algorithm: sum seven random numbers in the range 1 to 5, and give the result modulo 7. Or in code:

rand7approx :: (Functor f, Monad f, Integral a) => f a -> f a
rand7approx src = succ . (`mod` 7) . sum <$> replicateM 7 src

Printing the distribution looked perfectly fine, with all of them getting a little over 14%. But something felt off to me. The code was shorter than the version with rerolling and didn’t suffer the inifinite loop problem, so there had to be reason it wasn’t the provided solution. I changed all the functions to take a source argument rather than calling rand3 and rand5 directly and printed the theoretical distributions as well (except for rand7, since the distribution for that one is non-terminating). This revealed that there is a 0.3% difference between the most and least common values. In retrospect, this should’ve been obvious, as 5^7 mod 7 isn’t equal to 0, which means it’s impossible for all 7 values to get the same distribution. Some more reading up revealed that there is indeed no solution that both provides an equal distribution and is guaranteed to terminate, since 7 is an infinitely repeating fraction in base 5.

Here are the tests I used:

main :: IO ()
main = do print $ dist (rand9 [1..3]) == zip [1..9] [1,1..]
          print . dist =<< replicateM 100000 (rand9 rand3)
          print . dist =<< replicateM 100000 (rand7 rand5)
          print $ dist (rand7approx [1..5])
          print . dist =<< replicateM 100000 (rand7approx rand5)

Programming Praxis – 4SUM

August 14, 2012

In today’s Programming Praxis exercise, our goal is to find four integers in a given list that sum up to a given target number. Let’s get started, shall we?

We use the same approach of storing pair sums as the given solution. We store them using the sum as the key, which means we can use an IntMap, which offers improved performance over a regular Map.

import qualified Data.IntMap as I

First we generate all the pairs, then we try to find two pairs that sum up to the given number.

sum4 :: Int -> [Int] -> [[Int]]
sum4 n xs = take 1 [p1++p2 | (s, p1) <- I.assocs pairs
                           , p2 <- maybe [] return $ I.lookup (n-s) pairs]
    where pairs = I.fromList [(a+b, [a,b]) | a <- xs, b <- xs]

Some tests to see if everything is working properly:

main :: IO ()
main = do print $ sum (head $ sum4 0 [2,3,1,0,-4,-1]) == 0
          print $ sum4 0 [1,2,3,4,5,6] == []
          print $ sum4 13 [1,2,3,4,5,6] == [[1,1,6,5]]

Programming Praxis – Minimum Scalar Product

August 10, 2012

In today’s Programming Praxis exercise, our goal is to calculate the minimum scalar product of two vectors. Let’s get started, shall we?

A quick import:

import Data.List

Initially, I wrote a version that calculated all possible permutations and took the minimum value. After looking at the provided solution it turns out this isn’t necessary, which leads to the following shorter and more efficient version:

minScalar :: (Ord a, Num a) => [a] -> [a] -> a
minScalar a = sum . zipWith (*) (sort a) . reverse . sort

A test to see if everything is working properly:

main :: IO ()
main = print $ minScalar [1,3,-5] [-2,4,1] == -25