# Thread: I Failed

1. Member
Join Date
Nov 2010
Posts
90
Rep Power
0

## I Failed

I tried a Challenge

Objective
25 years ago, a British computer magazine had a programming contest and this was one of the puzzles.

There are a large number of 9 digit integers in the range 123456789 to 987654321 where each digit only appears once. What is the 100,000th number in this sequence?

Example
The first number is 123456789, the second is 123456798, the third is 123456879 and so on. No digit can repeat so 122345675 is not a valid number in this sequence.

The problem was "Write a program in Ansi C, C++ or C# 2.0 (C# 1.0 is allowed) that outputs the 100,000th number as fast as possible. Use any algorithm, except you cannot pre-calculate the answer and then write a program that just prints the result. Your entry must calculate the number!".

Results
The correct answer was 358926471

i tried this in Java. i got 147028357 and it took about 20 secs or so to get that number.

the faster in c++ was 0.00000050521 secs

Heres the code i wrote.. and i did it all by myself :) i learnt alot about the language trying to figure this out. but still failed the challenge haha

there's obvioulsy something going wrong somewhere

Java Code:
```import java.util.*;
public class Challenge1 {

public static void main(String[] args) {
int startNumber = 123456789;
int count = 0;
ArrayList numSplit = new ArrayList();

while(count < 100000){
int num = startNumber;
//fill each ArrayList element with a number from num
while (num > 0) {
int digit = num % 10;
numSplit.add(digit);
num /= 10;
}
// find the double ups. if it finds a double up it returns 0, count += 0 is the same
// so count only goes up when it doesn't find a double up(when it returns 1)
count += findDoubles(numSplit);
//adds one more to the initial number, i orignally used just num and then found out
// when i added to the ArrayList it didn't copy the number but removed from
// num and into ArrayList
startNumber++;

//empties the arrayList and starts the process again
numSplit.clear();
}
System.out.println(startNumber);
}

//looks through each element andcompares itself to each  of the elements looking
// for double ups
public static int findDoubles(ArrayList n){
ArrayList numSplit = n;
for( int i = 0; i < numSplit.size(); i++ ){
for (int j = i+1; j < numSplit.size(); j++){
if(numSplit.get(i) == numSplit.get(j)){
return 0; // if double up leave loops and try next number
}

}
}
return 1;// if no double ups are found Add 1 to Count outside this method.
}
}```

2. Senior Member
Join Date
Feb 2009
Posts
312
Rep Power
12
Without thinking up any algorithms and using a brute force method, I was able to obtain the answer in just over 46 seconds.

I originally got your answer, but I realized I was allowing digits with the '0' character.

Here's my quick program.

Java Code:
```public class Tester {

public static void main(String[] args) {
long startTime = System.currentTimeMillis();
long baseNumber = 123456789l;
int i = 1;
while (i < 100000) {
baseNumber++;
if (isUnique(baseNumber)) {
i++;
}
}
System.out.println("Number: " + baseNumber);
System.out.println("End Time: " + (System.currentTimeMillis() - startTime));
}

private static boolean isUnique(long number) {
String numberString = String.valueOf(number);
for (int i = 0; i < numberString.length(); i ++) {
char c = numberString.charAt(i);
if (c == '0') {
return false;
}
if (numberString.lastIndexOf(c) != numberString.indexOf(c)) {
return false;
}
}
return true;
}

}```

3. Member
Join Date
Nov 2010
Posts
90
Rep Power
0
ooooo so how do i get rid of the 0's

4. Moderator
Join Date
Apr 2009
Posts
13,541
Rep Power
27
I think you can shave a smidge off here:
Java Code:
`if (numberString.lastIndexOf(c) != numberString.indexOf(c)) ...`
You already know indexOf(c) since it's "i", so simply compare with "i" and save some ticks.

5. Moderator
Join Date
Apr 2009
Posts
13,541
Rep Power
27
Originally Posted by maknib
ooooo so how do i get rid of the 0's
Look in isUnique() and do you see the extra check put in?

6. Member
Join Date
Nov 2010
Posts
90
Rep Power
0
in his version i do, i need to find a way fro mine seeing as my arrayList is filled with int

7. Moderator
Join Date
Apr 2009
Posts
13,541
Rep Power
27
Well, check for 0 instead of '0' for numAt i?

ETA: Do that check before the second loop, since there's no point doing that second loop if (numAt.get(i) == 0).

ETA2: Sorry, replace numAt with numSplit!
:)
Last edited by Tolls; 11-05-2010 at 02:47 PM.

8. Member
Join Date
Nov 2010
Posts
90
Rep Power
0
ooo OOHOOO it's taking alot longer.. maybe it will work :D

9. Member
Join Date
Nov 2010
Posts
90
Rep Power
0
it's taken about 3 mins so far and it's upto count 11,000 / 100,000 haha.. do i wait, see if i get the correct answer... i think so

10. Senior Member
Join Date
Feb 2009
Posts
312
Rep Power
12
Using my new computer, your method took just over 86 seconds. If you put the check in the right spots it should work.

I love this new machine.

11. Moderator
Join Date
Apr 2009
Posts
13,541
Rep Power
27
Sub 20 seconds, but this is a zippy machine (using StormyWaters method this is, give or take).

12. Member
Join Date
Nov 2010
Posts
90
Rep Power
0
i've got the check where you suggested. so far on this computer its taking over 6 mins :P still not even halfway there
BUT i just want to see if i got the right number so im going to let it run.

if i get the right number i can work on making it quicker :)

13. Using a bit more clever algorithm:

Java Code:
```import java.util.ArrayList;
import java.util.List;

public class T {

private static int fac(int n) {
return (n == 0)?1:n*fac(n-1);
}

public static List<Integer> permute(List<Integer> list, int r) {

int n= list.size();
int f= fac(n);

List<Integer> perm= new ArrayList<Integer>();

list= new ArrayList<Integer>(list);

for (list= new ArrayList<Integer>(list); n > 0; n--, r%= f) {

f/= n;
perm.add(list.remove(r/f));
}
return perm;
}

public static void main(String[] args) {
List<Integer> list= new ArrayList<Integer>();
for (int i= 1; i < 10; i++)
list.add(i);
System.out.println(permute(list, 99999));
}
}```
I didn't time it but it would surprise me if it took more than 0.01 secs.

kind regards,

Jos
Last edited by JosAH; 11-05-2010 at 03:51 PM.

14. Senior Member
Join Date
Feb 2009
Posts
312
Rep Power
12
Just trying to understand that algorithm is giving me a headache lol, but very nice.

15. Member
Join Date
Nov 2010
Posts
90
Rep Power
0
WOOO!! mine works i got the right answer :)

16. Originally Posted by StormyWaters
Just trying to understand that algorithm is giving me a headache lol, but very nice.
I once wrote a little article about all the fiddling. It's an extremely fast algoritm but an extremely clumsy implementation thereof.

kind regards,

Jos

17. Member
Join Date
Nov 2010
Posts
90
Rep Power
0
wow that is quick

18. Member
Join Date
Nov 2010
Posts
4
Rep Power
0
Originally Posted by JosAH
I once wrote a little article about all the fiddling. It's an extremely fast algoritm but an extremely clumsy implementation thereof.

kind regards,

Jos
The problem as written states that you can't just print the answer.
My “street read” of this is that you have to compute all permutations stopping at the 100,000th.
For example, is the following code a solution?
It runs in a fraction of a millisecond on a slow machine. It prints the correct answer:

List<Integer> l = new ArrayList<Integer>(Arrays.asList(new Integer[]{1,2,3,4,5,6,7,8,9}));

long startTime = System.nanoTime();

System.out.print(l.remove(99999 % 362880 / 40320 ));
System.out.print(l.remove(99999 % 40320 / 5040 ));
System.out.print(l.remove(99999 % 5040 / 720 ));
System.out.print(l.remove(99999 % 720 / 120 ));
System.out.print(l.remove(99999 % 120 / 24 ));
System.out.print(l.remove(99999 % 24 / 6 ));
System.out.print(l.remove(99999 % 6 / 2 ));
System.out.print(l.remove(99999 % 2 / 1 ));
System.out.print(l.remove(99999 % 1 / 1 ));

long runTime=System.nanoTime()-startTime;
System.out.println(String.format("\nRuntime=%d nanoseconds.", runTime));

Regards,
StanO

19. Originally Posted by StanO
The problem as written states that you can't just print the answer.
My “street read” of this is that you have to compute all permutations stopping at the 100,000th.
For example, is the following code a solution?
It runs in a fraction of a millisecond on a slow machine. It prints the correct answer:

List<Integer> l = new ArrayList<Integer>(Arrays.asList(new Integer[]{1,2,3,4,5,6,7,8,9}));

long startTime = System.nanoTime();

System.out.print(l.remove(99999 % 362880 / 40320 ));
System.out.print(l.remove(99999 % 40320 / 5040 ));
System.out.print(l.remove(99999 % 5040 / 720 ));
System.out.print(l.remove(99999 % 720 / 120 ));
System.out.print(l.remove(99999 % 120 / 24 ));
System.out.print(l.remove(99999 % 24 / 6 ));
System.out.print(l.remove(99999 % 6 / 2 ));
System.out.print(l.remove(99999 % 2 / 1 ));
System.out.print(l.remove(99999 % 1 / 1 ));

long runTime=System.nanoTime()-startTime;
System.out.println(String.format("\nRuntime=%d nanoseconds.", runTime));

Regards,
StanO
You algorithm is identical to mine; my version uses a loop while your version unraveled the loop.

kind regards,

Jos

20. Senior Member
Join Date
Feb 2010
Location
Waterford, Ireland
Posts
748
Rep Power
11
that algorithm was beautiful :D

Page 1 of 2 12 Last

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•