Largest palindromic long long int that is also the product of two integers

Just to practice my C skills I’ve begun doing the Project Euler exercises in that language.

Project 4 asks what is the largest palindromic number that can be expressed as the product of two 3-digit numbers. The answer is 906609 = 993 x 913.

Just for fun I modified my program to compute the largest integer that could be represented in C on my machine as the product of two integers. After about 3.5 hours, the glorious answer came back:

999900665566009999 = 999980347 x 999920317

And for the record, here is my program:

\#include 
\#include 

\#define MIN 100000000LL
\#define MAX 1000000000LL

typedef unsigned long long bigint;

int is_palindrome(char* str) {
  char* n = str + strlen(str) - 1;
  while (n > str) if (*str++ != *n--) return 0;
  return 1;
}

int main() {
  bigint product;
  bigint a,b;
  bigint largest = 0;
  char product_str[30];
  for (a = MAX-1; a > MIN; a--) {
    if (a\*a < largest) break;
    for (b = a; b > MIN; b--) {
      product = a*b;
      if (product < largest) break;
      sprintf(product_str, "%llu", product);
      if (is_palindrome(product_str)) {
        largest = product;
        printf("%llu x %llu = %llu\n", a, b, product);
        break;
      }
    }
  }
  return 0;
}

Default welcome page with Tomcat and Spring MVC

In my professional development, I felt that I had always neglected the field of web aplication development. To correct this I’ve started a little side project with Spring MVC, a web application to help a Toastmasters club’s Vice-President Education with their duties.

Between the official documentation and the Spring in Action book, I found the documentation on Spring MVC more than satisfactory.

I wanted my webapp to display a default, welcome page. And just for extra points, I wanted to use the Velocity framework instead of the default Java Server Pages.

So I defined my web.xml file thus:

<web-app>
  <display-name><a class="zem_slink" href="http://www.toastmasters.org/" title="Toastmasters International" rel="homepage">Toastmasters International</a> - Education Assistant</display-name>

  <servlet>
    <servlet-name>tmi-education</servlet-name>
    <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
    <load-on-startup>1</load-on-startup>
  </servlet>

  <servlet-mapping>
    <servlet-name>tmi-education</servlet-name>
    <url-pattern>*.htm</url-pattern>
  </servlet-mapping>

  <welcome-file-list>
    <welcome-file>home.htm</welcome-file>
  </welcome-file-list>

</web-app>

And the Spring configuration file looks like the following:

<beans>
  <bean id="velocityConfig" class="org.springframework.web.servlet.view.velocity.VelocityConfigurer">
    <property name="resourceLoaderPath" value="/WEB-INF/velocity/">
  </property>
  <bean id="viewResolver" class="org.springframework.web.servlet.view.velocity.VelocityViewResolver">
    <property name="suffix" value=".vm">
  </property>

  <bean id="urlMapping" class="org.springframework.web.servlet.handler.SimpleUrlHandlerMapping">
    <property name="mappings">
      <props>
        <prop key="/home.htm">/home.htm</prop>
      </props>
    </property>
  </bean>

  <bean name="/home.htm" class="org.springframework.web.servlet.mvc.UrlFilenameViewController">
  </bean>
</bean>

With this setup, any URL whose filename ends with .htm should be mapped to a .vm velocity template, looked up from the WEB-INF/velocity directory. In particular, /home.htm is served based on the home.vm template.

And yet, when I point the browser to the root URL http://localhost:8080/tmi-education, I don’t see the default page. All I get is a 404 error message. Even more surprisingly, http://localhost:8080/tmi-education/home.htm works perfectly.

So why wasn’t Tomcat serving up the right welcome page? After much fiddling, and based on examples from this blog post, I finally found that you must include the following snippet in your web.xml file (at least under Apache Tomcat/6.0.18):

<servlet-mapping>
  <servlet-name>tmi-education</servlet-name>
  <url-pattern>/home.htm</url-pattern>
</servlet-mapping>

With this in place, the default welcome page works right.

Source code filtering with Maven

Today I searched for a Maven plugin that would filter some of my source files before compiling them. An equivalent to the resources plugin with filtering turned on, but for Java sources, that would replace occurences of, say, ${token.name} with somevalue wherever that string occurs in the source files.

I could not find such a plugin and I think I understand why. When the resources plugin processes the resources, it simply copies them from src/main/resources to target/classes, optionally filtering them. In the packaging phase, Maven simply zips up everything he finds in target/classes to the target jarfile.

But with source code you cannot simply copy the .java files to, say, target/generated after filtering them, and expect Maven to compile these filtered source files. You would have .java source files with the exact same name and same package declaration in src/main/java and in target/generated. So source file filtering cannot work in Maven unless you tell the compiler to change the directory from which to compile files. Well, I don’t have that much experience with Maven and I don’t know how to do that. I know the build-helper plugin can add a directory to the compile path, but I don’t know how to remove a directory from it.

On my project I needed to process only one single file. Let’s call it mypackage.Locator.java. I declared that class in a file named src/main/java/mypackage/_Locator.java (note the underscore). Then I configured an antrun task to copy that file over to target/generated/mypackage/Locator.java, a directory that build-helper had added to the compile path. I then told the compiler plugin to exclude all source files whose names begin with an underscore.

The most important parts of my pom.xml file look like this:

  <build>
    <plugins>

      <plugin>
        <groupId>org.apache.maven.plugins</groupId>
        <artifactId>maven-compiler-plugin</artifactId>
        <configuration>
          <excludes>
            <exclude>**/_*.java</exclude>
          </excludes>
        </configuration>
      </plugin>

      <plugin>
        <artifactId>maven-antrun-plugin</artifactId>
        <executions>
          <execution>
            <id>generate-locator</id>
            <phase>process-sources</phase>
            <configuration>
              <tasks>
                <filter token="token.name" value="somevalue"/>
                <copy file="src/main/java/mypackage/_Locator.java"
                      tofile="target/generated/mypackage/Locator.java"
                      filtering="true"/>
              </tasks>
            </configuration>
            <goals>
              <goal>run</goal>
            </goals>
          </execution>
        </executions>
      </plugin>

    </plugins>
  </build>

Note that you now let Ant filter the source files, so you must use Ant-like tokens (e.g. @token.name@). This works reasonably well, but if I can make some time for it I would really like to know how to remove the default source directory from the compile path.

Don’t unit test JavaBeans

Should unit tests cover JavaBeans just to get a higher code coverage?

These days I am working on a payment processing application that exposes its main interface as a SOAP web service. The API requires the client to build a wrapper object that packages the information needed for processing, for instance, a credit-card debit authorization: customer name and address, credit card number and so on.

I wrote the application code-first, and let the web service stack automatically generate the WSDL and other artefacts needed by the calling client software. From that WSDL and the generated XML schemas, the client can then generate the required Java supporting code to use the web service (almost) transparently.

This requires that I define those wrapper objects with a default no-args constructor, and that I define getters and setters for all its fields (the so-called JavaBean convention. Personally I dislike this kind of programming for a variety of reasons, but it was forced upon me by the web service stack.

When the time came to write unit tests, I actually had more time available than I had planned for, so I thought I should try to increase my test code coverage as much as possible. That led to several refactorings that overall helped the code’s testability, improved the test coverage, and probably improved the overall design.

But then I noticed that several of the wrapping objects’ get/setters had not been exercised by the test code. I first thought of writing unit tests for these classes, but then I realized how stupid that would be. Come one, writing unit tests for getters and setters?

A much better approach is to understand why the unit tests did not cover these methods in the first place. Upon investigating I discovered that I had not written unit tests that covered certain, very special logic branches&emdash;the very ones that needed those unexercised get/setters.

I duly wrote unit tests for these special cases, and after a few more minutes like this my test code coverage reached more than 80%, or twice what it was when I started out.

Lessons learned:

  • Write unit tests. Always.
  • Do not unit test JavaBeans. Unit test the methods that use the JavaBean methods instead.
  • Monitor your test code coverage. Tools such as Cobertura make this trivial.
  • Improve your test code coverage through relentless refactoring. Not only will your coverage improve, but so will probably your design.
Reblog this post [with Zemanta]

Spring for structure, property files for parameters

Spring is a great framework for externalizing the object graph of your application. Typically you write an XML config file that defines a number of Java objects (or “beans“) and how they are supposed to relate to each others.

For example, suppose you have a class ThermalNode whose instances need to hold a reference to, say, an instance of a TimeProvider class. The way you usually do this in vanilla Java is you define this relationship somewhere close to the program’s start:

ThermalNode node = new ThermalNode();
node.setTimeProvider(new TimeProvider());

But in Spring you define this structure outside of your main program, and the above would be written somewhat like this:

<bean class="ThermalNode">
  <property name="timeProvider" ref="timeProvider"/>
</bean>
<bean id="timeProvider" class="TimeProvider"/>

And thus the structure of your object graph has been moved away from your compiled code.

Where this got really interesting for me was when I started introducing parameters for the thermal nodes, e.g. thermal capacicities. I would have for instance this sort of structure:

+---------------+
|  ThermalNode  |
|---------------|
|  capacity1    |
+---------------+
       |
       \
       /
       \ conductance
       /
       \
       |
+---------------+
|  ThermalNode  |
|---------------|
|  capacity2    |
+---------------+

What you then start having are beans whose properties (or constructor arguments, which is the way I prefer doing it) are not only references to other beans but also values.

Now a requirement for this project of mine is that it should be easily customizable by the end user. And that means not having the poor user coming and manually edit Spring config files.

Instead, Spring lets you define properties in plain property files, e.g.

# A property file
capacity1=300
capacity2=250

Then these properties are available to your main Spring config file through this kind of incantation:

<context:property-placeholder
    location="classpath:my.properties"/>

And your beans can then refer to these properties like this:

<bean class="ThermalNode">
  <contructor-arg ref="timeProvider"/>
  <constructor-arg value="${capacity1}"/>
</bean>

I have found this way particularly useful, namely put the structural data in the Spring config file, and put the parameter data in its properties file. Doing so not only makes it easy for the user to run the program with different parameters. It also lets you stash away the Spring config file in your application’s jarfile, putting it out of the way of the user. And that, I believe, is a very good thing, because you typically do not want to confuse the user with Spring’s syntax.

Reblog this post [with Zemanta]

A unit test that Could. Not. Fail. (but did)

I am now convinced that even the most trivial pieces of code must be unit-tested.

Recently I’ve been working on a Java implementation of a building thermal model. A textbook model with thermal nodes and thermal capacities and conductances between them. This is supposed to eventually become part of a generic testing harness for home and building control algorithms. If you’re interested feel free to visit the project’s homepage.

I needed to implement thermal nodes whose temperature was given by an external schedule, e.g. read from a database of climactic data. Before I jumped in, I wanted to write a simplified node implementation whose temperature could be a simple function of time.

So I wrote a node implementation whose temperature would be a sinewave, oscillating between 20 degrees at noon and -20 degress at midnight. I defined a FunctionOfTime interface and implemented it with a SineWave class, the gist of which is shown here:

public class SineWave implements FunctionOfTime {
  private final long phase;
  private final double omega;
  private final double amplitude;
  private final double offset;

  public SineWave(double amplitude, double omega,
                  long phase, double offset) {
    this.amplitude = amplitude;
    this.phase = phase;
    this.omega = omega;
    this.offset = offset;
  }

  public double getAt(Calendar time) {
    return offset + amplitude *
        Math.sin((time.getTimeInMillis() - phase) *
        2 * Math.PI / omega);
  }
}

This code was extremely straightforward, but I had some time on my hands and wrote anyway a unit test for it:

public class TestSineWave extends TestCase {
  private SineWave sineWave;
  private Calendar calendar = Calendar.getInstance();

  protected void setUp() throws Exception {
    calendar.set(2009, 0, 1, 6, 0);
    sineWave = new SineWave(20, 24*3600*1000,
               calendar.getTimeInMillis());//-20 at midnight, 0 at 6am, 20 at noon
  }

  public void testGetAt() {
    Calendar calendar = Calendar.getInstance();
    calendar.set(2009, 4, 23, 12, 0);
    assertEquals(20, sineWave.getAt(calendar), 1e-5);
  }
}

You see what this is doing? The sinewave function will oscillate between -20 and 20 degrees with a period of exactly one day, 86400000 miliseconds. Its phase is defined so that on January 1st 2009 at 6am the temperature is 0 degrees. Therefore, on any day, you expect the temperature at noon to be 20 degrees.

Now when I ran it I got this:

Tests run: 1, Failures: 1, Errors: 0, Skipped: 0, Time elapsed: 0.025 sec
testGetAt(ch.visnet.heartbreak.TestSineWave)  Time elapsed: 0.004 sec
junit.framework.AssertionFailedError: expected:&lt;20.0> but was:&lt;19.318516902217773>
at junit.framework.Assert.fail(Assert.java:47)
at junit.framework.Assert.failNotEquals(Assert.java:282)
at junit.framework.Assert.assertEquals(Assert.java:101)
at junit.framework.Assert.assertEquals(Assert.java:108)
at ch.visnet.heartbreak.TestSineWave.testGetAt(TestSineWave.java:23)

I expected 20 degrees but got 19.3. It just did not make any sense. The rounding error hypothesis was easily ruled out: you just don’t make 3% rounding errors with modern implementations of the sine function. I tried with other days of the year, and always got the same result, 19.3 degrees.

The discrepancy being relatively small I was at this point very tempted just to ignore the thing, and to subconsciously blame it on some peculiarity inherent to Java’s Calendar implementations. I think I even entertained the thought that some days might have more seconds than others.

Come to think of it, this was actually not so far off the mark as it sounds. Are there days that do not have exactly 86400 seconds? The answer came instantenously when I tested for days in February: the answer came out right, 20 degrees.

Silly me. Daylight Saving Time. Of course.

Canonical data formats, middleware and GCC

These days I’m working on a middleware application that bridges a company’s ERP and its warehouses. The ERP posts messages in a given XML schema, our application reads these messages, transforms them into the schema understood by the warehouse management system, and uploads onthem on the warehouse’s FTP server.

We use XSLT to transform messages in one schema to messages in the other. In the example above, one XSL file can handle the whole transformation.

But what happens when you deal with more than one schema on either end? Suppose you have on the ERP side one schema for orders, one schema for defining the product catalogue, and so on. And on the warehouse side you might have more than one schema for different kinds of messages.

Say you end up with N schemata on the input and M on the output side, and suppose (for the sake of argument) that your application must handle every possible combination. If you use one XSL file per transformation, that’s NxM files. If the customer changes one schema on the input side, or adds one (and we have no control over that) then we must revise M files.

The classical solution to this combinatorial explosion is the Canonical Data Model messaging pattern. We have defined a common data format for our middleware application, and we transform all incoming messages to this common format before transforming them into the proper outgoing format.

With this solution, whenever a schema changes or is added we only need revise ONE XSL file. Pretty neat and innovative solution, right? I thought so too. Until I listened to this interview about the GCC internals.

The GCC can compile C, C++, Fortran, Ada, Java (and probably lots more languages) to an amazing number of platforms. How can it do this and avoid the combinatorial explosion when a language changes, or the definition of one platform changes?

Simple. It uses a canonical data format. More specifically, GCC’s frontend compiles the source code into an intermediate language-neutral and platform-neutral representation called GIMPLE. This representation is then translated by GCC’s backend into platform-specific code. If a language is modified, only the frontend must be revised. If a platform changes, only the backend must be revised.

The GCC folks (and probably many others) had been doing Canonical Data Format for decades before this pattern became recognized as such. And I thought we were being so clever…

Reblog this post [with Zemanta]

Remotely editing files as root with Emacs

I often need to edit files on remote machines or on embedded devices, that is, machines without a monitor and on which a proper editor might not necessarily be installed.

In the past that has always left me with the rather painful choice between vi and nano. Now I have never invested enough time in learning vi beyond the most basic editing commands. And nano is okayish for small edits but hopeless for larger ones.

So I was delighted to learn that you can edit files remotely through ssh with Emacs. If you want to remotely edit aFile on host aHost, open the following file:

/aHost:/path/to/aFile

The built-in Tramp package will take care of the rest. You can even use Dired remotely with this mechanism, an extremely powerful feature.

But what was missing for me was a painless way of editing remote files as root. The Tramp version that’s included in Emacs 22.2.1 was 2.0.57, with which I was unable to remotely edit files as root. The latest version of Tramp, 2.1.14, is in my humble opinion far easier to work with.

To install it, just follow the instructions. I created a directory ~/emacs into which I unzipped the Tramp distribution. I compiled it in place and did not bother installing it system-wide, being the only user of my system.

Then I added the following to my .emacs file:

;; Load most recent version of Tramp for proxy support
(add-to-list 'load-path "~/emacs/tramp/lisp/")
(require 'tramp)
(add-to-list 'Info-default-directory-list "~/emacs/tramp/info/")

With this in place, suppose you want to edit as root the files on aHost. The best is to add the following to your .emacs:

;; Setting for working with remote host
(add-to-list 'tramp-default-proxies-alist
'("aHost.*" "root" "/ssh:yourusername@%h:"))

Now editing remote files on aHost is easy, just open the following:

/sudo:aHost:/path/to/aFile

And that’s about it.

MATLAB, Java, Spring and dynamic classloading

I have sort of a love-hate relationship with MATLAB, and always had since I read its tutorial in January 2003.

On one hand it’s a proprietary closed-source system, which in my book rules it out for any scientific work. My one and only encounter with a Mathworks sales representative did nothing to help my misgivings. It is virtually impossible to reproduce any scientific work done on the MATLAB platform without a licence—rendering it almost by definition unscientific.

Furthermore, MATLAB as a language is very low-level, and lacks constructs found in most modern languages. Object-orientation is a joke. You can’t loop on anything else than vectors. There are no primitives per se apart from the matrix (a single scalar is a 1×1 matrix—come ooooon).

These gripes aside, MATLAB is remarkably useful in its own domain, namely technical computing. And the more I use Simulink, its embedded simulation tool, the more impressed I am.

A side project of mine involves a Simulink-based physical model of an office room, complete with wall and air temperatures, daylight illuminances, heating elements and power consumptions. But what’s really cool on this project is that we’ve extended the Simulink model with Java code running on the JVM that ships with MATLAB. This code exposes through RMI the heating, lighting and blinds control in the office room to any remote process.

I’ve used this model quite extensively on my PhD thesis, and I’m now trying to make it somewhat more useful to the wider community of building control algorithm designers. To that end I have explored the possibility of basing this Java code on the Spring framework, in particular the parts that require database queries.

Well the proof of concept I wrote worked out just fine, with the following caveats. First, forget about dynamically loading Java classes from MATLAB. Second, FORGET ABOUT DYNAMICALLY LOADING JAVA CLASSES FROM MATLAB. It just doesn’t work beyond baby-style HelloWorldish applications. And it certainly will not work for any code relying heavily on the Class.forName() construct, which is vital for Spring.

I think part of the reason is that it’s not the same classloader that does the dynamical loading and the static one. According to this bug report, if your classes are on the dynamic path then you must use the following signature:

java.lang.Class.forName('com.mycompany.MyClass',true,cloader)

where cloader is the classloader that loads classes from the dynamic path. But who’s going to dive in and change the Spring code for that?

So forget about dynamic classloading in MATLAB. Just edit classpath.txt to point to your jarfiles and everything will be fine. Really. I have packages the Java code using Maven’s jar-with-dependencies predefined assembly descriptor, yielding a single jarfile with all my dependencies, including Spring and the MySQL connector. Just splendid.

We even have a webpage for this project, but be warned that there’s not much there yet. The URL is http://smartbuildings.sf.net/coolcontrol/

Schema validation with LXML on Ubuntu Hardy

LXML is an amazing Python module that picks up where the standard xml.dom(.minidom) left off.

It’s basically a set of wrapper code around the libxml2 and libxslt libraries, and provides functionality missing in Python’s standard library, including XML validation and XPaths.

On a project I’m currently working on I needed a good XML library for Python and ended up trying out lxml. But I simply could not get the schema validation to work, and after several wasted hours I understood that the default lxml that ships with Ubuntu Hardy (the distro I’m using) used the relatively old 1.3.6 python-lxml package.

I’m usually very reluctant to install anything as root that does not come from the “official” repository, but for lxml I made an exception and installed the python-lxml package from the upcoming Intrepid distribution.

Add the following line to your /etc/apt/sources.list file:

deb http://ch.archive.ubuntu.com/ubuntu intrepid main

Then run Synaptic as usual and install python-lxml version 2.1.1. To verify that it works fine, you can test schema validation thus:

>>>> from lxml import etree
>>>> schema_tree = etree.parse('path_to_schema.xsd')
>>>> schema = etree.XMLSchema(schema_tree)
>>>> doc = etree.parse('path_to_some_document')
>>>> schema.validate(doc)

That last command returns as a boolean the result of the validation.