The Sum of Even Fibonacci Numbers

A co-worker showed me the following problem last night:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

If you jump too fast to your early CS101 knowledge you might bang out a recursive fibonacci function to get yourself started (using Ruby as an example):

def fib(n)
  return 0 if n==1
  return 1 if n==2
  return fib(n-1)+fib(n-2)
end

But that's not terribly efficient in this problem, where you'll end up calculating and recalculating the fibs all the way up to 4 million.

If you spot that the recursion will just do an absolute number on your stack management and want to get it out of there you can write the function without it:

def fib(n)

  prev = 0
  curr = 1
  (n - 1).times do
    curr, prev = prev+curr, curr
  end
  curr
end


But you're still going to calculate too many numbers and end up with a solution that is O(N^2) because every time you move to position N your function is going to recalculate everything from 1 to N-1.

Instead, don't abstract the function.  Treat it like the formula that it is, and write it in a single loop.  You are going to be calculating your variable N using the N(x) = N(x-1)+N(x-2) formula, until N>4000000.  Along the way, if N is even, add it to your growing sum:

first = 0
second = 1
sum = 0
while (second < 4000000) do
  sum += second if second.even?
  temp = second
  second = first + second
  first = temp
end
puts sum

Did you get 4613732?  You could clean up that code a bit and there's tricks to avoid that temp variable but I want to get to a better solution.  The one above calculates all the Fibonacci numbers less than 4 million, which means it goes through the loop 33 times.

We can do better.  If you look closely at the fibonacci sequence you may spot a pattern in the even numbers.  Did you notice that every 3rd number is the even one?  Which makes sense because once you bring even a single odd number into the pattern it's going to go the same way -- even plus odd equals odd, odd plus odd equals even.  So the Fibonacci sequence goes odd even odd odd even odd odd even odd where each even number is wrapped with odd numbers.

How can we use this?  Well this means if we know that fib(N) is even, we want to jump to fib(N+3) without worrying about the two in the middle.  So instead of looping over them why not just calculate them while we're here?  I'm going to use the sequence 5,8,13,21,34 as an example.  If I'm on 8, I want to calculate 34:

Given fib(x)=8
Given fib(x-1)=5
Calculate fib(x+1) = (8+5)
Calculate fib(x+2) = fib(x+1)+fib(x) = (8+5)+8  = (8*2 + 5) = fib(x)*2 + fib(x-1)
Calculate fib(x+3) = fib(x+2)+fib(x+1) = ((8+5)+8)+(8+5) = (3*8 + 2*5) = fib(x)*3 + fib(x-1)*2

Still with me?  So as long as I have fib(x) and fib(x-1) I can jump to fib(x+3) with some multiplication.

So now I can go through the loop like this:

x1 = 1

x  = 2
sum = 0
while (x < 4000000) do
      sum += x
      n = 3*x+2*x1
      x1 = 2*x+x1
      x = n
end
print "Your total is #{sum}"


Same result, only this time we bounced up to 4 million in just 10 hops.

Again, we could probably make it even more efficient than that by considering the actual cost of each math operation - I added some multiplications but now I'm also no longer testing for even numbers, so maybe it's a wash. I was mostly interested in showing that whole "even numbers every third so only jump by 3s and don't test for even" pattern.

I wanted to document this approach since I haven't seen it yet as one of the standard answers.  Enjoy.

Copy And Paste Between Two Devices

If you're a developer, this has probably happened more than once. You're working on two devices that are physically right next to each other, yes? Maybe, like me, you've got your iPad next to your laptop.  And inevitably you find a link on your laptop that you want on your iPad.  Blah.  What's the fastest way to get it from one to the other?

Sure you could mail it to yourself, or drop it in DropBox, or even maybe type it directly into the secondary device.  All too much bother.

Run an instant messaging program of some sort on both devices (like AIM).  IM the message to an understanding friend.  Now go over to your secondary device and fire up the conversation.  Your message, link included, will be there.  

Totally hacky but it's the fastest way I've yet found!

Array Sampling Without Repeating [Ruby]

I've often come across the problem of random sampling in situations where you don't want repeats.  For instance say you've got a list of the user's MP3 files and you are playing them randomly.  You've just played a song and you choose another random one.  It's easy to say "Don't pick the same one that you just picked."  And with a little work you could pick an N and say, "Don't repeat a song in the last N songs."

But you also don't want to say "Don't repeat any songs until all the songs are played", because if the user's got 500 songs in their library it'll be a long time before they hear their favorite song again.  What you really want is just something that says "Make it less likely to pick this song too too frequently."

So, here's the idea I finally came up with.  Say that you've got an array of files to work with, regardless of what is in them.  In Ruby you can just ask for file  = files.sample to get a random element out of the array.

Now what?  We go and do what we want with file, but now we want to assure that this is less likely to be called in the near future (and, preferably, absolutely guarantee that it is not called within the next N samples).

Start by snipping file out of filenames and moving it to the end of the array:

files <<= files.delete(file)

Try it:


(main)> files=["foo", "bar", "baz", "quux"]
=> ["foo", "bar", "baz", "quux"]
(main)> file = files.sample
=> "bar"
(main)> files <<= files.delete(file)
=> ["foo", "baz", "quux", "bar"]

So what?  The sample method is equally likely to pick any item in the array, right?

What if we tell it not to?  What if we tell it to only sample a portion of the array?

file = files[0..files.size>>2].sample

Here, we're saying to only get samples out of half the array.  So when a sample is chosen and moved to the back, we've established that there's no way this sample can be repeated until at least N/2 samples have been taken.

Depending on your N you might want to do something like N*0.90 or something (if N is a thousand maybe only 100 samples have to go by before it's ok to repeat).  

It's a little trick, but I think it's important.  I've got an app I'm working on that chooses random quotes, placing them on random images.  It bothers me when I know that I've got over 500 quotes in the database, and the user sees a repeated quote after 4 refreshes of the page.  So now they won't, now it'll take hundreds of refreshes before they see a repeat. Truthfully I'll probably switch that over to cap at 100.

RubyMotion : Gems Are Not Being Compiled / Built / Included

I was working on the most basic of apps, really nothing complicated at all, and trying to include BubbleWrap.  But the first time I tried to use anything (in this case, Device.screen.width) I was getting a name error - as if BW was not included.

I had  require 'bubble-wrap' in my Rakefile. I'd done a gem install bubble-wrap.  That wasn't it.  What appeared to be happening was that over in build/iPhoneSimulator-5.1-Development/objs there should have been a /Users/dmorin/.rvm/... directory where my required gems were getting copied, and that directory didn't exist.

I double checked everything, I ran "rake clean", I could not for the life of me make it include that directory.  I even created a brand new empty motion directory and included bubble-wrap in it so that this was literally the single line change I made from default -- and it compiled.  Go figure.

Finally, I found it.  I had been modifying some sample code that I found online, and it was this line:


app.files = Dir.glob(File.join(app.project_dir,'app/lib/**/*.rb'))|

Dir.glob(File.join(app.project_dir, 'app/**/*.rb'))

I'd seen something like that trick before, and it seemed like something I understood - basically saying that you're going to put some common code into a /lib subdirectory, so compile that first in order to make it available to your primary code.

But that's not quite accurate.  I think there was a mistake in the code that I copied, because what this does is to make app.files *only* point the files in your app/ and app/lib directory - completing removing any gems from the filepath.  You can check this with rake config - performing this command on a brand new directory will return all of your gem paths (whether it's .rvm or not), but doing so in the directory where the above line is included in the Rakefile?  Shows all my app/ code, but no gems.

In my case it turns out I don't need that line at all, so I've removed it.  Soon as I did that, my gems were included.  If you do need to manipulate app.files and the way things are included, you'll want to append or otherwise manipulate the existing list, not just replace it with a plain old equals!

Rails MVC vs iOS MVC

If your primary experience with Model View Controller (MVC) has been via Ruby on Rails, and then you switch over to iOS (iPhone / iPad) programming, see that it also supports MVC and think, "Oh, cool, I already know that!"  Not so fast.

I am not expert at either of these technologies, but let me put it in the best terms I can.  In the Rails world, the controller is primarily associated with manipulating the model.  You have a Person object, you have a PersonController.  That PersonController has actions like index (show a list of Person objects), show (a single Person), edit/update, create/save, destroy and so on.  Things that you can do with that object.  Each action, in general, has a view.  To the point where the default behavior of an action called "foo" on the PersonController is to assume that there is a file called foo in the /views/person directory.

In iOS world, each controller handles a single view.  I'm still trying to get my head around it.  I keep thinking of the View as an entirely separate object that I instantiate and "connect" to the controller in some way, such that the controller's only real job is to take in some user input, manipulate some stuff, and then let the next view do its thing.

Not really.  In fact, the controller can go ahead and just instantiate a UIView object and start populating it.  There' a method called viewDidLoad, that gets called when the view is all loaded.  Fair enough.  Where is that method?  Is there a didLoad() method on UIView?  Nope!  It's on the controller.  So it's practically hard coded in the framework that a controller deals with "the view" and you don't get to trick it into managing many views.

I don't yet fully get it.

UPDATE - As I do more googling on stuff like "switch UIView" I'm learning some techniques for how to manage multiple views inside a controller.  It's not quite the same thing as having a specific view associated with a specific action like Rails does, but it's inaccurate to say that a controller can only handle a single view at a time. It's more like, "The controller has a pointer to a view.  You are free to swap out and/or otherwise regenerate that view according to whatever rules you like."  So I don't think I have to have a PeopleIndexController and a PeopleShowController and a PeopleEditController...

Speeding Up the Stanford iPhone / iPad / iOS Development Course

I've known for years that I should learn iOS and Objective-C programming. I've just never found the time and/or patience to do it.  I'm a full time Ruby on Rails developer with a bunch of years of Java before that, so I feel relatively confident in my ability to pick up a new platform/language, but I found that there were a number of key differences between that world and the world of Objective-C that merely picking up a book on the subject and banging on it for a few hours a night wasn't working for me.

What is the greatest resource for learning iOS programming?  Everybody points to the Stanford iPad and iPhone Development Course.  Tens of thousands of people have gone through the course, and most rave about it.   I like the idea, a lot.  My biggest problems with it are two-fold.  First, it's a video long video course - almost 20 hour-long episodes.  I don't have the attention span for that, honestly.  Second and perhaps related to the first, it is impossible for all learners to get the same amount out of a single course.  Someone who has never touched Smalltalk, for example, will take longer to grap the idea of message passing than someone who knows Smalltalk.  That means that a lesson on messages will be the kind of thing that some folks want to just fast forward past.  But then if you FF too far you may miss important things.

This is why I've never done the Stanford courses, and instead tried to wing it with heavy Googling and lots of time on Stack Overflow.

Today, I found a better answer.  Playback the Stanford courses at double speed.  How?  Harder than it looks, actually, if you've got the latest of everything on your machine. Turns out you have to go back in time a bit.  [ Note that I am running a Mac with Lion installed.  Your mileage on Windows may vary.]

1. Download Quicktime Player 7.  This advice comes straight from discussions on the Apple.com website, by the way.
2. Find your video in iTunes, select Show in Finder.
3. Right-click (or ctrl-click or whatever) on your video, go to Open With... and pick QuickTime Player 7.   Note that you did not upgrade QuickTime in the first step, and it will not become the default player. You deliberately installed a previous version.  You may have to find it under "Other" the first time you do an Open With, but in my experience once you've done that the first time it will show up as an option the next time.
4. Got it open in QTPlayer 7?  Good.  Now go to Window -> Show A/V Controls.  This is the part that you needed QT7 for, because they've taken it out in later versions.
5. In the lower right corner there's a slider for Playback Speed.  Pick a speed.  I'm running them at 2x, and I find it the right combination of understandable while causing me to yell "Faster, talk faster!" at the screen like I do at 1x.

Now I feel like I'm getting somewhere.  If you've got two monitors, that's even better - put the video up on a second screen, and then go about your business doing whatever other tasks are important while you half-listen to the lecture (just like most of us developers do in staff meetings when we bring the laptop, am I right?)  When it gets to something that seems interesting, pay more attention to the video.

I learned this trick this morning, and blew through the first lesson (the one that I would have been most likely to scream "Talk faster!" at) while doing other things.  Now I'm halfway through lesson 2 and into stuff that's more interesting to me, but still only at that "Confirm and clarify stuff that I'd already experienced" sort of phase (remember, I've been banging around on all this stuff by myself for a long time).  Eventually I'll get to the "Entirely new to me" stuff and, if necessary, I can bring the speed back down to 1x.

But probably not 1x. ;)

How To Hard Reboot / Factory Reset Your Verizon Droid Incredible 2

I have a Droid Incredible 2 from Verizon.  Had it coming up on 2 years.  This past Father's Day it stopped powering on.  Very weird circumstance, it rebooted itself while in camera, then acted flaky, then when I put it on the charger....nothing.  Stopped responding in any way to any sort of stimulus.  No lights, no nothing.  When I'd first plug it in there'd be a little red charging light, but that would go off in 5 seconds.  Left it on over night, nothing.  Popped the battery, still nothing.

Having tried everything and now bracing myself for the worst (a dead phone), I call Verizon tech support, who quickly moves me along past all the above steps to "Ok let's do a factory reset on the phone."

1. Hold down the Volume Down key.
2. Press and hold the Power key for 3-5 seconds.
3. You should now get a boot screen.  (The hacker/geek in me squealed with glee when I saw this come up).
4. One option is Factory Reset, which if you've never done one I'll warn you wipes your entire phone as if it's brand new, and you'll be tasked with setting up your Google accounts and such al over again, not to mention the havoc it will wreak on your various installed apps.
5. Another option, however, is Fast Boot.

I asked the tech person, "Since I know what a factory reset will do, can I try Fast Boot?  Worst case it does nothing, and I repeat this process and select the reset."

"Sure, sounds good," she tells me.  "All we really have is directions for how to reset it."

Wonderful.  I hit the Reboot and thank her for her time.

A few minutes later (the I2 has a very long boot time, you ever notice that?)  I have my phone back!  Yay.

Documenting here because I did go googling for how to hard reboot my phone, and could not find easy instructions to do so.  Maybe the next guy to come along looking for it will land here.  Hold down Volume Down + Power, get boot screen, pick Fast Reboot.

Zazzle on Rails

I have merchandise on the Zazzle store.  I also have sites that I manage, and I would like to advertise my merchandise on my sites under my own control.  Zazzle offers a handful of banner options, but I wasn't really finding the level of control that I wanted.  So I've set about writing my own.

Zazzle does offer a PHP front end if you want to host your own store.  However I'm a Rails guy and would much prefer to work in that language.  From what I can tell, there is no Zazzle gem.  Yet.

What they do offer is a simple enough RSS feed that will allow you to easily pull the relevant info on your products, in a variety of ways.  You can customize the call to grab newest items, or most popular, via search terms or by searching for specific product types only.  In my case, and since I have less than 100 items in the store,  I can just go ahead and grab all of them:

@feed = Feedzirra::Feed.fetch_and_parse("http://feed.zazzle.com/ShakespeareGeek/feed?st=date_created&pg=1&ps=100")


You'll get back the item URL, description, and even a pre-made

complete with image that you can just go ahead and drop right on your page, if you like.


Now it's really up to you what you do next.  I actually use this call to go ahead and seed a local database of Product objects, which I'm then tagging and categorizing as I see fit.  Since I know when I create new products, I can manually go in and update my database to stay in sync.

I wrote up a simple banner script for now that just goes in and says "Get me 3 random products," and then I display the supplied HTML that came with the RSS feed.  Later, depending on the context of the page, I'll be able to say "Get me 3 random Hamlet products" or "Get me 3 t-shirts" or possibly even change what and how I'm displaying the items.

Note that the URL takes you back to the product page on Zazzle, where your customer would then still have to hit a Buy button.  Not the greatest user experience, but I'm not trying to rebuild the store from scratch, either.  I just wanted a way to display advertisements for my merchandise in my own way.  Your mileage may vary.

When I have time I hope to expand this with more source code and examples about exactly what I'm doing.  At the moment, though, I have no idea if Google will pick up this post and if anybody will ever see it.  So if you did land here because you do want to connect Zazzle and Rails, leave a comment so I'll know whether to keep posting on the subject.