fork download
copy 
  1. /*
  2.  * Solution to the "Imperial Messengers" problem by Anish Laxman Ramaswamy.
  3.  *
  4.  * -------------------------------------------------------------------------------------------
  5.  *
  6.  * We can consider this as a shortest path problem. Each city represents a node in a
  7.  * graph, and each entry in the adjacency matrix given as input describes an edge. A
  8.  * number in the adjacency matrix (which denotes the time taken to travel between those
  9.  * cities) will denote the weight of that edge. An 'x' in the adjacency matrix would mean
  10.  * that there is no edge connecting those respective nodes.
  11.  *
  12.  * Thus, to find the time taken for the message to reach all the cities, we can run Dijkstra's
  13.  * algorithm on the graph of cities. This will give us the shortest paths from the capitol
  14.  * city to all the other cities. Then, the minimum time it would take for the message to
  15.  * reach all the cities will be the maximum of the path lengths from the capitol to every 
  16.  * other city. This would work only because we are working under the assumption that there
  17.  * are no limits upon the number of messengers available at each city.
  18.  *
  19.  * For example, given the graph of the empire as follows (where city #1 is the capitol city):
  20.  *
  21.  *                                      1
  22.  *                                     / \
  23.  *                                  1 /   \ 3
  24.  *                                   /     \
  25.  *                                  2 ----- 3
  26.  *                                      1
  27.  *
  28.  * Dijkstra's algorithm will give us the shortest path from:
  29.  *     - City #1 to city #2 = 1
  30.  *     - City #1 to city #3 = 2
  31.  *
  32.  * Thus, the minimum time it will take for the message to reach all the cities will be the
  33.  * maximum of (1, 2) = 2.
  34.  *
  35.  * -------------------------------------------------------------------------------------------
  36.  *
  37.  * This solution can be broken down into the following steps:
  38.  *
  39.  *     1. Take the adjacency matrix as input, and store it.
  40.  *     2. Run Dijkstra's algorithm on the graph represented by the stored matrix.
  41.  *     3. Running step #2 would have resulted in path lengths being found for all nodes from
  42.  *        the source.
  43.  *     4. Find the maximum of all the path lengths found in step #3 above. This is the answer.
  44.  *
  45.  * -------------------------------------------------------------------------------------------
  46.  *
  47.  * Time efficiency:
  48.  *
  49.  * It is common knowledge that Dijkstra's algorithm takes O(|E| + |V| log(V)) time. Given an
  50.  * adjacency matrix, this algorithm will take O(|E| + |V| log(V) + |V|) time where the last
  51.  * extra element comes from step #4 above. Thus, this algorithm takes O(|E| + |V| log(V)) time.
  52.  *
  53.  * -------------------------------------------------------------------------------------------
  54.  *
  55.  * Assumption: I am assuming that a time value in the inputted adjacency matrix cannot be
  56.  * negative, as that wouldn't really make sense given this problem because you cannot lose
  57.  * time or go back into the past while traveling from one city to another. (Dijkstra's
  58.  * algorithm would also fail if negative times were allowed.)
  59.  *
  60.  * Notes:
  61.  *
  62.  *     1. Typically, I would separate declaration from implementation by defining all
  63.  *        publicly visible data structures in a header file. However, the question's PDF
  64.  *        mentioned I should submit "a .c file", so I'm putting everything in here.
  65.  *
  66.  *     2. I would also have separated related implementations into separate .c files had it
  67.  *        not been for the instructions in the PDF to submit "a .c file".
  68.  *
  69.  *     3. The adjacency matrix will only store integers. Whenever an 'x' is encountered in the
  70.  *        input, we can simply store a negative value (say '-1') to denote that this edge does
  71.  *        exist.
  72.  *
  73.  * -------------------------------------------------------------------------------------------
  74.  *
  75.  * Alternative algorithm: I had also considered finding the minimum spanning tree (MST) of
  76.  * the given graph. Since a minimum spanning tree would give me a tree where the total edge
  77.  * weight is the minimum compared to other such trees, and yet include all the nodes. After
  78.  * finding this MST, I initially thought of just traversing from the source to every leaf node,
  79.  * incrementing a path length. Once I reached a child node, I may have the minimum time it takes
  80.  * for the message to be spread throughout the graph.
  81.  *
  82.  * However, I quickly determined that this would not work for even the sample input provided.
  83.  * For example, using the above method, I would get a tree which is connected as follows:
  84.  *
  85.  *       #1 ---10---> #5 ---10---> #4 ---20---> #2 ---5---> #3 ---> NULL
  86.  *             ^            ^
  87.  *             |            |
  88.  *              \_____ _____/
  89.  *                    |
  90.  *          represent edge weights
  91.  *
  92.  * Following the above MST-based algorithm, I would wind up with path lengths as follows:
  93.  *
  94.  *      #1 - #5 = 10
  95.  *      #1 - #4 = 20
  96.  *      #1 - #2 = 40
  97.  *      #1 - #3 = 45
  98.  *
  99.  * The above would give us a minimum time of 45 to spread the message, which is incorrect.
  100.  *
  101.  * -------------------------------------------------------------------------------------------
  102.  *
  103.  * Time spent on this solution can be broken down as follows:
  104.  *
  105.  *     1. Designing the algorithm          = 0.5 hours
  106.  *
  107.  *        Coding each individual module
  108.  *     2. (i.e. the input module,          = 0.75 hours
  109.  *        Dijkstra's algorithm, etc.)
  110.  *
  111.  *     3. Integrating everything + testing = 0.25 hours
  112.  *
  113.  *     4. Documenting the code             = 0.5 hours
  114.  *
  115.  *                              TOTAL      = 2.0 hours (approx.)
  116.  *
  117.  * -------------------------------------------------------------------------------------------
  118.  */
  119.  
  120. #include <stdio.h>          // For all the IO
  121. #include <string.h>         // For string functions
  122. #include <stdint.h>         // For SIZE_MAX
  123. #include <stdlib.h>         // For all the dynamic memory stuff
  124. #include <assert.h>         // For 'assert's
  125. #include <stdbool.h>        // To use 'bool', 'true' and 'false'
  126.  
  127. /*
  128.  * By the problem definition. The following was made a preprocessor definition to make life
  129.  * easy if it was ever needed that some other city must be the capitol city.
  130.  */
  131.  
  132. #define CAPITOL_CITY_NUMBER 1
  133.  
  134. /*
  135.  * We can define an invalid (or non-existent) edge to have a value of '-1' due to the assumption
  136.  * made above that all negative valued edges are not possible in this problem.
  137.  */
  138.  
  139. #define INVALID_EDGE -1
  140.  
  141. // Define an adjacency matrix
  142. typedef struct
  143. {
  144.     int **matrix;
  145.     size_t size;
  146. } ADJACENCY_MATRIX;
  147.  
  148. // Allocates memory for the adjacency matrix
  149. void initializeAdjacencyMatrix(ADJACENCY_MATRIX *adjacencyMatrix)
  150. {
  151.     assert(adjacencyMatrix != NULL);
  152.  
  153.     if (adjacencyMatrix->size <= 0)
  154.     {
  155.         return;
  156.     }
  157.  
  158.     /*
  159.      * We know the following constraints on the adjacency matrix as specified by the problem
  160.      * statement:
  161.      *     1. matrix[i][i] = 0 for 1 <= i <= n
  162.      *     2. matrix[i][j] = matrix[j][i]
  163.      *
  164.      * Thus, it would be sufficient to allocate memory for a lower triangular matrix.
  165.      */
  166.  
  167.     size_t i = 0;
  168.  
  169.     adjacencyMatrix->matrix = calloc(adjacencyMatrix->size, sizeof(*adjacencyMatrix));
  170.     if (!adjacencyMatrix->matrix)
  171.     {
  172.         exit(EXIT_FAILURE);
  173.     }
  174.  
  175.     for (i = 1; i <= adjacencyMatrix->size; i++)
  176.     {
  177.         adjacencyMatrix->matrix[i] = calloc(i, sizeof(*(adjacencyMatrix->matrix[i])) + 1);
  178.         if (!adjacencyMatrix->matrix[i])
  179.         {
  180.             /*
  181.              * There may have been some allocated memory before this point, but we can treat
  182.              * this as a fatal error, and crash. So the OS will free up the memory.
  183.              */
  184.  
  185.             exit(EXIT_FAILURE);
  186.         }
  187.     }
  188. }
  189.  
  190. // Frees the memory allocated for the adjacency matrix
  191. void freeAdjacencyMatrix(ADJACENCY_MATRIX *adjacencyMatrix)
  192. {
  193.     assert(adjacencyMatrix != NULL);
  194.  
  195.     size_t i = 0;
  196.  
  197.     for (i = 1; i <= adjacencyMatrix->size; i++)
  198.     {
  199.         free(adjacencyMatrix->matrix[i]);
  200.         adjacencyMatrix->matrix[i] = NULL;
  201.     }
  202.  
  203.     free(adjacencyMatrix->matrix);
  204.     adjacencyMatrix->matrix = NULL;
  205.  
  206.     adjacencyMatrix->size = 0;
  207. }
  208.  
  209. /*
  210.  * Populate the adjacency matrix from 'stdin'. This was made as a function so that
  211.  * in the future, if input was ever needed from a file or another source, only this
  212.  * function needs to be changed.
  213.  */
  214.  
  215. void getAdjacencyMatrix(ADJACENCY_MATRIX *adjacencyMatrix)
  216. {
  217.     assert(adjacencyMatrix != NULL);
  218.  
  219.     size_t i = 0;
  220.     size_t j = 0;
  221.     char numberStr[64] = { 0 };
  222.  
  223.     for (i = 1; i <= adjacencyMatrix->size; i++)
  224.     {
  225.         for (j = 1; j < i; j++)
  226.         {
  227.             /*
  228.              * Read the current number. However, if the input is an 'x', we can
  229.              * store 'INVALID_EDGE' in the adjacency matrix to denote that this is
  230.              * an invalid (or non-existent) edge (since I earlier made the documented
  231.              * assumption that negative valued edges are not allowed).
  232.              *
  233.              * Ideally, I'd read a line of input using 'fgets' and parse that into
  234.              * the numbers required. Doing so would make reading the input safe from
  235.              * malicious user input. But I didn't want to waste time doing something
  236.              * that isn't directly related to the problem at hand.
  237.              */
  238.  
  239.             scanf("%s", numberStr);
  240.             if (0 == strcmp(numberStr, "x"))
  241.             {
  242.                 adjacencyMatrix->matrix[i][j] = INVALID_EDGE;
  243.             }
  244.             else
  245.             {
  246.                 adjacencyMatrix->matrix[i][j] = atoi(numberStr);
  247.  
  248.                 /*
  249.                  * The following is just a sanity check. I've decided to assert this
  250.                  * since I've made the documented assumption that negative values make
  251.                  * no sense for this particular problem earlier.
  252.                  */
  253.  
  254.                 assert(adjacencyMatrix->matrix[i][j] >= 0);
  255.             }
  256.         }
  257.     }
  258. }
  259.  
  260. /*
  261.  * Using Dijkstra's algorithm, we find and store the shortest paths from the given
  262.  * source node, to all other nodes.
  263.  *
  264.  * I recreated Dijkstra's algorithm, since it was quite simple to remember. Basically,
  265.  * we scan every node exactly once while updating its neighbors with the current path
  266.  * length plus the weight of the edge leading to it ONLY if that sum is lesser than
  267.  * the value it already holds. Once we have scanned all the nodes, the remaining
  268.  * numbers stored at each node will hold the shortest path length to that node from
  269.  * the source node.
  270.  *
  271.  * This function returns an array where each element will hold a value for the shortest
  272.  * path from the source to that element (barring the 0th element, which we do not consider).
  273.  */
  274.  
  275. size_t *findShortestPathsToAllNodes(const ADJACENCY_MATRIX adjacencyMatrix, const size_t source,
  276.                                     size_t *pathLengths)
  277. {
  278.     if (adjacencyMatrix.size == 0)
  279.     {
  280.         // Nothing to do
  281.         return NULL;
  282.     }
  283.  
  284.     assert(pathLengths != NULL);
  285.     assert(adjacencyMatrix.matrix != NULL);
  286.     assert(source > 0 && source <= adjacencyMatrix.size);
  287.  
  288.     size_t i = 0;
  289.     size_t currNode = 0;            /*
  290.                                      * Current node whose neighbors are being examined in each
  291.                                      * iteration of the algorithm.
  292.                                      */
  293.  
  294.     size_t currMinLength = 0;       // Stores the minimum length in each iteration of the algorithm
  295.     bool *visited = NULL;           // Storage for whether a node has been visited or not
  296.  
  297.     visited = malloc((adjacencyMatrix.size + 1) * sizeof(*visited));
  298.     if (!visited)
  299.     {
  300.         /*
  301.         * Fatally crash since there isn't much else we can do. All the memory allocated
  302.         * until this point should be taken care of by the OS.
  303.         */
  304.  
  305.         exit(EXIT_FAILURE);
  306.     }
  307.  
  308.     // Initially, all the nodes have not been visited, and we set all the path lengths to a maximum value
  309.     for (i = 1; i <= adjacencyMatrix.size; i++)
  310.     {
  311.         visited[i] = false;
  312.         pathLengths[i] = SIZE_MAX;       // For all practical purposes, infinity
  313.     }
  314.  
  315.     // The shortest path from the source to itself is 0 by definition
  316.     pathLengths[source] = 0;
  317.  
  318.     // Start at the source
  319.     currNode = source;
  320.  
  321.     /*
  322.      * Loop through all unvisited nodes. The first time when 'visited[currNode]' is false will
  323.      * denote the time when we have visited all the nodes. This is because 'currNode' will not
  324.      * have been updated by the last nested loop inside the following loop.
  325.      */
  326.  
  327.     while (visited[currNode] == false)
  328.     {
  329.         visited[currNode] = true;
  330.  
  331.         // Loop through all the current node's possible neighbors
  332.         for (i = 1; i <= adjacencyMatrix.size; i++)
  333.         {
  334.             if (i == currNode)
  335.             {
  336.                 // Node 'i' is definitely not a neighbor to 'currNode', so ignore
  337.                 continue;
  338.             }
  339.  
  340.             size_t possibleLengthToNodeI = 0;
  341.  
  342.             /*
  343.              * Since our matrix is lower triangular, it will not have valid values for matrix[i][j]
  344.              * whenever 'i > j'. However, by definition matrix[i][j] = matrix[j][i], and in the cases
  345.              * when 'i > j', matrix[j][i] will have valid values.
  346.              */
  347.  
  348.             if (currNode < i)
  349.             {
  350.                 // If the edge doesn't exist, move on
  351.                 if (adjacencyMatrix.matrix[i][currNode] == INVALID_EDGE)
  352.                 {
  353.                     continue;
  354.                 }
  355.  
  356.                 possibleLengthToNodeI = pathLengths[currNode] + adjacencyMatrix.matrix[i][currNode];
  357.             }
  358.             else
  359.             {
  360.                 // If the edge doesn't exist, move on
  361.                 if (adjacencyMatrix.matrix[currNode][i] == INVALID_EDGE)
  362.                 {
  363.                     continue;
  364.                 }
  365.  
  366.                 possibleLengthToNodeI = pathLengths[currNode] + adjacencyMatrix.matrix[currNode][i];
  367.             }
  368.  
  369.             /*
  370.              * If we find that adding up the current path length seen until 'currNode' and the edge
  371.              * weight from 'currNode' to its neighbor 'i' is actually lesser than the currently stored
  372.              * path length from the source node to node 'i', update it!
  373.              */
  374.  
  375.             if (possibleLengthToNodeI < pathLengths[i])
  376.             {
  377.                 pathLengths[i] = possibleLengthToNodeI;
  378.             }
  379.         }
  380.  
  381.         /*
  382.          * Now we need to pick our next node such that it has the least seen path length thus far.
  383.          * Additionally, this next node has to not have been visited.
  384.          */
  385.  
  386.         currMinLength = SIZE_MAX;
  387.  
  388.         for (i = 1; i <= adjacencyMatrix.size; i++)
  389.         {
  390.             if (!visited[i] && pathLengths[i] < currMinLength)
  391.             {
  392.                 currMinLength = pathLengths[i];
  393.                 currNode = i;
  394.             }
  395.         }
  396.     }
  397.  
  398.     free(visited);
  399.     visited = NULL;
  400.  
  401.     return pathLengths;
  402. }
  403.  
  404. // Prints the maximum value in the given array
  405. void printMaximumValue(const size_t *array, const size_t size)
  406. {
  407.     if (!array || size <= 0)
  408.     {
  409.         // Nothing to do
  410.         return;
  411.     }
  412.  
  413.     size_t i = 0;
  414.     size_t maxValue = 0;
  415.  
  416.     maxValue = array[1];
  417.  
  418.     for (i = 2; i <= size; i++)
  419.     {
  420.         if (array[i] > maxValue)
  421.         {
  422.             maxValue = array[i];
  423.         }
  424.     }
  425.  
  426.     printf("%u", maxValue);
  427. }
  428.  
  429. int main(void)
  430. {
  431.     size_t *shortestPathLengths = NULL;
  432.     ADJACENCY_MATRIX adjacencyMatrix = { 0 };
  433.  
  434.     /*
  435.      * First get the number of nodes. 'scanf' is not really safe. Ideally, I'd
  436.      * read a line of input using 'fgets' and parse that into the numbers required.
  437.      * But I didn't want to waste time doing something that isn't directly related
  438.      * to the problem at hand.
  439.      */
  440.  
  441.     scanf("%u", &(adjacencyMatrix.size));
  442.  
  443.     // Allocate memory for the adjacency matrix
  444.     initializeAdjacencyMatrix(&adjacencyMatrix);
  445.  
  446.     // Read the adjacency matrix from input
  447.     getAdjacencyMatrix(&adjacencyMatrix);
  448.  
  449.     // Find the shortest path from the capitol city node to all other nodes
  450.     shortestPathLengths = calloc(adjacencyMatrix.size + 1, sizeof(*shortestPathLengths));
  451.     if (!shortestPathLengths)
  452.     {
  453.         /*
  454.          * Fatally crash since there isn't much else we can do. All the memory allocated
  455.          * until this point should be taken care of by the OS.
  456.          */
  457.  
  458.         exit(EXIT_FAILURE);
  459.     }
  460.  
  461.     shortestPathLengths = findShortestPathsToAllNodes(adjacencyMatrix,
  462.                                                       CAPITOL_CITY_NUMBER,
  463.                                                       shortestPathLengths);
  464.  
  465.     /*
  466.      * After we have all the shortest paths, we just need to find the maximum element
  467.      * in that shortest path array.
  468.      */
  469.  
  470.     printMaximumValue(shortestPathLengths, adjacencyMatrix.size);
  471.  
  472.     /*
  473.      * Free up allocated memory. This step may not actually be necessary here if this
  474.      * code will surely reside on its own. This is because in that case, it is better
  475.      * just return instead of freeing up memory since the OS is going to do it anyway.
  476.      * However, if this gets introduced as a module in some larger code-base, then we
  477.      * have a resource leak on our hands! Yikes...
  478.      */
  479.  
  480.     freeAdjacencyMatrix(&adjacencyMatrix);
  481.  
  482.     free(shortestPathLengths);
  483.     shortestPathLengths = NULL;
  484.  
  485.     return 0;
  486. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
2
a
stdout
copy 
Standard output is empty
https://ideone.com/rVcGJK
language:
C (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!