*Update: I posted a wrap-up here*.

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.

For example, part of the output would be:

- 8, 9, 10, 12 (11 is not valid)
- 98, 102, 103 (99, 100 and 101 are not valid)
- 5432, 5436, 5437 (5433, 5434 and 5435 are not valid)

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

Post your solution in the comments or on your blog. All languages and all approaches (brute force or not) are welcome.

I’m curious to see if somebody can come up with a clever solution (I don’t have one)…

#1 by

Bob Leeon June 29, 2008 - 2:31 pm@chrisb: FWIW, that would take 12 hrs. for max=10,000,000,000.

#2 by ciju on June 29, 2008 - 3:56 pm

I spent some time over the problem, with python. The result is linked below. Bob Lee might find this interesting, as there is a comparison with my implementation of his methods.

ciju.wordpress.com/2008/06/29/beust-sequence-aka-sequence-of-numbers-without-repeating-digits/

#3 by

Bob Leeon June 29, 2008 - 5:10 pmOK, last time. I made mine a little longer, but clearer and faster: crazybob.org/BeustSequence.java.html

@ciju: This implementation may help reduce the overhead you’re seeing from method calls in Python.

#4 by Bob Lee on June 29, 2008 - 8:46 pm

OK, last last time. I went the other direction and made an alternate, more concise version: crazybob.org/BeustSequence2.java.html

#5 by

John Wilsonon June 30, 2008 - 7:04 amA not very pretty but quite fast Java version: rifers.org/paste/show/7580

Time of 1 to 10,000,000 ~58ms on a very old Pentium 4.

The test method could do to be a bit more comprehensive.

#6 by ciju on June 30, 2008 - 7:41 am

Tried my solution in C. It ran through the whole sequence in 180ms. The most important change is the use of integer to store the sequence, rather than string(originally, Bob’s idea).

@Bob: I tried implementing your method(BeustSequence2), in C. It took about 700ms. Again I am being partial of not trying to improve your code. Let me know if you would like to see the code, and suggest changes, although I assume we have spent too much time on this problem.

#7 by

cijuon June 30, 2008 - 7:45 amForgot to mention. The performance results are for limit of 10,000,000,000(ex: all possible).

#8 by

Thierry Janaudyon June 30, 2008 - 8:15 amCreated another (my last ;-)) version based on ‘Permutations Listing': oogifu.blogspot.com/2008/06/coding-challenge-ii.html

Runs the 10^9 one in .6 second.

#9 by ciju on June 30, 2008 - 8:32 am

There was a bug in the code :(. Current version runs in about 230ms($time ./a.out).

ciju.wordpress.com/2008/06/29/beust-sequence-aka-sequence-of-numbers-without-repeating-digits/

#10 by

Danilon June 30, 2008 - 8:57 amThis is a pretty fast solution using ascii-APL J (jsoftware.com). Experts from likely will write even more terse code

f =: [:(#;[:>./2-~/\])(#~([:*/[:~:”:)”0)

f i. 10000

+—-+—+

|5275|105|

+—-+—+

#11 by

Bob Leeon June 30, 2008 - 9:22 am@ciju: BeustSequence2 is the slower but more concise version. I’d try BeustSequence. Then again, the C compiler may not optimize around the recursion very well.

#12 by

Taylor Venableon June 30, 2008 - 9:32 amNot really particularly cute or clever, but a solution in Lua that uses a coroutine that generates numbers as high as your implementation can count:

local c = coroutine.create(function ()

local i = 0

while true do

while tostring(i):match(“(%d).*%1″) do

i = i + 1

end

coroutine.yield(i)

i = i + 1

end

end)

I’m sure it’s not especially fast either.

#13 by

Jason Cheathamon June 30, 2008 - 10:58 ampublic static void main(String[] args) {

int max = 5437;

for (int i = 0; i repeats = new HashSet();

for (int i = 0; i < str.length(); i++) {

if (!repeats.add(str.substring(i, i + 1))) {

return true;

}

}

return false;

}

#14 by

Jason Cheathamon June 30, 2008 - 11:00 amOops:

public static void main(String[] args) {

int max = 5437;

for (int i = 0; i repeats = new HashSet();

for (int i = 0; i < str.length(); i++) {

if (!repeats.add(str.substring(i, i + 1)))

return true;

}

}

return false;

}

#15 by

Jason Cheathamon June 30, 2008 - 11:07 ampublic static void main(String[] args) {

int max = 5437;

for (int i = 0; i < max; i++) {

if (!hasRepeatingInteger(i + “”)) {

System.out.println(i + “”);

}

}

}

public static boolean hasRepeatingInteger(String str) {

Set<String> repeats = new HashSet<String>();

for (int i = 0; i < str.length(); i++) {

if (!repeats.add(str.substring(i, i + 1))) {

return true;

}

}

return false;

}

#16 by

Bob Leeon June 30, 2008 - 11:31 amAlright, I’ve settled on the shorter solution: crazybob.org/BeustSequence.java.html

Here’s the test harness which prints the count and largest gap: crazybob.org/TestBeustSequence.java.html

And here’s the shared Listener interface: crazybob.org/Listener.java.html

#17 by

Bill Kresson June 30, 2008 - 12:11 pmThis is exactly the type of problem in which you want to avoid high level structures like Strings.

Couldn’t post the code so I put it in my google docs:

docs.google.com/Doc?id=avjh8kg87sn_29d4p2gk35

My guess is this is about the fastest implementation you’ll come up with unless someone codes it in C with pointers, and even then the JVM is probably close. To do large numbers be sure to comment out the println that prints a number every iteration.

The one you requested:

For a max of: 10000

Total Displayed=5274

Biggest Jump=104

A smallish one:

For a max of: 1000000

Total Displayed=168570

Biggest Jump=10468

The largest power of 10 that executes instantly:

For a max of: 10000000

Total Displayed=712890

Biggest Jump=104690

Big one still takes less than a minute:

For a max of: 100000000

Total Displayed=2345850

Biggest Jump=1046912

The pattern on “Biggest Jump” seems strange. I suppose it’s a power of 10 type thing.

I could probably go up another power of 10 or two, but that would start to take minutes/hours and any higher than that and I’ll have to change a few ints to longs.

#18 by

Bill Kresson June 30, 2008 - 12:17 pmNever mind–I hadn’t seen Eugene’s solution–keeping it all within ints improves the hell out of it as long as you aren’t printing anything each iteration.

#19 by

Pete Kirkhamon June 30, 2008 - 5:07 pmI think the sum of the values for n digits is (9!/(9-(n-1))!) * ( 45 * pow(10, n-1) + 40 * floor(pow(10, n-1) / 9) ) . Or the progression of the pattern in my blog.

Empirically, the maximum jump for n digits is floor( ( 1203456789-1098765432 ) / pow(10, 10-n) ), since they all have much the same format. For the maximum below an arbitrary value, you’d test the 987… 1023… jump as well.

Probably could think of an expression for a non-noughty number, but it’s bed time.

tincancamera.com/blog

#20 by

Bob Leeon June 30, 2008 - 5:40 pm@Bill Kress: Mine handles 10^10 in less than half a second.

#21 by

Anonymouson July 1, 2008 - 5:03 amfactor-language.blogspot.com/2008/06/cedrics-code-challenge.html

#22 by

Bill Kresson July 1, 2008 - 11:13 amYeah, sorry. I started coding before reading the bottom 1/2 of the responses (the power solutions).

I mostly feel strange about all the earlier solutions using higher language constructs to make a short (nloc) solution when that really doesn’t help anyone. Even java String should be out of the consideration–let alone anything that actually manipulated their strings by splitting them apart just to compare them–holy cow that’s inefficient.

Also, all the solutions are brute force. The pattern of count of numbers found for each power of 10 leads me to believe there actually is a much faster mathematical solution than comparing digits. Probably some factorial-looking thing.

#23 by

stinkyminkyon July 1, 2008 - 11:30 amAnother version of recursive approach – the similar with Crazy Bob’s. I did a quick benchmark and it is faster. I’m not sure it is because I calculate bits and reuse them…

public class Test {

private static class ResultListener

{

public void foundResult(long result)

{

// System.out.println(result);

}

}

static int BITS[];

static

{

BITS = new int[10];

BITS[0] = ( 1 = max )

return;

for( int i = 0 ; i < 10; i++ )

{

if ( (used & BITS[i]) == 0 )

{

l.foundResult(start+i);

recurseRetrieve( (start+i) * 10 , max, used | BITS[i], l );

}

}

}

}

#24 by

stinkyminkyon July 1, 2008 - 11:47 amMy bad. The above does not return in 1 to MAX in sequence. It is basically combinatorial approach so it will be ( 1 , 10 , 102, 1023 , 1203 )

#25 by

Robert Fischeron July 1, 2008 - 1:03 pmAs requested, I posted my solution on my blog.

It’s in OCaml, and finds all the values from 1 to max_int in 27 seconds on my 2.16 GHz MacBook Pro.

enfranchisedmind.com/blog/2008/07/01/cedrics-problem-in-ocaml/

#26 by

Robert Fischeron July 1, 2008 - 1:03 pmBTW, your blog software balks at if you prefix the URL with the HyperText Transfer Protocol prefix.

#27 by ciju on July 1, 2008 - 2:24 pm

@Bill Kress

I don’t know what makes you feel that all solutions are brute force. At the least Bob’s and my solutions are not. They just generate the required numbers(which the problem statement asks to generate).

If you are talking about the count of such numbers, then thats altogether a different issue. Its simple permutation. Here’s google helping us out with the answer for maximum possible such numbers.

http://www.google.co.in/search?hl=en&q=9*(1+%2B+9!%2F8!+%2B+9!%2F7!+%2B+9!%2F6!+%2B+9!%2F5!+%2B+9!%2F4!+%2B+9!%2F3!+%2B+9!%2F2!+%2B+9!+%2B+9!)

If you need explanation, visit the end of my blog entry.

ciju.wordpress.com/2008/06/30/beust-sequence-aka-sequence-of-numbers-without-repeating-digits/

Note: the link has changed from the one posted before, I don’t know what wordpress.com is doing.

#28 by

siderealon July 1, 2008 - 5:16 pmI’m fascinated by the number of authors that claim their solution isn’t brute force, when in fact the solution is clearly brute force (up to and including regex! A recompiled regex on every loop iteration! That’s brute with a big, wooden club!)

We may be watching the end of the era when programmers even cared about the performance of an algorithm and nowadays simply assume that the implementation that takes the fewest characters to write is the fastest one.

We need a symposium on the definition of brute force.

#29 by ciju on July 1, 2008 - 6:51 pm

Brute-force or not!

Regarding the confusion about whats brute-force and whats not, let me explain a little. If you are asked to generate numbers form 1 to 10, generating those numbers is not brute-force. You have to go though them to print them out, at the least. Now, if you are asked to print numbers in range [1, 10] which are divisible by 5. Then checking each number and printing only the once divisible by 5 (ex: 5 and 10), does make it brute-force. Because the output length is 2, and you are going through whole of the search space to generate those 2 numbers. The one which only generates 5 and 10 is the _not_ brute-force method. And I can conform that at least Bob’s and my method are not brute-force. They only generate the numbers which don’t have repeated digits. They don’t generate the whole sequence and check whether digits are repeated in a number. And thats why, for example, my solution completes in about 0.2s (I am talking about generating all the possibilities and only the possibilities, 8877690(see my comment above), in sequential order).

#30 by

Paulo Gasparon July 1, 2008 - 8:51 pm@Bill Kress:

Something wrong with your algorithm: I could verify that your “Biggest Jump” is wrong for the 10,000 case. Here are my results:

The one you requested:

For a max of: 10,000 done in 0 ms

Total Displayed: 5,274

Biggest Jump: 124

Biggest Jump begin: 9,877

Biggest Jump end : 10,000

@Crazy Bob:

414 ms

… yeah, I have fast hardware and yeah your code is cleaner!

Huge Crazy Bob’s one…:

For a max of: 10,000,000,000 done in 414 ms

Total Displayed: 8,877,690

Biggest Jump: 123,456,790

Biggest Jump begin: 9,876,543,211

Biggest Jump end : 10,000,000,000

@all:

I just jump number ranges when most significant numbers have repetitions. The essentials (copy+paste on your IDE and format if you will):

public class BeustLongSequenceFinder {

private final long m_maxValue;

private long m_maxContinuousSkippingCount;

private long m_maxContinuousSkippingEnd;

private long m_continuousSkippingCount;

private long m_totalSkippingCount;

public BeustLongSequenceFinder(final long maxValue) {

if (maxValue 0″);

m_maxValue = maxValue;

}

//… getters …

public void findNumbers() {

// Result fields

m_maxContinuousSkippingCount = 0;

m_maxContinuousSkippingEnd = 0;

m_totalSkippingCount = 0;

// Calc. state fields

m_continuousSkippingCount = 0;

final long xNextVal = loopNext(0, m_maxValue, digitCount(m_maxValue) – 1, 0);

if (0 != m_continuousSkippingCount)

storeJump(xNextVal);

} // end method findNumbers

private final void storeJump(final long xNextVal) {

m_totalSkippingCount += m_continuousSkippingCount;

if (m_continuousSkippingCount > m_maxContinuousSkippingCount) {

m_maxContinuousSkippingCount = m_continuousSkippingCount;

m_maxContinuousSkippingEnd = xNextVal – 1;

}

}

private final long loopNext(long nextValue, final long maxValue,

final long digitIndex, final int leftmostMask) {

if (0 == digitIndex) {

for (int i = 0; (i maxValue)

m_continuousSkippingCount += maxValue – nextValue + 1;

else

m_continuousSkippingCount += xSkipped;

nextValue = xNextNextValue;

}

else {

nextValue = loopNext(nextValue, maxValue, xNextIndex, leftmostMask | (1 << i));

} // end if-else

} // end for

} // end if-else

return nextValue;

} // end if-else

} // end method loopDigit

private static final long digitCount(final long num) {

return (long) Math.log10(num) + 1;

} // end method digitCount

} // end class BeustSequenceFinder

#31 by

Paulo Gasparon July 1, 2008 - 9:00 pmSorry! 2nd attempt giving HTML escaping to less-than and greater-than operators:

public class BeustLongSequenceFinder {

private final long m_maxValue;

private long m_maxContinuousSkippingCount;

private long m_maxContinuousSkippingEnd;

private long m_continuousSkippingCount;

private long m_totalSkippingCount;

public BeustLongSequenceFinder(final long maxValue) {

if (maxValue <= 0)

throw new IllegalArgumentException(“must be: maxValue > 0″);

m_maxValue = maxValue;

}

//… getters …

public void findNumbers() {

// Result fields

m_maxContinuousSkippingCount = 0;

m_maxContinuousSkippingEnd = 0;

m_totalSkippingCount = 0;

// Calc. state fields

m_continuousSkippingCount = 0;

final long xNextVal = loopNext(0, m_maxValue, digitCount(m_maxValue) – 1, 0);

if (0 != m_continuousSkippingCount)

storeJump(xNextVal);

} // end method findNumbers

private final void storeJump(final long xNextVal) {

m_totalSkippingCount += m_continuousSkippingCount;

if (m_continuousSkippingCount > m_maxContinuousSkippingCount) {

m_maxContinuousSkippingCount = m_continuousSkippingCount;

m_maxContinuousSkippingEnd = xNextVal – 1;

}

}

private final long loopNext(long nextValue, final long maxValue,

final long digitIndex, final int leftmostMask) {

if (0 == digitIndex) {

for (int i = 0; (i < 10) && (nextValue <= maxValue); ++i, ++nextValue) {

if (0 != (leftmostMask & (1 << i)))

++m_continuousSkippingCount;

else {

if (0 != m_continuousSkippingCount) {

storeJump(nextValue);

m_continuousSkippingCount = 0;

}

} // end if-else

} // end for

return nextValue;

}

else {

final long xNextIndex = digitIndex – 1;

if (0 == leftmostMask) {

nextValue = loopNext(nextValue, maxValue, xNextIndex, 0); // Leading 0

for (int i = 1; i < 10; i++)

nextValue = loopNext(nextValue, maxValue, xNextIndex, (1 << i));

}

else {

for (int i = 0; (i < 10) && (nextValue <= maxValue); i++) {

if (0 != (leftmostMask & (1 << i))) {

// Digits already repeated

// Skipping inner loops

long xSkipped = 10; // = pow10(digitIndex);

{ for (int p = 1; p < digitIndex; ++p)

xSkipped *= 10;

}

final long xNextNextValue = nextValue + xSkipped;

if (xNextNextValue > maxValue)

m_continuousSkippingCount += maxValue – nextValue + 1;

else

m_continuousSkippingCount += xSkipped;

nextValue = xNextNextValue;

}

else {

nextValue = loopNext(nextValue, maxValue, xNextIndex, leftmostMask | (1 << i));

} // end if-else

} // end for

} // end if-else

return nextValue;

} // end if-else

} // end method loopNext

private static final long digitCount(final long num) {

return (long) Math.log10(num) + 1;

} // end method digitCount

} // end class BeustSequenceFinder

#32 by

Bob Leeon July 1, 2008 - 10:37 pm@sidereal: For max=10^10, 8,877,691 values match. My algorithm only performs 8,877,690 operations while the brute force approach requires 10^10 ops (or 1,125X more than mine).

#33 by

Bob Leeon July 1, 2008 - 10:58 pm@sidereal: To illustrate, here’s a log2-scale graph of:

1) the # of ops performed by my algorithm

2) the # of ops performed by a brute force algorithm

