#!/usr/bin/env ruby
Inf = 1/0.0 # isn't it about time to add this to the core library?
class Integer
def smallest_integer(k)
[self, '1023456789'[0,k].to_i].max.upto(Inf) {|i|
break i if i.to_s.chars.to_a.uniq.length == k
}
end
end
So, how does this work?
Let's first remove the optimization:
class Integer
def smallest_integer(k)
upto(Inf) {|i|
break i if i.to_s.chars.to_a.uniq.length == k
}
end
end
Integer#upto is an enumerator that does just what you expect: starting at self, it yields every integer between self and its argument. So, 42.upto(47) will yield 42, 43, 44, 45, 46 and 47. In this case, we are asking it to yield every integer between our starting point and infinity. Which will obviously not work, which is why we use the break keyword to break out of the loop.
And we pass an argument like this: break i to get a meaningful return value for the block, which is then also going to be the return value for the upto method which in turn is the return value for our method.
And when do we break? We break if the current integer (i), when we convert it to a string (to_s) and split it into characters (chars) has the number of unique digits (uniq.length) that we are looking for (k).
The to_a in there is only needed, because chars does not actually return an array of characters, but an iterator for each character and uniq doesn't work with iterators (because uniq needs to look at every element and iterators can be infinite), so we need to convert to an array first.
Actually, after I went to sleep last night, I realized that I had commited the mortal sin of Ruby in that code snippet: not knowing the true power of Enumerable. I had forgotten about the find method, I didn't know that find also works with Enumerators and I didn't know that upto returns an Enumerator when you don't pass a block. So, this is much more readable, I think:
class Integer
def smallest_integer(k)
upto(Inf).find {|i| i.to_s.chars.to_a.uniq.count == k }
end
end
In this case, upto returns a lazy Enumerator, and find finds the first element for which the condition is true. (The condition is the same as before, except that yesterday I also forgot about count, which is just an alias for length, but makes the code flow a little better, when read out loud.)
Now, you can almost read that like an English sentence without even knowing Ruby, and will (sort of) make sense (which is how a well-written program should be):
When counting up to infinity, find a number for which the number of unique digits is k.
Okay, now let's add @Ofir's optimization back in: we take the string '1023456789', and starting from the beginning, we slice off k characters ([0,k]). Then we convert that to an integer (to_i) and look for the maximum of that and our original starting point (self):
[self, '1023456789'[0,k].to_i].max
Now we just stick that into our method:
class Integer
def smallest_integer(k)
[self, '1023456789'[0,k].to_i].max.upto(Inf).find {|i|
i.to_s.chars.to_a.uniq.count == k
}
end
end
And of course, no Rubyist would ever leave the house without his testing framework in his pocket:
require 'test/unit'
class TestSmallestInteger < Test::Unit::TestCase
def test_that_the_answer_for_n47_and_k1_is_55
assert_equal 55, 47.smallest_integer(1)
end
def test_that_the_answer_for_n7_and_k3_is_102
assert_equal 102, 7.smallest_integer(3)
end
def test_that_the_answer_for_n69_and_k2_is_69
assert_equal 69, 69.smallest_integer(2)
end
def test_that_the_answer_for_n12364_and_k3_is_12411
assert_equal 12411, 12364.smallest_integer(3)
end
end