Sunday, April 28, 2013

MongoDB Aggregation Framework Basics Explained

This post assumes that, the reader has a very good understanding of SQL.

To understand the MongoDB's aggregation framework, lets start with inserting the following data.
db.Student.insert ({Student_Name:"Kalki",  Class: "2", Mark_Scored:100, Subject: ["Tamil", "English", "Maths"]})
db.Student.insert ({Student_Name:"Matsya", Class: "1", Mark_Scored:10,  Subject: ["Tamil", "English"]})

db.Student.insert ({Student_Name:"Krishna",Class: "1", Mark_Scored:50,  Subject: ["Tamil"]})
db.Student.insert ({Student_Name:"Buddha", Class: "2", Mark_Scored:60,  Subject: ["Tamil"]})
db.Student.insert ({Student_Name:"Rama",   Class: "2", Mark_Scored:80,  Subject: ["Tamil"]})

db.Student.insert ({Student_Name:"Krishna",Class: "1", Mark_Scored:50,  Subject: ["English"]})
db.Student.insert ({Student_Name:"Buddha", Class: "2", Mark_Scored:60,  Subject: ["English"]})
db.Student.insert ({Student_Name:"Rama",   Class: "2", Mark_Scored:80,  Subject: ["English"]})

db.Student.insert ({Student_Name:"Matsya", Class: "1", Mark_Scored:67,  Subject: ["Maths"]})
db.Student.insert ({Student_Name:"Krishna",Class: "1", Mark_Scored:95,  Subject: ["Maths"]})
db.Student.insert ({Student_Name:"Buddha", Class: "2", Mark_Scored:88,  Subject: ["Maths"]})
db.Student.insert ({Student_Name:"Rama",   Class: "2", Mark_Scored:40,  Subject: ["Maths"]})

Pipeline

The aggregation framework is based on pipeline concept, just like unix pipeline. There can be N number of operators. Output of first operator will be fed as input to the second operator. Output of second operator will be fed as input to the third operator and so on.


Pipeline Operators

Following are the basic pipeline operators and let us make use of these operators over the sample data which we created. We are not going to discuss about Map-Reduce in this post.

  1. $match
  2. $unwind
  3. $group
  4. $project
  5. $skip
  6. $limit
  7. $sort

$match

This is similar to MongoDB Collection's find method and SQL's WHERE clause. Basically this filters the data which is passed on to the next operator. There can be multiple $match operators in the pipeline.


Note:The data what we pass to the aggregate function should be a list of Javascript objects (Python dictionaries). Each and every operator should be in a separate javascript object like shown in all the examples below.

Example:We want to consider only the marks of the students who study in Class "2"
db.Student.aggregate ([
  {
     "$match":
     {
        "Class":"2"
     }
  }
  ])
and the result is
{
	"result" : [
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa5c"),
			"Student_Name" : "Kalki",
			"Class" : "2",
			"Mark_Scored" : 100,
			"Subject" : [
				"Tamil",
				"English",
				"Maths"
			]
		},
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa5f"),
			"Student_Name" : "Buddha",
			"Class" : "2",
			"Mark_Scored" : 60,
			"Subject" : [
				"Tamil"
			]
		},
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa60"),
			"Student_Name" : "Rama",
			"Class" : "2",
			"Mark_Scored" : 80,
			"Subject" : [
				"Tamil"
			]
		},
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa62"),
			"Student_Name" : "Buddha",
			"Class" : "2",
			"Mark_Scored" : 60,
			"Subject" : [
				"English"
			]
		},
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa63"),
			"Student_Name" : "Rama",
			"Class" : "2",
			"Mark_Scored" : 80,
			"Subject" : [
				"English"
			]
		},
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa66"),
			"Student_Name" : "Buddha",
			"Class" : "2",
			"Mark_Scored" : 88,
			"Subject" : [
				"Maths"
			]
		},
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa67"),
			"Student_Name" : "Rama",
			"Class" : "2",
			"Mark_Scored" : 40,
			"Subject" : [
				"Maths"
			]
		}
	],
	"ok" : 1
}
Let us say, we want to consider only the marks of the students who study in Class "2" and whose marks are more than or equal to 80
db.Student.aggregate ([
  {
     "$match":
     {
        "Class":"2",
        "Mark_Scored":
        {
           "$gte": 80
        }
     }
  }
  ])