3) the number of matching values

for maximum values up to 10^10: crazybob.org/beust.png

As you can see, a brute force algorithm scales at about O(max) while my algorithm scales at O(matches) in the worst case (and much better in common cases).

#34 by

jdumbon July 1, 2008 - 11:30 pmsome ugly java code

usage

long from = Long.parseLong(args[0]);

long to = Long.parseLong(args[1]);

long last=-1;

for(Udin z = new Udin(from); z.inc() && (last=z.toLong()) 0 || number==0){

int rem = (int) (num % 10);

if(set.get(rem)){

throw new IllegalArgumentException( number + ” is invalid ‘cas “+rem+” exist in “+set );

}

setDigit(++biggest, rem);

num = num / 10;

if(number==0){

break;

}

}

Arrays.fill(digits, biggest+1, digits.length, (short) -1);

}

@Override

public String toString() {

StringBuilder str = new StringBuilder();

for (int i=biggest; i>=0; i–){

str.append(digits[i]);

}

return str.toString();

}

public long toLong(){

long rez = 0;

for (int i=biggest; i>=0; i–){

rez = rez*10 + digits[i];

}

return rez;

}

void setDigit(int pozition, int digit) {

assert !set.get(digit) : digit + ” already there ” + set+” – “+Arrays.toString(digits);

digits[pozition] = (short) digit;

set.set(digit);

}

/**

* @return false means state becomes inconststent

* */

public boolean inc(){

int little=0;

// try to inc littlest

for(; little0){

// havent free digits to fill

if(little > 10-set.cardinality()){

return false;

}else{

// fill digits from oldest by less numbers

little–;

for( ;little>=0; little– ){

setDigit(little, set.nextClearBit(0));

}

return true;

}

} else {

return true;

}

}// newVal=10 go ahead to next little

}

return false;

}

}

#35 by

Hoang Thangon July 2, 2008 - 1:36 amusing System;

using System.Collections.Generic;

using System.Text;

namespace ConsoleApplication1

{

class Program

{

static void Main(string[] args)

{

//System.Console.WriteLine(1 reserved = new List();

ICollection ketqua = new List();

void print()

{

foreach (int i in ketqua)

{

System.Console.Write(i + ” “);

}

System.Console.WriteLine();

System.Console.WriteLine(count);

System.Console.ReadKey();

}

void dequi(int next)

{

for (int j = 0; j < 10; j++)

{

int temp = next * 10 + j;

if (!reserved.Contains(j) && temp < max && temp != 0)

{

ketqua.Add(temp);

count++;

reserved.Add(j);

dequi(temp);

reserved.Remove(j);

}

}

}

}

}

#36 by

Paulo Gasparon July 2, 2008 - 2:38 amSlight improvement after a couple of optimizations, including seeding (when max big enough) the biggest jump with a very conservative (max/100)-1.

Code is still ugly and I will just post the timings:

The one you requested:

For a max of: 10,000 done in 0 ms

Total Displayed: 5,274

Biggest Jump: 124

Biggest Jump begin: 9,877

Biggest Jump end : 10,000

Huge Crazy Bob’s one…:

For a max of: 10,000,000,000 done in 383 ms

Total Displayed: 8,877,690

Biggest Jump: 123,456,790

Biggest Jump begin: 9,876,543,211

Biggest Jump end : 10,000,000,000

Have Fun,

#37 by

augustsson July 2, 2008 - 5:58 amSimple Haskell version:

import Data.List(nub)

main = print $ counter 10000

counter n = (length ns, maximum $ zipWith (-) (tail ns) ns) where ns = filter (not . anySame . show) [1..n]

anySame xs = xs /= nub xs

#38 by

Bob Leeon July 2, 2008 - 7:52 am@Paulo: Both 9,876,543,211 and 10,000,000,000 contain dups.

#39 by

Paulo Gasparon July 2, 2008 - 8:02 am@Bob Lee

Of course they are! They are the first and last element of the range, since I am presenting the jump as a closed boundary interval.

Now, if I can get my implementation as clean as yours…

Have fun,

#40 by

Daniel Spiewakon July 2, 2008 - 10:01 amAnother Scala version (completely untested):

def printNonRep(min: Int)(max: Int) = {

(min until max).toList.flatMap { num =>

val str = num.toString.toCharArray

val (_, res, _) = ( str :\ (false, Nil, Set[Char]()) ) { (tuple, ch) =>

val (dup, res, set) = tuple

if (dup || set contains ch) {

(true, res, set)

} else {

(false, ch :: res, set + ch)

}

}

(0 /: res) { (_ * 10) + _ }

}

}

No-where near as elegant as the first version given, but I think it works and is reasonably efficient. Of course, it’s functional soup…

There’s probably an issue with type inference in the foldRight tuple, but I haven’t tried it to be sure.

#41 by

Sam Pullaraon July 2, 2008 - 12:41 pmBob Lee’s version in Java is by far the best one I’ve seen.

#42 by

Paulo Gasparon July 2, 2008 - 1:14 pm@Sam

Yes, it is cleeeaaan!

I wonder if I am getting any meaningful performance gain over Bob’s version and still can’t get clean code with my strategy.

#43 by

Devaon July 2, 2008 - 1:29 pmhttp://www.lolcode.com/home

I will followup soon with a kickass LOLCODE implementation soon

#44 by Mauricio Fernandez on July 2, 2008 - 5:08 pm

I have written a slightly more general solution in OCaml (it can count efficiently in any arbitrary base, not only in base 10, so e.g. base 1000 is no problem for it, unlike most solutions above).

It is a bit faster than Bob Lee’s Java version on my box (AMD Athlon 64 X2 6000+). My program runs in 640ms, the Java implementation counts to 10^10 in ~680ms (total exec time ~750ms including JVM startup time, etc.).

It can be found at

eigenclass.org/hiki/ordered_permutations

#45 by

Jimon July 2, 2008 - 9:19 pmWhat, no Lisp submissions?!

#46 by

sunwukongon July 2, 2008 - 10:20 pmWell, here is one.

(defun collect-numbers-without-repetition (min max)

(flet ((repeatedp (n)

(let ((digits (format nil “~d” n)))

(/= (length digits) (length (remove-duplicates digits))))))

(loop for i from min to max unless (repeatedp i) collect i)))

#47 by

Bob Leeon July 3, 2008 - 1:38 amSince Mauricio upped the ante, here’s a slightly longer version which runs in 210ms for max=10^10 on my machine: crazybob.org/FastBeustSequence.java.html

Like Mauricio’s OCaml solution, iteration of the digit set is now O(size) as opposed to O(capacity), but unlike the OCaml solution, set ops are O(1) instead of O(log(n)).

#48 by ragstorooks on July 3, 2008 - 2:25 am

I have a different approach which works quite quickly but is highly customized to fit max=10,000. It would in its current state involve code changes if max changed. Anyway, for what its worth, the code can be found here: ragstorooks.wordpress.com/2008/07/03/cedrics-coding-challenge/

#49 by

Paulo Gasparon July 3, 2008 - 4:00 am@Bob

Interesting code!

You have to tell us what Java version + hardware you are using.

My 10,000,000,000 done in 383 ms was ran in Java 6 on under OS X on a MacPro 2008 2.8GHz. (8 cores but that is not important.)

Java 5 runs it twice as slow!

Tkx,

#50 by

Chris Cardon July 3, 2008 - 6:17 amHere is a brute force implementation in Fan.

class Nonrepeat

{

static const Int START := 0

static const Int MAX := 10000

static Void main()

{

Int m := 0 //max gap

Int k := 0 //valid value count

Int p := START //previous valid value

(START..MAX).each |Int x|

{

Str s := x.toStr

if(s.size == uniqueCharCount(s))

{

k++

Int g := (x-p)

echo( “$x gap: $g (count $k)”)

if(g>m)

{

m=g

}

p=x

}

}

echo(“Max gap is $m” )

}

static Int uniqueCharCount(Str s)

{

u := Int[,]

s.each |Int c |

{

if(!u.contains(c))

{

u.add(c)

}

}

return u.size

}

}