You will write a program that will take an input file that describes the land, the starting point,

potential lodges we can relax in, and some other characteristics for our skier. For each lodge

location, you should find the optimal (shortest) safe path from the starting point to that target

lodge. A path is composed of a sequence of elementary moves. Each elementary move consists

of moving the skier from their current position to one of its 8 neighbors. To find the solution you

will use the following algorithms:

- Breadth-first search (BFS)

- Uniform-cost search (UCS)

- A* search (A*).

Your algorithm should return an optimal path, that is, with shortest possible journey cost.

Journey cost is further described below and is not equal to geometric path length. If an optimal

path cannot be found, your algorithm should return FAIL as further described below.

Terrain map

We assume a terrain map for the mountain is specified as follows:

A matrix with H rows (where H is a strictly positive integer) and W columns (W is also a strictly

positive integer) will be given, with a value E (an integer number, to avoid rounding problems)

specified in every cell of the WxH map. If E is a negative integer, this means there is a tree of

height |E| in that cell. If E is a positive integer, the value represents the elevation of that cell. For

example:

10 20 -30

12 13 40

is a map with W=3 columns and H=2 rows, and each cell contains an E value (in arbitrary units).

By convention, we will use North (N), East (E), South (S), West (W) as shown above to describe

motions from one cell to another. In the above example, elevation E in the North-West (NW)

corner of the map is 10, and it is 40 in the South-East (SE) corner, which means our skier will

spend more stamina to move into the SE corner than the NW corner.

Every skier will have a stamina value S that determines whether they can climb up certain

elevations. A move from E = 20 to E = 40 is only allowed if a skiers stamina is higher than or

equal to 40 20 = 20. Important Note: Stamina remains as a constant value.

Notice that there is a tree of height 30 in the NE corner. If a cell contains a tree, there are a few

factors that determine whether a move into that cell is allowed:

- If your current E is higher than or equal to tree height |E|, you are allowed to move into

the cell. In this case, we imagine the tree is covered with snow of height |E|. Therefore,

if our tree is height 30 as above, it would be allowed to move into that cell from the cell

with elevation 40, but not from others.

- If your current E is lower than the tree height |E|, a move into that cell is not allowed

from your current cell. Note that your stamina (or momentum) does not change whether

a move like this is allowed.

To help us distinguish between your three algorithm implementations, you must follow the

following conventions for computing operational path length:

- Breadth-first search (BFS)

In BFS, each move from one cell to any of its 8 neighbors counts for a unit path cost of 1. You do

not need to worry about the elevation levels or about the fact that moving diagonally (e.g., North-

East) is actually a bit longer than moving along the North to South or East to West directions.

However, you still need to make sure the move is allowed by checking how steep the move is

(depends on the skiers stamina) or whether a tree is involved. Therefore, any allowed move

from one cell to an adjacent cell costs 1.

- Uniform-cost search (UCS)

When running UCS, you should compute unit path costs in 2D. Assume that cells center

coordinates projected to the 2D ground plane are spaced by a 2D distance of 10 North-South and

East-West. That is, a North or South or East or West move from a cell to one of its 4-connected

neighbors incurs a unit path cost of 10, while a diagonal move to a neighbor incurs a unit path

cost of 14 as an approximation to 10 when running UCS. You still need to make sure the

move is allowed, in the same way you did for BFS.

- A* search (A*).

When running A*, you will have modified rules for allowed moves AND you should compute an

approximate integer unit path cost for each move according to how the elevation of the terrain

changes. We will explain these rules using elevations Ecurr (current cell elevation), Enext (potential

next cell elevation), and Eprev (previous cell elevation), as well as stamina S (given as input) and

momentum M (defined below).

Allowed moves for A*: For running A*, we modify whether a move is allowed by considering

momentum (M), that is whether we gained some speed by going down in elevation in our most

recent move. If we are currently at a cell with Ecurr, whether we are allowed to go into a cell Enext

is determined by whether our momentum M going from Eprev to Ecurr can assist us. We will define

