Inspirated

 
 

July 27, 2008

At least I wasn’t even close

Filed under: Blog — krkhan @ 4:35 pm

“I think I have a problem with that silver medal.
I think, if I was an Olympic athlete, I would rather come in last then win the silver.
If you think about it… if you win the gold, you feel good.
If you win in the bronze, you think: “Well, at least I got something.”
But if you win that silver, it’s like:
“Congratulations! You… almost won.”
“Of all the losers, you came in first of that group.”
“You’re the number one… loser.”
“No one lost… ahead of you.”” — Jerry Seinfeld

I had two chances for progressing in Code Jam by qualifying in one of the two sub-rounds assigned to me. Both sub-rounds had three problems A, B & C ordered in increasing difficulty level. Here’s a quick summary of both:

  • For the first sub-round (1A), I did solve problem A and got 15 points. However, I didn’t solve it quick enough. Problem B was left untouched by me. Problem C’s small input contained only 29 cases and could have very well been solved using only a scientific calculator. However, that just didn’t seem the right way of progressing (30 points would have been enough to qualify, but I’d definitely have failed at the subsequent rounds).
  • For the second sub-round (1C), apart from connectivity issues, I couldn’t provide correct output for any of the problems. I did solve problem B but as my solution was recursive, it was taking too much time for calculating the output. I’m not that good with refactoring recursive solutions for yielding iterative ones, so my chances got blown right away.

Overall, Code Jam was pretty fun and having fun was the sole aim of participating this year. Now I’ve got to start reading the Introduction to Algorithms book and get myself formally acquainted with algorithmic problem solving. Good luck to all the gurus who did progress (seeing some of them solve all 3 problems within half the time was amazing). They thoroughly deserve it and I’ll keep monitoring later rounds as a spectator — just reading through their ingenuous solutions is nothing short of a delightful experience.

Tags: , , , , ,

July 18, 2008

Jam and Geometry

Filed under: Blog — krkhan @ 5:24 am

The scores for Google Code Jam qualification round are out. It lasted 24-hours, and the participants were allowed to enter any time and try to solve any of the three given problems. Each problem had one small and one large input set. Participants were able to check during the qualification whether their programs produced correct results on the small input sets but had to wait for the round to finish to know whether correct outputs were produced on large ones.

Correct solutions for small and large input sets were worth 5 and 20 points respectively. To progress to Online Round 1, each participant needed to score at least 25 points. Participants based on the times of their correct submissions and their wrong submissions. And, what I actually did not know was that the timer started ticking with the qualification kick-off. Which means that if someone slept through the earlier hours (or watched the final scenes of One Flew Over the Cuckoo’s Nest again, like me), he’d be ranked lower even though he may solve the problem within half an hour of viewing it.

Anyways, since points were what mattered the most and not the rankings, I actually started off with the problem set 2-3 hours after the qualification had started. Participants were provided with the following three problems:

  1. Saving the Universe

    The urban legend goes that if you go to the Google homepage and search for “Google”, the universe will implode. We have a secret to share… It is true! Please don’t try it, or tell anyone. All right, maybe not. We are just kidding.

    The same is not true for a universe far far away. In that universe, if you search on any search engine for that search engine’s name, the universe does implode!

    To combat this, people came up with an interesting solution. All queries are pooled together. They are passed to a central system that decides which query goes to which search engine. The central system sends a series of queries to one search engine, and can switch to another at any time. Queries must be processed in the order they’re received. The central system must never send a query to a search engine whose name matches the query. In order to reduce costs, the number of switches should be minimized.

    Your task is to tell us how many times the central system will have to switch between search engines, assuming that we program it optimally.

    I solved the problem using a vector of strings in STL. It took me around 35-40 minutes. My entry for the small input set was judged to be correct on my first attempt.

  2. Train Timetable

    A train line has two stations on it, A and B. Trains can take trips from A to B or from B to A multiple times during a day. When a train arrives at B from A (or arrives at A from B), it needs a certain amount of time before it is ready to take the return journey – this is the turnaround time. For example, if a train arrives at 12:00 and the turnaround time is 0 minutes, it can leave immediately, at 12:00.

    A train timetable specifies departure and arrival time of all trips between A and B. The train company needs to know how many trains have to start the day at A and B in order to make the timetable work: whenever a train is supposed to leave A or B, there must actually be one there ready to go. There are passing sections on the track, so trains don’t necessarily arrive in the same order that they leave. Trains may not travel on trips that do not appear on the schedule.

    This was actually easier than problem A. As I only had to use a simple multimap and a vector to hold the departure/arrival times in minutes and then loop throughout the day and manage the trains. I had 2 wrong attempts on the smaller input set though, which were caused by the fact that I started solving the problem initially with a map instead of multimap; which was imposing the limit of only one train’s departure from a station at a given instant.

  3. Fly Swatter

    What are your chances of hitting a fly with a tennis racquet?

    To start with, ignore the racquet’s handle. Assume the racquet is a perfect ring, of outer radius R and thickness t (so the inner radius of the ring is R−t).

    The ring is covered with horizontal and vertical strings. Each string is a cylinder of radius r. Each string is a chord of the ring (a straight line connecting two points of the circle). There is a gap of length g between neighbouring strings. The strings are symmetric with respect to the center of the racquet i.e. there is a pair of strings whose centers meet at the center of the ring.

    The fly is a sphere of radius f. Assume that the racquet is moving in a straight line perpendicular to the plane of the ring. Assume also that the fly’s center is inside the outer radius of the racquet and is equally likely to be anywhere within that radius. Any overlap between the fly and the racquet (the ring or a string) counts as a hit.

    This is where I got stuck, and stuck bad. This problem had more to do with Euclidean Geometry than with data structures, STL or structured programming, and I know this much about Euclidean Geometry: chapter 6 from my higher-secondary school Mathematics book was titled “Conic Sections”. Naturally, my first resort was to try and find some library which would issue my particular problems (using free library code is allowed in Code Jam). More specifically, I wanted a library that would allow me to calculate the area of intersection between a circle and a rectangle (so that I’d gradually subtract out the racket strings’ area in calculations). The result wasn’t much different from my Euclidean Geometry knowledge, as now I know this too: there’s a GPL library called GLAC which does geometry stuff. To summarize, I was unsuccessful in solving this problem. Maybe I’ll need to familiarize myself with GLAC before next round to have a good shot at progressing.

