I Failed

Printable View

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• 11-05-2010, 03:06 PM
maknib
I Failed
I tried a Challenge

Quote:

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

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.         } }```
• 11-05-2010, 03:27 PM
StormyWaters
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.

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;         } }```
• 11-05-2010, 03:38 PM
maknib
ooooo so how do i get rid of the 0's
• 11-05-2010, 03:38 PM
Tolls
I think you can shave a smidge off here:
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.
• 11-05-2010, 03:39 PM
Tolls
Quote:

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?
• 11-05-2010, 03:42 PM
maknib
in his version i do, i need to find a way fro mine seeing as my arrayList is filled with int
• 11-05-2010, 03:44 PM
Tolls
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!
:)
• 11-05-2010, 03:49 PM
maknib
ooo OOHOOO it's taking alot longer.. maybe it will work :D
• 11-05-2010, 03:53 PM
maknib
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
• 11-05-2010, 03:56 PM
StormyWaters
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-05-2010, 04:01 PM
Tolls
Sub 20 seconds, but this is a zippy machine (using StormyWaters method this is, give or take).
• 11-05-2010, 04:01 PM
maknib
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 :)
• 11-05-2010, 04:13 PM
JosAH
Using a bit more clever algorithm:

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
• 11-05-2010, 04:18 PM
StormyWaters
Just trying to understand that algorithm is giving me a headache lol, but very nice.
• 11-05-2010, 04:28 PM
maknib
WOOO!! mine works i got the right answer :)
• 11-05-2010, 04:29 PM
JosAH
Quote:

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
• 11-05-2010, 04:45 PM
maknib
wow that is quick
• 11-19-2010, 05:56 PM
StanO
Quote:

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
• 11-19-2010, 06:34 PM
JosAH
Quote:

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
• 11-20-2010, 03:17 AM
al_Marshy_1981
that algorithm was beautiful :D
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last