Programming Praxis

99 bottles

It’s been a while since I put up one of these simple code posts. Let me fix that. :P

Quiet a while ago, this code needed to have the dust blown off of it. Programming Praxis had its readers program out the song for “Nintey-Nine Bottles of Beer on the Wall".

Here is my version of it:

  1. #!/usr/bin/env python
  2.  
  3. from __future__ import print_function
  4.  
  5. def output(in_int):
  6. if in_int != 1:
  7. return "%d bottles of beer on the wall, %d bottles of beer." \
  8. "You take one down, pass it around, %d bottles of beer" \
  9. "on the wall." % (in_int,in_int, in_int - 1)
  10. else:
  11. return "%d bottle of beer on the wall, %d bottle of beer." \
  12. "You take one down, pass it around, %d bottles of beer" \
  13. "on the wall." % (in_int,in_int, in_int - 1)
  14.  
  15. if __name__ == "__main__":
  16. [ print(output(x)) for x in reversed(xrange(1,99)) ]

That’s all there is to it really. The only enlightening thing about this I can say is that this algorithm reminds me a lot of my Code to lyrics post I wrote a little over a year ago. It’s amazing how simple songs are when they’re broken down to their basic elements. Anyone feel like setting up an “automatic song generation” business with me?

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
  3.  
  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.

Programming Praxis – Two Kaprekar Exercises

Sorry I haven't written in a while. Been rather busy with life recently. I'm still planning on continuing my Tweet Dump series, and I will post that up soon. One of the reasons for the delay is because I'm learning the Colemak keyboard layout has slowed down my typing quite a lot this week.

Anyway, yesterday's Programming Praxis question goes,
For today’s exercise we return to the world of recreational mathematics with two exercises due to the Indian mathematician Dattaraya Ramchandra Kaprekar. First we compute Kaprekar chains:

1. Choose any four-digit number, with at least two different digits. Leading zeros are permitted.

2. Arrange the digits into two numbers, one with the digits sorted into ascending order, the other with the digits sorted into descending order.

3. Subtract the smaller number from the larger number.

4. Repeat until the number is 6174. At that point, the process will cycle with 7641 − 1467 = 6174.

For instance, starting with 2011, the chain is 2110 − 112 = 1998, 9981 − 1899 = 8082, 8820 − 288 = 8532, and 8532 − 2358 = 6174.

The second exercise determines if a number is a Kaprekar number, defined as an n-digit number such that, when it is squared, the sum of the first n or n−1 digits and the last n digits is the original number. For instance, 703 is a Kaprekar number because 7032 = 494209 and 494 + 209 = 703.

So here is the code I wrote and submitted to the comments section. I will happily admit (like I did in my comment) that my isKaprekar function is a modified version of one I saw in the comments here as it was cleaner than my first version and I wanted to try out the "int(s[:-sz] or 0)" expression)

  1. #!/usr/bin/python3
  2.  
  3. import itertools
  4.  
  5. def isKaprekar(number):
  6. square = str(number ** 2)
  7. numlen = len(str(number))
  8. return number == int(square[:-numlen] or 0) + int(square[-numlen:])
  9.  
  10. def keprekar_chain(number):
  11. retlist = [number]
  12. if len(set(str(number))) > 2:
  13. while retlist[-1] != 6174:
  14. pers = [int(''.join(x)) for x in
  15. itertools.permutations(str(retlist[-1]))]
  16. retlist.append(max(pers) - min(pers))
  17. return retlist
  18. else:
  19. return []
  20.  
  21.  
  22. if __name__ == "__main__":
  23. print('Keprekar numbers from 1 to 1000:')
  24. print(*[x for x in range(1,1001) if isKaprekar(x)])
  25.  
  26. print('Longest chain between 1000 and 9999')
  27. kep_list = []
  28. for x in range(1000,10000):
  29. tlist = keprekar_chain(x)
  30. kep_list.append((len(tlist), tlist))
  31.  
  32. print(sorted(kep_list, key= lambda x: x[0], reverse=True)[0])

That's all for now; more to show up once I can type at normal speeds again.

If you made it this far down into the article, hopefully you liked it enough to share it with your friends. Thanks if you do, I appreciate it.

Bookmark and Share

Syndicate content