Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling
 
PerlMonks  

Sorting challenge

by PerlSufi (Pilgrim)
on Jul 22, 2013 at 21:20 UTC ( #1045728=perlquestion: print w/ replies, xml ) Need Help??
PerlSufi has asked for the wisdom of the Perl Monks concerning the following question:

Hello Monks,
In a scheme of mine to suck less at perl, I am trying some coding challenges- so meta-hints are fine, too. This challenge requires me to take user input and sort it in ascending order. Each line should be greater than 0 and <= 1000000. The first number of user input, is the number of lines to follow and it should not be printed. Here is what I have so far. It tells me 'Time limit exceeded', when I submit- so I assume I'm not looping through this efficiently..
my @numbers = split(/\s+/, <>); while(<>) { last if ($_ == 0); last if ($_ >= 1000001); last if ($_ eq ''); push (@numbers, $_); } shift @numbers; my @sorted = sort {$a <=> $b} @numbers; foreach(@sorted){ print $_; }
I also tried making a subroutine for doing the sorting, and still got the same message. Any insight is greatly appreciated ;)

Comment on Sorting challenge
Download Code
Re: Sorting challenge
by tobyink (Abbot) on Jul 22, 2013 at 21:27 UTC

    This condition never happens:

    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
      Great, thanks tobyink. I'll give that a try
Re: Sorting challenge
by jeffa (Chancellor) 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"; }


    jeffa

    L-LL-L--L-LL-L--L-LL-L--
    -R--R-RR-R--R-RR-R--R-RR
    B--B--B--B--B--B--B--B--
    H---H---H---H---H---H---
    (the triplet paradiddle with high-hat)
    
      Thanks, jeffa. Good call. I'll try this out when I can
Re: Sorting challenge
by davido (Archbishop) 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.


    Dave

      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

        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.


        Dave

Re: Sorting challenge
by BillKSmith (Chaplain) 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.

    Bill
Re: Sorting challenge (Insertion sort)
by BrowserUk (Pope) on Jul 23, 2013 at 15:50 UTC

    Try:

    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.
      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!
        Unfortunately, that got a time limit exceeded, too.

        Then they are taking the piss.


        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.

      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. ;)


      Dave

        I have seen advice on codechef.com to optimize I/O, not to use cin/cout but scanf/printf instead in C++. Which probably means that they are not after the best algorithm but just highly optimized code.



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

        • they supply less than the number they said they would.

          How will cater for that?

        • Maybe they lied about the sie of the numbers also.

          How about if one of the numbers is 4e9?

        • And they didn't state that the numbers would be decimal ascii.

          Maybe we should cater for octal and hex; but what if they supply binary or base64 or ...?

        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.

        FWIW: this passed with a time of 4.56s. The main difference between this and failing attempts -- besides the correction for dups -- is preallocation of the array size:

        $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.
Re: Sorting challenge
by PerlSufi (Pilgrim) 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..

      They are using a really slow machine. A C version of the insertion sort that takes 0.7 seconds on my machine takes 2.5 seconds on theirs.


      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.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://1045728]
Approved by tobyink
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (5)
As of 2014-07-26 02:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (175 votes), past polls