!Anand Oza

!March 26, 2006

!Contest #4 - PATHWAYS

!Takoma Park Middle School

!Intermediate Division

DIM grid(1,1)

DIM nodes(0,2)

LINE INPUT PROMPT "Enter the coordinates of the nodes--->" : nodeinput$

DO

LET rc$ = ""

LET cc$ = ""

DO WHILE nodeinput$[1:1] <> ","

LET rc$ = rc$ & nodeinput$[1:1]

LET nodeinput$ = nodeinput$[2:LEN(nodeinput$)]

LOOP

LET nodeinput$ = nodeinput$[2:LEN(nodeinput$)]

DO WHILE nodeinput$[1:1] <> ","

LET cc$ = cc$ & nodeinput$[1:1]

LET nodeinput$ = nodeinput$[2:LEN(nodeinput$)]

LOOP

LET nodeinput$ = nodeinput$[2:LEN(nodeinput$)]

LET node=node+1

LET r = VAL(rc$)

LET c = VAL(cc$)

IF r > SIZE(grid,1) THEN MAT redim grid(r,SIZE(grid,2))

IF c > SIZE(grid,2) THEN MAT redim grid(SIZE(grid,1),c)

MAT REDIM nodes(node,2)

LET nodes(node,1) = r

LET nodes(node,2) = c

LOOP UNTIL nodeinput$[1:1]="0"

FOR X = 1 TO node

LET grid(nodes(X,1),nodes(X,2)) = X

NEXT X

FOR X = 1 TO SIZE(grid,1)

FOR Y = 1 TO SIZE(grid,2)

IF grid(x,y)>0 THEN PRINT "X "; ELSE PRINT "- ";

NEXT Y

PRINT

NEXT X

DIM edges$(1)

MAT REDIM edges$(node)

FOR X = 1 TO node

IF nodes(X,1) <> 1 THEN

IF grid(nodes(X,1)-1,nodes(X,2)) > 0 THEN LET edges$(X)=edges$(X) & STR$(grid(nodes(X,1)-1,nodes(X,2))) & ","

END IF

IF nodes(X,1) <> SIZE(grid,1) THEN

IF grid(nodes(X,1)+1,nodes(X,2)) > 0 THEN LET edges$(X)=edges$(X) & STR$(grid(nodes(X,1)+1,nodes(X,2))) & ","

END IF

IF nodes(X,2) <> 1 THEN

IF grid(nodes(X,1),nodes(X,2)-1) > 0 THEN LET edges$(X)=edges$(X) & STR$(grid(nodes(X,1),nodes(X,2)-1)) & ","

END IF

IF nodes(X,2) <> SIZE(grid,2) THEN

IF grid(nodes(X,1),nodes(X,2)+1) > 0 THEN LET edges$(X)=edges$(X) & STR$(grid(nodes(X,1),nodes(X,2)+1)) & ","

END IF

NEXT X

DIM path(1)

MAT REDIM path(node)

FOR program = 2 TO 5

PRINT

INPUT prompt "Enter the starting node--->" : r1,c1

INPUT prompt "Enter the ending node----->" : r2,c2

LET start=grid(r1,c1)

LET end=grid(r2,c2)

PUBLIC totalpaths

LET totalpaths=0

DECLARE FUNCTION CheckPath

IF CheckPath(path(),edges$(),start,1,end) = 1 THEN

LET totalpaths=totalpaths+1

END IF

IF totalpaths=0 THEN

PRINT "NONE - There are no paths from (";r1;",";c1;") to (";r2;",";c2;")"

ELSE

PRINT totalpaths;"- There are";totalpaths;"paths from (";r1;",";c1;") to (";r2;",";c2;")"

END IF

PRINT

NEXT program

END

FUNCTION CheckPath(path(),edges$(),chosen,nextstep,end)

DECLARE PUBLIC totalpaths

DIM choices(0)

LET path(nextstep) = chosen

LET commachoices$ = edges$(path(nextstep))

DO WHILE LEN(commachoices$)>0

IF commachoices$[1:1] <> "," THEN

LET next$=next$ & commachoices$[1:1]

ELSE

MAT REDIM choices(SIZE(choices)+1)

LET choices(SIZE(choices))=VAL(next$)

LET next$ = ""

END IF

LET commachoices$ = commachoices$[2:LEN(commachoices$)]

LOOP

FOR X = 1 TO SIZE(choices)

LET usedup = 0

FOR Y = 1 TO SIZE(path)

IF path(y)=choices(x) THEN

LET usedup = 1

END IF

NEXT Y

IF usedup <> 1 THEN

IF choices(x)=end THEN

LET CheckPath=1

ELSE IF CheckPath(path(),edges$(),choices(x),nextstep+1,end) = 1 THEN

LET totalpaths = totalpaths + 1

END IF

END IF

NEXT X

END FUNCTION