Or we can use $match operator twice to achieve the same result
db.Student.aggregate ([
  {
     "$match":
     {
        "Class":"2",
     }
  },
  {
     "$match":
     {
        "Mark_Scored":
        {
           "$gte": 80
        }
     }
  }
  ])
and the result would be
{
	"result" : [
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa5c"),
			"Student_Name" : "Kalki",
			"Class" : "2",
			"Mark_Scored" : 100,
			"Subject" : [
				"Tamil",
				"English",
				"Maths"
			]
		},
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa60"),
			"Student_Name" : "Rama",
			"Class" : "2",
			"Mark_Scored" : 80,
			"Subject" : [
				"Tamil"
			]
		},
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa63"),
			"Student_Name" : "Rama",
			"Class" : "2",
			"Mark_Scored" : 80,
			"Subject" : [
				"English"
			]
		},
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa66"),
			"Student_Name" : "Buddha",
			"Class" : "2",
			"Mark_Scored" : 88,
			"Subject" : [
				"Maths"
			]
		}
	],
	"ok" : 1
}

$unwind

This will be very useful when the data is stored as list. When the unwind operator is applied on a list data field, it will generate a new record for each and every element of the list data field on which unwind is applied. It basically flattens the data. Lets see an example to understand this better

Note: The field name, on which unwind is applied, should be prefixed with $ (dollar sign)

Example:Lets apply unwind over "Kalki"'s data.
db.Student.aggregate ([
   {
      "$match":
      {
         "Student_Name": "Kalki",
      }
   }
])
This generates the following output
{
	"result" : [
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa5c"),
			"Student_Name" : "Kalki",
			"Class" : "2",
			"Mark_Scored" : 100,
			"Subject" : [
				"Tamil",
				"English",
				"Maths"
			]
		}
	],
	"ok" : 1
}
Whereas
db.Student.aggregate ([
   {
      "$match":
      {
         "Student_Name": "Kalki",
      }
   },
   {
      "$unwind": "$Subject"
   }
])
will generate the following output
{
	"result" : [
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa5c"),
			"Student_Name" : "Kalki",
			"Class" : "2",
			"Mark_Scored" : 100,
			"Subject" : "Tamil"
		},
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa5c"),
			"Student_Name" : "Kalki",
			"Class" : "2",
			"Mark_Scored" : 100,
			"Subject" : "English"
		},
		{
			"_id" : ObjectId("517cbb98eccb9ee3d000fa5c"),
			"Student_Name" : "Kalki",
			"Class" : "2",
			"Mark_Scored" : 100,
			"Subject" : "Maths"
		}
	],
	"ok" : 1
}

$group

Now that we have flatten the data to be processed, lets try and group the data to process them. The group pipeline operator is similar to the SQL's GROUP BY clause. In SQL, we can't use GROUP BY unless we use any of the aggregation functions. The same way, we have to use an aggregation function in MongoDB as well. You can read more about the aggregation functions here. As most of them are like in SQL, I don't think much explanation would be needed.


Note: The _id element in group operator is a must. We cannot change it to some other name. MongoDB identifies the grouping expression with the _id field only.

Example: Lets try and get the sum of all the marks scored by each and every student, in Class "2"
db.Student.aggregate ([
   {
      "$match":
      {
         "Class": "2"
      }
   },
   {
      "$unwind": "$Subject"
   },
   {
      "$group":
      {
         "_id":
         {
            "Student_Name" : "$Student_Name"
         },
         "Total_Marks":
         {
            "$sum": "$Mark_Scored"
         }
      }
   }
])
If we look at this aggregation example, we have specified an _id element and Total_Marks element. The _id element tells MongoDB to group the documents based on Student_Name field. The Total_Marks uses an aggregation function $sum, which basically adds up all the marks and returns the sum. This will produce this Output
{
	"result" : [
		{
			"_id" : {
				"Student_Name" : "Rama"
			},
			"Total_Marks" : 200
		},
		{
			"_id" : {
				"Student_Name" : "Buddha"
			},
			"Total_Marks" : 208
		},
		{
			"_id" : {
				"Student_Name" : "Kalki"
			},
			"Total_Marks" : 300
		}
	],
	"ok" : 1
}
We can use the sum function to count the number of records match the grouped data. Instead of "$sum": "$Mark_Scored", "$sum": 1 will count the number of records. "$sum": 2 will add 2 for each and every grouped data.
db.Student.aggregate ([
   {
      "$match":
      {
         "Class": "2"
      }
   },
   {
      "$unwind": "$Subject"
   },
   {
      "$group":
      {
         "_id":
         {
            "Student_Name" : "$Student_Name"
         },
         "Total_Marks":
         {
            "$sum": 1
         }
      }
   }
])
This will produce this Output
{
	"result" : [
		{
			"_id" : {
				"Student_Name" : "Rama"
			},
			"Total_Marks" : 3
		},
		{
			"_id" : {
				"Student_Name" : "Buddha"
			},
			"Total_Marks" : 3
		},
		{
			"_id" : {
				"Student_Name" : "Kalki"
			},
			"Total_Marks" : 3
		}
	],
	"ok" : 1
}
This is because each and every student has marks for three subjects.

$project

The project operator is similar to SELECT in SQL. We can use this to rename the field names and select/deselect the fields to be returned, out of the grouped fields. If we specify 0 for a field, it will NOT be sent in the pipeline to the next operator. We can even flatten the data using project as shown in the example below

Example:
db.Student.aggregate ([
   {
      "$match":
      {
         "Class": "2"
      }
   },
   {
      "$unwind": "$Subject"
   },
   {
      "$group":
      {
         "_id":
         {
            "Student_Name" : "$Student_Name"
         },
         "Total_Marks":
         {
            "$sum": "$Mark_Scored"
         }
      }
   },
   {
      "$project":
      {
         "_id":0,
         "Name":  "$_id.Student_Name",
         "Total": "$Total_Marks"
      }
   }
])
will result in
{
	"result" : [
		{
			"Name" : "Rama",
			"Total" : 200
		},
		{
			"Name" : "Buddha",
			"Total" : 208
		},
		{
			"Name" : "Kalki",
			"Total" : 300
		}
	],
	"ok" : 1
}
Lets say we try to retrieve Subject field by specifying project like shown below. MongoDB will simply ignore the Subject field, since it is not used in the group operator's _id field.
"$project":
{
   "_id":0,
   "Subject":1,
   "Name":  "$_id.Student_Name",
   "Total": "$Total_Marks"
}

$sort

This is similar to SQL's ORDER BY clause. To sort a particular field in descending order specify -1 and specify 1 if that field has to be sorted in ascending order. I don't think this section needs more explanation. Lets straight away look at an example
Example:
db.Student.aggregate ([
   {
      "$match":
      {
         "Class": "2"
      }
   },
   {
      "$unwind": "$Subject"
   },
   {
      "$group":
      {
         "_id":
         {
            "Student_Name" : "$Student_Name"
         },
         "Total_Marks":
         {
            "$sum": "$Mark_Scored"
         }
      }
   },
   {
      "$project":
      {
         "_id":0,
         "Name":  "$_id.Student_Name",
         "Total": "$Total_Marks"
      }
   },
   {
      "$sort":
      {
         "Total":-1,
         "Name":1
      }
   }
])
Will Sort the data based on Marks in descending Order first and then by Name in Ascending Order.
{
	"result" : [
		{
			"Name" : "Kalki",
			"Total" : 300
		},
		{
			"Name" : "Buddha",
			"Total" : 208
		},
		{
			"Name" : "Rama",
			"Total" : 200
		}
	],
	"ok" : 1
}

$limit and $skip

