The Man Who Knew Infinity: Coding Ramanujan’s Taxi

Ramanujan is on the left

Have you see the movie (or read the book) The Man Who Knew Infinity?

This new movie — which stars Dev Patel and Jeremy Irons — explores Indian mathematician Srinivasa Ramanujan and his profound understanding, ingenuity, and love of math.  The film inspired me on both an intellectual and emotional level. But what really drew my attention was a particular five second scene.

The scene takes place in 1918. Ramanujan‘s mentor and friend G.H. Hardy quips that he had just taken taxi number 1729 and finds the number “a rather dull one.”  Ramanujan passionately replies, “No, Hardy, it’s a very interesting number! It’s the smallest number expressible as the sum of two cubes in two different ways.”

Ramanujan was able to see beyond the simple taxi cab number and into the depths of the expression behind it: a³ + b³ = c³ + d³…better known as Ramanujan’s Taxi. I thought this problem was fascinating and wondered how the code implementation would look. Little did I realize there were many optimization layers to this algorithm onion.

The taxi Ramanujan took — at least in the movie

First Crack at Implementing Ramanujan’s Taxi

I started with a straight forward implementation written in Scala. The code, with performance timings, can be found on GitHub:


We begin with a brute-force implementation by looping though all combinations to find where a³ + b³ = c³ + d³. We achieve O(n⁴) performance because of the four loops used to calculate all values of a³, b³, c³, and d³ equal or less than parameter n, which bounds our search field.

This brute-force implementation, with O(n⁴) performance, kinda sucks. So, how can we do better?

We Can Do Better

First question to ask is: do we always need to calculate all the values of a³, b³, c³, and d³? Remember, the equation we are using is a³ + b³ = c³ + d³. If we solve for d³, we get d³ = a³ + b³ – c³. Thus, once we know a³, b³, and c³, we can calculate the value of d³ directly instead looping through all values of d³.

My next implementation, again in Scala, replaces the fourth loop with the calculation d³ = a³ + b³ — c³:

The 2nd version has O(n³) performance since we get to skip that final loop. Neat!

Third Time’s A Charm

We’re not done yet. There is a third, and the best yet, enhancement to consider. What if we don’t need to solve for all values of not only d³, but c³ too? A few things to understand:

  • If we calculate all values of a³ and b³ equal to or less than n, we essentially have all possible values of not only a³ and b³, but also c³ and d³.
  • The sum of a³ + b³ is equal to the sum of c³ + d³
  • If the sum of #2 above for a given pair of integers (a³, b³) matches the sum of another pair of integers (a³, b³), we have in essence found the c³ and d³ pair.

If we store every combination of the sum of a³ + b³ and the corresponding pair (a³, b³), any sum that has two pairs means we have found a³ + b³ = c³ + d³ where the first pair in the list can be considered (a³, b³) and the next (c³, d³).

For example, if we iterate through the combinations of a³ + b³, we will store the sum 1729 with the pair (1³, 12³). Continuing to iterate, we will see another sum of 1729 arise, but this time with the pair (9³, 10³). Because we have two different pairs both summing to 1729, we have found a Ramanujan Taxi that solves for a³ + b³ = c³ + d³.

In the third version, we use a Hashmap to store the sum (key) and the corresponding list of pairs as a Sorted Set (value). If the list contains more than one pair, we’ve got a winner!

This implementation has O(n²) performance since we only need two loops to calculate the combinations for a³ and b³. Very neat!

I suspect there is a forth optimization where we only need to calculate values of a³ and derive b³ from a³ (the ‘b’ loop is just an offset of the ‘a’ loop) with O(n) performance.

Also, another challenge is to re-write the implementations as a functional programming pattern. I’ll leave that for you to explore.

An Amazing Movie, an Amazing Man

After watching The Man Who Knew Infinity, I was in awe of Ramanujan’s genius. By implementing his taxi algorithm — with its several performance optimizations — I got a glimpse of the beauty he saw in “No, Hardy, it’s a very interesting number!”

Ramanujan’s Taxi, at almost a century old, is still making new discoveries. Mathematicians at Emory University have found the number 1729 relates to elliptic curves and K3 surfaces — objects important today in string theory and quantum physics.

I expect we have only scratched the surface of Ramanujan’s taxi cab number and the man’s amazing genius.

Article originally appeared at Free Code Camp

We're Hiring Engineers at Ladders. Come join our team!

Ladders Engineering Cultural Values

The Ladders team is very excited to share with the world our Engineering Cultural Values. We hold these truths to be self-evid…just kidding. Creating a set of inspiring, long lasting, and fundamental values isn’t easy. It is a reflective process with many different, but often surprisingly similar opinions.

We asked ourselves:

  • What does it mean to be an engineer at Ladders?
  • What do we expect from ourselves, our colleagues, and our company?
  • What do we take pride in and where do we need to do better?
  • What are our core values that will form the bedrock now and in the future?

Wow! That is a lot of stuff to consider. After many brain-storming sessions, inspirations from other companies (thank you Zillow and Amazon), and tossed/consolidated ideas, we came up with 7 core cultural values.

Without much further adieu, we present Ladders Engineering Cultural Values.

Ladders Engineering Cultural Values

Why Do I Have to Test Your Shit? (The 5-Minute Sniff Test)

1*BJr8YvnbtRMw5idQ8pFCGA

If you can’t spend 5 minutes testing your work, then don’t make me.

I’ve spent 18 years in the software engineering industry, and have been called a programmer, then a developer, and now a software engineer — next is “delivery demon,” mark my words. In that time, I’ve tested my fair share of code. I’ve worked as a part-time tester, tested code I’ve written, ran QA groups, and poked my nose into systems I shouldn’t have.

There are many titles for those who professionally test software. You might be called a Tester, a Quality Assurance Analyst, or an Engineer in Test. You might be creating incredibly advanced automation scripts that produce beautiful reports via SonarQube, or you might be doing fully manual testing. Regardless of your title or approach, you are trying to discover issues before they make it to production, and users discover them.

A Tester is an Engineer’s partner in crime. Just like the editor of a book, you take what others (i.e. Engineers) have written and make it greater. As Steinbeck said of his editor Pat Covici, “He was much more than my friend. He was my editor. Only a writer can understand how a great editor is a father, mother, teacher, personal devil, and personal god. For 30 years Pat was my collaborator and my conscience. He demanded more than I had, and thereby caused me to be more than I should have been without him.”

Testers help Software Engineers go from Good to Great.

Over the years I’ve come to believe two things about testing:

First, what a tester does is hard. Their task requires the application of precision to a project’s specific requirements, unconventional thinking (box, what box?), channelling the end user, and a holistic/system-level view. Testers do an amazing job and have been critical to my success in releasing awesome software.

Second, a Tester’s job is made even harder by Software Engineers, because Engineers hand over shit code that doesn’t pass what I call the “5-Minute Sniff Test.”

The 5-Minute Sniff Test

As a Software Engineer, you chose a career building great software. You love solving fun and interesting problems using the latest frameworks, the coolest algorithms, and rainbows & unicorns. On a daily basis, “You Crush It!” However, all that screeches to a halt if you have to stumble through the muck of poorly defined (sometimes incomprehensible) requirements just to get to the heart of the problem.

Your progress is delayed, your time is wasted, and you’re pissed off! All of this could have been avoided if the Product Manager had just put a little more care into what they handed you. Doesn’t the PM take pride in their work? Do they even know what they are doing? Garbage in is garbage out.

When it is the Software Engineer’s turn to hand over their work, the code quality determines the efficiency, success, and morale of the person testing. The Tester expects the same level of quality as the Software Engineer expected from the PM. This doesn’t mean your code is bug free — we don’t want to be putting anyone out of a job — but it does mean your code meets a certain level of quality and professionalism.

How do we quantify the quality and professionalism expected? Enter the 5-Minute Sniff Test. Basically, if a someone (Tester, QA, Spouse, or Priest) can find major and obvious bugs in the first five minutes of testing your code, then you didn’t spend enough time testing. You’ve wasted your time, disrespected the Tester’s time, and started to build a reputation for delivering sloppy work (question: do you even know what you’re doing?). You laid a rotten egg that smells bad, everyone knows it is you, and you should be embarrassed. Garbage in is garbage out.

A Lesson from the Front

That “I want to crawl under a rock” feeling

My team and I once built an awesome new feature in our iPad app that was technically challenging and had the coolest design, and I was very proud of the work we did. It rocked and we had crushed it!

With a cheshire cat grin, I presented the app to our CTO of Asia (senior guy with about 10,000 people reporting to him). He started clicking everywhere except where I wanted him to click.

No. Don’t! STOP!

But he just kept clicking. The app crashed, data wouldn’t load, and mayhem ensued. He eventually handed the iPad back to me and grumbled, “This doesn’t look ready.”

He never actually saw the new features we had built. I was devastated, embarrassed, and wanted to crawl under a rock, but I had also learned an important lesson.

Take Care of Your Stuff

Don’t make someone else pick up after you.

Typically I’ll hear software engineers argue that it’s too hard to change their mindset from coding to testing.

That is why we have a testing team, right?

Bullshit!

I’m not asking you to walk, rub your tummy, and chew gum at the same time (it is harder than you think). I’m asking you to literally spend five minutes testing what you built and what you should be proudly standing behind.

Just because the city has street cleaners, doesn’t mean you should toss your candy wrapper onto the ground.

Don’t make someone else pick up after you.

We need to do better.

And we can.

How To Perform Your Own 5-Minute Sniff Test

The 5-Minute Sniff Test is the first line of defense against the “I will just hand over anything” mentality.

It means before you hand over your feature, stop, take a deep breath, clear your mind, and for the next 300 seconds, test what you just built.

  • Outside the Box — 90 Seconds: Did you step outside of your engineering shoes and test from a user’s perspective? Does the feature look nice and feel right, aside from the requirements? I’ve painted myself into corners arguing a feature is valid because it is “what the requirements asked for.”
  • Check Your Unit Tests — 30 Seconds: Do all the unit tests pass, and is there full code coverage? You can’t test everything by hand, so automated unit tests are vital for code quality. The 30 seconds allotted isn’t to create the unit test, but just to verify they pass. You should also consider failing the build if the unit tests don’t pass, which would allow more time for the obvious.
  • The Obvious — 190 Seconds: Did you test all the obvious cases? For example, if the pressed button should cause unicorns to dance across the screen, be sure to test if pressing the button actually makes unicorns dance across the screen. Do I get any errors in the logs, do rainbows show even though that isn’t part of the requirements (although it should be, because that would be awesome), and what happens if I double click the button? Review the requirements and make sure everything adds up. For example, did you catch that the total number of seconds listed here equals 310 instead of 300 seconds? Let’s correct “The Obvious” to 180 seconds.

Five minutes is all it takes to make sure you’re not handing over shit. If all else fails, grab a colleague and ask them to sniff around.

Looking Ahead

In his book “Blink,” Malcolm Gladwell relates the story of interviewers making snap judgements about the quality of a candidate within the first five seconds of meeting. The interviewer continues to subconsciously reinforce their initial impression by subjectively weighing the candidate’s answers towards their bias.

In other words, your first impression is your last impression. I don’t believe I ever fully recovered my reputation with the CTO of Asia after that bad first impression.

Performing the 5-Minute Sniff Test to check your shit takes very little time, but it can be of tremendous benefit to you, your colleagues, and your company:

  • It helps you build a Reputation for excellence and quality,
  • It Respects your partner in crime, the Tester, and
  • It is more Efficient with everyone’s time.

When everything looks and feels right after the 5-Minute Sniff Test, go ahead and hand off the feature you are proud of and can stand behind. You’ll have a thankful Tester, and have built yourself a reputation as an awesome engineer.

Originally published at Simple Programmer

We're Hiring Engineers at Ladders. Come join our team!

How Much Is Your Resume Worth? – Part 1

resume-reviewer

Have you ever considered how much your resume is worth?  Put an actual dollar value on it?  I sometimes ask people seeking resume help how much they think their two-page resume is worth (hopefully their resume is only two pages and not the 10+ I’ve seen).  I get answers from five cents to “a lot,” but the right answer is: it depends on how much I make.  If I earn $100,000 every year for the next ten years, these two pages are worth $1,000,000 dollars to me.  Think about that for a second.  The resume I thought of as a burden to create and update, which I worked on while watching The Big Bang Theory or Game of Thrones, is possibly worth $1mm or more to me.  What other documents have you recently created worth $1mm+ to you?

While your resume is far from the only factor in getting a job, it is your gateway into getting the interview.  Malcolm Gladwell describes in his book “Blink” how people, especially interviewers, make snap judgments.  When you first meet someone and shake their hand, you make a snap judgment about that person.  A strong handshake might indicate a smart and put together individual or a weak handshake might indicate a timid and unmotivated individual.  The interviewer sub-consciously continues to reinforce that initial judgment through out the discussion.  For example,

“Do you know Java?” the interviewer asks.

You reply, “No, but I read a lot and can quickly learn.”

If the interviewer snap judged they don’t like you, they sub-consciously think, “Hmm, doesn’t seem to have the right skills.  No hire.”  If the interviewer snap judged they like you, they sub-consciously think, “Wow, seems to have a real can do attitude and has great potential.  Hire!”  The very first snap judgment a hiring manager makes about you is based on your resume.

A well organized, easy to read, and error free resume indicates an intelligent and well-organized individual.  A sloppy, dense, or error-filled resume indicates a lazy and “lacks attention to detail” individual.

That is why we said, let’s build something that helps people build the best resume possible, create a great first impression, and get them the right job: The Resume Reviewer.

To Be Continued in Part 2: Building the Resume Reviewer where we’ll get into the tech detail!

We're Hiring Engineers at Ladders. Come join our team!