30
\$\begingroup\$

A Stack Exchange script determines which five comments on questions or answers are initially seen on the main page of sites through the number of upvotes on them; the five comments with the highest number of votes are displayed. Your task is to recreate this behavior.

Write a full program or function taking input through STDIN, command-line args, or function arguments and prints or returns the top five comment scores. Input will be an array of integers representing the number of upvotes on the comments of some post. For instance, an input of

0, 2, 5, 4, 0, 1, 0

means that the first comment has no votes, the second one has two votes, the third has five, the fourth had four, etc. The order of the comment scores should remain the same in the output.

If the input contains five or fewer comment scores, then the output should contain nothing more than the ones given. If two or more comment scores are the same, the first score(s) should be displayed. You may assume that the input array will contain at least one comment score.

The numbers in the output should be easily distinguished (so 02541 for case 1 is invalid). Otherwise there are no restrictions on output format; the numbers may be separated by a space or newline, or they may be in list format, etc.

Test cases:

[0, 2, 5, 4, 0, 1, 0] -> [0, 2, 5, 4, 1]
[2, 1, 1, 5, 3, 6] -> [2, 1, 5, 3, 6]
[0, 4, 5] -> [0, 4, 5]
[1, 1, 5, 1, 1, 5] -> [1, 1, 5, 1, 5]
[0, 2, 0, 0, 0, 0, 0, 0] -> [0, 2, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0, 0] -> [0, 0, 0, 0, 1]
[5, 4, 2, 1, 0, 8, 7, 4, 6, 1, 0, 7] -> [5, 8, 7, 6, 7]
[6, 3, 2, 0, 69, 22, 0, 37, 0, 2, 1, 0, 0, 0, 5, 0, 1, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2] -> [6, 69, 22, 37, 5]

The last example was taken from this Stack Overflow question.

If possible, please provide a link in your post where your submission can be run online.

This is code golf, so the shortest code in bytes wins. Good luck!

\$\endgroup\$
2
  • \$\begingroup\$ Must we retain order? \$\endgroup\$ Jan 27, 2016 at 19:53
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ Yes. The order in which the integers appear should not change. \$\endgroup\$
    – TNT
    Jan 27, 2016 at 19:56

17 Answers 17

10
\$\begingroup\$

Jelly, 6 bytes

NỤḣ5Ṣị

Try it online! or verify all test cases at once.

How it works

NỤḣ5Ṣị    Main link. Input: A (list)

N         Negate (multiply by -1) all elements of A.
 Ụ        Grade the result up.
          This consists in sorting the indices of A by their negated values.
          The first n indices will correspond to the n highest vote counts,
          tie-broken by order of appearance.
  ḣ5      Discard all but the first five items.
    Ṣ     Sort those indices.
          This is to preserve the comments' natural order.
     ị    Retrieve the elements of A at those indices.
\$\endgroup\$
0
10
\$\begingroup\$

Python 2, 58 bytes

x=input()[::-1]
while x[5:]:x.remove(min(x))
print x[::-1]

Test it on Ideone.

How it works

list.remove removes the first occurrence if its argument from the specified list. By reversing the list x, we essentially achieve that it removes the last occurrence instead.

Thus, it suffices to keep removing the comment with the minimal amount of upvotes until a list of no more than five comments is reached. Afterwards, we reverse the list once more to restore the original order.

\$\endgroup\$
9
\$\begingroup\$

Pyth, 11 bytes

_.-_Q<SQ_5

We calculate the multiset intersection of the input (Q) with the five greatest elements in Q (in the order they appear in Q), then take the first five of those.

_ .-           Reverse of multiset difference
     _ Q       of reversed Q
     <         with all but last 5 elements of sorted Q
       S Q                   
       _ 5

Try it here.

\$\endgroup\$
3
  • \$\begingroup\$ <5SQ is equivalent to <SQ_5, which saves 1 byte. \$\endgroup\$ Jan 27, 2016 at 20:30
  • \$\begingroup\$ Nope. \$\endgroup\$
    – lirtosiast
    Jan 27, 2016 at 20:33
  • \$\begingroup\$ Interesting. I wonder why it's not implemented as b[:-a]... I think it even might've been that at some point. \$\endgroup\$ Jan 27, 2016 at 20:36
5
\$\begingroup\$

MATL, 16 bytes

tn4>?t_FT#S5:)S)

This uses current release (10.2.1), which is earlier than this challenge.

Try it online!

Explanation

          % implicitly get input
t         % duplicate
n         % number of elements
4>?       % if greater than 4...
  t       % duplicate
  _       % unary minus (so that sorting will correspond to descending order)
  FT#S    % sort. Produce the indices of the sorting, not the sorted values
  5:)     % get first 5 indices
  S       % sort those indices, so that they correspond to original order in the input
  )       % index the input with those 5 indices
          % implicitly end if
          % implicitly display
\$\endgroup\$
5
\$\begingroup\$

JavaScript, 74 65 62 61 bytes

3 bytes off thanks @user81655. 1 byte off thanks @apsillers.

f=a=>5 in a?f(a.splice(a.lastIndexOf(Math.min(...a)),1)&&a):a

f=a=>5 in a?f(a.splice(a.lastIndexOf(Math.min(...a)),1)&&a):a

document.write('<pre>' +
  '[0, 2, 5, 4, 0, 1, 0] -> ' + f([0, 2, 5, 4, 0, 1, 0]) + '<br>' +
  '[2, 1, 1, 5, 3, 6] -> ' + f([2, 1, 1, 5, 3, 6]) + '<br>' +
  '[0, 4, 5] -> ' + f([0, 4, 5]) + '<br>' +
  '[1, 1, 5, 1, 1, 5] -> ' + f([1, 1, 5, 1, 1, 5]) + '<br>' +
  '[0, 2, 0, 0, 0, 0, 0, 0] -> ' + f([0, 2, 0, 0, 0, 0, 0, 0]) + '<br>' +
  '[0, 0, 0, 0, 1, 0, 0, 0, 0] -> ' + f([0, 0, 0, 0, 1, 0, 0, 0, 0]) + '<br>' +
  '[5, 4, 2, 1, 0, 8, 7, 4, 6, 1, 0, 7] -> ' + f([5, 4, 2, 1, 0, 8, 7, 4, 6, 1, 0, 7]) + '<br>' +
  '[6, 3, 2, 0, 69, 22, 0, 37, 0, 2, 1, 0, 0, 0, 5, 0, 1, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2] -> ' + f([6, 3, 2, 0, 69, 22, 0, 37, 0, 2, 1, 0, 0, 0, 5, 0, 1, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2]) + '<br>' +
'</pre>')

\$\endgroup\$
0
5
\$\begingroup\$

Python 3, 76

Saved 9 bytes thanks to Kevin reminding me that I can abuse if statements in a list comp.

Saved 5 bytes thanks to DSM.

Pretty simple solution right now. Grab the top 5 scores and then parse through the list adding them to the result as we find them.

def f(x):y=sorted(x)[-5:];return[z for z in x if z in y and not y.remove(z)]

Here are my test cases if anyone wants them:

assert f([0, 2, 5, 4, 0, 1, 0]) == [0, 2, 5, 4, 1]
assert f([2, 1, 1, 5, 3, 6]) == [2, 1, 5, 3, 6]
assert f([0, 4, 5]) == [0, 4, 5]
assert f([0, 2, 0, 0, 0, 0, 0, 0]) == [0, 2, 0, 0, 0]
assert f([0, 0, 0, 0, 1, 0, 0, 0, 0]) == [0, 0, 0, 0, 1]
assert f([5, 4, 2, 1, 0, 8, 7, 4, 6, 1, 0, 7]) == [5, 8, 7, 6, 7]
assert f([6, 3, 2, 0, 69, 22, 0, 37, 0, 2, 1, 0, 0, 0, 5, 0, 1, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2]) == [6, 69, 22, 37, 5]
\$\endgroup\$
0
4
\$\begingroup\$

05AB1E, 12 11 bytes

Code:

