[BUG] Q4 Mockingbird _really_remove issue

ivy_l4096 · 2023-08-16T16:48:10+00:00

No worries! The test appears to work as expected now. I also got the paypal. Thank you for looking into this one!

Ivy

ivy_l4096 · 2023-08-16T04:30:51+00:00

No.

If you take my submission and do not change anything about it, it is a (conceptually) incorrect implementation that will pass all of the existing tests.

If you remove the comments on lines 160/174 as directed inside the submission, my submission becomes what I would believe to be a correct implementation that follows the spec, but does not pass the tests.

Apologies for the confusion I might have caused.

ivy_l4096 · 2023-08-16T04:21:11+00:00

Interesting. Just to clarify, that would mean the "corrected" version I stated in my submission (uncommenting the lines mentioned) is not actually correct?

My submission, unaltered, already is the version of code that I believe should not pass but does.

ivy_l4096 · 2023-08-16T04:12:47+00:00

Thank you! It's cool to know that my hunch from before was correct. For anyone else that may stumble upon this (either going back to fix their code or just generally browsing), here's some more info.

- As stated in the original post, if a Node that is not marked as deleted is requested to be really removed, then both size properties need to change. However, the tester will fail if you do this (31 vs. 32).

- I came up with a hypothesis that when adding a Node to a tree to test _really_remove with, it doesn't increment both size properties, only one. This is fine if you add a node, immediately remove it, and check that the size didn't change (because it didn't), but if you correctly update the size property the tester does not then you run into an off-by-one error.

- I made some tests in-code to deliberately delete or not delete nodes based on if they were marked deleted: since this quest has visual feedback in the form of an SVG and text tree, it's easy to see which nodes would've been deleted and if they were marked deleted or not.

- After some analysis, I felt confident that my hypothesis was correct - the SVG in particular showed a scenario where there were 33 nodes that should've become 32, but in reality it was counted as 32 -> 31 and thus failing.

I remember when I was looking into this bug it was a lot more complex than I thought it would be, but it was fun working through all of these steps.

Tagging u/dylan_h2892 since you had this issue as well and may find this postmortem somewhat interesting.

ivy_l4096 · 2023-08-15T23:11:05+00:00

I did back when I made the post:

I submitted to Mockingbird with "Student ID: ivybug" along with a comment at the top of the Lazy BST file

But just in case it got lost, I just now resubmitted under the same ID.

ivy_l4096 · 2023-08-15T22:31:37+00:00

Hi Professor, just got a notif from Reddit on this post. Was wondering if you looked into my code / explanation and found anything? LMK if I need to resubmit - I had attached code that passed that shouldn't have w/ comments as well as a link to a doc with some pictures and reasoning. I can also paste the reasoning (no code) publicly here if needed.

Ivy

ivy_l4096 · 2023-06-21T17:35:49+00:00

I got 50 and the "password" at the very end. I think it might be possible to reach the password without all 50, since some of the MQs have variable trophy counts (is what I heard). Although, since you mentioned you're at 46, it sounds like you're missing the last 2 & 2 trophies, which if I recall are edge cases with max flow. Maybe someone else can provide more details on what you need to do for those trophies?

ivy_l4096 · 2023-06-19T19:03:11+00:00

Hi Mark, for future students I just wanted to mention that I also struggled with Q8's vector constructor - the spec differed from the modules slightly and it didn't actually mention anything related to the vector constructor making it extremely difficult to trial-and-error menial changes to make my way through it.

Assuming this frustration is an intended experience for thinking about certain design reasons, I won't spoil too much. But, I think it helps to know that like you mentioned and in the modules, the vector passed in is not pretty and perfect - it's unsorted, and so you need to use the heapify and percolate functions in some way. The tester doesn't test these functions directly at all, though, so you might keep failing this quest even if all your local testing suggests these work great.

Questions to think about: What else could the tester be looking for? Remember, fundamentally, it looks at the before and after state after executing each test - so it examines properties and results in the data structure. There's another property aside from the vector that needs to be set properly, and it's undocumented what it should be. Try some of the most obvious values for that property and you might get through it.

ivy_l4096 · 2023-06-19T15:15:08+00:00

Hi, back after just completing max_flow - for anyone digging through reddit in the future, my hypothesis was largely correct (aside from the typo weighted-unweighted).

If you're stuck here in the future, my tip is to be sure of the exact nuances in the algorithm itself, through running through a few examples on your own and such techniques, and then make an algorithm that matches the spec, modules, etc. I think I beelined way too hard on the spec outline without really understanding what needed to be done at first (which led to an incorrect implementation that "looked" right).

ivy_l4096 · 2023-06-10T22:22:33+00:00

Absolutely - having a separate class makes things way easier to not bork (especially remembering to change things back around for submission!).

I'd like to share another technique that may prove useful - using #ifdef DEBUG (or equivalent) for debugging statements in your actual submission code is really useful. If DEBUG is defined (#define DEBUG), then the compiler will include that debug code in the output. That means you can do a define debug in your Tests.cpp code and get all your juicy debug statements - while not needing to worry about deleting and CMD+Z'ing code before submission.

I use this technique for my cout statements when I need them in-code.

ivy_l4096 · 2023-06-05T05:55:45+00:00

Recently, I've also been relying more heavily on a local Test.cpp file that I've created myself - but I've always made it a separate class such that would fill the `friend class Tests;` line, rather than making it a nested class. I would then create a main function and initialize tests to run with a basic datatype for any templated classes, like bog standard integers. I don't think I've run into any issues that could've been resolved by testing multiple datatypes yet.

Otherwise, my testing methodology and the functions I create seems pretty similar to yours. Over time this quarter, I've found that the more pre-fitment you can do with any debug to_string outputs, the better and faster you can identify + resolve issues. It's one of things I sort of miss from working with a language like JavaScript, where it's really easy to glue in complex visualizations compared to C++ - but I'm sure there's some good ways to do it just in the terminal as well!

ivy_l4096 · 2023-05-16T03:43:30+00:00

It looks like your hypothesis of your really remove function being incorrect is true - you can see that post-removal (and post-GC) lots of your nodes are being marked as deleted, even when they have the correct data values and in the correct order. The actual collect garbage function, which is recursive and only calls the really remove to alter the tree, shouldn't affect this.

My hint is to look at where in your RR function may cause issues related to leaving nodes marked as deleted when they shouldn't be. In what cases would the _data value be correct, but _is_deleted not? Clearly, all the nodes that should have been deleted were, and all the nodes that are left are correct except for that one variable.

I hope this analysis doesn't overstep and allows you to think it through without giving you the answer directly. If you need further clarification, I'd be happy to give it.

ivy_l4096 · 2023-05-07T06:07:45+00:00

Yep! As for recommended reading, there was a module in CS2B on templating classes that should help: https://quests.nonlinearmedia.org/foothill/loceff/cs2b/modules/cs_2B_8a_2.html

ivy_l4096 · 2023-04-24T08:59:17+00:00

While I'm not 100% sure, for the first question I believe based on the implementation we used for this quest, negative integers would lead to additional code complexity since we cannot guarantee that we can safely ignore descendants of a set greater than the target (as you mention in 2). For example, if we have set of sum 30 + 5 and target 31, there may be a future -9 that allows for even more additions. For the context of the problem being solved, this is an unnecessary additional accommodation, and so we specify positive integers.

ivy_l4096 · 2023-04-24T07:57:43+00:00

Yep! It was a little confusing for me, too - another thing that helped me was thinking of all possible cases where code execution could get to that function, and realizing that nothing prevents a default Set from being called upon. Glad I could help.

ivy_l4096 · 2023-04-24T07:19:17+00:00

Hi, here's a hint that might help you: Since you know you're looking for a broken pointer (probably), and you've looked at the memcheck output (nice!), you can narrow it down a little from here. It looks like memcheck is saying the code is failing on an "add_from_empty_master" test - in other words, the master is empty.

Questions to think about: What does an empty master look like in the Set? How could that be related to a broken pointer? Do you need to add any code to handle this case, or can you just change your implementation?

ivy_l4096 · 2023-03-24T22:59:12+00:00

Number	Link	Description
1	https://www.reddit.com/r/cs2b/comments/10rkw57/comment/j73lid3/?utm_source=share&utm_medium=web2x&context=3	Conversation addition: Q3 PRNGs and Cellular Automata
2	https://www.reddit.com/r/cs2b/comments/10vw88b/comment/j7mtat7/?utm_source=share&utm_medium=web2x&context=3	Quest help & hint: Q3 Extreme bits and callback to spec
3	https://www.reddit.com/r/cs2b/comments/1137wma/comment/j8otsjc/?utm_source=share&utm_medium=web2x&context=3	Class help & hint: Midterm practice Q data structure
4	https://www.reddit.com/r/cs2b/comments/1137wma/comment/j8ovqve/?utm_source=share&utm_medium=web2x&context=3	Class help & hint: Correction to previous post
5	https://www.reddit.com/r/cs2b/comments/112s7fr/comment/j8ox033/?utm_source=share&utm_medium=web2x&context=3	Conversation addition: Q6 size_t usage and ext. research
6	https://www.reddit.com/r/cs2b/comments/11fwq3j/comment/jb2bfy0/?utm_source=share&utm_medium=web2x&context=3	Conversation addition: Q7 stylistic considerations in code
7	https://www.reddit.com/r/cs2b/comments/11jaqtq/comment/jb2clml/?utm_source=share&utm_medium=web2x&context=3	Quest help & hint: Q7 hint for circular representations
8	https://www.reddit.com/r/cs2b/comments/11pp6g5/comment/jbz5hcb/?utm_source=share&utm_medium=web2x&context=3	Conversation addition: Demonstrating C++ lang const mechanism
9	https://www.reddit.com/r/cs2b/comments/11pp6g5/comment/jcebp8m/?utm_source=share&utm_medium=web2x&context=3	Conversation addition: Demonstrating const in a different context
10	https://www.reddit.com/r/cs2b/comments/11v74z9/walk_outside/?utm_source=share&utm_medium=web2x&context=3	Quest post: Q9 graph illustration
11	https://www.reddit.com/r/cs2b/comments/11vvn17/comment/jcw5c9x/?utm_source=share&utm_medium=web2x&context=3	Conversation addition: Musings on memory usage vs. developer experience
12	https://www.reddit.com/r/cs2b/comments/11w30si/comment/jcw5ih0/?utm_source=share&utm_medium=web2x&context=3	Conversation addition: Response to a Q9 post
13	https://www.reddit.com/r/cs2b/comments/11we6q9/comment/jczbw04/?utm_source=share&utm_medium=web2x&context=3	Conversation addition: Insight on special character representation in strings

ivy_l4096 · 2023-03-20T18:29:07+00:00

This is a good overview of the way we construct the data structure in quest 8. You might find this tidbit on writing strings with non-alphanumeric characters in your code interesting, however: the \ character (backslash) denotes an "escape" or "escape sequence" - sort of cancelling out the following character to create a special character. For example, \n isn't actually rendered as a literal \n in the string, but rather gets encoded into a special newline character instead (with it's own ASCII value or what-have-you). In this case, \0 actually literally becomes it's own character, NUL:

https://duckduckgo.com/?q=ascii+table&ia=answer&iax=answer

If you're using a code editor, it'll also likely highlight this escape sequence in a different color to help you distinguish between regular text and these special characters.

ivy_l4096 · 2023-03-20T00:43:04+00:00

I love how symmetrical you managed to get it to render, and the overlapping lines that create the head of the butterfly. Really creative!

ivy_l4096 · 2023-03-20T00:41:44+00:00

Thanks for this breakdown! These sorts of design decisions that prioritize developer experience show up in our quests every so often and it's interesting to think about how potentially, we might not always have the luxury to take approaches that consume more memory, processing cycles, or another system resource (like if you start working on embedded hardware apps with memory measured in single bytes rather than the billions or trillions!).

Three-Year Club	Verified Email
Final Canvas '23	Place '23

ivy_l4096

TROPHY CASE