Computing and Smart Buildings

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:

And for the record, here is my program:

#include <stdio.h>
#include <string.h>

#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.

Ubuntu fonts problem after reboot

My screen fonts under Ubuntu are occasionally completely screwed up. They show up in blue with overstrikes:

I think this happens when I reboot my machine without a second monitor being attached to it, which it usually has. I suppose X.org gets confused when it cannot find a monitor that used to be there.

To solve this problem you must reconfigure X.org. Just enter the following and log out and in again to your X session:

sudo dpkg-reconfigure xorg

Strongest chess program money can (not) buy

Kinda offtopic, but I’m also an avid chessplayer, so…

Crafty is recognized as one of the strongest open-source chess engines available, having once achieved a rating of 2792 on the internet chess server and having an estimated 2608 ELO rating. A default installation on Ubuntu 8.04 (e.g. aptitude install crafty and aptitude install crafty-books-medium) will pack firepower enough to plunge anyone of us mere mortals into despair as we see it effortlessly pondering the game 13 moves ahead. But it’s actually quite easy to push the envelope even more and take full advantage of your computer’s hardware. Here’s what I did to turn my Dell Latitude D830 into, basically, an unbeatable (by me) chess opponent that almost burned my lap.

There are three things we are going to give Crafty to make it stronger:

• more memory for its transposition/refutation hash table
• more memory for its pawn structure/king safety hash table
• the second core of my Intel Centrino Duo processor.

My machine has about 2Gb RAM and we are going to use as much of that as we can for the transposition/refutation hash table, this being the most critical of the two. It can only be set to certain allowed values, and after some experimentation I found that the highest value I could give it before paging was 1536Mb. The pawn structure/king safety hash table gets the rest of my 2Gb RAM, or 128Mb.

Make sure you exit all (and I mean all) non-essential applications before you do this. I also had to stop my local MySQL and Apache servers to make this work without paging. You’ll also have to run the following command or Linux will not let you allocate that much memory:

sudo sh -c "echo 2000000000 > /proc/sys/kernel/shmmax"

How many threads to use on a multi-processor machine is set with the smpmt parameter, which I set to 2.

For reference, here is my complete .craftyrc file:

  hash=1536M
  hashp=128M
  smpmt=2
  exit

(And I’m not covering the almost 1Gb of openings database I have installed. I refer you to Crafty’s website on how to do that.)

You’re now all ready to start XBoard, and enjoy many fine chess games indeed. On the screenshot below you’ll see both crafty.bin processes share close to 1.6Gb RAM and how both cores jumped up to almost 100% usage. And just for fun, notice also how the CPU’s temperature climbed up to 64 celsius from an intial 44 celsius (it would later climb beyond 70 celsius). Don’t you just love it when a computer is used to its full potential instead of running screensavers?

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.

Trends in Smart Buildings Meeting, March 2009

Several home automation enthusiasts met again at LESO-PB to discuss recent developments in the field. There were four of us this time, Adil, Friedrich, David and yours truly.

Friedrich openened the discussion by telling us about his ongoing work on the influence of light, especially its color, on human health. Early results suggest that proper daylighting control will not only help us save oodles of energy but will actually make us healthier. For more details we will, however, have to wait for his thesis to be complete.

Adil showed us his recent work on the large-scale physical modeling of cities. He showed us how, from publicly available data (including data from Google Earth) one could derive a fairly realistic model of a city’s impact on its environment.

He told us also that he was considering analyzing shadows on pictures from Google Earth to derive 3D models of entire cities. This idea has great potential, provided he finds a way around Google’s tendency to stitch together satellite images taken at different times of the day.

We also discussed the recently announced Google Powermeter project, whereby Google aggregates measurements remotely taken on your utility meters and presents the information to you. We were all amazed that Google managed to pull this one off (and frankly we have no idea how they do it) but some of us also expressed concern about privacy issues. How long will it be until we start getting email telling us that “People taking their baths while watching TV usually buy this-or-that book. Click here to buy it now” ?

And finally the evening concluded with me asking the assembly for advice on some building simulation software issues I had been having lately. Friedrich, in particular, suggested I tried solving the problem in Fourier space instead of time space, something I would indeed never have thought about. I’ll definitely have a look and see if this could help for my open-source Heartbreak building simulation project.

Software Engineering Radio

People often ask me what podcasts I regularly listen to. Well there are many of them and I won’t enumerate them all here, but I wanted to mention one that I listen to almost every day nowadays.

Markus Voelter started Software Engineering Radio in January 2006. As he describes it on the website, this podcast tries to be a lasting educational resource and not a newscast. You won’t find new product announcements, no tech news of any kind. Only tutorials, interviews, and discussions about specific software-engineering topics.

When I discovered this podcast, about one year ago, I quickly downloaded just the episodes that appeared to be the most relevant to my work. But I found that almost all episodes had something in there for me. For example, recently I listened to the episode on real-time systems, a field I do not work in anymore. Well, at one point the interviewee discussed how jobs were scheduled in certain real-time systems, trying to optimize the total value or utility of the work done by choosing which tasks to perform and which to let slip past their deadlines. And that got me thinking about the Scrum planning process, when the Scrumaster selects, for the upcoming sprint, items from the product backlog in decreasing order of importance until the total estimated time fills up the scrum duration.

Now imagine for a minute that we could get the product owner to assign utility values to each product backlog item. Then instead of selecting product backlog items in decreasing order of importance, we could apply the same kind of decision process and optimize the utility created by each sprint.

(Later that day I went to the library to research this topic but all I found was an exercise from the classic Introduction to Algorithms in which the reader is asked to optimize such a job schedule. The chapter in question was the one about Dynamic Programming, in case anyone is interested.)

Anyway, back to SE-Radio. I’ve found the episodes’ quality range from good to very good, covering a broad range of topics. Perhaps they could be slightly improved with a little bit more structure, and also if the interviewer would stop regularly interrupting the guests with their own opinions. Sound quality has been an issue in the early days (ONE episode in particular was literally painful to listen to—I won’t say which one) but now it’s much, much better.

These days I listen to at least one episode a day, my goal being to listen to all of them. I can really recommend it.

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.

Trends in Smart Buildings Meeting, January 2009

I just realized how late I was with a summary of our last Trends meeting, which we held on Tuesday January 27th at LESO. So here follow my distant recollections of the event.

There were only three of us this time, but David was so kind as to give us a nice demo of the IDA simulation tool. He walked us through a typical use of the software, which apparently runs only on Windows. You basically use the provided GUI to build the model of your building, but IDA can also import from CAD tools.

From this model, IDA then builds a mathematical model of your simulation. From what I understood, it generates all the equations required to simulate the model, e.g. all the thermal nodes with their U-values etc. From there on the model is ready to run.

Running the simulation on a commodity PC took about 1 minute for 30 simulated days. Apparently IDA is unable to take advantage of multi-cores, so while it was running only one core was shown as busy.

You can also implement your own logic that should run along the simulation by embedding C code inside the NMF code generated by IDA. David showed us how he implemented a fuzzy logic controller running inside of IDA, implemented in C.

I had a good impression of IDA’s capabilities, especially the extensibility part. I am however a little bit put off by the fact that it runs only on Windows and is apparently not multithreaded. But that aside I think it is a neat tool.