E[Dg6‹#Rß\R

Explanation:

E           # Evaluate input
 [          # Infinite loop
  D         # Duplicate top of the stack
   g        # Get the length
    6‹#     # If smaller than 6, break
       R    # Reverse top of the stack
        ß\  # Extract the smallest item and remove it
          R # Reverse top of the stack
            # Implicit, print the processed array

Uses CP-1252 encoding.

\$\endgroup\$
4
\$\begingroup\$

CJam, 16 bytes

{ee{1=~}$5<$1f=}

An unnamed block (function) that takes an array and returns an array.

Test suite.

Explanation

ee   e# Enumerate the array, pairing each number with its index.
{    e# Sort by...
 1=  e#   The original value of each element.
 ~   e#   Bitwise NOT to sort from largest to smallest.
}$   e# This sort is stable, so the order tied elements is maintained.
5<   e# Discard all but the first five.
$    e# Sort again, this time by indices to recover original order.
1f=  e# Select the values, discarding the indices.
\$\endgroup\$
3
\$\begingroup\$

Bash + GNU utilities, 36

nl|sort -nrk2|sed 5q|sort -n|cut -f2

I/O formatted as newline-separated lists via STDIN/STDOUT.

Try it online.

\$\endgroup\$
3
\$\begingroup\$

Python, 68 bytes

lambda l,S=sorted:zip(*S(S(enumerate(l),key=lambda(i,x):-x)[:5]))[1]

Example run.

A lump of built-ins. I think the best way to explain is to run through an example.

>> l
[5, 4, 2, 1, 0, 8, 7, 4, 6, 1, 0, 7]
>> enumerate(l)
[(0, 5), (1, 4), (2, 2), (3, 1), (4, 0), (5, 8), (6, 7), (7, 4), (8, 6), (9, 1), (10, 0), (11, 7)]

enumerate turns the list into index/value pairs (technically an enumerate object).

>> sorted(enumerate(l),key=lambda(i,x):-x)
[(5, 8), (6, 7), (11, 7), (8, 6), (0, 5), (1, 4), (7, 4), (2, 2), (3, 1), (9, 1), (4, 0), (10, 0)]
>> sorted(enumerate(l),key=lambda(i,x):-x)[:5]
[(5, 8), (6, 7), (11, 7), (8, 6), (0, 5)]

The pairs are sorted by greatest value first, keeping the current order of index for ties. This puts at the front the highest-scored comments, tiebroken by earlier post. Then, the 5 best such comments are taken.

>> sorted(_)
   [(0, 5), (5, 8), (6, 7), (8, 6), (11, 7)]
>> zip(*sorted(_))[1]
   (5, 8, 7, 6, 7)

Put the top five comments back in posting order, and then remove the indices, keeping only the scores.

\$\endgroup\$
3
\$\begingroup\$

PowerShell v4, 120 97 bytes

param($a)$b=@{};$a|%{$b.Add(++$d,$_)};($b.GetEnumerator()|sort Value|select -l 5|sort Name).Value

Experimenting around, I found an alternate approach that golfed off some additional bytes. However, it seems to be specific to PowerShell v4 and how that version handles sorting of a hashtable -- it seems, by default, that in v4 if multiple Values have the same value, it takes the one with a "lower" Key, but you're not guaranteed that in v3 or earlier, even when using the ordered keyword in v3. I've not fully vetted this against PowerShell v5 to say if the behavior continues.

This v4-only version takes input as $a, then creates a new empty hashtable $b. We loop through all the elements of the input $a|%{...} and each iteration add a key/value pair to $b (done by pre-incrementing a helper variable $d as the key for each iteration). Then we sort $b based on Value, then select the -last 5, then sort by Name (i.e., the key), and finally output only the .Values of the resultant hash.

If fewer than 5 elements are entered, it will just sort on value, select the last five (i.e., all of them), re-sort on key, and output.


Older, 120 bytes, works in earlier versions

param($a)if($a.Count-le5){$a;exit}[System.Collections.ArrayList]$b=($a|sort)[-5..-1];$a|%{if($_-in$b){$_;$b.Remove($_)}}

Same algorithm as Morgan Thrapp's answer, which is apparently an indication that great minds think alike. :)

Takes input, checks if the number of items is less-than-or-equal-to 5, and if so outputs the input and exits. Otherwise, we create an ArrayList $b (with the exorbitantly lengthy [System.Collections.ArrayList] cast) of the top five elements of $a. We then iterate over $a and for each element if it's in $b we output it and then remove it from $b (and here's why we need to use ArrayList, as removing elements from an Array isn't a supported feature in PowerShell, since they're technically fixed size).

Requires v3 or greater for the -in operator. For an answer that works in earlier versions, swap $_-in$b for $b-contains$_ for a total of 126 bytes.

\$\endgroup\$
2
\$\begingroup\$

Haskell, 62 bytes

import Data.List
map snd.sort.take 5.sortOn((0-).snd).zip[0..] 

Usage example: map snd.sort.take 5.sortOn((0-).snd).zip[0..] $ [5, 4, 2, 1, 0, 8, 7, 4, 6, 1, 0, 7] -> [5,8,7,6,7].

How it works: augment each element with it's index, sort descending, take first 5 elements, sort by index and remove index.

\$\endgroup\$
2
\$\begingroup\$

PHP 5, 107 102

Saved 5 bytes thanks to @WashingtonGuedes

function p($s){uasort($s,function($a,$b){return$a<=$b;});$t=array_slice($s,0,5,1);ksort($t);return$t;}

Ungolfed

function p($scores) {
    // sort the array from high to low,
    // keeping lower array keys on top of higher
    // array keys
    uasort($scores,function($a, $b){return $a <= $b;});
    // take the top 5
    $top_five = array_slice($scores,0,5,1);
    // sort by the keys
    ksort($top_five);
    return $top_five;
}

Try it.

\$\endgroup\$
6
  • \$\begingroup\$ For 1 1 5 1 1 5, your submission produces an output of 1 5 1 1 5 instead of the correct 1 1 5 1 5. \$\endgroup\$
    – TNT
    Jan 28, 2016 at 4:13
  • \$\begingroup\$ It seems to behave differently for PHP 7.X, switch the PHP version to 5.6 or below. \$\endgroup\$
    – Samsquanch
    Jan 28, 2016 at 16:52
  • \$\begingroup\$ Gotcha, didn't notice the version number. :) \$\endgroup\$
    – TNT
    Jan 28, 2016 at 17:18
  • \$\begingroup\$ I didn't either at first. I'm not sure why that doesn't save what version used as well as the code. I'm also not sure why it doesn't work correctly on 7.X. \$\endgroup\$
    – Samsquanch
    Jan 28, 2016 at 17:36
  • \$\begingroup\$ @WashingtonGuedes Removing spaces saved me 5 bytes, but I'm not seeing any unnecessary semicolons that wouldn't throw an error? \$\endgroup\$
    – Samsquanch
    Jan 29, 2016 at 17:36
0
\$\begingroup\$

Ruby, 82 87 89 bytes

$><<eval($*[0]).map.with_index{|x,i|[i,x]}.sort_by{|x|-x[1]}[0,5].sort.map(&:last)

to call: ruby test.rb [1,2,2,3,4,5]

original submission - 56 bytes but fails on certain test cases & didn't support $stdin and $stdout

_.reduce([]){|a,x|a+=_.sort.reverse[0..4]&[x]if !a[4];a}

Explanation

$><<               # print to stdout
eval($*[0])        # evals the passed in array in stdin ex: [1,2,3,4]
.map.with_index    # returns an enumerator with indices
{|x,i|[i,x]}       # maps [index,value]
.sort_by{|x|-x[1]} # reverse sorts by the value
[0,5]              # selects the first 5 values
.sort              # sorts item by index (to find the place)
.map{|x|x[1]}      # returns just the values
\$\endgroup\$
4
  • \$\begingroup\$ Nice program. You might have to ask the OP about that though. I am not sure the input format is okay. \$\endgroup\$
    – Riker
    Jan 29, 2016 at 21:33
  • \$\begingroup\$ @RikerW it actually fails when there is a duplicate top # in the last indice, I'm modifying it now \$\endgroup\$
    – John
    Jan 29, 2016 at 22:02
  • \$\begingroup\$ @RikerW its fixed now, and it supports stdin and writes to stdout. \$\endgroup\$
    – John
    Jan 29, 2016 at 22:40
  • \$\begingroup\$ Okay. I like the input method though. I was just saying to ask @TNT about it. \$\endgroup\$
    – Riker
    Jan 29, 2016 at 22:57
0
\$\begingroup\$

Java 7, 155 bytes

import java.util.*;List c(int[]f){LinkedList c=new LinkedList();for(int i:f)c.add(i);while(c.size()>5)c.removeLastOccurrence(Collections.min(c));return c;}

Ungolfed & test-code:

Try it here.

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

class Main{
    static List c(int[] f){
        LinkedList c = new LinkedList();
        for (int i : f){
            c.add(i);
        }
        while(c.size() > 5){
            c.removeLastOccurrence(Collections.min(c));
        }
        return c;
    }

    public static void main(String[] a){
        System.out.println(Arrays.toString(c(new int[]{ 0, 2, 5, 4, 0, 1, 0 }).toArray()));
        System.out.println(Arrays.toString(c(new int[]{ 2, 1, 1, 5, 3, 6 }).toArray()));
        System.out.println(Arrays.toString(c(new int[]{ 0, 4, 5 }).toArray()));
        System.out.println(Arrays.toString(c(new int[]{ 1, 1, 5, 1, 1, 5 }).toArray()));
        System.out.println(Arrays.toString(c(new int[]{ 0, 2, 0, 0, 0, 0, 0, 0 }).toArray()));
        System.out.println(Arrays.toString(c(new int[]{ 0, 0, 0, 0, 1, 0, 0, 0, 0 }).toArray()));
        System.out.println(Arrays.toString(c(new int[]{ 6, 3, 2, 0, 69, 22, 0, 37, 0, 2, 1, 0, 0, 0, 5, 0, 1, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2 }).toArray()));
    }
}

Output:

[0, 2, 5, 4, 1]
[2, 1, 5, 3, 6]
[0, 4, 5]
[1, 1, 5, 1, 5]
[0, 2, 0, 0, 0]
[0, 0, 0, 0, 1]
[6, 69, 22, 37, 5]
\$\endgroup\$
0
\$\begingroup\$

Julia, 48 bytes

!x=x[find(sum(x.<x',2)+diag(cumsum(x.==x')).<6)]

Try it online!

How it works

The comment c1 has higher precedence than the comment c2 iff one of the following is true:

  • c1 has more upvotes than c2.
  • c1 and c2 have the same amount of upvotes, but c1 was posted earlier.

This defines a total ordering of the comments, and the task at hand is to find the five comments that have the highest precedences.

Instead of sorting the comments by precedence (which would alter their order, for each comment c, we count the comments that have a greater or equal precedence. We keep c if and only if this count is 5 or less.

To partially sort the comments by number of upvotes, we do the following. Let x be the column vector containing the vote counts. Then x' transposes x ‐ thus creating a row vector ‐ and x.<x' creates a Boolean matrix that compares each element of x with each element of xT.

For x = [0, 2, 5, 4, 0, 1, 0], this gives

<     0      2      5      4      0      1      0
0 false   true   true   true  false   true  false
2 false  false   true   true  false  false  false
5 false  false  false  false  false  false  false
4 false  false   true  false  false  false  false
0 false   true   true   true  false   true  false
1 false   true   true   true  false  false  false
0 false   true   true   true  false   true  false

By summing across rows (via sum(...,2)), we count the number of comments that have strictly more upvotes than the comment at that index.

For the example vector, this gives

4
2
0
1
4
3
4

Next, we count the number of comments with an equal amount of upvotes have been posted earlier than that comment. We achieve this as follows.

First we build an equality table with x.==x', which compraes the elements of x with the elements of xT. For our example vector, this gives:

=     0      2      5      4      0      1      0
0  true  false  false  false   true  false   true
2 false   true  false  false  false  false  false
5 false  false   true  false  false  false  false
4 false  false  false   true  false  false  false
0  true  false  false  false   true  false   true
1 false  false  false  false  false   true  false
0  true  false  false  false   true  false   true

Next, we use cumsum to calculate the cumulative sums of each columns of of the matrix.

1  0  0  0  1  0  1
1  1  0  0  1  0  1
1  1  1  0  1  0  1
1  1  1  1  1  0  1
2  1  1  1  2  0  2
2  1  1  1  2  1  2
3  1  1  1  3  1  3

The diagonal (diag) holds the count of comments that have an equal amount of upvotes and occur no later than the corresponding comment.

1
1
1
1
2
1
3

By adding the two row vectors we produced, we obtain the priorities (1 is the highest) of the comments.

5
3
1
2
6
4
7

Comments with priorities ranging from 1 to 5 should be displayed, so we determine their indices with find(....<6) and retrieve the corresponding comments with x[...].

\$\endgroup\$
0
\$\begingroup\$

Python 3.5, 68 bytes

f=lambda x,*h:x and x[:sum(t>x[0]for t in x+h)<5]+f(x[1:],*h,x[0]+1)

No match for my Python 2 answer, but only three bytes longer than its port to Python 3, and I think it's different enough to be interesting.

I/O is in form of tuples. Test it on repl.it.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.