One of the advantages of using STL is that if your program is correct on small inputs, i.e., the logic is applied correctly, there’s little chance that things shall take the unfortunate route for the large ones as larger data structures are accommodated dynamically. Consequently, my solutions for A and B were later on judged as correct for the large input sets too. This gave me 50 points, and 1319th rank among the 7154 participants (I wish I had known that wasting time earlier on means a drop in my ranks, but all’s well that ends well).

The Online Round 1 takes place in another week or so. I started solving algorithmic problems only a fortnight ago so I think I’ll need some more practice to be able to compete properly. To be fair though, I didn’t have high hopes for even the qualification round, as I had entered just for fun and some experience so that I’d be able to contend properly next year — after I’ve had some proper and extensive practice with this kind of problem-solving.

Tags: , , , , , , , , , , , , , ,

July 11, 2008

Programming Challenges: Australian Voting

Filed under: Blog — krkhan @ 10:44 am

PC/UVa IDs: 110108/10142, Popularity: B, Success rate: low, Level: 1

I had 28 (that’s twenty-eight) “Time Limit Exceeded” tries on this problem. I was looking everywhere for a loop that would drag, for every possible input that would cause breakdown and I couldn’t find any such thing. So much so, that I considered labeling this post as Australian Nightmare. The issue, once I found it, had nothing to do with Australia and all to do with the string and istringstream objects being significantly heavy to be constructed/destructed on each iteration of the loop on lines #138-153.

The book recommends further reading on voting systems and has linked to some mathematical theorem that proves that no voting system can ever be perfect. Considering the democratic results around the world in recent elections, yeah, what an absolute shocker.

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <iterator>
#include <map>
 
using namespace std;
 
#define NBALLOTS 1000
 
typedef vector< vector< int > > twod_vector;
 
vector< int > calculate(vector< int > &votes, int ncand, bool atleast_50)
{
	vector< int > winners;
 
	int total = votes.size();
	int max = 0;
	for(int i = 0; i < ncand; i++) {
		int vote_count = count(votes.begin(), votes.end(), i);
		bool cond = !atleast_50 || (vote_count > total / 2);
		if(vote_count > 0 &&
				vote_count >= max &&
				cond) {
			max = vote_count;
			winners.push_back(i);
		}
	}
 
	return winners;
}
 
bool compare(pair< int, int > a, pair< int, int > b)
{
	return a.second < b.second;
}
 
map< int, int > vote_map(vector< int > &votes)
{
	map< int, int > table;
 
	for(vector< int >::iterator p = votes.begin();
			p < votes.end();
			p++) {
		table[*p]++;
	}
 
	return table;
}
 
vector< int > least_votes(vector< int > &votes)
{
	map< int, int > table = vote_map(votes);
	vector< int > min_keys;
	int min_value =
		min_element(table.begin(), table.end(), compare)->second;
 
	map< int, int >::iterator p;
	for( p = table.begin(); p != table.end(); p++ ) {
		if(p->second == min_value) {
			min_keys.push_back(p->first);
		}
	}
 
	return min_keys;
}
 
void eliminate(twod_vector &ballots, int value)
{
	for(int i = 0; i < (int) ballots.size(); i++) {
		for(int j = 0; j < (int) ballots.at(i).size(); j++) {
			if(ballots.at(i).at(j) == value) {
				for(int k = i;
					k < (int) ballots.size() - 1;
					k++) {
					ballots.at(k).at(j)
						= ballots.at(k + 1).at(j);
				}
			}
		}
	}
}
 
void eliminate(twod_vector &ballots)
{
	vector< int > min_values = least_votes(ballots.at(0));
 
	for(vector< int >::iterator p = min_values.begin();
			p != min_values.end();
			p++) {
		eliminate(ballots, *p);
	}
}
 
bool draw(vector< int > &votes)
{
	if(!votes.size()) {
		return true;
	}
 
	map< int, int > table = vote_map(votes);
	map< int, int >::iterator p = table.begin();
	int n = p->second;
	p++;
	for(; p != table.end(); p++) {
		if( n != p->second ) {
			return false;
		}
	}
 
	return true;
}
 
