James Horsley

Project Euler - Problem 19 - JodaTime Rocks

2008-01-14T21:11:00.000-08:00

Problem 19

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

This really feels like cheating, but the very simplest way I immediately thought to solve this was using Joda Time.

Joda Time is a wonderfully written Java library, that replaces the need for the both inept and ugly mess that is java.util.Date and java.util.Calendar. Joda Time is so good that it is the basis on which the new Java 7 Date and Time API will be built (see here).

Here's my solution in the typically oh so long winded Java:

DateTime date = new DateTime(1901, 1, 1, 0, 0, 0, 0);
DateTime end = new DateTime(2000, 12, 30, 0, 0, 0, 0);
   
int numberOfSundays = 0;
   
while (date.isBefore(end)) {
  if (date.getDayOfWeek() == DateTimeConstants.SUNDAY) {
      numberOfSundays++;
  }
  date = date.plusMonths(1);
}

Short, simple, expressive. Thanks Joda Time.

Liquibase

2008-01-02T03:20:00.000-08:00

Following from my previous post, I've continued to try out Liquibase, a database refactoring/migration tool.

I'm becoming increasingly impressed with Liquibase. Not only is the framework very well documented (including demo videos) but I'm increasingly seeing the benefits it provides.

At work we're pretty much an "always branch" team. We work at the mercy of the business who often will push deadlines on certain parts of a release back, or try and bring them forward. A consequence of that is the high SCM maintenance overhead, which is done by me. We only rebase (merge out from trunk) when trunk is updated, which is only done after a release. This means that two branches can end up fairly incompatible fairly quickly.

Rather than turn this into a post on SCM, I'll refocus and say that database changes from one branch are not pushed to other active development branches until that branch is released. Our big problem is that since there is not formalized database migration process, the released branch's database changes are typically not applied to the test server for the branch still in development. The development branches only finally work with the previous releases database changes when the dev databases are refreshed from production (obviously containing the previous releases changes.) This is further compounded by our lack of across the board automated testing, and that the production refresh typically happens when a branch is moved to systems or user testing (not when you want to discover a tonne of error messages.)

If we were using Liquibase when the released branches changes were merged to the dev branches via trunk, the changes would automatically be applied by the Liquibase framework when the dev branch was built/deployed (depending on the build configuration.) This is because Liquibase keeps track of the change sets it applies through a unique id, author, file combination, so only the new changes would be applied. Ignoring the SCM practice being somewhat of the root cause here, at least Liquibase reduces the manual overhead of keeping track of the changes and applying them.

It's all quite impressive, but I still feel like I've barely scratched the surface.

Project Euler

2007-12-28T03:22:00.000-08:00

I haven't gone to the site in a while with all the other distractions going on at the moment (largely the new baby.) However, I'd been chatting with Aaron Feng, a friend of mine, who I'd turned onto it a while back and he had now gotten into it. Being the infectious evil thing that Project Euler is, talking with Aaron's got me back onto it. I still have next to no time to mess with it, but that's ok all I need is a few minutes here and there anyway.

I did problems 11 and 15 this morning. I had been trying to think of a clever way to do problem 11, but could only come up with a brute force approach



require "matrix"

matrix_str = <<MATRIX_STR
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
MATRIX_STR

rows = matrix_str.split("\n")
rows = rows.inject([]) { |rows,row| rows << row.split.inject([]) { |num_row, str| num_row << str.to_i  } }
matrix = Matrix.rows(rows)  


def sum_up(matrix, x, y)
  return 0 if y < 3
  matrix[x,y] * matrix[x,y-1] * matrix[x,y-2] + matrix[x,y-3]
end

def sum_down(matrix, x, y)
  col_size_adj_for_zero_start = matrix.column_size - 1
  return 0 if y > (col_size_adj_for_zero_start - 3)
  matrix[x,y] * matrix[x,y+1] * matrix[x,y+2] + matrix[x,y+3]
end

def sum_right(matrix, x, y)
  row_size_adj_for_zero_start = matrix.row_size - 1
  return 0 if x > (row_size_adj_for_zero_start - 3)
  matrix[x,y] * matrix[x+1,y] * matrix[x+2,y] + matrix[x+3,y]
end

def sum_left(matrix, x, y)
  return 0 if x < 3
  matrix[x,y] * matrix[x-1,y] * matrix[x-2,y] + matrix[x-3,y]
end

def sum_diag_north_west(matrix, x, y)
  return 0 if x < 3 || y < 3
  matrix[x,y] * matrix[x-1,y-1] * matrix[x-2, y-2] * matrix[x-3, y-3]
end

def sum_diag_north_east(matrix, x, y)
  col_size_adj_for_zero_start = matrix.column_size - 1
  return 0 if x < 3 || y > (col_size_adj_for_zero_start - 3)
  matrix[x,y] * matrix[x-1,y+1] * matrix[x-2, y+2] * matrix[x-3, y+3]
end

def sum_diag_south_east(matrix, x, y)
  col_size_adj_for_zero_start = matrix.column_size - 1
  row_size_adj_for_zero_start = matrix.row_size - 1
  return 0 if x > (row_size_adj_for_zero_start - 3) || y > (col_size_adj_for_zero_start - 3)
  matrix[x,y] * matrix[x+1,y+1] * matrix[x+2, y+2] * matrix[x+3, y+3]
end

def sum_diag_south_west(matrix, x, y)
  row_size_adj_for_zero_start = matrix.row_size - 1
  return 0 if x > (row_size_adj_for_zero_start - 3) || y < 3
  matrix[x,y] * matrix[x+1,y-1] * matrix[x+2, y-2] * matrix[x+3, y-3]
end

max = 0

1.upto(matrix.row_size-1) do |x|
  1.upto(matrix.column_size-1) do |y|
    temp = sum_up(matrix, x, y)
    max = temp if (max < temp)
    
    temp = sum_down(matrix, x, y)
    max = temp if (max < temp)
    
    temp = sum_left(matrix, x, y)
    max = temp if (max < temp)
    
    temp = sum_right(matrix, x, y)
    max = temp if (max < temp)
    
    temp = sum_diag_north_west(matrix, x, y)
    max = temp if (max < temp)
    
    temp = sum_diag_north_east(matrix, x, y)
    max = temp if (max < temp)
    
    temp = sum_diag_south_east(matrix, x, y)
    max = temp if (max < temp)
    
    temp = sum_diag_south_west(matrix, x, y)
    max = temp if (max < temp)
  end
end

puts "max=#{max}"

Now don't get me wrong, this is terrible Ruby code, but I had been more focussed on trying to work out a good mathematical way and ended up with this. I'll probably rewrite it to make better use of Ruby over the weekend, also maybe port it to scala?

Problem 15 was far more fruitful on the math approach. I'm glad that when I first saw this problem my initial reaction wasn't to think algorithmically, and rather mathematically. Aaron and I had talked about that recently, and he was right that as a programmer one tends to think of solutions to these problems in code. So this was somewhat of a litmus test to see if my maths and physics instructors brainwashing was still in there somewhere.

The problem is as follows:

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 2020 grid?

My gut reaction was that this could be solved using permutations. I'll be honest, it did take me getting a pencil and paper plus a few references to my discrete maths book; but, happily I sorted out that the problem was just a case of permutations of indistinguishable objects.

My thinking was as follows, if I use the top-left corner as the origin and have the x-axis extend to the right and the y-axis extend down,since there is no backtracking, the path will consist of 10 moves in the positive x direction and 10 moves in the positive y direction. I tested my idea with the 2x2 grid, which gives the following six paths xxyy, xyxy, xyyx, yyxx, yxyx, yxxy. This essentially is just taking xxyy and seeing how many permutations there are of it, scaled up of course we're just looking for permutations of 20 x's and 20 y's. The simple formula for this is

n! / (n1! n2!)

where n is the total number of objects, n1 is the number of objects type 1 (x) and n2 is the number of objects of type 2 (y).

Database Refactoring with Liquibase

2007-12-26T22:12:00.000-08:00

I currently work with a very database-centric team. While this has allowed me to work with some great Oracle DBA's and developers. That being said, when release time comes changes to the database are fairly ad-hoc. There is no standard way in which additions, removals, or updates are made; everything is performed by sql scripts each written by the developer. We do have a code review process, but with there being no strict guides to work within everything ends up being somewhat of a hodgepodge.

Having worked with Rails for a little while also now, I was wondering if there were any equivalent database migration tools for Java. My search has lead me to Liquibase. Liquibase provides an entire database refactoring framework through some simple xml change set files. The change sets can be applied through command line, ant, maven, spring, and some other methods. It initially seems very promising, in particular the automatic rollback generation, and the simple fact that it provides a consistent way to migrate a database.

I've only just got started with it but am hoping it continues to live up to the initial promise.

Project Euler

2007-02-17T21:15:00.000-08:00

I've done a little with a math competition site called projecteuler.net. I use the term competition very loosely. It's more that you just do problems at your leisure, and the site just happens to keep a leader board. I highly recommend the site, but with this caveat, it's about as addictive as crack; I know that sounds ridiculous, but consider yourself warned!

I've been using the project euler problems as a good way to familiarize myself with Ruby and it definitely seems to have been success in that regard. Although the problems are small enough in most cases that you're not building anything sizable, it gets you familiar with the libraries and gives the opportunity to think ruby thoughts where possible. I haven't run into a performance issue doing the problems in ruby yet. I'm sure I'll run into them at some point, 'tis the nature of the beast, but often that just means there's a better way to approach a problem.

I believe I've broken the top 900 (I guess that's a woohoo moment? ... right?) but if I actually get more than an hour or two to spend on it a week, hopefully I'll manage to finish more problems.

Inalienable Rights

2006-05-25T06:49:00.000-07:00

Writing C/C++ with ACE

2006-05-18T21:40:00.000-07:00

What is it about writing C/C++ code that turns us in cryptographers? I know that the language is inherently cryptic with its myriad of possible ways to shoot yourself in the foot, but shouldn't that make us want to write cleaner code? In an effort to break the cycle I've picked up a highly recommended book by Scott Meyers called "Effective C++". I love "Effective Java" by Joshua Bloch, and I'm fairly certain that Bloch got the idea for his book directly from Meyers's book. Looking forward to devouring its 55 nuggets of wisdom.

I recently have come into contact with the Adaptive Communication Environment (ACE) toolkit for C++. My first thought was "wow! this is incredible", followed shortly by "why on earth haven't I ever heard of this before?!?!" I felt a little cheated for it never to have been mentioned in any classes I took, particularly considering how long it's been around. I'm on a very steep learning curve with how to use it and will post in more depth when I'm further up that curve. But the initial report is still "wow".

Posting from Seattle

2006-03-26T21:27:00.001-08:00

Well the conference is over and I'm posting from Seattle airport. My flight has been delayed a little and I thought this a good time to try and summarize the trip a little.

I firstly want to apologies for my previous post "Good Morning Seattle", I was deliriously tired while writing that. I had thought about going back and changing it, but it's a little humorous to go back and read so I've left it up.

The trip has been a huge mixture of success and failure. Firstly, our presentation went wonderfully. I really feel that we hit the key points of Shoechicken to great effect, and skipped the uninteresting details. There were so many questions at the end that the session chair had to cut many off due to a lack of time. People seemed genuinely interested, now we just need to get something out there for people to download,

That's the up side of the conference, the down side is that the conference wasn't that great to say the least. There were at most 50-60 people and may of those didn't stay the whole time. Many of the talks were either barely intelligible, or downright awful. There were a few notable exceptions, but I have to say that I will certainly not be coming back next year.

On the up side of things, Seattle has been wonderful. It's reminded me of home a great deal. I got to see the space needle, pike market, the first starbucks, underground Seattle, and many more things. I cannot believe how many coffee shops there are here. It's almost unfathomable that there are that many, particularly the number of starbucks. Not that I'm complaining of course, as a coffee addict it's a big selling point for me. I really liked being able to walk from place to place. Living in Pensacola has pretty much abolished any daily walking I do; outside of downtown people just don't walk places. We've walked well in excess of 10 miles while being here and it's been lovely. The only bad comments I have about Seattle are the number of homeless, and the lack of police presence.

Overall I've enjoyed my trip. In a way more importantly I feel like it's been a huge learning experience. I have taken a great deal from presenting at this conference. Some of which is what to do and some being what not to do. The other side of it being general travel experience. I hadn't realized how inflexible travel packages from places like expedia are. We also ended up with a rental car that we barely used due to the convenience of walking everywhere here.

Well everyone, this is it from Seattle for me, ta ta for now.

Good Morning Seattle

2006-03-20T22:44:00.000-08:00

