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.

Comments

[der_flo]

My quick and ultra dirty solution gives me 15 solutions.
http://gist.github.com/599667

[noelrap]

Pretty sure your solution misses things. For one thing, there is no limit on the sequence length beyond the other restrictions

[Pete]

http://gist.github.com/600039

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

What's your enumerations idea?

[Pete]

Slightly longer, but neater and more efficient version:

http://gist.github.com/600069

[noelrap]

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.

[Prakash Murthy]

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:

http://gist.github.com/600173

[Pete]

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]

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.