Channels ▼

Mark Nelson

Dr. Dobb's Bloggers

Google Treasure Hunt

May 18, 2008

Google has kicked off their 2008 Treasure Hunt, which looks like it's going to be a four-part series of short puzzles:

designed to test yer problem-solving skills in computer science, networking, and low-level UNIX trivia.

The first puzzle has already expired, and while there is a link to it, I'll reprise it here.

My Transcription

The playing field is a rectangular matrix with R rows and C columns. Place a marker in the upper left corner, labeled [1,1].  Your goal is to move the marker from that position to the lower right corner, labeled [R,C]. If the marker is only allowed to move one square at a time, and only allowed to move directly down or directly to the right, how many unique paths are there between the start and the destination?

Google will generate an instance of the problem for you, with values of R and C that seem to vary between 30 and 70. Once you provide the solution, in theory it will tell you whether your answer is correct, although I had some trouble in that area. (Warning: if you lose your confirmation number, your confirmation number is lost!)

Notes

This would be a nice warm-up problem for an algorithms class. There are a few interesting aspects to the problem. First - finding the exact answer. Second, providing a concise definition of the algorithm used to calculate the answer. Third - doing so in as efficient a manner as possible.

Try to see if you can solve this for values 56 and 43.  If you can come up with an implementation you're proud of in the language of your choice, post it as a comment.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video