Sorting and Searching Algorithms and Project Euler

I've some extra time recently (well, not really), so I've decided to increase my understanding of sorting and searching algorithms.

http://code.google.com/p/kgl-algorithms/

The project hosting site above is where I'll be doing my work.

I'm also using this to get familiar with Java, and in particular: polymorphism, interfaces, exceptions, encapsulation, inheritance, and modularization.

I've also started doing some problems from the Project Euler site, an algorithm problem website. Here's some of my solutions:

http://code.google.com/p/kgl-project-euler/

33. Decathlon Design 3

This is the final phase of our solar decathlon home management system mockup for the semester. We've been tasked with taking our Balsamiq mockups and converting it to an HTML-Wicket Framework model.

http://code.google.com/p/solar-decathlon-teamhawaii-6/

What I learned from this:

I learned a lot about Wicket, and got some very helpful hints on web design as well. I also can see the advantages of a framework like Wicket; it allows the developer to bundle everything into a neat little archive file that can be run from any computer. And in the webpage sector, this involves bundling a webserver (we used Jetty) so that any prospective client can view dynamic web content as long as they have the Java JVM installed. This avoids the difficulty of having to set up a web server or the need to have internet access in order to view a dynamic web page.

What we did well:

I've been lucky enough to be part of a group that has two exceptional web designers and programmers, which makes it incredibly easy and efficient to get things accomplished. I thought that we did a good job on focusing on the development of a template. This really allowed us to push forward quickly with the knowledge that the framework that we were working on was sound and well-developed.

Some Difficulties Encountered:

There was a lot of time spent just figuring out how to get Wicket to do what we wanted to in the HTML markup. There was also some Javascript that we used for some of the interactive portions of the system, and importing different libraries and getting them to sync with the CSS files was challenging to say the least.

What I wish we had done differently:

I would've liked to have created my own CSS file for custom classes. I had to add a few CSS classes and during one instance, I updated the CSS and found that another team member had committed the same CSS file prior to me, resulting in a conflict.

Other than that, we had pretty good communication and met a number of times in-person as well as over the phone to ensure everyone was on the same page.

How did we satisfy the three prime directives?

The three prime directives of open source software engineering are:

1. The system successfully accomplishes a useful task.
2. An external user can successfully install and use the system.
3. An external developer can successfully understand and enhance the system

Directive 1:

This system provides home users with a portal that allows them to view the current status of the major systems within the home. It also allows the user to change settings such as temperature, lighting, and security to name a few.

Directive 2:

Due to the use of the Ant build system, installing and running the embedded jetty server takes a single command: java -jar filename.jar

Directive 3:

Developers can edit the server-side source code via eclipse (distribution file has been included in downloads section).

LISP and Finding an Interpreter/Compiler

After hearing of the 'light switch' effect and nirvana that LISP brings about, and reading the following article:

http://www.defmacro.org/ramblings/lisp.html

I've decided to start learning LISP during Christmas break. I had about a 3-week crash course on it during my Computer Programming Concepts class, but I didn't really think much more of it other than 'okay that was cool, but I'll never use this again.'

The Search for An Interpreter/IDE

I started by going through a couple of the available LISP interpreters: GNU CLISP, Ufasoft LISP, and LispWorks.

I'd used LispWorks before but decided that I ought to try some other IDE to get a sense for what's out there.

After trying to install Ufasoft, I found that a Microsoft Visual Studio component needed to be installed first. Cancel -- I wanted something that could work on both my MacBook and Windows machines. GNU CLISP installed fine, but this gave a command-line only interface and a quick look through things did not uncover any extensive help information.

So back to LispWorks. Here we go!

Network to Host Long Long

Since I'm applying for summer internships and employment now, I've been trying to hone my coding skills. I decided to implement my own version of network-to-host-long-long (ntohll) for 8-byte integers using bitwise operators in C. Operates similar to ntohs(short s).

Source code: http://kevingleong.blogspot.com/2010/12/network-to-host-long-long-source-code.html

This was for a group networking protocol assignment in my data networks class.

http://code.google.com/p/ics451-vsp-protocol

It was challenging, although time consuming, and later I found a much more elegant solution on the internet. But this my ugly bastard child and I'm keeping it.

Network to Host Long Long (Source Code)

/**
 * Determines the host machine's endianness.
 *
 * @return 1 if Little Endian, 0 if Big Endian
 */