These two operators can be used to limit the number of documents being returned. They will be more useful when we need pagination support.

Example:
db.Student.aggregate ([
   {
      "$match":
      {
         "Class": "2"
      }
   },
   {
      "$unwind": "$Subject"
   },
   {
      "$group":
      {
         "_id":
         {
            "Student_Name" : "$Student_Name"
         },
         "Total_Marks":
         {
            "$sum": "$Mark_Scored"
         }
      }
   },
   {
      "$project":
      {
         "_id":0,
         "Name":  "$_id.Student_Name",
         "Total": "$Total_Marks"
      }
   },
   {
      "$sort":
      {
         "Total":-1,
         "Name":1
      }
   },
   {
      "$limit":2,
   },
   {
      "$skip":1,
   }
])
will result in
{ "result" : [ { "Name" : "Buddha", "Total" : 208 } ], "ok" : 1 }
Because the limit operator receives 3 documents from the sort operator and allows only the first two documents to pass through it, thereby dropping Rama's record. The skip operator skips one document (that means the first document (Kalki's document) is dropped) and allows only the Buddha's document to pass through.

All the examples shown here are readily usable with pyMongo (Just replace db.Student with your Collection object name)


Friday, April 26, 2013

Ubuntu Screen Configuration

As we all know Screen is an excellent program. Here is how my ~/.screenrc looks like

   vbell off
   defscrollback 10000
   hardstatus on
   hardstatus alwayslastline "%{wk}%-w%{kw}%n %t%{-}%+w %=%{Gk} %H %{Wk} %d-%M-%Y %C:%s %a %D "
   termcapinfo xterm ti@:te@
   startup_message off
   msgwait 1
   altscreen on
   escape ``
   bind c screen 1
   bind ^c screen 1
   bind 0 select 10
   screen 1

And this is how it looks in action



  1. blockquote (the key right above Tab key) will be the command character
  2. As you see in the image, the screen numbers will begin with 1
  3. The bottom bar shows list of open terminals, machine name, date, time, weekday
  4. `+c will create a new terminal
  5. `+1,`+2,`+3,... will switch to the respective terminals



Thursday, April 25, 2013

PuttY style word selection in xfce4-terminal

For all those who have made themselves comfortable with PuttY software, word selection by double clicking in xfce4-terminal would be difficult to get used to.

So they can follow these steps to use PuttY style word selection.

  1. Right click anywhere inside xfce4-terminal and select Preferences

  2. Select the Advanced tab

  3. Paste the following text in the box below "Double Click" section
-A-Za-z0-9./?_~

That's it. Enjoy PuttY style word selection on xfce4-terminal :)

MongoDB Miscellaneous

Querying based on Date & Time
   db.[Colletion].find ({Date:ISODate('2013-04-22T00:00:00Z')})

