Sunday, June 29, 2008

Cedric's code challenge

Cedric Beust posed a coding challenge:

Here is an interesting coding challenge: write a counter function that counts from 1 to max but only returns numbers whose digits don't repeat.

...
Also:
  • Display the biggest jump (in the sequences above, it's 4: 98 -> 102)
  • Display the total count of numbers
  • Give these two values for max=10000

In the comments section of his blog, you can find many solutions, some are long, some are short but have lovely punctuation soup like !/(.).*\1/, 1..MAX; (that's from the Perl solution).

Here is a Factor version that is shorter than anything in the comments there:
USING: kernel math.parser math.ranges math.vectors sequences sets ;

1 10000 [a,b] [ number>string all-unique? ] filter
[ ] [ length ] [ dup 0 prefix v- supremum ] tri

It leaves three values on the stack (hence tri): a sequence of numbers with non-repeating digits, the length of this sequence, and the largest jump between any two numbers in the sequence.

Of course one could claim that this is cheating, since I'm using a lot of library words here. Fair enough, but those library words in the library for a reason: they get used a hell of a lot.

2 comments:

Crest said...

Although having more tokens I prefer this version because it doesn't create an uneccesary copy of the the 5274 element sequence returned by filter by appending the prefix 0.

1 10000 [a,b] [ number>string all-unique? ] filter
[ ] [ length ] [ [ 1 tail-slice ] keep v- supremum ] tri

Slava Pestov said...

Crest: here's another approach which avoids both intermediate sequences:

1 10000 [a,b] [ number>string all-unique? ] filter
[ ] [ length ] [ 2 <clumps> 0 [ first2 swap - max ] reduce ] tri