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
|
/*
Challenge 101
TASK #1 � Pack a Spiral
Submitted by: Stuart Little
You are given an array @A of items (integers say, but they can be anything).
Your task is to pack that array into an MxN matrix spirally counterclockwise,
as tightly as possible.
�Tightly� means the absolute value |M-N| of the difference has to be as small
as possible.
*/
#include <iostream>
#include <iomanip>
#include <vector>
int numbers_width;
std::vector<int> collect_numbers(int argc, char* argv[]) {
std::vector<int> numbers;
for (int i = 0; i < argc; i++) {
numbers.push_back(atoi(argv[i]));
if (numbers[i] >= 1000 && numbers_width < 4) numbers_width = 4;
else if (numbers[i] >= 100 && numbers_width < 3) numbers_width = 3;
else if (numbers[i] >= 10 && numbers_width < 2) numbers_width = 2;
else if (numbers_width < 1) numbers_width = 1;
}
return numbers;
}
void smallest_rect(int n, int& width, int& height) {
width = 1; height = n;
for (int i = 1; i <= n; i++) {
if ((n % i) == 0) {
width = i; height = n / i;
if (width >= height)
break;
}
}
}
std::vector<std::vector<int>> make_empty_rect(int width, int height) {
std::vector<std::vector<int>> rect;
for (int r = 0; r < height; r++) {
rect.push_back({});
for (int c = 0; c < width; c++)
rect[r].push_back(-1);
}
return rect;
}
void fill_spiral(std::vector<std::vector<int>>& rect,
std::vector<int>& numbers) {
int width = static_cast<int>(rect[0].size());
int height = static_cast<int>(rect.size());
int count = static_cast<int>(numbers.size());
int i = 0;
int r = height - 1;
int c = 0;
while (i < count) {
// go East
while (c < width && rect[r][c] < 0) {
rect[r][c] = numbers[i++];
c++;
}
c--; r--;
// go North
while (r >= 0 && rect[r][c] < 0) {
rect[r][c] = numbers[i++];
r--;
}
r++; c--;
// go West
while (c >= 0 && rect[r][c] < 0) {
rect[r][c] = numbers[i++];
c--;
}
c++; r++;
// go South
while (r < height && rect[r][c] < 0) {
rect[r][c] = numbers[i++];
r++;
}
r--; c++;
}
}
void print_spiral(std::vector<std::vector<int>>& rect) {
int width = static_cast<int>(rect[0].size());
int height = static_cast<int>(rect.size());
for (int r = 0; r < height; r++) {
for (int c = 0; c < width; c++)
std::cout << std::setw(numbers_width + 1) << rect[r][c];
std::cout << std::endl;
}
}
void spiral(int count, char* nums[]) {
std::vector<int> numbers = collect_numbers(count, nums);
int height, width;
smallest_rect(count, width, height);
std::vector<std::vector<int>> rect = make_empty_rect(width, height);
fill_spiral(rect, numbers);
print_spiral(rect);
}
int main(int argc, char* argv[]) {
if (argc == 1) {
std::cerr << "Usage: ch-1 N..." << std::endl;
exit(EXIT_FAILURE);
}
else
spiral(--argc, ++argv);
}
|