Equivalent of Oracle's Count function
   db.[Collection].find ({'FieldName':'value').length

Find distinct values of a column, after Querying
   db.[Collection].distinct ('ColumnName', {'SearchColumnName' : 'SearchValue'})

Number of distinct values
   db.[Collection].distinct ('ColumnName').length

Sorting the returned result with pymongo
  db.[Collection].find().sort (
  [
   ("FieldName1", pymongo.DESCENDING),
   ("FieldName2", pymongo.DESCENDING),
   ("FieldName3", pymongo.ASCENDING),
  ])


Ubuntu Screen Custom Resolution

Configuring the screen resolution to custom value in Ubuntu was a big headache to me. With most of the monitors I was not able to change the resolution to something of my choice, apart from what is listed in the Display settings. Then I found the following way.

First, lets see how to get to know the list of displays attached to Ubuntu

~$ xrandr
Screen 0: minimum 8 x 8, current 2881 x 1280, maximum 16384 x 16384
VGA-0 connected 1600x1280+1281+0 (normal left inverted right x axis y axis) 376mm x 301mm
   1280x1024      60.0*+   75.0  
   1152x864       75.0  
   1024x768       75.0     60.0  
   800x600        75.0     60.3  
   640x480        75.0     59.9  
LVDS-0 connected (normal left inverted right x axis y axis)
   1600x900       60.0 +   40.0  
DP-0 connected 1280x1024+0+0 (normal left inverted right x axis y axis) 376mm x 301mm
   1280x1024      60.0*+   75.0  
   1152x864       75.0  
   1024x768       75.0     60.0  
   800x600        75.0     60.3  
   640x480        75.0     59.9  
DP-1 disconnected (normal left inverted right x axis y axis)
HDMI-0 disconnected (normal left inverted right x axis y axis)
DP-2 disconnected (normal left inverted right x axis y axis)
DP-3 disconnected (normal left inverted right x axis y axis)
~$ 
This is what I got on my machine. And following are the display names as per Ubuntu.
VGA-0
LVDS-0
DP-0
Now to set the resolution 1600x900 on VGA-0, I would execute the following

xrandr --newmode "1600x900_60.00"  118.25  1600 1696 1856 2112  900 903 908 934 -hsync +vsync
xrandr --addmode VGA-0 "1600x900_60.00"
xrandr --output VGA-0 --mode "1600x900_60.00"

First command creates a new mode with resolution 1600x900
Second command makes it available for use, with display (in this case VGA-0)
Third command selects the newly added mode as the display resolution for the specified display

We see that, the first line has lot of numbers. To come up with those numbers, there is a helper tool called cvt. It takes width and height as inputs.

~$ cvt 1600 1280
# 1600x1280 59.92 Hz (CVT 2.05M4) hsync: 79.51 kHz; pclk: 171.75 MHz
Modeline "1600x1280_60.00"  171.75  1600 1712 1880 2160  1280 1283 1290 1327 -hsync +vsync
~$ 

To change this to any custom resolution, just replace Modeline in the output of cvt with xrandr --newmode. Thats it. Enjoy :)


Tuesday, April 23, 2013

SPOJ - ACODE - AlphaCode

Problem Description - http://www.spoj.com/problems/ACODE/

Approach :

1) Initialize an Array of Size N with 0 and element 0 as 1
2) Loop through all the elements
3) If it is a valid single digit number, Copy the previous element's value to the current element (DP[i] = DP[i-1])
4) If it is a valid two digit number, Add the previous to previous element's value to the current element (DP[i] += DP[i-2])

In one line : DP[i] = DP[i-1] {if valid single digit number} + DP[i-2] {if current and previous elements make a valid two digit number}

Solution:
# include <cstdio>
# include <cstring>
char Input[5001] = "";
unsigned long long DP[5001];
int main()
{
 freopen ("Input.txt", "r", stdin);
 freopen ("Scratch.txt", "w", stdout);
 scanf ("%s", Input);
 while (strcmp(Input, "0"))
 {
  int Len = strlen (Input), Index = 1;
  memset (DP, 0, sizeof DP);
  DP[0] = 1;
  while (Index < Len)
  {
   int temp = 0;
   temp = (Input[Index-1]-'0') * 10;
   temp += (Input[Index] -'0');
   if (Input[Index]-'0') DP[Index] = DP[Index-1];
   if (temp <= 26 && temp > 9) DP[Index] += DP[Index-2 < 0?0:Index-2];
   //printf ("%d\t%llu\n",Index, DP[Index]);
   Index++;
  }
  //printf ("%llu\t%s\n", DP[Len-1], Input);
  printf ("%llu\n", DP[Len-1]);
  scanf ("%s", Input);
 }
}

Sunday, April 21, 2013

Timus - 1018 - Binary Apple Tree - Dynamic Programming

Today, I saw this interesting problem.

Timus - 1018 - Binary Apple Tree

