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
23|English|52
22|English|51
26|Data Structures|72
23|Data Structures|61
21|English|81

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.

Advertisements

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)))
                                     (newline)))
                  (receive (id cname score) (apply values (parse-line line))
                    (hash-table-update!/default ht
                                                cname
                                                (lambda (id+score)
                                                  (if (< id (first id+score))
                                                      (list id score)
                                                      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;}'
    

    Output:

    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]))
      sys.exit(1)
    
    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)
    

    Output:

    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 '|' ' '
    

    output:


    Data Structures 45
    English 81

  5. sbocq said

    Clojure.

    (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))
    

    Output:

    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';
      }
      rewind(fp);
      hcreate(n_lines);
      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) {
          ++n;
          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);
      }
      hdestroy();
      free(courses);
      free(data);
      return EXIT_SUCCESS;
    }
    

    Example Usage:

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

    Solution in Ruby.

    require 'csv'
    
    def fn(csv)
      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]
        end
    end
    

    Test Code

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

    Output

    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)
    (reverse
    (map
    (lambda (x) (string-append (cadr x) "|" (number->string (caddr x))))
    results))
    (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)))
    (recurse
    (cdr records)
    (if (equal? #f (member class (map (lambda (x) (cadr x)) results)))
    (cons new-result results)
    (map
    (lambda (x)
    (if
    (and (equal? class (cadr x)) (< id (car x)))
    new-result
    x))
    results)))))))

  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
    23|English|52
    22|English|51
    26|Data Structures|72
    23|Data Structures|61
    21|English|81
    
    ; 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
    GTM>
    

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 )

Google+ photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s

%d bloggers like this: