fork(3) download
copy 
  1. ;; coursera.com
  2. ;;
  3. ;; Design and Analysis of Algorithms I
  4. ;;
  5. ;; Programming Question-4
  6. ;; Question 1
  7. ;;
  8. ;; Download the SCC.txt text file.
  9. ;;
  10. ;; The file contains the edges of a directed graph. Vertices are labeled as
  11. ;; positive integers from 1 to 875714. Every row indicates an edge, the vertex
  12. ;; label in first column is the tail and the vertex label in second column is
  13. ;; the head (recall the graph is directed, and the edges are directed from the
  14. ;; first column vertex to the second column vertex). So for example, the 11th
  15. ;; row looks liks : "2 47646". This just means that the vertex with label 2 has
  16. ;; an outgoing edge to the vertex with label 47646
  17. ;;
  18. ;; Your task is to code up the algorithm from the video lectures for computing
  19. ;; strongly connected components (SCCs), and to run this algorithm on the given
  20. ;; graph.
  21. ;;
  22. ;; Output Format: You should output the sizes of the 5 largest SCCs in the
  23. ;; given graph, in decreasing order of sizes, separated by commas (avoid any
  24. ;; spaces). So if your algorithm computes the sizes of the five largest SCCs to
  25. ;; be 500, 400, 300, 200 and 100, then your answer should be
  26. ;; "500,400,300,200,100". If your algorithm finds less than 5 SCCs, then write
  27. ;; 0 for the remaining terms. Thus, if your algorithm computes only 3 SCCs
  28. ;; whose sizes are 400, 300, and 100, then your answer should be
  29. ;; "400,300,100,0,0".
  30. ;;
  31. ;; Answer: 434821 968 459 313 211
  32.  
  33.  
  34. (defun not-implemented (name)
  35.   "Print 'not yet implemented' message and return NIL."
  36.   (format t "~a~%" (concatenate 'string "FIXME: not implemented yet: " name)))
  37.   ; The 'concatenate' is to remember how to make single string
  38.   ; from the bunch of them.
  39.  
  40.  
  41. (defun take-safe (seq n)
  42.   "Take up to n first elements of the sequence depending on its size."
  43.   (subseq seq 0 (min n (length seq))))
  44.  
  45.  
  46. (defun const-list (val size)
  47.   "Make list of given size with all elements equal to val."
  48.   (loop for i from 1 to size collect val))
  49.  
  50.  
  51. (defun take/default (seq n default)
  52.   "Take first n elments of the sequence seq padding with default value on the
  53.    right if necessary."
  54.   (let ((x (min n (length seq))))
  55.     (append (subseq seq 0 x) (const-list default (- n x)))))
  56.  
  57.  
  58. (defun read-file-linewise (path proc)
  59.   "Return list of values obtained by applying proc function on each line
  60.    read from file."
  61.   (with-open-file (s path)
  62.     (loop for line = (read-line s nil nil)
  63.           while line
  64.           collect (funcall proc line) into res
  65.           finally (return res))))
  66.  
  67.  
  68. (defun line-to-edge (line)
  69.   "Turn line into edge (pair of integers)."
  70.   (multiple-value-bind (from end-of-from) (parse-integer line :junk-allowed t)
  71.     (cons from (parse-integer line :start end-of-from))))
  72.  
  73.  
  74. (defun read-edges (file)
  75.   "Return list of edges read from the file."
  76.   (read-file-linewise file #'line-to-edge))
  77.  
  78.  
  79. (defun reverse-edges (edges)
  80.   "Return list of reversed edges."
  81.   (mapcar (lambda (e) (cons (cdr e) (car e))) edges))
  82.  
  83.  
  84. (defun hash-table-keys (ht)
  85.   "Return list of hash table keys."
  86.   (loop for key being the hash-keys of ht
  87.         collect key))
  88.  
  89.  
  90. (defun edges-to-vertices (edges)
  91.   "Make list of vertices from list of edges."
  92.   (hash-table-keys
  93.     (reduce
  94.       (lambda (ht e)
  95.         (setf (gethash (car e) ht) t)
  96.         (setf (gethash (cdr e) ht) t)
  97.         ht)
  98.       edges
  99.       :initial-value (make-hash-table))))
  100.  
  101.  
  102. (defun edges-to-graph (edges)
  103.   "Turn list of edges into graph."
  104.   (not-implemented "edges-to-graph"))
  105.  
  106.  
  107. (defun dfs-loop (graph vertices init pre-func acc-func)
  108.   "DFS loop."
  109.   (not-implemented "dfs-loop"))
  110.  
  111.  
  112. (defun scc (edges)
  113.   "Make list of SCCs -- list of lists of vertices."
  114.   (let* ((_ (format t "pass 1~%"))
  115.  
  116.          (vv (dfs-loop ; pass 1
  117.                (edges-to-graph (reverse-edges edges))
  118.                (edges-to-vertices edges)
  119.                '()
  120.                (lambda (v acc) acc)
  121.                (lambda (v acc) (cons v acc))))
  122.  
  123.          (_ (format t "pass 2~%"))
  124.  
  125.          (rr (dfs-loop ; pass 2
  126.                (edges-to-graph edges)
  127.                vv
  128.                '()
  129.                (lambda (v acc) (cons '() acc))
  130.                (lambda (v acc) (cons (cons v (car acc)) (cdr acc))))))
  131.  
  132.     rr))
  133.  
  134.  
  135. (defun p4-file (input.txt)
  136.   "Read edges from given file, compute SCCs and return list of sizes of
  137.    first largest 5 SCCs."
  138.   (take/default (sort (mapcar #'length (scc (read-edges file))) #'>) 5 0))
  139.  
  140.  
  141.  
  142. ;; end of file
  143. ;; vim: ts=4 sw=4 et
Time limit exceeded #stdin #stdout 5s 21968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.

[EXPRNPSR3] Missing function declaration for defun.
         CLIPS (V6.24 06/15/06)
CLIPS>
https://ideone.com/ym9spt
language:
Clips (clips 6.30)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!