in reply to Re: Sorting challenge (Insertion sort)
in thread Sorting challenge

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];
}

[download]

If that exceeds the time limitation, I'm with BrowserUk; they're nuts; this is an O(n) solution. ;)


Dave

Replies are listed 'Best First'.
Re^3: Sorting challenge (Insertion sort)
by BrowserUk (Patriarch) on Jul 23, 2013 at 19:57 UTC
    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.
[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]

        Project Euler's challenges are at least usually well thought out, and you're unlikely to get rejected with reasonable code that should pass. But some of them can consume a fair amount of time on research, and that time might be better spent productively. ;)


        Dave

[reply]
Re^3: Sorting challenge (Insertion sort)
by BrowserUk (Patriarch) on Jul 24, 2013 at 12:02 UTC

    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;

    [download]
    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]

      Interesting. ...and a good idea as well. It surely saves a lot of copying to progressively larger containers. It's possible that the data-set was even designed to make this an issue.


      Dave

[reply]
        It's possible that the data-set was even designed to make this an issue.

        Could be. It is a 'simple' problem that is deceptively hard to accomplish given the constraints. Time in this case.

        Howver, I picked another of the easy tasks at random -- namely: TIDRICE -- and submitted the following:

        #! perl -slw
use strict;

## substitute <DATA> for <> in 3 places to test 

for( 1 .. <> ) {
    my %h;
    for( 1 .. <> ) {
        $h{ $_->[0] } = $_->[1] for [ split ' ', <> ];
    }
    my $score = 0;
    /\+/ and ++$score or --$score for values %h;
    print $score;
}
__DATA__
3
4
tilak +
tilak +
tilak -
tilak +
3
ratna +
shashi -
ratna -
3
bhavani -
bhavani +
bhavani -

        [download]

        which produces their exact required output from their sample input on my machine; but it is rejected as producing the wrong output.

        So, I'm not sure if that means I missed some subtly of the spec. or their testing is flawed.

        I haven't reached a conclusion about the site yet. Their UI certainly has some annoyances -- but hell, I've hung around here for 10+ years and this place is far from perfect :)

        And one can't but wonder if perlsufi pulled off a very subtle spam with this thread :)

        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]
Re^3: Sorting challenge (Insertion sort)
by PerlSufi (Friar) on Jul 23, 2013 at 19:57 UTC
    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^3: Sorting challenge (Insertion sort)
by hdb (Monsignor) on Jul 23, 2013 at 19:39 UTC

    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.

[reply]
[d/l]

In Section Seekers of Perl Wisdom