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 Ketil on September 4, 2008 - 8:37 am
Quote
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).
#2 by none on September 5, 2008 - 11:39 pm
Quote
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)
#3 by B P on September 14, 2008 - 9:53 am
Quote
Bob’s solution in C# – 459 ms.
#4 by Aaron Davies on September 22, 2008 - 6:55 pm
Quote
k4:{(|/-’:;#:)@\:&(=’).#:”(::;=:’)@\:$1+!x}
10.1 ms for 10,000, 141 ms for 100,000, 160 ms for 1,000,000
#5 by Aaron Davies on September 22, 2008 - 6:57 pm
Quote
Oops, that should have been 1560 ms for 1,000,000
#6 by RC on October 5, 2008 - 6:47 am
Quote
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?
#7 by RC on October 5, 2008 - 7:03 am
Quote
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
#8 by John Haugeland on December 8, 2008 - 1:57 pm
Quote
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) ].
#9 by vidhut on February 27, 2009 - 6:52 am
Quote
#!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”;
#10 by vidhut on February 27, 2009 - 6:55 am
Quote
there is some problem i am not able to post my code
#11 by Tracy Harms on May 28, 2009 - 5:58 pm
Quote
A tacit solution in J:
ddr=: (#~ [: (= ~.&.>) 10&#.^:_1&.>)@: i.
#12 by Tracy Harms on May 29, 2009 - 9:02 am
Quote
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
#13 by Peter Marks on May 30, 2009 - 7:20 pm
Quote
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.
#14 by F. Levine on December 4, 2009 - 7:45 pm
Quote
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
#15 by Madura on January 13, 2010 - 12:25 am
Quote
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;
}
#16 by The D on January 4, 2011 - 7:05 pm
Quote
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
#17 by Dinesh on March 13, 2011 - 6:49 am
Quote
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);
}
}