|
Re^2: Sorting challenge (Insertion sort)
by davido (Cardinal) on Jul 23, 2013 at 18:32 UTC
|
This is an excellent approach, but there are two potential issues with the specific solution. In other words, the algorithm is great, but the implementation is not quite there yet. One issue is that the test harness is probably happily supplying an infinite stream of integers, or at least more of them than are specified in the first input. If time limit is exceeded, I would guess that the stream just keeps going.
The second issue is that there could be, and probably are, integers that show up multiple times in the input stream. They would be lost here. So modifying Buk's solution:
chomp( my $count = <> );
my @numbers;
$numbers[scalar <>]++ while $count--;
foreach my $number ( 0 .. $#numbers ) {
next unless defined $numbers[$number];
print "$number\n" for 1 .. $numbers[$number];
}
If that exceeds the time limitation, I'm with BrowserUk; they're nuts; this is an O(n) solution. ;)
| [reply]
[d/l] |
|
|
One issue is that the test harness is probably happily supplying an infinite stream of integers, or at least more of them than are specified in the first input.
Hm. I'll put my hands up to the dups issue -- easily correct as you've done -- but this "they might supply more than they said they would" issue I do not buy.
The spec says that the first line will tell you how many number are in the file. If they supply more than that; they lied. More formally, they broke the contract of the specification. The fault is their's not mine.
Now, I know many people will take the approach that have taken, and say; "Well, we can cater for this unspecified possibility and handle it at very little extra cost, so we'll do that. It's defensive programming. It's a little extra effort now to save effort later....". And I say: "Just say no to trying 'what-if' code design".
Sure you can cater for that possible future; but what if:
Once you stop taking them at their word and catering for all the things they didn't say; or those they might have told lies about; you're on a slippery slope to a over-engineered project that gets canceled for going over budget.
Just say no to trying to predict the future.
Anyone who thinks my attitude to this is "just laziness"; read Meyer on Design by Contract.
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply] |
|
|
Well said, BrowserUk. Maybe I should just try Project Euler instead :P
I learned a lot from all your responses and concluded that this is an obvious demonstration of how good you guys are at perl and how devoted you are to solving a problem. Giving a ++ to all of you
| [reply] |
|
|
|
|
$max = <>;
$#n = $max;
++$n[ $_ ] while <>;
defined $n[$_] and print "$_\n" x $n[$_] for 0 .. $#n;
exit 0;
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply]
[d/l] |
|
|
| [reply] |
|
|
|
|
|
|
|
|
|
|
| [reply]
[d/l] |
|
|
Unfortunately, it did.. I am considering taking a peek at an example solution. What you posted is pretty robust- I have no idea how that isn't working.
| [reply] |
Re^2: Sorting challenge (Insertion sort)
by PerlSufi (Friar) on Jul 23, 2013 at 16:50 UTC
|
Awesome, BrowserUk- thank you. Unfortunately, that got a time limit exceeded, too. You guys have all been quite awesome in your suggestions on this. Thanks again! | [reply] |
|
|
| [reply] |