Different Approaches (Think Like a Programmer)

This episode features a viewer-suggested problem from a programming contest site. I show different approaches to the problem -- but the code's not shown until the end, so give it a try yourself! Thanks to Jesus Castello ( / matuxiv ) for the suggestion. You can see the original problem description at www.hackerrank.com/contests/c....
Your comments and suggestions for future videos are welcome.
"Think Like a Programmer" is a book I've written to help programmers with problem solving. If you've found that you are able to read programs and understand programming language syntax but aren't always confident writing programs from scratch, my book may be able to help.
For more information on the book head to one of these:
Amazon page for the book: amzn.to/1MZlmlY
My site: www.vantonspraul.com/TLAP
My publisher's site: nostarch.com/thinklikeaprogrammer
Connect with me:
My site: vantonspraul.com
Twitter: / vantonspraul
Facebook: / thinklikeaprog

[@random4573]

You left out this crucial condition while explaining
"It is assured that any such tracing generates the same word. "

[@animesh616]

I used naive aproach by creting matrix and iterate through every element.Works good only for small input. Having some problem in recursion though.

[@brentlio5578]

Add 1 for each step proceeded to the right or down, when the step reaches the bottom right, check if that 1 has become 10 or not. Do all possible combination and if out put the number of times that the finishing move equals 10 (or whatever number "Mathmatics" s length is equal to.
Does that work?

[@andreipatrascu1944]

I too used the math way into this problem (Pascal's triangle) so the end result is
return FACT(m+n-2)/(FACT(m-1)*FACT(n-1));

[@gimpycoder8548]

If you want to look further into this problem, read about Pascal's Triangle (your spreadsheet data reflected this) at en.wikipedia.org/wiki/Pascal%27s_triangle and en.wikipedia.org/wiki/N_choose_k
Thanks for these videos. You really helped me think like a programmer.

[@vantonspraul]

Glad the videos helped. Got another work in the pipeline. And thanks for the reference. It's funny, I know about Pascal's Triangle, but it's been a long time since I've taught a math course, and honestly the connection didn't occur to me until I read your comment. I guess it just shows there's always more ways to approach a solution!

[@Anjoys01]

Thank you again for these videos

[@vantonspraul]

Sure thing!

[@Anjoys01]

Could you please do a video on planning(problem solving technique) or how you go about planning when it comes to solving a problem. Thank you.

[@vantonspraul]

Do you mean, how to come up with a plan to solve a problem? That's something I cover in the book, too. Yes, I think that could be a good subject for a video. Let me see what I can do. Thanks for the suggestion!

[@Anjoys01]

V. Anton Spraul Yes! Thank you very much!

[@Mattmahlatse]

I know this is old, but thought the problem was about finding number of valid PATHS, not number of valid STEPS, how did you conclude that it was about steps

[@user-mu2qq3eb7t]

this is my solution, which seems rather naive:)
int path(int row, int col) {
If(row == 1) return 1;
If(col == 1) return 1;
Int TotalPaths = path(row - 1, col) + path(row, col-1);
Return TotalPaths;
}

[@sinistergeek]

Does sudoku help in problem solving ability!

[@maikio2729]

i found this but i would like to know if someone found a non recursive solution for this
#include
int matrixtracing(a,b)
int a,b;
{int ans;
if(a==1||b==1){ans=1;}
else{ans=matrixtracing(a-1,b)+matrixtracing(a,b-1);};
return ans;
}
main()
{int m,n,s;
scanf("%i",&m);
scanf("%i",&n);
s=matrixtracing(m,n);
printf("%i",s);
}

[@EarthCrossers]

//Here's a c# solution:
using System;
public class HelloWorld
{
static public void Main ()
{
MatrixPath mp = new MatrixPath(4,4);
mp.CountPaths(0,0);
Console.WriteLine ("the number of paths is: " + mp.pathCount);
}
}//End class
public class MatrixPath
{
int numRows;
int numCols;
public int pathCount = 0;
public MatrixPath(int rows, int columns)
{
numRows = rows;
numCols = columns;
}
public void CountPaths(int r, int c)
{
if(r < numRows-1 || c < numCols-1)
{
if(r < numRows-1)
{
CountPaths(r+1,c);
}
if(c < numCols-1)
{
CountPaths(r,c+1);
}
}
else if(r == numRows-1 && c == numCols-1)
{
pathCount++;
}
}
}