0

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.

Improve this question
4
  • 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. – Cliff B May 30 '17 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 '17 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. – Cliff B May 30 '17 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 '17 at 4:24
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.

Improve this answer
4
  • 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 '17 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). – DinoCoderSaurus May 30 '17 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 '17 at 16:30
  • added info to answer. – DinoCoderSaurus May 30 '17 at 17:22
0

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!

Improve this answer
2
  • In debugger and by using printf i can get the array's content sorted as expected both in sort call and search call. I will edit the code in a more explicit way. – sp3 May 30 '17 at 4:43
  • And i tested with a lot of values including pseudo random from the CS50 generate function. Worked as expected.. – sp3 May 30 '17 at 5:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .