News for hackers. Stuff that matters.
Re:How to Crack the Toughest Coding Interviews by Someone on Friday October 26, 2012 @06:55PM (#4704641)
"I vaguely recall counting lattice paths in 3-space being a wickedly hard problem with no known polynomial time solution."

I think you can easily write the recursion:

  p(x,y,z) = p(x-1,y,z) + p(x,y-1,z) + p(x,y,z-1)
Leave out the term with x-1, y-1, or z-1 for the edge cases for x, y, and/or z equal to zero.

With that in hand, it is easy to compute all values bottom up, starting with those where x+y+z = 0, 1, 2, etc.

Definitely fewer than (x+y+z)^3 values to compute, all of them in O(1) (disregarding cases where the numbers become bignums)

Generalization to any number of dimensions seems easy, too.

A closed form solution, that might be harder.

Re:How to Crack the Toughest Coding Interviews by pjscott on Friday October 26, 2012 @09:34PM (#4705016)
You're assuming that all movement must be in one of three directions, but in general, you can go in six directions -- forward or backward along the x, y, and z axes. Your cubic-time DP algorithm doesn't solve the self-avoiding walk problem, which I think is what jsolson vagely recalls.

http://en.wikipedia.org/wiki/Self-avoiding_walk

Re:How to Crack the Toughest Coding Interviews by jsolson on Friday October 26, 2012 @11:18PM (#4705232)
So, the professor in question was Dana Randall. I believe she was talking about this topic: http://en.scientificcommons.org/42983059

Basically, yes, self-avoiding paths.

This was basically a brief aside in her honors undergrad algorithms course, so the topic was a bit beyond what I was prepared for at the time :)

Re:How to Crack the Toughest Coding Interviews by Someone on Saturday October 27, 2012 @05:17AM (#4705798)
I wasn't assuming, I was following what the OP wrote: "by going only up or right one point with each move (that is, each move is either (0,1) or (1,0)))" for 3D.

Counting self-avoiding walks is hard in 2D, too (http://oeis.org/A007764)