ghostdog74

January 6th, 2007, 06:23 PM

Seeing that the challenge has not been decided till now, i think i will post one taken from somewhere but simplified. If anyone has any better one or if its too difficult, let me know and i will re-edit/delete this post. Here goes

The problem:

We have a 4 x 4 square grids 1 through 16, from left to right, top to bottom.

Eg. 4x4 grid:

1 2 X 4

5 6 7 8

9 10 11 X

13 14 X 16

3 of these squares (3,12 and 15) contain obstacles, ( X above )

Find the longest(maximum) path one can go before he gets stuck with the following criteria

- Always start walking on grid 1, going either down or right.

- Can move in 4 directions: up, down, left, right.

- He cannot travel through the obstacle (X) or a previous grid

- He moves straight until he reaches a square he can not travel through or the edge.

-When he cannot move straight, he turns either left or right.

-When he cannot move left, right, or straight, he stops.

For a start, we just solve for obstacles at 3,12,15. The maximum path I could find is

1->2->6->5->9->13->14->10->11->7->8->4 so the final answer is 12 grids (?I may be wrong.?).

The challenge is to find an algorithm to calculate this path.

Its good to print the path taken too..

You can also solve for straight line only, as some of you have pointed out its more simple.

eg.

For situation of "totally no obstacles" using straight line (simpler) rule, i can find only 2 solutions (correct me if i am wrong):

a) 1->2->3->4->8->12->16->15->14->13->9->5->6->7->11->10

b) 1->5->9->13->14-15->16->12->8>4->3->2->6->10->11->7

So for the above obstacle example at 3,12, 15 , using straight line rule, the solution seeem to be

1->5->9->13->14->10->6->2 (correct me if i miss something)

any diagonals not allowed

1->6->11->16->x->x->x ......<---not allowed

The problem:

We have a 4 x 4 square grids 1 through 16, from left to right, top to bottom.

Eg. 4x4 grid:

1 2 X 4

5 6 7 8

9 10 11 X

13 14 X 16

3 of these squares (3,12 and 15) contain obstacles, ( X above )

Find the longest(maximum) path one can go before he gets stuck with the following criteria

- Always start walking on grid 1, going either down or right.

- Can move in 4 directions: up, down, left, right.

- He cannot travel through the obstacle (X) or a previous grid

- He moves straight until he reaches a square he can not travel through or the edge.

-When he cannot move straight, he turns either left or right.

-When he cannot move left, right, or straight, he stops.

For a start, we just solve for obstacles at 3,12,15. The maximum path I could find is

1->2->6->5->9->13->14->10->11->7->8->4 so the final answer is 12 grids (?I may be wrong.?).

The challenge is to find an algorithm to calculate this path.

Its good to print the path taken too..

You can also solve for straight line only, as some of you have pointed out its more simple.

eg.

For situation of "totally no obstacles" using straight line (simpler) rule, i can find only 2 solutions (correct me if i am wrong):

a) 1->2->3->4->8->12->16->15->14->13->9->5->6->7->11->10

b) 1->5->9->13->14-15->16->12->8>4->3->2->6->10->11->7

So for the above obstacle example at 3,12, 15 , using straight line rule, the solution seeem to be

1->5->9->13->14->10->6->2 (correct me if i miss something)

any diagonals not allowed

1->6->11->16->x->x->x ......<---not allowed