Project Euler Problem #55

May 20, 2010

Read the details of the problem here

Summary

How many Lychrel numbers are there below ten-thousand?

Solution

Very straightforward. I even used a couple of BigInteger metaClass extensions to make it more readable, well, perhaps more readable! The algorithm was just a simple implementation of the details in the question.

BigInteger.metaClass.isPalindrome() { ->
  def s = delegate.toString()
  s == s.reverse()
}

BigInteger.metaClass.reverse() { ->
  delegate.toString().reverse().toBigInteger()
}

def answer = 0

for (i in 1G..<10000G) {
  def n = i
  answer++
  for (c in 0..50) {
    n += n.reverse()
    if (n.isPalindrome()) {
      answer--
      break
    }
  }
}

Not much else to say on this, it just does what it says on the tin. It runs in 0.39 seconds.

It’s possible to do this as a one-liner with Groovy listops but it’s not as clear as to what’s going on – or maybe it is?

BigInteger.metaClass.isPalindrome() { ->
  def s = delegate.toString()
  s == s.reverse()
}

BigInteger.metaClass.reverse() { ->
  delegate.toString().reverse().toBigInteger()
}

def answer = 
    (1G..<10000G).findAll { i ->
            !(0..50).any {  (i += i.reverse()).isPalindrome() }
    }.size()

Run time is 0.50 seconds, so not too bad considering but around 30% up from the iterative solution.

Conclusion

Groovy was fine to do this in. The metaClass extensions made the syntax a little more natural (maybe) and the rest was reasonably terse. No real performance concerns for the scale of the problem.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: