chenshuo · February 2, 2012 11:39 · chenshuo · Feb 2, 2012 · hrluo · Feb 2, 2012
diff --git a/2012.cc b/2012.cc
 // 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);
 }
diff --git a/fix_memory_leak.diff b/fix_memory_leak.diff
 --- 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);
 }
	// 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);
	}
	--- 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);
	}