Spent most of this evening working with Mike on our presentation for when we present our Shoechicken paper on Friday. It looks like we're going to have about 25 mins in total, but that will include setting up time and questions. We're aiming for the presentation to last 20 mins, perhaps with a few extra slides in there we can skip over if we're low on time. We're estimating that we'll need 23-24 slides; that gives us one per minute but with a few extra as backup incase we fly through them too quickly.

It turns out that we're not staying in the conference hotel. We are within walking distance though, and since UWF is picking up the tab I can't complain :)

What's the deal with St. Petersburg?

2006-03-18T05:40:00.002-08:00

While studying for a statistics test the other day, I came across an interesting statistical paradox (not of my own invention of course). The problem goes as follows. There's a game of chance that you have to pay a fixed amount to play. After paying your fixed amount, the person running the game, let's just call this the casino, flips a coin until the coin lands on tails (or heads, it doesn't really matter). When the coin lands on tails, the total number of coin tosses is used to determine your winnings of $2^n. E.g. if the coin was flipped the first time and it was heads, then heads on the second and third, but tails on the fourth toss then your winnings would be $2^4=$16.

All sounds good so far? Well here's where the funky part comes in. The probability of you winning $2^n is 1/(2^n). This means that when you calculate the expected value of the game, where the expected value tells you how much you are likely to win on average, the expected value is infinity!?! This can be seen as follows

# tosses (n)	Winnings	Probability	Expected Payoff
1	$2	1/2	$1
2	$4	1/4	$1
3	$8	1/8	$1
4	$16	1/16	$1
5	$32	1/32	$1
...	...	...	...
n	$2^n	1/(2^n)	$1

Now, if you consider that you could be lucky enough, or not, that the coin would keep coming up heads indefinitely you could win an indefinitely large sum of money. This means that to calculate the expected value of the game, we must sum the expected payoff from each possible outcome, namely sum(2^n * 1/(2^n)) where n=1,2,3,... As can be seen from the table this is sum(1) n=1,2,3,... which is infinity. This means that whatever fixed amount of money one has to pay to get in on this game, you should always do it.

Of course this isn't right, we know this intuitively as the odds on getting 5 heads in a row is pretty remote. There is a great website that simulates this game
http://www.mathematik.com/Petersburg/Petersburg.html

A few people have proposed solutions to the paradox. The first was Bernoulli who proposed that the value of money decreases logarithmically with how much you have. That the difference to between having one billion and two billion is realistically less than the difference between one billion and one million. This doesn't solve the problem however as the winnings can be altered to increase to cancel the logarithmic decrease in the value of money. The other proposed "solution" is that no casino has an infinite amount of money to give you, the game has a maximum winnings. Capping the winnings does fix the problem, but you almost get the sense that this is somehow cheating a little.

Here are some great links for a much more in depth (and prettier) analysis of the paradox:

http://plato.stanford.edu/entries/paradox-stpetersburg/

http://en.wikipedia.org/wiki/St._Petersburg_paradox

Appearances can be deceiving

2006-03-14T23:21:00.000-08:00

I was thinking about the NP problem of Satisfiability today. I remember my first instinct with the problem being that it would seem impossible for this problem to be in P. How on earth could you know whether any truth assignments would satisfy the boolean expression without trying them all? But I remember having similar thoughts about problems such as the subset sum problem; and although it's still a mystery as to whether it's in P, techniques such as dynamic programming bring it pretty close.

I guess what I'm trying to say is that I've typically been a P != NP guy, but for a brief moment today I crossed the divide. I really started to believe that maybe all we're missing is some simple trick that'll change everything. Now that yesterday has become its tomorrow, I'm beginning to come out of my stupor. However, the doubt appears to have been sowed and the romantic in me is kind of glad.

Murky waters

2006-03-12T19:26:00.000-08:00

I heard an interview with a Palestinian on the Bush administration's halting non-humanitarian aid pending further review. The Palestinian felt that the Bush administration was being hypocritical by encouraging democracy in the middle east, but then not liking its result. His comment kept me thinking most of the way into work, I'm really quite torn on the issue. I understand the guys stance to a degree. The west wants democracy, Palestine has democratic elections and then we refuse existing aid because we don't like who the Palestinians' picked as leader. However, this seems to be an oversimplification. Yes it is wonderful that Palestine had free and democratic elections, but isn't that the point? It's not as though the Bush administration made a shock move by stopping the aid, it's part of US law not to fund terrorist groups. The Palestinian people should have, and if they didn't could have, known this and factored it into their decision. This could be thought of as a form of bribing the voters, but if Hamas is who the Palestinians think will lead them to prosperity then they must factor in that Hamas will be doing it without much foreign aid.

I feel an analogy can be drawn with the private sector funding research projects. Company X can offer a great deal of money to anyone who wants to do research in a particular area. Researchers can either work in that area knowing they'll be well funded, or if it's not what they want to research then they accept the funding risk and/or try to find funding elsewhere.

If Hamas wants to not accept Israel then that's their choice. If the Palestinian people agree with Hamas, then that's their choice. But, they also have to accept that it doesn't fit with a typically accepted world view and work with what they have.

Falling in love

2006-03-11T22:51:00.000-08:00

Falling in Love

Well I've fallen in love again (no not with another woman, very much in love with my wife!), and JUnit is the object of my desire. I remember being skeptical about using unit testing on a project. I had all the typical concerns about how much it would slow me up and whether it would be worth all the extra time. Ladies and gentlemen, it's been worth every ounce of effort.

I got to a point in developing where I was sick and tired of buggy code. Tired of doing a demo and something breaking, or changing a seemingly innocent isolated piece of code and then finding out much later on that I'd broken some obscure feature. I don't consider myself a bad programmer in the sense of writing typically unstable code, but something had to change. Enter unit testing.

I've been using my Shoechicken project (http://www.shoechicken.com), as my first testbed for unit testing. I decided that if it worked well for Shochicken, I'd start looking into using it elsewhere. Well I have to say that Shoechicken has benefited wonderfully from our ever growing set of tests. Not only do I feel much more confident about code I write, but I feel more confident in refactoring and improving older code as the unit tests provide a good indication of whether all is well with the chicken. I do feel that the unit tests slowed me down, there's no real way that doing extra typing isn't going to. Where I feel I've actually saved time is in code maintenance and bug tracking.

Bottom line is that I recommend unit testing to anyone who's interested (and those who aren't.)

Busy busy busy

2006-01-29T23:06:00.000-08:00

Been a busy period for me at the moment. Working full-time, taking three classes, repairing the house, and other family duties certainly isn't leaving much time for play! Luckily the light at the end of the tunnel is shining regarding UWF; although I'm really quite enjoying this semester's classes.

I've been delving into "Artificial Intelligence: Structures and Strategies for Complex Problem Solving" by George Luger. I'd previously been using "Artificial Intelligence: A Modern Approach" by Norvig but thought I'd check out logger's take on things. In particular I'm going over the machine learning section for Shoechicken (http://www.shoechicken.com & http://shoechicken.blogspot.com), and have thus far come up with some great ideas from the text. I hadn't thought about using a genetic algorithm for Shoechicken, but the more I think about it the more I like it. This will become a big source of interest over the next week or so.

At work we've been working hard to get a stable release of MAST (http://mast.ihmc.us) out. We've just switched to using InstallAnywhere and I have to say that I am suitably impressed! It's allowed us to package the software in a very professional looking manner. We'd previously had problems with licensing and using other software; in particular MySQL. Since MySQL is under GPL, although MAST is free to download and use, it's not GPL so were having the user download and install MySQL for the MAST Server. I suddenly had a brainstorm a couple of weeks ago, can't believe I didn't think about it before to be honest, why not switch to another db server????? We only need a lightweight SQL database and all database traffic goes through a proxy. We have now switched MAST over to use Hsqldb (http://www.hsqldb.org) and can report that life is gooooooood. We now have everything we need packaged with the installation, so it's just a single download.

We've also been testing, testing, testing, which of course means debugging, debugging, debugging. I think that this is the most testing we've done of MAST all at once. Matteo and I really have brought the product a long way in the last two weeks. The installation procedure has become quite robust, and MAST itself is looking much more stable. Our target is to have a final release out on the web that's been tested by a few different people, so watch this space to find out when it's ready for download!

Starting on the rating agent and being under the weather

2006-01-21T19:58:00.000-08:00

Well, to start with I'm under the weather. Colds are bad! But, through the cold I've managed to be fairly productive for both Shoechicken and my Complexity class. I finished up some loose ends on the Bufunkalo, mostly in reference to the unit tests but there was a little refactoring too. I'm really looking forward to working on the rating agent. I spent such a long time researching how we're going to implement it that it's very exciting to finally delve into the code.

I think I'm going to call it an early night and try and get some rest so ta ta for now.