Advanced Search

Page 1 of 3 123 LastLast
Results 1 to 10 of 25

Thread: The best challenge (please read!)

  1. #1
    Join Date
    May 2012
    Location
    Hitchhiking the Galaxy
    Posts
    1,013
    Thanks
    47
    Thanked 139 Times in 139 Posts
    Blog Entries
    1

    Default The best challenge (please read!)

    Hiya guys,
    I came across this pretty little problem a while ago, and I was wondering if anyone here wanted to give it a crack.
    It was invented by a guy called Cedric beust, so here it is:
    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
    Anyone want a shot?
    Bernie

  2. #2
    Join Date
    Mar 2005
    Location
    SE PA USA
    Posts
    28,674
    Thanks
    43
    Thanked 3,125 Times in 3,091 Posts
    Blog Entries
    12

    Default

    Even going to just 1000, the biggest jump is 13, from 987 to 1000, not "4: 98 -> 102" as stated. If you're going higher, 1001 would be disqualified as well, etc.

    I've just about got this, but since part of the problem as stated appears wrong, I'm going to wait for clarification. Output to 1000 shows these numbers (among others) disqualified (the number after the colon is the length of the gap at that point for the current gap that each number to the left is a part of):

    988: 1
    989: 2
    990: 3
    991: 4
    992: 5
    993: 6
    994: 7
    995: 8
    996: 9
    997: 10
    998: 11
    999: 12
    1000: 13
    And, there's an awful lot of numbers that qualify, to output them all seems almost pointless. Giving the total number that qualify, and the total that don't and of course giving the largest gap seems more sensible. Going to 10000 would yield an awful lot of rejects too, why list them all?
    - John
    ________________________

    Show Additional Thanks: International Rescue Committee - Donate or: The Ocean Conservancy - Donate or: PayPal - Donate

  3. #3
    Join Date
    May 2012
    Location
    Hitchhiking the Galaxy
    Posts
    1,013
    Thanks
    47
    Thanked 139 Times in 139 Posts
    Blog Entries
    1

    Default

    Quote Originally Posted by jscheuer1 View Post
    Even going to just 1000, the biggest jump is 13, from 987 to 1000, not "4: 98 -> 102" as stated. If you're going higher, 1001 would be disqualified as well, etc.

    I've just about got this, but since part of the problem as stated appears wrong, I'm going to wait for clarification. Output to 1000 shows these numbers (among others) disqualified (the number after the colon is the length of the gap at that point for the current gap that each number to the left is a part of):



    And, there's an awful lot of numbers that qualify, to output them all seems almost pointless. Giving the total number that qualify, and the total that don't and of course giving the largest gap seems more sensible. Going to 10000 would yield an awful lot of rejects too, why list them all?
    Because beust said so

  4. #4
    Join Date
    Mar 2005
    Location
    SE PA USA
    Posts
    28,674
    Thanks
    43
    Thanked 3,125 Times in 3,091 Posts
    Blog Entries
    12

    Default

    Because he said the biggest gap is one of the smaller ones?
    - John
    ________________________

    Show Additional Thanks: International Rescue Committee - Donate or: The Ocean Conservancy - Donate or: PayPal - Donate

  5. #5
    Join Date
    May 2012
    Location
    Hitchhiking the Galaxy
    Posts
    1,013
    Thanks
    47
    Thanked 139 Times in 139 Posts
    Blog Entries
    1

    Default

    Quote Originally Posted by jscheuer1 View Post
    Because he said the biggest gap is one of the smaller ones?
    Interestingly enough, when he set the challenge, he had no idea how to do it himself.

    And yes
    Bernie

  6. #6
    Join Date
    Mar 2005
    Location
    SE PA USA
    Posts
    28,674
    Thanks
    43
    Thanked 3,125 Times in 3,091 Posts
    Blog Entries
    12

    Default

    Well, unless I missed something, this is nothing all that challenging, really:

    Code:
    <!DOCTYPE html>
    <html>
    <head>
    <title>Beustiality</title>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
    <style type="text/css">
    table {
    	border: 2px solid #ccc;
    }
    td {
    	border: 1px solid #555;
    }
    #good, #bad {
    	vertical-align: top;
    }
    </style>
    <script type="text/javascript">
    // Cedric Beust's Challenge Script (c)2012 John Davenport Scheuer
    // as first seen in http://www.dynamicdrive.com/forums/
    // username: jscheuer1 - This Notice Must Remain for Legal Use
    function beust(){
    	var count = 0, max = 10000, good = [], r = [], bad = {}, str, t, ok, gap = [0, 0];;
    	while(count < max){
    		ok = true;
    		str = (++count).toString(10);
    		t = str.split('');
    		for(var i = 0; i < t.length; ++i){
    			for (var j = t.length - 1; j > -1; --j){
    				if(j !== i && t[j] === t[i]){
    					bad[str] = count - good[good.length -1];
    					ok = false;
    					break;
    				}
    				if(!ok){break;}
    			}
    		}
    		if(ok){good.push(str);}
    	}
    	for(var p in bad){
    		if(gap[1] < bad[p]){
    			gap = [p, bad[p]];
    		}
    		r.push(p);
    	}
    	return {max: max, gnum: good.length, good: good.join(', '), bnum: r.length, bad: r.join(', '), biggest: gap[1] + ', from: ' + (gap[0] - gap[1] + 1) + ' to: ' + gap[0]};
    }
    </script>
    </head>
    <body>
    <table>
    <tr>
    <th colspan=2 id="title"></th>
    </tr>
    <tr>
    <th>Good</th><th>Bad</th>
    </tr>
    <tr>
    <td id="totg"></td><td id="totb"></td>
    </tr>
    <tr>
    <td id="good"></td><td id="bad"></td>
    </tr>
    </table>
    <script type="text/javascript">
    (function(){
    	var data = beust();
    	document.getElementById('title').innerHTML = 'Cedric\'s Challenge to: ' + data.max;
    	document.getElementById('totg').innerHTML = 'Total Good: ' + data.gnum;
    	document.getElementById('totb').innerHTML = 'Total Bad: ' + data.bnum + '<br>Largest gap was: ' + data.biggest + ', inclusive';
    	document.getElementById('good').innerHTML = data.good;
    	document.getElementById('bad').innerHTML = data.bad;
    })();
    </script>
    </body>
    </html>
    Demo:

    http://home.comcast.net/~jscheuer1/side/beust.htm

    But other languages are apparently much more efficient at math, see:

    http://beust.com/weblog/2008/08/28/c...lenge-wrap-up/
    Last edited by jscheuer1; 06-25-2012 at 07:34 AM. Reason: update code
    - John
    ________________________

    Show Additional Thanks: International Rescue Committee - Donate or: The Ocean Conservancy - Donate or: PayPal - Donate

  7. #7
    Join Date
    May 2012
    Location
    Hitchhiking the Galaxy
    Posts
    1,013
    Thanks
    47
    Thanked 139 Times in 139 Posts
    Blog Entries
    1

    Default

    Pretty nice,
    Good work John
    Bernie

  8. #8
    Join Date
    Mar 2005
    Location
    SE PA USA
    Posts
    28,674
    Thanks
    43
    Thanked 3,125 Times in 3,091 Posts
    Blog Entries
    12

    Default

    Actually there's an error in math for the starting number of the largest gap. Correcting that led to the elimination of 1 var and the simplification of another. And some time can be saved by breaking out of the loops as soon as ok becomes false. I'm going to edit my previous post for the changes.
    - John
    ________________________

    Show Additional Thanks: International Rescue Committee - Donate or: The Ocean Conservancy - Donate or: PayPal - Donate

  9. #9
    Join Date
    Mar 2006
    Location
    Illinois, USA
    Posts
    12,154
    Thanks
    260
    Thanked 690 Times in 678 Posts

    Default

    That's not too bad doing a loop where you generate each number then throw out the ones that are bad. It would be much harder (and probably mathematically interesting) doing this by looping through only the good numbers.
    I did something else recently that was similar. I don't remember exactly what the task was, but it was so much easier looping through all numbers then throwing them out when they failed a test rather than generating them 'correctly' the first time around.
    Then the trick can be making this recursive. That's where a second loop to throw out the bad ones becomes the real time saver for the programmer, although perhaps not the 'best' way to do it.

    I would've tried this today, but I was busy on another project. And now John has done it so that should be enough.
    Daniel - Freelance Web Design | <?php?> | <html>| espaŮol | Deutsch | italiano | portuguÍs | catalŗ | un peu de franÁais | some knowledge of several other languages: I can sometimes help translate here on DD | Linguistics Forum

  10. #10
    Join Date
    May 2012
    Location
    Hitchhiking the Galaxy
    Posts
    1,013
    Thanks
    47
    Thanked 139 Times in 139 Posts
    Blog Entries
    1

    Default

    Sure thing dj, it'll be interesting to see if anyone other than mods actually post an answer

Bookmarks

Posting Permissions

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