UVa | Inspirated

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.

#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;
}

#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: Algorithms, Australian, C++, Code, Function, Map, Programming Challenges, Reference, STL, UVa, Vector, Voting

Comments (5)

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.

#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;
}

#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: Algorithms, Bishop, C++, Check, Chess, Code, Function, King, Knight, Pawn, Programming Challenges, Queen, Reference, Rook, STL, Transform, UVa, Vector

Comments (1)

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.

#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: Algorithms, C++, Code, Function, Interpreter, Programming Challenges, Reference, STL, UVa, Vector

Comments (2)

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.

#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;
}

#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: Algorithms, C++, Code, Function, Function Pointer, Programming Challenges, Recursion, Reference, STL, UVa, Vector

Comments (4)

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.

#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;
}

#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: Algorithms, C++, Code, Function Pointer, Programming Challenges, STL, UVa, Vector

Comments Off

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.

#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: C++, Code, Programming Challenges, STL, UVa, Vector

Comments Off

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.

#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: C++, Code, Programming Challenges, STL, UVa, Vector

Comments (2)

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:

#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: C++, Code, Programming Challenges, UVa

Comments Off

Programming Challenges

Filed under: Blog — krkhan @ 7:58 am

There are few better ways of spending your vacations than trying to solve a series of programming problems, especially when you’re trying to learn something new related to those problems.

And this is where Programming Challenges pops in the picture. It is a combination of book containing about one hundred selected problems from various international competitions of the past. There are two online judges for checking solutions, the book’s own website and another site called UVa Online Judge. I will be constantly keep posting code on my blog as I keep solving problems according to the book’s chronological order.

P.S. Since I wanted to practice STL, please bare with its bloated usage that you’re bound to find in my solutions.

Tags: C++, Code, Programming Challenges, STL, UVa

Comments Off