{ }codelper
query pipelines (LINQ, streams)recordsgroupingP0122

Top k per stage

Make the game log a record, and group, count and sort it with query pipelines (C# LINQ, Java streams) instead of loops. The first line has the number of entries n and k, and the next n lines have one entry each as "stage player score". A player may have played the same stage several times.
For each stage, a player's score is the single highest score they got on that stage. For each stage, order the players by score from high to low, and on equal scores by name in code order (ASCII, uppercase before lowercase). Print the number of stages on the first line. Then, for each stage in code order of the stage name, print one line "stage players name:score ...".
players is the number of different players who played that stage, followed by the first k players separated by spaces. If there are fewer than k players, list them all.
Names are case-sensitive, so Ann and ann are different players.

Input
1 ≤ n ≤ 5000, 1 ≤ k ≤ 10.
Stage names are 1 to 8 lowercase English letters, and there are at most 100 different stages.
Player names are 1 to 8 English letters, upper or lower case.
0 ≤ score ≤ 1,000,000,000 (integer)
Output
the number of stages, then one line per stage
Example 1 · stdin
6 2
cave ann 50
sky Bob 7
cave bob 70
cave ann 90
sky adam 7
cave Ann 70
stdout
2
cave 3 ann:90 Ann:70
sky 2 Bob:7 adam:7
Example 2 · stdin
5 3
moon zed 4
beach Zed 4
moon Zed 9
moon zed 9
moon eve 1
stdout
2
beach 1 Zed:4
moon 3 Zed:9 zed:9 eve:1
main.py
Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 2 languages

This problem takes only C# (LINQ) and Java (streams), which have query pipelines built in.
You have to group again inside each group.
C# uses another GroupBy(player) and Max inside GroupBy(stage); Java nests collectors, as in groupingBy(stage, TreeMap::new, toMap(player, score, Math::max)).
The first k are C# Take(k) and Java limit(k); if k is larger, they give as many as there are.
Five traps: (1) sorting the entries as they are, without grouping by player again, puts the same player in the ranking several times.
(2) Java groupingBy defaults to HashMap, so the order of stages is not defined (pass TreeMap::new).
C# GroupBy yields groups in order of first appearance, so it needs a separate OrderBy(g => g.Key).
(3) In Java, putting reversed() at the end, as in comparingInt(Best::score).thenComparing(Best::player).reversed(), reverses the whole comparison built so far, so the name order is reversed too.
Attach it right after the score: comparingInt(Best::score).reversed().thenComparing(Best::player).
(4) In C#, another OrderBy after OrderByDescending throws away the earlier sort and sorts again from scratch.
The second key is written with ThenBy.
(5) C# OrderBy / ThenBy compare strings by culture rules by default, which puts adam before Bob.
This problem uses code order (uppercase first), so pass StringComparer.Ordinal.
Java String.compareTo is code order to begin with.

JavaMain.java · 44 lines
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Comparator;import java.util.List;import java.util.Map;import java.util.TreeMap;import java.util.stream.Collectors; record Play(String stage, String player, int score) {} record Best(String player, int score) {} public class Main {    public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        String[] first = in.readLine().trim().split(" ");        int n = Integer.parseInt(first[0]), k = Integer.parseInt(first[1]);        List<Play> plays = new ArrayList<>();        for (int i = 0; i < n; i++) {            String[] p = in.readLine().trim().split(" ");            plays.add(new Play(p[0], p[1], Integer.parseInt(p[2])));        }         // 판으로 묶고(TreeMap: 판 이름 순서) → 판 안에서 선수마다 가장 높은 점수(toMap + Math::max)        Map<String, Map<String, Integer>> best = plays.stream()            .collect(Collectors.groupingBy(Play::stage, TreeMap::new,                Collectors.toMap(Play::player, Play::score, Math::max)));         StringBuilder out = new StringBuilder().append(best.size()).append('\n');        best.forEach((stage, players) -> {            String top = players.entrySet().stream()                .map(e -> new Best(e.getKey(), e.getValue()))                .sorted(Comparator.comparingInt(Best::score).reversed() // 점수만 거꾸로                    .thenComparing(Best::player))                       // 이름은 그대로                .limit(k)                .map(b -> b.player() + ":" + b.score())                .collect(Collectors.joining(" "));            out.append(stage).append(' ').append(players.size()).append(' ').append(top).append('\n');        });        System.out.print(out);    }}
C#Main.cs · 42 lines
using System;using System.Collections.Generic;using System.Linq;using System.Text; record Play(string Stage, string Player, int Score); class Program{    static void Main()    {        string[] first = Console.ReadLine()!.Trim().Split(' ');        int n = int.Parse(first[0]), k = int.Parse(first[1]);        var plays = new List<Play>();        for (int i = 0; i < n; i++)        {            string[] p = Console.ReadLine()!.Trim().Split(' ');            plays.Add(new Play(p[0], p[1], int.Parse(p[2])));        }         // 판으로 묶고 → 판 안에서 다시 선수로 묶어 가장 높은 점수 → 정렬해서 k명        var stages = plays            .GroupBy(r => r.Stage)            .OrderBy(g => g.Key, StringComparer.Ordinal) // 문화권 규칙이 아니라 코드 순서로            .Select(g =>            {                var ranked = g                    .GroupBy(r => r.Player)                    .Select(pg => (Player: pg.Key, Best: pg.Max(r => r.Score)))                    .OrderByDescending(x => x.Best)                    .ThenBy(x => x.Player, StringComparer.Ordinal)                    .ToList();                return (Stage: g.Key, Players: ranked.Count, Top: ranked.Take(k).Select(x => $"{x.Player}:{x.Best}"));            })            .ToList();         var sb = new StringBuilder().Append(stages.Count).Append('\n');        foreach (var s in stages)            sb.Append(s.Stage).Append(' ').Append(s.Players).Append(' ').Append(string.Join(" ", s.Top)).Append('\n');        Console.Write(sb);    }}