Two Homework Problems
August 21, 2015
For the first problem, the standard solution operates in linear time and constant space: keep two pointers, lo and hi, increasing lo and accumulating left-sum if the left-sum is less than the right-sum, decreasing hi and accumulating right-sum otherwise, and stopping when the two pointers meet:
(define (inflect xs)
(define (x i) (vector-ref xs i))
(let loop ((lo 0) (left-sum 0)
(hi (- (vector-length xs) 1))
(right-sum 0))
(cond ((< hi lo)
(values lo left-sum right-sum
(abs (- left-sum right-sum))))
((< left-sum right-sum)
(loop (+ lo 1) (+ left-sum (x lo))
hi right-sum))
(else (loop lo left-sum (- hi 1)
(+ right-sum (x hi)))))))
> (inflect '#(3 7 9 8 2 5 6))
3
19
21
2
For the second problem, the standard solution is to keep a ring buffer, writing lines to the buffer on input then emptying the buffer when input is exhausted:
(define (tail n file-name)
(with-input-from-file file-name
(lambda ()
(let ((buffer (make-vector n "")))
(let loop ((i 0) (line (read-line)))
(cond ((eof-object? line)
(do ((j 0 (+ j 1))) ((= j n))
(display (vector-ref buffer (modulo (+ i j) n)))
(newline)))
(else (vector-set! buffer i line)
(loop (modulo (+ i 1) n)
(read-line)))))))))
> (tail 5 "bible.txt")
Revelation22:17 The Spirit and the bride say, "Come." Let the hearer say, "Come." Let the one who thirsts come forward, and the one who wants it receive the gift of life-giving water.
Revelation22:18 I warn everyone who hears the prophetic words in this book: if anyone adds to them, God will add to him the plagues described in this book,
Revelation22:19 and if anyone takes away from the words in this prophetic book, God will take away his share in the tree of life and in the holy city described in this book.
Revelation22:20 The one who gives this testimony says, "Yes, I am coming soon." Amen! Come, Lord Jesus!
Revelation22:21 The grace of the Lord Jesus be with all.
We used read-line from the Standard Prelude. You can run the program at http://ideone.com/Kz1XuS.
1st
2nd
tail -5 a_file.txt
;; 1. Given an array of positive integers, find the inflection point ;; where the total of the integers before the inflection point and the ;; total of the integers after the inflection point are least ;; different. For instance, given the array [3, 7, 9, 8, 2, 5, 6], the ;; inflection point is between the 9 and 8, which leaves a total of 19 ;; before the inflection point and 21 after, a difference of 2. ;; (3 1 3) ;; ^ 3 4 ;; ;; (3 1 2 3) ;; ^ 4 5 ;; (3 2 1 3) ;; ^ 5 4 ;; (2 2 3 1 1 1 4 1 1 8 2 2) ;; ^ 14 14 (defun inflection-point (vector) (let ((i -1) (j (length vector)) (l 0) (r 0)) (loop :while (< (1+ i) j) :do (if (< (abs (- (+ l (aref vector (1+ i))) r)) (abs (- l (+ r (aref vector (1- j)))))) (progn (incf i) (incf l (aref vector i))) (progn (decf j) (incf r (aref vector j))))) (values i l r (abs (- l r))))) (progn ;; tests (assert (= 0 (inflection-point #(3 1 3)))) (assert (= 1 (inflection-point #(3 2 1 3)))) (assert (= 2 (inflection-point #(3 7 9 8 2 5 6)))) (assert (= 6 (inflection-point #(2 2 3 1 1 1 4 1 1 8 2 2)))) (assert (= -1 (inflection-point #()))) (assert (= -1 (inflection-point #(42))))) (inflection-point #(42)) ;; --> -1 ;; 0 ;; 42 ;; 42 (inflection-point #(3 7 9 8 2 5 6)) ;; --> 2 ;; 19 ;; 21 ;; 2 ;; 2. Write a program that reads a file from disk and writes the last n ;; lines of the file, where n is an input parameter. ;; Of course, we may use a library, loading the whole file in RAM, and ;; processing the list of lines with the language primitives: (defun last-lines (file n) (last (com.informatimago.common-lisp.cesarum.file:string-list-text-file-contents file) n)) ;; (last-lines #P"~/src/lisp/encours/programming-praxis--20150821.lisp" 5) ;; --> ("(defun last-lines (file n)" ;; " (last (com.informatimago.common-lisp.cesarum.file:string-list-text-file-contents file)" ;; " n))" ;; "" ;; "(last-lines #P\"~/src/lisp/encours/programming-praxis--20150821.lisp\" )") ;; This is what you would do in a "professional" setting (use libraries). ;; But at school, we're learning to write programs, not to use ;; libraries. Also there is the objection that the file could be ;; bigger than the RAM, and that N is big too (the tail could also ;; represent a bigger than RAM size if this tail was loaded at once). ;; Therefore we will write a function reading the file, noting the ;; last N line positions, and re-reading the tail. Instead of ;; collecting the whole tail into a buffer, we call a processing ;; function provided by the caller. (defun last-lines (file n fun) (let ((last-lines (make-array (1+ n) :initial-element nil)) (last-index -1)) ;; LAST-LINES will be used as a circular buffer, with LAST-INDEX ;; pointing to the last entry. We need one more slot for the EOF. (flet ((modinc (x) (mod (1+ x) (1+ n)))) (with-open-file (stream file) (loop :do (setf last-index (modinc last-index) (aref last-lines last-index) (file-position stream)) :while (read-line stream nil nil)) (loop :repeat n :for index := (modinc last-index) :then (modinc index) :when (aref last-lines index) :do (file-position stream (aref last-lines index)) (funcall fun (read-line stream))))))) ;; (last-lines #P"~/src/lisp/encours/programming-praxis--20150821.lisp" 20 (function print)) ;; ;; " (let ((last-lines (make-array (1+ n) :initial-element nil))" ;; " (last-index -1))" ;; " ;; LAST-LINES will be used as a circular buffer, with LAST-INDEX" ;; " ;; pointing to the last entry. We need one more slot for the EOF." ;; " (flet ((inc (x) (mod (1+ x) (1+ n))))" ;; " (with-open-file (stream file)" ;; " (loop" ;; " :do (setf last-index (inc last-index)" ;; " (aref last-lines last-index) (file-position stream))" ;; " :while (read-line stream nil nil))" ;; " (loop" ;; " :repeat n" ;; " :for index := (inc last-index) :then (inc index)" ;; " :when (aref last-lines index)" ;; " :do (file-position stream (aref last-lines index))" ;; " (funcall fun (read-line stream)))))))" ;; "" ;; "(last-lines #P\"~/src/lisp/encours/programming-praxis--20150821.lisp\" 20 (function print))" ;; "" ;; "";; Now, if the file is really that big (bigger than RAM), perhaps ;; there's no point in reading it all just to find the tail. We could ;; read it "from the end". ;; In Common Lisp, calling file-position with a position not obtained ;; from file-position is not conforming (it could fail on "strange" ;; systems), but it will work as expected on implementations ;; targetting posix systems (with some care for file position falling ;; in the middle of a CR-LF newline). The following code is not ;; strictly conforming Common Lisp, but it will work on the usual ;; implementations and systems. (defvar *disk-buffer-size* 4096) (defvar *default-line-size* 134) ;; columns + newline (defun estimate-lines-size (n &key last-size last-count) "Return an estimation of the size of N lines. If LAST-SIZE and LAST-COUNT are given, then this estimation takes into account the fact that only LAST-COUNT lines could be read from LAST-SIZE bytes." (let ((estimation (ceiling (* n (if (and last-size last-count) (+ 2 (/ last-size last-count)) *default-line-size*))))) #+DEBUG (format t "Estimating ~D lines ~:[~*~;~:*given ~D lines took ~D characters ~]to ~D~%" n last-count last-size estimation) estimation)) ;; (progn (estimate-lines-size 50 :last-size 8192 :last-count 30) ;; (estimate-lines-size 50)) ;; Estimating 50 lines given 30 lines took 8192 characters to 13754 ;; Estimating 50 lines to 6700 (defun big-file-last-lines (file n fun) (catch 'short (return-from big-file-last-lines (with-open-file (stream file) (let ((file-size (file-length stream)) (lines-size (estimate-lines-size n))) (when (<= file-size lines-size) ;; close the file and try again with the normal procedure. (throw 'short nil)) (flet ((count-lines (stream n from to old-count) "Return the file position of the Nth line before the end, starting from the FROM file position, and assuming there are OLD-COUNT lines between the TO file position and the end of file." (let* ((modulo (- n old-count)) (last-lines (make-array modulo :initial-element nil)) (last-index -1)) (file-position stream from) ; could be in the middle of a line (read-line stream) ; so throw it away. (flet ((modinc (x) (mod (1+ x) modulo))) (let ((new-count (loop :for line-position := (file-position stream) :while (and (< line-position to) (read-line stream nil nil)) :do (setf last-index (modinc last-index) (aref last-lines last-index) line-position) :count 1))) (if (<= modulo new-count) (values n (aref last-lines (modinc last-index))) (values (+ old-count new-count) (aref last-lines (mod (- last-index new-count) modulo)))))))) (round-file-position (file-position) (* (truncate file-position *disk-buffer-size*) *disk-buffer-size*))) (loop :with line-position := file-size :with line-count := 0 :do (multiple-value-setq (line-count line-position) (count-lines stream n (round-file-position (- file-size lines-size)) line-position line-count)) (setf lines-size (estimate-lines-size n :last-size (- file-size line-position) :last-count line-count)) :while (< line-count n) :finally (file-position stream line-position) (loop :repeat line-count :do (funcall fun (read-line stream))))))))) ;; Only called when 'short has been thrown. (last-lines file n fun)) ;; cl-user> (ls :l #P"/tmp/actors.list" ) ;; - 900710027 Aug 21 19:07 /tmp/actors.list ;; ; No value ;; cl-user> (time (big-file-last-lines #P"/tmp/actors.list" 12 'write-line)) ;; 5. CD-ROM distribution is prohibited without written ;; permission from the Internet Movie Database Ltd ;; ;; Distribution by e-mail, BBS and Internet systems is positively ;; encouraged within these limitations. ;; ;; The files and software which make up the movie database may be ;; uploaded to commercial BBS systems providing that the above ;; conditions are met and no *additional* fees are applied above the ;; standard connect time or downloading charges. ;; ;; For further info visit http://www.imdb.com/licensing/contact ;; (big-file-last-lines #P"/tmp/actors.list" 12 'write-line) ;; took 379 microseconds (0.000379 seconds) to run. ;; During that period, and with 8 available CPU cores, ;; 0 microseconds (0.000000 seconds) were spent in user mode ;; 0 microseconds (0.000000 seconds) were spent in system mode ;; 22,528 bytes of memory allocated. ;; 1 minor page faults, 0 major page faults, 0 swaps. ;; nil ;; cl-user>To compare with the last-lines function that reads the whole file first:
cl-user> (time (last-lines #P"/tmp/actors.list" 12 'write-line)) 5. CD-ROM distribution is prohibited without written permission from the Internet Movie Database Ltd Distribution by e-mail, BBS and Internet systems is positively encouraged within these limitations. The files and software which make up the movie database may be uploaded to commercial BBS systems providing that the above conditions are met and no *additional* fees are applied above the standard connect time or downloading charges. For further info visit http://www.imdb.com/licensing/contact (last-lines #P"/tmp/actors.list" 12 'write-line) took 62,900,029 microseconds (62.900030 seconds) to run. 454,223 microseconds ( 0.454223 seconds, 0.72%) of which was spent in GC. During that period, and with 8 available CPU cores, 63,359,959 microseconds (63.359960 seconds) were spent in user mode 116,007 microseconds ( 0.116007 seconds) were spent in system mode 4,002,904,464 bytes of memory allocated. 7 minor page faults, 0 major page faults, 0 swaps. nil cl-user>Exercise to the reader: there’s an obvious bug in big-file-last-lines ;-)
Jura gur ovt svyr fgvyy pbagnvaf srjre yvarf guna A (vg pbhyq pbagnva whfg 1 irel ybat yvar), gura gur SEBZ cbfvgvba pbhyq orpbzr artngvir naq YVAR-PBHAG nyjnlf or yrff A. Jr zhfg hfr SYBBE vafgrnq bs GEHAPNGR va EBHAQ-SVYR-CBFVGVBA gb qrny cebcreyl jvgu artngvir cbfvgvbaf, naq grfg sbe gurz va gur ybbc pnyyvat PBHAG-YVARF.
For the second problem, if we are supplied with an actual file, why read it at all? Let’s just memory map it and look for line ends backwards from the end. Error checking etc. omitted for brevity:
#include <stdlib.h> #include <unistd.h> #include <sys/stat.h> #include <sys/mman.h> #include <fcntl.h> int main(int argc, char *argv[]) { int fd = open(argv[1],O_RDONLY); int lines = strtol(argv[2],NULL,0); struct stat statbuf; fstat(fd,&statbuf); size_t len = statbuf.st_size; char *p = (char*)mmap(0,len,PROT_READ,MAP_PRIVATE,fd,0); size_t i = len-1; for ( ; i > 0; i--) { if (p[i-1] == '\n' && --lines == 0) break; } write(1,p+i,len-i); }Scala:
def inflection(nums: List[Int], left: Int = 0, right: Int = 0, inf: Int = -1): Int = { if (nums.isEmpty) inf else if (left <= right) inflection(nums.tail, left + nums.head, right, inf + 1) else inflection(nums.tail, left, right + nums.head, inf) } //> inflection: (nums: List[Int], left: Int, right: Int, inf: Int)Int inflection(List()) //> res5: Int = -1 inflection(List(1)) //> res6: Int = 0 inflection(List(1, 2)) //> res7: Int = 0 inflection(List(1, 2, 1)) //> res8: Int = 1 inflection(List(1, 2, 1, 2)) //> res9: Int = 2 inflection(List(3, 7, 9, 8, 2, 5, 6)) //> res10: Int = 3 def filesLastN(path: String, n: Int): Seq[String] = { def lastn(lines: Iterator[String], n: Int, lastLines: List[String]): Seq[String] = if (!lines.hasNext) lastLines else if (lastLines.size == n) lastn(lines, n, lastLines.tail ++ List(lines.next())) else lastn(lines, n, lastLines ++ List(lines.next())) lastn(Source.fromFile(path).getLines(), n, List()) } new PrintWriter("5lines.txt") { write("l1\r\nl2\r\nl3\r\nl4\r\nl5"); close } filesLastN("5lines.txt", 2) //> res12: Seq[String] = List(l4, l5)fun inflection_point [] = raise Domain
| inflection_point (R as x::xs) = let
val sum = foldl (op +) 0 R
fun inflection_point_aux [] difference current_index diff_index prev_sum sum = (difference, diff_index)
| inflection_point_aux (x::xs) difference current_index diff_index prev_sum sum = let
val left = x + prev_sum
val right = sum – x
val new_difference = Int.abs(left-right)
in
if new_difference < difference then inflection_point_aux xs new_difference (current_index + 1) current_index left right
else inflection_point_aux xs difference (current_index + 1) diff_index left right
end
in
inflection_point_aux R sum 0 0 0 sum
end
> use "inflection_point.sml";
val inflection_point = fn : Int.int list -> Int.int * int
val it = () : unit
> inflection_point [3, 7, 9, 8, 2, 5, 6];
val it = (2, 2) : Int.int * int
> inflection_point [1,2,3,4,5,15];
val it = (0, 4) : Int.int * int
Seems like every third submission ignores my sourcecode tags:
fun inflection_point [] = raise Domain | inflection_point (R as x::xs) = let val sum = foldl (op +) 0 R fun inflection_point_aux [] difference current_index diff_index prev_sum sum = (difference, diff_index) | inflection_point_aux (x::xs) difference current_index diff_index prev_sum sum = let val left = x + prev_sum val right = sum - x val new_difference = Int.abs(left-right) in if new_difference < difference then inflection_point_aux xs new_difference (current_index + 1) current_index left right else inflection_point_aux xs difference (current_index + 1) diff_index left right end in inflection_point_aux R sum 0 0 0 sum end > use "inflection_point.sml"; val inflection_point = fn : Int.int list -> Int.int * int val it = () : unit > inflection_point [3, 7, 9, 8, 2, 5, 6]; val it = (2, 2) : Int.int * int > inflection_point [1,2,3,4,5,15]; val it = (0, 4) : Int.int * int1st Problem:
public class InflectionPoint {
public static int point(int a[])
{
int diff;
int sums =0;
int suml = 0;
for(int s=0,l = a.length-1;s =s;)
{
if(sums suml)
{
diff = sums-suml;
}else diff = suml – sums;
return diff;
}
public static void main(String[] args) {
int arr[] = {3, 7, 9, 8, 2, 5, 6};
//Random r = new Random();
for(int i:arr)
{
// i = r.nextInt(50);
System.out.println(i);
}
System.out.println(“The infleation point is:” + point(arr) );
}
}
2nd Problem:
public class FewLines {
public static int countLines(String fileName) throws FileNotFoundException, IOException
{
int count = 0;
String lines = “”;
LineNumberReader reader = new LineNumberReader(new FileReader(fileName));
while((lines = reader.readLine())!=null){
reader.skip(Long.MAX_VALUE);
count = reader.getLineNumber();
}
reader.close();
return count;
}
public static void main(String[] args) throws IOException {
int n;
int i = 0;
String fileName = “Find.txt”;
String lines = “”;
LineNumberReader reader = new LineNumberReader(new FileReader(fileName));
n = countLines(“Find.txt”);
System.out.println(“Total number of lines is:” + n);
Scanner s =new Scanner(System.in);
System.out.println(“On which line you want to read File:”);
i = s.nextInt();
while(reader.getLineNumber()!= i)
{
lines = reader.readLine();
}
while(reader.getLineNumber() == i)
{
lines = reader.readLine();
System.out.println(lines);
}
}
}