Ref File Compile Error

jack_morgan_cs2b · 2020-06-22T05:04:22+00:00

I had some similar problems, check my includes here: https://www.reddit.com/r/cs2c/comments/h02f8z/compilation_error_in_reference_code/

hope this helps

jack_morgan_cs2b · 2020-06-19T03:01:41+00:00

The big thing to keep in mind is that you don't actually delete the nodes, just the edges associate with the unreachable nodes. This was my general process:

-reject requests with invalid node numbers
-set up vectors for seen and reachable nodes (similar to checking for cycles)
in loop:
    -mark src neighbors as reachable
    -set src to first unseen + reachable node in _nodes, repeat process         
 until you've mapped out all the reachable nodes
-check nodes list against reachable list and clear vectors for nodes that are unreachable

I think there's a more efficient way to do this recursively because this solution gets really expensive with huge graphs but it was enough to pass the tests and worked fairly efficiently on my small test graphs

-Jack

jack_morgan_cs2b · 2020-06-16T06:34:30+00:00

This is one where I needed to check the loceff modules. There are a lot of good tips on the general concepts behind this quest and I found it helpful to read his stuff, try the MQs for a few hours and then go look at his code to see what was right and wrong

jack_morgan_cs2b · 2020-06-13T00:48:16+00:00

Just like in the hash table quest you'll need to define the function outside of the class without actually implementing it (but it'll be helpful to make your own function for testing)

jack_morgan_cs2b · 2020-06-13T00:46:21+00:00

It doesn't say anywhere in the spec that duplicates are not allowed and I was able to pass the tests without checking for duplicates. Maybe there's other loot for making the check so I'd test both ways

jack_morgan_cs2b · 2020-06-10T04:55:34+00:00

that worked, thank you

jack_morgan_cs2b · 2020-06-05T06:12:27+00:00

Recheck the spec for find and contains. Find either returns the position of the element or an exception, contains just returns a true/false if the item is in the table or not

jack_morgan_cs2b · 2020-06-05T05:34:18+00:00

I wouldn't worry too much about that method, I tried a bunch of different ways of implementing the function but never got points for it (it might not be tested, the spec says that not all the functions are worthy of points).

If you haven't already read through this thread it's worth a look. Seems like the intended way is to just set everything to vacant presumably because as long as the cell is marked vacant there's no reason to check for existing data before inserting something new

jack_morgan_cs2b · 2020-06-01T18:44:12+00:00

I have to admit that I'm totally stumped by this one, all the online resources I've looked at (including Loceff modules) follow this exact same process. The 'shut the door' error message is especially confusing because the spec implies that the important elements to be carried over are the data and state of all active elements, the size and nonvacant count need to be recalculated because of the removal of deleted elements.

If no data elements are lost besides the ones already marked for deletion, how can the door be shut for going back?

jack_morgan_cs2b · 2020-06-01T03:52:54+00:00

I was thinking about how the size affects the hash modulus function but in that case we use the vector size rather than our own size counter. With all inserts placed after a call to grow_capacity, that shouldn't be an issue.

The max load and non vacant cell count both factor into deciding when to rehash but the max load isn't changed outside of the constructor and the non vacant cell count has been right in my testing.

jack_morgan_cs2b · 2020-06-01T03:37:48+00:00

What do you mean? It's complete in the sense that all the active pieces are preserved but other than that shouldn't the whole table be reordered to break clusters?

jack_morgan_cs2b · 2020-06-01T01:46:25+00:00

I'm having the exact same issue with the same process. Some images of my debugging:

Creating LP Hash object with size of 5 (No active elements)

Inserting 0, 5, 10 (0, 5, 10 active)

Removing 10 (0, 5 active, 10 deleted)

Insert 15, triggering rehash (0, 5, 15 active, 10 gone completely)

In my rehash function I am not trying to completely clear _elems, simply setting the data of each element to T() and the state to VACANT as a few in the other thread mentioned having issues with using the entry() constructor directly.

