-
Notifications
You must be signed in to change notification settings - Fork 0
/
Pancakes_CRASSET.tar
238 lines (181 loc) · 10.5 KB
/
Pancakes_CRASSET.tar
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
pancakes.cpp 0100777 0000000 0000000 00000015036 13202117710 010304 0 ustar 00
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <set>
#include <unordered_set>
#include <utility> // for pair
#include <tuple>
#include "pancakes.hpp"
using std::cout;
using std::cin;
using std::endl;
using std::pair;
using std::set;
using std::string;
using std::get;
using std::unordered_set;
// <RealCost,Estimated End Cost,stack vector,flip vector>
typedef std::tuple<int,int,stack_type,flip_type> pancake_stack;
/* ------------------------------------------------------------------------- *
* Comparison function to sort the vectors in ascending order of cost in the set
* PARAMETERS
* - Two tuples that contain the vector of ints to sort as well as it's realCost and Estimated
* end cost
* ------------------------------------------------------------------------- */
bool compare(const pancake_stack stackA, const pancake_stack stackB){
int totalCostA = get<0>(stackA)+ get<1>(stackA);
int totalCostB = get<0>(stackB)+ get<1>(stackB);
if(totalCostA == totalCostB){
return stackA < stackB;
}
return totalCostA < totalCostB ;
}
/* ------------------------------------------------------------------------- *
* Function that returns an iterator to the max that is not at it's place of a vector
*
* PARAMETERS
* - One vector of ints
* end cost
* ------------------------------------------------------------------------- */
stack_type::iterator getMax(stack_type& stackA) {
stack_type::iterator maximum;
stack_type::size_type i = 0;
maximum = max_element(stackA.begin(),stackA.end());
// Iterate until the found maximum is not at it's place
while(maximum == stackA.end()-1-i) {
i++;
maximum = max_element(stackA.begin(),stackA.end()-i);
}
return maximum;
}
/* ------------------------------------------------------------------------- *
* Function that generates a hashCode from a given vector of ints
*
* PARAMETERS
* - One vector of ints
* ------------------------------------------------------------------------- */
size_t stackHash(const stack_type& stackA) {
size_t intHash = 0;
for (int i : stackA) {
intHash = intHash*10 + i;
}
return intHash;
}
/* ------------------------------------------------------------------------- *
* Function that returns the estimated end cost of a vector of ints
*
* PARAMETERS
* - One tuple containing information about the vector of ints to sort
* ------------------------------------------------------------------------- */
int getEstCost(pancake_stack& stackA) {
return *(getMax(get<2>(stackA)));
}
void astar_pancake_sort(const stack_type& pancakes, flip_type& flips) {
stack_type pancakes_copy;
// Pointer to the comparison function
bool(*compare_pt)(const pancake_stack, const pancake_stack) = compare;
//Create the set
set<pancake_stack,bool(*)(pancake_stack,pancake_stack)> p_queue(compare_pt);
//Copy the original pancakes
std::copy(pancakes.begin(),pancakes.end(),back_inserter(pancakes_copy));
//Create and initialie the tuple
pancake_stack initial_stack = std::make_tuple(0,0,pancakes_copy,flips);
pancake_stack parent_stack = initial_stack ;
//Inserting the first stack
p_queue.insert(initial_stack);
//Creating a container and iterator to store generated stacks
unordered_set<size_t> StackSet;
std::pair<unordered_set<size_t>::iterator,bool> foundStack;
//Insert the initial stack into the set
foundStack = StackSet.insert(stackHash(get<2>(initial_stack)));
while(!std::is_sorted(get<2>(parent_stack).begin(),get<2>(parent_stack).end())) {
//Extract the lowest cost stack
if(!p_queue.empty()){
parent_stack = *(p_queue.begin());
p_queue.erase(p_queue.begin());
}
//Generate children from parent stack
for(stack_type::size_type i = 1; i < get<2>(parent_stack).size(); i++) {
pancake_stack child_stack = parent_stack;
//Flip the stack
std::reverse(get<2>(child_stack).begin(),get<2>(child_stack).begin()+ 1 + i);
//Looking in the StackSet if the stack hasn't already been encountered
foundStack = StackSet.insert(stackHash(get<2>(child_stack)));
if(foundStack.second == false){
continue;
}
//Pushing the flip
get<3>(child_stack).push_back(i);
//Computing the cost
int realCost = i+1; // i+1 pancakes were flipped
int estCost = getEstCost(child_stack);
get<0>(child_stack) += realCost; // Add the child's realCost to the parent's realCost
get<1>(child_stack) = estCost;
//Insert child into the set
p_queue.insert(child_stack);
}
}
cout << "The size of the priority queue is : " << p_queue.size() << endl;
cout << "The best cost was: " << get<0>(parent_stack) + get<1>(parent_stack) <<endl;
cout << " The flips vector contains : ";
for(flip_type::iterator it = get<3>(parent_stack).begin(); it != get<3>(parent_stack).end() ; it++ ) {
cout << ' '<<*it ;
}
cout << endl;
}
void simple_pancake_sort(const stack_type& pancakes, flip_type& flips){
stack_type pancakes_copy;
stack_type::iterator maximum;
std::copy(pancakes.begin(),pancakes.end(),back_inserter(pancakes_copy));
if(!is_sorted(pancakes_copy.begin(), pancakes_copy.end())) {
while(pancakes_copy.size() != 1){
//Extract the maximum
maximum = getMax(pancakes_copy);
//If the maximum is at the beginning, we just flip the whole stack
if(maximum == pancakes_copy.begin()) {
std::reverse(pancakes_copy.begin(),pancakes_copy.end()); // flip the whole stack
flips.push_back(distance(pancakes_copy.begin(),pancakes_copy.end()-1));
}else if(maximum != pancakes_copy.end()-1){
flips.push_back(distance(pancakes_copy.begin(),maximum));
std::reverse(pancakes_copy.begin(),++maximum); // flip the max to the top
std::reverse(pancakes_copy.begin(),pancakes_copy.end()); // flip the whole stack
flips.push_back(distance(pancakes_copy.begin(),pancakes_copy.end()-1));
}
pancakes_copy.pop_back();
}
}
cout << "The flip vector contains :";
for(flip_type::size_type i = 0; i< flips.size();i++) {
cout << ' ' << flips[i];
}
cout << endl;
} pancakes.hpp 0100777 0000000 0000000 00000002621 13202117273 010311 0 ustar 00 #ifndef PANCAKES_H
#define PANCAKES_H
#include <vector>
typedef std::vector<int> stack_type;
typedef std::vector<stack_type::size_type> flip_type;
/* ------------------------------------------------------------------------- *
* Function that sorts a vector of ints using the prefix reversal method,
* commonly knows as pancake sorting
* This function uses the naive approach to find the max, flip it on top
* then flip the whole stack over. This guarantees a fast method but it is
* not optimal.
* PARAMETERS
* - The vector of ints that needs to be sorted
* - One vector of ints that will contain the index where the stack was flipped
* ------------------------------------------------------------------------- */
void simple_pancake_sort(const stack_type& pancakes, flip_type& flips);
/* ------------------------------------------------------------------------- *
* Function that sorts a vector of ints using the prefix reversal method,
* commonly knows as pancake sorting
*
* This function uses the A* algorithm to find the most optimal solution.
* PARAMETERS
* - The vector of ints that needs to be sorted
* - One vector of ints that will contain the indexes where the stack was flipped
* ------------------------------------------------------------------------- */
void astar_pancake_sort(const stack_type& pancakes, flip_type& flips);
#endif // PANCAKES_H