Created
February 2, 2012 11:39
-
-
Save chenshuo/1723099 to your computer and use it in GitHub Desktop.
A puzzle solved with breadth-first search
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// FIXME: memory leaks | |
#include <stdio.h> | |
#include <deque> | |
#include <set> | |
struct Node | |
{ | |
int value; | |
Node* parent; | |
const char* path; | |
Node(int val, Node* parent_, const char* path_) | |
: value(val), | |
parent(parent_), | |
path(path_) | |
{ | |
} | |
}; | |
void print(Node* tail) | |
{ | |
if (tail != NULL) | |
{ | |
print(tail->parent); | |
printf("%s %d\n", tail->path, tail->value); | |
} | |
} | |
typedef std::deque<Node*> Queue; | |
void bfs(Node* node) | |
{ | |
const bool trace = false; | |
std::set<int> seen; | |
Queue queue; | |
queue.push_back(node); | |
while (!queue.empty()) | |
{ | |
Node* front = queue.front(); | |
queue.pop_front(); | |
const int val = front->value; | |
if (trace) printf("%d :", val); | |
if (seen.find(val) == seen.end()) | |
{ | |
seen.insert(val); | |
if (val == 2017) | |
{ | |
printf("found 2017\n"); | |
printf(" 2011\n"); | |
print(front); | |
printf(" -5 2012\n"); | |
break; | |
} | |
else | |
{ | |
if (val % 2 == 1) | |
{ | |
int newval = (val+7)/2; | |
if (trace) printf("lu %d ", newval); | |
Node* next = new Node(newval, front, "+7/2"); | |
queue.push_back(next); | |
} | |
if (val % 2 == 0) | |
{ | |
int newval = val/2 + 7; | |
if (trace) printf("ld %d ", newval); | |
Node* next = new Node(newval, front, "/2+7"); | |
queue.push_back(next); | |
} | |
{ | |
int newval = val*3 - 5; | |
if (trace) printf("ru %d ", newval); | |
Node* next = new Node(newval, front, "*3-5"); | |
queue.push_back(next); | |
} | |
{ | |
int newval = (val-5)*3; | |
if (trace) printf("rd %d ", newval); | |
Node* next = new Node(newval, front, "-5*3"); | |
queue.push_back(next); | |
} | |
} | |
} | |
if (trace) printf("\n"); | |
} | |
} | |
int main() | |
{ | |
Node root(2018, NULL, " +7"); | |
bfs(&root); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
--- 2012.cc 2012-02-01 14:45:38.000000000 +0800 | |
+++ 2012a.cc 2012-02-01 15:28:02.000000000 +0800 | |
@@ -1,5 +1,5 @@ | |
#include <stdio.h> | |
-#include <deque> | |
+#include <boost/ptr_container/ptr_vector.hpp> | |
#include <set> | |
struct Node | |
@@ -31,12 +29,13 @@ | |
{ | |
const bool trace = false; | |
std::set<int> seen; | |
- Queue queue; | |
+ boost::ptr_vector<Node> queue; | |
queue.push_back(node); | |
+ int current = 0; | |
while (!queue.empty()) | |
{ | |
- Node* front = queue.front(); | |
- queue.pop_front(); | |
+ Node* front = &queue[current]; | |
+ ++current; | |
const int val = front->value; | |
if (trace) printf("%d :", val); | |
if (seen.find(val) == seen.end()) | |
@@ -87,6 +86,6 @@ | |
int main() | |
{ | |
- Node root(2018, NULL, " +7"); | |
- bfs(&root); | |
+ Node* root = new Node(2018, NULL, " +7"); | |
+ bfs(root); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
the best solution find with