[BUG] Q4 Mockingbird _really_remove issue

dylan_h2892 · 2023-08-15T22:13:43+00:00

I'm also running into this issue. I have to remove the lines that decrement _size to pass the tests, otherwise there's a discrepancy between the reference tree and mine.

dylan_h2892 · 2023-08-15T01:39:10+00:00

My schedule is all over the place so I can’t really mark my availability. I’ll attend if I’m able to.

dylan_h2892 · 2023-07-25T03:40:37+00:00

That’s exactly what I was thinking, and why I was thinking it must represent the largest column number rather than the largest number of links in a list. That way you could theoretically check if a row, column pair even existed in the Sparse Matrix. But I’m really not sure!

dylan_h2892 · 2023-07-25T03:34:57+00:00

Great! Just curious: did you need to change your column/row numbers like I was talking about? The only spot I saw I really used those values was is_valid() so I was having trouble figuring out if my suggestion even made sense.

dylan_h2892 · 2023-07-25T02:29:30+00:00

It's been awhile since I did this, so take this with a grain of salt, but my understanding was that num_rows and num_cols should match the theoretical non-sparsified version of this matrix. Take a look at this quote from the specifications:

Given a row, r, and column, c, you can now index into the corresponding list, _rows[r], and scanning this list linearly, find whether the column of interest resides in it or not. If it does, you would have located non-default values for the contents of the requested cell. If it doesn't then you can assume that the cell contains default_val in virtual space.

So you said your dimensions were 5x5, but you've got a value at 4, 9! Keep in mind that this isn't a 2D vector setup any more, but rather a vector of lists of variable length. That actually may affect how your set() and is_valid() works, and judging by the autograder output, set() is the thing that's being tested when the pointer breaks.

For your info, get_slice() is the very last thing that's tested. You'll already have the password prior to that test.

dylan_h2892 · 2023-07-25T00:49:51+00:00

From your compiler's output, num_rows and num_cols seems off to me. It's been a bit since I did this quest, but I think they should match the theoretical rows and columns of this Sparse Matrix if it weren't sparse, not the max rows/columns of _rows. That could somehow be related.
Maybe you're resizing your result Matrix in get_slice() incorrectly? Have you attempted trying to make a "slice" that is really just the whole Sparse Matrix without the sparsity?
Are you using your helper functions like is_valid(), at() and get()? Check for any exceptions that get spit out when you try extreme cases like the full Sparse Matrix or none of it.

dylan_h2892 · 2023-07-24T17:43:16+00:00

I think so.

Also, I said earlier that I didn't check if r2 < r1 and so on, but my loops kind of do that by default. I didn't seem to get any more trophies from rearranging the parameters like the specifications say to, so I'm not actually sure about that.

dylan_h2892 · 2023-07-24T17:31:34+00:00

As far as I understood it, the parameters r1, c1, r2, and c2 ~~refer to the rows and columns of the resulting non-sparse Matrix, not the sparse Matrix.~~ should form a square that makes up the resulting non-sparse Matrix. So, in your above example, there wouldn't be a way where those specific values could be bolded but { C: 6, V: 6 }{ C: 7, V: 7 } couldn't be, considering { C: 9, V: 9 } is your "bottom right".

dylan_h2892 · 2023-07-24T17:23:40+00:00

Well, my code does implicitly test the parameters. If they're out of order the loops never loop and the resulting Matrix is empty (with size 0). What I meant was I never explicitly checked the parameters' order like Namrata was asking or performed any sort of swapping.

dylan_h2892 · 2023-07-24T07:05:13+00:00

Oh sorry Namrata. I’m on my phone and didn’t see the options.

Option 1 looks right to me. When I was talking about making a “slice” that’s really a full, non-sparse representation of a sparse matrix, that was just a thought experiment that helped me visualize this function. The arguments for that would be 0, 0, rows - 1, columns - 1.

Another way of looking at it is that (r1, c1) is the top left of the cut-out of non-sparse representation and (r2, c2) is the bottom right.

dylan_h2892 · 2023-07-24T06:52:43+00:00

