In this post I will show the solution to one of the problems given in World University Programming Championship 2007 in Tokyo.
As a ACM rules stands programs should be written using C++ or Java languages, tht's why I decided to implement it using C++. However, it could be easily transfered to any C-like language.
Let's look at the problem:
A packet-switching network handles information in small units, breaking long messages into multiple packets before routing. Although each packet may travel along a different path, and the packets comprising a message may arrive at different times or out of order, the receiving computer reassembles the original message correctly.
The receiving computer uses a buffer memory to hold packets that arrive out of order. You must write a program that calculates the minimum buffer size in bytes needed to reassemble the incoming messages when the number of messages (N), the number of packets (M), the part of the messages in each packet, the size of each message, and the order of the incoming packets are given.
When each packet arrives, it may be placed into the buffer or moved directly to the output area. All packets thatare held in the buffer are available to be moved to the output area at any time. A packet is said to “pass the buffer” when it is moved to the output area. A message is said to “pass the buffer” when all of its packets have passed the buffer.
The packets of any message must be ordered so the data in the sequence of packets that pass the buffer is in order. For example, the packet containing bytes 3 through 5 of a message must pass the buffer before the packet containing bytes 6 through 10 of the same message. Messages can pass the buffer in any order, but all packets from a single message must pass the buffer consecutively and in order (but not necessarily at the same time).Note that unlike actual buffering systems, the process for this problem can look ahead at all incoming packets tomake its decisions.
The packets consist of data and header. The header contains three numbers: the message number, the starting byte number of data in the packet, and the ending byte number of data in the packet respectively. The first byte number in any message is 1.
For example, the figure below shows three messages (with sizes of 10, 20, and 5 bytes) and five packets. The minimum buffer size for this example is 10 bytes. As they arrive, packet #1 and packet #2 are stored in the buffer. They occupy 10 bytes. Then packet #3 passes the buffer directly. Packet #4 passes the buffer directly and then packet #2 exits the buffer. Finally, packet #5 passes the buffer directly and packet #1 exits the buffer.
And before I will show the code here are the steps that we need to complete:
1. Input data required for the buffer size calculation (number of messages, number of packets, packets data)
2. Validate if all the messages are valid to be processed. This means that we should chek if all the messages are containing correct data in their packets and no packets are missing for the specific massage. If we will find out that for the message 'A' with total size of 10 bytes we have 'B' packets with total size of 8, we will assume that this message is corrupted and should not be considered as valid message for processing.
3. Finally we can calculate the max buffer size needed to hold the packets.
//this array contains the numbers of messages //and shows whether the packages of //this message are correct // if(isMsgBad == true) this message (all of it's packets // will not be processed std::vector isMsgBad(msgNum,false); // this value shows next starting byte number //(during message check) for packet int nextByte = 1; // if we find packet with correct starting byte and message number // we start looping again and assigning bSetToZero = true, to set value to zero bool bSetToZero = false ; // this function may be used to detect if there are any // incorrect messages in buffer. Each message starting byte should be // equal to 1 and the total sum of all packets // shuould be equal to the message final size // if these conditions do not match for particular message I assign value 1 // to isMsgBad[] that means this message is // (all packets represents this message)not going to be processed later; for(int a = 1;a < (msgNum +1); a++) { for(int k = 0;k < pkgNum; k++) { if(bSetToZero) { k = 0; bSetToZero = false; } if(packets[k].startingbyte == nextByte && packets[k].msgNumber == a) { if(pkgsSize[a-1] == packets[k].endingByte) { nextByte = packets[k].endingByte; break; } nextByte = packets[k].endingByte + 1; bSetToZero = true; } } if(nextByte != pkgsSize[a-1]) isMsgBad[a-1] = true; else isMsgBad[a-1] = false; nextByte = 1; }
// This variable represents buffer size wich may be changed // while program is runnning. It is used to compare its value // with variable(maxBufferSize) int buffSize = 0; // this variable represents the final buffer size // we compare var(bufferSize ) with maxBufferSize to check if the // buffer size is changed while programm is running // and if (buffSize > maxBuffSize) we assign maxBufferSize = bufferSize; // if (buffSise <= maxBuffSize) we live everything like it is int maxBuffSize = 0; // Final buffer size // this value is defined to track current processing message number int currentMsg = 0; // Current processing message // this array represents next starting byte for each message package std::vector passingPkgs(msgNum); // this array is used as a buffer to store packages std::vector packetBuffer; // here we assign default passing byte number to each packet in array for(int a = 0; a < msgNum; a++) { passingPkgs[a].passingByteNumber = 0; } int i = 0; // here we actually start count the buffer size while(pkgNum != i && pkgNum > 0 ) { currentMsg = packets[i].msgNumber; Packet pkg = packets[i]; if(!isMsgBad[currentMsg-1]) { // here we check if current processing package has starting byte // equal to passingPkgs[pkg.msgNumber - 1].passingByteNumber+1 which by // default is 1, if it is true this packet is ready to pass the buffer // then we assign this packet ending byte to passingPkgs[pkg.msgNumber - 1].passingByteNumber+1 // which means this will be the next passing byte for this particular message number if(pkg.startingbyte == (passingPkgs[pkg.msgNumber - 1].passingByteNumber+1) ) { passingPkgs[pkg.msgNumber-1].passingByteNumber = pkg.endingByte; passingPkgs[pkg.msgNumber-1].msgNumber = pkg.msgNumber; //here we check if some packages exist in the buffer // if this is true we check if one of them is ready to leave the buffer if(packetBuffer.size() > 0) { int pkgsInBuffer = (int)packetBuffer.size(); int j = 0; while(pkgsInBuffer > j) { if((packetBuffer[j].msgNumber == pkg.msgNumber) && ((packetBuffer[j].startingbyte - 1) == passingPkgs[pkg.msgNumber-1].passingByteNumber)) { passingPkgs[pkg.msgNumber-1].passingByteNumber = packetBuffer[j].endingByte; buffSize -= (packetBuffer[j].endingByte - packetBuffer[j].startingbyte) + 1; packetBuffer.erase(packetBuffer.begin() + j, (packetBuffer.begin() + j + 1)); pkgsInBuffer--; // here we assign value j to zero to start looking through array // one more time because there may be another package ready to leave the buffer // Example: // we have 2 packages in the buffer for the same message, // 1 10 20 and 1 6 9, so if the packet 1 1 5 just pass the queue // we look through the // buffer if there is any other packages ready to pass the buffer // we look at the buffer and find the packet // 1 6 9 which is ready to pass // the buffer, but now packet 1 10 20 is also ready to leave the buffer, // so that's why we assigning value j to zero to start looking at the buffer // from the beginning if(j != 0) j = 0; else j++; } else j++; } } } //here we are just putting the packet into the buffer if starting byte is not equal to // passingPkgs[pkg.msgNumber - 1].passingByteNumber+1 else if(pkg.startingbyte != passingPkgs[pkg.msgNumber-1].passingByteNumber) { buffSize += (pkg.endingByte - pkg.startingbyte)+1; packetBuffer.push_back(pkg); } if(maxBuffSize < buffSize) maxBuffSize = buffSize; } i++; } return maxBuffSize;
I hope you enjoy it.