The next problem I attempted after solving Tic-Tac-Toe-Tomek was Fair and Square. A number is determined to be fair and square if it is both a palindrome and has an integral square root. 1, 4, 9, and 121 are fair and square but 676 is not. The submission of the small dataset officially qualified me for Round 1.

There were three datasets: a small and two large. I was able to quickly attack the small with the following snippet of code. Because the range was fairly small (1 >= B >= 1000), it's sufficient to use a brute force solution. You might have noticed that I used BigInteger instead of Integer in the code. At first glance, this seems like overkill. You can certainly do the same thing using ints and Math.pow or Math.sqrt. The problem with that approach is that both of them require doubles so you would have to cast to a double and back. The power convenience function returns a Number object there's no casting needed. After getting the square root, I checked if both were palindromes.

for (i in 1..n) {
  int start = scanner.nextInt()
  int end = scanner.nextInt()
  int count = 0
  for (j in start..end) {
    def x = new BigInteger(""+j)
    // small only
    def sq = x.power(0.5)
    def isSq = sq.toString().indexOf('.')
    if (isSq == -1) {
        // is square
        if (x.toString().equals(x.toString().reverse()) && sq.toString().equals(sq.toString().reverse())) {
            println x
            count++
        }
    }
  }

  text += "Case #${i}: ${count}\n"
}

The large datasets were a special case in that you were only allowed to attempt them once. Rather naively, I tried the above code against the smaller of the two large datasets (1 >= B >= 10^14) and it timed out. I wasn't able to get something working for the largest dataset (1 >= B >= 10^100). The key to the larger datasets seemed to be either pre-generating the list of fair and squares either by running a brute force algorithm before retrieving the large dataset or by observing the patterns and generating them on the fly.

Further Optimizations

Returning back to the knowledge that BigInteger.power returns a Number, for the small dataset only, I could have tested if the square root was an Integer. If that test fails, there's no reason to do 4 costly String initializations when that state isn't possible. This strategy would fair better than the above code, which would start to break once the JVM switched to exponential notation.

Almost two weeks ago, I participated in the Qualification Round of the Google Code Jam. The Google Code Jam is a competitive algorithm programming competition with multiple online rounds before the on-site finals at a Google campus somewhere in the world. This year's finals are in London.

For the Qualification Round, contestants have to reach a point threshold during a 25h period. Because only points matter at this phase, one can attempt all the problems without worry of penalties. I solved small and/or large datasets for three out of four problems securing a spot in Round 1. In this and the next couple posts, I'm going to go through my solutions. The stuff for file input and ouput and counting the number of test cases is pretty mundane so I'll be leaving those parts out.

The first problem I attempted was titled Tic-Tac-Toe-Tomek, a modified take on Tic-Tac-Toe. The task was to take a 4x4 grid and determine the game state(X won, O won, draw, or game not finished). A player could win with 3 of their symbols and a 'T' or 4 of their symbols. I used Groovy, a dynamic language on the JVM, for this solution.

Tic-Tac-Toe-Tomek Solution

I began with a small snippet of code to read in the lines of the grid. These are four of the ten variations we need to check for wins. The last line calls checkWinner which does the real work.

def a,b,c,d

a = lines.remove(0)
b = lines.remove(0)
c = lines.remove(0)
d = lines.remove(0)

text += "Case #${i}: ${checkWinner(a,b,c,d)}\n"

Upon receiving the input strings, I created the other test cases benefitting from the fact that strings in Groovy can use array indexes instead of the longer to type charAt.

def checkWinner = {a,b,c,d ->
  def winner = ""
  // down
  def g = a[0]+b[0]+c[0]+d[0]
  def h = a[1]+b[1]+c[1]+d[1]
  def m = a[2]+b[2]+c[2]+d[2]
  def n = a[3]+b[3]+c[3]+d[3]
  //diag
  def o = a[0]+b[1]+c[2]+d[3]
  def p = a[3]+b[2]+c[1]+d[0]
  [a,b,c,d,g,h,m,n,o,p].each {
    def x = []
    x.addAll(it.toCharArray())
    x.sort()
    if (x.join('').equals('TXXX') || x.join('').equals('OOOT') || x.join('').equals('XXXX') || x.join('').equals('OOOO')) {
        x = x - 'T'
        winner = x[0].toString() +" won"
    } else {
        def xx = a + b + c + d
        if (xx.indexOf('.') == -1 && !winner.equals("X won") && !winner.equals("O won"))
            winner = "Draw"
        else if (winner == "")
            winner = "Game has not completed"
    }
  }
  return winner
}

As opposed to having a bunch of if-statements to check every permutation of O's, X's, and T's, I instead sorted the strings to get them into one of a few known states. The String class doesn't give you an easy way to sort strings so you have to create an ArrayList and then add the output of toCharArray to the collection. You can get a string back out by calling join on the collection. Trying to do the same in Java would be much more verbose.

After getting the resulting sorted strings, I checked them against the four base states for a win. If a winner is not declared and there are empty slots, the game isn't done. If there are no empty slots, it's a draw.

Further Optimizations

Having some time away from the problem, if I were to do it again, I might attack it in a slightly different way. What if the sorting wasn't needed? Groovy allows us to call unique on a collection to get the unique values. If you had a line represented by ['X','X','X','X'] or ['X','X','T','X'], calling unique would return ['X'] or ['X','T'], both indicating a win. The set ['.', 'O', 'X'] would disqualify a win.

Conclusion

Tic-Tac-Toe-Tomek was a fun first problem and I was able solve both the small and large datasets receiving 30 of the 35 points needed to advance to the next round.

The ideas get pitched and people start to pick teams. On a good day, you end up with a nice mix of designers and developers. You might have the pedigree but a less experienced but nimble team can upset you. The starter gun is fired and work begins.

Your fully realized team is slogging through the mud pits, pulling the stragglers along. You can't let the team slow to the slowest person's pace but have to find out what they can do and then push for 10%-20% more again and again until they are keeping pace. You simply can't do that in a gym. You know what most of the apparatus will be upon entry. With a hackathon, you only have a rough lay of the land and don't know the curve balls the organizers will throw at you.

You can go to the gym alone and make decent progress if you work at it. But not so much at a hackathon. At almost every hackathon I've attended, there has inevitably been the single man team who pitched an idea that was far out there and couldn't make it compelling or compromise enough to attract people. And instead of joining another team, he pridefully goes it alone or quits. That's not to say that one can't do it but scaling a 15 ft wall is a whole lot easier with someone to give you a boost.

For me, the perfect hackathon has a decent but not overwhelming ratio of novices to experienced people, some curveballs, a ban on bringing pre-existing projects, are not prone to Pokémon behavior(gotta use all these APIs from the sponsors), and low attribution rates(helpful if you can't leave like in the case of StartupBus).

Hat tip to Hackathons are like gyms.

Photo used in accordance with Creative Commons 2.0 license: http://www.flickr.com/photos/dvids/8482383303/

In addition to Devoxx France (Paris), I will be presenting at Devoxx UK (London) and CodeMotion Italy (Rome) this month on Three.js and WebGL. Come check out my talks.

Informit.com just published an introductory article I wrote on creating mobile applications for Firefox OS.

If you already know how to package Chrome Web Apps, you're most of the way there.