Monthly Archives: February 2013

Simplicity

zen-garden-983809

Programming Praxis 4: Sudoku Solution

Sudoku problems can be perceived as quite complex. Counter-intuitively and from a mathematical standpoint, the solution is actually quite simple. I wrote this solution a while back in Python by pulling together algorithms from a number of sources. But by translating it into Haskell again, I think its acheived a certain Zen-like simplicity and elegance. Or maybe its the homebrew talking.

import Data.List
import Data.Maybe

check :: Int -> Int -> Bool
check i j
	| (f i)/9 == (f j)/9 = True
	| mod (i-j) 9 == 0 = True
	| (f i)/27 == (f j)/27 && (f $ mod i 9)/3 == (f $ mod j 9)/3 = True
	| otherwise = False
	where
		f = fromIntegral

solve :: [Int] -> [Int]
solve s
	| elem 0 s = solve $ a ++ [n | n <- [1..9], elem n e == False] ++ b
	| otherwise = s
	where
		a = take i s
		b = drop (i + 1) s
		i = fromJust $ elemIndex 0 s
		e = [s !! j | j <- [0..80], check i j]
		
main = print $ solve [7,0,0,1,0,0,0,0,0,0,2,0,0,0,0,0,1,5,0,0,0,0,0,6,3,9,0,2,
        0,0,0,1,8,0,0,0,0,4,0,0,9,0,0,7,0,0,0,0,7,5,0,0,0,3,0,7,8,5,0,0,0,0,0,
        5,6,0,0,0,0,0,4,0,0,0,0,0,0,1,0,0,2]

Dirty Little Monad

water bottle1
Never tried random numbers before in Haskell. Obviously it must involve a Monad, because randomness is considered so unpure. Found this great line somewhere, worth sharing here:

Using Monads in Haskell is like drinking from the communal water bottle, but never letting your lips touch the bottle.

Programming Praxis 3: Bingo

Such a simple game, Bingo, but such an annoying problem in Haskell. I suppose most of my grief stems from the fact that I’m still thinking in imperative concepts. Eventually I figured out that I would need to use higher order functions (and/or tail recursion) in lieu of iteration. Then I spent the next week reviewing mind numbing concepts like filters, maps, folds, scans. All are incredibly powerful but eventually I didn’t need them. Everything reduced down to good old fashioned list comprehensions. Still my favourite Haskell feature.

Found that System.Random provided lots of handy functions. “randomRs” needs seeds, so I just used the count numbers. Not very random, but ok for these purposes. Since its a random generator, I couldn’t guarantee that all my needed numbers were picked. So I generated more than enough numbers over a range, removed duplicates with “nub” and took the right number.

The other interesting note is the use of Data.Maybe. When using “elemIndex“, it could throw an error, so the function will return a type “Maybe“, akin to a Null value in other languages. Used “fromJust” to strip the “Maybe” off and use the “Int“. Didn’t worry about the error because the pool always held all 75 numbers.

In main, printed just the two calculations. The first shows the average number of balls called to get to Bingo with only one card and 500 different pools. The second shows the average number calls used to get to Bingo with one pool and 500 different cards. Routine only takes a second to run in GHCi.

import System.Random
import Data.List
import Data.Maybe

makePool :: Int -> [Int]
makePool s = take 75 $ nub $ take (1000) $ randomRs (1,75) (mkStdGen s) :: [Int]

makeCard :: Int -> [Int]
makeCard seed = (b ++ i ++ n ++ g ++ o)
  where
    b = take 5 $ nub $ take 20 $ randomRs (1,15) (mkStdGen seed) :: [Int]
    i = take 5 $ nub $ take 20 $ randomRs (16,30) (mkStdGen $ sum b) :: [Int]
    n = take 5 $ nub $ take 20 $ randomRs (31,45) (mkStdGen $ sum i) :: [Int]
    g = take 5 $ nub $ take 20 $ randomRs (46,60) (mkStdGen $ sum n) :: [Int]
    o = take 5 $ nub $ take 20 $ randomRs (61,75) (mkStdGen $ sum g) :: [Int]

filterCard :: [Int] -> [[Int]]
filterCard card = [[card !! x | x <- r] | r <- ranges]
  where
    ranges = [[0..4],[5..9],[10,11,13,14],[15..19],[20..24],
      [0,5..20],[1,6..21],[2,7,17,22],[3,8..23],[4,9..24],[0,6,18,24],[4,8,16,20]]

evaluate :: [Int] -> [Int] -> Int
evaluate pool subcard = maximum [fromJust $ elemIndex x pool | x <- subcard, elem x pool]

bingoTest :: [Int] -> [Int] -> Int
bingoTest pool card = minimum [evaluate pool x | x <- (filterCard card)]

main = do
  print $ 0.002 * fromIntegral (sum [bingoTest (makePool x) $ makeCard 1 | x <- [1..500]])
  print $ 0.002 * fromIntegral (sum [bingoTest (makePool 1) $ makeCard x | x <- [1..500]])

For Great Wine: Take Your Time and Follow the Directions

IMG_1037
Decided to try a bottle of my first wine batch a little early. See, I made some Pinot Noir using a 6-week kit fully expecting to let it “age” in the bottle afterwards a good couple months. My mother-in-law who will remain nameless (who got half the batch I might add) decided it was time to open up after only a couple weeks. After several OMG texts, we decided to open one too.

Notwithstanding it was young, there was no nasty aftertaste usually found with homemade wines made on store prem. The wine was smooth, deep flavour and was really enjoyable. Can you hear my surprise?

Brewing in the store can produce some good batches, but considering they’re probably cranking out at least a dozen batches a day, they gotta be cutting some corners. Maybe “it needed an extra day”, or maybe “hey, let’s add these bags together rather than 2 days apart”. In any case, there is nothing better than taking your time at home and following the manufacturer’s instructions exactly. The results are surprising.

My mother-in-law has ordered another batch. So I’m starting a Valpolicella (with grape skins). I am fully confident that its going to kick ass.

IPA 2.0

20130203-130639.jpg Just tried the first bottle from my second batch of IPA. Its only a week old and look how clear it is already. Made it following the same recipe as before because it was so damn good. The carbonation is still a bit weak and it needs to sharpen up. But this batch will be great in a couple weeks.

Next time, I’m considering doing IPA old school, using the can and malted sugar, rather than pre-pasteurized wort. This way, when I boil the wort myself, I can throw in some extra hops at the end. I prefer a North American IPA (ie. not wimpy). Festa Brew makes a West Cost IPA; maybe I can get ahold of that.

Basket Making 101

Kalathos_Louvre_MNE1176
Praxis 2: Write a function that calculates the list of prime numbers using the Sieve of Eratosthenes.

Ummm, yeah. Done it a couple dozen times before over at Project Euler. Never hurts to review. I did manage to use more function composition this time around. Oh, and don’t forget to install module data.ordlist using Cabal.


import Data.List.Ordered

primes :: Integer -> [Integer]
primes m = 2 : sieve [3,5..m]
    where
        sieve [] = []
        sieve (p:xs) = p : sieve (minus xs [p*p, p*p+2*p..m])

main = do
    putStrLn "Enter n: "  
    input <- getLine
    putStrLn $ "# of primes: " ++ (show . length . primes $ read input)