-
Notifications
You must be signed in to change notification settings - Fork 1
/
pancakes.cpp
156 lines (129 loc) · 3.61 KB
/
pancakes.cpp
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
// Jeff Ruhl
// Flipping Pancakes
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <cstring>
#include <vector>
#include <set>
#include <stack>
#include <queue>
using namespace std;
struct Pancake
{
int size;
bool is_burned_side_up;
};
class PancakeStack
{
public:
PancakeStack( const string& input ) {
_string_representation = input;
for ( auto pancake = input.begin(); pancake != input.end(); ++pancake ) {
if ( isupper( *pancake ) ) {
Pancake bird = { *pancake - 65, false };
_pancakes.push_back( bird );
}
else {
Pancake bird = { *pancake - 97, true };
_pancakes.push_back( bird );
}
}
}
PancakeStack flip( int howMany ) const {
PancakeStack pancake_stack = *this;
vector<Pancake> flipped_pancakes;
for ( int i = 0; i < howMany; ++i ) {
Pancake pancake = pancake_stack._pancakes.back();
pancake_stack._pancakes.pop_back();
flipped_pancakes.push_back( pancake );
}
for ( auto pancake = flipped_pancakes.begin(); pancake != flipped_pancakes.end(); ++pancake ) {
pancake->is_burned_side_up = !pancake->is_burned_side_up;
pancake_stack._pancakes.push_back( *pancake );
}
pancake_stack.update_string_representation();
return pancake_stack;
}
bool is_presentable() const {
bool result = true;
int prev_pancake_size = 0;
for ( auto pancake = _pancakes.begin(); pancake != _pancakes.end(); ++pancake ) {
if ( pancake->is_burned_side_up || pancake->size < prev_pancake_size ) {
result = false;
break;
}
prev_pancake_size = pancake->size;
}
return result;
}
size_t size() const {
return _pancakes.size();
}
bool operator<( const PancakeStack& other ) const {
return this->_string_representation < other._string_representation;
}
private:
deque<Pancake> _pancakes;
string _string_representation;
void update_string_representation() {
stringstream str( stringstream::in | stringstream::out );
for ( auto pancake = _pancakes.begin(); pancake != _pancakes.end(); ++pancake ) {
if ( pancake->is_burned_side_up ) {
str << (char)(pancake->size + 97);
}
else {
str << (char)(pancake->size + 65);
}
}
_string_representation = str.str();
}
};
template<typename T>
struct Node
{
T value;
int depth;
};
int find_minimum_flips_to_make_pancake_stack_presentable( const PancakeStack& pancake_stack ) {
queue<Node<PancakeStack> > stacks;
set<PancakeStack> found_stacks;
Node<PancakeStack> first_node = { pancake_stack, 0 };
stacks.push( first_node );
while ( !stacks.empty() ) {
auto node = stacks.front(); stacks.pop();
auto& stack = node.value;
if ( node.value.is_presentable() ) {
return node.depth;
}
else {
for ( int pancakes_to_flip = 1; pancakes_to_flip <= stack.size(); ++pancakes_to_flip ) {
Node<PancakeStack> new_node = { stack.flip( pancakes_to_flip ), node.depth + 1 };
if ( found_stacks.end() == found_stacks.find( new_node.value ) ) {
stacks.push( new_node );
found_stacks.insert( new_node.value );
}
}
}
}
}
int main( int argc, char const *argv[] ) {
ifstream fin( "pancakes.in" );
if ( fin ) {
ofstream fout( "pancakes.out" );
string line;
getline( fin, line );
while ( "0" != line ) {
PancakeStack pancake_stack( line );
int flip_count = find_minimum_flips_to_make_pancake_stack_presentable( pancake_stack );
fout << flip_count << endl;
getline( fin, line );
}
fout.close();
fin.close();
}
else {
cout << "Couldn't open file 'pancakes.in'" << endl;
}
}