Post Transition in C - Hacker Rank Solution

CodeWorld19
20 May, 2020
1
Post Transition in C - Hacker Rank Solution
Post Transition in C - Hacker Rank Solution


Problem


We live in a big country. This country has towns_count towns in it. Each town has some post offices in which packages are stored and transferred.

Post offices have different inner structure. Specifically, each of them has some limitations on the packages it can store - their weight should be between min_weight and max_weight inclusively, where min_weight and max_weight are fixed for each office.

Packages are stored in some order in the office queue. That means, that they are processed using this order when sending and receiving.

Sometimes two post offices, even in different towns, may organize the following transaction: the first one sends all its packages to the second one. The second one accepts the packages that satisfy the weight condition for the second office and rejects all other ones. These rejected packages return to the first office back and are stored in the same order they were stored before they were sent. The accepted packages move to the tail of the second office's queue in the same order they were stored in the first office.

You should process several queries in your program. You'll be provided with structures package, post_of fice and town. in order to complete this task, you should fill the following functions:

print_all_packages : given the town t, print all packages in this town. They should be printed as follows: 

Town_name:
    0:
        id_0
        id_1
        ...
    1:
        id_2
        id_3
        ...
    ...

where 0, 1 etc are the numbers of post offices and id0,id1 ... are the ids of packages from the 0th post office in the order of its queue, id2, id3 are from the 1st one etc. There should be one '\t' symbol before post office numbers and two '\t' symbols before the ids.

send_all_acceptable_packages given the towns source and target and post office indices source_of fice_index and target_of fice_index, manage the transaction described above between the post office # source_of fice_index in town source and the post office # target_of fice_index in town target.

town_with_most_packages - given all towns, find the one with the most number of packages in all post offices altogether. If there are several of them, find the first one from the collection town.

find_town - given all towns and a string name, find the town with the name name. It's guaranteed that the town exists.


Input Format :

First line of the input contains a single integer town_count . town_count blocks follow, each describing a town. Every town block contains several lines. On the first line there is a string town_name - the name of the town. On the second line there is an integer of fices_count - the number of the offices in the town. of fices_count blocks follow then, each describing an office.

Every office block also contains several lines. On the first line there are three integers separated by single spaces: package_count (the number of packages in the office), min_weight and max_weight (described above) package_count. blocks follow, each describing a package.

Every package block contains exactly two lines. On the first line there is a string id which is an id of the package. On the second line there is an integer weight which is the weight of the package.
Then, there is a single integer queries on the line which is the number of queries. queries blocks follow, each describing a query.

Every query block contains several lines. On the first line there is an integer 1, 2 or 3. If this integer is 1, on the second line there is a string town_name - the name of town for which all packages should be printed. If this integer is 2, on the second line there are string source_name, integer source_office_index, string target_name and target_office_index integer separated by single spaces. That means transactions between post office # source_office_index in the town source_name and post office # target_office_index in the town  target_name should be processed.
If the integer is 3, no lines follow and the town with the most number of packages should be found.

Constraints :

  • All integer are between 0 and 10
  • town_count > 0, of fice_count > 0.
  • All strings have length <= 5
  • All towns' names have only uppercase english letters and are unique.
  • All packages' ids have only lowercase english letters and are unique.
  • For each post office, min_weight <= max_weight.
  • All queries are valid, that means, towns with the given names always exist, post offices with the given indices always exist.

Output Format :

For queries of type 1, print all packages in the format provided in the problem statement. For queries of type 3, print "Town with the most number of packages is "town_name"on a separate line.


Sample Input :

2
A
2
2 1 3
a 2
b 3
1 2 4
c 2
B
1
4 1 4
d 1
e 2
f 3
h 4
5
3
2 B 0 A 1
3
1 A
1 B

Sample Output :

Town with the most number of packages is B
Town with the most number of packages is A
A:
    0:
        a
        b
    1:
        c
        e
        f
        h
B:
    0:
        d

Explanation :

Before all queries, town B has 4 packages in total, A town has 3. But after transaction all packages from B's 0th post office go to 1 the st post office of A, except package d because it's too light.


Solution :


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
//Post Transition in C - Hacker Rank Solution
#include <stdio.h>
#include <stdlib.h>
#define MAX_STRING_LENGTH 6

struct package
{
   char* id;
   int weight;
};

typedef struct package package;

struct post_office
{
   int min_weight;
   int max_weight;
   package* packages;
   int packages_count;
};

typedef struct post_office post_office;

struct town
{
   char* name;
   post_office* offices;
   int offices_count;
};

typedef struct town town;


void print_all_packages(town t)
{
    printf("%s:\n", t.name);
    for (int i = 0; i < t.offices_count; i++)
    {
        printf("\t%d:\n", i);
        for (int j = 0; j < t.offices[i].packages_count; j++)
            printf("\t\t%s\n", t.offices[i].packages[j].id);
    }
}

void send_all_acceptable_packages(town* source, int source_office_index, town* target, int target_office_index)
{
    int n = 0;
    for (int i = 0; i < source->offices[source_office_index].packages_count; i++)
        if (source->offices[source_office_index].packages[i].weight >= target->offices[target_office_index].min_weight &&
            source->offices[source_office_index].packages[i].weight <= target->offices[target_office_index].max_weight)
            ++n;
    package* newPackages = malloc(sizeof(package)*(n + target->offices[target_office_index].packages_count));
    package* oldPackages = malloc(sizeof(package)*(source->offices[source_office_index].packages_count - n));
    for (int i = 0; i < target->offices[target_office_index].packages_count; i++)
        newPackages[i] = target->offices[target_office_index].packages[i];
    n = target->offices[target_office_index].packages_count;
    int m = 0;
    for (int i = 0; i < source->offices[source_office_index].packages_count; i++)
        if (source->offices[source_office_index].packages[i].weight >= target->offices[target_office_index].min_weight &&
            source->offices[source_office_index].packages[i].weight <= target->offices[target_office_index].max_weight)
        {
            newPackages[n] = source->offices[source_office_index].packages[i];
            ++n;
        }
        else
        {
            oldPackages[m] = source->offices[source_office_index].packages[i];
            ++m;
        }
    target->offices[target_office_index].packages_count = n;
    free(target->offices[target_office_index].packages);
    target->offices[target_office_index].packages = newPackages;
    source->offices[source_office_index].packages_count = m;
    free(source->offices[source_office_index].packages);
    source->offices[source_office_index].packages = oldPackages;
}

int number_of_packages(town t)
{
    int ans = 0;
    for (int i = 0; i < t.offices_count; i++)
        ans += t.offices[i].packages_count;
    return ans;
}

town town_with_most_packages(town* towns, int towns_count)
{
    int ans;
    int max_packages = -1;
    for (int i = 0; i < towns_count; i++)
        if (number_of_packages(towns[i]) > max_packages)
        {
            max_packages = number_of_packages(towns[i]);
            ans = i;
        }
    return towns[ans];
}

town* find_town(town* towns, int towns_count, char* name)
{
    for (int i = 0; i < towns_count; i++)
        if (!strcmp(towns[i].name, name))
            return &(towns[i]);
    return &towns[0];
}

int main()
{
   int towns_count;
   scanf("%d", &towns_count);
   town* towns = malloc(sizeof(town)*towns_count);
   for (int i = 0; i < towns_count; i++) {
      towns[i].name = malloc(sizeof(char) * MAX_STRING_LENGTH);
      scanf("%s", towns[i].name);
      scanf("%d", &towns[i].offices_count);
      towns[i].offices = malloc(sizeof(post_office)*towns[i].offices_count);
      for (int j = 0; j < towns[i].offices_count; j++) {
         scanf("%d%d%d", &towns[i].offices[j].packages_count, &towns[i].offices[j].min_weight, &towns[i].offices[j].max_weight);
         towns[i].offices[j].packages = malloc(sizeof(package)*towns[i].offices[j].packages_count);
         for (int k = 0; k < towns[i].offices[j].packages_count; k++) {
            towns[i].offices[j].packages[k].id = malloc(sizeof(char) * MAX_STRING_LENGTH);
            scanf("%s", towns[i].offices[j].packages[k].id);
            scanf("%d", &towns[i].offices[j].packages[k].weight);
         }
      }
   }
   int queries;
   scanf("%d", &queries);
   char town_name[MAX_STRING_LENGTH];
   while (queries--) {
      int type;
      scanf("%d", &type);
      switch (type) {
      case 1:
         scanf("%s", town_name);
         town* t = find_town(towns, towns_count, town_name);
         print_all_packages(*t);
         break;
      case 2:
         scanf("%s", town_name);
         town* source = find_town(towns, towns_count, town_name);
         int source_index;
         scanf("%d", &source_index);
         scanf("%s", town_name);
         town* target = find_town(towns, towns_count, town_name);
         int target_index;
         scanf("%d", &target_index);
         send_all_acceptable_packages(source, source_index, target, target_index);
         break;
      case 3:
         printf("Town with the most number of packages is %s\n", town_with_most_packages(towns, towns_count).name);
         break;
      }
   }
   return 0;
}




Disclaimer :-
the above whole problem statement is given by hackerrank.com but the solution is generated by the codeworld19 authority if any of the query regarding this post or website fill the following contact form thank you.

CodeWorld19

CodeWorld19

Hey, I am Parthe Omkar

Next Post Previous Post
1 Comments
  • Anonymous
    Anonymous Sunday, July 04, 2021

    Wtf is this shit?

    Reply
Add Comment
comment url