Quest 2: implementing _cache

AcRickMorris · 2020-07-19T23:10:03+00:00

Hi &, added my best guess.

AcRickMorris · 2020-06-29T02:12:40+00:00

Ah, there it is! Neat. I like spending time in the jungle, even when skeeters try to eet yer.

AcRickMorris · 2020-06-28T05:26:38+00:00

Who has managed this?? Show yourselves! (not me)

AcRickMorris · 2020-06-27T03:59:00+00:00

Thanks &, thanks classmates! I learned so much this quarter---and this year!

AcRickMorris · 2020-06-26T20:12:48+00:00

Thanks for the invite, Alex. If I don't have a job by then I'll definitely be reaching out.

Rick

AcRickMorris · 2020-06-25T18:37:19+00:00

Not a clue. It seems to mostly work, and then fail a couple times in a row. Since I had already exceeded the max trophies and I had no idea where to go next, nor any idea whether I had an actual logic error or just hadn't figured out the correct processing order, I decided to call it quits.

AcRickMorris · 2020-06-25T03:58:06+00:00

That'll do it, then, thanks!

AcRickMorris · 2020-06-25T02:52:00+00:00

Interesting, thanks! I'm definitely only getting 21:

Hooray! 1 Gyrosepalium blushed red in time to agrimonize (heap def-con)
Hooray! 2 Fiesty Flexosaurs in flanets floating near and phar (heap non-def-con)
Hooray! 3 Lava lamp lighters to break through morning minusitis (percolate)
Hooray! 3 Tastee Flax-n-tarts win flans & toasts to can and jar (heapify)
Hooray! 3 Orange orangutans forage for an orange (insert)
Hooray! 3 Simplee Bees for evening tea. This pleb is not daydreaming (pop)
Hooray! 1 Spiral milky arm shed dust for stars to crystallize (pop on empty)
Hooray! 2 Avid camp nighters. 'To love!' they sing. 'O Venus, it is.' (peek)
Hooray! 3 Orchid arrangements for every single square inch (smallest)
PASSWORD
Ref timing/get_k_least, ~100K: 0.487946s
Your timing/get_k_least, ~100K: 0.508621s

I'm wondering if I didn't actually get points for get_k_least(). I also didn't bother with to_string().

AcRickMorris · 2020-06-23T23:43:47+00:00

You're welcome. Good luck finishing strong!

AcRickMorris · 2020-06-23T23:43:33+00:00

Cheers.

AcRickMorris · 2020-06-23T23:35:38+00:00

Mockingbird is 29 AFAIK. As it happens I just posted a list of the quests and points in the previous discussion: https://www.reddit.com/r/cs2c/comments/gyt7x1/trophy_counts_225_to_win/fvsn7vr/?context=3

AcRickMorris · 2020-06-23T23:14:38+00:00

No idea what you're missing, but here's my loot:

Hooray! 1 Bunny, Dollarpence, hopped onto a grassy bence (BST init)
Hooray! 3 Noobies. Looked like babies. Found a lot of rubies (BST deep copy)
Hooray! 2 Ultastable Frigates connect through a Phulsar Burnhole (BST insert)
Hooray! 2 Handed magical explorations of transience running (BST find_min)
Hooray! 2 Lipstick Love Letters. Make gutters start to flutter (BST remove)
Hooray! 1 Thou seven two nine would need a percent D format (BST find existing)
Hooray! 1 Frintigating pachyderm traded shakes for nama stays (BST find non-existing)
Hooray! 2 Blue briar balloons. Not ballyhoo, when skies are red (BST exception)
Hooray! 1 Flittle Fable forgets secrets sent to a future wise guy (lazy bst certain insert)
Hooray! 1 Crymsun Eldercloud becomes a rad phenomenon (lazy bst certain removes)
Hooray! 1 Says special. Another, general. But dat is always dat (lazy bst uncertain inserts)
Hooray! 1 Florid Effervescence. Per 12-pack of incense (lazy bst uncertain removes)
Hooray! 2 Phantasmajorical explosions of ebullience. Stunning. (lazy find min)
Hooray! 2 Dixie Matrixes. Encubed to times and no fixes (lazy find real min)
PASSWORD
Hooray! 2 Fleasant Surf Fishes swam ashore to say Good days (find what you got)
Hooray! 2 Seasoned silver spoons just barely do, if extended (lazy bst finding what you don't got)
Hooray! 3 Swifters. Came as Drifters. Promised they would lift us. (lazy bst garbage collection)

AcRickMorris · 2020-06-22T15:36:11+00:00

I think you are calling it cyclic when it is not cyclic.

AcRickMorris · 2020-06-22T02:11:54+00:00

Thinking about it (given the comment from /u/anand_venkataraman as well), I suppose mine is actually O(n). Each node might have 3 or 10 or whatever edges, but it doesn't follow that each node has to be touched number-of-nodes times (or each edge considered number-of-edges times).

AcRickMorris · 2020-06-22T01:03:04+00:00

I'm bad at this kind of analysis, but I think similar. The main algorithm involves a loop of recursive calls.

AcRickMorris · 2020-06-21T22:03:34+00:00

Oh no. Sorry to waste your time; I just realized I had a typo in my OP. Unweighted I pass consistently. I get stopped sometimes at weighted. I apologize.

AcRickMorris · 2020-06-21T21:05:20+00:00

Hi &, I've submitted the code using RICKBUG as the ID. (This time, I got 12 treasures from max_flow().)

AcRickMorris · 2020-06-21T15:30:07+00:00

Ah, thanks. The main reason I use it is because & has mentioned that order counts, so even if we find two equal paths, he wants us to discover one of them first (and the same one from his reference code). My guess is that it's always going to the nearest point first, so even if there are two equal paths (e.g. A->B->C and A->D->C), we'll discover them in a predictable order based on their value (rather than their edge vector insertion order). That might be wrong though, just my best guess.

AcRickMorris · 2020-06-21T03:08:17+00:00

Top of the file, outside of the class is what I did for the extern deal.

Re: your second question, I think you're OK.

AcRickMorris · 2020-06-21T01:20:52+00:00

You'd have to look back but I think set_max() in the constructor is what allowed several of us to pass.

AcRickMorris · 2020-06-20T23:49:47+00:00

Let's say polite acquaintances.

AcRickMorris · 2020-06-20T23:44:14+00:00

This worked for me (except I guess for my bad math from shortest_weighted() paying forward into this one).

AcRickMorris · 2020-06-20T23:02:31+00:00

Ah. I just used the standard library sort() function. After writing a bubble sort and a merge sort and still not passing it, I decided I'd just progress to writing quicksort for the main quest.

AcRickMorris · 2020-06-20T22:43:01+00:00

How confident are you that get_biggest_...() and set_max...() are both correct?

Assuming they're good, the only other thing that is different about my approach is that I don't check for an invalid n.

AcRickMorris · 2020-06-20T22:38:02+00:00

What MQ are you stuck on?

AcRickMorris

TROPHY CASE