Programming Praxis: The Sum of Two Integers

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:

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

In thinking about the problem a little bit I came up with this subtraction approach. My first approach was to use addition and add every item in the array against all the other items. But this method didn’t sit well with me. After a little bike ride I came up with the code you see above.

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:

  1. sumCheck total (x:xs) ys =
  2. let diff = total - x
  3. in if diff `elem` ys
  4. then Just (x, diff)
  5. else sumCheck total xs ys

And Adityz Siram contributed his version. Which is basically the first algorithm that I came up with and wanted to improve upon. His code is here:
  1. sums i as bs = [(x,y) | x <- as, y <- bs, x + y == i]

Finally, Gary Klindt took all of our code snippets, used some performance analysis tools inside GHC and came up with some run times that are (hopefully) more accurate than running time on an application. Here are those stats:
print $ sumCheck 500 [1..1000] [1..1000]
sumCheck1: 58,648
sumCheck2: 58,484
sumCheck3: 70,016

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.

Git Pre-Commit Python Syntax

All of us programmers have made this mistake before: we’ve submitted code that we thought was correct only to have it fail during compilation because of a simple syntax error. Just between you and me (and the rest of the interwebs), I did this last week. Then I thought to myself that it would be good to come up with a tool to help ensure it didn’t happen again. I’m proud to say that on the Git front, I have fixed my problem.

Enter Git Hooks, a way to add scripts to various parts of the Git workflow. Using what is called the pre-commit hook, I was able to write up a quick bash script that goes through all the changed files in Git staging area, check if they are Python files (based on the .py file extension), and then run those Python files through Pylint to look for various errors, including syntax and type errors.

So here is my git hook:

  1. #!/bin/bash
  3. files_modified=`git diff-index --name-only HEAD`
  5. for f in $files_modified; do
  6. if [[ $f == *.py ]]; then
  7. pylint -E $f
  8. if [ $? != 0 ]; then
  9. echo "Code fails pylint check."
  10. exit 1
  11. fi
  12. fi
  13. done
  14. exit

Feel free to copy this and modify it for your own needs. My gift to you; no charge. But an occasional “Thank you Bryce” email is always nice. I also accept lavish gifts of cash or ThinkGeek merchandise.

One quick thing before I let you get back to your busy lives. If you have an older version of Pylint than 0.24, the “-E” flag might need to be changed to “-e”.

Two Year Anniversary

Even though the actual anniversary was a little over two months ago, I see no reason not to talk about it and do some celebrating. I am absolutely amazed by how many people viewed my blog this past year. Below I've included the numbers for both this past year and the year before, for comparison’s sake. You should go and check those out. Don't worry, I'll wait.

Done? Good. I am really excited about these numbers. You might have noticed that my readership multiplied by almost 10 in one year. It's especially cool to see that over 20% of my readers are returning visitors.

I'm also really excited for this year, as I have a few ideas that I can't wait to turn into posts. Look for posts discussing Git pre-commit hooks, applying formal logic to practical programming, and more effective methods of Python error checking. Good things are coming.

Most Popular Posts For Last Year:
pxe-network boot virtualbox -pt 2 : Much like last year, I'm really surprised that this post made it into the top five. Mostly because I just appended some things that the original author didn't include. I guess a lot of people are still trying to figure this problem out.

Project Euler : Problem 5 : Sixteen comments. The coolest thing regarding this post was learning about the lowest common multiple math function.

Project Euler : Problem 4: THIRTY-SIX comments! I really have nothing more to say to that. Alright, I lied. I will also say the comment from Gary Campbell with the very efficient operations for getting a sum of a list was a real winner.

Project Euler : Problem 6: I believe this is the first time that agf (as he/she comments here) started posting comments on my blog. Luckily for me he/she hasn't stopped.

Using curl and a user agent string for web scraping: I guess webscraping is a hot topic in this day and age. I'm a little surprised by this, but am happy to be able to provide some help for people trying to figure it out.

Getting the comment from Dirkjan Ochtman , the maintainer of the couchdb-python project, was particularly cool. It really gave me a sense of being connected to a project, lead me to hang out on the mailing list for the better part of a year, and even helped out with trouble shooting a bug.

It was so awesome seeing all of the Project Euler answers readers posted in different languages. Thanks for sharing everyone! It’s interesting to me that I get more comments and discussion interaction from readers for getting a wrong answer than getting the right one. Does anyone have any ideas of why that might be?

Things learned:
I got a wild hair to change hosting providers. Though it was a hellish process, I learned a lot. Next time I switch, (if I ever do again) those lessons will make it a lot easier.

People really seemed to like seeing the Project Euler stuff in multiple languages. I think that readers also enjoyed seeing the performance numbers for the languages as well.

I've never forgotten that I started this blog as a bit of a lark, and it's just awesome to see that other people are starting to check it out and enjoy it as much as I do. Happy Birthday

The Devil is in the Details, part 2

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:

  1. chain :: Integer[Integer]
  2. chain 1 = [1]
  3. chain n
  4. | even n = n : chain ( n ` div` 2)
  5. | 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:

  1. ghci > chain 10
  2. [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:

  1. ghci> chain (-10)
  2. [-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:

  1. chain :: Integer -> [Integer]
  2. chain' 1 = [1]
  3. chain' n
  4. | n <= 0 = []
  5. | even n = n : chain' (n `div` 2)
  6. | 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.

Syndicate content