Test Driven Development and Project Euler Series: Smallest Number Divisible By a Set of All Numbers Less

Disclaimer: I will NOT disclose what the answers are to these problems.  The intent is that the testing is just as important, and in most cases, more than the answer.  If you want to know what the answer is without solving the problem, a simple google search will tell you what it is.

Background:

  • If you are not familiar with the series, please read this.
  • This is Java driven, as well as JUnit 4.
  • You are familiar with TDD tenants.

References:

Problem:

“2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?”

Difficulty: Crazy Easy, even via semi-brute force.

Background:

Because this problem is Crazy Easy, I’m not going to include the test file.  One thing to note is that after I solved th problem, I read the solution.  The answer was super elegant, but was initially difficult for me to comprehend.  I actually got a pen and paper and worked out the example(s) before I comprehended it.

Any way, I approached it with workability (yet legible) first (adjusted for 60s project Euler limit), elegance second (remember, let the test dictate your code), speed third.  So the brute force method is to start from 2 all the way to the highest possible max (which you get from multiplying all the numbers from 1 to 20), and for every single number, evenly divide it by all the numbers from 1 to 20 (modulo).  The first number that comes up is the correct answer.

My first tweak was the idea that let’s not start from 1, but let’s guess at a good number to start.  How about multiples of all the prime numbers less than or equal to N, where N is 20, or the number in question.

For the first test, let’s call it: shouldGetTheMultipleOfAllPrimesLessThanOrEqualToN.  In short:

  • assertEquals(3, smallestPrimeFactor(3));
  • assertEquals(3, smallestPrimeFactor(4));
  • assertEquals(15, smallestPrimeFactor(5));  // assertEquals(1*3*5, smallestPrimeFactor(5));
  • etc

Great.  I found my magic starting number and thought:

  • start at the magic number
  • end at the max magic number (mult of all numbers less than 20 inclusive)
  • increment by 1
  • divide that value by all numbers 20 or less inclusive.

Sounded like a chore to me and, perhaps, too brute force.  That’s when I thought, let’s take the multiple of primes and divide it by all the numbers below it.  Sounded like a plan.  I combined the two concepts above, and solved the problem fairly quickly.  I read the solution provided by Project Euler and didn’t understand it initially.  But I’m glad I read through it because it’s invaluable knowledge.

Linux Mint: Debian’s Favorite Grandchild

Linux Mint (Gloria release), at the time of writing via distro watch, has arguably become Debian’s favorite grandchild.  I can’t say that I use it, but I do recommend it.  I just installed it for a friend of mine.  I’ve installed it before and evaluated it, but I liked Ubuntu’s package manager better.  Just a personal preference, just like my preference towards Ubuntu’s desktop.

That being said, I will tell you what I do like about Linux Mint and why I recommend it to Windows’ converts.  Aside from its price tag (free as in speech, of course), its desktop interface is super easy to use.  Those who are familiar with modern desktops should be more comfortable with the environment.  It combines ease of use with a lightweight feel, free of heavy widgets, and any subsidizing promotional applications distributed with certain versions.

For common tasks, application management and organization seem to be more straight forward than Ubuntu.  The desktop seems “friendlier” as well,  with a hint of familiarity.  While virtual desktops is not inherently obvious, it is easy to invoke.  With one of my favorite key strokes, alt-ctrl left or right arrow, I can switch pretty easily from one desktop to another.   Compiz looks great on it, but didn’t install it for my friend.

There are other things that make Linux Mint pretty cool.  Like the integration of media codecs right out of the box.  Or the installation interface, which is based on Ubuntu’s installation interface but can be easier to use.  In conclusion, I still probably won’t use it personally, but I would recommend it to converts looking for a better experience than Windows.

References:

Test Driven Development and Project Euler Series: Palindrome Divisible by Three Numbers

Disclaimer: I will NOT disclose what the answers are to these problems.  The intent is that the testing is just as important, and in most cases, more than the answer.  If you want to know what the answer is without solving the problem, a simple google search will tell you what it is.

Background:

  • If you are not familiar with the series, please read this.
  • This is Java driven as well as JUnit 4.
  • You are familiar with TDD tenants.

References:

Problem:

“A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.”

Difficulty: Easy

The Test File:

  • Please download it here.

Explanation:

A brute force approach would be to go from 10,000 to 998,001 and evaluating each number for the two criterea:

  • Is this number a Palindrome?
  • Is this number a product of two three digit numbers?

Not being a mathematician, I kind of liked a brute force idea, but I tweaked it a bit.  Instead of an incremental approach from min to max, I decided to use a decremental approach.  I suspected that the answer should be in the 900,000′s.  I only have to traverse through, at most, 100,000 integers.

For determining the divisibility, I was also going to take a brute force approach as well, but I was going to make an assumption.  That is, I’m going to guess that both products will be between 800-999.  So the determination will be a decremental loop starting from 999.  If the palindrome is evenly divisible by that number, I would divide the palindrome with that number, and check if the product is less than 1000.  So it goes like this:

  • Start from 998,001 and decrement by one in a loop.
  • Is the number a palindrome?
  • If so, is it divisible by a number in a decremental range starting from 999, and ending in 800.
  • If so, is the product of the palindrome and that number less than 1000?
  • Good.  Print the number, or print the number and exit.

The hardest thing about this problem then was then evaluating whether or not a given number is a palindrome or not.  I know what a palindrome is, but I never implemented an algorithm that evaluated a palindrome.  With strings, it’s slightly easier because you can easily compare first and last characters in Java and then strip them.  You have charAt at your disposal, substring and many implementations of strip (first and last chars).

With numbers how do you do that?  I didn’t know, so I had to write it out on paper.  After that, it was fairly straight forward.  I had to write an algorithm that compared the first and last digits of the number using modulo based on ten and divisors based on 10.  Then I had to write an extractor that stripped out the left and right most digits.

Stop if the stripped digit is either single or double digits.  If it gets down to single digits, the number is a palindrome.  i.e.: 151 is a palindrome because the first and last digits are equal and the remainder is 5.  This works for all three digit (or odd) digit numbers.

Stop if the stripped remainder is two digits.  If the number is a palindrome (22, 33, etc) return true.  Else return false.

Implementation Details:

Methods shouldTestGetLeftMostNumber, and shouldTestGetRightMostNumber were my first two test methods.  It was easy to implement (10 based divisors retrieved left most numbers, modulo retrieved right most numbers).  I started with one test first, for example:

  • Given the number 5, I expect that left most number is 5.  Assert that 5 is expected against the actual, 5.

Then the tests followed…

  • Given the number 61, I expect that the left most number is 6.  Assert that expected and actual are equal.
  • You can do tests for any random 3, 4, 5 and 6 digit numbers.

Getting the right most number was similar and just as trivial.  Example:

  • Given a number 462, I expect that the right most number is 2.  Assert!
  • I didn’t do negative cases because I used random numbers.

So a palindrome checker is fun to implement.

  • Are the two numbers  on the ends equal?  If not, stop and return false;
  • If so return the center.
  • Stop and return true if the remainder is single digit.
  • Stop and return false if the remainder is double digit but not a palindrome.
  • Stop and return true if the remainder is double digit and is a palindrome (22, 33,  44, etc).

That’s it!!!  Now, how you implement your methods are totally up to you.  You can use recursion for the palindrome checker, but I didn’t.  I used iterative approaches for speed (although, unlike the Fibonacci problem, recursion shouldn’t pose to much of a performance hit).

Divisibility by three digits is easy as well.  It’s trivial so I need not write out the implementation.  Just guess that the range is between 999-800, decremented.

Java/Ubuntu/JBoss/Oracle XE Part II: Installation

This is the second installment of part I of the previous blog.  It will deal with the implementation portion.  If you have not already done so, please read the previous post.

Background:

This stack is a great choice for corporate environments or for someone who wants to learn Oracle and the full J2EE stack.  Make sure that your Ubuntu Server is the 32 bit version.

Quick Downloads:

Install the JDK:

