Problem with C# List when compiled in mono (homework-related)

Question

I'll admit this is my homework. The task statement said I have to write a program that finds a topological order of a graph which would be inputted by standard input. Then I need to submit it to be graded on the professor's server.

Now it's not the algorithm problem. It's more of a technical problem. In my computer, I use .NET compiler (csc) while the professor's grading machine uses some form of mono.

It works well, until the grader said I got 30/100. A friend of mine suggested that I use the grader's "manual input system", so here I go, I made it create array-of-100000 lists for the adjacency list.

The grader, after a few seconds, reported that my program has crashed.

Stacktrace:

at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke_object__this__ (object,intptr,intptr,intptr) <0xffffffff>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0x00004>
at (wrapper managed-to-native) object.__icall_wrapper_mono_object_new_fast (intptr) <0xffffffff>
at System.Exception.ToString () <0x00026>
at (wrapper runtime-invoke) object.runtime_invoke

This is kinda strange and unsettling to me, but I have yet to find an answer for this. Again, this program worked really fine on my PC.

This is my part of the program:

using System;
using System.Collections;
using System.Collections.Generic;

class topo{
public static void Main(){
    string[] ST = Console.ReadLine().Split(' ');
    int N=Convert.ToInt32(ST[0]), M=Convert.ToInt32(ST[1]);
    int[] ins = new int[N];  //node's total in-degrees
    List<int>[] E = new List<int>[N];

    for(int n=0;n<N;n++)    
        E[n] = new List<int>();

    for(int m=0;m<M;m++){
        ST = Console.ReadLine().Split(' ');
        int u = Convert.ToInt32(ST[0]);
        int v = Convert.ToInt32(ST[1]);
        E[u-1].Add(v-1);
        ins[v-1]++;
    }

    Queue S = new Queue();
    List<int> L = new List<int>(); //result list

    for(int n=0;n<N;n++){
        //add stranded nodes directly and don't process it
        if(ins[n]==0 && E[n].Count==0)
            L.Add(n);

        //put into queue
        else if(ins[n]==0)
            S.Enqueue(n);
    }

    while(S.Count>0){
        int n = (int) S.Dequeue();
        L.Add(n);
        foreach(int m in E[n])
            if(--ins[m]==0)
                S.Enqueue(m);
    }

    foreach(int n in L)
        Console.WriteLine(n+1);

}

}

Thank you very much, and I appreciate any and every response.

Edit: I took another look at the grader's output to see if I missed anything, and indeed I did. It said "syscal: 2", but all I know about it is that "the program didn't exit normally."

Edit #2: I've tried making the program attempt to make various sizes of the array-of-list, ranging from 5000, 10000, etc. and after 40000 the "manual input system" said the program got a System.OutOfMemoryException. With further look into various parts of the grader that the students are allowed into, it seems that prof misconfigured his grading parameters and gave us less memory than announced. (He said "32MB", but the program crashes at about 16MB)

I've reported the error to him and he is (right now) looking into it.

Dhu

There is a stacktrace, but is there an actual exception/error message? – Eyelash

@Maxim This is all I've got from the output. I took another look and found this, too: "syscal: 2" (also edited into question) – Dhu

The data to be used? You access the array based on the read data. So bad data = crash. You could put some sanity checks when you read the data, to prevent out-of-bound exceptions... – Provender

@Xanatos I've checked the problem statement, and it is already guaranteed that the input data is going to be "sane", e.g. no declaring 2 nodes then referencing node 3. – Dhu

@Lunatic do you have the data your teacher used? it could be a funny unix/windows end-of-the-line problem... (under unix the end of the line is different than on windows, and I don't know how the Console.ReadLine() and the pipes handle this) – Provender

@Xanatos Unfortunately no. I've reported this problem into his Facebook and still waiting for his reply. – Dhu

@LunaticNeko: use Int32.TryParse instead of Convert.ToInt32 (to avoid FormatException and OverflowException) and check that ST.Length >= 2. – Booboo

@Dhu As suggested by Jaroslav, but I think ST.Length should be == 2. If different throw an Exception, so you can see it in the output. On an unrelated note, if you use List<T>, you should use Queue<T> instead of Queue. – Provender

Though it usually wouldn't be a problem if you're coding in an IDE that handles indentation, it would be good practice to put if,while,for,foreach single-statement blocks in braces too, :) – Bridesmaid

To me, it seems a little 'unfair' that the grading system uses Mono to execute the programs, unless you were provided/allowed access to a Mono compiler configured the same as the grading system. On an unrelated note, it's awesome to see that not all universities require Java for everything. They still do at mine. – Elainaelaine

@Jaroslav @Provender Currently the professor is looking into it. @Bridesmaid I use vim :D @Josh Actually, we even allow Python in some courses. – Dhu

@Dhu To expand what @Bridesmaid said, I think it's a right to be an inexperienced programmer, it is NOT a right to be a disorderly/untidy inexperienced (or even experienced) programmer. When you program, you should follow coding guidelines on casing, variable names, use of braces... – Provender

After experimenting and discussing with classmates, and with partial confirmation from prof (best answer while he's looking into it), all this problem looks like one of the symptoms of running out of memory. The system gives students' solution only 16MB, but the program used more than that. (Should this be an answer?) – Dhu

@Dhu Should this (as in "Problem with C# List when compiled in mono (homework-related)") be a question, should be your question :-) We couldn't help you... You couldn't be helped by us... And the solution won't probably help other persons... :-) :-) – Provender

Answer 1

The following code is going to fail if the value of u or v is less than 1.

for(int m=0;m<M;m++){
    ST = Console.ReadLine().Split(' ');
    int u = Convert.ToInt32(ST[0]);
    int v = Convert.ToInt32(ST[1]);
    E[u-1].Add(v-1);
    ins[v-1]++;
}

Because u-1 or v-1 is going to be negative, and that will throw an exception.

Rochelle

Answer 2

Followup: This is anecdotal, self-answer, and very late because I just realized that it's okay to answer myself. I was later notified that I went over the memory limit enforced by the grading system. However, the exception was quite cryptic in my case and the grader did not report this issue. (It marked me only as incorrect.)

I was also quite careless to not realize that smaller inputs worked, and that's why I got 30/100 and not zero points.

For future readers: When programming in an automatic-grader environment, please make sure your program does not go over the memory limit, which may be there but may not be known to you (i.e. not written in problem statement).

Dhu