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

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.

• Without seeing any code, there's no way to know. Please edit your question and post the search code. My first instinct though, is that the code is finding the needle but simply returning the wrong value. May 30, 2017 at 0:58
• I posted all the code to avoid re editing later. In debugger, it stops on the right breakpoints (set to the return statements).
– sp3
May 30, 2017 at 2:27
• After thoroughly looking at the problem, I decided that my previous answer had nothing to do with the problem, so I deleted it. I really need to stop trying to multitasking when answering these things! :-( Still looking at it. May 30, 2017 at 4:17
• Well, we are not that far from a computer doing one thing at a time... As soon as we start thinking about several things our focus start to shatter :)
– sp3
May 30, 2017 at 4:24

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.

• Perfect! :) Thanks so much. Was blocked for much time... After changing LIMIT and MAX to 65535, it works fine. The reason behind this might also be that 65535 is the limit range of 16 bits?
– sp3
May 30, 2017 at 16:19
• chek50 is inscrutable, so reason is only a guess. Remeber, this makes the code pass check50 -- it doesn't make it right as per spec, since it runs in `O(65535 + n)` which is much "longer" than `O(log n)`. May 30, 2017 at 16:24
• Interesting, i'll have a look at to get the O log n time. Edited the question just in case someone knws check50 in depth.
– sp3
May 30, 2017 at 16:30