You have two choices for your jdk.  There’s an open source JDK, aptly named OpenJDK, a free-as-in-speech version of the jdk.  Most mid to large projects use the free-as-in-beer version.  Plus with Sun being pwned (sic) by Oracle, it makes sense.  That’s what I recommend for this exercise.  You can install Sun’s JDK via the command line, but I don’t like that route.  I only install the JDK via the command line if it’s the OpenJDK version.

  • Download the JDK here.  DO NOT CHOOSE any of the bundles.
  • Do choose Java SE Development Kit (pick the latest update).
  • Pick the Linux distribution (32 bit version).
  • It will be a .bin file and is an executable.
  • Run it from the command line.  You’ll have to agree to an SLA.  The result will be a folder.
  • Rename the folder to java.
  • Move the folder to your /opt folder.
  • Alter your .bash_profile, .bashrc or /etc/bash.bashrc file to include the following:
  • JAVA_HOME=/opt/java
  • PATH=$PATH:$JAVA_HOME/bin

Install JBoss:

  • Make sure you have unzip installed.  If not, type:   sudo apt-get install unzip.
  • Download JBoss here or from the sourceforge site.
  • It’s going to be a zip file.  Unzip it.  It will extract as a folder.
  • Rename the folder to jboss.
  • Move the jboss folder to /opt.

Install Oracle XE:

Refer to my previous blog on installing Oracle XE on Ubuntu Server (Jaunty), 32 bit version.

Conclusion:

There you have it.  A full implementation of the JBoss/Oracle XE stack.  Stay tuned for an implementation of Weblogic/Oracle XE stack.

References:

Oracle XE installation on Ubuntu Jaunty

These are my notes from installing Oracle Express Edition on my Ubuntu Server (Jaunty).  I am writing this partly because I will write a sequel to my other blog based on a Java/Ubuntu/JBoss/Oracle XE environment.  This sequel will be way too long if I include this in the same blog.  So here it is as a separate entry.

Background:

For your smaller projects, the Oracle database, even the Express Edition, probably isn’t your best choice.  Why?  Well, for one, Oracle is a beast.  Volumes of books have been written on the administrative portion alone.  The hardware requirements are pretty thick (Express Edition recommends half a gig of RAM, but I say at least a Gig, 1 will give your server more flexibility). Although queries are fairly easy to write (and I like the Oracle syntax over ANSII), writing packages and stored procs can be daunting.

Another thing you want to take seriously are the hardware requirements itself.  I wanted to install it in a 64 bit OS with OXE 32 bit binaries.  The 10g version does not support this.  Why?  Because Oracle does not want you to use this edition for production purposes.  It enforces this by limiting you to single core, 1 Gig of RAM and 4 Gigs of data.  I can see where they are coming from, but I think it’s kind of silly.

Lastly, I found this out the hard way, you’ll need a desk top so that you can finish the rest of the configuration.  I installed this on a 64 bit virtualized server host, so I didn’t want to use more memory than needed.  After hours of google-fu, I ended up deleting the host, reinstalling Ubuntu Server (Jaunty) as a 32 bit edition, upgraded to 2 gigs of RAM, with xfce as the desktop.  I lowered the number of processors to 1 since I didn’t need more due to Oracle XE’s 1 core limitiation.

Requirements:

  • Single core machine
  • Max of 1 Gig of RAM, but you can have more.  Oracle won’t use it.
  • 32 bit version of Ubuntu Server Edition
  • Comfortability with command line based terminal
  • root access

Installation:

So the installation process is pretty straight forward.  The notes below represents basically the documentation.  So I’ll make this as concise as possible.  For a more in depth documentation, please click here.

  • Download the Express Edition here.  You may have to sign up for a user account.
  • Choose the Western European character set.  For Ubuntu downloads, choose oracle-xe_10.2.0.1-1.0_i386.deb.
  • su as root.  If you don’t know how to do that, click here.
  • Go to the folder in which you downloaded the binary.  Type:
  • dpkg -i oracle-xe-universal_10.2.0.1-1.0_i386.deb
  • Configure by typing:
  • /etc/init.d/oracle-xe configure
  • Go with defaults for http port, the listener and auto start
  • Pick a strong password (chars, CAPS, nums).  REMEMBER THIS PASSWORD!!!

Set your env vars:

  • in your terminal,  do the following:
  • type:   cd /usr/lib/oracle/xe/app/oracle/product/10.2.0/server/bin
  • make sure you have permission to execute  scripts on file oracle_env.sh
  • type:   ./oracle_env.sh

Alter bash.bashrc or .bash_profile or .bashrc to set your env automatically.  I prefer editing the bash.bashrc because I like my environments initialized at start up.

  • append to end of file with vi or nano:   /usr/lib/oracle/xe/app/oracle/product/10.2.0/server/bin/oracle_env.sh

OK, so hopefully you installed Oracle XE on Ubuntu Server (instead of Desktop).  So you’ll need a desktop.  In your terminal, type the following:

  • sudo apt-get update
  • sudo apt-get install xubuntu-desktop
  • you may have to restart

A couple useful commands:

  • start:   /etc/init.d/oracle-xe start
  • stop:   /etc/init.d/oracle-xe stop

Make sure that OXE is started.  If not, type the start command in your terminal above.

On your desktop, pull up your favorite browser.  In the address bar, type:

  • http://localhost:8080/apex

You’ll have to login with your SYS or SYSTEM username and the password you defined above.

You’ll have to go to Administration–>Manage HTTP Access.  Choose:

  • Available from local server and remote clients
  • Click Apply Changes

Now you can do CRUD actions and write queries from remote computers.

You’re basically done.  You can install the oracle client, found here.  If you like TOAD (Windows), you can get it here.

References:

Test Driven Development Series Using Project Euler

This is a rewrite of my previous blog on test driven development, or TDD.  It will be based on two premises.  First, all tests (including test files) are going to be in Java.  That means we will be familiar with the language, understanding of the Eclipse IDE and know something about JUnit.  For those familiar with other languages, this blog may or may not seem fit.

Second, we will solve problems form Project Euler by writing tests first.  I’m not through the problems, not even close.  I’m not even sure if this process can scale (adjusted for my problem solving skills) as the problems get harder.  But I will try to solve as many as I can.

That being said, I would like to introduce some best practices into how we should break these problems down.  First, let’s make the code work under 60 seconds.  If the code doesn’t work, we can’t solve the problem, right?  Second, make the code elegant.  Third, make the code fast.  The second and third are a little tricky.  We aren’t working with a complex business process.  We are working with algorithms that’s been studied and has been around for a while.

So when you solve a problem in Project Euler, you get to see the answer which may be different from what you wrote.  You may notice it’s a lot smaller and is more efficient.  By reading the solution, I have learned a lot.  Perhaps the next iteration of these problems will focus on code optimization after writing the initial solution.

A computer science approach is to think about the problem, and write the most optimized code.  Elegance and speed are paramount.  I don’t disagree, however, with TDD, I want to let the test do the writing.  Essentially, sometimes the easiest path (brute force) is a good start.  From there I tweak it, then I write the test.  I don’t want to think about the problem too much, unless I’m stumped.  Then I bust out the pen and paper and start writing down ideas.  But I’m going to write a test first, way before I write an ounce of code.  I’m not going to implement more than I need to without writing the second test.

I’m not a genius and that is a good thing.  I believe if I can solve these problems, so can you.  That’s why I start out the easiest solution first, be it may be brute force.  It gives me to make something abstract into something concrete.  Then I can start to write testing, then using my tests to implement a solution.

Java/Ubuntu/JBoss/Oracle XE Part I: Background

I recently wrote two blogs.  The first, deals with Java/Ubuntu/JBoss/MySQL.  The second, deals with Java/Ubuntu/Tomcat/MySQL.  This deals with Java/Ubuntu/JBoss/Oracle Express Edition.

Update: I just finished a blog on installing Oracle XE on Ubuntu.  It can be found here.

Update: If you want to skip the background and read about the implementation, click here.

What we need is speed!  Speed is what we need!

How do you choose among the three stacks?  It depends upon your requirements.  I like all three.  Let’s look at these one by one.  The simplest stack to install, configure, develop, maintain is Java/Ubuntu/Tomcat/MySQL.  If you’re a novice, this is the way to go.  Moreover, there are trends in Java development that promotes speed and agility with light weight frameworks.  A lot of small to mid sized projects don’t use EJB’s.  They don’t need high availability or clustering.  While LAMP is a great solution for these requirements, development managers want the option of Java and all the great frameworks that come with it along with its inherent Object Oriented-ness.  Furthermore, as projects get bigger, organizations have the ability to start small (prototyping?) and advance to large implementations using proprietary application servers and/or databases.

The start up time and time to develop on a Tomcat/MySQL stack gives organizations this flexibility, while retaining the ability to use heavier frameworks down the road.  This choice is easy the smaller the project you have along with the more junior you are in the Java tech space.  So what happens when you want to use EJB’s or more advanced/supported application servers?

Simulating a Mid-Sized Project

Oracle is a robust database.  It’s used by big government, corporations of all sizes.  They have a virtual monopoly in such industries as banks in certain regions, manufacturing, finances, and even cities.  Their dba’s are among the highest paid and the Oracle implementations can be up in the tens of millions.  With mysql and postgress nipping at Oracle’s heels, Oracle’s database is available for free-as-in-beer download with restrictions.  The Express Edition is only available for 32 bit downloads and the environment as well.  That means that the RAM utilization can not be greater than 2 Gigs.  The data itself is less than 4 Gigs (features are also limited), while MySQL does not have these requirements.

With the acquisition of Sun Microsystems, Oracle has access to Sun’s JDK.  Oracle has also aquired Weblogic, so the inherent application for a true Java/Oracle stack would be Java (Sun’s version), Weblogic, Oracle XE (or non free variants) and Open Solaris, while using Oracle’s JDeveloper as an IDE.  In the future, I may release how to implement a free-as-in-beer blog for a full development stack using the Oracle technologies which were just mentioned.

For this particular blog, I will not focus on a full Oracle stack, but a stack that only uses it’s “free” database, Oracle Express Edition.  The benefit is the exposure to a highly marketable, highly used, industry leader in database management systems while remaining focused on Java development on the web.  This simulates most midsized environments.  While a lot of organizations use Oracle as their database, they don’t often use any of the other technologies that Oracle has acquired (that may change in the future, especially if Oracle abandons JDeveloper and either acquire IntelliJ or base the next generation of JDeveloper on Eclipse, which could be a conflict of interest or philosophy, read below).

A Balanced Approach

The balanced approach is using JBoss with MySQL.  It’s easy to set up and easy to develop.  The documentation available (for free) is incredible and the quality of the documentation is equally as good.  Moreover, I don’t like writing queries using ansii notation but MySQL allows you to write queries in near-Oracle like syntax.  If you stick to generic best practices for Java web development, porting to Weblogic or WebSphere can be easy.  However, it is likely that it’s easier said than done.  Typically, the easiness depends upon how early you it in the project, how generically you write your code (using interface, generic integration points, generic services), not using proprietary libraries (opt for third party libraries for your frameworks and ORM’s) and any support contracts involving migrational implementations.

After reading this entry, you should be aware of the ramifications of which environment you want to choose.  As I create more entries, I will update this blog to reflect other stacks I’m working on.

References:

Notes:

The only time I recommend implementing a full Oracle Web Stack (Sun’s Java/Weblogic/Oracle XE/Open Solaris) is when the requirements warrant it.  I’ve worked in an Oracle exclusive environment, and I love the technology, but the learning curve to develop in such an environment is too steep for most instances.  However, I do have an Oracle XE instance lying around for my mini projects that keep me “sharp” on the technology.

One thing I never like doing in Oracle environments is the IDE.  I’ve abandoned JDeveloper and set up Eclipse on my spare time and it payed off in dividends.  I did this with the backing of management as I don’t like acting in “cowboy” ways of development.  Abandoning JDeveloper for Eclipse is an easy sell to management any way, especially if done early on in the project.  I hope Oracle does find some way to re-implement JDeveloper, by either acquiring IntelliJ, or basing it on Eclipse without alienating the IBM/open source community.

Java/Ubuntu/Tomcat/MySQL: Just as Free but Faster

This is the sequel to my previous blog, regarding a Java/Ubuntu/JBoss/MySQL stack.  There are various reasons to choose one or the other application server.  Typically, tomcat (version 5/6) is the lighter weight servlet container and not technically and application server (no EJB’s, MDB’s, out of the box high availability, etc).  While JBoss is a full J2EE implementation and a true application server.  Resource requirements for tomcat is also smaller than JBoss.  Infact, tomcat’s resource requirements are so low, I can’t easily find what they are.  I remember using it on single core, P4′s with 512 megs of RAM and still had enough left over for a small IDE.

Another cool thing about a Java/Ubuntu/Tomcat/MySQL stack is that you can install all of it (including Eclipse, if you wanted) with a single command line.  This is the foundation of this blog.  The PHP world has the LAMP stack (with phpMyAdmin and BlueFish IDE) which can be installed, configured and up and running in half an hour.  Now, us Java folks have the same.

Background:

My favorite configuration for this stack is the free-as-in-speech strategy.  Normally, I like to use Sun’s JDK, but since Tomcat is free-as-in-speech, as well as MySQL, why not follow suit?

Ingredients:

  • Dual core processor, I like AMD’s but Intels work just as well
  • 512 MB RAM, but 1 Gig is better, especially with mysql installed on the same box
  • Ubuntu Server Edition, 9.04 Jaunty
  • Total time: 30 min

Installation:

In the command line, type:

  • sudo apt-get install openjdk-6-jdk openjdk-6-jre tomcat6 tomcat6-admin tomcat6-common mysql-server-5.0 mysql-client-5.0

My internet connection is relatively quick, so this took about 5 min to download and about 5 min to install.

Verification:

  • VERIFY MYSQL: Your mysql installation will ask you for a password for root.  Provide one and remember it.
  • VERIFY JAVA: In the command line, type java -version or javac -version, you should get a message that tells you which jdk you are using (openJDK) and which version (1.6)
  • VERIFY TOMCAT: pull up the browser, and type: http://whatever_the_host_is:8080   You should get a “It works!” screen followed by location of your tomcat docs, examples and admin, if you haven’t installed them already.

The verification process should take about 5-10 minutes, provided everything goes well.  If the above did not work, then you did something wrong.

Configure mysql:

You’ll want to allow your client machines to access your mysql database.  Type the following:

  • mysql -u root -p
  • then type your root password you provided above, then type:
  • GRANT ALL PRIVILEGES ON *.* TO ‘your_username’@’*’ IDENTIFIED BY ‘whatever_your_password_is’ with grant option;

The GRANT command will allow your clients to access the database.  If you do not do this, then you can only access the database locally or at the local host.  This took me about 5 mins.

Tomcat Notes:

  • RESTART TOMCAT: sudo /etc/init.d/tomcat6 restart
  • /var/lib/tomcat6/webapps/ROOT/index.html   is the default tomcat homepage

There you have it.  Now you can write JSP’s and Servlets.  Unfortunately, doing so it out of scope.  Stay tuned for Hello World JSP and Servlet tutorials.  Meanwhile, read up on the apache tomcat and sun tutorials.

References:

Side Notes:

You’ll probably want an IDE.  The best free-as-in-speech IDE is Eclipse.  You can install it via apt or synaptic, but it may not include extensions for J2EE (min JSP’s and Servlets).  Download it here.

Firefox Tip #4: Linux and Silverlight

Problem: You want to watch Silverlight based vids on Ubuntu, but Microsoft does not support Silverlight on Linux.

Solution: Install moonlight plugin for firefox in Linux.

There are a couple of practical uses for this.  For instance, some facebook applications are based on Silverlight.  Unfortunately, Netflix still restricts viewing based on OS, but there are rumors that Moonlight 2.0 and Ubuntu Jaunty will be supported by Netflix in the future.  If so, that’s cool.

Meanwhile, there’s only one real work around the Netflix issue.  Stay tuned for that tip.

References:

  • http://go-mono.com/moonlight-beta/

Follow

Get every new post delivered to your Inbox.