|
Re: Sorting challenge
by davido (Cardinal) on Jul 22, 2013 at 23:10 UTC
|
I suggest you read each line of code and decide what it is for. Follow the logic, and see if it makes sense.
- In your first line, why are you splitting on whitespace? Are you expecting a whitespace-delimited list of numbers? Why?
- while(<>): I thought user-input was supposed to be terminated after the number of items specified initially. Your while loop will continue until EOF.
- In your while loop, you're also reading a list of numbers, but instead of space-delimited, they're "\n" delimited.
- last if $_ eq ''; This will never be true, because you never chomped your input.
- shift @numbers; Now you're ignoring the input where the user presumably told you how many integers he was going to enter. Shouldn't you be using that number somewhere, like as one of the conditions of your while loop?
- foreach(@sorted) { print $_; } This will place all your output on a single line, with no space separating it. ...oh, except you never chomped, so each item will be printed to its own line, probably for the wrong reason. ;)
I was going to offer a more elegant (and working) solution, but it turns out that your specification is incomplete, and partially contradicts the code you demonstrated. So until that's straightened out, I'm a little hesitant to demonstrate a solution that might be misinterpreting what you're trying to accomplish.
| [reply]
[d/l]
[select] |
|
|
Great response davido. Your posts are always very well thought out. Each number needs to be on its own line. The input/output needs to look like:
#input
4
3
6
7
2
#output
2
3
6
7
| [reply]
[d/l] |
|
|
I'm still unclear on what's supposed to happen if you get input outside of (0,1000000]. I assume you don't need to prompt; the harness is not expecting any output except for the result. But what's supposed to happen on bad input?
Maybe you should just post the exact problem specification.
| [reply]
[d/l] |
|
|
|
|
|
Re: Sorting challenge
by tobyink (Canon) on Jul 22, 2013 at 21:27 UTC
|
last if ($_ eq '');
So your while loop just keeps going and going. Their test harness is expecting you to return a sorted list of numbers, but your script is just sitting there waiting for more input.
Your input loop should be something like:
chomp(my $count = <>);
my @numbers;
for (1 .. $count) {
chomp(my $line = <>);
die if $line < 1 || $line > 1_000_000;
push @numbers, $line;
}
package Cow { use Moo; has name => (is => 'lazy', default => sub { 'Mooington' }) } say Cow->new->name
| [reply]
[d/l]
[select] |
|
|
Great, thanks tobyink. I'll give that a try
| [reply] |
Re: Sorting challenge
by jeffa (Bishop) on Jul 22, 2013 at 21:35 UTC
|
Don't expect the user input to contain your exit condition. Instead, accept all user input (until EOF which terminates the program) and then filter the results.
chomp( my @input = <STDIN> );
for (sort { $a <=> $b } @input) {
next if /\D/;
last if $_ > 1_000_000;
print "$_\n";
}
| [reply]
[d/l]
[select] |
|
|
Thanks, jeffa. Good call. I'll try this out when I can
| [reply] |
Re: Sorting challenge
by BillKSmith (Monsignor) on Jul 23, 2013 at 04:02 UTC
|
Always prompt for input. Tell the user what you expect him to do. (e.g. Enter 6 numbers seperated by "Enter Key". Or Enter a list of numbers seperated by "Enter Key". Terminate with eof (ctrl-z)). This prevents most of the problems caused by the user not knowing that the program is waiting for him.
Even better, use a prompt module. In this case, it may be overkill, but it is worth learning how to use one.
| [reply] |
Re: Sorting challenge (Insertion sort)
by BrowserUk (Patriarch) on Jul 23, 2013 at 15:50 UTC
|
perl -nle"next if $.==1; $n[$_]=$_ }{ defined and print for @n" nums >
+nums2
If you need it in the form of a script rather than a one-liner, try: #!perl -l
<>;
$n[ $_ ]=$_ while <>;
defined and print for @n;
On my system it takes 1.59 seconds for 900,000 numbers: [16:53:01.85] C:\test>1045728 nums >nums2
[16:53:03.44] C:\test>
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]
[select] |
|
|
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] |
|
|
|
|
|
|
$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]
[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] |
|
|
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] |
Re: Sorting challenge
by PerlSufi (Friar) on Jul 23, 2013 at 20:13 UTC
|
On an interesting note, browsing through all submissions for that challenge using perl, none have been successful. All of them are either 'time limit exceeded' or wrong answer.. | [reply] |
|
|
| [reply] |
|
|
| [reply] |