Project Euler Problem #68

May 21, 2010

Read the details of the problem here

Summary

What is the maximum 16-digit string for a “magic” 5-gon ring?

Solution

I really didn’t think I’d be able to do this in Groovy and get it to run within my 15 second limit, at least not without some fiddly recursive solution. However, I used Groovy 1.7.2 which has been out for a while now and offers somewhat improved performance and a few extra collection operators. Notable in this solution is the eachPermutation() method which will iterate over a collection and call the closure for each permutation of elements.

The solution itself is quite straightforward and obvious. I don’t want to have duplicated (i.e. rotational symmetric) results so I enforce an ordering of numeral around the outer ring, this means that the first element can’t be greater than 6 otherwise there would be insufficient numbers available. I then enforce the ordering. The next step is to make sure that the number ten doesn’t appear in the inner ring otherwise it would appear twice in the concatenation and make it 17-digits. After getting through those basic guard conditions it’s then a case of making sure the various legs all add to the same total before assembling the string & checking to see if a new maximum has been found.

def SEQ = [ 0, 6, 7, 1, 7, 8, 2, 8, 9, 3, 9, 5, 4, 5, 6 ]
def answer = ""

(1..10).eachPermutation { nums ->

  if (nums[0] > 6) return

  for (i in 1..<5) {
    if (nums[0] > nums[i]) return
  }

  for (i in 5..<10) {
    if (nums[i] == 10) return
  }
    
  def sum = nums[0] + nums[6] + nums[7]

  def p = 3
  while (p < 15) {
    if (sum != nums[SEQ[p]] + nums[SEQ[p+1]] + nums[SEQ[p+2]]) return
    p += 3
  }

  def sb = new StringBuilder()
  for (i in 0..<15) {
    sb.append(nums[SEQ[i]])
  }

  answer = [ sb.toString(), answer ].max()
}

It runs in 8.3 seconds. Not fast, but within the 15s target so I’ll leave it there! Improvement is left, as they say, as an exercise for the reader…

Update: Having gained access to the forum, it seems that there is an additional logical tweak, actually a slight refinement to the commencing number that can be used. If I make that minor change the run time drops to 4.3 seconds. Even better!

Conclusion

I thought that Groovy allowed for quite a quick time-to-solution for this problem. Although not the top in performance it wasn’t bad considering this is a brute-force approach. The code is quite clear in intent without a lot of supporting noise.

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: