[SOLVED] Ece365 programming assignment 1 to 4 solutions

First, you are going to create a hash table class. Then you are going to write a program that uses your hash table class to read in a “dictionary” and spell check a “document”. For the purposes of this assignment, a valid word is defined as any sequence of valid characters, and the valid characters are letters (capital and lowercase), digits (0 – 9), dashes (-), and apostrophes (‘). Every other character is considered a word separator.

 

A dictionary is defined as a list of recognized words. The dictionary is guaranteed to contain exactly one word per line, with no leading or trailing spaces, followed by a single, Unix-style newline character (
). Some of the words in the dictionary might not be valid (i.e., they may contain invalid characters). When loading the dictionary, invalid words, and also words that are too long (see below), can optionally be ignored. The dictionary does not specify the meanings of words; it just lists them.

 

The document to spell check may be any valid text file. Each line in the document will end with a single, Unix-style newline character. When spell checking the document, your program should indicate every unrecognized word, including the line number on which it occurs. Words should only be allowed to grow up to 20 characters. If a word in the document is too long, you should indicate the line number on which this occurs along with the first 20 characters of the word. The first line in the document is line 1. Words in the document that include digits (perhaps in addition to other valid characters) are technically valid but should not be spell checked (i.e., your program should ignore them). In the document, as previously stated, every character that is not a valid word character is a word separator; e.g., the string “abc@def” represents two valid words, “abc” and “def”. Therefore, there cannot be invalid words in the document.

 

Your program should be case insensitive, and all capital letters in both the dictionary and the document should be converted to lowercase immediately upon seeing them.

 

Your program must be written in C++. In order to implement this task efficiently, you will use a hash table. You must implement a hash table class using separate files, including a header file and a source code file. Not every member function of the class will be necessary for this assignment, but you will reuse this class for your next two assignments. Since our textbook provides code for the separate chaining and quadratic probing collision resolution strategies, I am requiring that you use either linear probing or double hashing. (Linear probing is a bit simpler to implement, and you will not receive any extra credit if you choose double hashing.) You are welcome to look at the book’s code for the other two strategies, but keep in mind that the instructions I am specifying for your hash table class make this different than the book’s implementation in several ways. For example, the book uses templates for its hash table class, but you will not. Also, your hash table class will allow the programmer to associate additional data with each entry, while the book’s implementation does not. More details about the requirements for your hash table class will be discussed later in this handout and in class.

 

To process the dictionary, simply insert every word in the dictionary into the hash table. To spell check the document, locate every valid word in the document (keeping track of line numbers), and lookup (i.e., search for) each word in the hash table to see if it is recognized. You should assume that an average dictionary contains about 50,000 words, but that some might be as large as 1,000,000 words. This is my way of telling you that you should implement a rehash member function! A sample dictionary, a bit on the small side (approximately 25,000 words), will be posted on the course home page.

 

Your program should prompt the user for the name of the dictionary file, the name of the document file to be spell-checked, and the name of the file where output should be written. Your program should indicate how long, in seconds, it takes to read the dictionary and how long it takes to spell check the text file, measured in terms of CPU time. (These times should be displayed to standard output, not to the output file.) Your program must compile and run correctly using the g++ compiler on either Cygwin or Ubuntu.

 

Your hash table implementation must include a header file called “hash.h” and a source code file called “hash.cpp”. The spell-checking code, and the rest of the main program, should be included in a separate file. You should also create a “Makefile” that I can use to compile your program. I will provide a sample “Makefile” that I used for my version of the program (also shown on the final page of this handout). I will also provide my version of “hash.h” (also shown later in this handout). You may reuse these two files directly if you wish. These files will also be posted on the course home page and discussed in class.

 

A sample document, a sample run of the program using that document, and a sample output file appear on pages 3 and 4 of this handout. The document file used for this sample run, as well as the dictionary used, will be available from the course home page. Your output file should adhere exactly to the format shown, and all the messages should be worded exactly the same way, with the same spacing. I will use “diff” to compare your output to mine, and you will lose points for any differences. (Of course, I will test your programs on multiple test cases involving different documents and dictionaries with various sizes.) Note that the output displayed to standard output does not have to match my formatting, as long as the content is the same.

 

Pages 5 and 6 of this handout show my “hash.h” file. Your hash table class must implement the same public member functions as mine. Note that the “getPointer”, “setPointer”, and “remove” member functions will not be used for this assignment; however, they will be used for future assignments! It is OK if you do not implement these member functions now. The specifics of this header file, and also a “Makefile” (shown on page 7 of this handout), will be discussed in more detail in class. Both files will also be made available to you from the course home page.

 

