Project euler – again

I am back working on Project Euler again.  It has been a great long while, maybe 4 or 5 years, not sure, since I started on it originally, using ruby.  Now I am using a mixture, starting for Python for a bit, and possibly switching back to ruby.  I say that after solving this last problem (#4) and then going thru some of the other folks solutions, the most elegant usually are the ruby ones, in my humble opinion. 

There are of course smaller, or rather more concise, ones but they are too cryptic.  Solutions is in statistical languages such as J or K are frightfully illegible.  I have to share, just for kicks.  First, the problem was to find the largest numeric palindrome that is the product of two 3-digit numbers.  Similar to 9009 being the largest that is the product of two 2-digit numbers, 99 and 91.  So just for giggles, here are a couple of super concise (and un-readable INHO) solutions:

1. This is in J (http://www.jsoftware.com)

   1: >([:{: ]#~ (=|.&.>)) <@":"0 /:~(0:-.~[:,>:/**/)~(i.100)-.~i.1000

and

2. This one is in K (http://www.kx.com/developers/documentationkdb.php)

   1: |/m@&{x~|x}'10_vs'm:*/',/n,/::n:100+!900

Please realize that I am in awe of the guys that posted these solutions and maybe someday I will be able to learn a language such as one of these, but for now…

I am going to stick to C# and Javascript, and Ruby and Python.  They are sufficient to accomplish the tasks I perform on a daily basis at work.  I am just learning Python again and also planning to brush up on Ruby.  I spent a year or so messing with ruby and ruby on rails, but only at home in my spare time so naturally I didn’t get super far.

So, to the issue at hand.  How to find the largest numeric palindrome that is a product of two 3-digit numbers.  And, for me, more importantly how do I do this in Python using Test-Driven-Development, only using VIM as my development environment.  Pow!  Throw that one in there at the last minute.  Ha, Ha!  Vim super rocks and I am learning more and more about how to mack it out and make it easier to use.  Death to my mouse!

Vim setup

I decide to use VIM because I have been really wanting an excuse to get better with it.  I use it at work sometimes but when I am in a hurry I end up going back to Notepad++ or SublimeText (which is super nice in its own right, closest thing you can find to Textmate for windows).  Anyways I figured this would be a good chance to spend some time with VIM.  I am using gVIM by the way on Windows 7 and I have python 2.7 installed as well and in my PATH variable. 

I did some research on VIM and found out that I needed to add a ~_vimrc file with some settings in it.  Over the next day or two I slowly acquired a pretty good selection of customizations for VIM that make it much nicer to use.  Things like syntax highlighting and default font and color scheme presets.  One of the coolest things I figured out from this wonderful article, Turning VIM into a modern Python IDE, which gave me numerous tips, was to use the vertical screen split to show two buffers (files being edited) at once.  This allowed me to work on my class in on one side and my unit tests on the other.  Like so:

vim_split_screen

Once I had this setup I was rolling pretty good, really helped with the TDD workflow of:

  1. Write a test
  2. See the test fail
  3. Refactor code to pass test

This was also aided by the VIM settings for executing my scripts using the python command and seeing the output in a new command window.  The following additions to my _vimrc file allow me to simply hit ‘F5’ to execute the code in the current buffer.  And, conveniently, the *.py filter ensures that it is only set up to do so for Python files.  These autocmd lines take advantage of the fact that you can execute any shell command from the VIM command line by prepending it with the ‘!’ character.  The last setting maps the ‘F5’ key to the command output of “python “ + the current filename (represented by the ‘%’ output placeholder).  Super convenient.

vim_settings

The settings file allowed me to correct the weird backspace key behavior that VIM was displaying.  I couldn’t be more pleased, VIM is seemingly endlessly configurable.

The Problem

The goal was to find the correct answer to the 4th problem on Project Euler which is to find the largest numeric palindrome that is a product of two 3-digit numbers.  After a bit of thought I decided to start at 999 and work down with any loop I would use, that way I would get to the solution faster than if I started at 100 and went up.  But the very first thing I needed to do was to write a test.  So I went for an isPalindrome method test, as I knew I would need a test for my products as I iterated through the numbers.  

I turns out that there are numerous ways to solve the problem, of course, including using pen and paper and some algebra.  I must admit that it never occurred to me to use algebra to solve the problem.  Brute force was immediately where my thoughts went and where they stayed.  I guess years of coding have taught me that using the simplest and most direct approach is usually the best.  There were many interesting solutions posted in the forum for the problem though, and I encourage everyone to check out the many different bits of code there, but only after you solve the problem yourself.

TDD

Before I could write a test I had to figure out exactly how unit testing worked with python, so I did some research and came up with what I would guess is the most direct solution.  There is an included unit test module called, unittest and so it was there I began.  No configuration necessary, only the use of the very sweet vertical split screen in VIM, so I could look at my tests and my code as I wrote them both.

My first code that I wrote was a class that derived from the base unittest.TestCase class and I named it TestProblem4Solution.  I then did a little setup, a valid palindrome value and an invalid palindrome value that I figured I would need in my tests of an isPalindrome method.  Then straight to my first test, which was:

   1: def test_isPalindrome_ReturnsFalse(self):

   2:        result = self.cut.isNumericPalindrome(self.invalid_palindrome)

   3:        self.assertFalse(result)

Naturally this test failed when I ran it, so I had some code to write in my Problem4Solution class, which I needed to create as well.  Here is a shot of what I ended up with for making the first test pass:

problem4_firstmethod

This was enough to make my second test pass as well, test_isPalindrome_ReturnsTrue which is just a positive result test to go with the first one which tested the negative result.

Moving on to some product work, I knew I would want to test products that were produced from a loop, so I wrote a test called test_highestPalindromeProduct_ReturnsCorrect that would test a method that would take a starting number and multiply it by a set of numbers beginning with itself and stepping down by –1 until a palindrome product was found.  Of course there was no such method so the test failed and I was back to my solution class to fix the problem.  The resulting method, after a few tweaks and quick trips to the python online docs came out looking like this:

problem4_secondmethod

I then added a test for a solve method that I figured would use the two helper methods and find my solution.  But, before I finished that I realized that I might want to solve this problem for multiple length numbers.  The sample given in the problem was for tow 2-digit numbers and the challenge was for two 3-digit numbers so right off I needed to handle multiple length start numbers (I was using the two 2-digit as test values because I already had the correct answer).  Therefore I stepped back and wrote a test for a buildStartNumber method that would take a length up to 5 and return the highest number of that length.  I wanted to get back 999 for an input of 3.  Here is that test:

   1: def test_buildStartNumber_ReturnsCorrectNumber(self):

   2:         result = self.cut.buildStartNumber(3)

   3:         self.assertEqual(self.expectedStartNumber, result)

Again, fairly straight forward, I am just testing a result produced by calling the method.  The expected value is hanging off of the class instance (self.expectedStartNumber) and is 999 which is what I wanted back.  The assertEqual test statement just checks that value against the actual result.

The method to make this test pass was the simplest one in the solution, but only because I did some Googling first to learn some more about what python is capable of…

   1: def buildStartNumber(self, length):

   2:        start = ''.join("9" for x in range(length))

   3:        return int(start)

You can see that I am using the join function to join the “9” string together for x times in a range of the provided length. The range function is very handy.

That brought me to the solve method which would get me my answer.  I first wrote a test that used the known example solution for two 2-digit numbers which is 99 * 91 = 9009.  These values ensured that my solve method produced correct results.  Sort of!  I did get an incorrect answer the first time because I had assumed that if I counted down instead of up the first solution I came to would be the correct one but it wasn’t.  I had to store the results and continue on down until I found them all and then keep only the highest one.  Counting down from 999 and looking for palindrome products you come first to 995 * 583 which is 580085, a palindrome but not the highest palindrome.  You have to keep going to get to 993 * 913 which is 906609 and the correct answer.  Now, if I had limited my attempts with a bottom end of say 900 then I would have come to the correct answer first, but I didn’t.  I let it go all the way down to 100 until it found a result.  Oh well, live and learn.

Back to the TDD, the next test looked like this:

   1: def test_solve_ReturnsCorrectValue(self):

   2:         result = self.cut.solve(2)

   3:         self.assertEqual(self.solution, result)

Another simple test, where the expected value of self.solution (defined in the test setup method) is an array of [99,91,9009] which is the correct answer for two 2-digit numbers, including the product itself.  I knew I would want my solve method to provide me all three values for a complete answer, even though technically all I needed was the palindrome itself to submit to the answer page at project euler.

And the code that I added to make the test pass:

problem4_solvemethod

This completed the problem.  I submitted the solution, which thanks to my handy ‘F5’ key mapping was just a click away after adding a small main() method to the class that would print out the result of the solve method to the screen.  The final output looked like this:

problem4_finaloutput

And the answer you can see printed out as [993, 913, 906609], nice and neat.  The final code is actually shown at the beginning of the post in the screen shot of VIM with the vertical split.  You can see both the Problem4Solution class on the left and the TestProblem4Solution class on the right.  If you have any questions just post a comment!

Console2 Tabs for GitBash, Cygwin, Powershell & More

I recently rebuilt my work machine, with a new SSD.  But that meant I had to setup Console2 again…

I recently rebuilt my work machine.  I have had my Dell Precision M4600 for almost two years now and it has served me well.  I started with 8gb of RAM and have upgraded to 16gb.  Despite the increase in ram though I had started to notice a slow down in performance, partly due to my frequent use of Visual Studio 2012 and the new Office 365 suite.  These newer apps use a lot of memory, a whole lot.  VS 2012 can easily use a gb of ram per instance if left open too long.  So I decided to ask for a hard drive upgrade and lucky me I received approval.  I promptly ordered a 256 gb Sandisk Ultra Plus SSD and eagerly awaited its arrival.

The drive arrived and aside from a slight snafu that cost me a 20 dollar part from ebay (I broke off the HD cover plate when removing the factory HD) the installation was fairly simple.  I cloned an M4600 Windows 7 x64 image our IT Manager gave me and was up and running in a couple of hours.  I did have to wait until the next morning to re-join the domain, but then I was off and running.  And I mean running!  The new drive is wicked fast.

I installed VS 2012 in about an hour (instead of the three it took when I first started) as well as Office 365 and a host of smaller utilities.  A small note about that, I cannot recommend enough the Chocolatey package manager for windows.  It was the first utility I installed and then I used it to install almost everything else, including things like:

  • 7zip
  • AutoHotKey
  • BeyondCompare 3
  • Calibre
  • Console2
  • DaemonToolsLite
  • Dropbox
  • Filezilla
  • Git
  • iTunes
  • GVim
  • Notepad++
  • Paint.Net
  • Python
  • SharpKeys  (I use this to map keys for my Apple Keyboard)
  • uTorrent
  • vlc

To get a list of all of the packages you have installed use the command:

cver all -localonly
I was continually amazed at how easy it was.  I would be working and realize, for instance, that I needed to add some annotations to a wireframe for some documentation for my latest feature task, but I hadn’t installed paint.net yet.  So, I hit Win-Key, then type in Console and hit enter.  Then at the command line, I tried:
cinst paint.net
And it just worked.  It would search the packages find it and install it.  Bam!  Then I could hit Win-Key again and type in paint and select Paint.Net and hit enter and be working.  Super cool and super easy.  I really can’t say how much time it saved me and also how much space it saved me because I didn’t have to go out and search for installers and download them and forget to delete them when I was done.  Thanks to Chocolatey my downloads directory is practically empty.

Console2 Setup

A new machine meant I had to do some reconfiguring of my utilities, especially the ones I use the most, like Console2, or just Console now.  I have previously published an article that contained my Console2 Setup and it has been quite a popular article, my most popular one on the site in fact.  And when I had to figure out how to do it all again I  thought a new article would be a good idea.  Especially because I have added even more tabs to this setup.
Console2 Tabs screenshotAs you can see I have the following tabs available:
  • Windows Cmd Prompt
  • Visual Studio Cmd Prompt
  • Git Bash
  • Cygwin
  • Powershell

I was able to salvage some of my settings from my old hard drive by locating and copying the settings file from Console2 which for me was located in \AppData\Roaming\Console\console.xml but on my new build I am using a portable install of Console so that my settings file is in the Console2 directory.

Details

Here are the specifics.  I am assuming that you know enough about Console to open the settings and add a new tab and get to this screen:

Console2 Settings Screenshot
And here is the goodies!  A detailed list of the settings for each tab that work for me.  I add that caveat because due to the differences in versions of Windows and install locations I cannot swear that my settings will work for you, but you should be able to use my settings to figure out how to make yours work…

Visual Studio Cmd Prompt

VS Cmd Prompt in Console 2

  1. Title:  VS Cmd
  2. Icon:  C:\Users\jgilliland\bin\Console2\vscommand.ico    (from Scott H.)
  3. Shell: %comspec% /k “”C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\vcvarsall.bat”” x86
  4. Startup dir:
Git Bash Shell

Git Bash in Console2 Screenshot

  1. Title:  Git Bash
  2. Icon:  C:\Program Files (x86)\Git\etc\git.ico
  3. Shell:  C:\Program Files (x86)\Git\bin\sh.exe –login –i
  4. Startup dir:  %HOMEDRIVE%%HOMEPATH%
Cygwin Shell

Cygwin in Console2 screenshot

  1. Title:  Cygwin
  2. Icon:  C:\users\jgilliland\bin\Cygwin\Cygwin.ico
  3. Shell:  C:\users\jgilliland\bin\Cygwin\Cygwin.bat
  4. Startup dir: 
Powershell

Powershell in Console2 screenshot

  1. Title:  Powershell
  2. Icon:  C:\Users\jgilliland\bin\Console2\vspowershell.ico  (from Scott H.)
  3. Shell: %SystemRoot%\system32\WindowsPowerShell\v1.0\powershell.exe
  4. Startup dir:

Conclusion

So there you have it!  My new drive with all of my utilities, mostly portable installs this time, so that next time they can just be moved with me.  In fact, here is a screenshot of my username/bin directory where all of my portable installs are:

My bin directory with portable installs

In conclusion I am super stoked about my new ssd and I cannot recommend using Chocolatey enough for your windows package management needs.  And of course you now have all of the details of my Console2 setup.  Enjoy!