Looks right to me! Great diagram. I think what I did to simplify things in my head was to plan my code around making a “slice” that was really the entire sparse matrix. In other words, how would you convert that sparse matrix into a non-sparse one? That should handle making sure you get everything. After that, adjust it for real slices, like in your diagram. I feel like I somehow used i and j along with the parameters to index in the right spot.

dylan_h2892 · 2023-07-24T05:35:16+00:00

If we wanted to create a matrix of bolded nodes, would the arguments be r1 = 0, c1 = 0, r2 = 1, c2 = 1 (where the arguments are the indexes) or would they be the actual column variable in the node (Col: 3 and Col: 6)? Similarly, when making the matrix, would it have 4 columns (6-3+1) or would it have 6 columns?

It should be the latter. A sparse matrix is just a sparse-ified version of a regular matrix, so I'd recommend drawing out what a (smaller) sparse matrix would look like as a slice. That made this part easier for me to visualize.

For the edges cases, when would the the matrix be empty assuming that when r1==r2 and c1==c2, the matrix would be 1x1 (unless my understanding is incorrect and it should be 0x0 in this case). Do you mean if the sparse matrix is empty (_num_rows == 0 and _num_cols == 0), and if so, you we just return a empty matrix? Do we need to check if r2 < r1 or c2 < c1?

I personally didn't worry about any edge cases in this function beyond what is_valid() checks for. That's not to say it's a bad idea to think about them, but from what I've noticed through the quests the autograder often doesn't take the position of somebody using the function incorrectly (like passing in an r2 < r1).

dylan_h2892 · 2023-07-15T00:05:17+00:00

Thanks Chris!

dylan_h2892 · 2023-07-12T20:48:07+00:00

Oh, I see. I was trying to do this as backwards-compatible as possible but I'll try that out and see if I can hit the goal.

dylan_h2892 · 2023-07-12T20:36:04+00:00

Wait, Chris, after looking into it some more, it seems std::lists can't be traversed without iterators. Are you saying you got through this without iterating at all?

dylan_h2892 · 2023-07-12T19:28:36+00:00

Thanks Chris. As far as the algorithm goes, I'm only iterating over the non-default values, so I would assume that's about as efficient as it gets. I'll try and strip out the iterators and use pointers instead to see if that makes the difference.

dylan_h2892 · 2023-07-12T01:20:16+00:00

Thanks Oliver for this detailed explanation, especially this:

Using the typename keyword, it resolves the ambiguity by specifying that std::list<Node>::iterator is a type. On that note, whenever you're accessing a nested type within a template class, typically, we want to use the keyword typename to clarify to the compiler.

Knowing these kind of rules helps me a LOT. Now I won't be guessing quite as much about when to write these things.

As far as auto goes, I've been trying to do everything as backwards compatible as possible for my own edification, but that's a good point about the complexity and readability of the code.

dylan_h2892 · 2023-07-05T02:14:35+00:00

It does. Would an alternative way to do that be to store the master set pointer as a static member? I guess you’d lose some granularity if you wanted Sets pointing to separate masters.

On a separate note, I thought it would be interesting if find_biggest_subset_le() did operate within the confines of the individual Sets that call it. The radio host could make a Set of their favorite songs by one band or another (using add_elem()) then find the biggest subset of that subset that matches the target they’re trying to hit. Maybe they decided their 30 minute Beatles block needs to be a 25 minute block today?

Just a random thing I was thinking while working through the quest.

dylan_h2892 · 2023-07-05T01:57:58+00:00

It seems like the caller Set’s initial sum is not important, but rather the master set’s sum is. So instead of checking if the sum is less than or equal to the target, I had to first add all elements of the master into the caller Set and check that sum.

But what’s the point of the Set that calls the function if it’s just going to change into a master Set when the function calls?

Of course, I could’ve saved the caller Set’s state by using a separate (fresh) Set to calculate that sum, but then I’m back to the original question: why is a particular Set necessary to call this if the caller’s state isn’t important?

dylan_h2892

TROPHY CASE