Archive for October, 2011

A new coding challenge

It’s been a while since I offered a coding challenge, so let’s remedy this.

This one comes from this week’s Car Talk’s puzzler. Here is the short version of it:

A farmer has a forty pound stone that he uses to weigh food for his animals on a scale. One day, he loans the stone to his neighbor. A few days later, the neighbor returns the stone and apologizes to the farmer because his stone is now broken in four pieces. The farmer responds “Please don’t apologize, you have actually made my life easier because with these four pieces, I can now measure any weight between one and forty pounds”.

The question is: how much do these four individual pieces weigh?

I’m adding a few clarifications, which are not necessarily what the Car Talk guys meant (I don’t have the solution and I haven’t looked at any discussion on the subject):

  • The four weights are integers.
  • The weights we can measure between one and forty pounds are in one pound increment.
  • They are measured in one session (otherwise, you could measure forty pounds with a one pound stone by performing forty measurements).
  • If there is no solution (the farmer might be bad at math), show the four weights that allow to measure the most weights between one and forty pounds.

The challenge? Write a brute force solution to this puzzler in any language that you want. I don’t care if your solution is slow, fast, ugly or elegant as long as it works, and I suspect that certain languages will be very good for this puzzler

Bonus questions:

  • Your solution should explain how exactly you use the stone pieces to measure each weight.
  • Is there a formal way to solve this problem without using brute force?

Solution to the quiz

Wow, my little quiz received a lot more attention than I thought it would. Surprisingly, of all the answers that I have read so far (over 150 between the comments on my blog and Google+), I only spotted three that match exactly my reasoning, which in itself, has to be a statistical anomaly.

Anyway, enough waiting, here is my interpretation of the puzzler.

This is a meta quiz: a question about a question. The first step to figure it out is to solve the “inner” question, which is determining what “right answer” or means. In other words, we need to answer “If you have a choice between four options and you pick randomly, what are the odds you’ll get the right answer?”.

This is a very general question that can be answered easily: 1 in 4. 25%.

Armed with this knowledge, we now focus on the “outer” question, which we can rephrase as follows:

If you choose an answer to this question at random, what is the chance you will pick 25%?

Looking at the choices, we notice that 25% appears twice among four choices, so you will be right 50% of the time.

Therefore, the answer is 50%, right?

Wrong!

It’s B! You’re asked to pick a choice between A, B, C and D, not a percentage. Some teachers will actually fail you if your answer doesn’t typecheck :-)

I think this is the answer that the creator of this quiz expected, however, the more I thought about it, the more I started to realize that there was a crack in the reasoning. Can you spot it?

It’s the answer to the question above:

If you have a choice between four options and you pick randomly, what are the odds you’ll get the right answer?

The answer will be 25% only if the answer is present exactly once among the options. Not zero, not two, three or four.

Do you think the meta quiz obeys this constraint? After all, 25% appears twice in the options, right? Yes, except that the correct answer is not 25% but 50%, which appears exactly once, so the quiz seems to be consistent with this caveat.

Exercise left to the reader: can you rephrase the original quiz to close this loophole?

Probability quiz



Link to the discussion on Google+.

Goodbye, old friend

Yesterday, I received my Galaxy S II and it’s now time to say goodbye to my trusty Nexus One.

I’ve had it for over two years and it is by far the best phone that I’ve ever owned. Even today, I still think it looks absolutely gorgeous. If you’ve never held one in your hands, you are missing out. It managed to run all of the applications that I’ve installed very well, even compared to more modern phones.

As for the Galaxy S II, it’s quite a formidable phone and I have a lot of things to say about it after only twenty-four hours, but I’ll save this for a future post.

Halloween

How about a scary comic to get in the mood for Halloween?

Too soon. Definitely too soon.

There is a special place in history for personalities who didn’t die of old age. These people continue to cast a shadow on the world long after they died, not just because of what they did while they were alive, but because even when they are not around, they still get people to wonder how things could be different.

These people inspire not just the indicative (what they have done) but also the subjunctive (what would they have done?).

John Fitzgerald Kennedy, Martin Luther King, Carl Sagan, Richard Feynman… They all continue to haunt our thoughts. Just last week, I was wondering what Feynman would have thought of CERN scientists breaking the speed of light. I’m sure it would have been inspirational, modest and full of insight. And who knows, maybe this breakthrough would have happened earlier if Feynman were still alive?

Steve Jobs joins this very select club. Of course, innovation will keep happening and awesome products will keep shipping, but each of them will be overlooked by Jobs’ aura. Would Steve Jobs have done it differently? How much of this product was influenced by Jobs, explicitly or implicitly?

Steve Jobs isn’t done changing the tech landscape and the way we view products, he’s just no longer around to see the results of his work.

Still… What a sad, sad day.

Android and Amazon

Interesting piece from Jean-Louis Gassée, commenting on the various tech events of last week. However, I have to disagree with his take on the Amazon/Google relationship regarding Amazon’s new tablet, the Fire.

Jean-Louis quotes the following excerpt from Michael Mace:

“The problem is that Amazon is using Android as just an OS, not using the Google-branded services and application store that Google layers on top of the OS (link). Although Google touted the openness of Android when it was first launched, the reality is that Google is using it as a Trojan horse to force its services onto hardware. What Amazon did with Android is very threatening to Google, and so you’re not likely to hear a lot of supportive words from them.”

I really don’t see the threat, here, especially not the one coming from Amazon’s Silk browser being used as a cloaking proxy for its users. Yes, Google will not be getting browser hits directly from Fire users, but let’s face it: no matter how successful the Fire will be (and I bet it will be very successful), it will never go very far in terms of browser market share compared to smartphone access or even PC access. As for Amazon, I bet they will keep getting most of their data from non-Fire users connecting to Amazon.com by a very, very wide margin.

As for Android: Google’s mobile OS was designed from the very first day as an open platform that anyone, vendor, carrier or third party, can use in their own product without giving so much as a phone call to Google to ask permission. In a famous tweet from a year ago, Andy Rubin gave his definition of ‘open’:

the definition of open: “mkdir android ; cd android ; repo init -u git://android.git.kernel.org/platform/manifest.git ; repo sync ; make”

I think it’s nice, and it’s certainly one definition of ‘free’, but hardly the one that really matters. The important aspect of Android’s freedom lies in its license and the fact that every day, it’s being used as the foundation of products that even Google has never heard of, and probably never will until they ship.

Amazon is not the first company to go down that route. Just this past week, Boeing announced that their next generation of in-flight software will be based on Android. I don’t know if Google was involved in this project or not (I’m betting not) but I’m not seeing any outrage from tech pundits about this decision. Why is Amazon’s Fire different?

It’s a non-story.

Very soon, companies announcing that they are choosing Android for their next generation of products and they did not cooperate with Google to do so will be as interesting to read as an article about what operating system your toaster runs on.

The bottom line is that every new product that comes out running on Android solidifies its success in the market, and by extension, Google’s.