The best challenge (please read!)

Printable View

Show 40 post(s) from this thread on one page

06-24-2012, 09:24 PM
bernie1227

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:

Quote:

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
06-24-2012, 10:33 PM
jscheuer1

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):

Quote:

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?
06-25-2012, 03:16 AM
bernie1227

:mad:

Quote:

Originally Posted by jscheuer1

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 :p
06-25-2012, 04:30 AM
jscheuer1

Because he said the biggest gap is one of the smaller ones?
06-25-2012, 04:34 AM
bernie1227

Quote:

Originally Posted by jscheuer1

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
06-25-2012, 05:50 AM
jscheuer1

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/
06-25-2012, 06:43 AM
bernie1227

Pretty nice,
Good work John
Bernie
06-25-2012, 07:15 AM
jscheuer1

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.
06-25-2012, 09:57 AM
djr33

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.
06-25-2012, 10:38 AM
bernie1227

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

Show 40 post(s) from this thread on one page