If you haven’t figured it out by now, I enjoy solving problems. And over the course of the last year or two, I’ve learned that interview questions make for great problems to work on. Actual interview problems are nice because they are usually quick, but have a quirk or two in there that makes them challenging, unlike simple questions like the Fizz Buzz problem that just checks if you have the most basic coding skills. (Has anyone actually been asked that question in an interview?)

The most recent problem I got to sink my teeth into (found it on a recruiting site, but not going to share where I got it; wouldn’t be fair to the company posting the problem) is for finding pangrams in sentences. If you don’t know what a pangram is Wikipedia defines them as, “a sentence using every letter of the alphabet at least once.” Yeah, I didn’t know what they were either until I started programming this little puzzle. Here is the code:

module Main (main) where
 
import System (getArgs)
import qualified Data.Set as S
import qualified Data.Text as T
import qualified Data.Text.IO as TI (readFile)
 
buildList :: FilePath -> IO [T.Text]
buildList filename = TI.readFile filename >>=
    return . map (T.toLower . T.filter (/=' ')) . T.lines 
 
compareAndPrint :: S.Set Char -> String
compareAndPrint sset = if S.null result
                       then "NULL"
                       else S.toList result
  where result = S.difference (S.fromList ['a'..'z']) sset
 
main = do
  args <- getArgs
  sentences <- buildList $ head args
  mapM_  (putStrLn . compareAndPrint) $ map( S.fromList . T.unpack) sentences 

I came up with the solution pretty quickly by using Sets. Having a set of the alphabet and finding the difference of the letters used in the sentence makes the problem almost trivial. The hard part for me was figuring out how to filter out the spaces and change all characters to lower case in the buildList function. I eventually figured it out, but it took some head against wall action to get it right.

This is going to be my last post for this year. I would like to wish you all Happy Holidays and a Happy New Year. Thank for reading and see you again in 2012. I would also like to thank everyone from planet.haskell.org who decided to read this. Welcome!

A couple of months ago the Programming Praxis website put up a challenge to find a sum inside an array of integers (the direct wording of the challenge can be found here) and since I’ve come up with my own solution, this little challenge has provided me with a lot of feedback.

Just to get some of the geeky stuff out of the way, here is the code I wrote for the problem:

import Data.List
import Data.Maybe
 
sumCheck :: Int -> [Int] -> [Int] -> Maybe (Int, Int)
sumCheck _ [] _ = Nothing
sumCheck total (x:xs) ys = if total' == Nothing 
                                then sumCheck total xs ys
                                else return (x, (ys !! ( fromJust total')))
                           where total' = (total - x) `elemIndex` ys 

After I wrote it, I submitted my code to the Haskell-beginners email list asking for critiques and possible enhancements. Arlen Cuss contributed a slight improvement of my code:

sumCheck total (x:xs) ys =
let diff = total - x
               in  if diff `elem` ys
                              then Just (x, diff)
                              else sumCheck total xs ys

sums i as bs = [(x,y) | x <- as, y <- bs, x + y == i]

print $ sumCheck 5000 [1..10000] [1..10000]
sumCheck1: 238,668
sumCheck2: 238,504
sumCheck3: 358,016
(unit: byte)

Out of the three code snippets, my function was in the middle, speed-wise. But I think that it’s also really nice to see how much better it is than the regular addition method. It’s also nice to see how the little change made to my code can improve the overall speed of the function.

At the end of the day I take a little bit of pride in myself for coming up with an improved algorithm for this task on my own. I know that on a hardware level, subtraction takes more time than addition. But I get the improvements I get because I reduce the number of additions and comparisons I have to make in order for the function to be complete. I also estimate the worst case speed for my algorithm to be O(n), which isn’t too shabby.

When I started learning Haskell, one of the things I read on the internet was how the people who programmed it were helpful to one another. I was skeptical when I first read that, but I have to say that all of my doubt has been removed. And it is interactions like this that make me glad to participate in a community as helpful as this one.

In the last blog post I made with this title, I told a little story on how I helped a learning Haskell programmer see why his version of the code wasn't as complete as the example given. I also thought that this series wouldn't be having a second part to it, but it looks like I was wrong.

I've recently been given a copy of “Learn You a Haskell For Great Good” to write up a review for it. I've been trying to go through that book as fast and thoroughly as I can because I really want to learn the material and because I will be able to give a better review if I actually complete the book. Yeah, big shocker there, I know.

Just a quick personal note before I continue. I'm not trying to point out these short coming in code that I see to please my ego. I'm doing this because I see a pattern that I don't think is correct and I don't only want to prevent this problem from happening within my own code, but also to bring the idea to public forefront so that other people can see what is going on to and (hopefully) learn from it.

In “Learn You a Haskell”, more specifically Chapter 5 – High Order Functions, the book walks someone through how to construct a Collatz chain. The code in the book is:

chain :: Integer → [Integer]
chain 1 = [1]
chain n
    | even n = n : chain ( n ` div` 2)
    | odd n = n : chain ( n * 3 + 1)

and as an example from the book as well, when you run the above code you get this as a result:

ghci > chain 10
[10,5,16,8,4,2,1]

This is the right answer, but much like the code in the last blog post, what happens if you give it a negative argument, let's say -10:

ghci> chain (-10)
[-10,-5,-14,-7,-20,-10,-5,-14,-7,-20,-10,...] #(I'm sure you can see the pattern at this point).

So I propose to make a small change to fix this problem. Here is my version of chain:

chain :: Integer -> [Integer]
chain' 1 = [1]
chain' n
     | n <= 0 = []
     | even n = n : chain' (n `div` 2)
     | odd n = n : chain' ( n * 3 + 1)

At the end of the day, I'm just making the case that when I, or anyone really, programs something up, a quick thought should be given towards what type of input verification should be done before the function/application/whatever runs so that it runs cleanly and correctly. Ok, time to get off my soap box and start looking for these same holes on the programs I've written.

Thank you for your patience as you all (I'm sure) anxiously await my next posting.

Not only has it been a really long time since I posted something technical, it's also been a really long time since I posted a Project Euler solution. On that note, let's go over the challenge:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.


Seems simple enough doesn't it? Let's find out. For Python the code is:

#!/usr/bin/python
"""
Python based code solution to problem 10 of project euler.
"""
import math
 
def is_prime(divided):
  divisor = 3
  sqrt_divided = int(math.sqrt(divided))
  while divisor <= sqrt_divided:
    if divided % divisor == 0:
      return False
 
    divisor += 2
 
  return True
 
if __name__ == "__main__":
  print sum([2] + [x for x in xrange(3,2000000+1, +2) if is_prime(x)])

And for Haskell the code looks like:

module Main where
 
prime_wrapper:: Int -> [Int]
prime_wrapper divided = prime 3 divided (round . sqrt. fromIntegral $ divided)
 
prime:: Int -> Int -> Int -> [Int]
prime divisor divided sqrt_divided
  | divisor > sqrt_divided = [divided]
  | mod divided divisor == 0 = []
  | otherwise = next_prime
  where next_prime = prime (divisor + 2) divided sqrt_divided
 
main :: IO ()
main = print $ sum primes 
  where primes = 2 : [ x | x <- [3,5..2000000],  prime_wrapper x /= [] ]

I will be the first to admit that this problem is a little on the easy side. Mostly because you can reuse the code you created for problems 3 and 7, or at least I did. :)

Even though you and I know that Haskell will execute this code faster than Python, I feel I still need to uphold the tradition of posting my highly inaccurate execution times:

Python: 34.054s
Haskell: 20.690s