pset3 - find Why do we need a limit at 65535 to pass check50?

Question

While debugging locally, the program executes as expected, tested with random inputs and the check50 proposed inputs. When uploading by using check50, it returns the following, never finding 42 :

~/workspace/pset3/find/ $ check50 2016.find.more helpers.c
:) helpers.c exists
:) helpers.c compiles
:( finds 42 in {42,43,44}
\ expected an exit code of 0, not 1
:( finds 42 in {41,42,43}
\ expected an exit code of 0, not 1
:( finds 42 in {40,41,42}
\ expected an exit code of 0, not 1
:( finds 42 in {41,42,43,44}
\ expected an exit code of 0, not 1
:( finds 42 in {40,41,42,43}
\ expected an exit code of 0, not 1
:( finds 42 in {39,40,41,42}
\ expected an exit code of 0, not 1
:) doesn't find 42 in {39,40,41}
:) doesn't find 42 in {39,40,41,43}
:( finds 42 in {42,40,39,41}
\ expected an exit code of 0, not 1

https://sandbox.cs50.net/checks/a6706d4746af4c36a88bee91283974a8

locally using {43,44,42} as inputs in this order:

~/workspace/pset3/find/ $ debug50 ./find 42 < numbers.txt

haystack[0] = 
haystack[1] = 
haystack[2] = 
haystack[3] = 

Found needle in haystack!

debug shows everything as expected behaviour.

Code is as follow: helpers.c

// CODE
#define LIMIT 65536
//CODE

Why does LIMIT cause this error when set to 65536 and not when set to 65535? Even though it is written in the instructions, i would like to understand it.

Answer 1

It has to do with LIMIT vis-a-vis run time. If LIMIT is defined 65536 the check50 fails. If LIMIT is defined 65535 check50 passes. Suspect it is timing out, since part of the exercise is "running time" as in:

The running time of your implementation must be in O(log n), where n is the array’s size.

Even though changing LIMIT will make the program pass the autograder, it doesn't make it right as per the spec, because it exceeds the allowable run time. If you notice in the sandbox result, check50 does a make -s. The -s switch means silent, so there is no report of the clang command you would normally see. That's part of the check50 "special sauce". You, the user, cannot know what all is being included; nor can the user know what find.c or Makefile is being used, since only helpers.c is submitted.

It would be reasonable to assume that check50 has some kind of time threshold built in, since that is part of the assignment. So for a 3 element array it runs for 3X time units, or a 4 element array, it runs for 4X time units. It just so happens, when LIMIT is 65536, it exceeds the allowable "time units". It is merely coincidence.

It would take a fair amount of reverse engineering to deobfuscate check50. That doesn't seem like a good use of time. Not to mention, it sounds like a violation of the academic honesty policy.

Answer 2

After looking more closely at this one, I'm convinced that the problem is the sort function. It appears to be corrupting the content of the values[] array and not sorting the list. (Frankly, I couldn't figure out what it was doing.) I didn't see any code that looks like it would be doing a sort.

If the values[] array isn't sorted correctly, a binary search would fail. I can't explain why it appears to be functioning correctly during manual testing, but I suspect that any successful results are likely false positives in that a success is produced, but not for the right reasons.

It would probably be helpful to print out the sorted values array at various places - the end of the sort routine and again at the beginning of the search routine. Personally, I wasn't able to print it at the end of the sort routine, but was able to do so at the beginning of sort. Go figure!