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
To compare with the last-lines function that reads the whole file first:
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:
Scala:
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:
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 = “”;
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);
}
}
}