[Serious?] Java Challenge fail?

Just for fun I have been trying to solve an algorithm challenge but sadly my solution fails. Here is the description of the challenge:

Quote:

---

Input
Each test file contains three lines.

First line starts with two space-separated integers NN and MM, the size of the list and the number of words Kanga says respectively.
Second line follows, containing NN space-separated words. This composes the no-no list.
Third line contains MM space-separated words. This composes the words Kanga has said during the day.

Each word is always strictly composed of lowercase english characters (a-z).
All words in the no-no list are unique, i.e. there are no repeated words
The length of each word is at most 1010 characters long.

Output
A single line containing a number - the number of times Kanga said a word that was in the no-no list.

Example:
Sample Input:
5 12
smallest take most room in
sometimes the smallest things take up the most room in your heart

Sample Output:
5

---

A quick solution I came up with is the following:

Code:

---

import java.util.Scanner;

public class JavaApplication1 {

    public static void main(String[] args)  {
       
        Scanner myObj = new Scanner(System.in); 
       
        //System.out.print("Input N & M: ");
        String NM = myObj.nextLine(); 
       
        //System.out.print("Input N: ");
        //String N = "smallest take most room in";
        String N = myObj.nextLine();
        String N2 = N.replace(" ", "XX");
       
        //System.out.print("Input M: ");
        //String M = "sometimes the smallest things take up the most room in your heart"; //myObj.nextLine();
        String M = myObj.nextLine();
       
        String[] tempArray;
 
        String delimiter = " ";
 
        tempArray = M.split(delimiter);
 
        int occurence = 0;
        for (int i = 0; i < tempArray.length; i++)
        {
            if (N2.contains(tempArray[i]))
                occurence += 1;
        }
       
        System.out.println(occurence);
    }   
}

---

The solution above "seems" to solve the problem but whenever I submit it it always fails. Can anyone point out where I could be failing their tests?

The wording of the program description seems to imply the source data is stored in a file, and you don't appear to have any file i/o code at all, just user input.

Also,

Quote:

---

First line starts with two space-separated integers NN and MM, the size of the list and the number of words Kanga says respectively.

---

you don't appear to have any code that does anything at all with these input values.

Is this supposed to work out how much Kanga has to put in the swear jar?

Quote:

---

Originally Posted by OptionBase1

The wording of the program description seems to imply the source data is stored in a file, and you don't appear to have any file i/o code at all, just user input.

Also,



you don't appear to have any code that does anything at all with these input values.

---

They said

Quote:

---

The program will be tested against the hidden test cases. You may assume that all test cases use valid inputs (no input error trapping is required).

---

hence I am not testing if the input is correct or not. I am not even sure what is the usage of the 1st line, should I use it to determine if the succeeding lines are of the correct size or not?

I've just tried reading from their input files and still this is failing. I am not sure what I am doing wrong.

Code:

---

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.util.Scanner;

class solution {
    public static void main(String[] args) {
                try {
            Scanner scanner = new Scanner(new java.io.File("000.in"));
            String MN = scanner.nextLine();
            String N = scanner.nextLine();
            String M = scanner.nextLine();
            scanner.close();
            String N2 = N.replace(" ", "XX");
            String[] tempArray;
            String delimiter = " ";
            tempArray = M.split(delimiter);
            int occurence = 0;
            for (int i = 0; i < tempArray.length; i++)
            {
                if (N2.contains(tempArray[i]))
                    occurence += 1;
            }  System.out.println(occurence);
                       
            String str1 = Integer.toString(occurence);
                       
            BufferedWriter out = new BufferedWriter(new FileWriter("." + java.io.File.separator + "000.ans"));
            out.write(str1);
            out.newLine();
                        out.close();
           
        } catch (Exception ex) {
           
        } finally {
           
        }
       
        return;
    }
}

---

Quote:

---

Originally Posted by dee-u

I've just tried reading from their input files and still this is failing.

---

Exactly where and how is it failing? The symptoms lead you to the cause and the cause leads you to the solution. "It's failing" is not a symptom.

When I am submitting it it shows it is not passing their tests, 0 out of 8. It doesn't give a clue as to the reason why.

If anyone is interested, for fun or anything else, the site can be found here but I am not sure if you guys could register.

From looking at the web site, I suspect the problem is with scoring issue g) or h) - which if either is met then the score is 0.

g) Code with run-time errors
h) Code that exceeds the time limit

It also specified the following, but I don't really understand it:

Quote:

---

1≤N≤25000
1≤M≤25000

---

Anyone who knows what it means?

Quote:

---

1≤N≤25000
1≤M≤25000

---

The no-no list has at least one word and no more than 25,000 words.

The list of words Kanga has said has at least one word and no more than 25,000 words.

PS Based on the given that the maximum length of each word is 1010 characters, and assuming that each word can therefore be that length, reading all the possible words into memory uses 2 * 25000 * 1010 bytes = 50,500,000 bytes = approx 50 megabytes. In your implementation, the size of N, N2, M and tempArray could each be 25000 * 1010 bytes = 25,250,000 = approx 25 megabytes for each String which gives a total of approx 100 megabytes of memory required. I suspect you are exceeding some size limit. Given that this is a competition, I suspect your solution, whilst probably correct for small sets of data, is too simplistic given the potential size of the data. ie that a total memory based solution fails on memory usage and that a total file based solution would fail on time limit.

I would suggest that you write a program to create a test data file containing the maximum number of words with each being the maximum size and run your program against this test file.

I don't use Java, so can't help with that implementation. However, looking at a possible c++ solution, you only need to store the no-no list in something like a set. Then for each read word from the said list, increment occurrence if this is found in the no-no set as it is read. Thus only a max of 25 megabytes of storage is needed. For info, a possible c++ implementation could be:

Code:

---

#include <fstream>
#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

const string wrdnam = "wrdnam.txt";

int main()
{
        ifstream ifs(wrdnam);

        if (!ifs.is_open()) {
                cout << "Cannot open file " << wrdnam << endl;
                return 1;

        }

        size_t M, N;
        string w;
        unordered_set<string> nosay;

        ifs >> M >> N;

        for (size_t m = 0; m < M; ++m) {
                  ifs >> w;
                  nosay.insert(w);
        }

        size_t occ = 0;

        while (ifs >> w)
                occ += nosay.count(w);

        cout << occ << " occurances\n";
}

---

This runs OK for the maximum number of no-no words and said words, with each word being the maximum length.

Good luck! :wave:

Thanks 2kaud, I just really need to optimize my code so it will pass their test cases, my solution is now accepted. :D