Exercise 7

June 1, 2018

This must be somebody’s homework:

You are given an input file containing lines with three pipe-separated fields; the first field is a student number (a positive integer), the second field is a class name (a string), and the third field is the grade the student received for the class (a non-negative integer, no greater than 100):

22|Data Structures|45
26|Data Structures|72
23|Data Structures|61

You are to output a list of class names along with the grade earned by the lowest-numbers student in each class. For instance, given the above data, the output for Data Structures is 45 corresponding to student 22 (with student number lower than 23 or 26, who also took Data Structures) and the output for English is 81 corresponding to student 21 (with student number lower than 22 or 23, who also took English).

Your task is to write a program to produce the requested output. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


Pages: 1 2

11 Responses to “Exercise 7”

  1. chaw said

    Here is a hashing-based solution in standard R7RS Scheme and a few
    popular SRFIs.

    (import (scheme base)
            (scheme write)
            (scheme file)
            (only (srfi 1) first second third)
            (only (srfi 8) receive)
            (only (srfi 13) string-tokenize)
            (only (srfi 14)
                  char-set-complement char-set)
            (only (srfi 69)
                  make-hash-table hash-table-update!/default hash-table-walk))
    (define parse-line
      (let ((token-char-set (char-set-complement (char-set #\|))))
        (lambda (str)
          (let ((toks (string-tokenize str token-char-set)))
            (list (string->number (first toks))
                  (second toks)
                  (string->number (third toks)))))))
    (define (ex7 in-file-name)
      (let ((ht (make-hash-table string=?)))
        (with-input-from-file in-file-name
          (lambda ()
            (let loop ((line (read-line)))
              (if (eof-object? line)
                  (hash-table-walk ht
                                   (lambda (k v)
                                     (for-each display (list k " " (second v)))
                  (receive (id cname score) (apply values (parse-line line))
                    (hash-table-update!/default ht
                                                (lambda (id+score)
                                                  (if (< id (first id+score))
                                                      (list id score)
                                                (list id score))
                    (loop (read-line)))))))))
    (ex7 "input101.txt")

  2. Daniel said

    Here’s a solution using Unix utilities.

    sort data.txt -t'|' -k2,2 -k1,1n | awk -F'|' '{if (a[$2]++ == 0) print $2,$3;}'


    Data Structures 45
    English 81
  3. Daniel said

    Here’s a solution in Python.

    import sys
    if len(sys.argv) != 2:
      sys.stderr.write("Usage: {} <FILE>".format(sys.argv[0]))
    with open(sys.argv[1]) as f:
      D = dict()
      for line in f.readlines():
        student_id, class_name, grade = line.strip().split("|")
        student_id = int(student_id)
        grade = int(grade)
        if not class_name in D or student_id < D[class_name][0]:
          D[class_name] = (student_id, grade)
      for class_name, (_, grade) in D.items():
        print(class_name, grade)


    Data Structures 45
    English 81
  4. sbocq said

    Bash (no Awk) solution.

    sort -t'|' -k1,1n data.txt|sort -s -t'|' -k2,2 -u|cut -d'|' -f2-|tr '|' ' '


    Data Structures 45
    English 81

  5. sbocq said


    (doseq [[_ class grade] (->> (line-seq (clojure.java.io/reader "data.txt"))
                                 (map #(clojure.string/split % #"\|"))
                                 ;; sort and then partition by class
                                 (sort-by second)
                                 (partition-by second)
                                 ;; keep row with smallest student number in each partition
                                 (map (fn [part]
                                        (first (sort-by #(read-string (first %)) part)))))]
      (println class grade))


    Data Structures 45
    English 81

  6. Globules said

    A Haskell solution.

    import Data.List (groupBy, sortBy)
    import Data.List.Split (splitOn)
    import Data.Monoid ((<>))
    import Data.Ord (comparing)
    data Grade = Grade { stuId  :: Int
                       , course :: String
                       , grade  :: Int
    gradeFrom :: String -> Grade
    gradeFrom s = let [sId, sCourse, sGrade] = splitOn "|" s
                  in Grade (read sId) sCourse (read sGrade)
    showGrade :: Grade -> String
    showGrade g = course g ++ " " ++ show (grade g)
    courseGradesForLowestStuId :: [Grade] -> [Grade]
    courseGradesForLowestStuId = map head . groupBy sameCourse . sortBy courseStuId
      where courseStuId g1 g2 = comparing course g1 g2 <> comparing stuId g1 g2
            sameCourse g1 g2 = course g1 == course g2
    main :: IO ()
    main = do
      gs <- courseGradesForLowestStuId . map gradeFrom . lines <$> getContents
      mapM_ (putStrLn . showGrade) gs
    $ ./grades < grades.txt
    Data Structures 45
    English 81
  7. Daniel said

    Here’s a solution in C.

    #include <search.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    typedef unsigned int uint;
    typedef struct {
      uint id;
      uint grade;
    } datum_t;
    int main(int argc, char* argv[]) {
      if (argc != 2) {
        fprintf(stderr, "Usage: %s <FILE>\n", argv[0]);
        return EXIT_FAILURE;
      FILE* fp = fopen(argv[1], "r");
      if (!fp) {
        fprintf(stderr, "%s: Error reading file\n", argv[1]);
        return EXIT_FAILURE;
      size_t n_lines = 0;
      char c;
      while ((c = fgetc(fp)) != EOF) {
        n_lines += c == '\n';
      char** courses = NULL;
      datum_t* data = NULL;
      size_t n = 0;
      char* line = NULL;
      size_t linecap = 0;
      ssize_t linelen;
      ENTRY item;
      ENTRY* found_item;
      while ((linelen = getline(&line, &linecap, fp)) > 0) {
        char* _line = line;
        uint id = atoi(strsep(&_line, "|"));
        char* course = strsep(&_line, "|");
        uint grade = atoi(strsep(&_line, "\n"));
        item.key = course;
        if ((found_item = hsearch(item, FIND)) == NULL) {
          courses = realloc(courses, n * sizeof(char*));
          data = realloc(data, n * sizeof(datum_t));
          courses[n-1] = strdup(course);
          data[n-1] = (datum_t){id, grade};
          item.key = courses[n-1];
          item.data = data + n - 1;
          hsearch(item, ENTER);
        } else {
          datum_t* datum = (datum_t*)found_item->data;
          if (id < datum->id) {
            datum->id = id;
            datum->grade = grade;
      for (size_t i = 0; i < n; ++i) {
        printf("%s %d\n", courses[i], data[i].grade);
      return EXIT_SUCCESS;

    Example Usage:

    $ ./exercise7 data.txt
    Data Structures 45
    English 81
  8. V said

    Solution in Ruby.

    require 'csv'
    def fn(csv)
        .parse(csv, col_sep: '|')
        .group_by { |_, c_name, _| c_name }
        .map do |c_name, row|
          [c_name, row.min_by { |s_num, _| s_num }.last]

    Test Code

    def test(target, output, input)
      puts "target: #{target}"
      puts "output: #{output}"
      puts "pass: #{output == target ? '✅' : '❌'}"
    scores = <<-SCORES
    22|Data Structures|45
    26|Data Structures|72
    23|Data Structures|61
    target = [
      ['Data Structures', '45'],
      ['English',         '81']
    test target, fn(scores), scores


    target: [["Data Structures", "45"], ["English", "81"]]
    output: [["Data Structures", "45"], ["English", "81"]]
    pass: ✅

  9. Kevin said

    A solution in Racket.

    (define (x7 class-records)
    (let recurse ((records class-records) (results null))
    (if (null? records)
    (lambda (x) (string-append (cadr x) "|" (number->string (caddr x))))
    (let* ((items (string-split (car records) "|"))
    (id (string->number (car items)))
    (class (cadr items))
    (grade (string->number (caddr items)))
    (new-result (list id class grade)))
    (cdr records)
    (if (equal? #f (member class (map (lambda (x) (cadr x)) results)))
    (cons new-result results)
    (lambda (x)
    (and (equal? class (cadr x)) (< id (car x)))

  10. Steve said

    A solution in Mumps

    ; Load data into 1-dimensional array
    GTM>f  r !,x:5 q:'$t  s arr($i(arr))=x
    22|Data Structures|45
    26|Data Structures|72
    23|Data Structures|61
    ; Reformat data into 2-dimensional array (arr2)
    GTM>k arr2 f i=1:1:6 s arr2($p(arr(i),"|",2),$p(arr(i),"|"))=$p(arr(i),"|",3)
    ; This is how the data looks now
    GTM>s glo="arr2" f  s glo=$q(@glo) q:glo=""  w !,glo," = ",@glo
    arr2("Data Structures",22) = 45
    arr2("Data Structures",23) = 61
    arr2("Data Structures",26) = 72
    arr2("English",21) = 81
    arr2("English",22) = 51
    arr2("English",23) = 52
    ; For each class, get first student number and corresponding score
    GTM>s c="" f  s c=$o(arr2(c)) q:c=""  w !,c,": ",arr2(c,$O(arr2(c,"")))
    Data Structures: 45
    English: 81

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: