*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

dubekon June 28, 2008 - 1:08 amIn Ruby, brute-force, probably really slow:

(98..103).select { |x| x.to_s.size == x.to_s.split(//).uniq.size }

=> [98, 102, 103]

#2 by

szeryfon June 28, 2008 - 1:15 amPerl:

#!perl -wl

use strict;

use List::Util qw(reduce max);

use constant MAX => 10_000;

my @nums = grep !/(.).*\1/, 1..MAX;

my $count = @nums;

my $jump = 0;

reduce {$jump = max($jump, $b – $a); $b} @nums;

print “@nums”;

print “$count, $jump”;

#3 by szeryf on June 28, 2008 - 1:26 am

Ruby, same approach (dunno if you call it clever or brute):

#!ruby -w

MAX = 10_000;

nums = (1..MAX).reject {|num| num.to_s =~ /(.).*\1/}

count = nums.length

jump = 0

nums.inject(1) {|a, b| jump = [jump, b – a].max; b}

p nums, count, jump

#4 by szeryf on June 28, 2008 - 1:44 am

Python, same approach:

#!python

import re

MAX = 10000

r = re.compile(r'(.).*\1′)

nums = [x for x in range(1, MAX) if not r.search(str(x))]

count = len(nums)

jump = 0

last = 0

for x in nums :

jump = max(jump, x – last)

last = x

print nums

print count

print jump

BTW. Now I see I forgot to use precompilation of regexps in Perl and Ruby versions — to do this, add o after the regexp, i.e. /(.).*\1/o

#5 by

dirkfon June 28, 2008 - 2:05 amJavascript, approach based on regexp :

<script>

var max = 10000, count=jump=bigjump=0;

for(var i=1; i<=max; i++) {

jump++;

if(! /(\d).*\1/g.test(i) ) {

document.write(i+’ ‘+jump+’ ‘ +'<br />’);

bigjump = Math.max(jump,bigjump);

jump=0;

count++;

}

}

bigjump = Math.max(jump,bigjump);

document.write(‘Total count:’+count+'<br />Biggest jump:’+bigjump+'<br />’);

</script>

#6 by

Marc Logemannon June 28, 2008 - 2:15 amSounds like a Google interview question or something. ๐ Am far too tired to “work” on that, but its a funny puzzler.

Marc

#7 by

levi_hon June 28, 2008 - 2:16 amJava (I’m sorry for the lack of indentation, I couldn’t figure out how the system expects you to post code):

import java.io.PrintStream;

import java.util.LinkedList;

import java.util.List;

public class Test {

private final int start;

private final int end;

private List numbersWithoutRepeatingDigits;

private int biggestJump;

public Test(int start, int end) {

this.start = start;

this.end = end;

numbersWithoutRepeatingDigits = new LinkedList();

}

public void calculateResults() {

int previousNumber = 0;

for (int number = start; number 0);

return false;

}

public void displayResults(PrintStream out) {

out.printf(“Numbers up to %d without repeating digits (%d): %s%n”, end, numbersWithoutRepeatingDigits.size(), numbersWithoutRepeatingDigits);

out.printf(“Biggest jump: %d%n”, biggestJump);

}

public static void main(String… parameters) {

Test test = new Test(1, 10000);

test.calculateResults();

test.displayResults(System.out);

}

}

A Set solution seems to be twice as slow, a regex one about 11 times. Both are still fast enough for finding results between 1 and 10000, though.

#8 by

levi_hon June 28, 2008 - 2:24 amThe comment system also ate my generics and most of both the calculateResults and hasRepeatingDigit(int) methods… oh well. I published it at docs.google.com/Doc?id=dppnxf9_0gtzdzzfw

#9 by

Keith Henryon June 28, 2008 - 2:39 amC#3:

//this could also be a regex based func

Func isNonRepeat =

i =>

{

char[] digits = i.ToString().ToCharArray();

return digits.Distinct().Count() == digits.Length;

};

//get all the non-repeating nums

var nums =

from int i in Enumerable.Range( 1, 10000 )

where isNonRepeat( i )

select i;

int last = 1, gap = 0, count = 0;

foreach ( var i in nums )

{

gap = Math.Max( gap, i – last );

last = i;

count++;

}

Console.WriteLine( “count: {0,0}”, count );

Console.WriteLine( “max gap: {0,0}”, gap );

Still brute forcing to get the gaps, I’m not sure whether there’s a Linq expression for Last.

#10 by

Nils Kassubeon June 28, 2008 - 2:52 am// Groovy version. The readable version seems fast enough

final MAX = 10000

def candidates = (1..MAX).findAll {

it.toString().size() == it.toString().toList().unique().size()

}

def jump = 0

def last = 0

for (x in candidates) {

if (x-last > jump) {jump = x-last}

last = x

}

println “Number of candidates: $candidates.size – Biggest jump $jump”

#11 by

Kannan Karthaon June 28, 2008 - 4:59 amHere is one from me in Java.

May not be a smart one, but works … Regex was really slow. Apologies for the indentation problem.

public class GenrateNumbers {

static int jump = 0;

static int MAX = 10000;

public static void main(String[] args) {

int tempValue = 0;

for (int i = 1; i < MAX; i++) {

String number = String.valueOf(i);

boolean flag = hasRepeatingNumber(number.toCharArray());

if(!flag){

System.out.println(number);

jump = jump < (i – tempValue) ? (i – tempValue) : jump;

tempValue = i;

}

}

System.out.println(“Jump: ” + jump);

}

private static boolean hasRepeatingNumber(char[] charArray) {

for (int j = 0; j < charArray.length; j++) {

for (int j2 = j+1; j2 < charArray.length; j2++) {

if(charArray[j] == charArray[j2]){

return true;

}

}

}

return false;

}

}

#12 by

Thierry Janaudyon June 28, 2008 - 5:57 amCedric,

Here is my not-clever solution: janaudy.com/weblog/

But, there is an easier solution to the total count of numbers, for 1 to 10,000:

I am going to do it from 1, to 9,999 as 10,000 is not part of it (4 0s):

How many 4 digits number can be made out of 0, 1, …, 9 if no digit can repeat:

9 (9 choices for the first digit, no 0) * 9 (for the second) * 8 (third) * 7 (fourth) = 4,536

How many 3 digits number can be made out of 0, 1, …, 9 if no digit can repeat:

9 (9 choices for the first digit, no 0) * 9 (for the second) * 8 (third) = 648

How many 2 digits number can be made out of 0, 1, …, 9 if no digit can repeat:

9 (9 choices for the first digit, no 0) * 9 = 81

How many 1 digits number can be made out of 0, 1, …, 9 if no digit can repeat:

9 (9 choices for the first digit, no 0) = 9 (0 excluded)

So the total count is 4,536 + 648 + 81 + 9 = 5,274

As for the biggest jump, it can only appear in the 4 digits one, so it is 10,000 – 9,876 = 124

(99xx, 9899, 9898, etc.. going down to 9,876)

Thierry

#13 by

Thierry Janaudyon June 28, 2008 - 5:58 amCedric,

Here is my not-clever solution: janaudy.com/weblog/

But, there is an easier solution to the total count of numbers, for 1 to 10,000:

I am going to do it from 1, to 9,999 as 10,000 is not part of it (4 0s):

How many 4 digits number can be made out of 0, 1, …, 9 if no digit can repeat:

9 (9 choices for the first digit, no 0) * 9 (for the second) * 8 (third) * 7 (fourth) = 4,536

How many 3 digits number can be made out of 0, 1, …, 9 if no digit can repeat:

9 (9 choices for the first digit, no 0) * 9 (for the second) * 8 (third) = 648

How many 2 digits number can be made out of 0, 1, …, 9 if no digit can repeat:

9 (9 choices for the first digit, no 0) * 9 = 81

How many 1 digits number can be made out of 0, 1, …, 9 if no digit can repeat:

9 (9 choices for the first digit, no 0) = 9 (0 excluded)

So the total count is 4,536 + 648 + 81 + 9 = 5,274

As for the biggest jump, it can only appear in the 4 digits one, so it is 10,000 – 9,876 = 124

(99xx, 9899, 9898, etc.. going down to 9,876)

Thierry

#14 by

Danon June 28, 2008 - 6:30 amThierry, your answer raises an important question. Is the biggest jump 124? Do we include the gap between 9876 and 10000 as a “jump” even though 10000 is not one of the values in the sequence?

#15 by

Danon June 28, 2008 - 6:34 amHere is my naive Haskell solution:

import List(nub)

— Predicate that returns True if a number contains no duplicate digits.

noDuplicateDigits :: Int -> Bool

noDuplicateDigits n = length (nub (digits)) == length digits

where digits = show n

values :: Int -> [Int]

values n = [x | x (Int, Int)

answer n = (length sequence, gap)

where sequence = values n

gap = maximum (zipWith subtract sequence (tail sequence))

#16 by

dimitrison June 28, 2008 - 6:50 amBrute force in Erlang without erlang library calls.

-module(count).

-compile(export_all).

to_digits(Number) ->

to_digits(Number, []).

to_digits(Number, List) when Number div 10 == 0 ->

[Number | List];

to_digits(Number, List) ->

to_digits(Number div 10, [Number rem 10 | List]).

test_to_digits() ->

[3] = to_digits(3),

[1,2] = to_digits(12),

[1,0,0] = to_digits(100).

in_list(Element, [Element|_T]) ->

true;

in_list(_Element, []) ->

false;

in_list(Element, [_H|T]) ->

in_list(Element, T).

test_in_list() ->

true = in_list(1,[1,2,3]),

true = in_list(2,[1,2,3]),

true = in_list(3,[1,2,3]),

false = in_list(0,[1,2,3]),

false = in_list(0,[]),

true = in_list(1,[1]).

unique_list([]) ->

true;

unique_list([H|T]) ->

case in_list(H,T) of

true ->

false;

false ->

unique_list(T)

end.

test_unique_list() ->

false = unique_list([1,1]),

true = unique_list([1,2]),

true = unique_list([1]),

false = unique_list([1,2,1]),

false = unique_list([2,1,1]),

false = unique_list([1,1,2]),

true = unique_list([1,2,3]).

count(From, Max) ->

Cons = fun(List,Element) -> [Element|List] end,

count(From, Max + 1, Cons, []).

count(Upto, Upto, _Fun, State) ->

State;

count(From, Upto, Fun, State) when From

case unique_list(to_digits(From)) of

true ->

count(From + 1, Upto, Fun, Fun(State,From));

false ->

count(From + 1, Upto, Fun, State)

end.

test_count() ->

[3,2,1] = count(1,3),

[12,10,9] = count(9,12),

[103,102,98,97] = count(97,103).

test_count4() ->

Counter = fun({List,Sum},Element) -> {[Element|List],Sum + 1} end,

{[12,10],2} = count(10,13,Counter,{[],0}),

4 = count(97,104,fun(Sum,_Element) -> Sum + 1 end,0),

GapFinder = fun({[H|_T]=List,MaxGap},Element) when Element – H > MaxGap ->

{[Element|List],Element – H};

({List,MaxGap},Element) ->

{[Element|List],MaxGap}

end,

{[103,102,98],4} = count(98,104,GapFinder,{[],0}).

challenge(Max) ->

Finder = fun({[H|_T]=List,MaxGap,Counter},Element) when Element – H >= MaxGap ->

% io:format(“Gap ~p from ~p to ~p~n”, [Element-H,H,Element]),

{[Element|List],Element – H,Counter + 1};

({List,MaxGap,Counter},Element) ->

{[Element|List],MaxGap,Counter + 1}

end,

{_,BiggestJump,CountOfNumbers} = count(1,Max+1,Finder,{[],0,0}),

{BiggestJump, CountOfNumbers}.

test_challenge() ->

{1,10} = challenge(10),

{2,90} = challenge(100),

{11,738} = challenge(1000),

{105,5274} = challenge(10000),

{1047,32490} = challenge(100000).

test() ->

test_to_digits(),

test_in_list(),

test_unique_list(),

test_count(),

test_count4(),

test_challenge(),

ok.

#17 by

Danon June 28, 2008 - 7:32 amI also posted my solution on my blog, because the comments and indentation were stripped here.

blog.uncommons.org/2008/06/28/cedrics-coding-challenge/

#18 by

DeWitton June 28, 2008 - 7:49 amThe following python generator also works:

(i for i in xrange(start, end) if len(str(i)) == len(set(str(i)))):

-DeWitt

#19 by

Keith Henryon June 28, 2008 - 8:43 amC#3 again, down to two Linq loops:

//get all the non-repeating nums, conv to array to make ordinal lookups quicker

int counter = 0;

var nums = (

from i in Enumerable.Range( 1, 10000 )

let digits = i.ToString().ToCharArray()

where digits.Distinct().Count() == digits.Length

select new { num = i, ordinal = counter++ }

).ToArray();

Console.WriteLine( “count: {0,0}”, nums.Length );

//get all the gaps, using array to loop up previous

var gaps =

from item in nums

let last = item.ordinal > 0 ? nums[item.ordinal – 1].num : 1

select item.num – last;

Console.WriteLine( “max gap: {0,0}”, gaps.Max() );

#20 by

Pete Kirkhamon June 28, 2008 - 9:37 amAnother python implementation at tincancamera.com which is somewhat coloured by my normal use of python (prototyping algorithms before porting them to C++ or Java). Both brute-force iterate and filter and a combinatorics approach; the combinatorics one is faster for big N, but slower for N < 2e6. For max = 10000, total 25277895; biggest jump 105, from 1098 to 1203.

Why doesn’t your url form allow h t t p

#21 by

Pete Kirkhamon June 28, 2008 - 9:39 amNo, I don’t want my email published on your web site. Please remove link.

#22 by

Anonymouson June 28, 2008 - 10:00 amA Scala version:

for (i <- 1 to 100000; s = i.toString; if HashSet[Char](s:_*).size == s.size) println(i)

#23 by

Eugene Kuleshovon June 28, 2008 - 10:36 amJava version (brute-force) without collections and nearly no memory allocation. http://www.jroller.com/eu/entry/cedric_s_coding_challenge

I wonder if it is possible to give an answer to “the biggest jump” question without iterating trough entire sequence.

Also, it would be interesting to check possibilities of parallelizing tasks, perhaps using Kilim or Doug Lea’s for/join framework.

#24 by

Eugene Kuleshovon June 28, 2008 - 10:39 amCedric, what is with your comment filter? it doesn’t allow to use “http” “colon” “slash” “slash” in the comment text and in the url field…

#25 by

Thierry Janaudyon June 28, 2008 - 10:40 amDan,

You are right. Cedric needs to clarify this point. It is no a ‘jump’ as per say, let’s call my jump a ‘relative jump’ and not an ‘absolute jump’.

#26 by

Mathieu Robinon June 28, 2008 - 11:06 amNon brute force, in python:

from collections import deque

BASE = 10

MAX = 10000

queue = deque(range(1, BASE))

max_gap = 0

count = 1

prev_n = 0

while len(queue) > 0:

__n = queue.popleft()

__max_gap = max(max_gap, n – prev_n)

__prev_n = n

__count += 1

__if n * BASE < MAX:

____has_digit = [False] * BASE

____k = n

____while k != 0:

______has_digit[k % BASE]= True

______k /= BASE

____for d, b in enumerate(has_digit):

______if not b:

________q = n * BASE + d

________queue.append(q)

print count, max_gap

Also results in 5275 numbers in the sequence, max gap of 105.

#27 by

Thierry Janaudyon June 28, 2008 - 11:29 amFollowing my investigation, a “clever” solution, only valid when max is a multiple of 10: 1000, 10,000, 100,000….

Result is immediate:

public class CC2 {

static final int[] PCA = {

9,

9 * 9,

9 * 9 * 8,

9 * 9 * 8 * 7,

9 * 9 * 8 * 7 * 6,

9 * 9 * 8 * 7 * 6 * 5,

9 * 9 * 8 * 7 * 6 * 5 * 4,

9 * 9 * 8 * 7 * 6 * 5 * 4 * 3,

9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2

};

static final int[] ST = {

9,

98,

987,

9876,

98765,

987654,

9876543,

98765432,

987654321

};

public static void main(String[] args) {

// 4 is up to 9999, 5 up to 99,999, 9 up to 999,999,999,

// Biggest is 9,876,543,210

int nbd = Integer.parseInt(args[0]);

int max = (int)Math.pow(10, nbd);

int nbt = 0;

for(int i=1; i <= nbd; i++) {

nbt += PCA[i-1];

}

int rjump = max – ST[nbd-1];

System.out.println(“For Max “+ max);

System.out.println(“Total Count Of Numbers: ” + nbt);

System.out.println(“Relative Jump: “+rjump);

}

}

#28 by

Mathieu Robinon June 28, 2008 - 11:55 amSmall patch to my solution:

– 0 is not part of the sequence, so count is initialized at 0, not 1

– to make it work if MAX is not a power of BASE:

if q queue.append(q)

#29 by

Andres Almirayon June 28, 2008 - 2:28 pmWaiting for someone to post a solution using Fan ๐

#30 by

Charles Milleron June 28, 2008 - 3:49 pmThis problem is so much easier to solve in binary.

#31 by

Ants Aasmaon June 28, 2008 - 4:08 pmA somewhat non-bruteforce functionally factored Python solution: pastebin.com/f63ce9880

#32 by

Ants Aasmaon June 28, 2008 - 4:09 pmSorry, pasted the wrong URL, the correct one is pastebin.com/f5cec4683

#33 by

Ed Davieson June 28, 2008 - 5:30 pmszeryf, in your Ruby solution (which is neat and quick, by the way) wouldn’t this

jump = 0

nums.inject(1) {|a, b| jump = [jump, b – a].max; b}

be more naturally expressed using each_cons(2) instead of inject with its “arbitrary” initial value and redundant return value?

#34 by

Erik Engbrechton June 28, 2008 - 6:30 pmI’ve got a heuristics based solution on my blog. It’s mildly slower than a brute-force solution for small n, and I bet it’s competitive with a combinatronics based solution for large n.

I would post a link, but your comment filter will just eat it.

#35 by

Cedricon June 28, 2008 - 6:49 pmEric’s heuristic solution is at erikengbrecht.blogspot.com/2008/06/cedrics-code-challenge.html

#36 by szeryf on June 28, 2008 - 11:44 pm

Ed Davies: sure, I forgot about each_cons. But the return value in inject is not redundant, it’s used as `a’ in next pair ๐

Ruby version with each_cons:

#!ruby -w

require “enumerator”

MAX = 10_000

nums = (1..MAX).reject {|num| num.to_s =~ /(.).*\1/o}

count = nums.length

jump = 0

nums.each_cons(2) {|a, b| jump = [jump, b – a].max}

p nums, count, jump

#37 by

Logan Johnsonon June 29, 2008 - 12:51 amsolution based on searching the string space:

docs.google.com/View?docID=dhpjhcjh_14f9msp3c8

#38 by

Bob Leeon June 29, 2008 - 1:52 amHere’s a really simple and efficient Java implementation that can find all values up to 10,000,000,000 on my Mac Pro in about 0.7s (not counting println overhead): crazybob.org/BeustSequence.java.html

#39 by

Bob Leeon June 29, 2008 - 2:17 amMake that 0.6s after a slight refactoring.

#40 by

Samuel A. Falvo IIon June 29, 2008 - 2:19 amPlease find herein a version that satisfies the challenge as stated, written in ANSI Forth. *WARNING* — This blog strips whitespace. VERY annoying. If the Forth code is found to be hard to read, this is partly to blame.

10000 constant largest

: rdrop postpone r> postpone drop ; immediate

( a simple approximation of integer sets using bit-masks )

( good enough to satisfy the challenge )

: mask ( n — n’ ) 1 swap lshift ;

: union ( n a — ) swap mask over @ or swap ! ;

: intersects ( n a — f ) @ swap mask and ;

( the challenge solution proper )

variable seen-set

variable recurs-set

variable t

variable max-j

variable j

: digits ( n — c-addr u ) 0 <# #s #> ;

: digit ( c-addr u — c-addr u n ) over c@ [char] 0 – ;

: recurs ( n — ) seen-set intersects recurs-set @ or recurs-set ! ;

: seen ( n — ) seen-set union ;

: analyze ( c-addr u — ) seen-set off recurs-set off begin dup while digit dup recurs seen 1 /string repeat 2drop ;

: recur ( c-addr u — f ) analyze recurs-set @ ;

: unique ( n — n ) dup digits recur if 1 j +! rdrop exit then ; ( filters numbers for uniqueness )

: j0 ( — ) 1 j ! ;

: initialize ( — ) t off j0 max-j off ;

: jumps ( — ) j @ max-j @ max max-j ! j0 ;

: total ( — ) 1 t +! ;

: stats ( — ) jumps total ;

: number ( n — n ) unique dup u. cr stats ;

: report ( — ) max-j @ . .” max jump” cr t @ . .” total numbers displayed” cr ;

: numbers ( — ) 1 begin number 1+ dup largest > until drop ;

: challenge ( — ) initialize numbers report ;

challenge

bye

To execute, paste the above code into “challenge.fs”, then execute “gforth challenge.fs” from the shell prompt.

#41 by

davidon June 29, 2008 - 3:20 amAnother Scala approach

class Counter(lower:Int, upper:Int) {

printMaxGapAndCount(filterDuplicates(new Range(lower, upper, 1)))

def hasNoDuplicate(charvals:Array[Char]):Boolean = {

charvals.takeWhile(charval => charvals.filter(el => el == charval).size == 1).size == charvals.size

}

def filterDuplicates(range:Range):List[Int] = {

range.toList.filter(num => hasNoDuplicate(num.toString.toArray))

}

def printMaxGapAndCount(list:List[Int]) = {

println(“count: ” + list.size + “, max gap: ” + list.map(el => list.dropWhile(num => num x > y).head)

}

}

new Counter(1,10000) results in count: 5274, max gap: 105 after about 5 minutes

#42 by

The real Mr. Funkon June 29, 2008 - 3:24 amAS3:

private const powers : Array = [ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 ];

private function doIt(max : Number) : void {

max = Math.min(max,999999999);

outer: for (var i : Number = 1; i 0) {

var remainder : uint = tmp % 10;

if (digits & powers[remainder])

continue outer;

digits += powers[remainder];

tmp /= 10;

}

trace(i);

}

}

#43 by

The real Mr. Funkon June 29, 2008 - 3:26 amRepost in html ๐

private const powers : Array = [ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512 ];

private function doIt(max : Number) : void {

max = Math.min(max,999999999);

outer: for (var i : Number = 1; i < max; i++) {

var tmp : uint = i;

var digits : uint = 0;

while (tmp > 0) {

var remainder : uint = tmp % 10;

if (digits & powers[remainder])

continue outer;

digits += powers[remainder];

tmp /= 10;

}

trace(i);

}

}

#44 by

Boni Gopalanon June 29, 2008 - 4:16 amWriting of the program was very simple with Java. The answer with 10K as the max limit is , a Jump of 124 : The jump from 9876 to 10K, a jump of 123 nos (All numbers from 9877 to 10000 are excluded hence a jump of 123). It was interesting to look at how the gap progression happened. There is a clear pattern and with this knowledge one can very trivially predict the biggest gap for numbers as big as google ๐

______________________________________________

The following is the test results of how the gap progression happened for a range of 1 to 1000000000

——————————————————-

T E S T S

——————————————————-

Running com.boni.challenge.service.TestSeriesGenerator

Lower:1, Higher :2 Difference :1

Lower:10, Higher :12 Difference :2

Lower:98, Higher :102 Difference :4

Lower:109, Higher :120 Difference :11

Lower:987, Higher :1023 Difference :36

Lower:1098, Higher :1203 Difference :105

Lower:9876, Higher :10234 Difference :358

Lower:10987, Higher :12034 Difference :1047

Lower:98765, Higher :102345 Difference :3580

Lower:109876, Higher :120345 Difference :10469

Lower:987654, Higher :1023456 Difference :35802

Lower:1098765, Higher :1203456 Difference :104691

Lower:9876543, Higher :10234567 Difference :358024

Lower:10987654, Higher :12034567 Difference :1046913

Lower:98765432, Higher :102345678 Difference :3580246

Lower:109876543, Higher :120345678 Difference :10469135

Lower:987654321, Higher :1000000000 Difference :12345679

Tests run: 2, Failures: 0, Errors: 0, Skipped: 0, Time elapsed: 41.883 sec

Results :

Tests run: 2, Failures: 0, Errors: 0, Skipped: 0

————————————————————————

BUILD SUCCESSFUL

————————————————————————

Total time: 44 seconds

Finished at: Sun Jun 29 16:44:34 GMT+05:30 2008

Final Memory: 16M/289M

————————————————————————

______________________________________________

#45 by

Assen Kolovon June 29, 2008 - 6:32 amA fast non-trivial readable Java solution is published on docs.google.com/Doc?id=ddn32vzw_25dqbrq2c4

With printing all numbers is commented out, it executes in 430ms on a MacBook.

The trick is to generate only the next good number – starting from the end see which is the first digit that can be incremented, then fill the rest with the smallest allowed number.

#46 by

DavidLGon June 29, 2008 - 7:53 amScala code that only visits valid numbers:

def numsWithDigits(len: Int, digs: Set[Char], leading:Boolean): Iterator[List[Char]] = {

if (len == 0) Iterator.single(Nil)

else {

for (c <- (if (leading) digs-‘0’+’ ‘ else digs).elements;

n <- numsWithDigits(len-1, digs-c, leading && c==’ ‘)) yield c :: n;

}

}

val nums = (for (x <- numsWithDigits(4, scala.collection.immutable.TreeSet((‘0’ to ‘9’).toList:_*), true);

str = x.mkString.trim if str.length > 0;

n = str.toInt if n > 0) yield n).toList;

printf(“Count: %d\n”, nums.length);

val (first, second, gap) =

nums.zip(nums.tail).map { case (x,y) => (x,y, y-x) }.reduceLeft((a,b)=>if (a._3 > b._3) a else b);

printf(“Biggest gap is %d between %d and %d\n”, gap, first, second);

#47 by

ravemanon June 29, 2008 - 8:37 amnice idea, however its pretty easy

#48 by

Bob Leeon June 29, 2008 - 11:05 amI further simplified and sped up my implementation. It’s down to 330ms for max=10,000,000,000. It recursively iterates through all possible values for each digit.

crazybob.org/BeustSequence.java.html

#49 by

Bob Leeon June 29, 2008 - 12:57 pmOut of curiosity, I ported my solution to C: crazybob.org/beust.c.html

Even when compiled using “gcc -O3”, the C version takes 532ms while the Java version only takes 475ms (335ms if you subtract Java startup time).

#50 by

chrisbon June 29, 2008 - 12:59 pmBrute force, 44ms on my 1.8 lappy:

Func include = i => {

var chars = i.ToString().ToCharArray();

return chars.Distinct().Count() == chars.Length;

};

var sequence = Enumerable.Range(1, 10000).Where(i => include(i)).ToArray();

var gap = sequence.Skip(1).Select((i, j) => i – sequence[j]).Max();

Console.WriteLine(“Count: {0,0}”, sequence.Length);

Console.WriteLine(“Max Gap: {0,0}”, gap);

#51 by

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

#52 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/

#53 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.

#54 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

#55 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.

#56 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.

#57 by

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

#58 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.

#59 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/

#60 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|

+—-+—+

#61 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.

#62 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.

#63 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;

}

#64 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;

}

#65 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;

}

#66 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

#67 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.

#68 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.

#69 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

#70 by

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

#71 by

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

#72 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.

#73 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 );

}

}

}

}

#74 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 )

#75 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/

#76 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.

#77 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.

#78 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.

#79 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).

#80 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

#81 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

#82 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).

#83 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).

#84 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;

}

}

#85 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);

}

}

}

}

}

#86 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,

#87 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

#88 by

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

#89 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,

#90 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.

#91 by

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

#92 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.

#93 by

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

I will followup soon with a kickass LOLCODE implementation soon ๐

#94 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

#95 by

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

#96 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)))

#97 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)).

#98 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/

#99 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,

#100 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

}

}

#101 by

Paulo Gasparon July 3, 2008 - 6:48 amI still have to run it on my usual hardware to see how much faster it is, but this is for sure faster and leaner than my previous solution:

public class BeustFastSequenceFinder {

private static final long LAST_NOREPS = 9876543210L;

private static final long[] POW10;

static {

POW10 = new long[11];

long xPow = 1;

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

POW10[i] = xPow;

xPow *= 10;

}

}

private final long m_maxValue;

private long m_maxJumpDelta;

private long m_maxJumpPreviousPrintedValue;

private long m_printCount;

private long m_lastPrintedValue;

public BeustFastSequenceFinder(final long maxValue) {

if (maxValue <= 0)

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

m_maxValue = maxValue;

}

public long getMaxJumpBegin() {

return m_maxJumpPreviousPrintedValue+1;

}

public long getMaxJumpSize() {

return m_maxJumpDelta-1;

}

public long getMaxValue() {

return m_maxValue;

}

public long getPrintCount() {

return m_printCount;

}

public void findNumbers() {

m_maxJumpDelta = Math.max(1, m_maxValue / 100);

m_maxJumpPreviousPrintedValue = 0;

m_lastPrintedValue = 0;

m_printCount = 0;

loopNext(0, (m_maxValue > LAST_NOREPS) ? LAST_NOREPS : m_maxValue, 10, 0);

final long xDelta = (m_maxValue+1) – m_lastPrintedValue;

if (xDelta > m_maxJumpDelta) {

m_maxJumpPreviousPrintedValue = m_lastPrintedValue;

m_maxJumpDelta = xDelta;

}

}

public long getMaxJumpEnd() {

return m_maxJumpPreviousPrintedValue + m_maxJumpDelta – 1;

}

protected void print(final long value) {

if (0 != value) {

final long xDelta = value – m_lastPrintedValue;

if (xDelta > m_maxJumpDelta) {

m_maxJumpPreviousPrintedValue = m_lastPrintedValue;

m_maxJumpDelta = xDelta;

}

m_lastPrintedValue = value;

++m_printCount;

// System.out.println(value);

}

}

private long loopNext(long nextValue, final long maxValue, final int digitIndex, final int leftmostMask) {

if (0 == digitIndex) {

int xUsedMask = leftmostMask;

for (int i = 0; (i < 10) && (nextValue <= maxValue); ++i, ++nextValue, xUsedMask >>= 1)

if (0 == (xUsedMask & 1))

print(nextValue);

return nextValue;

}

else {

if (0 == leftmostMask) {

nextValue = loopNext(nextValue, maxValue, digitIndex – 1, 0);

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

nextValue = loopNext(nextValue, maxValue, digitIndex – 1, (1 << i));

if (nextValue > maxValue)

return nextValue;

}

}

else {

final long xDigitPow10 = POW10[digitIndex];

int xUsedMask = leftmostMask;

for (int i = 0; i < 10; i++, xUsedMask >>= 1) {

if (0 != (xUsedMask & 1)) {

nextValue += xDigitPow10;

if (nextValue > maxValue)

return nextValue;

}

else {

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

if (nextValue > maxValue)

return nextValue;

}

}

}

return nextValue;

}

}

}

// Have Fun!

#102 by

Juan Manuelon July 3, 2008 - 9:01 amimport itertools

MAX=10000

# Using lists

nums = filter(lambda x: len(str(x)) == len(set(d for d in str(x))), range(1, MAX+1))

print “LIST”, nums

print “MAX”, max(map(lambda x,y: (x-y, y, x), nums[1:], nums[:-1]))

print “COUNT”, len(nums)

# With iterators and functional programming

# Remove initial dots

def mkseq(max):

….return itertools.ifilter(lambda x: len(str(x))==len(set(d for d in str(x))), xrange(1, max+1))

def mkdiff(max):

….curr, next = itertools.tee(mkseq(max))

….next.next()

….return itertools.imap(lambda x,y: (x-y, y, x), next, curr)

def max_count_step(x,y):

….max_, count_ = x

….return (max(max_, y), count_+1)

print “MAX, COUNT=”, reduce(max_count_step, mkdiff(MAX), ((0, 0, 0), 1))

# Results:

MAX, COUNT=((105, 8796, 8901), 5274)

#103 by

Peter Maciociaon July 3, 2008 - 9:27 amPython:

[x for x in xrange(10000) if len(str(x))==len(set(str(x)))]

#104 by

Bob Leeon July 3, 2008 - 9:47 am@Paulo: Same as above, 3ghz Mac Pro, Java 6 w/ -server.

#105 by

Paulo Gasparon July 3, 2008 - 10:06 am@Bob

I tested your (very interesting) algorithm at my laptop.

Yours is faster. Takes roughly 60% of mine’s time for the 10 Giga test.

However, it is missing the last Gap/Jump, because the last gap does not end at the max value boundary and you only collect the gap/jump data when you “print”.

Therefore I got results like this (both printed my way):

*** Bob Lee’s: ***

The largest power of 10…:

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

Total Displayed: 712,890

Biggest Jump: 104,691

Biggest Jump begin: 1,098,766

Biggest Jump end : 1,203,455

*** Paulo’s: ***

The largest power of 10…:

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

Total Displayed: 712,890

Biggest Jump: 123,457

Biggest Jump begin: 9,876,544

Biggest Jump end : 10,000,000

So, you are just missing a final gap check to get the last and bigger one.

Have fun,

PJG

#106 by

Sam Pullaraon July 3, 2008 - 11:06 am@PJG That last jump isn’t really. There are no more jumps because after that last begin it always has duplicate digits.

#107 by

Bob Leeon July 3, 2008 - 11:08 amI interpreted the biggest jump as being between two valid values (which 10^6 is not), but I suppose you could interpret it either way.

#108 by

Darmanion July 3, 2008 - 12:28 pmRuby one-liner (not counting the import):

require ‘enumerator’

puts (a=(1..10000).to_a.reject{|x| x.to_s.split(//).uniq!}), a.enum_cons(2).to_a.sort_by{|(b,c)|c-b}.last.inspect, a.inject(0){|s,n|s+n}

#109 by

Jonon July 3, 2008 - 2:02 pmIn Python

u = [x for x in range(1,10000) if len(str(x))==len(set(str(x)))]

gaps = [u[i+1]-u[i] for i in range(len(u)-1)]

print ‘number: ‘,len(nonrepeating) # 5274

print ‘biggest gap: ‘,max(gaps) # 105

#110 by Dennis Furey on July 3, 2008 - 2:29 pm

# solution in Ursala

#import nat

func = ^(nleq$^+ difference*typ,length)+ ~&triK2tkZ2FlS+ iota+successor; * ^lrhPX/~& %nP

answer = func 10000

#111 by

Paulo Gasparon July 3, 2008 - 3:11 pmYes, reading the original post it really looks open to both interpretations.

Anyway, changing Bob’s code to my interpretation is trivial and, obviously, has no impact on its to performance. I can’t imagine a more efficient solution (even if a couple of details could be added(*)).

(*) – Like always limiting the search to max <= 9876543210, since afterwards all numbers are repeated for base 10. But its number of digits limit does something like that too.

Have Fun,

#112 by

danon July 3, 2008 - 4:04 pmlisp

(let ((seq (loop for i from 1 to 1000 when

(= (parse-integer (remove-duplicates (write-to-string i))) i)

collect i)))

(list (length seq)

(reduce #’max (maplist #'(lambda (x) (if (cdr x) (- (cadr x) (car x)) 0)) seq))))

#113 by

Yifanon July 3, 2008 - 5:23 pm//a recursion one , use C

#include

#define N 10

int flag[N];

int number[N];

int lastNumber[N];

int maxdepth;

int max=0;

int this_num,last_num=20000000;

int run=1;

int count=0;

int max_begin, max_end;

//set your max value here;

int input_max=10000;

int recu(int depth)

{

int i;

if(depth==maxdepth)

{

this_num=0;

//get the value of current number

for(i=0;iinput_max)

{

run=0;

return;

}

//update max

if(max<this_num-last_num)

{

max=this_num-last_num;

max_begin=last_num;

max_end=this_num;

}

//store the last_num;

last_num=this_num;

//increase the counter by 1

count++;

}

else

{

//recursion to find the number

for(i=0;i<10 && run==1;i++)

{

if(!(depth==0 && i==0))

{

if(flag[i]==0)

{

//set flag

number[depth]=i;

flag[i]=1;

//recursion

recu(depth+1);

//reset flag

number[depth]=0;

flag[i]=0;

}

}

}

}

}

int main()

{

int i;

//set all flag to 0

for(i=0;i<N;i++)

flag[i]=0;

//start search for the number, maxdepth is actually the width of the number, i.e 45321, maxdepth = 5+1, or 564321, maxdepth=6+1

for(maxdepth=1;run==1;maxdepth++)

{

recu(0);

}

printf(“max:%d\n”, max);

printf(“begin, end: %d , %d\n”, max_begin, max_end);

printf(“count:%d\n”, count);

return 0;

}

#114 by

Yifanon July 3, 2008 - 5:29 pm//sorry for last post, the html tag covered some of the code, and that code is not complete

//the following code is complete

//a recursion one, using C

#include

#define N 10

int flag[N];

int number[N];

int lastNumber[N];

int maxdepth;

int max=0;

int this_num,last_num=20000000;

int run=1;

int count=0;

int max_begin, max_end;

//set your max value here;

int input_max=10000;

int recu(int depth)

{

int i;

if(depth==maxdepth)

{

this_num=0;

//get the value of current number

for(i=0;i<maxdepth;i++)

{

this_num=(this_num<<1)+(this_num<<3)+number[i];

}

//if larger than max, just abort

if(input_max<this_num)

{

run=0;

return;

}

//update max

if(max<this_num-last_num)

{

max=this_num-last_num;

max_begin=last_num;

max_end=this_num;

}

//store the last_num;

last_num=this_num;

//increase the counter by 1

count++;

}

else

{

//recursion to find the number

for(i=0;i<10 && run==1;i++)

{

if(!(depth==0 && i==0))

{

if(flag[i]==0)

{

//set flag

number[depth]=i;

flag[i]=1;

//recursion

recu(depth+1);

//reset flag

number[depth]=0;

flag[i]=0;

}

}

}

}

}

int main()

{

int i;

//set all flag to 0

for(i=0;i<N;i++)

flag[i]=0;

//start search for the number, maxdepth is actually the width of the number, i.e 45321, maxdepth = 5+1, or 564321, maxdepth=6+1

for(maxdepth=1;run==1;maxdepth++)

{

recu(0);

}

printf(“max:%d\n”, max);

printf(“begin, end: %d , %d\n”, max_begin, max_end);

printf(“count:%d\n”, count);

return 0;

}

#115 by Mauricio Fernandez on July 4, 2008 - 6:19 am

@Bob: interesting representation of the set of remaining digits.

I have nothing against imperative code in general (I use it often in OCaml),

but I decided to see how far a functional set could go. The resulting program

takes three additional lines of code and here’s how it compares to your

FastBeustSequence on an AMD Athlon 64 X2 6000+ (using Java 6):

$ time ./beust

Found 8877690 numbers under 10000000000.

Max jump: 104691357 (1098765432 — 1203456789).

real 0m0.273s

user 0m0.268s

sys 0m0.004s

$ time java -server TestBeustSequence 10000000000

count: 8877690

largest gap: 104691357 (1098765432..1203456789)

269ms

real 0m0.350s

user 0m0.328s

sys 0m0.008s

The difference is within the experimental error; I guess it’s a draw ๐

You can find the code at eigenclass.org/misc/beust.ml

The set of digits is represented with two lists (in a way reminiscent of a

functional queue), and all the operations are (amortized) O(1) and

non-destructive.

#116 by

joelon July 4, 2008 - 6:31 amsimpler ruby to to the basic stuff

(10..12).to_a.reject { |x| x.to_s.split(//).uniq! }

#117 by

Mathieu BORDASon July 4, 2008 - 8:11 amI found that challenge very interesting. I have an idea about finding the largest gap between two unvalid numbers. I tried that way:

I think that a very simple alorithm can generate all valid numbers (ie with no pair of symbols) simply in making the current one grow by the right. I mean: 10,12,13,14,15,16,17,18,19,20,21,23,24, etc.

We are to jump a gab when the unit just preceeds a symbol already used. So, the more the numbers used are near each other, the more the gab may be big. I mean: 4563 will goes to 4567 (gap of 4), but 4573 goes to 4576 (gap of 3). I think this is the way gap appears. So I tried to find a good combination, and I immediately found: 9876 which jumps over 9877, 9878, 9879, 988X, 989X, then 99XX, until 10234 (gap = 358). Ok, gap seems cool, but makes us go too far (over 10000). Trying that method with 3 symbols gives: 987 goes to 1023 with a gap of 36. I have a good feeling about that.

Sorry for my English, and for the lack of programming example.

Thanks.

Mathieu BORDAS, France

#118 by

Frank Bolanderon July 4, 2008 - 9:43 amProlog Version(Well, GNU Prolog)

checkit([]):-!.

checkit([H|T]):- \+memberchk(H,T),checkit(T).

dif([_|[]],[]).

dif([X,Y|T],R):-dif([Y|T],T2),

D is Y-X,

append([D],T2,R),!.

beust(Low,Hi):-

retractall(norpt(_)),

for(C,Low,Hi),

write_term_to_codes(X,C,[]),

checkit(X),

assertz(norpt(C)),

fail.

beust(_,_):-!.

printResults:-

bagof(X,norpt(X),R),

!,

length(R,Len),

dif(R,D),

max_list(D,M),

write(‘Count : ‘),write(Len),nl,

write(‘Max difference : ‘),write(M),nl,

write(‘Results ‘),write(R),nl.

printResults:-!.

main:- beust(98,120),printResults.

#119 by

Elias Pippingon July 4, 2008 - 12:49 pmHere’s one in awk.

function scan(num)

{

nlen = length(num);

for (j = 1; j <= nlen; j++) {

cmp = substr(num, j, 1);

for (i = j; i < nlen; i++)

if (index(substr(num, i+1, nlen-j+1), cmp))

return 0;

}

return 1;

}

function iter(max)

{

for (n=1; n<=max; n++)

if(scan(n))

print n;

}

BEGIN { iter(5440) }

#120 by

Bob Leeon July 4, 2008 - 12:55 pm@Mauricio: When I try to run your program, I get:

File “beust.ml”, line 19, characters 12-26:

Integer literal exceeds the range of representable integers of type int

#121 by

Bob Leeon July 4, 2008 - 1:47 pmI modified my test program to not allocate objects. Now it runs in 150ms for 10^10:

crazybob.org/FastBeustSequence.java.html

crazybob.org/TestFastBeustSequence.java.html

#122 by

Mauricio Fernandezon July 4, 2008 - 4:58 pmBob: you need a 64-bit ocamlopt.

I pushed the functional set some more.

eigenclass.org/misc/beust2.ml

Best of 5 runs:

$ time ./beust2

Found 8877690 numbers.

Max jump: 104691357 (1098765432 — 1203456789).

real 0m0.217s

user 0m0.216s

sys 0m0.000s

$ time java -server TestFastBeustSequence 10000000000

count: 8877690

largest gap: 104691357 (1098765432..1203456789)

207ms

real 0m0.309s

user 0m0.256s

sys 0m0.020s

The standard deviation is quite large, around 15ms (real time for OCaml,

System.nanoTime deltas for Java; a bit more for the latter) or so…

I guess an imperative structure is required for further improvements, but it’s

too late.

#123 by

Bob Leeon July 5, 2008 - 12:43 pmBest of 5 runs on my computer:

eigenclass.org/misc/beust2.ml:

$ time ./beust2

Found 8877690 numbers.

Max jump: 104691357 (-1048718216 — -944026859).

real 0m0.237s

user 0m0.233s

sys 0m0.004s

crazybob.org/FastBeustSequence.java.html:

$ time java TestFastBeustSequence 10000000000

count: 8877690

largest gap: 104691357 (1098765432..1203456789)

150ms

real 0m0.272s

user 0m0.233s

sys 0m0.042s

So, not counting Java startup overhead, we’re looking at 237ms (OCaml) vs 150ms (Java).

#124 by

Mark Mahieuon July 5, 2008 - 1:10 pmInteresting to see the effects of -client and -server on the Java versions. With -client (and Soylatte 1.0.2 on a MacBook Pro 2.16Ghz Core Duo) this one is faster than FastBeustSequence (though not as elegant):

slm888.com/snippets/Beust.java

slm888.com/snippets/BeustTest.java

$ java -client BeustTest 10

count: 8877690

max gap: 104691357 (1098765432..1203456789)

352ms

$ java -client TestFastBeustSequence 10000000000

count: 8877690

largest gap: 104691357 (1098765432..1203456789)

456ms

With -server they both have best run times of around 400ms.

#125 by Mauricio Fernandez on July 5, 2008 - 1:35 pm

The best times I can get after N (= a few dozen) runs are 205ms for Java

(without startup overhead), 212ms for OCaml with the functional set.

While my box runs the OCaml code a bit faster, yours is much better at Java.

I’m using this JVM:

java version “1.6.0_04”

Java(TM) SE Runtime Environment (build 1.6.0_04-b12)

Java HotSpot(TM) 64-Bit Server VM (build 10.0-b19, mixed mode)

I’ve compiled the OCaml program in a 32-bit jail with no substantial

difference in speed (it is meant to be compiled with a 64-bit ocamlopt though;

you can notice the integer overflow in the output you’re getting). Either

we’re observing a AMD vs. Intel discrepancy, or the 32-bit JVM is much faster

than the 64-bit one (even though 32-bit OCaml isn’t really faster than 64-bit,

on my machine). Not that it matters.

#126 by

bearophileon July 5, 2008 - 6:27 pmI have ported that fast Java code to C, it’s about twice faster on my PC:

codepad.org/wlz2Vaqn

#127 by

Aristotle Pagaltzison July 5, 2008 - 11:33 pmA nicer Perl version:

#!/usr/bin/perl

use strict; use warnings;

use List::Util qw(max);

use List::MoreUtils qw(pairwise);

my @num = grep { !/(.).*\1/ } 1 .. 10_000;

my $max_diff = max pairwise { $b – $a } (

$num[ 0 .. $#num – 1 ],

$num[ 1 .. $#num ],

);

print @num . “numbers, max diff $maxdiff\n”;

print “@num\n”;

#128 by

Unni Prasadon July 7, 2008 - 4:21 amHi, my code is very simple but are not getting through properly via this comment, Contact me via email if you are interested.

/*

* Author : Unni Prasad

* Email : unniready@gmail.com

* Date : July 07,2008

*/

public class Counter {

public static void main(String [] args)

{

int limit=10000;

int count=0,flag=0,number,jump=0,max_jump=0,max_jump_position=1;

int i,j,k,l;

int array[]=new int[5];

int answer[]=new int[10000];

for(i=0;i2)

jump=answer[count-1]-answer[count-2];

if(max_jump<jump){

max_jump=jump;

max_jump_position=count-1;

}

}

}

System.out.println(“The biggest jump was from “+answer[max_jump_position-1]+” to ”

+answer[max_jump_position]);

System.out.println(“The max jump was : “+max_jump);

System.out.println(“Total number counted : “+count);

}

}

/*Output

The biggest jump was from 1098 to 1203

The max jump was : 105

Total number counted : 5275

*/

#129 by

unni prasadon July 7, 2008 - 4:22 amHi, My codes are not getting through this comment, if you are interest contact me via email

/*

* Author : Unni Prasad

* Email : unniready@gmail.com

* Date : July 07,2008

*/

public class Counter {

public static void main(String [] args)

{

int limit=10000;

int count=0,flag=0,number,jump=0,max_jump=0,max_jump_position=1;

int i,j,k,l;

int array[]=new int[5];

int answer[]=new int[10000];

for(i=0;i2)

jump=answer[count-1]-answer[count-2];

if(max_jump<jump){

max_jump=jump;

max_jump_position=count-1;

}

}

}

System.out.println(“The biggest jump was from “+answer[max_jump_position-1]+” to ”

+answer[max_jump_position]);

System.out.println(“The max jump was : “+max_jump);

System.out.println(“Total number counted : “+count);

}

}

/*Output

The biggest jump was from 1098 to 1203

The max jump was : 105

Total number counted : 5275

*/

#130 by

Mark Mahieuon July 7, 2008 - 8:32 amFinal couple of tweaks to mine:

slm888.com/snippets/Beust.java

slm888.com/snippets/BeustTest.java

It now accepts a radix so you can try a larger range of values, eg base 11:

$ java BeustTest 10000000000 11

count: 62353010

max jump: 104690246 (10a9876543..1203456789)

1858ms

#131 by

Paulo Gasparon July 7, 2008 - 1:10 pm@Bob

The new method names for the Digit class are a readability improvement too – especially since your implementation is quite original / unusual.

@Mark

The radix thing is not so usefull since the maximum value without repeated digits is: 9876543210.

Above this value ALL integer numbers have repeated digits.

Have Fun,

#132 by

Mark Mahieuon July 7, 2008 - 2:14 pm@Paolo

That’s correct for base 10 numbers, but I’m applying the radix to the calculation as well, so in base 11, a9876543210 is the maximum value without repeating digits.

There are limits though. Eg. in hex, fedcba987654321 is the maximum non-repeating value it’s capable of finding since the data types I’m using limit it to values less than 2^63.

#133 by

Mark Mahieuon July 7, 2008 - 2:16 pm@Paulo

Oops, sorry I mis-typed your name on that last comment.

#134 by

Anonymouson July 7, 2008 - 3:40 pm@Mark Mahieu

Sorry, I had missed the multi-base “detail”.

And don’t hurry: that mistyping is quite common.

=;o)

#135 by

Wheelwrighton July 7, 2008 - 8:22 pmvar nums = (from n in Enumerable.Range(1, 10000)

where n.ToString().Select(c => c).Distinct().Count() == n.ToString().Length

select n).ToArray();

var gap = -1; for (int n = 1; n < nums.Length; n++) gap = Math.Max(gap, nums[n] – nums[n – 1]);

Response.Write(String.Format(“count: {0}, max gap: {1}”, nums.Length, gap));

Takes about 0.01sec on my old 3.2GHz Athlon. And since it is written in performant C# I don’t have to jump through hoops to optimize it.

#136 by

cavon July 8, 2008 - 4:31 am@Wheelwright

“Takes about 0.01sec on my old 3.2GHz Athlon. And since it is written in performant C# I don’t have to jump through hoops to optimize it.”

haha that’s not very impressive really, it’s barely faster than the Ruby one-liner…

Try to count up to 10000000000 with that code. See you in a couple days ๐ (if you can stand the disk trashing)

#137 by

Ananyo Banerjeeon July 8, 2008 - 5:12 ampublic class Puzzle

{

public static void main(String []args)

{

int max=new Integer(args[0]).intValue();

String digitString=null; //holds string representation of numbers.

boolean flag;

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

{

flag=true;

digitString=new Integer(i).toString();

//start of code for comparing digits of a number with each other

for(int strcount=0;strcount<digitString.length()-1;strcount++)

{

if(digitString.substring(strcount,strcount+1).equalsIgnoreCase(digitString.substring(strcount+1,strcount+2)))

{

flag=false;

}

else{

flag=true;

break;

}

}

//end of code for comparing digits of a number with each other

if(flag==true)

{

System.out.println(i);

}

}

}

}

#138 by

Ananyo Banerjeeon July 11, 2008 - 2:02 amSorry Cedric…The code in my previous comment is wrong and incomplete.I had posted the modifed code in my blog (ananyobanerjee.blogspot.com).Please have a look.

#139 by

Zach Beaneon July 12, 2008 - 4:48 pmI put a Common Lisp version here:

paste.lisp.org/display/63602

It does the 10,000 solution in 0.005 seconds.

#140 by

Muralion July 19, 2008 - 12:05 amNo solution using

* bash

* vi (remember vi is turing complete!)

#141 by

Tobyon August 5, 2008 - 8:24 pmA ‘lispier’ lisp solution (no iteration, just tail recursion) which also runs faster than any of my iterative solutions interestingly

paste.lisp.org/display/64850

#142 by

Sijin Josephon August 21, 2008 - 8:32 amclass Beust

{

public static void Run(int max)

{

System.Diagnostics.Debug.Assert(max > 1);

int maxGap = 0;

int last = 0;

int total = 0;

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

{

if (DoDigitsRepeat(i) == true)

continue;

Console.Write("{0}, ", i);

++total;

int gap = i – last;

maxGap = Math.Max(gap, maxGap);

last = i;

}

Console.WriteLine("\nTotal: {0}", total);

Console.WriteLine("Max Gap: {0}", maxGap);

}

private static bool DoDigitsRepeat(int num)

{

//Used to track which digits have already been encountered

int table = 0;

while (num > 0)

{

int digit = num % 10;

num = num / 10;

int index = 1 << digit;

if ((table & index) == index){

return true;

}

else{

table |= index;

}

}

return false;

}

}

#143 by

daniel lujanon August 21, 2008 - 11:50 am//javascript version (apply in c/c++,java,c#)

//using firebug over FF:

function check(x)

{

var x=x+”;

var z= 0

for( y in x) {

if( z & (1<<x[y])) return false

z |= (1<<x[y]);

}

return true;

}

for( var n =0 ;n<1000; n++)

if( check(n))

console.log(n)

#144 by

John Smithon August 30, 2008 - 8:46 pm#145 by Hatem Nassrat on August 30, 2008 - 9:14 pm

#!PYTHON

max = 10000

# Dual-brute-force, First attempt ———-

nums = [x for x in range(1,max+1) if len(list(str(x))) == len(set(str(x)))]

count = len(nums)

gaps = [(nums[i]-nums[i-1],i) for i in range(1,count)]

gaps.sort()

print nums

print count

i = gaps.pop()[1]

print ‘GAP:’,nums[i-1],’->’,nums[i]

#—- Refactored for effeciency.

count = last = 0

gap = (1,1)

nums = []

for x in range(1,max+1):

if len(list(str(x))) == len(set(str(x))):

nums.append(x)

count += 1

if last and x – last > gap[1] – gap[0]:

gap = (last,x)

last = x

print nums

print “\nCOUNTED:”, count

print “GAP :”, gap

#146 by

dr-steveon August 30, 2008 - 9:39 pmSo I’ll ask the obvious question: do leading zeroes count as repeated digits?

(Is that an African or a European swallow?)

#147 by

Keegan Carruthers-Smithon August 31, 2008 - 1:14 amThis is by no means the fastest way, but is done using list generators only

#!/usr/bin/env python

maximum = 10000

numbers = [a for a in range(1,maximum+1) if len(set(str(a))) == len(str(a))]

biggest_jump = max([numbers[i] – numbers[i-1] for i in range(1, len(numbers))])

print len(numbers), biggest_jump

you can also work out biggest_jump using zip

biggest_jump = max([b-a for a,b in zip(numbers, numbers[1:])])

#148 by

miranlon August 31, 2008 - 3:52 amghci> let xs = filter (\x -> let st = show x in st == nub st) [1..10000]

ghci> length xs

5274

ghci> maximum . map (abs . uncurry (-)) . zip xs . tail $ xs

105

#149 by

Saverioon August 31, 2008 - 4:10 amI don’t understand exactly the definition of the problem. What does brute-force mean? Linear respect to max?

I am pretty lazy to write the code. My high level solution is the following, which is NlogN complexity, where N = number of digits of _max_, power 10.

Actually it requires to subclass the standard library function of the binary tree, as as far as I know, there is no function in C/Java/Ruby to extract the left/right leaves of the tree.

tot_digits = number of digits of _max_

create an empty ordered binary tree

max_difference = 0

for all the permutations from 1 to 10^tot_digits:

if permutation <= _max_

put in the tree and extract left and right

if there is left and the difference with permutation is greater than max_difference, store

else if there is right and the difference with permutation is greater than max_difference, store

total_permutations = size of the tree

#150 by

vbgunzon August 31, 2008 - 10:29 am# a single line lambda, returns numbers in which no digit repeats itself

cunique = lambda x, y: [i for i in range(x,y) if len(set(str(i)))==len(str(i))]

print cunique(1, 10000)

#151 by

Ketilon September 4, 2008 - 8:37 amHere’s a simple, permutation-based Haskell solution:

Prelude> let perms 0 _ = [[]]; perms n xs = concat [ map (y:) (perms (n-1) (filter (/=y) xs)) | y <- xs]

Prelude> let numbers = filter ((/=’0′).head) $ concatMap (flip perms [‘0’..’9′]) [1..]

Prelude> take 100 numbers

[“1″,”2″,”3″,”4″,”5″,”6″,”7″,”8″,”9″,”10″,”12″,”13″,”14″,”15″,”16″,”17″,”18″,”19″,”20″,”21″,”23″,”24″,”25”,

“26”,”27″,”28″,”29″,”30″,”31″,”32″,”34″,”35″,”36″,”37″,”38″,”39″,”40″,”41″,”42″,”43″,”45″,”46″,”47″,”48″,”49″,”50″,

“51”,”52″,”53″,”54″,”56″,”57″,”58″,”59″,”60″,”61″,”62″,”63″,”64″,”65″,”67″,”68″,”69″,”70″,”71″,”72″,”73″,”74″,”75″,

“76”,”78″,”79″,”80″,”81″,”82″,”83″,”84″,”85″,”86″,”87″,”89″,”90″,”91″,”92″,”93″,”94″,”95″,”96″,”97″,”98″,

“102”,”103″,”104″,”105″,”106″,”107″,”108″,”109″,”120″,”123″]

(Sorry if somebody posted something like this already, and I missed it).

#152 by

noneon September 5, 2008 - 11:39 pmHere’s my dumb haskell solution:

import Data.List (nub)

nodup n = (sn == nub sn)

where sn = show n

beust = filter nodup [1..10000]

main = do

print $ maximum $ zipWith (-) (tail beust) beust

print (length beust)

#153 by

B Pon September 14, 2008 - 9:53 amBob’s solution in C# – 459 ms.

#154 by

Aaron Davieson September 22, 2008 - 6:55 pmk4:{(|/-‘:;#:)@\:&(=’).#:”(::;=:’)@\:$1+!x}

10.1 ms for 10,000, 141 ms for 100,000, 160 ms for 1,000,000

#155 by

Aaron Davieson September 22, 2008 - 6:57 pmOops, that should have been 1560 ms for 1,000,000

#156 by

RCon October 5, 2008 - 6:47 amhmmmmmmmmmmmmmmmmm,

It seems that SQL is not cool because no one has tried to solve this problem with SQL.

Here Oracle SQL:

select num, count_tot, (max(diff) over ()) max_diff

from

(

select num

, (count(*) over ()) count_tot

, (num-(lag(num) over (order by num))) diff

from

(

select level num

from dual

connect by level = length(num) -1

and length(replace(translate(num,’1′,’X’),’X’,null)) >= length(num) -1

and length(replace(translate(num,’2′,’X’),’X’,null)) >= length(num) -1

and length(replace(translate(num,’3′,’X’),’X’,null)) >= length(num) -1

and length(replace(translate(num,’4′,’X’),’X’,null)) >= length(num) -1

and length(replace(translate(num,’5′,’X’),’X’,null)) >= length(num) -1

and length(replace(translate(num,’6′,’X’),’X’,null)) >= length(num) -1

and length(replace(translate(num,’7′,’X’),’X’,null)) >= length(num) -1

and length(replace(translate(num,’8′,’X’),’X’,null)) >= length(num) -1

and length(replace(translate(num,’9′,’X’),’X’,null)) >= length(num) -1)

or (length(num)=1)

)

order by num

/

NUM COUNT_TOT MAX_DIFF

———- ———- ———-

1 738 11

2 738 11

3 738 11

4 738 11

5 738 11

6 738 11

7 738 11

8 738 11

9 738 11

10 738 11

12 738 11

13 738 11

…..

967 738 11

968 738 11

970 738 11

971 738 11

972 738 11

973 738 11

974 738 11

975 738 11

976 738 11

978 738 11

980 738 11

981 738 11

982 738 11

983 738 11

984 738 11

985 738 11

986 738 11

987 738 11

I used the Mikito way the generate the numbers.

If anyone knows how to use a regular expression as a filter to check for duplicate digits I could use this regular expressions instead of all the translate functions?

#157 by

RCon October 5, 2008 - 7:03 amMy sql statement becomes maimed, I can’t post it properly.

Beneath the connect by level…. one should insert:

)

where (length(replace(translate(num,’0′,’X’),’X’,null)) >= length(num) -1

#158 by

John Haugelandon December 8, 2008 - 1:57 pmThis one’s pretty easy.

is_unique_digital(X) ->

Base = int_to_list(X),

Uniqued = lists:usort(Base),

length(Base) = length(Uniqued).

non_repeating_digit_numbers_in(Low, High) ->

[ X || X <- lists:seq(Low,High), is_unique_digital(X) ].

#159 by

vidhuton February 27, 2009 - 6:52 am#!perl -wl

use strict;

my $max=10000;

my @nums;

my$count=1;

my $max_jump=1;

my $numbers=0;

while($count $max_jump;

}

}

$count++;

}

print join (” “,@nums);

print “\n $numbers , jump $max_jump”;

#160 by

vidhuton February 27, 2009 - 6:55 amthere is some problem i am not able to post my code

#161 by

Tracy Harmson May 28, 2009 - 5:58 pmA tacit solution in J:

ddr=: (#~ [: (= ~.&.>) 10&#.^:_1&.>)@: i.

#162 by

Tracy Harmson May 29, 2009 - 9:02 amI didn’t originally see all the requirements. Drawing on Danil’s code to improve my own, here’s a complete solution:

summarizeTo=: (bigjump, #) & cf

bigjump=: [: >./ 2-~/\]

cf =: ddr @: >: @: i.

ddr=: #~ ([:*./ [:~: 10&#.^:_1)”0

summarizeTo 1000

11 738

#163 by

Peter Markson May 30, 2009 - 7:20 pmMy Haskell solution is not as fast as some of the other optimized solutions here, nor as elegant as some of the unoptimized proposals, but it demonstrates memoization, recursive values and two ways to force strict evaluation. Compiled, it runs the whole list in about 2 seconds.

module Main where

import Data.List(foldl’)

import Data.Bits

data Result = Result !Int !Int !Int deriving Show

beust :: [(Int, Int)]

beust = tail digits ++ [(num * 10 + n, ds’) | (num, ds) <- beust, (n, d) <- digits, let ds’ = ds .|. d, ds’ /= ds]

digits = [(n, bit n) | n <- [0..9]]

calc m = foldl’ step (Result 0 0 0) . takeWhile (<= m) . map fst $ beust

where

step (Result maxJump count prev) n = Result (max maxJump (n – prev)) (count + 1) n

main = do

let (Result maxJump count _) = calc (9876543210)

putStrLn $ “max jump: ” ++ show maxJump

putStrLn $ “count: ” ++ show count

Further optimization suggestions welcome.

#164 by

F. Levineon December 4, 2009 - 7:45 pm3 lines of F#

let result = [0 .. 10000] |> List.filter (fun x -> x.ToString().ToCharArray() |> (fun (arr : _[]) -> arr.Length = (Set.ofArray arr).Count))

let max = List.max result

let gap = Seq.pairwise result |> Seq.map (fun (a,b) -> b-a) |> Seq.max

#165 by

Maduraon January 13, 2010 - 12:25 amI’ll publish this with more info in my blog @ madurax86.co.nr

well lets get down to business! I coded it in C and ran it on Ubuntu 9.10 system it tells that it took only 0.010 seconds to execute! Well my approach was different I didn’t convert the integers to string, I just let it be integers and did all comparing without any type conversion.

Here’s the code.

#include

#include

#include

clock_t startm, stopm;

#define START if ( (startm = clock()) == -1) {printf(“Error calling clock”);exit(1);}

#define STOP if ( (stopm = clock()) == -1) {printf(“Error calling clock”);exit(1);}

#define PRINTTIME printf( “\nExecution Time : %6.3f seconds.”, ((double)stopm-startm)/CLOCKS_PER_SEC);

#define MAX 10000

#define t 5

int main(){

int i,j=1,k=10,l,n,x,y,z,prev=0,jmp=0,bTop=0,bLow=0;

START;

for (i=10;i<MAX;i++){// drop 1 to 10 and count to MAX

if (i==k){ // keep track of number length

k=k*10;

j++; // j= number length

}

y=i;

int a[t]; // list to keep the digits of the number

for (l=0;l<j;l++){// go through the digit list

x=y%10; // get digit list by simple math, x gets the digit this starts from the end of the number

y=y/10;

z=0;

for (n=0;n<l;n++){

if (a[n]==x){z=1; break;}// check(1) one digit appears again

}

a[l]=x;// add new digit

if (z==1) break;// if the check(1) found duplicates get out of loop

}

if (z==0){

printf(“\n %d”,i);

x=i-prev;

if (jmp<x){ jmp=x; bTop=i; bLow=prev;}

prev=i;

}

}

STOP;

printf(“\nBiggest jump is %d: %d to %d”,bTop-bLow,bLow,bTop);

PRINTTIME;

}

#166 by

The Don January 4, 2011 - 7:05 pmif my assumption is not wrong about the your challenge, here’s the vb6 code, what you required are textbox as text1and command button as command1,suggestion are welcome:

Private Sub Command1_Click()

maxjump = 0

maxjumpno = “”

Counts = 0

prevnum = 0

For a = 1 To 10000

If a = 122 Then

jg = gg

End If

valid = True

For b = 1 To Len(a)

twin = 0

For c = 1 To Len(a)

If Mid(a, b, 1) = Mid(a, c, 1) Then

twin = twin + 1

End If

If twin >= 2 Then

valid = False

End If

Next c

Next b

If valid = True Then

Text1.Text = Text1.Text & a & “,”

Counts = Counts + 1

If Val(a) – prevnum >= maxjump Then

maxjump = Val(a) – prevnum

maxjumpno = a

End If

prevnum = a

End If

twin = 0

Next a

MsgBox “max jump = ” & maxjump & ” Max Jump Number = ” & maxjumpno & ” count = ” & Counts

End Sub

#167 by

Dineshon March 13, 2011 - 6:49 amhere is my solution using java–

/**

*

* @author Dinesh

*/

public class Main {

public static boolean isCorrect(int number){//this method returns true if the condition ok

boolean isOK = true;

String numberValues = number+””;

char array[] = numberValues.toCharArray();

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

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

if(array[i]==array[j]){

isOK = false;

break;

}

}

}

return isOK;

}

public static void main(String[] args) {

int total=0;

int previousValue = 0;

int maxGap = 0;

int max = 10000;

System.out.println("The numbers are —");

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

if (isCorrect(i)) {

int gap = i-previousValue;

if(maxGap “+i);

previousValue = i;

total += i;

}

}

System.out.println(“Maximum gap is — “+maxGap);

System.out.println(“The total is — “+total);

}

}