Solved

Grid Maze Problem

Posted on 2000-03-09
47
494 Views
Last Modified: 2006-11-17
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
0
Comment
Question by:Kory
  • 11
  • 9
  • 7
  • +6
47 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 2603593
Think of Pascal's Triangle
0
 
LVL 47

Expert Comment

by:dbrunton
ID: 2603653
For each step you are about to take there are two choices, up or to the right.

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.
0
 
LVL 2

Expert Comment

by:_lychee_
ID: 2603686
well... another way of thinking of it is just place R ups in a path of length R+C (R x C grid) so... (R+C) choose R
0
 
LVL 2

Expert Comment

by:_lychee_
ID: 2603690
oops (R+1) x (C+1) grid
0
 
LVL 3

Expert Comment

by:Alisher_N
ID: 2603977
is there a maximum values for M and N ?
0
 
LVL 4

Expert Comment

by:jack_p50
ID: 2605298
i think the most acceptable solution is to build a binary tree where nodes
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
0
 
LVL 4

Expert Comment

by:jack_p50
ID: 2605305
if you REALLY want a program, i think i could write it, but i'm quite busy for that time, so please do it yourself using the simple algorithm i gave to you..
0
 

Author Comment

by:Kory
ID: 2606938
Jack,
  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
0
 
LVL 47

Expert Comment

by:dbrunton
ID: 2607217
An array of char.  If you have a 12 by 12 array this is a 144 bytes.  If you have unusual arrays like 200 by 200 it will get very large, in this case an array of 40,000 bytes.
0
 

Author Comment

by:Kory
ID: 2607795
Jack_p50,
  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.
0
 
LVL 5

Accepted Solution

by:
scrapdog earned 400 total points
ID: 2608759
This is how I would go about the problem:

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.
0
 
LVL 5

Expert Comment

by:scrapdog
ID: 2608761
>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.

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.)

0
 
LVL 5

Expert Comment

by:scrapdog
ID: 2608764
by the way, if you rules do not allow diagonal movement (which I apparently overlooked), you can replace the for x1 = ... block with the following code:

if (x+1) <= width then
  traverse(x+1,y1);
if (y+1) <= height then
  traverse(x,y+1);
0
 
LVL 2

Expert Comment

by:_lychee_
ID: 2609031
if u have R rows and C columns, then to get to the top right using only up and right, u obviously need
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
0
 
LVL 4

Expert Comment

by:jack_p50
ID: 2609886
yes of course it would say you the paths
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?
0
 
LVL 4

Expert Comment

by:jack_p50
ID: 2609891
by the way, call me Jack

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
0
 
LVL 2

Expert Comment

by:yairy
ID: 2610458
I would do a simpler soloution
(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














0
 
LVL 3

Expert Comment

by:sumant032199
ID: 2610583
I was not able to "ANSWER" this question. But I think my solution is on right and simplest track. Hope you like this.

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.
0
 
LVL 2

Expert Comment

by:_lychee_
ID: 2610652
sigh... datz my soln actually (read up)...

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)...
0
 
LVL 2

Expert Comment

by:_lychee_
ID: 2610655
so, first u get
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)
0
 
LVL 2

Expert Comment

by:_lychee_
ID: 2610669
i think this'll work (haven't tested it tho...):

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;
0
 
LVL 4

Expert Comment

by:jack_p50
ID: 2611072
hey sucker, don't call me jeck
0
 
LVL 4

Expert Comment

by:jack_p50
ID: 2611083
i suppose that tree is maybe not most fast but most clear and obvious solution
0
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 
LVL 2

Expert Comment

by:yairy
ID: 2611423
Ofcourse, the number of one's should be
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

0
 
LVL 2

Expert Comment

by:_lychee_
ID: 2611478
running on integers is much easier??

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...
0
 

Author Comment

by:Kory
ID: 2611728
yairy,
  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.
0
 
LVL 2

Expert Comment

by:yairy
ID: 2611755
I disagree with you.

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
0
 
LVL 2

Expert Comment

by:yairy
ID: 2611760
can you explain why did you reject my answer ?
0
 
LVL 2

Expert Comment

by:yairy
ID: 2611948
>running on integers is much easier??
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
0
 
LVL 3

Expert Comment

by:sumant032199
ID: 2611987
This is the simplest implimentation of my alg. This program works just fine and gives correct output.

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.
0
 
LVL 3

Expert Comment

by:sumant032199
ID: 2611998
Binary tree is really an expensive way (in memory point of view) I think.
0
 
LVL 2

Expert Comment

by:yairy
ID: 2612354
I don't think giving her/him the full solution is to the point. It shouldn't be our task.

0
 
LVL 2

Expert Comment

by:_lychee_
ID: 2612484
kory:
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...

0
 
LVL 2

Expert Comment

by:_lychee_
ID: 2612505
sumant:
isn't ur code essentially equivalent to mine? (the U-R generation part?)
0
 
LVL 2

Expert Comment

by:yairy
ID: 2612667
Lychee:
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
0
 
LVL 2

Expert Comment

by:yairy
ID: 2612673
How to do permutations ?

take it as a challenge
(recursive definition...)

:-)
0
 
LVL 2

Expert Comment

by:_lychee_
ID: 2612888
have u been reading the other comments?

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

Expert Comment

by:sumant032199
ID: 2613352
To lychee, your U and R is just the notation I took that notation only what is wrong in it? My algo and program is original which is more important.
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.
0
 
LVL 2

Expert Comment

by:_lychee_
ID: 2613518
sumant:
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
0
 

Author Comment

by:Kory
ID: 2613762
I have looked at all the comments and possible answers that you all have given. I have tested them all, and scrapdog's answer was the first one in the list that appears to answer the question.

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

Expert Comment

by:scrapdog
ID: 2614473
Thanks!

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.
0
 

Author Comment

by:Kory
ID: 2614726
I also believe you made a mistake with:
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!
0
 
LVL 5

Expert Comment

by:scrapdog
ID: 2616893
Actually, it is supposed to be x=width and y=height, because if and only if this is true, the end of the path has been reached.  If you got it to work otherwise, however, I won't dispute it.
0
 

Author Comment

by:Kory
ID: 2620801
Re: my last comment...

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?
0
 
LVL 5

Expert Comment

by:scrapdog
ID: 2626287
>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.
0
 
LVL 4

Expert Comment

by:jack_p50
ID: 2627567
to yairy
if it's a typo, then sorry me
peace to you...
0
 
LVL 2

Expert Comment

by:yairy
ID: 2628121
:-)
0

Featured Post

What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

Join & Write a Comment

Learn to move / copy / export exchange contacts to iPhone without using any software. Also see the issues in configuration of exchange with iPhone to migrate contacts.
A procedure for exporting installed hotfix details of remote computers using powershell
Internet Business Fax to Email Made Easy - With eFax Corporate (http://www.enterprise.efax.com), you'll receive a dedicated online fax number, which is used the same way as a typical analog fax number. You'll receive secure faxes in your email, fr…
Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.

757 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now