Monday, April 19, 2010

Math for Software Engineers

I've recently gotten into TopCoder (don't ask me where I've been all this time). As a software engineer of about 7+ years, I was quite keen to find out where I stacked up in the programming stakes. I've programmed mostly in Java, so that was the language I chose to use in practice area of the Arena. I should also disclose that I got a tip to attempt some of the division 1 and 2 problems from a Google page about preparing for their interviews. This sparked my curiosity even further.

After starting the Arena (TopCode should have a UI contest to find a more user friendly place to show link to the jnlp. At the footer seems an odd place to have a link that is used frequently) I went into one of the practice rooms and picked a problem related to gambling. TopCoder does not allow unauthorized reproduction of their problems, so I won't violate their copyright. The problem can be found in practice room SRM 144 Div 1.

The crux of the problem is to find out how many combinations of a particular set of items that can be selected from another set of items. For example, if you have to pick 2 numbers from 1-10 inclusive, how many combinations can you include? What if the order is important (i.e. the second number you pick must be greater than the first)? What if the numbers must be unique (i.e. no repititions)? What if both the order and unique rules are necessary?

While I was intrigued with the logical challenge of solving this puzzle, I wondered whether this has a place as a problem for a software engineer. I suspect, depending on how the client has explained this problem (you would have to see the post for the problem from TopCoder) it either becomes a computer science or mathematical problem rather than one about building software. Many computer solutions are replacements for manual processes so sometimes it is necessary to ask the client, "What are you doing currently to solve this?" It could however be a new problem and it is unreasonable for the engineer to tell the client, "Sorry, I can't quite remember my high school math."

The solution to the problem required 4 routines:
  1. A method to calculate exponentials. In java - Math.pow is sufficient.
  2. A method to calculate permutations.
  3. A method to calculate factorials.
  4. A method to calculate binomial_coefficient.

Exponentials
Exponentials can be used to calculate the number of possibilities without any rules regarding order or uniqueness. For the example of 10,2 the number of possibilities is 100.


Permutations
From wikipedia, a permutation of a set of values is an arrangement of those values into a particular order. Going back to the original problem of picking 2 numbers between 1-10, regardless of order and ensuring the numbers are unique (i.e. 1,2 is valid but 2,2 is invalid), calculating the number of permutations of the 10 integers with 2 options for each.

  1. private long permutation(int n, int opts)
  2. {
  3. long result = 1;
  4. for (int idx = 0; idx < opts; idx++)
  5. result *= (n - idx);
  6. return result;
  7. }
Factorials
Factorials are a little more interesting than permutations. The factorial of a positive integer n (n!) is the product of all positive integers less than or equal to n. The factorial of zero is defined as 1. This is useful for calculating binomial coefficients.

Tuesday, January 5, 2010

Mobile Safari - Why am I developing for it?

This is my first post for the new year, 2010, so I thought perhaps to have a look at a new subject (to me). I've been fiddling with some iPhone development so far, brushing up on my Objective C and written a few posts on some of the lessons I've learnt. I also stumbled on an e-book I hadn't read in a while - Professional iPhone and iPod Touch Programming: Building applications for Mobile Safari, by WROX. This got me thinking, why would someone create a safari app, given the richness of the native applications?

The initial attraction I suppose is for those websites that already have an online community and would like to accommodate their mobile browsers. Then there are those whose applications would not be approved by Apple's App Store - on one end of the scale, those pioneers of online business - the purveyors of Adult entertainment a.k.a porn sites and on the other, competitors of Apple e.g Google. Amongst those looking to provide iPhone friendly versions of their websites, a huge chunk are media organisations. Wanting a slice of this market, I've decided to get onto learning how Mobile Safari works. I also expect the launch of the iSlate or whatever the call it, will herald a return to more content / feature driven demand for applications, and this is where some form of web applications will re-emerge. The main draw cards of Web 2.0 - community and content - ultimately belong server-side.

Initial impressions of Mobile Safari are not very promising. There is not much integration with many of the phone's key services but some are promising e.g. Geolocation. One sore point is the inability to directly upload photos. I expect this list to increase on both counts and look forward to interesting posts this year.

Thursday, November 19, 2009

The Regex & StringTokenizer Challenge!

Sometimes programming is difficult - You have to make large architectural decisions, with overreaching implications on maintainability, performance and security. Other times, programming is simply frustrating - Something 'simple' doesn't work the way you expected, you're seriously testing your logic and finally you bring out the paper and pen for some good-old pseudo code!

The problem...
I was doing some pro-bono processing work on an excel file, removing duplicate rows based on some complicated criteria. Preferring to keep my sanity I abandoned VBA so I exported the spreadsheet to CSV. The crunch is, some of the cells were blank and this produced unpredictable results in my code. Here's a sample of the data:


  1. ,,dsafdf,,15,,,,
  2. ,,fdsfjladsjf,,13,,,,
  3. df,,sdff,,bemail,1,1,,
  4. dsf,,sffdsf,,bsgemail,1,1,,
  5. token1,token2,token3,token4,token5,token6,token7,token8,token9


I've added the fifth row for demonstration of the number of tokens. In a row that is complete, we are expecting 9 tokens. Their position is important!

Source Code
I've included some source code showing 3 different approaches:

  1. import java.util.StringTokenizer;


  2. public class Processor {

  3. public static void main (String[] args) {

  4. final String _DELIM = ",";

  5. //An array of the strings
  6. String[] sourceStrings = {
  7. ",,dsafdf,,15,,,,",
  8. ",,fdsfjladsjf,,13,,,,",
  9. "df,,sdff,,bemail,1,1,,",
  10. "dsf,,sffdsf,,bsgemail,1,1,,",
  11. "token1,token2,token3,token4,token5,token6,token7,token8,token9"
  12. };

  13. System.out.println("Approach One: String.split()");
  14. for(String s: sourceStrings)
  15. {
  16. //do the processing on the strings using
  17. //the delimiter as a regular expression;
  18. String[] split = s.split(_DELIM);

  19. System.out.println("Number of tokens : " + split.length);
  20. }

  21. System.out.println("Approach Two: StringTokenizer");
  22. for(String s: sourceStrings)
  23. {
  24. StringTokenizer st = new StringTokenizer(s, _DELIM, false);

  25. System.out.println("Number of tokens : " + st.countTokens());
  26. }

  27. System.out.println("\r\nApproach Three: StringTokenizer returning delimiter - Take One");
  28. for(String s: sourceStrings)
  29. {

  30. StringTokenizer st = new StringTokenizer(s, _DELIM, true);

  31. System.out.println("Number of tokens : " + st.countTokens());
  32. }
  33. }
  34. }

Output
A listing of the output of the code above is shown below:

  1. Approach One: String.split()
  2. Number of tokens : 5
  3. Number of tokens : 5
  4. Number of tokens : 7
  5. Number of tokens : 7
  6. Number of tokens : 9

  7. Approach Two: StringTokenizer
  8. Number of tokens : 2
  9. Number of tokens : 2
  10. Number of tokens : 5
  11. Number of tokens : 5
  12. Number of tokens : 9

  13. Approach Three: StringTokenizer returning delimiter - Take One
  14. Number of tokens : 10
  15. Number of tokens : 10
  16. Number of tokens : 13
  17. Number of tokens : 13
  18. Number of tokens : 17


Approach One: String.split()
The first approach uses the String.split() method passing in the delimiter as a regular expression. As can be seen, this fails the test as we have ranges of 5-9 tokens. The correct answer should be 9.

Approach Two: StringTokenizer
The second approach uses the StringTokenizer to split up the strings. Again, we get unpredictable results. 2 tokens for the first two lines, as it picks only the items that are not the delimiter. The Correct answer here would be 9 and for the items that are null, we should get a null token.

Approach Three: StringTokenizer returning the delimiter
The third approach uses the StringTokenizer with a different constructor that also returns the delimiter. Again, lots of wrong results. The correct number of tokens should be 17 - 8 commas and 9 non comma items, preferrably null.

So there you have it, a rather simple task (I would have thought), but I did bang my head against the wall trying to find the right solution. If I ever get to be a teacher, this would be great for an exam! There's the challenge! I'll post the solution soon.


UPDATE!

  1. public class NonCollapsingStringTokenizer {  
  2.   
  3.     private String str;  
  4.     private String delim;  
  5.     private int currentPosition;  
  6.   
  7.     private NonCollapsingStringTokenizer() {  
  8.           
  9.     }  
  10.   
  11.     public NonCollapsingStringTokenizer(String str, String delimStr) {  
  12.         this.str = str;  
  13.         this.delim = delimStr;  
  14.     }  
  15.   
  16.     public String nextToken() {  
  17.         int nextDelimPosition = str.length();  
  18.         int delimPosition = str.indexOf(delim, currentPosition);  
  19.         if (delimPosition >= 0 && delimPosition < nextDelimPosition) {  
  20.             nextDelimPosition = delimPosition;  
  21.         }  
  22.         String token = str.substring(currentPosition, nextDelimPosition);  
  23.         currentPosition = nextDelimPosition + 1;  
  24.         return token;  
  25.     }  
  26.   
  27.     public boolean hasMoreTokens() {  
  28.         return (currentPosition < str.length());  
  29.     }  
  30.       
  31.     public int countTokens() {  
  32.         int count = 0;  
  33.           
  34.         NonCollapsingStringTokenizer clone = (NonCollapsingStringTokenizer) this.clone();  
  35.         while(clone.hasMoreTokens())  
  36.         {  
  37.             clone.nextToken();  
  38.             count++;  
  39.         }  
  40.           
  41.         return count;  
  42.     }  
  43.       
  44.     public Object clone() {  
  45.         NonCollapsingStringTokenizer copy = new NonCollapsingStringTokenizer();  
  46.         copy.str = str;  
  47.         copy.delim = delim;  
  48.         return currentPosition;  
  49.           
  50.     }  
  51. }  

The class above handles the challenge accordingly. This can be tested with the code below:

  1. public static void main(String[] args) {  
  2.         String s = ",,dsafdf,,15,,,,";  
  3.           
  4.         final String _DELIM = ",";  
  5.         //s = "token1,token2,token3,token4,token5,token6,token7,token8,token9";  
  6.         s = ",,sffdsf,,bsgemail,1,1,5,dsf";  
  7.                   
  8.         NonCollapsingStringTokenizer ncst = new NonCollapsingStringTokenizer(s, _DELIM);  
  9.         int x = 1;  
  10.         while(ncst.hasMoreTokens()) {  
  11.             String nextToken = ncst.nextToken();  
  12.               
  13.             System.out.println(Integer.toString(x++) + " " + nextToken);  
  14.         }  
  15.     }  

This produces the listing below:

  1. 1   
  2. 2   
  3. 3 sffdsf  
  4. 4   
  5. 5 bsgemail  
  6. 6 1  
  7. 7 1  
  8. 8 5  
  9. 9 dsf  

Tuesday, November 10, 2009

iPhone Programming Tools - What's in my toolbox?

Having developed in many programming languages, one finds one has picked up several tools along the way. Despite the relative immaturity of iPhone OS development, there's a lot of Objective-C and Cocoa developers out there and even the newly welcomed faithful have helped contribute a lot of different tools to the trade. Well I've decided to put down what's in my toolbox to help anybody who stumbles here looking for a tool to do something and also as a big thanks to the developers of these tools. (Always remember, a bad workman always blames his tools). This list is by no means definitive and I'll update it as I go along. Suggestions are welcome - to make this list more useful and also to make my life easier :)

X-Code & Interface Builder (IB)
The de-facto IDEs barely rate a mention because you can't do much useful development without them. Or so I thought until I found out that the 'first' iphone virus (ikee virus) was not developed using X-Code or IB. No! "It's good old C on a linux cross compile tool chain" as the developer reveals in an interview here. No expertise on the iPhone OS required either! On a serious note though, X-Code and IB are useful. I'd love to hear from non-X-Code developers.

Leaks Performance Measurement tool
This is part of the Development tools bundled with the iPhone SDK. It deserves a special mention as it is useful to profile you application during testing to ensure no memory leaks are present in your coding. Developers used to developing in programming languages where memory management and garbage collection is handled for you are prone to write code that contains many memory leaks. If only finding them was as easy as fixing them...

SQLite Admin is an GUI administration tool for SQLite - which is used as the portable database for iPhone applications. This tool is useful to view the schema of the SQLite database created by CoreData and pre-populate SQLite databases. It requires the Adobe Air runtime.

This is a utility to read the backups from an iPhone device. The backups are created using iTunes sync. This tool used in conjunction with the SQLite admin lets you get the SQLite backups from a device, not just the simulator - hence you can see not just your application's databases but those of other apps!

iPhone PNG normalization tools
When I need to access an image that has been used in a third-party or apple's applications, I usually rename the application's *.ipa file from the iTunes music folder to a zip file and unpack it. Then I show the contents of the "*.app" bundle. Inside this bundle are the resources used in the application. The png images are not in an easily readable format. I use the following two tools to normalize them:
  1. iPhonePNG. This is a pre-compiled objective-c project
  2. iPhone PNG Normalizer. This is a python script
Do not use this to infringe on the copyright of others.

3 Twenty is a static library that provides many useful UI components, such as image viewers and general utilities. It is based on the facebook iphone app which is one of the most downloaded facebook apps.

More tools to be added as discovered.

iPhone / Objective-C reading .csv files

I've been working on an iPhone application where I needed to save some data into the SQLite database via CoreData. The data I had was in a .csv file and I needed to preload this data on to the phone. I had two choices:
  1. Create an SQLite database by some programmatic means and import this as the store for CoreData.
  2. Read the .csv file and create NSManagedObject instances which can be saved to the context.
Option 1 seemed a little more daunting for me, so I chose the second option using NSUserDefaults to save a flag that I'd already read the .csv. I'm still investigating the first option and will report back if I'm successful. Anyway, here's a sample of the contents of the file:
  1. 31939,-37.838596,144.96726,1 - abcd
  2. 31752,-37.856249,144.979277,2 - efgh
  3. 31751,-37.854868,144.978053,3 - ijkl
  4. 31750,-37.856094,144.977565,4 mnop
  5. 31749,-37.855388,144.9753,4 qrst
So that's an excerpt of the .csv - four columns of integer, double, double and a string. Including your csv file in the resources folder of your XCode project. Ensure that the "Target" checkbox is checked (Its on the top of the right content pane when the .csv file has been selected). Next is the code to load this data:
  1. //
  2. // load the points from our local resource
  3. //
  4. NSString* filePath = [[NSBundle mainBundle] pathForResource:@"a_csv_file" ofType:@"csv"];
  5. NSString* fileContents = [NSString stringWithContentsOfFile:filePath];
  6. NSArray* pointStrings = [fileContents componentsSeparatedByCharactersInSet:[NSCharacterSet newlineCharacterSet]];
  7. //NSMutableArray* points = [[NSMutableArray alloc] initWithCapacity:pointStrings.count];
  8. for(int idx = 0; idx < pointStrings.count; idx++)
  9. {
  10. // break the string down even further to the columns
  11. NSString* currentPointString = [pointStrings objectAtIndex:idx];
  12. NSArray* arr = [currentPointString componentsSeparatedByCharactersInSet:[NSCharacterSet characterSetWithCharactersInString:@","]];
  13. NSNumber *colTwo = [[NSNumber alloc] initWithDouble: [[arr objectAtIndex:1] doubleValue]];
  14. NSNumber *colThree = [[NSNumber alloc] initWithDouble: [[arr objectAtIndex:2] doubleValue]];
  15. NSNumber *colOne = [[NSNumber alloc] initWithInt:[[arr objectAtIndex:0] intValue]];
  16. NSString *colFour = [[NSString alloc] initWithFormat:@"%@", [arr objectAtIndex:3]];
  17. //... we can now use these pointers to save to the CoreData database
  18. }
In line 06 of the code above, we've selected a newLineCharacterSet as the delimiter so that the file is split by lines. In line 14, we then use the comma character set to split the columns by comma. Et Voila! Finally, see the rather odd way of reading strings. Must be a simpler way...

Monday, November 9, 2009

Configure Tomcat 6 for JAX-WS

As a servlet container, Tomcat is not a full J2EE container hence requires some additional configuration in order to support JAX-WS. This article describes this configuration step-by-step:

  1. Download a copy of the JAX-WS library – Instructions here were tested this on version 2.1.5 (https://jax-ws.dev.java.net/2.1.5/)
  2. Copy the file JAXWS2.1.5-20081030.jar to an appropriate folder on your computer – say, /root/tools/ JAXWS2.1.5-20081030.jar
  3. Execute the jar: java –jar JAXWS2.1.5-20081030.jar
  4. This in effect unpacks the files contained in this jar. You should get a folder /root/tools/jaxws-ri containing the supporting libraries, docs, tools and samples. Let’s call this path $JAX-WS-HOME$.
  5. Copy the jar files in $JAX-WS-HOME$/lib/ to the Tomcat (let’s call the install path for this $CATALINA_HOME$) library$CATALINA_HOME$/lib and $CATALINA_HOME$/shared/lib path.
  6. Create an folder in the Tomcat installation directory called “endorsed”. The full path should be$CATALINA_HOME$/endorsed.
  7. Copy the files “jaxb-api.jar” and “jaxws-api.jar” from the “$JAX_WS_HOME$/lib” to the “$CATALINA_HOME$/endorsed/”folder.
  8. Edit the Tomcat configuration file “$CATALINA_HOME$/conf/catalina.properties” (You might want to take a backup before you edit it). There should be a property with the key “shared.loader”. Make sure the path $CATALINA_HOME$/shared/lib/*.jar is included in the comma separated list of paths in the value for this property. For example it could look like :shared.loader=/etc/tomcat/shared/lib/*.jar. That’s the main set of configuration that needs to be done.
  9. Before running tomcat, ensure the following property is to be set on the script used to start tomcat:
    -Djava.endorsed.dirs=$CATALINA_HOME$\endorsed
  10. This ensures the two jars we copied into the endorsed folder are picked up.
  11. Start tomcat.
UPDATE: This post makes assumptions about your source and web-archive being correctly set up. When I was doing this, I was working in a Contract-First approach and I wrote a quick guide to that here. This covers how your web.xml and sun-jaxws.xml file should be done. When I get sometime I'll upload a redacted version of my code as it has some work stuff. Good luck!

Contract-First Web Services in practice - part 5 of 5 (Java / J2EE)

This is the last article in the series of 5 and today we're looking at contract first development in Java/J2EE. I've left this for last after considering PHP and NET due to the various application servers and technologies in which this is possible. Java is also my forte hence I'm not shying away from this challenge. We'll look at JAX-WS on J2EE and Tomcat.

JAX-WS / EE5 Application Servers
If you prefer the blue pill and like the neat, java 5+, annotation heavy, jaxws-does-everything-for-you alternate reality, then you're in for a treat. The JAX-WS RI is available in most J2EE servers. I've picked JBOSS (the 4.2.2 GA) which is what I was using for work. JBOSS ships with wstools in the bin directory. Run the command "wsconsume -k SampleService.wsdl". This creates client stubs and a server interface "com.kimenye.SampleServicePortType". This is the class to be implemented. Once this is done, create a web.xml file and create a servlet with the servlet-class as the implementation created. Package this as a web-archive, and pop it into the deploy directory of the app server.

Tomcat 6
Tomcat 6 is a servlet container and not a full J2EE container hence it is not compulsory for it to provide JAX-WS. See my post on how to configure Tomcat 6 to use JAX-WS. Follow the steps below to implement the sample service:
  1. Use "wsimport" tool to create the service stubs. This tool is available from the bin directory of an unpacked JAX-WS installation. The full command to run is : wsimport -keep SampleService.wsdl
  2. Create a web application in your preffered IDE. Copy the artifacts generated from the wsimport into your source. Implement the port type interface. For our example this class will be com.kimenye.ProvisionServicePortType. Compile the implementations and the generated classes.
  3. Copy the wsdl into a folder named wsdl under the WEB-INF directory.
  4. Create a file named sun-jaxws.xml in the WEB-INF directory and fill in the content below:
    1. <endpoints xmlns="http://java.sun.com/xml/ns/jax-ws/ri/runtime"
    2. version="2.0">

    3. <endpoint name="SampleService" interface="com.applicationsnet.service.soap.SampleServicePortType"
    4. implementation=com.kimenye.SampleServiceImpl" wsdl="WEB-INF/wsdl/SampleService.wsdl"
    5. service="{http://kimenye.com/}SampleService" port="{http://kimenye.com/}SampleServicePort"
    6. url-pattern="/SampleService" />

    7. </endpoints>
  5. Edit the web.xml file to include the content below:
    1. <web-app xmlns="http://java.sun.com/xml/ns/j2ee" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    2. xsi:schemaLocation="http://java.sun.com/xml/ns/j2ee http://java.sun.com/xml/ns/j2ee/web-app_2_4.xsd"
    3. version="2.4">
    4. <description>sample</description>
    5. <display-name>sample</display-name>
    6. <listener>
    7. <listener-class>com.sun.xml.ws.transport.http.servlet.WSServletContextListener</listener-class>
    8. </listener>
    9. <servlet>
    10. <description>Sample End-Point</description>
    11. <display-name>Sample End-Point</display-name>
    12. <servlet-name>SampleServicePortType</servlet-name>
    13. <servlet-class>com.sun.xml.ws.transport.http.servlet.WSServlet</servlet-class>
    14. <load-on-startup>1</load-on-startup>
    15. </servlet>
    16. <servlet-mapping>
    17. <servlet-name>SampleServicePortType</servlet-name>
    18. <url-pattern>/SampleService</url-pattern>
    19. </servlet-mapping>
    20. </web-app>
  6. Create the web-archive file and copy it to your tomcat web applications directory.
  7. Edit the startup script for tomcat to include the property : -Dcom.sun.xml.ws.fault.SOAPFaultBuilder.disableCaptureStackTrace=false – This is related to how the soap faults are formatted and is IMPORTANT!
  8. Start tomcat and enjoy!