M as follows:

M = &

max (0, !"#$ %&""), ('#() %&"") > 0

0, ('#() %&"") 0

That is, when we are going down from Eprev to Ecurr and then up from Ecurr to Enext, momentum M

is > 0 and will possibly assist us in reaching cells with higher Enext elevations. If the next move is

going up in elevation (Enext > Ecurr), a move will only be allowed if (Enext <= Ecurr + S + M). For

BFS/UCS, this rule was (Enext <= Ecurr + S). M = 0 initially at the starting position. Note how in all

cases other than going down from Eprev to Ecurr and then up from Ecurr to Enext, momentum M is 0

according to the above definition. Note that momentum does not accumulate across multiple

moves. Only the latest Eprev to Ecurr are considered when computing M.

If a tree is involved, the rules to determine whether a move is allowed do not change from the

BFS/UCS cases. If you are allowed to move into a cell with a tree, it acts as land with elevation

|E| from then on.

Path cost for A*: You should also compute an approximate integer unit path cost for each move

for A*, which is now approximately 3D. The cost of a move is computed by considering both the

horizontal move distance as in the UCS case (unit cost of 10 when moving North to South or East

to West, and unit cost of 14 when moving diagonally) and the change in elevation levels of the

land. The cost C for the move is hence defined as follows:

C = (Horizontal Move Distance) + (Elevation Change Cost)

Where the Elevation Change Cost is defined as follows:

Elevation Change Cost = &

0, ('#() %&"")

(0, '#() %&"" ), ('#() %&"") >

Thus, intuitively, the elevation change cost is how much we are going uphill, possibly minus how

much momentum we have from going downhill on the previous move.

Examples:

- If our previous cell was Eprev = 20 and our current cell is Ecurr = 8, we have M = 12. If our

stamina is 30, we are allowed to go into a cell with Enext up to Ecurr + M + S = 8 + 12 + 30 =

50. Assume we choose a cell with Enext = 25. If were moving diagonally, our path cost

becomes: 14 (Move Distance) + (25 8 12 = 5) (Elevation Change Cost) = 19.

- If our previous cell was Eprev = 20 and our current cell is Ecurr = 25, we have M = 0. If our

stamina is 15, we are allowed to go into, for example, a cell with Enext = 35 (since 35 25

< 0 + 15). If were moving South, our path cost becomes: 10 (Move Distance) + (35 25)

(Elevation Change Cost) = 20.

- If our current cell is Ecurr = 40 and our next cell is Enext = 15, the move is allowed since we

are going downhill. If were moving East, our path cost becomes: 10 (Move Distance) + (0)

(Elevation Change Cost) = 10.

- If our previous cell was Eprev = 12 and our current cell is Ecurr = -5, we have M = 7, since we

treat tree cells as |E| elevation once we move into them. If our stamina is 5, we can go

into, for example, a cell with Enext = 30 (since 30 12 < 7 + 5). If were moving SW, our

path cost becomes: 14 (Move Distance) + (30 5 7) (Elevation Change Cost) = 32.

Remember: In addition to computing the path cost, you also need to design an admissible

heuristic for A* for this problem.

Input: The file input.txt in the current directory of your program will be formatted as follows:

First line: Instruction of which algorithm to use, as a string: BFS, UCS or A*

Second line: Two strictly positive 32-bit integers separated by one space character, for

W H the number of columns (width) and rows (height), in cells, of the map.

Third line: Two positive 32-bit integers separated by one space character, for

X Y the coordinates (in cells) of the starting position for our skier. 0 X W-1

and 0 Y H-1 (that is, we use 0-based indexing into the map; X increases when

moving East and Y increases when moving South; (0,0) is the North West corner

of the map). Starting point remains the same for each of the N lodge sites below

and will never contain a tree.

Fourth line: Positive 32-bit integer number for the stamina S of the skier which determines

how advanced our skier is. S will be used to compute allowed moves if were

moving into a non-tree cell.

Fifth line: Strictly positive 32-bit integer N, the number of lodges on the mountain.

Next N lines: Two positive 32-bit integers separated by one space character, for

X Y the coordinates (in cells) of each lodge site. 0 X W-1 and 0 Y H-1 (that

is, we again use 0-based indexing into the map). These N target lodge sites are

not related to each other, so you will run your search algorithm on each lodge

site and write the result to the output as specified below. We will never give you

a lodge site that is the same as the starting point. They will never contain a tree.

Next H lines: W 32-bit integer numbers separated by any numbers of spaces for the M values

of each of the W cells in each row of the map. Each number can represent the

following cases:

E >= 0, snowy mountain slope with elevation E

E < 0, tree of height |E| that might be covered with snow depending on

the elevation we approach it from

For example:

A*

8 6

4 4

5

2

2 1

6 3

-10 40 34 21 42 37 18 7

-20 10 5 27 -6 5 2 0

-30 8 17 -3 -4 -1 0 4

-25 -4 12 14 -1 9 6 9

-15 -9 46 6 25 11 31 -21

-5 -6 -3 -7 0 25 53 -42

In this example, on an 8-cells-wide by 6-cells-high grid, we start at location (4, 4) highlighted in

green above, where (0, 0) is the North West corner of the map. The maximum stamina that the

skier has is 5 (in arbitrary units which are the same as for the E values of the map). We have 2

possible lodge sites, at locations (2, 1) and (6, 3), both highlighted in red above. The map of the

land is then given as six lines in the file, with eight E values in each line, separated by spaces.

The negative values are trees.

Output: The file output.txt which your program creates in the current directory should be

formatted as follows:

N lines: Report the paths in the same order as the lodge sites were given in the input.txt

file. Write out one line per target lodge. Each line should contain a sequence of

X,Y pairs of coordinates of cells visited by the skier to travel from the starting point

to the corresponding lodge for that line. Only use a single comma and no space to

separate X,Y and a single space to separate successive X,Y entries.

If no solution was found (lodge was unreachable by the skier from the given

starting point), write a single word FAIL in the corresponding line. Our skier needs

a rescue in this case. J

For example, output.txt may contain:

4,4 3,3 2,2 2,1

4,4 5,3 6,3

Here the first line is a sequence of five X,Y locations which trace the path from the starting

point (4,4) to the first settling site (1,1). Note how both the starting location and the settling

site location are included in the path. The second line is a sequence of three X,Y locations which

trace the path from the starting point (4,4) to the second possible settling site (6,3).

The first path looks like this:

-10 40 34 21 42 37 18 7

-20 10 5 27 -6 5 2 0

-30 8 17 -3 -4 -1 0 4

-25 -4 12 14 -1 9 6 9

-15 -9 46 6 25 11 31 -21

-5 -6 -3 -7 0 25 53 -42

With the starting point shown in green, the lodge sites in red, and each traversed cell in between

in yellow. Note how one could have thought of a perhaps shorter path: 4,4 4,3 3,2 2,1

(general lower |E| values). But this was not allowed, since once we get to position 4,3 we are

blocked by the tree in 3,2.

And the second path looks like this:

-10 40 34 21 42 37 18 7

-20 10 5 27 -6 5 2 0

-30 8 17 -3 -4 -1 0 4

-25 -4 12 14 -1 9 6 9

-15 -9 46 6 25 11 31 -21

-5 -6 -3 -7 0 25 53 -42

Notes and hints:

- Please name your program homework.xxx where xxx is the extension for the

programming language you choose (py for python, cpp for C++11, and java for

Java).

- Likely (but no guarantee) we will create 15 BFS, 15 UCS, and 20 A* text cases.

- There is no limit on input size, number of target lodges, etc. other than specified above

(32-bit integers, etc.). However, you can assume that all test cases will take < 30 secs to

run on a regular laptop.

Example 1:

For this input.txt:

BFS

2 2

0 0

5

1

1 1

0 -10

-10 -20

the only possible correct output.txt is:

FAIL