Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

I've got this problem:

- Given a user specified n by m grid, write a program which computes the number of paths from the bottom left corner to the upper right corner. Paths may only proceed from bottom to top and left to right. For example in the 3 x 3 grid:

g--h--i

| | |

d--e--f

| | |

a--b--c

yields 6 paths

adghi

adefi

abcfi

abefi

adehi

abehi

Output:

The user should be able to specify:

- Output the number of valid paths only

OR

- Output the number of valid paths and all valid paths (i.e. as in the above example)

I've been working on it and here's what I got so far:

VARIABLES

X - Current X co-ordinate

Y - Current Y co-ordinate

XMax - Maximum width of grid

YMax - Maximum height of grid

XModifier - The number of positions "user" moves right

YModifier - The number of positions "user" moves up

PathCount - The number of paths "user" has taken

Begin with:

Xmax = user defined

Ymax = user defined

X = 1

Y = 1

XModifier = 0

Ymodifier = 1

PathCount = 0

Procedure:

1. Increment x,y by respective modifiers until Y reaches max.

2. Increase X until ='s Xmax.

3. Set to x, y to 1, 1 and add 1 to PathCount

4. Increase YModifier by 1.

5. Repeat steps 1 - 4 util YModifier ='s (YMax - 1).

6. Increase XModifier by 1 and set YModifier to 1.

7. Repeat steps 1 - 6 until XModifier ='s (XMax - 1).

The problems I have SO FAR are:

-What about moving something like: right 2, up 3, right 1, up 1, etc?

-What should the proper way of writing the path's be? (ex: (1,1) to (1,5) to (3,5) OR (1,1), (1,2), (1,3), etc)

Any help is apprecated, even if it's just an idea.

Thanks in advance,

Kory

- Given a user specified n by m grid, write a program which computes the number of paths from the bottom left corner to the upper right corner. Paths may only proceed from bottom to top and left to right. For example in the 3 x 3 grid:

g--h--i

| | |

d--e--f

| | |

a--b--c

yields 6 paths

adghi

adefi

abcfi

abefi

adehi

abehi

Output:

The user should be able to specify:

- Output the number of valid paths only

OR

- Output the number of valid paths and all valid paths (i.e. as in the above example)

I've been working on it and here's what I got so far:

VARIABLES

X - Current X co-ordinate

Y - Current Y co-ordinate

XMax - Maximum width of grid

YMax - Maximum height of grid

XModifier - The number of positions "user" moves right

YModifier - The number of positions "user" moves up

PathCount - The number of paths "user" has taken

Begin with:

Xmax = user defined

Ymax = user defined

X = 1

Y = 1

XModifier = 0

Ymodifier = 1

PathCount = 0

Procedure:

1. Increment x,y by respective modifiers until Y reaches max.

2. Increase X until ='s Xmax.

3. Set to x, y to 1, 1 and add 1 to PathCount

4. Increase YModifier by 1.

5. Repeat steps 1 - 4 util YModifier ='s (YMax - 1).

6. Increase XModifier by 1 and set YModifier to 1.

7. Repeat steps 1 - 6 until XModifier ='s (XMax - 1).

The problems I have SO FAR are:

-What about moving something like: right 2, up 3, right 1, up 1, etc?

-What should the proper way of writing the path's be? (ex: (1,1) to (1,5) to (3,5) OR (1,1), (1,2), (1,3), etc)

Any help is apprecated, even if it's just an idea.

Thanks in advance,

Kory

These choices sometimes may not exist eg you are at the top or at the right of the array.

So you have a recursive problem if you know what recursion is. This is the easiest way to solve it.

You will need an array to store the path you are travelling and this will be passed recursively. You will also need to pass another variable recursively and this is the number of paths found.

What sort of array could this be? How about an array of char that is initialised to E for empty. At each step the array point you are at is changed to either U or R for Up or to the Right. In this way you are saving the path you are travelling.

This may explain ozo's hint.

are points with x and y coordinates - for each node make two other nodes (one-up and one-right), and keep growing the tree in such way until every tree branch comes to the upper-right corner; in that way when you will have

a complete tree, then the number of the branches would be number of paths or something like that

Before I give ya the points, I'm going to have to "research" your idea. (I haven't used Binary Trees before) One question I have about your answer. Sure I can count the number of branches to find out the number of paths, but is it able to tell me what the paths are too?

Alisher,

No, there is no max value for M and N. They are both user defined.

_lychee_,

Could you please explain your idea again? I don't think I caught on.

dbrunton,

Do you mean entering a value (right or up) in the array for each and every point in the grid? That could be one enormous array if the grid is large.

ozo,

Pascal's triangle?

Thanks all for the ideas. I'm looking into all of them. If anyone has anymore ideas, go right ahead and post them!

TKS,

Kory

I looked at Binary trees briefly last night. Still a few questions. How would I put in the (X,Y) co-ordinate in each node? In each example I have seen, it is only possible to put strings and/or integers into the nodes.

>ordinate in each node? In each example

>I have seen, it is only possible to

>put strings and/or integers into the

>nodes.

If you WERE to use a binary tree structure, you can store ANY type of data in a node. If you wanted to store both the X and Y coordinate, you could declare a structure

type

TPoint = record

x, y :integer;

end;

and then use TPoint as the data type for each of your nodes (as opposed to strings, integers, etc.)

if (x+1) <= width then

traverse(x+1,y1);

if (y+1) <= height then

traverse(x,y+1);

R-1 ups and C-1 rights

so in ur path that is length (R+C-2), u need C-1 rights or R-1 ups (it's the same)

so, total number of ways = (R+C-2) choose (C-1) [like nCr]

can get the path by moving the ups and rights around: like for a 3x3:

UURR -> URUR -> URRU -> RUUR -> RURU -> RRUU

basically start with all on one side (in this case U is on the left), then start moving the last U to the right, until u hit the edge, then advance the next U and reset the U...

argh the explanation's not good but it's just how u would systematically get all the combinations....

for 3Us and 2Rs, it would be like:

UUURR -> UURUR -> UURRU -> URUUR -> URURU -> URRUU -> RUUUR -> RUURU -> RURUU -> RRUUU

see the pattern?

btw, what ozo means by pascal's triangle is like if u take the top right corner to be the top of a triangle and the up to right diagonal to be the base, and u put the number of ways to get to the topright on each grid intersection, u'll see that it is a pascal triangle

let's see :

here's your example

g h i

d e f

a b c

we create a tree starting at (a) point and then going up/right from every

item (if there's way up/right). check this tree out :

start ___________(a)__________

/ \

___(b)____ ___(d)____

/ \ / \

__(e)__ __(c)__ __(e)__ __(g)__

/ \ / \ / \ / \

(f) (h) (f) nil (h) (f) (h) nil

/ \ / \ | \ / \ | / \

(i) nil nil (i) nil (i) (i) nil | (i) nil

/ \

nil (i)

from that tree you must see (if you're not blind, and i think you're not)

that there're only 6 paths ending at the final (i) point, and you obviously

see the paths themselves

now got it?

about your comment about only integers or strings

there are several solutions :

1) write the tree yourself with two coordinates

2) string "4 3" stands for x=4, y=3

3) use longints instead of integers (if you want big x,y) and store

x in the lower word and y in the higher (or vice versa, as you wish)

in any case, any of these solutions are quite useful

i'd recommend you 1), but if you're in hurry, the better would be 3)

ask any questions if you got them

(sorry jeck.... :-))

lets take the exmple.

it is clear that the path consist

of two steps up and two steps right.

lets say that 0 - represents up

1 - represent right.

for 3*3 grid there are 4 steps paths.

lets translate your solution:

g--h--i

| | |

d--e--f

| | |

a--b--c

yields 6 paths

a 0 d 0 g 1 h 1 i

a 0 d 1 e 1 f 0 i

a 1 b 1 c 0 f 0 i

a 1 b 0 e 1 f 0 i

a 0 d 1 e 0 h 1 i

a 1 b 0 e 0 h 1 i

we got a four digits binary number

with the rule that the number

of one's is Equal to the number of zero's. (and it makes sence !)

(just omit all other numbers...)

so:

D = num of digits M+N-2

range of numbers 2^(D-1) - 2^D-1

to find digit is very simple

(divide with 2 until you get 0, and the reminder is the digit...)

AND no need need with more the a simple

loop inside a loop !!!

Yair

As in your example there are m X n(3 X 3) lines.

BY any means if you use (m-1) ups and (n-1) rights then you

are at the destination.

Hence the problem reduces to just an array manupulation

with fixed number of U(ups) and fixed number of R(rights)

All possible combinations of U and R is the answer.

thus in your example m=2 and n=2

hence UURR URUR URRU RRUU RURU RUUR

are the combinations.

I will need some more time to code it.

anyway, a way of doing it is:

1) generate a starting string consisting of all U's and R's separated:

eg. UUURR

2) starting from the right of the string, look for the first R, (let the number of U's skipped be N), and the first U to the left of the R (this U is called "the U")

3) advance "the U" one space to the right, and put the N U's that u skipped to "the U"'s immediate right...

4) this is a solution

5) repeat from (2) until there are no more U's on the left of the first R (ie. RRUUU)...

UUURR

then, N = 0, u advance "the U" (which is the 3rd character)

UURUR

then, N=0 still, u advance "the U" (4th character)

UURRU

then, N=1, u advance "the U" (2nd character) and put the 1 Us to its immediate right:

URUUR

and so on... it's the same sequence as the one i proposed earlier (i think)

suppose the string S is the start string... with Us to the left and Rs to the right; i, j, k all integers

while true do begin

{S contains a solution here}

i := Length(S);

j := 0;

while (S[i] <> 'R') do begin

S[i]:='R';

dec(i);

inc(j);

end;

while ((i > 0) and (S[i] <> 'U')) do dec(i);

if (i = 0) then break;

S[i] := 'R';

for k := i+1 to i+1+j do S[k] := 'U';

end;

equal to M-1 and the number of zero's is N-1...

I think running on integers is

much easier then strings.

> hey sucker, don't call me jeck

we don't use this kind of language here,

but there are other forums on the web that you may.

I am sorry, its a typo.

Yair

how're u gonna generate ur numbers? by running thru all 2^(m+n-2) numbers?

what if (m+n-2) is too large?

if u're talking about an integer array, i don't think there's a great deal of time savings from a string...

In your example, it is not possible to create the array of the points travelled (ie: (1,1),(2,1), etc) unless you create another loop incrementing X or Y respectivly.

_lychee_ & sumant,

In your example it appears to be the same problem that I have with yairy's answer.

instead of printing the binaric number,

scan its digits.

keep coord. indexes of the matrix corner.

print the value they point to and increase the proper

(x/y) index value according to the digit.

Yair

Yes,

a simple FOR command.

>how're u gonna generate ur numbers? by running thru all 2^(m+n-2) numbers?

Yes,

you can solve it in a iterative mode or recursive mode

but anyway this the Range of solutions.

any solution work as hard.

>what if (m+n-2) is too large?

>if u're talking about an integer array, i don't think there's a great deal of time savings from a string...

Well, the number of solutions in order of 2^(m+n-2).

When this value (m-n-2) equals 30

you have 2^30 = 1,000,000,000 possible solutions.

so I guess running on large scale matrixes

(over 32 ==> number of bits in a WORD)

is not too pratical in terms of TIME (~4*10^9).

one can use 64 bits word (most OS's supports that)

and really can be sure.

another way is to two, four intergers....

Yair

program grid;

uses crt;

const C = 20;

var a : array[1..C] of char;

i,row,col,m,n,Rs,Us,count : integer;

begin

clrscr;

write('Enter Horizontal lines: ');

readln(row);

write('Enter Vertical lines: ');

readln(col);

if (row < 2) or (col < 2) then

begin

write('Invalid input.');

halt;

end;

count:=1;

for i:=1 to (row-1) do a[i]:='U';

for i:=i+1 to (row-1) + (col-1) do a[i]:='R';

writeln(count:3,' st Combination: ',a);

while true do

begin

m:=(row-1)+(col-1);

Us:=row-1;

Rs:=col-1;

while true do

begin

if a[m]='R' then

begin

m:=m-1;

if m=0 then break;

Rs:=Rs-1;

end

else if Rs < (col-1) then

begin

a[m]:='R';

Rs:=Rs+1;

m:=m+1;

Us:=Us-1;

break;

end

else

begin

m:=m-1;

Us:=Us-1;

end;

end;

if m=0 then break;

while (Rs < (col-1)) or (Us < (row-1)) do

begin

if Us < (row-1) then

begin

a[m]:='U';

Us:=Us+1;

m:=m+1;

end

else

begin

a[m]:='R';

m:=m+1;

Rs:=Rs+1;

end;

end;

count:=count+1;

writeln(count:3,' th Combination: ',a)

end;

write('Press any key to continue...');

readkey;

end.

given the turnings made it is definitely possible (and trivial) to get the coordinates out... i'm sure u can code it...

yairy:

the number of solutions is definitely NOT on the order of 2^(m+n-2).... it is on the order of (m+n-2)C(n-1)... potentially MUCH less than 2^(m+n-2)... take M=1000000 and N=1 for eg... ur algo will take ages 2^999999 but there's only 1 path...

sorry but i think that going through all the numbers is REALLY not efficient at all...

You are right about the order remark.

I been thinking about a different approach:

make an array with M-1 1's and N-1 0's.

for example M=5, n=3:

111100

now DON'T count the array.

just run all PERMUTATIONS of it.

All Premutations ar leagle paths

(because the number of 1's and 0's remains...)

AND you don't do ANY extra work.

I think its the best one get for this problem.

Yair

pls read them... they're mostly about permutations =)... or whatever u choose to call them...

If the grid has 2 horiz lines i.e. one row and N vertical lines i.e. (N-1) columns then answer is (N-1) not 1.

sorry then... just that ur algo is about the same as mine... u can read my algo if u want and compare and see... :>

urm... what i mean by 1 row is 1 horizontal line (logical since travel is along lines)... like i take 3x3 in the qn to mean 3 rows and 3 cols...

so 1 row means 1 answer

Thank you all for your help. scrapdog, the points are yours.

But I should mention that I made a typo above:

if (x+1) <= width then

traverse(x+1,y1);

if (y+1) <= height then

traverse(x,y+1);

The "y1" should be "y". But I'm sure you've already figured that out.

if (x=width) and (y=height) then begin

for i := 1 to n do write('(',x_coordinates[i]

',',y_coordinates[i],') ');

writeln;

inc(count);

Shouldn't the x=width and y=height be <= instead? When I remove the diagonal movement code, the only point it prints is the final one. (the top right corner)

Besides that, everything else seems fine!

The typo wasn't changing the = to <= it was changing:

if (x+1) <= width then

traverse(x+1,y1);

if (y+1) <= height then

traverse(x,y+1);

to:

if (x+1) <= width then

inc(N);

traverse(x+1,y1);

dec(N);

if (y+1) <= height then

inc(N);

traverse(x,y+1);

dec(N);

Not sure if you're willing to help me with one more problem I'm having with your code...

You declare your array using [1..width+height] while width+height are constants... but when I change them to user defined variables, I can't seem to get it to work. Would it work if I declared the array in the procedure instead?

Nope...the sizes of the array must be declared at compile-time.

This is an easy problem to fix though. Change the constants to

const

max_width = (some number);

min_width = (some number);

then declare your array like this:

[1..max_width + max_height]

max_width and min_width are pretty self explanatory...they specify the upper limits that you will allow the user to enter. The declaration will allocate the maximum number of bytes you will need for a grid max_width x max_height in any case.

Continue using width and height as variables, and the program should work correctly.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

You would use a binary tree of a sort, but there would be no need to declare any sort of structure for one. By using recursion and testing both (or all three) possible alternatives at each position, the tree will be built on the stack.

The constants width and height below are self-explanatory. The bottom-left position is (1,1). Note that I used two separate arrays to store the x and y coordinates for convenience purposes (it could be done with only one array storing a structure with both coordinates, for example). The variable n is the index to the end of the array. Before a new position is traversed, n is incremented. When execution returns from that point, n is decremented again.

The code below assumes that you can travel up, right, or diagonally (up and right in one move). This can be changed to accomodate whatever rules you need...I used the two loops from 0 to 1, and didn't test when both offsets were 0 (testing the same position over and over will result in a stack overflow).

The count variable simply keeps track of how many successful paths were found.

If you have any questions at all about how this works, let me know.

const

width = 8;

height = 8;

var

x_coordinates :array[1..width+height] of integer;

y_coordinates :array[1..width+height] of integer;

n :integer;

count :integer;

procedure traverse(x, y :integer);

var

i,x1,y1,x2,y2 :integer;

begin

x_coordinates[n] := x;

y_coordinates[n] := y;

if (x=width) and (y=height) then begin

for i := 1 to n do write('(',x_coordinates[i]

',',y_coordinates[i],') ');

writeln;

inc(count);

end else begin

for x1 := 0 to 1 do

for y1 := 0 to 1 do begin

if (x1 + y1) > 0 then begin

x2 := x + x1;

y2 := y + y1;

if (x2 <= width) and (y2 <= height) then begin

inc(n);

traverse(x2,y2);

dec(n);

end;

end;

end;

end;

end;

begin

count := 0;

n := 1;

traverse(1,1);

writeln ('total paths ',count);

end.