chenshuo/2012.cc

## 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);
}

## 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);
	}