int main(int argc, char *argv[])
{
	twod_vector ballots;
	int ncases;
	cin>>ncases;
	cin.ignore();
	string dummy;
	getline(cin, dummy);
 
	for(int i = 0; i < ncases; i++) {
		int ncand;
		cin>>ncand;
		cin.ignore();
 
		vector< string > candidates(ncand);
		for(int j = 0; j < ncand; j++) {
			getline(cin, candidates.at(j));
		}
 
		twod_vector ballots(ncand);
		string str;
		istringstream iss;
		for(int j = 0; j < NBALLOTS; j++) {
			getline(cin, str);
 
			if(str == "") {
				break;
			}
			iss.str(str);
 
			for(int k = 0; k < ncand; k++) {
				int value = *istream_iterator< int >(iss);
				ballots.at(k).push_back(
						value - 1
						);
			}
			iss.clear();
		}
 
		vector< int > winners;
		int j = 0;
		while(winners.size() == 0) {
			if(draw(ballots.at(0))) {
				winners = calculate(ballots.at(0),
						ncand,
						false);
				break;
			}
 
			winners = calculate(ballots.at(0), ncand, true);
			eliminate(ballots);
			j++;
		}
 
		if(!ballots.at(0).size()) {
			for(int k = 0; k < ncand; k++) {
				winners.push_back(k);
			}
		}
 
 
 
		sort(winners.begin(), winners.end());
		if(i > 0) {
			cout<<endl;
		}
		vector< int >::const_iterator p;
		for(p = winners.begin(); p < winners.end(); p++) {
			cout<<candidates.at(*p)<<endl;
		}
	}
 
	return 0;
}
Tags: , , , , , , , , , , ,

July 2, 2008

Programming Challenges: Check the Check

Filed under: Blog — krkhan @ 7:55 pm

PC/UVa IDs: 110107/10196, Popularity: B, Success rate: average, Level: 1

I had two approaches in mind for checking the check before solving this problem:

  • return a flag value from the move-generation functions as soon as opponent’s king is encountered in a reachable square.
  • Generate all reachable squares for a side first, and then check whether opponent’s king is positioned on one.

I opted for the latter because even though it was more performance-intensive, it made my move-generation functions more generic and appropriate for extensibility.

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433

#include <iostream>
#include <vector>
#include <iterator>
 
using namespace std;
 
#define EMPTY '.'
#define CROSS 'x'
 
typedef vector< vector< char > > twod_vector;
 
bool opponent(twod_vector board, int row1, int col1, int row2, int col2)
{
	return (islower(board.at(row1).at(col1))
			&& isupper(board.at(row2).at(col2)))
		|| (isupper(board.at(row1).at(col1))
			&& islower(board.at(row2).at(col2)));
}
 
twod_vector generate_move_rook_limit(twod_vector board,
		int row, int col, int limit)
{
	for(int i = row - 1, n = 0; i >= 0 && n < limit; i--, n++) {
		if(board.at(i).at(col) != EMPTY) {
			if(opponent(board, row, col, i, col)) {
				board.at(i).at(col) = CROSS;
			}
			break;
		}
		board.at(i).at(col) = CROSS;
	}
 
	for(int i = row + 1, n = 0; i <= 7 && n < limit; i++, n++) {
		if(board.at(i).at(col) != EMPTY) {
			if(opponent(board, row, col, i, col)) {
				board.at(i).at(col) = CROSS;
			}
			break;
		}
		board.at(i).at(col) = CROSS;
	}
 
	for(int j = col - 1, n = 0; j >= 0 && n < limit; j--, n++) {
		if(board.at(row).at(j) != EMPTY) {
			if(opponent(board, row, col, row, j)) {
				board.at(row).at(j) = CROSS;
			}
			break;
		}
		board.at(row).at(j) = CROSS;
	}
 
	for(int j = col + 1, n = 0; j <= 7 && n < limit; j++, n++) {
		if(board.at(row).at(j) != EMPTY) {
			if(opponent(board, row, col, row, j)) {
				board.at(row).at(j) = CROSS;
			}
			break;
		}
		board.at(row).at(j) = CROSS;
	}
 
	return board;
}
 
twod_vector generate_move_bishop_limit(twod_vector board,
		int row, int col, int limit)
{
	for(int i = row - 1, j = col - 1, n = 0;
			i >= 0 && j >= 0 && n < limit;
			i--, j--, n++) {
		if(board.at(i).at(j) != EMPTY) {
			if(opponent(board, row, col, i, j)) {
				board.at(i).at(j) = CROSS;
			}
			break;
		}
		board.at(i).at(j) = CROSS;
	}
 
	for(int i = row + 1, j = col - 1, n = 0;
			i <= 7 && j >= 0 && n < limit;
			i++, j--, n++) {
		if(board.at(i).at(j) != EMPTY) {
			if(opponent(board, row, col, i, j)) {
				board.at(i).at(j) = CROSS;
			}
			break;
		}
		board.at(i).at(j) = CROSS;
	}
 
	for(int i = row - 1, j = col + 1, n = 0;
			i >= 0 && j <= 7 && n < limit;
			i--, j++, n++) {
		if(board.at(i).at(j) != EMPTY) {
			if(opponent(board, row, col, i, j)) {
				board.at(i).at(j) = CROSS;
			}
			break;
		}
		board.at(i).at(j) = CROSS;
	}
 
	for(int i = row + 1, j = col + 1, n = 0;
			i <= 7
			&& j <= 7
			&& n < limit;
			i++, j++, n++) {
		if(board.at(i).at(j) != EMPTY) {
			if(opponent(board, row, col, i, j)) {
				board.at(i).at(j) = CROSS;
			}
			break;
		}
		board.at(i).at(j) = CROSS;
	}
 
	return board;
}
 
