An experiment with carbs

About a month ago, Appu, Abbas and myself met and Appu happened to mention that an increased intake of carbs. generally lent itself to hunger pangs if one did not eat for a while.
For the last month, I've been having only salad for lunch, and daal, vegetables and chapati(3 nos.) for dinner and have also been limiting my carb. intake by way of reducing the amount of sugar I add to my hot beverages.
However, yesterday I had 4 liquor chocolates (which Devdas had so generously brought back from New Zealand), 5 milk pedhas (courtesy Jaineev) and 2 Kaju Katris (courtesy Mukesh), which considerably increased my carb intake for that day. Furthermore, I had 5 chapatis and extra helpings of other stuff yesterday for dinner. I don't know if it had any direct link to the carb. intake, but I will be monitoring this more closely now.

Moments

I visited Sandeep in Bangalore when I had gone for the Agile 2010 conference in Jan 2010. Good times followed ;)

• Neela Aasmaan Soo Gaya


• Tere Khushboo Mein Basee Khat


• Jhuki Jhuki See Nazaar


• Mainee Tere Liye Hii Saat Rang Kee (Part-1)


• Mainee Tere Liye Hii Saat Rang Kee (Part-2)

Vanilla Milk using natural vanilla extract

I started making vanilla extract in July 2009 using adaptations of the innumerable recipes available online. It's now been 7 months since I started so I decided to try out the extract for making vanilla milk (which btw I absolutely love and up to this point made using pulverized vanilla beans).

• Attempt-1: Measure about 1 cup (approx. 200 ml) of milk in a glass, pour it in a vessel and heat. Add 1/2 tsp vanilla extract to the glass (which has traces of cool milk). The last bit caused the trace amounts of milk in the glass to curdle. However, pouring the heated milk and sugar in the glass did not curdle the rest of it. The whole drink smelt of alcohol though.


• Attempt-2: This time, I decided to not leave trace amounts of milk before adding the extract to the glass. Again however, I did get some smell of alcohol.


• Attempt-3: This time, I decided to do some research online and figure out if anyone else is facing the problem of an alcoholic smell in their extract. As it turns out, it is expected to be this way for a real extract!! (feature, not a bug ;) ). I also happened to read that adding sugar reduces the alcoholic smell, and that when this extract is used in cooking, most of the alcohol will in fact evaporate and hence not leave behind that alcoholic smell. So, this time, I added some sugar to the glass before adding the vanilla extract, and after pouring in the hot milk, I stirred for about 4-5 minutes before consuming the drink. Viola!! No smell now!!

Another nice link explaining a lot of things.

Eggless Brownies Recipe

Ingredients:

Flour (sifted):	195g
Dark Chocolate:	160g
Fat (Butter + Oil)	120g (80g + 40g)
Water:	255ml
Cocoa powder:	2-3tsp
Sugar (castor or powder sugar):	2 cups
Salt (if not using salter butter):	1/2 tsp
Vanilla extract/essence:	1 1/2 - 1 4/5 tsp
Baking powder:	1 1/5 tsp(for guey brownies) - 1 1/2 tsp(for cakey/fluffy brownies)
Chopped walnuts:	40g

Procedure:

1. Grease and dust an 8" X 9" pan (basically 72 square inches in area), and pre-heat the oven to 180 degree celcius.



2. Heat the water on a low flame till it is warm/mildly hot and add to it ¹/₃^rd of the flour (65g). Do not remove the utensil from the flame, and continue stirring till the mixture thickens.



3. Add the oil to the chocolate and melt the chocolate either in a microwave oven or on a double boiler.



4. For making cakey(not guey) brownies, mix the sugar with the butter and whisk/beat till the mixture is light and fluffy. For making guey brownies, just mix the sugar with the flour and water mixture you just made.



5. Mix the baking powder, cocoa powder and salt (if using unsalted butter) with the rest of the flour and sift it again a couple of times to mix them uniformly well.



