Project Euler Problem #112

September 5, 2010

Read the details of the problem here

Summary

Investigating the density of “bouncy” numbers.

Solution

The problem reads as being relatively straightforward and fairly non-mathematical in nature (though I can see that it might have to become a statistical problem on a larger scale) so, before I tried anything too clever I went for a simple brute force approach. I just looked to see if the digits of the number were already sorted in either ascending or descending order.

def (answer, b) = [ 100, 0 ]

while (true) {
  def s = answer.toString()
  def sorted = (s as List).sort().join()
  if ((s != sorted) && (s != sorted.reverse())) b++
  if (answer * 0.99 == b) break
  answer++
}

This runs in 13.24 seconds and so just sneaks in under the wire to satisfies my success conditions!

This did seem a little slow though and replacing lines 4-6 in the solution above with a call to the method below brought the runtime down to 10.59 seconds.

def isBouncy(n) {
  def s = n.toString()
  def direction = 0
  def len = s.length()
  for (i in 1..<len) {
    if (direction == 1 && (s[i] < s[i-1])) return true
    if (direction == -1 && (s[i] > s[i-1])) return true
    if (direction == 0) {
      if (s[i] > s[i-1]) {
        direction = 1
      }
      else if (s[i] < s[i-1]) {
        direction = -1
      }
    }
  }
  return false
}
 

Is the added complexity worth that reduction of 20%? In this case, probably not!

Conclusion

Groovy made this a nice, terse solution. Performance wasn’t excellent but the solution was quick to write and easy to understand when reading it back.

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: