Page 1 of 2 12 LastLast
Results 1 to 20 of 23

Thread: I Failed

  1. #1
    maknib is offline Member
    Join Date
    Nov 2010
    Posts
    90
    Rep Power
    0

    Default 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. #2
    StormyWaters is offline Senior Member
    Join Date
    Feb 2009
    Posts
    305
    Rep Power
    6

    Default

    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. #3
    maknib is offline Member
    Join Date
    Nov 2010
    Posts
    90
    Rep Power
    0

    Default

    ooooo so how do i get rid of the 0's

  4. #4
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,755
    Rep Power
    19

    Default

    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. #5
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,755
    Rep Power
    19

    Default

    Quote Originally Posted by maknib View Post
    ooooo so how do i get rid of the 0's
    Look in isUnique() and do you see the extra check put in?

  6. #6
    maknib is offline Member
    Join Date
    Nov 2010
    Posts
    90
    Rep Power
    0

    Default

    in his version i do, i need to find a way fro mine seeing as my arrayList is filled with int

  7. #7
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,755
    Rep Power
    19

    Default

    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. #8
    maknib is offline Member
    Join Date
    Nov 2010
    Posts
    90
    Rep Power
    0

    Default

    ooo OOHOOO it's taking alot longer.. maybe it will work :D

  9. #9
    maknib is offline Member
    Join Date
    Nov 2010
    Posts
    90
    Rep Power
    0

    Default

    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. #10
    StormyWaters is offline Senior Member
    Join Date
    Feb 2009
    Posts
    305
    Rep Power
    6

    Default

    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. #11
    Tolls is offline Moderator
    Join Date
    Apr 2009
    Posts
    11,755
    Rep Power
    19

    Default

    Sub 20 seconds, but this is a zippy machine (using StormyWaters method this is, give or take).

  12. #12
    maknib is offline Member
    Join Date
    Nov 2010
    Posts
    90
    Rep Power
    0

    Default

    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. #13
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,310
    Blog Entries
    7
    Rep Power
    20

    Default

    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. #14
    StormyWaters is offline Senior Member
    Join Date
    Feb 2009
    Posts
    305
    Rep Power
    6

    Default

    Just trying to understand that algorithm is giving me a headache lol, but very nice.

  15. #15
    maknib is offline Member
    Join Date
    Nov 2010
    Posts
    90
    Rep Power
    0

    Default

    WOOO!! mine works i got the right answer :)

  16. #16
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,310
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by StormyWaters View Post
    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. #17
    maknib is offline Member
    Join Date
    Nov 2010
    Posts
    90
    Rep Power
    0

    Default

    wow that is quick

  18. #18
    StanO is offline Member
    Join Date
    Nov 2010
    Posts
    4
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    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. #19
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,310
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by StanO View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  20. #20
    al_Marshy_1981 is offline Senior Member
    Join Date
    Feb 2010
    Location
    Waterford, Ireland
    Posts
    748
    Rep Power
    5

Page 1 of 2 12 LastLast

Similar Threads

  1. JVM creation failed
    By RogerP in forum NetBeans
    Replies: 12
    Last Post: 10-08-2011, 09:33 PM
  2. failed to connect to DB
    By danghieu in forum New To Java
    Replies: 16
    Last Post: 05-25-2010, 11:27 AM
  3. my Quicksort attempt has failed
    By Jeremy8 in forum New To Java
    Replies: 4
    Last Post: 11-16-2009, 02:56 AM
  4. Failed in reading xml
    By gayathri_g in forum New To Java
    Replies: 0
    Last Post: 08-27-2009, 02:07 PM
  5. failed to connect to remote vm
    By plummer in forum Eclipse
    Replies: 1
    Last Post: 05-08-2009, 08:11 AM

Posting Permissions

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