6. Add the vanilla extract with the flour and water mixture and mix it well.



7. Now, mix all the portions that you have with each other and add the walnuts to this mixture. Make sure you mix it well. Perform this step quickly and briskly so that the baking powder doesn't wear out by the time you start baking it.



8. Transfer the contents to the greaded and dusted pan, and bake in the oven for 45-55 minutes (or till you think it is done).



9. Remove frm over and wait for it to cool a bit (about 30-45 minutes), cut into pieces and enjoy!!

One week of salad

I started having salad last week for lunch every day, and it's going pretty well as of now. Bought supplies for the next week today.

Ingredients:

• Iceberg lettuce


• Lettuce


• Purple/Green cabbage


• Brocolli


• Red/Green/Yellow Capsicum


• Tomatoes


• Cherry Tomatoes


• Baby corn


• Fresh Green Peas


• Finely chopped carrots


• Green/Black Olives


• Soaked and sprouted moong and moth


• Extra Virgin olive Oil (for the dressing)


• Honey (for the dressing)


• Salt (for the dressing, added just before eating)


• Mixed Herbs (for the dressing)

Procedure:

1. Cut and mix whatever you want to have in the salad. I generally choose about 6-8 items every day, and mix and match in any order I feel fit.


2. Introduce the dressing (generally just olive oil and honey) except for the salt since the salt will make the vegetables dehydrate and lose their water. I take this tossed salad to office, so it is about 3hrs time from the time I mix it to the time that I consume it.

It's funny to know....

.... that something you have thought of doing and have done has been thought of by someone else across the world and done in almost exactly the same way as you have....

It's saddening and encouraging at the same time. Saddening because it's not something novel any more. Someone has "been there.. and done that..". Encouraging because you know that you are not having any insanely weird and impractical thoughts and ideas and that you are solving some real problem out there.

This is the second time that this has happened to me, and it is a real confidence booster I should say!!

The project under question is StickyLinks. The exact same thing was done in 1997 and is called WebCite. The funny thing is that it was made for the exact same problem that I was trying to solve, which probably explains why it turned out to be so similar.

The thing that still gets to me is that even the layout of the version page (view where a version of a certain page is displayed) is almost identical. Both projects use frames. Both projects have a bookmarklet.

However, there are ways I plan to extend StickyLinks, so stay posted!!

ps. My next idea: To develop a search engine that will let you search for already existing ideas/concepts/implementations of thoughts that you may have and may think are novel. I use the internet (esp. the search engines) a lot to search for projects that I may want to undertake, just to check if it's already been done by someone else. Most of the time I have to search a lot of times, tweaking my search keywords ever so slightly in the hope of a match. Many a times, I fail to chance upon the right set of keywords (the words that the original author used to describe his/her idea/project) and am under the impression that the idea I have is novel/un-thought of. However, many times it does happen that such a thing does not exist. However, it is only time that lets you ascertain this (if a similar concept exists, you hear of it sooner rather than later, assuming you have shared it with friends).

Chocolate Rum Balls

This is been pending for a while now.
Barbara asked me how to make these last year!!!! (realistically, about a month ago) and I haven't yet gotten back to her. That is pretty bad of me.
Here goes nothing....

Ingredients:

Chocolate sponge cake:	about 250g
Dark chocolate:	about 250g (preferably &ge 40% cocoa)
Fresh Cream:	about 100g
Walnuts:	about 100g (or to your taste)
Rum:	to taste

Procedure:

1. Crumble the cake well into.... well crumbles.... Use very soft hands to do this.


2. Mix the rum with the crumbled cake, but don't form a paste.


3. Melt the chocolate (always over steam).


4. Heat the cream in a saucepan till it is simmering and mix it well with the melted chocolate.


5. Make small pieces of the walnuts and add them to the chocolate and cream mixure and mix well again.


6. Empty the cake crumbs into the mixture above and mix till it forms a solid paste which can be rolled into balls. Note: You may need more/less of the cake crumbs depending on how watery/viscous the chocolate and cream mixture is.


