Add a dash of color!

I have experienced another one of those events that every man experiences on his journey through marriage.  That moment when your wife pulls you close, looks deep in your eyes, and says “we should paint a wall”!

I present to you said wall:

IMG_2476Now I admit, it isn’t much to look at, but it has served our house quite well over the last eight years.  In honor of its years of faithful service, we decided to splash it blue.  In order to only splash the desired parts of it blue, we first had to tape it:

IMG_2489IMG_2488

Taping this out turned out to be a fairly major job, and Cari did a great job as she taped most of it.  Now the moment we have all been waiting for, the first new paint lands on the wall:

IMG_2491Now just a dab more here and there and we get:

IMG_2493Let it dry a bit and suddenly poor little white wall has blue….ness.

IMG_2538Wives; turning houses into homes one wall at a time!

From Google Interviews to Rooks Paths

The internet is a great for people with stream-of-consciousness thinking.  Today that is me.

Over the last few days I have been playing a lot with Mongodb.  Mongodb is one of those products that looks pretty amazing, and having played with it a bit I think it is pretty amazing if applied to the right problem.

One of the things I have been trying to do more when I find a cool project is learn about the people behind the technologies.  In the case of Mongodb, one of the developers who wrote the book on Mongodb is Kristina Chodorow.  I Googled her name and discovered her blog (cutely named “snail in a turtleneck“).

Turns out our Mongodb hero has just accepted a job with Google!  Awesome for her.  One of the posts she did that caught my eye was The Google Interviews post.  Being on the hiring team for Schweitzer Engineering Laboratories I am often looking for good interview questions.  Google, Microsoft, and the other “big companies” are know for having hard interview questions, so I was excited to see the questions they asked her.

The tree-like thing wasn’t too hard.  I could program up a recursive solution for that in 15 minutes I think.  It would be harder for me to do it iteratively, just because I haven’t done that in a bit.  The power series question is interesting, and the part I haven’t figured out yet is how to avoid continual calls to next() in the second series as I foil out that expressions, but I will figure it out.  Reversing the bytes in an int isn’t too bad nor is the subsets one.  atoi is also straightforward (and maybe I will do another post on my solution to it).  The longest substring of two distinct characters seemed easy though I completely messed it up when I tried to write it because my solution didn’t handle skipping intermediate letters correctly (yet another post?).

The problem that definitely caught my eye was:

Suppose you are on a Cartesian coordinate system. Find all paths from (0,0) to (m,n) that only go through each point once. For example, if you were given m=2, n=2, you’d have the following:

paths

This would be one possible path:

paths2

Return the number of possible paths. Then extend for negative coordinates.

All credit goes to http://www.kchodorow.com/blog/2013/03/04/the-google-interviews/ for this, as I am copying it, and the images, verbatim from her.

This problem seemed really hard.  I figured out in my head that for a 1 by 1 there were 2 solutions, and for a 1 x 2 I figured there were 4 solutions.  I couldn’t figure out what the solution for a 2 x 2 was.  I was guessing around 10.  Turns out it is 12.

I kept thinking about this issue and how hard the problem seemed, but most likely I was just missing something.  I decided to try to code up a solution to the problem, and it was an adventure.  I published my script at my github account.  Its pretty cool if I do say so myself as it actual finds the number of solutions and shows you them.  Here is an example:

python path_finder.py -s 2 2
0  1  2
|        
3  4  5
|        
6__7__8

0  1  2
|        
3  4__5
|  |  |  
6__7  8

0  1__2
|  |  |  
3  4  5
|  |  |  
6__7  8

0  1  2
|        
3__4  5
   |     
6  7__8

0  1  2
|        
3__4__5
      |  
6  7  8

0  1__2
|  |  |  
3__4  5
      |  
6  7  8

0__1  2
   |     
3  4  5
   |     
6  7__8

0__1  2
   |     
3  4__5
      |  
6  7  8

0__1  2
   |     
3__4  5
|        
6__7__8

0__1__2
      |  
3  4  5
      |  
6  7  8

0__1__2
      |  
3  4__5
   |     
6  7__8

0__1__2
      |  
3__4__5
|        
6__7__8

Found: 12 solutions

This is cool, but I can’t really see a pattern as to how to do this correctly yet in a close-form solution.  I ran the script with various inputs and recorded the outputs:

For a 2×2 version, there are 12 solutions.
For a 2×3 version, there are 38 solutions.
For a 2×4 version, there are 125 solutions.
For a 2×5 version, there are 414 solutions.
For a 2×6 version, there are 1369 solutions.

This, while highly interesting, wasn’t helping me find the close form solution I was looking for.  I turned to Google and search for those numbers.  I found a few interesting pages including http://mathworld.wolfram.com/Self-AvoidingWalk.html and http://www.iwriteiam.nl/Crook_path.html that talked about what they refer to as “The rook path problem”.

Unfortunate that I had to write a script to generate the numbers to give me a search criteria that actually returned something related to this problem, but life is always interesting.

Wolfram does have some interesting generating functions and recurrence relations for this family of problem.

In summary, I still don’t know what Kristina said in response to the Cartesian Coordinate problem, and I don’t know what I would have said, but I am pretty sure I wouldn’t have gotten it right since I still don’t know an easy way I can find the number of possible paths knowing m and n :-(.

 

New Flash Equipment

I am very excited that I picked up some new flash equipment.

I hope to post more about it later.  For now, checkout the new images:

So much to learn, but so much potential!

Time Lapse Videos in Linux

I love watching time lapse videos.  Some time ago I discovered http://timescapes.org and enjoy watching some of the amazing work they have done.  It has even motivated me to do some experimenting with making my own time lapse videos.

So far the best information I have found on creating time lapse videos in linux are http://ubuntuforums.org/showthread.php?t=2022316 and http://ultrawide.wordpress.com/2009/01/27/timelapse-photography-on-linux/.  CyberAngel’s post on ubuntuforums is really awesome because he was kind enough to release his deflickering script.

So, in way of testing everything, I setup my tripod at the edge of our office, set my camera into manual mode, setup my intervalometer, and took 512 JPG images.

I copied these images off my CF card onto my computer and decided I wanted to encode them to an H.264 video.  This lead me to following the instructions at https://ffmpeg.org/trac/ffmpeg/wiki/UbuntuCompilationGuide so that I could get an H.264 compatible ffmpeg.

After I had my ffmpeg working, I following CyberAngel’s advice and ran:

cd source_folder_of_pictures
mkdir resized
mogrify -path resized -resize 800x533 *.jpg
cd resized

I also ran CyberAngel’s script (which I have mirrored here) to deflicker the images.

Unfortunately I didn’t have good luck with the mencoder command, so I ended up running:

ffmpeg -start_number 1055 -start_number_range 512 -f image2 -i IMG_%d.JPG -vcodec libx264 -vf "scale=iw:trunc(ih/2)*2" -r 30 video.avi

instead.  My jpeg images started at IMG_1055.JPG and ran up to IMG_1568.JPG, hence the start_number and start_number_range.  If I didn’t include the scale option to vf I got an irritating error “height not divisible by 2 (800×533)”.

Without further ado, here is the result:

Not too bad.  Now I just need to snap some pictures of something more useful.  Maybe if this weekend is nice I will get to make time lapse videos of the sky instead of the dog!