When your assignment is complete, e-mail me ([email protected]) your program, including your source code files, your header file(s), and your “Makefile” (even if you used the provided files). In addition to correctness, your grade may also depend on the efficiency and elegance of your code and adherence to proper C++ style. Your program is due before midnight on the night of Wednesday, September 26.

 

Below are the lyrics to “Supercalifragilisticexpialidocious” from “Mary Poppins”. This represents the contents of the document “lyrics.txt” used in the sample run shown on the next page. This file will also be posted on the course home page.

 

Um-deedledeedledeedle um-deedleday

Um-deedledeedledeedle um-deedleday

Um-deedledeedledeedle um-deedledeedle

Um-deedledeedledeedle um-um um-um um-um

 

For example…

 

Supercalifragilisticexpialidocious

Even though the sound of it is something quite atrocious

If you say it loud enough you’ll always sound precocious

Supercalifragilisticexpialidocious

 

Um-deedledeedledeedle um-deedleday

Um-deedledeedledeedle um-deedleday

Um-deedledeedledeedle um-deedleday

 

Super-super

Supercali

Super Supercalifragi

 

So when the cat has got your tongue there’s no need for dismay

Just summon up this word and then you’ve got a lot to say

But better use it carefully or it can change your life

 

For example…

 

Yes?

 

One day I said it to me girl and now me girl’s me wife

 

Supercalifragilisticexpialidocious

Even though the sound of it is something quite atrocious

If you say it loud enough you’ll always sound precocious

Supercalifragilisticexpialidocious

 

Supercalifragilisticexpialidocious

Even though the sound of it is something quite atrocious

If you say it loud enough you’ll always sound precocious

Supercalifragilisticexpialidocious

 

Supercalifragilisticexpialidocious

Even though the sound of it is something quite atrocious

If you say it loud enough you’ll always sound precocious

Supercalifragilistic

Supercalifragilistic

Supercalifragilisticexpialidocious

 

Below is a sample run using the sample dictionary provided on the course home page and a text file that contains the lyrics to “Supercalifragilisticexpialidocious” from “Mary Poppins”.

 

Enter name of dictionary: DICT/wordlist_small

Total time (in seconds) to load dictionary: 0.031

Enter name of input file: FILES/lyrics.txt

Enter name of output file: out_lyrics_small.txt

Total time (in seconds) to check document: 0

 

The output file should look exactly like this:

 

Long word at line 1, starts: um-deedledeedledeedl

Unknown word at line 1: um-deedleday

Long word at line 2, starts: um-deedledeedledeedl

Unknown word at line 2: um-deedleday

Long word at line 3, starts: um-deedledeedledeedl

Unknown word at line 3: um-deedledeedle

Long word at line 4, starts: um-deedledeedledeedl

Unknown word at line 4: um-um

Unknown word at line 4: um-um

Unknown word at line 4: um-um

Long word at line 8, starts: supercalifragilistic

Long word at line 11, starts: supercalifragilistic

Long word at line 13, starts: um-deedledeedledeedl

Unknown word at line 13: um-deedleday

Long word at line 14, starts: um-deedledeedledeedl

Unknown word at line 14: um-deedleday

Long word at line 15, starts: um-deedledeedledeedl

Unknown word at line 15: um-deedleday

Unknown word at line 17: super-super

Unknown word at line 18: supercali

Unknown word at line 19: supercalifragi

Unknown word at line 21: has

Unknown word at line 21: there’s

Unknown word at line 21: dismay

Unknown word at line 23: better

Unknown word at line 23: carefully

Unknown word at line 27: yes

Unknown word at line 29: girl’s

Long word at line 31, starts: supercalifragilistic

Long word at line 34, starts: supercalifragilistic

Long word at line 36, starts: supercalifragilistic

Long word at line 39, starts: supercalifragilistic

Long word at line 41, starts: supercalifragilistic

Unknown word at line 44: supercalifragilistic

Unknown word at line 45: supercalifragilistic

Long word at line 46, starts: supercalifragilistic

 

Below and on the next page, I am providing you with the header file (“hash.h”) for my hash table implementation. This file will also be posted on the course home page.

 

#ifndef _HASH_H

#define _HASH_H

 

#include <vector>

#include <string>

 

class hashTable {

 

public:

 

// The constructor initializes the hash table.

// Uses getPrime to choose a prime number at least as large as

// the specified size for the initial size of the hash table.

hashTable(int size = 0);

 

// Insert the specified key into the hash table.

// If an optional pointer is provided,

// associate that pointer with the key.

// Returns 0 on success,

// 1 if key already exists in hash table,

// 2 if rehash fails.

int insert(const std::string &key, void *pv = NULL);

 

// Check if the specified key is in the hash table.

// If so, return true; otherwise, return false.

bool contains(const std::string &key);

 

// Get the pointer associated with the specified key.

// If the key does not exist in the hash table, return NULL.

// If an optional pointer to a bool is provided,

// set the bool to true if the key is in the hash table,

// and set the bool to false otherwise.

void *getPointer(const std::string &key, bool *b = NULL);

 

// Set the pointer associated with the specified key.

// Returns 0 on success,

// 1 if the key does not exist in the hash table.

int setPointer(const std::string &key, void *pv);

 

// Delete the item with the specified key.

// Returns true on success,

// false if the specified key is not in the hash table.

bool remove(const std::string &key);

 

 

private:

 

// Each item in the hash table contains:

// key – a string used as a key.

// isOccupied – if false, this entry is empty,

//              and the other fields are meaningless.

// isDeleted – if true, this item has been lazily deleted.

// pv – a pointer related to the key;

//      NULL if no pointer was provided to insert.

class hashItem {

public:

std::string key;

bool isOccupied;

bool isDeleted;

void *pv;

};

 

int capacity; // The current capacity of the hash table.

int filled; // Number of occupied items in the table.

 

std::vector<hashItem> data; // The actual entries are here.

 

// The hash function.

int hash(const std::string &key);

 

// Search for an item with the specified key.

// Return the position if found, -1 otherwise.

int findPos(const std::string &key);

 

// The rehash function; makes the hash table bigger.

// Returns true on success, false if memory allocation fails.

bool rehash();

 

// Return a prime number at least as large as size.

// Uses a precomputed sequence of selected prime numbers.

static unsigned int getPrime(int size);

};

 

#endif //_HASH_H

 

This page shows the “Makefile” that I used for my program. This will also be posted on the course home page.

 

spell.exe: spellcheck.o hash.o

g++ -o spell.exe spellcheck.o hash.o

 

spellcheck.o: spellcheck.cpp hash.h

g++ -c spellcheck.cpp

 

hash.o: hash.cpp hash.h

g++ -c hash.cpp

 

debug:

g++ -g -o spellDebug.exe spellcheck.cpp hash.cpp

 

clean:

rm -f *.exe *.o *.stackdump *~

 

backup:

test -d backups || mkdir backups

cp *.cpp backups

cp *.h backups

You are going to create a class called “heap” that provides programmers with the functionality of a priority queue using a binary heap implementation. Each item inserted into the binary heap will specify a unique string id, an integer key, and optionally any pointer. The implementation of the class should use pointers to void in order to handle pointers to any type of data. When a heap is declared, a capacity will be passed to its constructor representing the maximum number of items that may be in the heap at one time; the heap will never be allowed to grow past its initial capacity (although it is not difficult to implement a resize operation).

 

I have written a program that uses my own implementation of the class. I will provide you with that program (useHeap.cpp) and with a Makefile. You should not change my source code file! You are allowed to add c++11 flags to the Makefile if you need to. Both files will be discussed in class and can be obtained from the course home page. Your heap will also make use of the hash table class that you created for the previous programming assignment.

 

This assignment asks you to fill in the missing heap.cpp and heap.h files, and to correct or add to your hash.cpp file if necessary, so that everything works. This implies that your heap class must include at least the following: a constructor that accepts an integer representing the capacity of the binary heap; a public member function, insert, used to insert a new item into the heap; a public member function, deleteMin, that removes the item with the lowest key from the heap; a public member function, setKey, providing both increaseKey and decreaseKey functionality; and a public member function, remove, that allows the programmer to delete an item with a specified id from the heap. In class we will discuss the parameters of these member functions and their return values. In addition, your class should contain private data members and private member functions that allow you to elegantly and efficiently implement the required public member functions. I will discuss my own implementation in class, and it is described on the next page.

 

In class, we will look at a sample run of the program and discuss the provided code. This program only passes string ids and integer keys to the insert member function of the heap class, but again, the insert member function should also optionally accept any pointer that can be stored and associated with the id. In the future, you will be using the class you write for this assignment in order to implement an algorithm involving graph data structures, and this functionality will be necessary. Also note that the integer keys will not necessarily be positive integers.

 

All operations should be implemented using average-case logarithmic time (or better) algorithms. In order to achieve setKey and remove in average-case logarithmic time, your program needs to be able to map an id to a node quickly. Since each id can be any arbitrary string, a hash table is useful for this purpose. Searching a heap to find an item with a particular id would require linear time, but a hash table in which each hash entry includes a pointer to the associated node in the heap allows you to find the item in constant average time. Apart from the calls to the hash table member functions, which are worst-case linear time but average-case constant time operations, all heap operations should use worst-case logarithmic time algorithms, and the insert operation should use an average-case constant time algorithm.

 

My heap class contains four private data members. Two are simple integers representing the capacity and the current size of the heap. The third is a vector of node objects containing the actual data of the heap; each node contains a string id, an integer key, and a pointer to void that can point to anything. (I have made “node” a private nested class within the heap class.) The fourth private data member is a pointer to a hash table (the actual hash table is allocated in the heap’s constructor). Since the constructor is provided with the maximum size of the heap, you may allocate the hash table to be large enough such that there is a small likelihood of a rehash, but that is up to you. (Note that since items get removed from the heap, but only lazily deleted from the hash table, it is still possible that a rehash of the hash table will be necessary.)

 

Your heap.h file should contain the declaration of your class along with the declarations of its public and private data members and member functions. The heap.cpp file should contain the implementation of the class. I don’t think you should need to implement any functions other than the member functions of the class itself in this file (I did not).

 

As usual, you will be graded not only on the correctness of your program, but also on the appropriateness of the decisions that you make, the elegance (and perhaps the formatting) of your code, and on the appropriate use of C++ concepts and routines.

 

The following page shows the declarations of the constructor and the public member functions of my heap class along with my comments describing their functionalities, parameters, and return values. I am not showing the declarations of my private data members or private member functions here, but this will be discussed further in class.

 

E-mail me ([email protected]) your program, including all source code files, head files, and your Makefile (including any provided files that you use without making changes). Your program must compile and run using either Ubuntu or Cygwin. The program is due before midnight on the night of Wednesday, October 24.
//

// heap – The constructor allocates space for the nodes of the heap

// and the mapping (hash table) based on the specified capacity

//

heap(int capacity);

 

//

// insert – Inserts a new node into the binary heap

//

// Inserts a node with the specified id string, key,

// and optionally a pointer. They key is used to

// determine the final position of the new node.

//

// Returns:

//   0 on success

//   1 if the heap is already filled to capacity

//   2 if a node with the given id already exists (but the heap

//     is not filled to capacity)

//

int insert(const std::string &id, int key, void *pv = NULL);

 

//

// setKey – set the key of the specified node to the specified value

//

// I have decided that the class should provide this member function

// instead of two separate increaseKey and decreaseKey functions.

//

// Returns:

//   0 on success

//   1 if a node with the given id does not exist

//

int setKey(const std::string &id, int key);

 

//

// deleteMin – return the data associated with the smallest key

//             and delete that node from the binary heap

//

// If pId is supplied (i.e., it is not NULL), write to that address

// the id of the node being deleted. If pKey is supplied, write to

// that address the key of the node being deleted. If ppData is

// supplied, write to that address the associated void pointer.

//

// Returns:

//   0 on success

//   1 if the heap is empty

//

int deleteMin(std::string *pId = NULL, int *pKey = NULL, void *ppData = NULL);

 

//

// remove – delete the node with the specified id from the binary heap

//

// If pKey is supplied, write to that address the key of the node

// being deleted. If ppData is supplied, write to that address the

// associated void pointer.

//

// Returns:

//   0 on success

//   1 if a node with the given id does not exist

//

int remove(const std::string &id, int *pKey = NULL, void *ppData = NULL);

You are going implement Dijkstra’s algorithm to solve the single-source shortest-path problem. The program will determine the shortest path in a specified graph from a specified starting vertex to each other vertex in the graph. In order to do this efficiently, your program should use the binary heap class that you created for the previous assignment.

 

Your program should start by asking the user to enter the name of a file specifying the graph. Every row in the input file represents an edge in the graph. Each row consists of two string ids representing the source vertex and destination vertex of the edge (in that order) followed by an integer representing the cost (a.k.a. distance or weight) of the edge. The rows will contain no leading or trailing whitespace, single spaces will separate fields, and all rows will end with a single Unix-style newline character. All vertex ids will consist only of lowercase and capital letters and digits. All edge costs will be positive integers less than one million. A vertex exists if it is the source or the destination of any edge. The source vertex of an edge will never be the same as the destination vertex, but it is possible that multiple edges might connect the same vertices. Your program may assume that the file, if it can be opened, is valid. You are not required to include error checks for invalid file formats; you may if you wish, but I will not check for this.

 

Once the program is finished reading in the graph, the user should be prompted to enter the id of a starting vertex. The user should be re-prompted until they enter a valid index (i.e., a string id representing a vertex that exists in the graph). The program should then apply Dijkstra’s algorithm to determine the shortest path to each node from the specified starting vertex. The implementation should rely on the binary heap class that you created for the previous assignment. (The heap class, of course, relies on the hash class you created for the first assignment, and you will also likely rely on the hash class for a couple of other purposes as well.) When the algorithm has finished determining the shortest path to each node, your program should output the CPU time, in seconds, that was spent executing the algorithm.

 

The program should then ask the user for the name of an output file. The output file should contain one row for every vertex that exists in the graph, with vertices listed in the same order that they first appear in the input file. Each row in the output file should contain a vertex id followed by a colon, a single space, and then the shortest distance from the specified starting vertex to the given vertex. All of these distances are guaranteed to be less than one billion. After the distance, the row should contain one space, a left bracket, the path from the starting vertex to the current vertex, a right bracket, and finally a single Unix-style newline character. Vertices in the path should be separated by a comma followed by a single space. There should not be any space or comma before the first vertex in the path (the specified starting vertex) or after the last vertex in the path. If there is no path from the specified starting vertex to any existing vertex in the graph, the corresponding output row should contain the vertex id followed by a colon, a single space, and then the text “NO PATH” followed by a single Unix-style newline character. You must follow these instructions exactly.

 

In class, we stepped through Dijkstra’s algorithm for the following graph, which came from Figure 9.20 in the textbook:

 

 

The file representing this graph might look like this:

 

v1 v2 2

v1 v4 1

v2 v4 3

v2 v5 10

v3 v1 4

v3 v6 5

v4 v3 2

v4 v5 2

v4 v6 8

v4 v7 4

v5 v7 6

v7 v6 1

 

Any permutation of the rows representing edges in this file would designate the same graph (but the order of rows in the output file might be different). Assume a file called graph.txt exists, containing the data shown above. Then a sample run of your program might look like this:

 

Enter name of graph file: graph.txt

Enter a valid vertex id for the staring vertex: v1

Total time (in seconds) to apply Dijkstra’s algorithm: 0.000

Enter name of output file: out.txt

 

The prompts to the user may vary, but the file out.txt should look exactly like this:

 

v1: 0 [v1]

v2: 2 [v1, v2]

v4: 1 [v1, v4]

v5: 3 [v1, v4, v5]

v3: 3 [v1, v4, v3]

v6: 6 [v1, v4, v7, v6]

v7: 5 [v1, v4, v7]

 

If the user specifies the same graph file but enters v5 as the id of the starting vertex, then the output file should look exactly like this:

 

v1: NO PATH

v2: NO PATH

v4: NO PATH

v5: 0 [v5]

v3: NO PATH

v6: 7 [v5, v7, v6]

v7: 6 [v5, v7]

 

As already stated, you should rely on your heap implementation (which in turn relies on your hash table implementation) to implement Dijkstra’s algorithm efficiently. If you have implemented these classes correctly and completely, you should not need to modify any of your heap or hash files for this assignment. You should also create a graph class that is constructed with Dijkstra’s algorithm in mind, so the implementation of the algorithm can be handled by a member function of this class. I suggest including a private nested class to store nodes in the graph. The graph can also contain a linked list of pointers to nodes. Whenever a new node is encountered, you can allocate memory for the node and add a pointer to the new node to the end of the linked list. (Alternatively, you may decide to use a linked list of nodes directly, instead of a linked list of pointers. Either way, you may use the provided C++ list class for this purpose.) One field of each node must store an adjacency list for the node. This can also use the provided linked list class. Each node in an adjacency list represents an edge, and each edge must at least specify the destination vertex and the cost of the edge. (You do not necessarily have to specify the source node in each edge, since it is the same for every node in an adjacency list.)

 

As you are reading the edges of the graph from the input file, you will need some way to efficiently determine whether or not you have encountered each vertex id already. If not, you need to create a new vertex node. If the source vertex of the edge has been previously encountered, you have to locate the corresponding node efficiently in order to update its adjacency list. I suggest using your own hash table implementation for these tasks. Whenever a new vertex is encountered, add an entry with the new vertex id to the hash table, and use the void pointer to point to the new node. To locate a node corresponding to a source vertex, use the getPointer member function of the hash table class. I also suggest using your hash table class to determine whether or not a starting vertex entered by the user is valid.

 

When you are implementing Dijkstra’s algorithm, I suggest using the void pointer of each heap node to point to the node corresponding to each vertex. You can then use the optional parameter of deleteMin to obtain this pointer and access the node immediately. Although you could also locate the node by just obtaining the vertex id from deleteMin and then using your hash table to obtain the pointer to the node, this is a bit less efficient, and I consider this less elegant, so I may take off a few points for this solution.

 

After you have completed the assignment, e-mail me ([email protected]) all of your code, including a Makefile. I should be able to run “make” and then test your executable. The program is due before midnight on the night of Monday, November 19.

This problem came from the 1998 regional ACM Programming Contest. As I described in class, it was the only question my Columbia team did not complete in the time limit. We had a solution which would work given unlimited time, but we did not realize it was an exponential time solution for contrived input. I am letting you know that the solution (probably) requires dynamic programming to be implemented efficiently. If you want to see how the problem was stated at the competition, check out this link:

 

https://www.acmgnyr.org/year1998/prob_g.html

 

The problem defines a “merge” of two strings as a third string containing all the characters from each of the original two strings mixed together. The two sets of characters can be interspersed, but the characters from each individual string cannot be permuted. For example, one possible merge of “hello” and “world” would be “wohrellold”. However, the string “wohrelldol” is not a valid merge. Although this string contains all the correct characters, and “hello” and “world” are both subsequences, there is no way to select two subsequences with distinct characters to form both of the original two strings.

 

You are asked to write a program that accepts three strings at a time; we’ll call them A, B, and C. All strings will consist of only lowercase letters. You can assume that A and B will contain at most 1000 letters, and C will contain at most 2000 letters. Your program should determine whether or not C is a valid merge of A and B. If so, the program should output C with the characters from A converted to uppercase. If more than one merge is possible, the letters of A should be made to occur as early as possible. If no merge is possible, the output should read “*** NOT A MERGE ***”.

 

For this assignment, your program should prompt the user for the names of an input file and an output file. The input file will consist of multiple sets of three strings, one string per line (i.e., the number of rows in the file will be a multiple of three). Your program should read three strings at a time, and it should determine whether or not the third string is a merge of the first two. The output for each set of strings should be written to the output file as specified in the previous paragraph. Your program should continue to process sets of three strings until it reaches the end of the input file. Every line in the input file will be, and every line in the output file should be, followed by a single Unix-style newline character.

 

My major hint to you is that dynamic programming is (probably) necessary to write this program in a way such that it will run correctly for certain inputs in reasonable time. Simple algorithms will either get some cases wrong or require exponential time to run. Either top-down dynamic programming or bottom-up dynamic programming is appropriate (although you might run into stack-size problems with top-down dynamic programming on some systems). Note that you should be able to declare a global matrix (i.e., a two-dimensional array) that is big enough to handle all instances of this problem. Do not try to make the matrix a local variable; you might overflow the stack. There is no need to allocate the matrix dynamically.

 

A sample run of the program might look like this:

 

Enter name of input file: input.txt

Enter name of output file: output.txt

 

If the input file looks like this:

 

chocolate

chips

cchocholaiptes

chocolate

chips

bananasplit

abac

bad

ababacd

hello

world

wohrelldol

ab

ba

abab

zzzzzzzzzzzzzzzzzzzzab

zzzzzzzzzzzzzzzzzzzzac

zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzacab

zzzzzzzzzzzzzzzzzzzzabc

zzzzzzzzzzzzzzzzzzzzacb

zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzabcbac

 

Then the output file should look exactly like this:

 

CcHOChOLAipTEs

*** NOT A MERGE ***

ABAbaCd

*** NOT A MERGE ***

AbaB

ZZZZZZZZZZZZZZZZZZZZzzzzzzzzzzzzzzzzzzzzacAB

*** NOT A MERGE ***

 

The first three examples (i.e., the first nine rows of the input and the first three rows of the output) were the examples provided at the actual competition. I contrived the other four examples to show cases that make the problem more difficult. Of course, I will test your programs with several additional difficult (and in some cases, much longer) test cases.

 

Submit your program to me via e-mail ([email protected]). I encourage you to send early presubmissions; I will reply with responses similar to those given at the contest (it may take a day or longer). The program is due before midnight on the night of Wednesday, December 5.