The best challenge (please read!)

**keyboard** · 06-25-2012, 11:29 AM

PHP Code:


<?php

$total = 0;

for ($i = 0; $i < 1000; $i++) {

    $total += $i;

    $array = str_split($i);

    for($v = 0; $v < count($array); $v++) {

        if(substr_count($i,$array[$v]) == 1) {

            echo $i . '<br />';

            break;

        }

    }

}

echo 'Total: ' . $total;

?>

Strips out numbers like 11, 22, 33 but not 101, 122, 262... Can anyone work out why???

**jscheuer1** · 06-25-2012, 03:19 PM

Originally Posted by 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.

I think it might have been in a thread calculating odds, perhaps in the PHP section, ring any bells? I don't think I contributed to that thread, but was lurking in it.

However, this challenge stipulates that we list all the good numbers and all the bad numbers. Unless I misunderstood that, we can't skip anything.

But, in the challenge author's blog there is a response page:

http://beust.com/weblog/2008/08/28/c...lenge-wrap-up/

where several or more elegant and not so elegant solutions are proffered in various languages. It looks to me, even though I'm no expert in those languages, that at least some of the solutions, even the ones he lists first as having impressed him in one way or another, seem to play fast and loose with the original stipulations. I see a number that don't look like they output anything.

Javascript and PHP will never approach the speeds of some of those other languages. C/C++ are probably about the industry standard for speed. That one called j I never heard of, neither had Cedric, but he checked and it's a real language. It might be faster.

And on that blog page, speed had become the main criteria, as he upped the ante to 10 to the tenth as the minimum number to count to. Just using 1000000, will crash Firefox with my javascript method. It gets the right answer, but the browser is useless after that. And it takes forever.

I've tightened the code up a little and noticed that it runs faster on Chrome, 1000000 runs OK there with the new code, but there's a noticeable lag of a few moments and refreshing the page causes a crash imminent warning, I selected to skip the page and went back to 10000, then it was OK again in Chrome:

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;
}
th {
	font: bold 95% sans-serif;
}
</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 start = 1, max = 10000, good = [], bad = [], gap = [0, 0], count, gapln, str, temp, i, ok;
	count = start - 1;
	while(count < max){
		ok = true;
		str = (++count).toString(10);
		temp = str.split('');
		i = temp.length;
		while(temp[--i]){
			if(str.indexOf(temp[i]) !== i){
				bad.push(str);
				ok = false;
				if(gap[1] < (gapln = count - good[good.length - 1])){
					gap = [count, gapln];
				}
				break;
			}
		}
		if(ok){good.push(str);}
	}
	return {
		start	: start,
		max	: max,
		gnum	: good.length,
		good	: good.join(', '),
		bnum	: bad.length,
		bad	: bad.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 Code Challenge from: ' + data.start + ' 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>

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

**jscheuer1** · 06-25-2012, 03:40 PM

Originally Posted by keyboard1333

PHP Code:


<?php

$total = 0;

for ($i = 0; $i < 1000; $i++) {

    $total += $i;

    $array = str_split($i);

    for($v = 0; $v < count($array); $v++) {

        if(substr_count($i,$array[$v]) == 1) {

            echo $i . '<br />';

            break;

        }

    }

}

echo 'Total: ' . $total;

?>

Strips out numbers like 11, 22, 33 but not 101, 122, 262... Can anyone work out why???

This logic:

Code:

if(substr_count($i,$array[$v]) == 1) {

in that loop checks each character. If it finds one that's unique it echoes the number. Because of that, numbers like 984 get echoed 3 times, 991 gets echoed once. 999 is skipped. 1000 is not considered, if it were it would echo once for the 1. 10 echoes twice.

Even if it worked, it doesn't completely fulfill the original challenge. Neither does this, but it fixes the above problem:

PHP Code:


<?php 

$total = 0; 

for ($i = 0; $i < 1001; ++$i) { 

    $total += $i; 

    $str = implode('', array_unique(str_split($i)));

    if($str == $i){

       echo $i . '<br />'; 

    } 

} 

echo 'Total: ' . $total; 

?>

**djr33** · 06-25-2012, 07:25 PM

However, this challenge stipulates that we list all the good numbers and all the bad numbers. Unless I misunderstood that, we can't skip anything.

You're right, John. These directions do suggest you do it in that way. And I'm not sure (I think the math is beyond me) how you could do this without stripping them out. I'm just saying that the harder version of this is to "plan ahead" rather than go through a second time.
In fact, the easiest way to do this is just with two loops: generate all numbers, then loop through all of them and decide good/bad. Done.
(You could also embed one in the other, but that's not necessary and could potentially make the logic a little complicated, as in the case of what keyboard did.)

**jscheuer1** · 06-26-2012, 12:08 AM

Originally Posted by djr33

You're right, John. These directions do suggest you do it in that way. And I'm not sure (I think the math is beyond me) how you could do this without stripping them out. I'm just saying that the harder version of this is to "plan ahead" rather than go through a second time.
In fact, the easiest way to do this is just with two loops: generate all numbers, then loop through all of them and decide good/bad. Done.
(You could also embed one in the other, but that's not necessary and could potentially make the logic a little complicated, as in the case of what keyboard did.)

In my revised edition, that's what I do 1 loop in a loop:

Code:

	while(count < max){
		ok = true;
		str = (++count).toString(10);
		temp = str.split('');
		i = temp.length;
		while(temp[--i]){
			if(str.indexOf(temp[i]) !== i){
				bad.push(str);
				ok = false;
				if(gap[1] < (gapln = count - good[good.length - 1])){
					gap = [count, gapln];
				}
				break;
			}
		}
		if(ok){good.push(str);}
	}

See post #12 for the full revised code.

But the real bottleneck here is javascript. Other languages have innate functions (like uniq, or similar under other names) that can do this stuff so much faster, and closer to machine level, rather than relying upon the browser's script engine.

In any language, it's my impression that an innate function is always faster than one you write in that language to replace it or create it if none exists. That's certainly true in javascript.

**djr33** · 06-26-2012, 06:31 AM

In any language, it's my impression that an innate function is always faster than one you write in that language to replace it or create it if none exists. That's certainly true in javascript.

I've gotten the impression that expert users believe they can write certain functions in a faster way than some of the defaults in PHP. But probably not all. I can certainly imagine that is true for JS, and probably for some of PHP and other languages. I'd guess that of course it's the general pattern rather than the other way, but in some cases (what about C++?) it would be equivalent if written with the same logic.

JS might be slower because it needs to parse it?

**jscheuer1** · 06-26-2012, 07:32 AM

I've never heard of a function written in javascript to replace native code that was faster than the native code, do you have any examples?

Parsing may be an issue in speed in some cases, not so much here because the code is short and sweet. It's the loops. You have to check every digit of every number that passes. Well, depending upon which direction you're checking the digits in, you can actually skip the first or last digit. By the time you get to it, if none of the others matched it, it's unique. But it's still a lot of checking per number once the numbers start getting larger/longer. And there seems to be in javascript a sort of 'loop decay'. Almost like a human doing a repetitive action would forget exactly what they're doing and slow down, or get bored, maybe even lose count.

Javascript just isn't built for speed though, for whatever reasons, and this is widely known. PHP isn't much better if at all. I fixed keyboard1333's code so it at least listed the 'good' numbers correctly. It bogs down around 1000000, just the way javascript does.

PHP and javascript are both runtime languages. For speed you need a compiled language. That's not enough on its own, the code still has to be well written, but it does seem to be a prerequisite.

**bernie1227** · 06-26-2012, 08:38 AM

Originally Posted by jscheuer1

I've never heard of a function written in javascript to replace native code that was faster than the native code, do you have any examples?

Parsing may be an issue in speed in some cases, not so much here because the code is short and sweet. It's the loops. You have to check every digit of every number that passes. Well, depending upon which direction you're checking the digits in, you can actually skip the first or last digit. By the time you get to it, if none of the others matched it, it's unique. But it's still a lot of checking per number once the numbers start getting larger/longer. And there seems to be in javascript a sort of 'loop decay'. Almost like a human doing a repetitive action would forget exactly what they're doing and slow down, or get bored, maybe even lose count.

Javascript just isn't built for speed though, for whatever reasons, and this is widely known. PHP isn't much better if at all. I fixed keyboard1333's code so it at least listed the 'good' numbers correctly. It bogs down around 1000000, just the way javascript does.

PHP and javascript are both runtime languages. For speed you need a compiled language. That's not enough on its own, the code still has to be well written, but it does seem to be a prerequisite.

Indeed, it seems that web based scripting languages aren't good for heavy number crunching, offline applications seem to be more appropriate for that kind of thing, just on that topic, I was wondering what you guys think each kind of language are more suitable for.
Bernie

**jscheuer1** · 06-26-2012, 07:39 PM

I don't know enough about all the various languages to really say. If I see a problem I generally can tell what might be good, if not best at dealing with it.

Assuming one wanted the output live on the web, what I would try with this one is to use PHP, but have it drop to the OS for a C or C++ app to do the math, which would pass back the info to PHP for display. I've done this before where I had an app for solving/generating sudoku. It output to the console, which PHP was able to pick up, format and echo to the page.

**bernie1227** · 06-26-2012, 08:47 PM

Originally Posted by jscheuer1

I don't know enough about all the various languages to really say. If I see a problem I generally can tell what might be good, if not best at dealing with it.

Assuming one wanted the output live on the web, what I would try with this one is to use PHP, but have it drop to the OS for a C or C++ app to do the math, which would pass back the info to PHP for display. I've done this before where I had an app for solving/generating sudoku. It output to the console, which PHP was able to pick up, format and echo to the page.

As far as I'm aware, the best language for very heavy number crunching, is MATLAB, which is used by a lot of mathematicians to do very big equations.
Bernie

Thread: The best challenge (please read!)

Thread Tools

Search Thread

Bookmarks

Bookmarks

Posting Permissions