Shortest path with elevation in the mix

Sanjay lives in the hilly terrain of Uttarakhand. For work, he had to relocate to the bigger city of Bangalore.
He has been a resident of the city for many years now. He earns a living as a passionate developer who
believes he can solve any problem with the aid of a well-written program. Keep that in mind. One of the
pesky problems that started bothering him recently is during his visit back to his home state he often walks
on the hilly terrain. Thanks to the growing traffic and also his doctor’s recurring advice from the master
health check-up sponsored by his employer. All right, we admit we phrased it badly. It was not the walk that
was the problem it was rather the exhaustion that followed. Having shifted to lesser hilly terrain he was
losing touch with his natural skill of walking along the hilly terrain.
On a laid-back Sunday, he was rephrasing his challenge in his mind. The rephrased version is – What
could be the optimal path between two points on a hilly terrain which for navigation uses the least energy of
the walker? If you have been to hilly terrain any time you would immediately pick up the point that energy
exerted to walk is very closely related to the elevation of the path.
As an example, if you pick a path that is very steep but by Euclid distance is the shortest you will exert
more energy than a path that is less steep even if its Euclid distance is more. Did Google Maps ring a bell?
We say drop that thought. Sanjay did so. Because it is good for walking along the roads. Roads are good
for vehicles. Which by the way are already overcrowded. It is growing difficult for pedestrians by the way.
Over time locals have carved paths that are good for walking on foot. But then which one is easier that
demands the lowest energy is something that Sanjay is determined to find.
He fires up his laptop not to google but to write a program that could solve this problem. If he could crack it,
he has plans to make it a mobile app that he wishes to use equivalent to Google Maps for climbers. On the
hills, anyone who walks along a path is a climber. Isn’t it? It is fancy to have an assistant in the office. The
advent of modern assistants driven by technology had made them prevalent. Keeping the climber in mind
Sanjay named his new project as Climber’s assistant.
The input
One of the first things that developers often start with when struck by the sweet lightening of the idea is to
build a console line app. As the name indicates there is no fancy UI or buttons that you click which you will
experience in day-to-day interactions with many apps. Rather it is a simple and humble blank dark screen
with a blinking cursor staring back at the developer. The only guiding light in that darkness for the
developer is the location. The folder location that the console can use to locate files. Oh, we missed one
source of the guiding light, it is the idea in the developer’s head itself. All right enough of romanticising with
the console and let us get cracking the first problem that comes with console line programs. How do you

input the real world in characters (be it words or numbers)? This is often glorified as the great input format
challenge.
Sanjay picked a spaced multi-line input as an input format. The convention he used was designed to
capture the hilly terrain in terms of elevation. Often in the hilly area that is information that is available if you
know where to look. His initial draft looked like this
3 4 5 7
2 4 8 3
1 5 6 4
0 2 3 1
0 0 1 0
Is that elevation? They are just random numbers that to limited between 0 and 10 if we round up 8. Isn’t
elevation measured in meters from mean sea level?
Yes, is the answer to all those raging questions. Remember we said elevation is a piece of information that
is available easily in hilly areas if you know where to look. Sanjay did know how to read the markings by the
side of roads that often surveyors drop and also in the maps in the local library. But the resolution of those
is much wider and often he has to make an assumption for the places that we walk by. He superimposed a
grid of rectangles on the routes that he walks by to reach his points of interest. He will use the known
elevation information and using heuristic or better call gut feeling assign a number to indicate the elevation
is steeper or less steep relative to his reference point. For ease of programming, he will keep this reference
point for which the elevation is known at the bottom left corner of the grid. Like the origin in a graph. Then
based on his gut rate his experience of walking along a path with a relative score for elevation. He used a
resolution scale of 500 meters. So, two adjacent numbers in his matrix are separated physically by 500
meters in the simplest of directions i.e., North, East, South, and West.
Since, these are paths that are kind of hacked by the locals for walking and not laid by the authorities you
are bound to encounter hurdles like buildings, fences and one will have to go around. For handling such
scenarios Sanjay modified his grid representation to something like this –
3 4 X X
2 4 8 3
1 X 6 4
0 X X 1
0 0 1 0
Now where the X’s are present are the place where a pedestrian cannot tread. One has to circumnavigate
it to reach a destination on the other side of the X’s. Given this as terrain he also needs to make provision
to collect his wish of what is the starting and destination point for which he wants to find the path. To make
provision for that he modified his input approach a bit and introduced a header column which indicates the
purpose of each row.
E 3 4 X X
E 2 4 8 3
E 1 X 6 4
E 0 X X 1
E 0 0 1 0
You might ask why to do that for each row? Instead of creating a section. We will touch upon it soon. By
doing this he can now use a different marker to indicate his origin and destination. Something like this –
E 3 4 X X
E 2 4 8 3
E 1 X 6 4
E 0 X X 1
E 0 0 1 0
O 1 2
D 4 3
Where the marker O indicates the origin coordinates in the grid and D indicates the destination coordinates.
The values that follow are always 2 numbers which is a 0-based index of the coordinates in the grid of the
hilly terrain. In case you are wondering the character E stands for the elevation profile. So, from the

example above Sanjay is currently located in the place which is on the 1 st column on the grid. Remember
the 0 th column is now the header which for the grid bares the character E. On the row he is stationed in 2 nd
row from the top remember there is no header and with 0-based counting. In simple English, it is the 3 rd row
from the top. The elevation of that place is 1 from the reference. He has set a destination for 4,3 which by
similar logic is situated in the intersection of the last column in the grid and the second last row in the grid
from the top. That place also has an elevation profile of 1.
One of the primary things that any developer embarking on such an interesting journey needs to do first is
to solve the puzzle by hand the first time. Can we visually see what are the possibilities for the path? In the
response, we will use the same coordinate system style to communicate the path. We will use the column
index ‘W’ to signify the waypoint.
Possibility 1
W 1 2
W 1 3
W 1 4
W 2 4
W 3 4
W 4 4
W 4 3
Possibility 2
W 1 2
W 1 1
W 2 1
W 3 1
W 4 1
W 4 2
W 4 3
Possibility 3
W 1 2
W 2 1
W 3 2
W 3 1
W 4 1
W 4 2
W 4 3
Amongst these, Possibility 3 is the shortest by Euclid distance method but has steep climbs to make.
Whereas Possibility 1 and 2 are similar on the Euclid distance but differ starkly on the elevation profile.
Amongst all these the much planar and shortest is the Possibility 1. The quirk in Possibility 3 is the diagonal
movement which is possible since the climber is on foot. But Sanjay has marked it as a complexity booster
to code if it comes to it, he will re-evaluation that possibility at that point.
Sanjay is fairly confident that the input shape is hammered well for the first draft of the app. He now needs
to code for it. The next biggest challenge for the developer is what language to use. Sanjay does not have
any preference or dislike for any language. He rather uses such an opportunity to learn a new language.
But this time around he wanted to get nostalgic with the wider topic which is helping him save energy while
walking up and down the hill. He chose C++ to re-familiarize himself with the language with which he
started the journey years back. We will reserve that for the next dispatch of this series.