Rails Test Prescriptions Blog

Keeping Your Application Healthy Since 2008

A Quick Ruby Kata

This is, I have on good authority, actual homework from a 4th grade gifted program, paraphrased to make it more code-kata like.

Find all the unique sequences of digits, like [1, 1, 2, 3, 8] that have the following properties:

  • Each element of the sequence is a digit between 1 and 9
  • The digits add to 15
  • There is at least digit that appears exactly twice
  • No digit appears more than twice
  • Order is irrelevant [1, 1, 2, 3, 8] and [1, 3, 2, 1, 8] are the same sequence and only count once.

I believe the original problem did specify that there are 38 sequences that match.

I’m interested in seeing solutions to this if anybody goes ahead and does it. I’m pretty sure there’s an elegant solution using Ruby 1.9 enumerations, but that’s not the way I went on my first try.

Advertisements

8 responses to “A Quick Ruby Kata

  1. der_flo September 27, 2010 at 2:35 pm

    My quick and ultra dirty solution gives me 15 solutions.

  2. Pete September 27, 2010 at 6:14 pm

    Just a simple recursive solution. It spits out the required 38 answers in a reasonably efficient way.

    What’s your enumerations idea?

    • noelrap September 27, 2010 at 6:56 pm

      Very clever. I’m always impressed by people who can keep a recursive solution in their head. In production code, I’d prefer to see the constraints expressed more explicitly, but this is a cool solution.

      My Ruby 1.9 solution would have the sequence be a Ruby enumeration, so that the main driver would just be a select statement. But I haven’t done it yet.

      • Pete September 27, 2010 at 10:47 pm

        Yep, know what you mean about wanting the constraints more explicit. Basically you want to make the code look like the problem, right?

        my_magic_set.select do |digits|
        digits.sum == 15 &&
        a_digit_appears_twice?(digits) &&
        no_digit_appears_more_than_twice?(digits)
        end

        Problem is, what’s my_magic_set? The problem says “all the unique sequences of digits”, but that’s an infinite set, which is a bit tricky to iterate over. 🙂

        So I think you’d have to pick one of the constraints to narrow the set down to something finite to iterate over, and then you could use select to apply the remaining constraints.

        Thoughts?

      • noelrap September 27, 2010 at 10:55 pm

        Yes, I picked a constraint to make the magic set not infinite. Though, I think my initial solution isn’t as purely elegant as the recursive version.

  3. Pete September 27, 2010 at 6:27 pm

    Slightly longer, but neater and more efficient version:

  4. Prakash Murthy September 27, 2010 at 7:36 pm

    This kata is very similar to Problem number 76 on Project Euler – http://projecteuler.net/index.php?section=problems&id=76

    Modified my brute force solution to that problem to get the required 38 combinations for the kata:

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: