Euler 78

Finished Euler 78. My solution is here.

The problem dealt with partitioning: how many distinguishable ways can you make collections of indistinguishable objects. My initial thoughts on the solution revolved around some notion of permutations of partitions, and it was totally wrong. As it turns out, there are a number of recursive definitions that allow you to calculate partition counts.

I picked one that seemed tractable and easily programmable, and it worked. Using my initial implementation, however, yielded the result only after an hour or two of computation; this is always a sign that you’ve screwed something up on an Euler problem.

A little examination showed that I was doing a lot of unnecessary recursive computation that could be short circuited. I would have felt smarter if I had noticed this before I submitted my answer, but, in any event, I got the answer right on my first submission. Adding the short-circuiting brought the runtime down to around a minute…much better.

  1. Leave a comment

Leave a Reply

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

You are commenting using your 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: