Write a Java program that reads a large file of strings and determines whether a

Question

Write a Java program that reads a large file of strings and determines whether all the strings are unique. As you read the file, generate a frequency histogram of the lengths of all the strings you read in. The filenames will start with either "3x3" or "4x4". Using this fact you can deduce that a filename starting with '3' will not have any string in that file greater than 3x3=9 chars long. A filename starting with '4' will be guaranteed to have no more than a string of length 4x4=16 chars. Use this fact to know how big of an array to declare for your histogram without having to read the strings from the file Use ArrayList container. You should use it to hold your strings for comparison purposes to determine uniqueness. You are free to use whatever algorithm you can devise to solve this problem but be aware that if you use a brute-force algorithm your program will take a very long time - even on the smaller file. The most obvious brute force approach would be to search the ArrayList for the presence of each new string before you put it into the ArrayList. Each search requires O(n) comparisons if there are n elements in the Array at that time. There are N total searches to be done. Thus the total number of comparisons needed for this brute force approach is n * N where n is the number of elements in the ArrayList at any given time and N is the total number of strings that get read in. Since little n varies from 0 to N you have a total number 1+2+3+4+5+6+ ... + N comparisons. This sum is (N squared + N)/2. Considering that even the little file has 10,000 strings in it, your brute force approach requires millions of comparisons. The larger test file has 3 million strings in it. A brute force algorithm would require millions * millions of comparisons. A brute force approach is just not feasible for this problem. Consider the topics we covered in conjunction with the ArrayList. use the Collections library to search or sort an ArrayList. use .get() and .add(). compare a string to another string to test for equality. The rest is up to you Here is the starter file import java.util.*; import java.io.*; public class Program7 { public static void main( String args[] ) throws Exception { ArrayList list = new ArrayList(); BufferedReader infile = new BufferedReader( new FileReader( args[0] ) ); int maxLen= 1; // CHANGE THIS: a 3x3 grid has a max string length of 9, 4x4 grid has a max string length of 16 int[] histogram = new int[maxLen]; // because out inputfile is a 4 by 4 longest string can only be 16 long startTime = System.currentTimeMillis(); while (infile.ready()) { // right now this is an infinite loop // read in the strings and generate the freq histogram } infile.close(); System.out.printf( "List contains %d Strings. ",list.size()); System.out.println("LEN FREQ"); for ( int i = 0; i < histogram.length ; ++i) // System.out.printf( "- %d ",i,histogram[i] ); boolean unique = true; int indexOfDupe = 0; // Look at the Strings in the list and set unique to fasle if you find any dupes if (unique) System.out.println("List has NO dupes."); else System.out.println("List has dupes at index position: " + indexOfDupe ); long endTime = System.currentTimeMillis(); long ms = endTime-startTime; System.out.printf("Elapsed time: %f seconds ", ms/1000.0); } } Computer Science

Explanation / Answer

i have written this program which works and uses brute force .there is some changes i have made in the code.

import java.util.*;
import java.io.*;

public class Program7 {
        public static void main( String args[] ) throws Exception {
                ArrayList<String> list = new ArrayList<String>(); // create a new arraylist
                try {
                        File file = new File(args[0]);         // create a file object
                        System.out.println(args[0]);
                        FileReader fileReader = new FileReader(file);
                        BufferedReader bufferedReader = new BufferedReader(fileReader);
                        String line;
                        System.out.println(args[0].toString().substring(0,1)); // find the first character of filename
                        int length = Integer.parseInt(args[0].substring(0,1));
                        // add each line of file to list
                        while ((line = bufferedReader.readLine()) != null) {
                                list.add(line);
                        }
                        fileReader.close();
                        // find the size of list
                        if ( list != null ){
                                int len = list.size();
                        /* create a histogram array which stores the length of string . you created histogram array which was of wrong size you created array of size which is maximum length of string .we have to store the length of each string which is len not length. */
                        int[] histogram = new int[len];
                        long startTime = System.currentTimeMillis();
                        //brute forrce
                        for ( int i = 0;i < len ;i++){
                                for ( int j = i+1 ; j < len ;j++)
                                        if (list.get(i).equals(list.get(j)) )
                                                System.out.println( " string at index " + i + "matches string at index " + j);
                                histogram[i] = list.get(i).length(); // add length to histogram
                        }
                        // print histogram
                        for ( int i = 0 ; i < len ; i++ ){
                                System.out.printf("(%4d) | ",i);
                                for ( int j = 0 ; j < histogram[i] ; j ++ )
                                        System.out.print("*");
                                System.out.println("("+histogram[i]+")");
                        }
                        System.out.print("        ");
                        for ( int i = 0 ; i < length*length;i++)
                                System.out.print("_");
                        System.out.println();
                        long endTime = System.currentTimeMillis();
                        long ms = endTime-startTime;
                        System.out.printf("Elapsed time: %d seconds ", ms);

                        }
                } catch (Exception e) {
                        e.printStackTrace();
                }
        }
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.