SHARE
TWEET

lab 10

a guest May 19th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>//definition of bool type and true/false
  4.  
  5. #define MAX_FILE_SIZE 10000//change to ork with bigger files
  6.  
  7. typedef struct      s_date
  8. {
  9.     unsigned int    day;
  10.     unsigned int    month;
  11.     unsigned int    year;
  12. }                   t_date;
  13.  
  14. typedef struct      s_bridge
  15. {
  16.     t_date          date;
  17.     unsigned int    island_id;//id of the island that is connected with the bridge
  18.     unsigned int    island2_id;//if of the second island that ...
  19. }                   t_bridge;
  20.  
  21. typedef struct      s_data
  22. {
  23.     unsigned int    n;//number of islands
  24.     unsigned int    k;//number of bridges
  25. }                   t_data;
  26.  
  27. static void static_value(const char *buff, unsigned int *i, unsigned int *value)
  28. {
  29.     while (buff[*i] == ' ' || buff[*i] == '\n' || buff[*i] == '/')//skip delimiters
  30.         ++(*i);
  31.     *value = atoi(&(buff[*i]));//parse value
  32.     while (buff[*i] >= '0' && buff[*i] <= '9')//skip the value
  33.         ++(*i);
  34. }
  35.  
  36. static bool static_parse_bridges(t_data *data, t_bridge *bridges,
  37.     const char *buff, unsigned int *i)
  38. {
  39.     for (unsigned int b = 0; b < data->k; ++b)
  40.     {
  41.         static_value(buff, i, &bridges[b].island_id);
  42.         if (bridges[b].island_id == 0 || bridges[b].island_id > data->n)
  43.             return (false);
  44.         static_value(buff, i, &bridges[b].island2_id);
  45.         if (bridges[b].island2_id == 0 || bridges[b].island2_id > data->n)
  46.             return (false);
  47.         static_value(buff, i, &bridges[b].date.day);
  48.         if (bridges[b].date.day > 32 || bridges[b].date.day == 0)
  49.             return (false);
  50.         static_value(buff, i, &bridges[b].date.month);
  51.         if (bridges[b].date.month == 0 || bridges[b].date.month > 12)
  52.             return (false);
  53.         static_value(buff, i, &bridges[b].date.year);
  54.     }
  55.     return (true);
  56. }
  57.  
  58. static bool static_parse(t_data *data, t_bridge **bridges, const char *input_file)
  59. {
  60.     FILE            *input;//input file
  61.     int             ret;//n of bytes read from the input file
  62.     char            buff[MAX_FILE_SIZE + 1];//buffer to read to
  63.     unsigned int    i = 0;//iterator for buff
  64.  
  65.     if (!(input = fopen(input_file, "r")))
  66.     {
  67.         printf("Error: Can't open file \"%s\"\n", input_file);
  68.         system("pause");
  69.         return (false);
  70.     }
  71.     if (!(ret = fread(buff, 1, MAX_FILE_SIZE + 1, input)))
  72.     {
  73.         printf("Error: Can't read from \"%s\"\n", input_file);
  74.         system("pause");
  75.         return (false);
  76.     }
  77.     if (ret == MAX_FILE_SIZE + 1)
  78.     {
  79.         printf("Error: File \"%s\" is way too large\n", input_file);
  80.         system("pause");
  81.         return (false);
  82.     }
  83.     static_value(buff, &i, &data->n);//parse n
  84.     if (data->n < 2 || data->n > 1000)//check n
  85.     {
  86.         printf("Error: Invalid value of n (%u)\n", data->n);
  87.         system("pause");
  88.         return (false);
  89.     }
  90.     static_value(buff, &i, &data->k);//parse k
  91.     if (data->k == 0 || data->k > 10000)//check k
  92.     {
  93.         printf("Error: Invalid value of k (%u)\n", data->k);
  94.         system("pause");
  95.         return (false);
  96.     }
  97.     *bridges = malloc(sizeof(t_bridge)* data->k);//allocate array of bridges
  98.     if (!static_parse_bridges(data, *bridges, buff, &i))
  99.     {
  100.         printf("Error: Invalid value in the bridge description\n");
  101.         system("pause");
  102.         return (false);
  103.     }
  104.     return (true);
  105. }
  106.  
  107. //check if connected
  108. static bool     static_done(const bool *connected, unsigned int size)
  109. {
  110.     while (size-- > 0)
  111.     if (!connected[size])
  112.         return (false);
  113.     return (true);
  114. }
  115.  
  116. //compare dates
  117. static bool     static_infuture(t_date date, t_date curr_date)
  118. {
  119.     if (curr_date.year >= date.year
  120.         && curr_date.month >= date.month
  121.         && curr_date.day >= date.day)
  122.         return (false);
  123.     return (true);
  124. }
  125.  
  126. //check if one of the islands connected by the bridge is connected to the other islands
  127. static bool     static_connected(unsigned int *cnctd_list, unsigned int *n_cnctd,
  128.     t_bridge *bridge)
  129. {
  130.     unsigned char   n = 0;
  131.     unsigned int    id = 0;
  132.  
  133.     for (unsigned int i = 0; i < *n_cnctd; ++i)
  134.     {
  135.         if (cnctd_list[i] == bridge->island_id
  136.             || cnctd_list[i] == bridge->island2_id)
  137.         {
  138.             if (cnctd_list[i] == bridge->island_id)
  139.                 id = bridge->island2_id;
  140.             else
  141.                 id = bridge->island_id;
  142.             ++n;
  143.         }
  144.     }
  145.     if (n == 1)
  146.     {
  147.         cnctd_list[*n_cnctd] = id;
  148.         ++(*n_cnctd);
  149.     }
  150.     return (n == 1 ? true : false);
  151. }
  152.  
  153. static void     static_connect(t_bridge *bridges, bool *connected, t_data *data,
  154.     t_date curr_date, unsigned int *cnctd_list, unsigned int n_cnctd)
  155. {
  156.     //connects if possible
  157.     for (unsigned int i = 0; i < data->k; ++i)
  158.     {
  159.         if (!static_infuture(bridges[i].date, curr_date)
  160.             && static_connected(cnctd_list, &n_cnctd, &bridges[i]))
  161.         {
  162.             connected[bridges[i].island_id - 1] = true;
  163.             connected[bridges[i].island2_id - 1] = true;
  164.             i = 0;
  165.         }
  166.     }
  167. }
  168.  
  169. static t_date   static_solve(t_data *data, t_bridge *bridges)
  170. {
  171.     t_date          curr_date = { 1, 1, 1 };
  172.     bool            *connected;//list of islands connected to the first island
  173.     unsigned int    *cnctd_list;
  174.     unsigned int    n_cnctd = 1;//number of connected islands
  175.  
  176.     connected = malloc(sizeof(bool)* data->n);
  177.     cnctd_list = malloc(sizeof(unsigned int)* data->n);
  178.     cnctd_list[0] = 1;//the island to start check connections from
  179.     connected[0] = true;//connected to itself
  180.     for (unsigned int i = 1; i < data->n; ++i)
  181.         connected[i] = false;
  182.     //calculation based on that there are 32 days in each month
  183.     while (!static_done(connected, data->n))//check if all are connected
  184.     {
  185.         //update curr date
  186.         if (curr_date.day < 32)
  187.             curr_date.day++;
  188.         else if (curr_date.month < 12)
  189.         {
  190.             curr_date.day = 1;
  191.             curr_date.month++;
  192.         }
  193.         else
  194.         {
  195.             curr_date.day = 1;
  196.             curr_date.month = 1;
  197.             curr_date.year++;
  198.         }
  199.         static_connect(bridges, connected, data, curr_date, cnctd_list, n_cnctd);//connect islands
  200.     }
  201.     free(connected);
  202.     free(cnctd_list);
  203.     return (curr_date);
  204. }
  205.  
  206. int main()
  207. {
  208.     t_data      data;
  209.     t_bridge    *bridges;
  210.     static char *input_file = "map.txt";
  211.     //static char *output_file = "result.txt";
  212.     //FILE      *output;
  213.     t_date      result;
  214.  
  215.     if (!static_parse(&data, &bridges, input_file))
  216.         system("pause");
  217.     return (false);
  218.     //if (!(output = fopen(output_file, "w")))
  219.     //{
  220.     //  printf("Error: Can't open file \"%s\"\n", output_file);
  221.     //  system("pause");
  222.     //  return (false);
  223.     //}
  224.     result = static_solve(&data, bridges);
  225.     printf("%u/%u/%u\n", result.day, result.month, result.year);//console output
  226.     //fprintf(output, "%u/%u/%u\n", result.day, result.month, result.year);//file output
  227.     system("pause");
  228.     return (true);
  229. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top