twod_vector generate_move_rook(twod_vector board, int row, int col)
{
	return generate_move_rook_limit(board, row, col, 8);
}
 
twod_vector generate_move_bishop(twod_vector board, int row, int col)
{
	return generate_move_bishop_limit(board, row, col, 8);
}
 
twod_vector generate_move_queen(twod_vector board, int row, int col)
{
	return generate_move_bishop_limit(
			generate_move_rook_limit(board, row, col, 8),
			row,
			col,
			8);
}
 
twod_vector generate_move_king(twod_vector board, int row, int col)
{
	return generate_move_bishop_limit(
			generate_move_rook_limit(board, row, col, 1),
			row,
			col,
			1);
}
 
twod_vector generate_move_pawn_white(twod_vector board, int row, int col)
{
	if(row - 1 >= 0) {
		if(col - 1 >= 0) {
			if(board.at(row - 1).at(col - 1) == EMPTY
				|| opponent(board, row, col,
						row - 1, col - 1)) {
				board.at(row - 1).at(col - 1) = CROSS;
			}
		}
		if(col + 1 <= 7) {
			if(board.at(row - 1).at(col + 1) == EMPTY
				|| opponent(board, row, col,
						row - 1, col + 1)) {
				board.at(row - 1).at(col + 1) = CROSS;
			}
		}
	}
 
	return board;
}
 
twod_vector generate_move_pawn_black(twod_vector board, int row, int col)
{
	if(row + 1 <= 7) {
		if(col - 1 >= 0) {
			if(board.at(row + 1).at(col - 1) == EMPTY
				|| opponent(board, row, col,
						row + 1, col - 1)) {
				board.at(row + 1).at(col - 1) = CROSS;
			}
		}
		if(col + 1 <= 7) {
			if(board.at(row + 1).at(col + 1) == EMPTY
				|| opponent(board, row, col,
						row + 1, col + 1)) {
				board.at(row + 1).at(col + 1) = CROSS;
			}
		}
	}
 
	return board;
}
 
twod_vector generate_move_knight(twod_vector board, int row, int col)
{
	if(row - 2 >= 0) {
		if(col - 1 >= 0) {
			if(board.at(row - 2).at(col - 1) == EMPTY
				|| opponent(board, row, col,
						row - 2, col - 1)) {
				board.at(row - 2).at(col - 1) = CROSS;
			}
		}
		if(col + 1 <= 7) {
			if(board.at(row - 2).at(col + 1) == EMPTY
				|| opponent(board, row, col,
						row - 2, col + 1)) {
				board.at(row - 2).at(col + 1) = CROSS;
			}
		}
	}
 
	if(row + 2 <= 7) {
		if(col - 1 >= 0) {
			if(board.at(row + 2).at(col - 1) == EMPTY
				|| opponent(board, row, col,
						row + 2, col - 1)) {
				board.at(row + 2).at(col - 1) = CROSS;
			}
		}
		if(col + 1 <= 7) {
			if(board.at(row + 2).at(col + 1) == EMPTY
				|| opponent(board, row, col,
						row + 2, col + 1)) {
				board.at(row + 2).at(col + 1) = CROSS;
			}
		}
	}
 
	if(row - 1 >= 0) {
		if(col - 2 >= 0) {
			if(board.at(row - 1).at(col - 2) == EMPTY
				|| opponent(board, row, col,
						row - 1, col - 2)) {
				board.at(row - 1).at(col - 2) = CROSS;
			}
		}
		if(col + 2 <= 7) {
			if(board.at(row - 1).at(col + 2) == EMPTY
				|| opponent(board, row, col,
						row - 1, col + 2)) {
				board.at(row - 1).at(col + 2) = CROSS;
			}
		}
	}
 
	if(row + 1 <= 7) {
		if(col - 2 >= 0) {
			if(board.at(row + 1).at(col - 2) == EMPTY
				|| opponent(board, row,
						col, row + 1, col - 2)) {
				board.at(row + 1).at(col - 2) = CROSS;
			}
		}
		if(col + 2 <= 7) {
			if(board.at(row + 1).at(col + 2) == EMPTY
				|| opponent(board, row, col,
						row + 1, col + 2)) {
				board.at(row + 1).at(col + 2) = CROSS;
			}
		}
	}
 
	return board;
}
 
twod_vector generate_move(twod_vector board, int row, int col)
{
	switch(board.at(row).at(col)) {
	case 'R':
	case 'r':
		return generate_move_rook(board, row, col);
		break;
	case 'B':
	case 'b':
		return generate_move_bishop(board, row, col);
		break;
	case 'Q':
	case 'q':
		return generate_move_queen(board, row, col);
		break;
	case 'K':
	case 'k':
		return generate_move_king(board, row, col);
		break;
	case 'P':
		return generate_move_pawn_white(board, row, col);
		break;
	case 'p':
		return generate_move_pawn_black(board, row, col);
		break;
	case 'N':
	case 'n':
		return generate_move_knight(board, row, col);
		break;
	}
 
	return board;
}
 
char mix_board_position(char a, char b)
{
	if(a == CROSS || b == CROSS) {
		return CROSS;
	}
	if(a == EMPTY) {
		return b;
	}
	return a;
}
 
twod_vector join_boards(twod_vector board1, twod_vector board2)
{
	twod_vector v(8, vector< char >(8, EMPTY));
 
	for(int i = 0; i <=7; i++) {
		transform(board1.at(i).begin(),
				board1.at(i).end(),
				board2.at(i).begin(),
				v.at(i).begin(),
				mix_board_position);
	}
 
	return v;
}
 
twod_vector calculate_reach(const twod_vector board, bool white)
{
	twod_vector reach(8, vector< char >(8, EMPTY));
 
	for(int i = 0; i <= 7; i++) {
		for(int j = 0; j<= 7; j++) {
			if((bool) isupper(board.at(i).at(j)) == white) {
				reach = join_boards(
						generate_move(
							board,
							i,
							j),
						reach
						);
			}
		}
	}
 
	return reach;
}
 
bool check_check(twod_vector board, bool white)
{
	char king = (white ? 'K' : 'k');
	twod_vector reach = calculate_reach(board, !white);
 
	for(int i = 0; i <= 7; i++) {
		for(int j = 0; j <= 7; j++) {
			if(board.at(i).at(j) == king) {
				if(reach.at(i).at(j) == CROSS) {
					return true;
				} else {
					return false;
				}
			}
		}
	}
 
	return false;
}
 
bool is_board_empty(twod_vector board)
{
	for(int i = 0; i <= 7; i++) {
		for(int j = 0; j <= 7; j++) {
			if(board.at(i).at(j) != EMPTY) {
				return false;
			}
		}
	}
 
	return true;
}
 
ostream& operator<<(ostream &out, twod_vector v)
{
	twod_vector::const_iterator p;
 
	for(p = v.begin(); p < v.end(); p++) {
		copy((*p).begin(), (*p).end(),
				ostream_iterator< char >(cout, ""));
		cout<<endl;
	}
 
	return out;
}
 
istream& operator>>(istream& in, twod_vector &v)
{
	for(twod_vector::iterator p = v.begin(); p < v.end(); p++) {
		for(vector< char >::iterator pr = (*p).begin();
				pr < (*p).end();
				pr++) {
			*pr = *istream_iterator< char >(in);
		}
	}
 
	return in;
}
 
int main(int argc, char *argv[])
{
	twod_vector board(8, vector< char >(8, '\0'));
 
	int i = 1;
	cin>>board;
	while(!is_board_empty(board)) {
		if(check_check(board, true)) {
			cout<<"Game #"<<i<<": white king is in check."
				<<endl;
		} else if(check_check(board, false)) {
			cout<<"Game #"<<i<<": black king is in check."
				<<endl;
		} else {
			cout<<"Game #"<<i<<": no king is in check."
				<<endl;
		}
 
		string dummy;
		getline(cin, dummy);
		cin>>board;
 
		i++;
	}
 
	return 0;
}
Tags: , , , , , , , , , , , , , , , , ,

July 1, 2008

Programming Challenges: Interpreter

Filed under: Blog — krkhan @ 8:38 am

PC/UVa IDs: 110106/10033, Popularity: B, Success rate: low, Level: 2

Nothing extraordinarily interesting here — typical straight-outta-the-book exercise.

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

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
 
using namespace std;
 
bool decode(int &pc, vector< int > &reg, vector< int > &ram)
{
	int inst = ram.at(pc);
	int c = inst / 100,
		a = (inst % 100) / 10,
		b = inst % 10;
 
	switch(c) {
	case 1:
		return false;
		break;
	case 2:
		reg.at(a) = b;
 
		pc++;
		break;
	case 3:
		reg.at(a) += b;
		reg.at(a) %= 1000;
 
		pc++;
		break;
	case 4:
		reg.at(a) *= b;
		reg.at(a) %= 1000;
 
		pc++;
		break;
	case 5:
		reg.at(a) = reg.at(b);
 
		pc++;
		break;
	case 6:
		reg.at(a) += reg.at(b);
		reg.at(a) %= 1000;
 
		pc++;
		break;
	case 7:
		reg.at(a) *= reg.at(b);
		reg.at(a) %= 1000;
 
		pc++;
		break;
	case 8:
		reg.at(a) = ram.at(reg.at(b));
 
		pc++;
		break;
	case 9:
		ram.at(reg.at(b)) = reg.at(a);
 
		pc++;
		break;
	case 0:
		if(reg.at(b) == 0) {
			pc++;
		} else {
			pc = reg.at(a);
		}
 
		break;
	}
 
	return true;
}
 
int main(int argc, char *argv[])
{
	string dummy;
	int ncases;
 
	cin>>ncases;
 
	// ignore two empty lines
	getline(cin, dummy);
	getline(cin, dummy);
 
	for(int n = 0; n < ncases; n++) {
		vector< int > reg(10), ram(1000);
 
		fill(reg.begin(), reg.end(), 0);
		fill(ram.begin(), ram.end(), 0);
 
		for(int i = 0; i < 1000; i++) {
			string str;
 
			getline(cin, str);
			if(str == "") {
				break;
			}
 
			istringstream iss(str);
			iss>>ram.at(i);
		}
 
		int executed = 1;
		int pc = 0;
		while(decode(pc, reg, ram)) {
			executed++;
		}
 
		if(n > 0) {
			cout<<endl;
		}
		cout<<executed<<endl;
	}
 
	return 0;
}
Tags: , , , , , , , , ,

Programming Challenges: Graphical Editor

Filed under: Blog — krkhan @ 1:31 am

PC/UVa IDs: 110105/10267, Popularity: B, Success rate: low, Level: 1

Few notes:

  • In the problem input, pixels are specified as [column# row#], whereas two-dimensional vectors (or arrays) are referenced using [row# column#] format.
  • The program would be doomed to infinite recursion if the condition on line #51 is omitted.
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <iterator>
 
using namespace std;
 
typedef vector< vector< char > > twod_vector;
 
ostream& operator<<(ostream &out, const twod_vector &v)
{
	twod_vector::const_iterator p;
 
	for(p = v.begin(); p < v.end(); p++) {
		copy((*p).begin(), (*p).end(),
				ostream_iterator< char >(cout, ""));
		cout<<endl;
	}
 
	return out;
}
 
void reset(twod_vector &image)
{
	twod_vector::iterator p;
 
	for(p = image.begin(); p < image.end(); p++) {
		fill((*p).begin(), (*p).end(), 'O');
	}
}
 
void set_pixel(twod_vector &image, int x, int y, char c)
{
	image.at(y).at(x) = c;
}
 
void fill_rect(twod_vector &image,
		int x1, int y1, int x2, int y2, char c)
{
	for(int i = y1; i <= y2; i++) {
		for(int j = x1; j <= x2; j++) {
			image.at(i).at(j) = c;
		}
	}
}
 
void fill_region(twod_vector &image, int x, int y,
		char old_color, char new_color)
{
	if(old_color == new_color) {
		return;
	}
 
	image.at(y).at(x) = new_color;
 
	if(x > 0) {
		if(image.at(y).at(x - 1) == old_color) {
			fill_region(image, x - 1, y,
					old_color, new_color);
		}
	}
 
	if(x < static_cast<int>(image.at(y).size()) - 1) {
		if(image.at(y).at(x + 1) == old_color) {
			fill_region(image, x + 1, y,
					old_color, new_color);
		}
	}
 
	if(y > 0) {
		if(image.at(y - 1).at(x) == old_color) {
			fill_region(image, x, y - 1,
					old_color, new_color);
		}
	}
 
	if(y < static_cast<int>(image.size()) - 1) {
		if(image.at(y + 1).at(x) == old_color) {
			fill_region(image, x, y + 1,
					old_color, new_color);
		}
	}
}
 
void swap(int &x, int &y)
{
	int tmp = x;
	x = y;
	y = tmp;
}
 
int main(int argc, char *argv[])
{
	twod_vector image;
	string line;
 
	getline(cin, line);
	while(line[0] != 'X') {
		istringstream iss(line);
		int m, n, x, y, x1, x2, y1, y2;
		char command, c, file_name[13];
		twod_vector::iterator p;
 
		iss>>command;
		switch(command) {
		case 'I':
			iss>>m>>n;
 
			image.clear();
			image.resize(n);
			for(p = image.begin(); p < image.end(); p++) {
				(*p).resize(m);
			}
 
			reset(image);
 
			break;
		case 'C':
			reset(image);
 
			break;
		case 'L':
			iss>>x>>y>>c;
			x--;
			y--;
 
			set_pixel(image, x, y, c);
 
			break;
		case 'V':
			iss>>x>>y1>>y2>>c;
			x--;
			y1--;
			y2--;
 
			if(y1 > y2) {
				swap(y1, y2);
			}
 
			fill_rect(image, x, y1, x, y2, c);
 
			break;
		case 'H':
			iss>>x1>>x2>>y>>c;
			x1--;
			x2--;
			y--;
 
			if(x1 > x2) {
				swap(x1, x2);
			}
 
			fill_rect(image, x1, y, x2, y, c);
 
			break;
		case 'K':
			iss>>x1>>y1>>x2>>y2>>c;
			x1--;
			y1--;
			x2--;
			y2--;
 
			if(x1 > x2) {
				swap(x1, x2);
			}
			if(y1 > y2) {
				swap(y1, y2);
			}
 
			fill_rect(image, x1, y1, x2, y2, c);
 
			break;
		case 'F':
			iss>>x>>y>>c;
			x--;
			y--;
 
			fill_region(image, x, y,
					image.at(y).at(x), c);
 
			break;
		case 'S':
			iss.ignore();
			iss.getline(file_name, 13);
 
			cout<<file_name<<endl;
			cout<<image;
 
			break;
		}
 
		getline(cin, line);
	}
 
	return 0;
}
Tags: , , , , , , , , , ,

June 30, 2008

Programming Challenges: LCD Display

Filed under: Blog — krkhan @ 8:35 am

PC/UVa IDs: 110104/706, Popularity: A, Success rate: average, Level: 1

Two-dimensional vectors again, with an array of function pointers to construct the digits’ appearance.

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177

#include <iostream>
#include <cmath>
#include <string>
#include <sstream>
#include <vector>
#include <iterator>
#include <algorithm>
 
#define PRINTCHARV	'|'
#define PRINTCHARH	'-'
#define FILLCHAR	' '
 
using namespace std;
 
vector< char > row_fill(int cols, char c1, char c2, char c3)
{
	const int firstcol = 0, lastcol = cols - 1;
	vector< char > v(cols);
 
	v.at(firstcol) = c1;
	for(int i = firstcol + 1; i <= lastcol - 1; i++) {
		v.at(i) = c2;
	}
	v.at(lastcol) = c3;
 
	return v;
}
 
vector< char > row_mid(int cols)
{
	return row_fill(cols, FILLCHAR, PRINTCHARH, FILLCHAR);
}
 
vector< char > row_left_side(int cols)
{
	return row_fill(cols, PRINTCHARV, FILLCHAR, FILLCHAR);
}
 
vector< char > row_right_side(int cols)
{
	return row_fill(cols, FILLCHAR, FILLCHAR, PRINTCHARV);
}
 
vector< char > row_both_sides(int cols)
{
	return row_fill(cols, PRINTCHARV, FILLCHAR, PRINTCHARV);
}
 
vector< char > row_empty(int cols)
{
	return row_fill(cols, FILLCHAR, FILLCHAR, FILLCHAR);
}
 
vector< vector< char > > col_empty(int s)
{
	const int rows = 2 * s + 3;
	vector< vector< char > > v(rows);
 
	for(int i = 0; i < rows; i++) {
		v.at(i).push_back(FILLCHAR);
	}
 
	return v;
}
 
vector< vector< char > > lcd(int s, int n)
{
	const int rows = 2 * s + 3;
	const int cols = s + 2;
	const int firstrow = 0,
		midrow = static_cast<int>(floor(rows / 2.00)),
		lastrow = rows - 1;
	vector< vector< char > > v(rows);
	vector< char > (*table[10][5])(int) = {
	// 0
	{row_mid, row_both_sides, row_empty, row_both_sides, row_mid},
	// 1
	{row_empty, row_right_side, row_empty, row_right_side, row_empty},
	// 2
	{row_mid, row_right_side, row_mid, row_left_side, row_mid},
	// 3
	{row_mid, row_right_side, row_mid, row_right_side, row_mid},
	// 4
	{row_empty, row_both_sides, row_mid, row_right_side, row_empty},
	// 5
	{row_mid, row_left_side, row_mid, row_right_side, row_mid},
	// 6
	{row_mid, row_left_side, row_mid, row_both_sides, row_mid},
	// 7
	{row_mid, row_right_side, row_empty, row_right_side, row_empty},
	// 8
	{row_mid, row_both_sides, row_mid, row_both_sides, row_mid},
	// 9
	{row_mid, row_both_sides, row_mid, row_right_side, row_mid}
	};
 
	for(int i = 0; i < rows; i++) {
		v.at(i).resize(cols);
	}
 
	v.at(firstrow) = (*table[n][0])(cols);
 
	for(int i = firstrow + 1; i <= midrow - 1; i++) {
		v.at(i) = (*table[n][1])(cols);
	}
 
	v.at(midrow) = (*table[n][2])(cols);
 
	for(int i = midrow + 1; i <= lastrow - 1; i++) {
		v.at(i) = (*table[n][3])(cols);
	}
 
	v.at(lastrow) = (*table[n][4])(cols);
 
	return v;
}
 
ostream& operator<<(ostream &out, const vector< vector< char > > &v)
{
 
	vector< vector< char > >::const_iterator p;
 
	for(p = v.begin(); p < v.end(); p++) {
		copy((*p).begin(), (*p).end(),
			ostream_iterator< char >(cout, ""));
		cout<<endl;
	}
 
	return out;
}
 
int main(int argc, char *argv[])
{
	int s = -1, n = -1;
 
	cin>>s>>n;
	while(s != 0) {
		const int rows = 2 * s + 3;
 
		ostringstream oss;
		oss<<n;
		istringstream iss(oss.str());
 
		vector< vector< char > >v(rows);
		char c;
		int counter = 0;
		while(iss>>c) {
			int digit = c - '0';
			vector< vector< char > > vd = lcd(s, digit);
 
 
			if(counter > 0) {
				vector< vector< char > > ve
					= col_empty(s);
 
				for(int i = 0; i < rows; i++) {
					copy(ve.at(i).begin(),
						ve.at(i).end(),
						back_inserter(v.at(i)));
				}
			}
 
			for(int i = 0; i < rows; i++) {
				copy(vd.at(i).begin(),
					vd.at(i).end(),
					back_inserter(v.at(i)));
			}
 
			counter++;
		}
		cout<<v<<endl;
 
		cin>>s>>n;
	}
 
	return 0;
}
Tags: , , , , , , ,

Programming Challenges: The Trip

Filed under: Blog — krkhan @ 8:31 am

PC/UVa IDs: 110103/10137, Popularity: B, Success rate: average, Level: 1

I have more wrong submissions for this problem than any other one until now. The reason? I was oblivious to the fact that the default rules for type-conversion between double and long in C++ include floor()ing positive values and ceil()ing negative ones.

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

#include <iostream>
#include <cmath>
#include <vector>
#include <numeric>
 
using namespace std;
 
int main(int argc, char *argv[])
{
	cout.setf(ios::fixed | ios::showpoint);
	cout.precision(2);
 
	int count;
	cin>>count;
	while(count != 0) {
		vector< double > v;
		for(int i = 0; i < count; i++) {
			v.push_back(*istream_iterator< double >(cin));
		}
 
		double avg = accumulate(v.begin(), v.end(), 0.0) / v.size();
		double low = 0, high = 0;
		for(int i = 0; i < count; i++) {
			double diff = v.at(i) - avg;
 
			if(diff < 0) {
				low -= ceil(diff * 100) / 100;
			} else {
				high += floor(diff * 100) / 100;
			}
		}
 
		cout<<"$"<<(low > high? low : high)<<endl;
 
		cin>>count;
	}
 
	return 0;
}
Tags: , , , , ,

Programming Challenges: Minesweeper

Filed under: Blog — krkhan @ 8:12 am

PC/UVa IDs: 110102/10189, Popularity: A, Success rate: high, Level: 1

Hello two-dimensional vectors.

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

#include <iostream>
#include <vector>
#include <iterator>
#include <sstream>
 
using namespace std;
 
int main(int argc, char *argv[])
{
	int rows, cols, counter;
 
	counter = 1;
	cin>>rows>>cols;
	while(rows != 0 && cols != 0) {
		vector< vector< char > > vc;
 
		for(int i = 0; i < rows; i++) {
			vector< char > row;
			char c;
			for(int j = 0; j < cols; j++) {
				cin>>c;
				row.push_back(c);
			}
			vc.push_back(row);
		}
 
		vector< vector< int > > vi;
 
		for(int i = 0; i < rows; i++) {
			vector< int > row;
			for(int j = 0; j < cols; j++) {
				row.push_back(0);
			}
			vi.push_back(row);
		}
 
		for(int i = 0; i < rows; i++) {
			for(int j = 0; j < cols; j++) {
				if(vc.at(i).at(j) == '*') {
					if(i > 0) {
						vi.at(i - 1).at(j) += 1;
					}
					if(i < rows - 1) {
						vi.at(i + 1).at(j) += 1;
					}
					if(j > 0) {
						vi.at(i).at(j - 1) += 1;
					}
					if(j < cols - 1) {
						vi.at(i).at(j + 1) += 1;
					}
					if(i > 0 && j > 0) {
						vi.at(i - 1).at(j - 1) += 1;
					}
					if(i < rows - 1 && j > 0) {
						vi.at(i + 1).at(j - 1) += 1;
					}
					if(i > 0 && j < cols - 1) {
						vi.at(i - 1).at(j + 1) += 1;
					}
					if(i < rows - 1 && j < cols - 1) {
						vi.at(i + 1).at(j + 1) += 1;
					}
				}
			}
		}
 
		if(counter > 1) {
			cout<<endl;
		}
		cout<<"Field #"<<counter<<":"<<endl;
		for(int i = 0; i < rows; i++) {
			for(int j = 0; j < cols; j++) {
				if(vc.at(i).at(j) == '*') {
					cout<<"*";
				} else {
					cout<<vi.at(i).at(j)<<"";
				}
			}
			cout<<endl;
		}
 
		counter++;
		cin>>rows>>cols;
	}
 
	return 0;
}
Tags: , , , , ,

Programming Challenges: The 3n+1 problem

Filed under: Blog — krkhan @ 8:08 am

PC/UVa IDs: 110101/100, Popularity: A, Success rate: low, Level: 1

The Collatz problem. More of an introductory “hello world” for the algorithmic programming than a “challenge”. But still:

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

#include <iostream>
 
using namespace std;
 
int length(int n)
{
	int i = 1;
 
	while(n != 1) {
		if(n % 2 == 0)  {
			n /= 2;
		} else {
			n *= 3;
			n += 1;
		}
		i++;
	}
	return i;
}
 
int main(int argc, char *argv[])
{
	int a, b, low, high;
 
	while(cin>>a>>b) {
		if(a < b) {
			low = a;
			high = b;
		} else {
			low = b;
			high = a;
		}
 
		int max = length(low);
 
		for(int i = low + 1; i <= high; i++) {
			int l = length(i);
			if(l > max) {
				max = l;
			}
		}
 
		cout<<a<<" "<<b<<" "<<max<<endl;
	}
 
	return 0;
}
Tags: , , ,
Next Page »
 
Creative Commons License

This work is licensed under a Creative Commons Attribution-Share Alike 3.0 License