7. Roll them into balls!!!! You can put a thin layer of melted butter or ghee (clarified butter) on your palms so that the stuff doesn't stick to your palms while mixing.

Merry Christmas, and have a Great New Year!! :) :)

Gaajar Halwa

I met Appu and Abbas today, and we had this nice talk about carbs. and how the lesser there are around and within us, the better it is for our kind of lifestyle. I have steadily reduced the amount of sugar I have with my cup of tea or ukada (or ukado since it is a gujarati recipe) and am okay with it.
The recipe below is in complete defiance of the statements above. However in my defense, I used much less sugar than I usually would have.

Ingredients:

Grated fresh red carrots(gaajar):	about 1kg
Cow's Milk (preferably full fat containing ≥ 9% SNF):	about 2ltr
Sugar:	to your taste, but you could start off with 200g
Cow's Ghee (clarified butter):	2-3 Tbsp
Elaichi:	seeds of 4-5 pods, well separated
Elaichi powder:	1 tsp (or to taste)

Procedure:

1. Take the Ghee in a saucepan and add the elaichi seeds, and heat the ghee till it is hot, and just till you hear a pop sound.
   



2. 
   Add the grated carrots and coat every bit of them with the Ghee (on a slow flame).
   
   



3. 
   Heat the milk in a saucepan till it is hot.
   
   



4. 
   Pour some (about 500ml) of the hot milk into the carrot and ghee mixture, turn up the flame to medium and stir continuously.
   
   



5. The milk will come to a boil.
   
   



6. We want to make mawa (or khoa) from the 1.5ltr of remaining milk. You can find out how this is done. Basically it involves simmering the milk till the water almost vaporizes. The semi-solid mass that is left will be used later in the making of our halwa.



7. Once the mawa is made, mix it with the rest of the carrot mixture (which should have considerably thickened by now. I hope you were continuously stirring it all this while!!).



8. Also add the sugar. The sugar will immediately melt and give off a lot of water. We need to burn off all this water.
   
   



9. Stir continuously till the water evaporates and we are left with a semi-solid mass (more liquidy though).
   
   



10. Evenly sprinkle the elaichi powder over this mass and stir continuously.
    
    



11. Till the mixture thickens to a consistency of your choice.
    
    



12. Let it cool, and enjoy!!!! :)

btw, this is the 100^th post on this blog!!

An O(1) approach to the LFU page replacement algorithm

LFU: Least Frequently Used

The LFU algorithm evicts pages that have been least frequently used. If the cache is full, and one more page needs to be added, the page that has been used the least number of times is evicted from the cache.

How can we efficiently implement this algorithm? Each operation of the LRU algorithm can be implemented in worst case O(1) complexity. We can do the same for LFU as well.

For this, we maintain a doubly linked list where each node of the linked list looks like this:

struct CountNode
{
 CountNode *prev, *next;
 PageNode *root;
 int count;
};

Each node of this linked list points to the root of another doubly linked list which holds the actual pages. All the pages in this 2^nd linked list have the same usage count. The node for this linked list looks like this:

struct PageNode
{
 PageNode *prev, *next;
 CountNode *parent;
 char pageData[4096];
};

The PageNode's parent member points to that CountNode of which it is a child. So there is a direct pointer from every PageNode to the corresponding CountNode it falls under. These extra links are not shown in the diagram to keep it simple.

The CountNode linked list's count member holds the usage count of each element under that node. So each PageNode under a CountNode having a count value of 6 will have been accessed 6 times.

How to implement the various operations?

1. Insetion: To insert, we always add the new PageNode to the CountNode list with the count value of 1. This will always be the first node in the linked list pointed to by head. If the first CountNode pointed to by head is greater than 1, we just add a new CountNode with a count value of 1 and then perform the insertion. All this can be done in time O(1).


2. Deletion: We will delete nodes, only if the cache is full, and this deletion will always happen from the CountNode list which has the least count. So, we just follow head, and delete a PageNode in such a CountNode. Additionally, if that CountNode happens to become empty because of this deletion, we also delete that CountNode. This too takes time O(1).


3. Access: Access involves incrementing the count of a PageNode, i.e. moving the accessed PageNode from it's CountNode list to a CountNode list with a count value that is 1 greater than it's current count value. We maintain pointers to the CountNode in the PageNode. This makes deleting the PageNode(and possibly the CountNode to which it belonged) a constant time operation. After that is done, we can insert a new CountNode that has a count value of 1 more than the CountNode from which the accessed PageNode was removed. If such a CountNode does not exist, we can always create it first. All this can also be done in constant time, making the whole process O(1).

   A lot of people have asked me how they can get to a PageNode in the first place. The answer to that question is that we maintain a hash table which hashes an object(page address, integer, etc...) such that accessing it (getting to the PageNode that that object corresponds to) can be accomplished in O(1) time.

This implementation takes advantage of the fact that:

1. When we add a new object to the cache, it is always going to start off with a use count of 1, and


2. Whenever we access an object, it's use count will go up by exactly 1.

I haven't found any resource that says that LFU can be implemented in time O(1). If you (reader) find any, please do let me know.

The Missionaries and Cannibals Problem

Some reading before you start: http://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem

Problem Statement:
[From the link above] "In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries.) The boat cannot cross the river by itself with no people on board."

Solution:
We will solve the generalized version of this problem, wherein there are C cannibals and M missionaries, and at most P people are allowed on the boat simultaneously.

This problem can be solved by noticing that at every stage, we can encode the state of the problem by using 3 variables, (nc, nm, shore). nc is the number of cannibals, nm is the number of missionaries and shore is either 0 or 1, which signifies whether nc and nm represent the count on the source or the destination shore respectively.

Thus, there are at most 2 x n² states that the problem can be at any point in time.

We can use BFS (breadth first search) to perform an exhaustive search on the search space to find a solution if one exists. The run-time complexity of doing so is O(CM P²). Below is the Python2.5 code that solves this problem using the BFS search method.

import sys
import string
from collections import deque


states = [[], []]
dq = deque()
nc = 0
nm = 0
c = 0
combinations = [ ]


def gen_combinations():
    global c, combinations

    for i in xrange(0,c+1):
        for j in xrange(0,c+1):
            if i+j>0 and i+j<=c:
                combinations.append((i,j))


def init_states():
    global nc, nm, states
    for i in xrange(0, nc+1):
        states[0].append([])
        states[1].append([])
        for j in xrange(0, nm+1):
            states[0][i].append(-1)
            states[1][i].append(-1)


def is_valid_state(nc, nm):
    return (nm>=nc) or (nm==0) or (nc==0)


def bfs():
    global dq, states, nc, mn, c, combinations

    while (len(dq) > 0) and states[1][nc][nm] == -1:
        (x,y,depth,boat) = dq.popleft()

        present = boat
        next = 1-boat

        if states[present][x][y] != -1:
            continue

        states[present][x][y] = depth

        for comb in combinations:
            (dx,dy) = comb

            if x>=dx and y>=dy:
                new_st = (nc-(x-dx),nm-(y-dy),depth+1,next)
                (lx,ly) = (nc-(x-dx),nm-(y-dy))
                (rx,ry) = (nc-lx,nm-ly)

                if is_valid_state(lx, ly) and is_valid_state(rx, ry) \
                       and states[next][lx][ly] == -1:
                    dq.append(new_st)



def main():
    global dq, nc, nm, c, combinations, states
    input = string.split(raw_input())
    nc = int(input[0])
    nm = int(input[1])
    c  = int(input[2])

    init_states()
    gen_combinations()

    dq.append((nc, nm, 0, 0))
    bfs()

    print states[1][nc][nm]

    return 0


if __name__ == "__main__":
    sys.exit(main())