XmlRpcMessageService - A Google Apps Script Library

This post is part of a series: Trakt.TV & Subtitles - A Google Apps Script Project

Overview

As part of my project I worked on fetching subtitles availability from several providers. One of the providers is OpenSubtitles.org. This site has an API which is implemented based on XML-RPC. From Wikipedia on XML-RPC: "XML-RPC is a remote procedure call (RPC) protocol which uses XML to encode its calls and HTTP as a transport mechanism". This protocol is quite verbose and is not that JavaScript friendly. Because of these reasons I decided to implement a library to ease the use of XML-RPC in JavaScript. This library enables the user to describe the request and get the response in plain JSON. The bottom line is that using this library, executing a method call in JavaScript, for example the "LogIn" method to OpenSubtitles.org, can be as easy as:

var methodCall = {
   methodName : "LogIn",
   params : [ "", "", "en", "OS Test User Agent" ]
}
var url = "http://api.opensubtitles.org/xml-rpc";
var methodResponse;
var onSuccess = function(mr) { methodResponse = mr; };
XmlRpcMessageService.execMethodCall(url, methodCall, onSuccess);

The First Translation - Verbose JSON

First I defined a quite verbose JSON model which translates to and from an XML-RPC in a straight forward conversion. Examples are better than words-

A simple value is described in XML-RPC:

<value><string>David</string></value>

In JSON:

{ type : "string", value : "David" }

An array in XML-RPC:

<value><array>
   <data>
      <value><string>David</string></value>
      <value><string>John</string></value>
   </data>
</array></value>

In JSON:

{ type : "array", value : [
      { type : "string", value : "David" },
      { type : "string", value : "John" }
   ] }

A struct value in XML-RPC:

<value><struct>
   <member>
      <name>qwerty</name>
      <value><double>1234</double></value>
   </member>
   ...
</struct></value>

In JSON:

{ type : "struct", value : [
      name : "qwerty",
      value : { type : "double", value : "1234" }
   ] 
}

So basically, you can see that a similar schema is kept for the different value types.

A method call in XML-RCP contains the name of the method and the values for the parameter:

<methodCall>
   <methodName>foo</methodName>
   <params>
      <param>...value...</param>
      ...
   </params>
</methodCall>

In JSON:

{
   methodName : "foo",
   params : [
      { type : "...", value : "..." },
      ...
   ]
}

The result of this transformation is still verbose, more or less the same as the XML representation. The main advantage of the JSON representation is that it is much easier to use in JavaScript since there is no need for string manipulation, XML encoding, etc.

The Second Transformation - "Semantic" JSON

(Maybe the name "semantic" is not that good, but I'll stick with it for now)

After implementing the first translation, which can be used in all scenarios, I decided to go a little bit further. I thought - instead of persisting the name of the value type, persist the value in its designated type. So for the next transformation I decided on the following mapping:

JSON - Verbose	JSON - Semantic
double value object { type: "double", value: 7 }	number 7
string value object { type: "string", value: "Hello" }	string "Hello"
boolean value object { type: "boolean", value: true }	boolean true
array value object { type: "array", value: [ ... ] }	array [ ... ]
struct value object { type: "struct", value: [ { name: "bar", value: ... } ] }	object { bar: ... }

The method call itself stays the same, the values become more simple:

{
   methodName : "foo",
   params : [ "Hello", 7, true, { bar : 100 } ]
}

Of course this transformation can be applied on the response as well, which is simple as:

{ params : [ ... ] }

Conclusion

The idea was to make the use of XML-RPC web services easier in JavaScript in general, and in Google Apps Script specifically. This implementation has two-step transformation. The first step is as verbose as the original XML-RPC, but can be used easily in JavaScript. The second step makes it much less verbose but does not support, for now, some of the value types defined in XML-RPC specification (e.g. integer, base64, etc).

The code is available in GitHub:
https://github.com/yinonavraham/GoogleAppsScripts/tree/master/XmlRpcMessageService

Full Example for Comparison

XML-RPC

<methodCall>
   <methodName>foo</methodName>
   <params>
      <param>
         <value><string>Hello</string></value>
      </param>
      <param>
         <value><double>7</double></value>
      </param>
      <param>
         <value><boolean>1</boolean></value>
      </param>
      <param>
         <value><array>
            <data>
               <value><string>a</string></value>
               <value><string>b</string></value>
            </data>
         </array></value>
      </param>
      <param>
         <value><struct>
            <member>
               <name>bar</name>
               <value><double>100</double></value>
            </member>
         </struct></value>
      </param>
   </params>
</methodCall>

JSON - Verbose

{ 
   methodName : "foo", 
   params : [ 
      { type: "string", value : "Hello" }, 
      { type: "double", value : 7 },
      { type: "boolean", value: true },
      { type: "array", value: [ 
            { type: "string", value: "a" }, 
            { type: "string", value: "b" } 
         ] },
      { type: "struct", value: [ 
            { name: "bar", value: { type: "double", value: 100 } } 
         ] } 
   ]  
}

JSON - Semantic

{ 
   methodName : "foo", 
   params : [ "Hello", 7, true, [ "a", "b" ], { bar : 100 } ] 
}

Griddlers Solver

You know these griddlers puzzles? Every day there is a new 2D 20x20 puzzle in the newspaper we were getting at work. So I decided to implement a solver for those problems.
Before I start talking, you can take a look at the Griddler Solver page. I have prepared some examples.

I chose client-side JavaScript as the runtime environment. Why? just because it's easy to use for coding the solver and it also integrates smoothly with a well known UI - HTML... Oh, and because I wanted to practice my JavaScript skills...
My first attempt with implementing the solver was using kind of DFS (Depth-First-Search). The algorithm was (roughly):

1. Calculate possible solutions for each column
2. Iterate recursively over the columns:
1. Get the current column
2. Iterate recursively over the possible solutions of the column:
1. Get the current possible solution
2. If this is the last column:
1. If the problem is solved (the rows constraints are matched) - stop

This worked great for small problems (about 5x5), but for bigger problems the performance was horrible.
The next step I tried was to add some heuristics. For example, I added some heuristics for pruning branches which are not feasible. Some of the rules I used:

• If the sum of colored cells in a row of the solution is higher than the some of colored cells in the constraint - this branch is not feasible
• If the length of the current block is higher than its expected length - this branch is not feasible

With those rules the performance improved tremendously, but still not enough for the average problem (20x20). 

Then I decided to change direction and instead of implementing based on a generic algorithm (i.e. DFS), I decided to implement an algorithm which is based on the way a human will solve it. So, how do you solve these puzzles? I usually use an iterative solution:

1. Find the large blocks and find overlaps - color them.
2. Check for other constraints which are now easier to match, according to the new colored cells.
3. If there is no single solution - find the minimal possible solutions, select one and try to move forward. If this fails, go back and select a different possible solution. (This step usually does not happen - you usually just need to look harder in steps #1 & #2).

What I have decided to implement was some variation of it. I decided to calculate all the possible solutions for all rows and columns and then do cross-checks for each cell and calculate its probability to be colored. In each step some possible solutions can be discarded since they do not match the decisions that were made during that step.

So the algorithm is basically:

1. Initialize:
1. Calculate all possible solutions for each row & column
2. Initialize the grid so that each cell has an undefined value
2. Solve - while the solution changes:
1. Update probabilities:
   For each cell, calculate the probability for it to be colored by cross checking the possible solutions for both row and column - count the number of solutions where the cell is colored and not colored.
2. Remove false solutions:
   For each cell, if the cell's value is known (i.e. 100% colored or empty) - remove all possible solution (columns and rows) where the cell's value is different from its expected value.

You can see above that I don't yet handle the case when there are multiple possible solutions which none of them can be removed - i.e. need to choose one of them and try to move forward. This is because I did not have such a case yet in any of the puzzles I tried. It's not that difficult to create such example, nor implement it, I just didn't... (for example: 2x2 puzzle with rows - [ [1], [1] ] , and columns - [ [1], [1] ]. Try it...).

In my implementation I implemented the solver as an Iterator which enabled me to add animation to the UI. Since in each step the grid has probabilities for each cell (for whether it is colored), it can make quite nice animations.

You can find the code in my GitHub project yinonavraham/GriddlerSolverJS.