Wednesday, July 2, 2014

Roundabout

Problem:

TopCoder Problem Statement - Roundabout

Overview:

Simulate vehicles entering and exiting a traffic circle.

Java Source:
001: /*
002: TopCoder
003: Single Round Match: 146
004: Division: 1
005: Level: 3
006: Points: 800
007: Description: http://community.topcoder.com/stat?c=problem_statement&pm=1605
008:  */
009:
010: import java.util.ArrayList;
011: import java.util.List;
012:
013: public class Roundabout {
014:
015:     private static final short NORTH = 0;
016:
017:     private static final short EAST = 1;
018:
019:     private static final short SOUTH = 2;
020:
021:     private static final short WEST = 3;
022:
023:     private static final char SPACE = '-';
024:
025:     /*
026:     Return a new list composed of characters from s
027:      */
028:     private static List initializeQueue(String s) {
029:
030:         List l = new ArrayList<>();
031:
032:         for (int i = 0; i < s.length(); i++) {
033:             l.add(s.charAt(i));
034:         }
035:
036:         return l;
037:     }
038:
039:     /*
040:     Checks the roundabout and all queues to see if they are empty
041:      */
042:     private static boolean isCleared(Character[] c, List[] q) {
043:
044:         // Check the roundabout
045:         for (Character aC : c) {
046:             if (aC != SPACE) { return false; }
047:         }
048:
049:         // Check each queue
050:         for (List l : q) {
051:             for (Character aL : l) {
052:                 if (aL != SPACE) { return false; }
053:             }
054:         }
055:
056:         return true;
057:     }
058:
059:     /*
060:     If a car is at its destination, the remove it by replacing it with a SPACE.
061:      */
062:     private static void processExit(Character[] circle) {
063:
064:         if (circle[NORTH] == 'N') { circle[NORTH] = SPACE; }
065:         if (circle[EAST] == 'E') { circle[EAST] = SPACE; }
066:         if (circle[SOUTH] == 'S') { circle[SOUTH] = SPACE; }
067:         if (circle[WEST] == 'W') { circle[WEST] = SPACE; }
068:     }
069:
070:     /*
071:     Process each of the queues to determine if their lead car may enter the
072:     roundabout.  The car is allowed to enter if, and only if,
073:     the space to their left (both in the roundabout, and the queue) are empty.
074:     Use the "oldCircle" since exists have already been removed.
075:
076:     An entry is performed by inserting the car one space in the clock-wise
077:     direction from where it entered.  The next step in the algorithm is to
078:     advance all cars which puts it in the correct starting position.
079:      */
080:     private static void processEntry(Character[] circle,
081:                                      Character[] oldCircle,
082:                                      List[] q) {
083:
084:
085:         /*
086:         The North queue is a special case.  This car may enter if the space
087:         to the east is available in both the roundabout and the east queue;
088:         or if the east space in the roundabout is open and all queues are
089:         ready to enter.
090:          */
091:         if (readyToEnter(q[NORTH]) && (oldCircle[EAST] == SPACE)) {
092:
093:             if (!readyToEnter(q[EAST]) ||
094:                     (
095:                             readyToEnter(q[EAST]) &&
096:                                     readyToEnter(q[SOUTH]) &&
097:                                     readyToEnter(q[WEST])
098:                     )) {
099:                 circle[EAST] = q[NORTH].remove(0);
100:             }
101:         }
102:
103:         // East checks to the South.
104:         if (readyToEnter(q[EAST]) && (!readyToEnter(q[SOUTH])) &&
105:                 (oldCircle[SOUTH] == SPACE)) {
106:             circle[SOUTH] = q[EAST].remove(0);
107:         }
108:
109:         // South checks to the West.
110:         if (readyToEnter(q[SOUTH]) && (!readyToEnter(q[WEST])) &&
111:                 (oldCircle[WEST] == SPACE)) {
112:             circle[WEST] = q[SOUTH].remove(0);
113:         }
114:
115:         // West checks to the North.
116:         if (readyToEnter(q[WEST]) && (!readyToEnter(q[NORTH])) &&
117:                 (oldCircle[NORTH] == SPACE)) {
118:             circle[NORTH] = q[WEST].remove(0);
119:         }
120:     }
121:
122:     // Queue is ready to enter if there is a car at the front.
123:     private static boolean readyToEnter(List q) {
124:         return !(q.isEmpty() || (q.get(0) == SPACE));
125:     }
126:
127:     /*
128:     Moves each element forward one position in the circle.  The first element
129:      loops around to the back.
130:      */
131:     private static void advanceCircle(Character[] c) {
132:
133:         char t = c[0];
134:         for (int i = 0; i < c.length - 1; i++) {
135:             c[i] = c[i + 1];
136:         }
137:         c[c.length - 1] = t;
138:     }
139:
140:     /*
141:     Removes the first SPACE found in each queue.  Effectively moves each car
142:     up by one if possible.
143:      */
144:     private static void advanceQueues(List[] q) {
145:
146:         for (List aQ : q) {
147:             if (aQ.isEmpty()) { continue; }
148:
149:             for (int j = 0; j < aQ.size(); j++) {
150:                 if (aQ.get(j) == SPACE) {
151:                     aQ.remove(j);
152:                     break;
153:                 }
154:             }
155:         }
156:     }
157:
158:     // Left in for debugging.
159:     private static String printState(Character[] c, List[] q) {
160:
161:         return "Circle:" + " North: " + c[NORTH] + " East: " + c[EAST] +
162:                 " South: " + c[SOUTH] + " West: " + c[WEST] + "\nQueues:" +
163:                 "\nNorth: " + printQueue(q[NORTH]) + "\nEast: " +
164:                 printQueue(q[EAST]) + "\nSouth: " + printQueue(q[SOUTH]) +
165:                 "\nWest: " + printQueue(q[WEST]);
166:     }
167:
168:     // Left in for debugging.
169:     private static String printQueue(List l) {
170:         StringBuilder sb = new StringBuilder(l.size());
171:
172:         for (Character aL : l) {
173:             sb.append(aL);
174:         }
175:
176:         return sb.toString();
177:     }
178:
179:     public int clearUpTime(String north, String east, String south,
180:                            String west) {
181:
182:         // Our traffic circle
183:         Character[] circle = new Character[4];
184:         for (int i = 0; i < 4; i++) {
185:             circle[i] = SPACE;
186:         }
187:
188:         // Queues waiting to get into the circle
189:         List[] queues = new List[4];
190:         queues[NORTH] = initializeQueue(north);
191:         queues[EAST] = initializeQueue(east);
192:         queues[SOUTH] = initializeQueue(south);
193:         queues[WEST] = initializeQueue(west);
194:
195:         int time = 0;
196:         System.out.println(printState(circle, queues));
197:         System.out.println("Time: " + time);
198:         System.out.println("- - - - - - - - - -");
199:
200:         // Continue looping until the roundabout and all queues are cleared.
201:         while (!isCleared(circle, queues)) {
202:
203:             // Make a copy of the circle's current state
204:             Character[] oldCircle = new Character[circle.length];
205:             System.arraycopy(circle, 0, oldCircle, 0, circle.length);
206:
207:             processExit(circle);
208:             processEntry(circle, oldCircle, queues);
209:             advanceCircle(circle);
210:             advanceQueues(queues);
211:             time++;
212:
213:             System.out.println(printState(circle, queues));
214:             System.out.println("Time: " + time);
215:             System.out.println("- - - - - - - - - -");
216:         }
217:
218:         return time;
219:     }
220: }
Notes:

This problem has a few gotchas that you need to be aware of. And a few details weren't entirely clear from the description. I'll point these out as we walk through the code.

I chose to model the roundabout (we call them traffic circles here) as an array of 4 characters, and the roads leading in as an array of lists of characters. You might implement the roundabout as a circular linked list, and the roads as Queues. Lines 182-193 just create and initialize these data structures.

On line 201 we begin the main loop of the program. It will continue so long as there is a vehicle in either the roundabout, or any of the queues. The first thing, is to create a copy of the current state. This is important because we'll be removing vehicles, but also need to remember where they were to determine if a vehicle can enter.

This is the first tricky part. Many people have assumed that if a vehicle is exiting, then one in the next position is free to enter. This is not true, so be careful.

Line 207 calls processExit() to remove any vehicles that have reached their destination. This is a simple check to see if there is an 'N' in the north position, an 'E' in the east position, etc. and if so, replaces them with a '-'. I use the '-' or SPACE constant throughout to denote an opening.

Line 208 then calls processEntry() to see which cars may enter the circle. As noted above, it's important to provide this with a copy of the roundabout's state from before the vehicles exited.

Next, we advance all the vehicles in the circle, then advance the vehicles up in their queues, and finally increment the time.

processEntry() on line 80 handles all the logic for determining which vehicles may enter the roundabout. The special case of when all four vehicles are able enter is handled in lines 91-101. This avoids a gridlock situation.

Each queue checks both the roundabout position to it's left, and the queue to it's left; and if both are clear, then it enters the roundabout. Note that I place the new entrant one space back in the clock-wise direction because the advanceCircle() method will be called next which moves all vehicles ahead - putting it in the proper place.

Here's the second part that was a bit confusing. If there are cars at the head of the South and West roads, and the only car in the roundabout is at the North. You might think it's clear for the South car to enter. Since the West car cannot enter due to the car at the North, it should therefore be safe for the South car to go. Again, be careful, and just stick to the problem description.

The final two remaining methods, advanceCircle(), and advanceQueues() are very straightforward. advanceCircle() moves each vehicle one space around the roundabout, while advanceQueues() removes the first space in the queues leading up to the circle.

I've left the printState() method in to assist in debugging the code. This problem in particular really benefits from seeing what happens during each iteration.

No comments:

Post a Comment