Exercise 7

June 1, 2018

We first read the input into a list of studentnumber/classname/grade triples, using read-line and string-split from the Standard Prelude:

(define (read-input filename)
  (with-input-from-file filename
    (lambda ()
      (let loop ((line (read-line)) (lines (list)))
        (if (eof-object? line) lines
          (let* ((fields (string-split #\| line))
                 (student-number (string->number (car fields)))
                 (class-name (cadr fields))
                 (grade (string->number (caddr fields)))
                 (fields (list student-number class-name grade)))
            (loop (read-line) (cons fields lines))))))))

Then we sort by class name and student number and write output each time the class name changes:

(define (write-output lines)
  (let loop ((lines (sort lt? lines)) (prev ""))
    (when (pair? lines)
      (when (not (string=? prev (cadar lines)))
        (display (cadar lines)) (display #\tab)
        (display (caddar lines)) (newline))
      (loop (cdr lines) (cadar lines)))))
(define (lt? a b)
  (or (string<? (cadr a) (cadr b))
      (and (not (string<? (cadr b) (cadr a)))
           (< (car a) (car b)))))

Finally, we complete the exercise like this:

(define (exercise7 filename)
  (write-output (read-input filename)))
> (exercise7 "input.txt")
Data Structures 45
English 81

You can run the program at https://ideone.com/pO4cu1, where the program is modified to read from standard input, to conform to the requirements of Ideone.

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: