## Two Homework Problems

### August 21, 2015

I can see from my statistics that the new academic year is beginning. Again, as in a previous exercise, in the spirit of helping programming students who are just starting a new school year, we have two typical homework problems:

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.

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.

Your task is to write programs to solve these problems. 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

### 10 Responses to “Two Homework Problems”

1. Rutger said

1st

```# inefficient one-liner, returns tuple of (difference, index)
def inflection_point_1(l):
return min((abs(sum(l[:i]) - sum(l[i:])),i-1) for i in range(len(l)))

# O(n), returns tuple of (difference, index)
def inflection_point_2(l):
left, right = 0, sum(l)
difference = abs(right)
result = 0
for i in range(0, len(l)):
left += l[i]
right -= l[i]
if abs(left - right) < difference:
result = i
difference = abs(left - right)
return difference, result

print inflection_point_1([3, 7, 9, 8, 2, 5, 6])
print inflection_point_2([3, 7, 9, 8, 2, 5, 6])
print inflection_point_1([1,2,3,4,5,15])
print inflection_point_2([1,2,3,4,5,15])

# outputs:
# (2, 2)
# (2, 2)
# (0, 4)
# (0, 4)
```

2nd
tail -5 a_file.txt

2. informatimago said
```;; 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
;; 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))
(loop
:repeat n
:for index := (modinc last-index) :then (modinc index)
:when (aref last-lines index)
:do (file-position stream (aref last-lines index))

;; (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))"
;; ""
;; ""
```
3. informatimago said
```
;; 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)
: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
;; 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
;;
;;     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>

```
4. informatimago said

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

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>
```
5. informatimago said

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.

6. matthew said

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,O_RDONLY);
int lines = strtol(argv,NULL,0);
struct stat statbuf;
fstat(fd,&statbuf);
size_t len = statbuf.st_size;
size_t i = len-1;
for ( ; i > 0; i--) {
if (p[i-1] == '\n' && --lines == 0) break;
}
write(1,p+i,len-i);
}
```
7. FA said

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)
```
8. mcmillhj said

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

9. mcmillhj said

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 * int
```
10. sk said

1st 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 = “”;
}
return count;
}
public static void main(String[] args) throws IOException {
int n;
int i = 0;
String fileName = “Find.txt”;
String lines = “”;
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();