Sunday, December 28, 2014

SMBus

Problem:

TopCoder Problem Statement - SMBus
Single Round Match 162 Round 1 - Division II, Level Three

Overview:

Simulate a simple network. Determine how long it will take to process a series of messages.

Java Source:
001: import java.util.HashSet;
002: import java.util.Set;
003: 
004: public class SMBus {
005: 
006:     /*
007:     * Represents a device that wishes to transmit a message.  Contains
008:     * the message it wants to send, and how long it takes to send each
009:     * byte.
010:     */
011:     class Master {
012: 
013:         final String message;
014:         final int time;
015: 
016:         Master(String message, int time) {
017:             this.message = message;
018:             this.time = time;
019:         }
020:     }
021: 
022:     /*
023:     * Represents the SMBus.  Master objects may call setChar() and setTime()
024:     * to put the next character in their message, and the time required to
025:     * transmit onto the bus.  SMBus will keep track of the lowest value
026:     * character, and the greatest time.
027:     */
028:     class Bus {
029: 
030:         /*
031:         * Bigger than any legal character.  Expected to be over written when
032:         * the first character is set.
033:         */
034:         private final char MAX_CHAR = '9' + 1;
035: 
036:         StringBuilder message = new StringBuilder();
037:         int charIdx = 0;
038:         int time = 0;
039: 
040:         Bus() {
041:             reset();
042:         }
043: 
044:         void reset() {
045:             message = new StringBuilder();
046:             message.append(MAX_CHAR);
047:             time = 0;
048:             charIdx = 0;
049:         }
050: 
051:         // Creates a place holder for the next character.
052:         void nextChar() {
053:             message.append(MAX_CHAR);
054:             charIdx++;
055:         }
056: 
057: 
058:         // Keeps the lesser of the current character, and the parameter c.
059:         void setChar(char c) {
060:             if (c < message.charAt(charIdx)) {
061:                 message.setCharAt(charIdx, c);
062:             }
063:         }
064: 
065:         // Keeps the greater of the current time, and the parameter t.
066:         void setTime(int t) {
067:             time = Math.max(time, t);
068:         }
069: 
070:         int getTime() {
071:             return time;
072:         }
073: 
074:         void clearTime() {
075:             time = 0;
076:         }
077: 
078:         /*
079:         * Returns the current value in the message.  Removes the last
080:         * character, since that will be a place holder.
081:         */
082:         String getMessage() {
083:             return message.substring(0, message.length() - 1);
084:         }
085: 
086:     }
087: 
088:     // The method called by TopCoder.
089:     public int transmitTime(String[] messages, int[] times) {
090: 
091:         int time = 0;
092: 
093:         Bus bus = new Bus();
094: 
095:         // Holds all the masters that have not finished sending their message.
096:         Set incomplete = new HashSet<>();
097: 
098:         // Populate incomplete using the given parameters.
099:         for (int i = 0; i < messages.length; i++) {
100:             incomplete.add(new Master(messages[i], times[i]));
101:         }
102: 
103:         while (!incomplete.isEmpty()) {
104: 
105:             bus.reset();
106: 
107:             boolean messageComplete = false;
108: 
109:             // Loop until some master is able to complete their message.
110:             while (!messageComplete) {
111: 
112:                 String currentMessage = bus.getMessage();
113: 
114:                 /*
115:                 * If a message has been completed, we'll store a reference
116:                 * to it here.
117:                 */
118:                 Master completed = null;
119: 
120:                 // Look for a completed message.
121:                 for (Master m : incomplete) {
122:                     if (m.message.equals(currentMessage)) {
123:                         completed = m;
124:                         break;
125:                     }
126:                 }
127: 
128:                 /*
129:                 * If we've found a completed message, remove its master
130:                 * from the incomplete list.  Set messageComplete to true
131:                 * so we can prepare for a new message to start.
132:                 */
133:                 if (completed != null) {
134:                     incomplete.remove(completed);
135:                     messageComplete = true;
136: 
137:                 } else {
138: 
139:                     /*
140:                     * Otherwise.  Put the least character, and the greatest
141:                     * time onto the bus.
142:                     */
143:                     for (Master m : incomplete) {
144: 
145:                         /*
146:                         * Only consider masters whose message still matches
147:                         * the current pattern.
148:                         */
149:                         if (m.message.startsWith(currentMessage)) {
150:                             bus.setChar(m.message.charAt(bus.charIdx));
151:                             bus.setTime(m.time);
152:                         }
153:                     }
154: 
155:                     time += bus.getTime();
156: 
157:                     // Prepare for the next character.
158:                     bus.clearTime();
159:                     bus.nextChar();
160:                 }
161:             }
162:         }
163:         return time;
164:     }
165: }
Notes:

To solve this, I've created a class to represent the Master devices and another class to simulate the network. The transmitTime() method then coordinates these objects and keeps track of how much time is needed to complete all the messages.

The Master class simply represents a device that wishes to send a message. It's initialized with the message, and the time it requires to place each byte on the bus.

The Bus class represents the I2C System Management Bus. The idea is that after the bus is initialized or reset, Master objects can call setChar() and setTime() to drop their request onto the bus. The bus will keep track of the smallest character, and the greatest time. It also remembers all the characters in the current message.

When the transmitTime() method is called, it will create Master objects for each of the parameters. It adds all of these Master objects to the incomplete Set. It will then loop until the incomplete Set is empty - all Master devices have completed sending their messages.

For each message, we check to see if the current message on the bus matches the complete message for any Master. In this case, that Master is done, and is removed from the incomplete Set. Otherwise, each Master in the incomplete Set places it's character and time on the bus, so long as it's message continues to match the bus's message. time is incremented, and the bus is set up to receive the next character.

After all Master objects have been removed from the incomplete Set, time will hold our finishing time.

No comments:

Post a Comment