Test 5 - Find the shortest path on map

Find the shortest way between two points on a map (the map example can be found in the image below)

Requirements

Create a console app using a programming language of choice. The program should:

  • accept the path to the document which contains the map description (the map coordinates, start point and end point; see example below) as an input parameter (required parameter)
<map>
    <cells>
      <cell row="1" col= "A" />
      <cell row="1" col= "B" />
      <cell row="1" col= "C" />
      <cell row="1" col= "D" />
      <cell row="2" col= "B" />
      <cell row="3" col= "A" />
      <cell row="3" col= "B" />
      <cell row="3" col= "C" />
      <cell row="3" col= "D" />		
      <cell row="4" col= "A" />
      <cell row="4" col= "C" />
      <cell row="4" col= "D" />		
    </cells>	
    <start-point row="1" col= "C" />
    <end-point row="4" col= "C" />
</map>
  • accept the path to the document that will contain the task solution as an input parameter (the parameter is optional)
  • display an error message in case the required parameters aren't specified or are specified using an invalid format
  • display an error message in case the content of the document used to describe the map is invalid,
  • as a result, a document is generated (example below), which should contain the list of the shortest trajectories between two selected points, as well as the execution time
{
    "execution_time_in_ms": 10,	
    "paths": [
            {
              "points":[
                {
                  "row": 1,
                  "col": "C"
                },
                {
                  "row": 1,
                  "col": "B"
                },
                {
                  "row": 2,
                  "col": "B"
                },			
                {
                  "row": 3,
                  "col": "B"
                },
                {
                  "row": 3,
                  "col": "C"
                },
                {
                  "row": 4,
                  "col": "C"
                }
            ]
        }
    ]
}
  • display the path to the document that contains the task solution

Bonus

To get the bonus points, cover the complete code with Unit tests and/or expose the previously implemented functionality through a REST API.

Note

If you have any additional questions, feel free to send an email to jobs@rbt.rs


Please create a new GitHub repo and use it to upload the test solution along with the initialization instructions. Also send us your GitHub repo link along with your job application.


The test solution grading criteria are:

  • quality of the applied algorithm
  • code readability/cleanliness
  • code performance in terms of speed