Inspirated

 
 

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: , , ,

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: , , , ,
 
Creative Commons License

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