When I started working on this, I didnt know why do we need Dynamic Programming to solve this. My idea was pretty simple.
1. While reading Inputs find the total number of apples
2. Find all the leaf Branches (I mean branches without any branches on them)
3. Get the branch with the least number of apples and remove that
4. Goto Step 2 until N - Q - 1 times. (N is the total number of enumerated points on the tree, Q is the number of branches to keep, Always there will be N - 1 branches on the binary tree. So N - Q - 1 will give the number of branches to be removed)
It was pretty straight forward to implement.
# include <cstdio>
# include <map>
# include <set>
# include <bitset>
using namespace std;
int N, Q;
unsigned long long Total = 0;
struct Branch
{
 bool operator< (const Branch & branch) const
 {
  if (this->Apples == branch.Apples)
  {
   if (this->Start == branch.Start)
    return this->End < branch.End;
   return this->Start< branch.Start;
  }
  return this->Apples < branch.Apples;
 }
 Branch (int a, int b, int c){Start = a; End = b; Apples = c;}
 int Start, End, Apples;
};
set <Branch> Edges;
bitset <101> Visited;
map <int, map <int, int> > Tree;
void FindEdges (int current, int parent)
{
 //printf ("%d\t%d\n", current, parent);
 if (Visited[current]) return;
 //printf ("%d\t%d Not Visited\n", current, parent);
 Visited[current] = true;
 map<int, int>::iterator it = Tree[current].begin();
 if (Tree[current].size() == 1)
  Edges.insert (Branch (parent, current, Tree[parent][current]));
 else
  for (; it != Tree[current].end(); it++)
   if (!Visited[it->first])
    FindEdges (it->first, current);
}
int main()
{
 //freopen ("Input.txt", "r", stdin);
 //freopen ("Scratch.txt", "w", stdout);
 scanf ("%d%d", &N, &Q);
 Q = N - 1 - Q;
 int A, B, C;
 for (int i = 0; i < N - 1; i++)
 {
  scanf ("%d%d%d", &A, &B, &C);
  Tree[A][B] = C;
  Tree[B][A] = C;
  Total += C;
 }
 for (int i = 0; i < Q; i++)
 {
  Edges.clear();
  Visited.reset();
  map<int, int>::iterator it1 = Tree[1].begin();
  Visited[1] = true;
  for (; it1 != Tree[1].end(); it1++)
   FindEdges(it1->first, 1);
  //printf ("Edges Size : %lu\n", Edges.size());
  set<Branch>::iterator it = Edges.begin();
  //printf ("%d\t%d\t%d\n", it->Start, it->End, it->Apples);
  Total -= it->Apples;
  Tree[it->Start].erase (it->End);
  Tree[it->End].erase (it->Start);
 }
 printf ("%llu\n", Total);
}
However, this solution was failing so many times. Then I found the testcase for which this program was failing.
4 1
1 2 1
1 3 2
2 4 3

The above shown solution returns 1 as the result whereas the optimal result is 2. This approach is greedy approach I believe.
In the first iteration, it detects the branches
1 3 2
2 4 3
and removes the branch 1 3 2, since it has the least number of apples and in the next iteration it detects the following branch
2 4 3
since that is the only leaf branch available and it removes that, leaving us with the suboptimal solution 1.

Here is the DP solution which can really solve this problem and this got accepted by Timus.

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int N,Q, Tree[101][101], DP[101][101];
int solve (int current, int parent, int q)
{
 if (q <= 0) return 0;
 int lindex = -1, rindex = -1;
 int & result = DP[current][q];
 if (result != -1) return result;
 for (int i = 0; i < 101; i++)
  if (Tree[current][i] != -1 && i != parent) {lindex = i; break;}
 for (int i = (lindex == -1?0:lindex+1); i < 101; i++)
  if (Tree[current][i] != -1 && i != parent) {rindex = i; break;}
 //printf ("%d\t%d\t%d\t%d\t%d\n", current, parent, lindex, rindex, q);
 if (lindex == -1 || rindex == -1) return 0;
 for (int i = 0; i <= q; i++)
  result = max (result, (i == q?0:Tree[current][lindex] + solve(lindex, current, q - i - 1))
   + (i == 0?0:Tree[current][rindex] + solve(rindex, current, i - 1)));
 //printf ("Returning %d\n", result);
 return result;
}
int main()
{
 //freopen ("Input.txt", "r", stdin);
 //freopen ("Scratch.txt", "w", stdout);
 scanf("%d%d",&N,&Q);
 memset (Tree, -1, sizeof Tree);
 memset (DP, -1, sizeof DP);
 for (int i = 0; i < N; i++)
  for (int j = 0, x, y, z; j < N; j++)
  {
   scanf ("%d%d%d", &x, &y, &z);
   Tree [x][y] = z;
   Tree [y][x] = z;
  }
 printf ("%d\n", solve (1, 0, Q));
 return 0;
}
Please write to me if you want me to explain this program. We can do that over chat.

UVa 11259 - Coin Changing Again

This took lot of my time and I managed to come up with this Top-down Dynamic Programming solution. This approach times out. Any suggestions? Problem Statement : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2226
# include <cstdio>
# include <map>
# include <set>
using namespace std;
struct State
{
 State (int v1, int v2, int v3, int v4)
 {
  V1 = v1; V2 = v2; V3 = v3; V4 = v4;
 }
 int getPart2(int Value = 0)
 {
  int Part2 = 0;
  Part2 = (V4 >> 13);
  Part2 |= (Value << 4);
  return Part2;
 }
 unsigned long long getPart1()
 {
  unsigned long long Part1 = 0;
  Part1 = V1;
  Part1 |= (V2 << 17);
  Part1 |= ((unsigned long long)V3 << 34);
  Part1 |= ((unsigned long long)V4 << 51);
  return Part1;
 }
 int V1, V2, V3, V4;
};
map <int, set<unsigned long long> > States;
map <int, set<unsigned long long> > Solutions;
int c1, c2, c3, c4, q, d1, d2, d3, d4, v;
unsigned long long Result ;
bool CheckVisited (unsigned long long Part1, int Part2)
{
 if (States[Part2].count (Part1)) return true;
 States[Part2].insert (Part1);
 return false;
}
void Solution (State & s, int Value)
{
 unsigned long long Part1 = s.getPart1();
 int Part2 = s.getPart2(Value);
 if (!Value)
 {
  Solutions[Part2].insert (Part1);
  return;
 }
 if (CheckVisited(Part1, Part2)) return;
 if (s.V1 - 1 >= 0 && Value - c1 >= 0)
 {
  s.V1--;
  Solution (s, Value - c1);
  s.V1++;
 }
 if (s.V2 - 1 >= 0 && Value - c2 >= 0)
 {
  s.V2--;
  Solution (s, Value - c2);
  s.V2++;
 }
 if (s.V3 - 1 >= 0 && Value - c3 >= 0)
 {
  s.V3--;
  Solution (s, Value - c3);
  s.V3++;
 }
 if (s.V4 - 1 >= 0 && Value - c4 >= 0)
 {
  s.V4--;
  Solution (s, Value - c4);
  s.V4++;
 }
}
int main()
{
 freopen ("Input.txt", "r", stdin);
 freopen ("Scratch.txt", "w", stdout);
 int N;
 scanf ("%d", &N);
 State s (0, 0, 0, 0);
 while (N--)
 {
  scanf ("%d%d%d%d%d", &c1, &c2, &c3, &c4, &q);
  while (q--)
  {
   scanf ("%d%d%d%d%d", &s.V1, &s.V2, &s.V3, &s.V4, &v);
   Result = 0;
   States.clear();
   Solutions.clear();
   Solution (s, v);
   for (map<int, set<unsigned long long> >::iterator it = Solutions.begin(); it != Solutions.end(); it++)
    Result += it->second.size();
   printf ("%lld\n", Result);
  }
 }
}

Saturday, April 20, 2013

Number of ways to change making (Dynamic Programming)

This is a variant of change making problem. Here, we are just asked to count the number of ways to make the specific change. With a little change to the change making problem's solution, we can solve this one. The problems which can be solved with the following solution are
UVa - 657 - Coin Change

UVa - 357 - Let Me Count The Ways (Need to change the way solution is printed as per problem description)

# include <iostream>
# include <cstdio>
using namespace std;
unsigned long long NumberOfWays [30001], Coins []= {1, 5, 10, 25, 50}, Num;
int main ()
{
 //freopen ("Input.txt", "r", stdin);
 //freopen ("Scratch.txt", "w", stdout);
 NumberOfWays[0] = 1;
 for (int i = 0; i < 5; i++)
  for (int j = Coins[i]; j < 30001; j++)
   NumberOfWays [j] += NumberOfWays [j - Coins[i]];
 while (scanf ("%lld", &Num) != EOF)
  printf ("%lld\n", NumberOfWays[Num]); //Change this for UVa - 357 - Let Me Count The Ways
}

Change Making (Dynamic Programming) Problem

This is a classic change making problem.
A variant of the same problem, counting the number of ways to make the change is here
Problem Name : Making Change
Problem ID   : 2768
Problem URL  : http://acm.tju.edu.cn/toj/showp2768.html
Solution     :
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
int denoms [10];
int change [1001];
using namespace std;
int main()
{
 //freopen ("Input.txt", "r", stdin);
 //freopen ("Scratch.txt", "w", stdout);
 int C, N;
 scanf ("%d%d", &C, &N);
 fill (change, change + C + 1, 10000);
 for (int i = 0; i < N; i++) scanf ("%d", &denoms[i]);
 sort (denoms, denoms + N);
 change[0] = 0;
 for (int j = 0; j < N; j++)
  for (int i = denoms[j]; i <= C; i++)
   change[i] = min (change[i], change[i - denoms[j]] + 1);
 printf ("%d\n", change[C]);
}

Installing python-ldap in Ubuntu

These are the steps to be followed to install python-ldap in Ubuntu. At first,
sudo apt-get install python-ldap
would throw the following error
In file included from Modules/LDAPObject.c:4:0:
Modules/common.h:10:20: fatal error: Python.h: No such file or directory compilation terminated.
error: command 'gcc' failed with exit status 1
To get past this error, we need to install python-dev package
sudo apt-get install python-dev
After installing that we ll get the following error
In file included from Modules/LDAPObject.c:9:0:
Modules/errors.h:8:18: fatal error: lber.h: No such file or directory
compilation terminated.
To get past this error, we need to install ldap2-dev package
sudo apt-get install libldap2-dev
After installing that we ll get the following error
Modules/LDAPObject.c:18:18: fatal error: sasl.h: No such file or directory compilation terminated.
error: command 'gcc' failed with exit status 1
To get past this error, we need to install libsasl2-dev package
sudo apt-get install libsasl2-dev
After that
sudo apt-get install python-ldap
should install python-ldap without any problems.

Thursday, April 4, 2013

select2 JQuery dynamic JSON data with tags


          jQuery.noConflict();
          function formatListOptionSelection (Option, Container)
          {
             return Option;
          }
          function formatListOption (Option, Container, Query)
          {
             return "<div id='" + Option + "'>" + Option + "</div>";
          }
          jQuery(document).ready(function() {
             jQuery("#Data").select2 ({
                multiple: true,
                minimumInputLength: 5,
                maximumSelectionSize: 3,
                id: function (e) {return e;},
                ajax: {
                   url: 'fetch.json',
                   // json will be used if there is no Same Origin Policy violation, otherwise JSONP shall be used
                   dataType: 'json',
                   data: function (term, page) {
                      return {
                         searchkey: term,
                         field: 'Data'
                      };
                   },

                   // This method will be used when the data is returned from the server
                   results: function (data, page) {
                      return {results: data.Datas};
                   },
                },

                // This method will be used when you fetch result from server and add it to the element
                formatResult: formatListOption,

                // This method will be used when you select one of the options
                formatSelection: formatListOptionSelection,

                // This method will be used when you set the value attribute of the element
                initSelection: function(element, callback) {
                   var Datas = jQuery(element).val();
                   Data = []
                   jQuery(Datas.split(",")).each(function () {
                      if (this != "") Data.push (this);
                   });
                   callback (Data);
                },
             });
          });


         <input class="span12" id="Data" name="Data" type="hidden" value="<Value from POST back>" />