Problems

1 Grid Walk	10 points
2 Heuristics	10 points
3 Elevations	15 points
4 Optimizing Routes	15 points
5 Essential Services	15 points

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

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

40 23 1X X O XX X O OX X X OX O O O

4

Sample Input 2 Sample Output 2

60 15 2O O O O O XX X O X O OO O X O O XX O O O O OO O X X X OX O O X O O

5

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

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

40 23 1X X O XX X O OX X X OX O O O

6

Sample Input 2 Sample Output 2

60 15 2O O O O O XX X O X O OO O X O O XX O O O O OO O X X X OX O O X O O

12

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 Id 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
• 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.

Sample Output 1

Home9Bookworks, Home, 95Bookworks, Aquarium, -50Home, Aquarium, 150 Home, Starbucks, 12Home, Beach, -100Beach, Starbucks, 55Aquarium, Bookworks, 50 Starbucks, Carmel, 200Carmel, Home, -100

Bookworks: 200Home: 0Aquarium: 150Starbucks: -45Beach: -100 Carmel: 155

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, Im 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
• 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.

Sample Output 1

Home4Bookworks, 9CSUMB, 16East Village, 6Carmel Beach, 2117Presidio, Bookworks, 3Presidio, Aquarium, 3Presidio, Colton Hall, 2 Presidio, Home, 5Home, Carmel Village, 17Home, REI, 12REI, CSUMB, 3Home, CSUMB, 16Home, East Village, 6Home, 17-Mile Drive, 10Home, Colton Hall, 4Home, Sushi Time, 10CSUMB, Sushi Time, 7Carmel Beach, 17-Mile Drive, 12East Village, Colton Hall, 5Colton Hall, Home, 4Carmel Village, Carmel Beach, 4

Bookworks NO PATHCarmel Beach FASTEST CSUMB 1East Village FASTEST

5. Essential Services (15 _points)

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

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

Sample Output 1

5CerseiRobert JamieQyburn Tomin2CastleChurch9Castle, Robert, 15Robert, Qyburn, 155Robert, Tomin, 15Castle, Tomin, 35Qyburn, Church, 15 Robert, Jamie, 30Jamie, Church, 115Robert, Cersei, 300Cersei, Church, 60

Castle Church220 60 Cersei 45 115 Jamie170 15 Qyburn 15 145 Robert30 160 Tomin