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 dubek on June 28, 2008 - 1:08 am
In 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 szeryf on June 28, 2008 - 1:15 am
Perl:
#!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 dirkf on June 28, 2008 - 2:05 am
Javascript, 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 Logemann on June 28, 2008 - 2:15 am
Sounds like a Google interview question or something. 🙂 Am far too tired to “work” on that, but its a funny puzzler.
Marc
#7 by levi_h on June 28, 2008 - 2:16 am
Java (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_h on June 28, 2008 - 2:24 am
The 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 Henry on June 28, 2008 - 2:39 am
C#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 Kassube on 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 Kartha on June 28, 2008 - 4:59 am
Here 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 Janaudy on June 28, 2008 - 5:57 am
Cedric,
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 Janaudy on June 28, 2008 - 5:58 am
Cedric,
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 Dan on June 28, 2008 - 6:30 am
Thierry, 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 Dan on June 28, 2008 - 6:34 am
Here 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 dimitris on June 28, 2008 - 6:50 am
Brute 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 Dan on June 28, 2008 - 7:32 am
I 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 DeWitt on June 28, 2008 - 7:49 am
The following python generator also works:
(i for i in xrange(start, end) if len(str(i)) == len(set(str(i)))):
-DeWitt
#19 by Keith Henry on June 28, 2008 - 8:43 am
C#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 Kirkham on June 28, 2008 - 9:37 am
Another 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 Kirkham on June 28, 2008 - 9:39 am
No, I don’t want my email published on your web site. Please remove link.
#22 by Anonymous on June 28, 2008 - 10:00 am
A Scala version:
for (i <- 1 to 100000; s = i.toString; if HashSet[Char](s:_*).size == s.size) println(i)
#23 by Eugene Kuleshov on June 28, 2008 - 10:36 am
Java 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 Kuleshov on June 28, 2008 - 10:39 am
Cedric, 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 Janaudy on June 28, 2008 - 10:40 am
Dan,
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 Robin on June 28, 2008 - 11:06 am
Non 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 Janaudy on June 28, 2008 - 11:29 am
Following 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 Robin on June 28, 2008 - 11:55 am
Small 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 Almiray on June 28, 2008 - 2:28 pm
Waiting for someone to post a solution using Fan 😉
#30 by Charles Miller on June 28, 2008 - 3:49 pm
This problem is so much easier to solve in binary.
#31 by Ants Aasma on June 28, 2008 - 4:08 pm
A somewhat non-bruteforce functionally factored Python solution: pastebin.com/f63ce9880
#32 by Ants Aasma on June 28, 2008 - 4:09 pm
Sorry, pasted the wrong URL, the correct one is pastebin.com/f5cec4683
#33 by Ed Davies on June 28, 2008 - 5:30 pm
szeryf, 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 Engbrecht on June 28, 2008 - 6:30 pm
I’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 Cedric on June 28, 2008 - 6:49 pm
Eric’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 Johnson on June 29, 2008 - 12:51 am
solution based on searching the string space:
docs.google.com/View?docID=dhpjhcjh_14f9msp3c8
#38 by Bob Lee on June 29, 2008 - 1:52 am
Here’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 Lee on June 29, 2008 - 2:17 am
Make that 0.6s after a slight refactoring.
#40 by Samuel A. Falvo II on June 29, 2008 - 2:19 am
Please 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 david on June 29, 2008 - 3:20 am
Another 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. Funk on June 29, 2008 - 3:24 am
AS3:
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. Funk on June 29, 2008 - 3:26 am
Repost 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 Gopalan on June 29, 2008 - 4:16 am
Writing 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 Kolov on June 29, 2008 - 6:32 am
A 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 DavidLG on June 29, 2008 - 7:53 am
Scala 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 raveman on June 29, 2008 - 8:37 am
nice idea, however its pretty easy
#48 by Bob Lee on June 29, 2008 - 11:05 am
I 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 Lee on June 29, 2008 - 12:57 pm
Out 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 chrisb on June 29, 2008 - 12:59 pm
Brute 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 Lee on 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 Lee on June 29, 2008 - 5:10 pm
OK, 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 Wilson on June 30, 2008 - 7:04 am
A 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 ciju on June 30, 2008 - 7:45 am
Forgot to mention. The performance results are for limit of 10,000,000,000(ex: all possible).
#58 by Thierry Janaudy on June 30, 2008 - 8:15 am
Created 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 Danil on June 30, 2008 - 8:57 am
This 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 Lee on 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 Venable on June 30, 2008 - 9:32 am
Not 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 Cheatham on June 30, 2008 - 10:58 am
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;
}
#64 by Jason Cheatham on June 30, 2008 - 11:00 am
Oops:
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 Cheatham on June 30, 2008 - 11:07 am
public 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 Lee on June 30, 2008 - 11:31 am
Alright, 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 Kress on June 30, 2008 - 12:11 pm
This 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 Kress on June 30, 2008 - 12:17 pm
Never 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 Kirkham on June 30, 2008 - 5:07 pm
I 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 Lee on June 30, 2008 - 5:40 pm
@Bill Kress: Mine handles 10^10 in less than half a second.
#71 by Anonymous on July 1, 2008 - 5:03 am
factor-language.blogspot.com/2008/06/cedrics-code-challenge.html
#72 by Bill Kress on July 1, 2008 - 11:13 am
Yeah, 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 stinkyminky on July 1, 2008 - 11:30 am
Another 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 stinkyminky on July 1, 2008 - 11:47 am
My 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 Fischer on July 1, 2008 - 1:03 pm
As 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 Fischer on July 1, 2008 - 1:03 pm
BTW, 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 sidereal on July 1, 2008 - 5:16 pm
I’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 Gaspar on 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 Gaspar on July 1, 2008 - 9:00 pm
Sorry! 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 Lee on 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 Lee on 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 jdumb on July 1, 2008 - 11:30 pm
some 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 Thang on July 2, 2008 - 1:36 am
using 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 Gaspar on July 2, 2008 - 2:38 am
Slight 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 augustss on July 2, 2008 - 5:58 am
Simple 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 Lee on July 2, 2008 - 7:52 am
@Paulo: Both 9,876,543,211 and 10,000,000,000 contain dups.
#89 by Paulo Gaspar on 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 Spiewak on July 2, 2008 - 10:01 am
Another 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 Pullara on July 2, 2008 - 12:41 pm
Bob Lee’s version in Java is by far the best one I’ve seen.
#92 by Paulo Gaspar on 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 Deva on July 2, 2008 - 1:29 pm
http://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 Jim on July 2, 2008 - 9:19 pm
What, no Lisp submissions?!
#96 by sunwukong on July 2, 2008 - 10:20 pm
Well, 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 Lee on July 3, 2008 - 1:38 am
Since 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 Gaspar on 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 Card on July 3, 2008 - 6:17 am
Here 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 Gaspar on July 3, 2008 - 6:48 am
I 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 Manuel on July 3, 2008 - 9:01 am
import 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 Maciocia on July 3, 2008 - 9:27 am
Python:
[x for x in xrange(10000) if len(str(x))==len(set(str(x)))]
#104 by Bob Lee on July 3, 2008 - 9:47 am
@Paulo: Same as above, 3ghz Mac Pro, Java 6 w/ -server.
#105 by Paulo Gaspar on 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 Pullara on 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 Lee on July 3, 2008 - 11:08 am
I 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 Darmani on July 3, 2008 - 12:28 pm
Ruby 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 Jon on July 3, 2008 - 2:02 pm
In 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 Gaspar on July 3, 2008 - 3:11 pm
Yes, 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 dan on July 3, 2008 - 4:04 pm
lisp
(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 Yifan on 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 Yifan on 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 joel on July 4, 2008 - 6:31 am
simpler ruby to to the basic stuff
(10..12).to_a.reject { |x| x.to_s.split(//).uniq! }
#117 by Mathieu BORDAS on July 4, 2008 - 8:11 am
I 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 Bolander on July 4, 2008 - 9:43 am
Prolog 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 Pipping on July 4, 2008 - 12:49 pm
Here’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 Lee on 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 Lee on July 4, 2008 - 1:47 pm
I 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 Fernandez on July 4, 2008 - 4:58 pm
Bob: 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 Lee on July 5, 2008 - 12:43 pm
Best 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 Mahieu on July 5, 2008 - 1:10 pm
Interesting 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 bearophile on July 5, 2008 - 6:27 pm
I have ported that fast Java code to C, it’s about twice faster on my PC:
codepad.org/wlz2Vaqn
#127 by Aristotle Pagaltzis on July 5, 2008 - 11:33 pm
A 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 Prasad on July 7, 2008 - 4:21 am
Hi, 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 : [email protected]
* 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 prasad on July 7, 2008 - 4:22 am
Hi, My codes are not getting through this comment, if you are interest contact me via email
/*
* Author : Unni Prasad
* Email : [email protected]
* 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 Mahieu on July 7, 2008 - 8:32 am
Final 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 Gaspar on 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 Mahieu on 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 Mahieu on July 7, 2008 - 2:16 pm
@Paulo
Oops, sorry I mis-typed your name on that last comment.
#134 by Anonymous on 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 Wheelwright on July 7, 2008 - 8:22 pm
var 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 cav on 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 Banerjee on July 8, 2008 - 5:12 am
public 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 Banerjee on July 11, 2008 - 2:02 am
Sorry 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 Beane on July 12, 2008 - 4:48 pm
I put a Common Lisp version here:
paste.lisp.org/display/63602
It does the 10,000 solution in 0.005 seconds.
#140 by Murali on July 19, 2008 - 12:05 am
No solution using
* bash
* vi (remember vi is turing complete!)
#141 by Toby on August 5, 2008 - 8:24 pm
A ‘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 Joseph on August 21, 2008 - 8:32 am
class 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 lujan on 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 Smith on 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-steve on August 30, 2008 - 9:39 pm
So 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-Smith on August 31, 2008 - 1:14 am
This 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 miranl on August 31, 2008 - 3:52 am
ghci> 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 Saverio on August 31, 2008 - 4:10 am
I 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 vbgunz on 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 Ketil on September 4, 2008 - 8:37 am
Here’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 none on September 5, 2008 - 11:39 pm
Here’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 P on September 14, 2008 - 9:53 am
Bob’s solution in C# – 459 ms.
#154 by Aaron Davies on September 22, 2008 - 6:55 pm
k4:{(|/-‘:;#:)@\:&(=’).#:”(::;=:’)@\:$1+!x}
10.1 ms for 10,000, 141 ms for 100,000, 160 ms for 1,000,000
#155 by Aaron Davies on September 22, 2008 - 6:57 pm
Oops, that should have been 1560 ms for 1,000,000
#156 by RC on October 5, 2008 - 6:47 am
hmmmmmmmmmmmmmmmmm,
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 RC on October 5, 2008 - 7:03 am
My 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 Haugeland on December 8, 2008 - 1:57 pm
This 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 vidhut on 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 vidhut on February 27, 2009 - 6:55 am
there is some problem i am not able to post my code
#161 by Tracy Harms on May 28, 2009 - 5:58 pm
A tacit solution in J:
ddr=: (#~ [: (= ~.&.>) 10&#.^:_1&.>)@: i.
#162 by Tracy Harms on May 29, 2009 - 9:02 am
I 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 Marks on May 30, 2009 - 7:20 pm
My 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. Levine on December 4, 2009 - 7:45 pm
3 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 Madura on January 13, 2010 - 12:25 am
I’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 D on January 4, 2011 - 7:05 pm
if 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 Dinesh on March 13, 2011 - 6:49 am
here 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);
}
}