int checkEndian () {

  void * p;
  unsigned short * shortP;
  
  unsigned char buffer[2];
  p = (void * ) buffer;
  shortP = (unsigned short * ) p;
  
  * shortP = 0x01;  
  
  if (buffer[0] == 0x00){
    if (debug) {
      printf("Big Endian\n");
    }
    return false;
  }
  
  else {
    if (debug) {
      printf("Little Endian\n");
    }
    return true;
  }

}

 /**
  * Given a long long number reverse the order of the bytes
  * if the machine is Little Endian.  Otherwise do nothing and
  * return the number.
  *
  * @param input - network value to be converted to host order
  */
  unsigned long long ntohll (unsigned long long input) {
    if (checkEndian()){
      unsigned long long result = 0;
      unsigned long long mask = 0xFF;
      
      if (debug){
        // Print INPUT      
        void * p;
        unsigned char * buffer;
        p = (void *) &input;
        buffer = (unsigned char * ) p;
        int j;
        for (j = 7; j >= 0; j--) {
          printf("%x ", buffer[j]);
        }    
        printf("\n");
      }
      
      // Input will be reversed
      // Need to reverse all 8 bytes
      int i;
      for ( i = 0; i < 8 ; i ++){
         
        if (i < 4) {
          result = result | ((input & ( mask << (i * 8) )) << (8 * (7 - 2 * i) ));
        }
        else {
          result = result | ((input & ( mask << (i * 8) )) >> (8 * ( 2 * (i - 4) + 1) ));
        }
      }      
      // Print resulting value 
        if (debug) {
          void * p;
          unsigned char * bufferResult;
          p = (void *) &result;
          bufferResult = (unsigned char * ) p;
          int j;
          
          for (j = 7; j >= 0; j--) {
            printf("%x ", bufferResult[j]);
          }
        printf("\n");
      }   
      return result;
    }
    
    // If Big Endian, we can just return value without swapping bytes
    else {
      return input;
    }
  }

 

Google Visualizations for Final Project (ICS413)

NOTE:

chart size: Width x Height: 410 x 350 (&chs=410x350)

Title Font Size: 16.5 (&chts)

Axis Font Size: 11.5 (default)

Tick marks (y-axis, x-axis): 1,15 (&chxtc=1,15)

Energy Page:

(by Day)

http://chart.apis.google.com/chart?chxl=1:|Mon|Tues|Wed|Thurs|Fri|Sat|Sun&chxs=0,676767,11.5,0,lt,676767|1,676767,11.5,0,lt,676767&chxtc=1,15&chxt=y,x&chs=410x350&cht=lc&chco=DA3B15,008000&chd=s:QMNRVekpnlgfW,somedabelprmnr&chdl=Power+Consumption+(kWh)|Power+Production+(kWh)&chdlp=t&chg=16.67,10&chls=3|2&chtt=Energy+Consumption+vs+Energy+Production&chts=676767,16.5

(by Month)

http://chart.apis.google.com/chart?chxl=1:|Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec&chxr=0,500,2000&chxs=0,676767,11.5,0,lt,676767|1,676767,11.5,0,lt,676767&chxtc=1,15&chxt=y,x&chs=410x350&cht=lc&chco=DA3B15,008000&chds=500,2000,500,2000&chd=t:926.259,759.968,801.055,865.218,1112.252,1000.682,1014.534,794.78,794.213,768.188,639.259,691.447,655.782|1039.359,1107.18,1051.859,1148.457,1200.341,1413.972,1478.653,1435.088,1389.195,1283.2,1262.331,1333.671,1186.133,976.084&chdl=Power+Consumption+(kWh)|Power+Production+(kWh)&chdlp=t&chg=9.091,6.6667&chls=3|2&chtt=Energy+Consumption+vs+Energy+Production&chts=676767,16.5

Energy Breakout:

(by Day)

http://chart.apis.google.com/chart?chs=410x350&cht=p3&chco=EA0D0D|FF9900|3EC03E|3267CF&chd=t:45.634,50.337,28.189,25.964&chdl=Aquaponics|HVAC|Appliances|Lighting&chdlp=t&chtt=Energy+Consumption+Breakdown+by+Category&chts=676767,16.5

Temperature:

(by Day)

http://chart.apis.google.com/chart?chxl=0:|20|40|60|80|100|120|1:|Mon|Tues|Wed|Thurs|Fri|Sat|Sun&chxs=1,676767,11.5,0,lt,676767&chxtc=1,15&chxt=y,x&chs=470x350&cht=lc&chco=F66617,4582E7&chd=s:somedabelprmnr,acbXXPNbgggfis&chdl=Outside+Temperature|Inside+Temperature&chdlp=t&chg=16.67,10&chls=3|3&chtt=Inside+vs.+Outside+Temperature+(Fahrenheit)&chts=676767,16.5

Aquaponics Statistics:

(pH by Day)

http://chart.apis.google.com/chart?chxl=0:|5|5.5|6|6.5|7|7.5|8|8.5|9|9.5|10|1:|Mon|Tues|Wed|Thurs|Fri|Sat|Sun&chxs=1,676767,11.5,0,lt,676767&chxtc=1,15&chxt=y,x&chs=470x350&cht=lc&chco=FF0000,3072F3,FF9900&chds=0,100,-5,100&chd=t:30,30,30,30,30|42.043,45.165,44.785,37.934,38.18,25.102,21.844,44.405,51.957,52.305,52.412,50.339,55.195,72.881|48,48&chdl=Min+Recommended|Inside+Temperature|Max+Recommended&chdlp=t&chg=16.667,10&chls=2,5,5|3|2,5,5&chtt=pH+Levels&chts=676767,16.5

Aquaponics:

(Water Quality - Current Quick Look)

http://chart.apis.google.com/chart?chxl=0:|pH|NH3|Bacteria|Temp|O2|AT&chxt=x&chbh=a,5,15&chs=275x200&cht=bvg&chco=FF9900,008000&chd=s:cnwhZj,eYNkph&chdl=Actual|Recommended&chdlp=t&chtt=Water+Quality+(Quick+Look)&chts=676767,13.5

Aquaponics Water Reserves

(Current Levels)

http://chart.apis.google.com/chart?chs=470x350&cht=p3&chco=E93434|80C65A&chd=t:65,35&chdl=Used|Remaining&chdlp=t&chtt=Current+Status+of+Water+Reserves&chts=676767,16.5

31. Wicket Katas

We've been tasked with modifying a few example Wicket framework projects as "katas".

Wicket expertise prior to the Katas:

I've been slowly reading through the Wicket book. I think I a vague (albeit better) understanding of the difference between the static and dynamic model system. I would say that my understanding of Wicket as of now is still pretty elementary; I am still a little unsure about the whole component/model relationship and when a component gets re-rendered. Little by little, however, and as I continue to read the book, I've acquired a better understanding of the functions and underpinnings of the framework.

Here's a link to a description of the Katas: ICS413 Wicket Katas

Kata 1A: Duration - 30 min

Kata 1B: Duration - 10 min

Kata 1C: Duration - 2 min

Kata 2A: Duration - 1 hr 15 min

Kata 2B: Duration - 4 hours

Kata 3A: Duration - 30 min

Kata 4A: Duration - 5 min

Kata 4B: Duration - 20 min

Kata 6A: Duration - 2 min

Kata 6B: Duration - 2 min

Kata 6C: Duration - 2 hrs

Total Duration: 8 hrs 16 min

ALL Katas Completed.

Distribution Versions:

Example 01

Example 02

Example 03

Example 04

Example 06

For the most part, a lot of these Katas were adapting already existing code to meet the specifications and weren't all that difficult. 2B, however, took a lot more time to figure out. Here's what we were tasked to do:

Kata 2B: Add a button on the home page with the label, "Make font bold". After the user pushes it, all the text on the page should become bold, and the button label should change to "Make font italic". When the user pushes that button, all of the text should change to italic and the button label should change to "Make font normal". Pushing that button changes the text back to its original state and the button label should now say "Make font bold".

This kata really forced me to examine the interaction between what's presented on the page versus what lives in the java code. I also had to attach a CSS style attribute to the body of the page, which had nested tags, so Wicket's hierarchical structure initially caused errors in the page. After matching the hierarchy with the Java code, I was able to use the attribute modifier function to toggle between font-weight: bold/normal and font-style: italic.

Another problem that I ran into was the toggling of the styles with a submit button. This meant saving a state of some sort, which I solved through use of a session. Prior to this, the flag I used to toggle between styles would not save it's state between page refreshes.

Finally, I had to implement a child class to the Link class. For some reason or another, the button and submit classes did not refresh the page as needed. In order to change the label on the button with each click, I had to create a child class to the link class and implement this toggling of the label within the constructor.

This was by far the most difficult of the 11 assignments.

Probably the second most interesting kata was the following:

Kata 6C: It is often convenient for web applications to consult a properties file when starting up in order to get configuration values. An easy way to do this is with the standard Java Properties mechanism. (See Java in a Nutshell for details on properties file manipulation.) For this Kata, modify your Example06 system to read in a file (if present) located in ~/.example06/configuration.properties. (Note that ~ means "the user's home directory", and that there is a System property in Java that provides this value.) This property file should contain a line like the following: deployment=true

Although not really enlightening in regards to improving my familiarity with Wicket, I did learn about Properties files in Java and how they're used to configure applications. This exercise also helped me brush up on catching exceptions and opening files and streams.

Conclusion

I liked these exercises. I thought they were very do-able and the combination of having templates to work from in addition to other resources (book and Google) really helped to lessen the frustration factor.

I'm starting to appreciate the framework and it's workings. Although by no means have I mastered models, I do have a basic understanding of them as well some of the limitations that the framework presents. E.g., the need to store variables in a session in order to preserve their current values.

The Cheeser example is starting to grow on me too the more I look at it and examine what it can do.