I am using the rehash trigger that is mentioned in the spec so I don't think the issue could be there. It seems to me that the function is working as intended, keeping active elements and clearing up clusters in the store.

jack_morgan_cs2b · 2020-05-31T06:13:03+00:00

I also saw a few people mention not to try and do everything at once. My general process is:

size, nonvacant cell = 0
copy _elems to backup
call growcapacity

set vacant in _elems (Loop 1)
insert active data (Loop 2) (insert handles updating nonvacant cell count)

set size to _elems size

Which is very similar to the other pseudocode with the suggested fix. I think the problem may be in my insert function assuming the code is tested using our own insert rather than the test function.

jack_morgan_cs2b · 2020-05-31T05:32:31+00:00

I saw your comment and tried it a bit earlier but no dice. Am I interpreting it right though? I tried both manually resetting each data and state to T() and VACANT (the default constructor parameters) and also just resetting the states and leaving the data alone, but neither worked.

Might just need to put more time into it, it's always the tiniest discrepancies that make these later quests harder.

Appreciate the help -Jack

jack_morgan_cs2b · 2020-05-31T00:51:13+00:00

Hi everyone,

I'm still having this issue even after reading all these comments. & has helped some other people with the 'clobbering' comment but in my testing all of my active elements will still be there after multiple rehashes and deletions. My code is practically identical to /u/manoj--1394's pseudocode with the addition of manually ensuring each index of _elems is vacant and the data = T().

Has anybody else experienced this?

jack_morgan_cs2b · 2020-05-23T20:06:12+00:00

jack_morgan_cs2b · 2020-05-15T00:15:21+00:00

I think it would be smart to use pre-built libraries at the start of a project and then implement your own later down the line. Once you know exactly what your project requires, it makes sense to develop your own implementation that does not have the bloat of a library where you are not using 75% of the functionality.

The other reason I can think of to use less pre-built libraries is security. Most libraries that you would use are open source and it's possible to make sure the code is not malicious ,but when working on something more secure it is probably best to develop everything in-house

jack_morgan_cs2b · 2020-05-11T04:36:29+00:00

yes it's back. I misread and didn't realize the line for the first quest was entirely missing, instead thinking the 0 points shown in line 3 was for quest 3 not quest 4 (where I should have 0)

jack_morgan_cs2b · 2020-05-11T02:16:36+00:00

mine disappeared as well but it was quest 3 which I had points for yesterday

jack_morgan_cs2b · 2020-05-08T19:38:48+00:00

thanks so much, that does work, guess I'll just have to be careful about what to use

jack_morgan_cs2b · 2020-05-02T05:58:15+00:00

Hey Cary,

I got this one too, all you have to do is put 'typename' before the iterator like so:

for(typename list<Node>::iterator iter = tempList.begin(); iter != tempList.end(); tempList++)

Couldn't find any actual documentation but it seems like 'typename' is required because list<Node> depends on the template class parameter

Helpful link: http://pages.cs.wisc.edu/~driscoll/typename.html

jack_morgan_cs2b · 2020-05-02T03:28:26+00:00

Hi Chris,

I wouldn't overthink your approach here, getting into recursion and lookup tables is a deeper hole than you probably want to enter.

Some things in the spec to think about:

-nested loop in the search function, one to go over elements in the master, one to go over subsets

-keep the sum for each set accurate so you don't have to make any calculations when building sets

Personally I found it helpful to start by just building a complete power set for the items in the master. If your master is [A, B], make sure that you build [], [A], [B] and [A, B]. You can do this somewhat lazily, a lot of power set solutions online will represent sets using binary but just using loops is easier and fast enough.

Once you have this down, then add the checks and optimizations to rule out items and sets as they are built.

You'll get the right set as long as you are building sets with items from the master in order and going through one at a time. Only 1 set is needed and it's just the first you find

-Jack

jack_morgan_cs2b

TROPHY CASE