## Description

1. Grid Walk (10 points)

https://www.hackerrank.com/contests/cst370-s19-hw5/challenges/grid-walk

Given a grid with obstacles, we want to find the shortest path from a starting position to

an ending position using Dijkstra’s algorithm. In this grid, you can move in all 8 directions:

Up, Down, Left, Right, and the 4 diagonals.

Input

• The first line contains an integer, n, the dimension of the nxn grid.

• The second line contains two space-separated integers, the starting position in the

order row column.

• The third line contains two space-separated integers, the ending position in the order

row column.

• The next n lines contain the space separated row. Each element is either a O indicating

no obstacle or a X indicating an obstacle.

Constraints

You can assume a path exists (and therefore that the starting and ending positions are Os)

and that the starting and ending positions are in-bounds.

Page 3 of 12

CST 370 Homework 5 April 16, 2019

Output

The output contains a single line with an integer, the length of the shortest path (where

each move, whether up, down, left, right, or diagonal) counts as 1 step.

Sample Input 1 Sample Output 1

4

0 2

3 1

X X O X

X X O O

X X X O

X O O O

4

Sample Input 2 Sample Output 2

6

0 1

5 2

O O O O O X

X X O X O O

O O X O O X

X O O O O O

O O X X X O

X O O X O O

5

Page 4 of 12

CST 370 Homework 5 April 16, 2019

2. Heuristics (10 points)

https://www.hackerrank.com/contests/cst370-s19-hw5/challenges/heuristics

Given a grid with obstacles, we want to find the shortest path from a starting position to an

ending position. This time we’d like to use the A-Star algorithm. In this grid, you can only

move in four directions: up, down, left, right therefore the heuristic that we will use will be

the manhatten distance algorithm.

Input

• The first line contains an integer, n, the dimension of the nxn grid.

• The second line contains two space-separated integers, the starting position in the

order row column.

• The third line contains two space-separated integers, the ending position in the order

row column.

• The next n lines contain the space separated row. Each element is either a O indicating

no obstacle or a X indicating an obstacle.

Constraints

You can assume a path exists (and therefore that the starting and ending positions are Os)

and that the starting and ending positions are in-bounds.

Page 5 of 12

CST 370 Homework 5 April 16, 2019

Output

The output contains a single line with an integer, the length of the shortest path (where

each move, whether up, down, left, or right) counts as 1 step.

Sample Input 1 Sample Output 1

4

0 2

3 1

X X O X

X X O O

X X X O

X O O O

6

Sample Input 2 Sample Output 2

6

0 1

5 2

O O O O O X

X X O X O O

O O X O O X

X O O O O O

O O X X X O

X O O X O O

12

Page 6 of 12

CST 370 Homework 5 April 16, 2019

3. Elevations (15 points)

https://www.hackerrank.com/contests/cst370-s19-hw5/challenges/elevations

I like running to different places but hate running uphill. I have a number of typical routes

I run and I’d like to know the least elevation change it would take me to reach them. Help

me find the elevation change to get from my house to each of the places I run to, taking only

the routes I know. You will receive the list of pleces, the routes I know how to take, and the

elevation change per route.

Starter code

The code below will help you read input for this problem.

• C++: https://repl.it/@dsyang/Elevations-cpp

• Java: https://repl.it/@dsyang/Elevations-java

• Python: https://repl.it/@dsyang/Elevations-py

Input

• The first line will contain a location, my home.

• The next line will contain an integer, r, the number of routes I run.

• Finally, the last r lines will contain the routes, consisting of comma-separated endpoints

followed by the elevation change along that route.

Constraints

You cannot assume the graph is connected; there may be a place I cannot reach taking only

routes that I know.

Output

• The output will consist of n lines.

• each line consists of a place name (in alaphabetical order), followed by a colon, a space,

and the least elevation change to that place from my source.

• If there is no route to that place, print ”NONE” instead.

Page 7 of 12

CST 370 Homework 5 April 16, 2019

See the sample output section and hackerrank for concrete examples

Sample Input 1 Sample Output 1

Home

9

Bookworks , Home , 95

Bookworks , Aquarium , -50

Home , Aquarium , 150

Home , Starbucks , 12

Home , Beach , -100

Beach , Starbucks , 55

Aquarium , Bookworks , 50

Starbucks , Carmel , 200

Carmel , Home , -100

Bookworks : 200

Home : 0

Aquarium : 150

Starbucks : -45

Beach : -100

Carmel : 155

Page 8 of 12

CST 370 Homework 5 April 16, 2019

4. Optimizing Routes (15 points)

https://www.hackerrank.com/contests/cst370-s19-hw5/challenges/optimizing-routes

I have my set ways of traveling to places I visit often. However, I’m curious if my routes are

actually the best routes according to maps. Determine the difference in my route and the

supposed best route for each of my destinations.

subsection*Starter code The code below will help you read input for this problem.

• C++: https://repl.it/@dsyang/Optimizing-Routes-cpp

• Java: https://repl.it/@dsyang/Optimizing-Routes-java

• Python: https://repl.it/@dsyang/Optimizing-Routes-py

Input

• The first line will contain a location, my home.

• The next line will contain an integer n, the number of places I visit often enough to

have a set route, followed by how long my route to that place takes.

• The next line will contain an integer, r, the number of roads.

• Finally, the last r lines will contain the roads, consisting of comma-separated endpoints

followed by the time it takes to travel the road.

Constraints

You can assume all the weights are positive (it takes time to travel a road) and that all

locations have unique names. You may choose which appropriate path-finding algorithm to

use to solve this problem.

Output

• The output will consist of n lines.

• Each line consists of a destination I visit often, followed by a space, followed by either

”FASTEST” if my route is equal to or faster than the recommended route. ”NO

PATH” if there is no recommended route from my home to that location. Or an

integer x representing how much faster the recommended route is.

• The n destinations will be ordered alphabetically, case-insensitive. This means Carmel

will come before CSUMB.

Page 9 of 12

CST 370 Homework 5 April 16, 2019

See the sample output section and hackerrank for concrete examples

Sample Input 1 Sample Output 1

Home

4

Bookworks , 9

CSUMB , 16

East Village , 6

Carmel Beach , 21

17

Presidio , Bookworks , 3

Presidio , Aquarium , 3

Presidio , Colton Hall , 2

Presidio , Home , 5

Home , Carmel Village , 17

Home , REI , 12

REI , CSUMB , 3

Home , CSUMB , 16

Home , East Village , 6

Home , 17 – Mile Drive , 10

Home , Colton Hall , 4

Home , Sushi Time , 10

CSUMB , Sushi Time , 7

Carmel Beach , 17 – Mile Drive , 12

East Village , Colton Hall , 5

Colton Hall , Home , 4

Carmel Village , Carmel Beach , 4

Bookworks NO PATH

Carmel Beach FASTEST

CSUMB 1

East Village FASTEST

Page 10 of 12

CST 370 Homework 5 April 16, 2019

5. Essential Services (15 points)

https://www.hackerrank.com/contests/cst370-s19-hw5/challenges/all-pairs

King’s Landing is trying to evaluate the quality of life of its citizens. One of the components

is the time it takes each citizen to get to every essential service. Given the citizens and

services, find the distance from each citizen to each service.

Starter code

The code below will help you read input for this problem.

• C++: https://repl.it/@dsyang/Essential-Services-cpp

• Java: https://repl.it/@dsyang/Essential-Services-java

• Python: https://repl.it/@dsyang/Essential-Services-py

Input

• The first line contains an integer, c, the number of citizens.

• The next c lines contain the citizens’ names.

• The next line contains an integer, s, the number of services.

• The next s lines contain the services’ names.

• The next line contains an integer, e, the number of direct routes.

• Each of the next e lines contains a direct route which consists of two comma-separated

entities (citizens or servies) and a time it takes to get from one to the other.

Constraints

You can assume all the weights are positive (it takes time to get from one place to the other)

and that all citizens and services have unique names.

Output

• The output will consist of c + 1 lines.

• The first line consists of the services in alphabetical order, space-separated.

• The next c lines consist of a citizen and their times from each service. You should have

s space-separated integers, the time from each service in alphabetical order, followed

by the citizen name (in alphabetical order).

Page 11 of 12

CST 370 Homework 5 April 16, 2019

See the sample output section and hackerrank for concrete examples

Sample Input 1 Sample Output 1

5

Cersei

Robert

Jamie

Qyburn

Tomin

2

Castle

Church

9

Castle , Robert , 15

Robert , Qyburn , 155

Robert , Tomin , 15

Castle , Tomin , 35

Qyburn , Church , 15

Robert , Jamie , 30

Jamie , Church , 115

Robert , Cersei , 300

Cersei , Church , 60

Castle Church

220 60 Cersei

45 115 Jamie

170 15 Qyburn

15 145 Robert

30 160 Tomin

Page 12 of 12