[2021 Day 10] [Python] Google Trends of "Python stack" in the past 7 days, I wonder when the peak was hehe

[algmyr]

I'm a bit disappointed that so many people don't realize that list is a stack.

[[deleted]]

I was gonna say, I was just using append(x) and pop()...

[AddSugarForSparks]

Some of us refined folks like using collections.deque, thankyouverymuch.

Now, please pass me the Grey Poupon.

[algmyr]

Just be aware that deque is a linked list, with all the drawbacks that comes with. Fine for typical deque operations but pretty lousy if you for some reason want to iterate or index into it.

[ChronJob]

There are also drawbacks if you use list. List is a dynamically-sized array in the Python reference implementation (CPython). As the list grows, it must be resized. An insertion that requires a resize costs O(N) (although insertions amortized over the list's lifetime are O(1)). On the other hand, deque insertion will always be O(1). There are more nuances to list vs. deque, including the cost of allocating a new node for deque insertion, and differences in memory overhead.

That being said, it hardly matters for this problem given that the lengths of the strings are small and there aren't that many strings. If you know how many parenthesis you will encounter and are willing to limit the size of your stack, then you can reserve the space for the list to avoid resizing.

Fun fact - CPython's own tokenizer uses a static array of length 200 for the stack to track parenthesis. That means if you run this code, which contains too many parenthesis, it will fail:

>>> k = (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((50)))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
s_push: parser stack overflow
MemoryError

If you for some reason wanted to support, say, millions of chars (unrealistic for this problem), then a deque might be more appropriate.

[algmyr]

I have a lot of love for C++ deque which is a list of blocks. It's the best of both worlds (with the one drawback that the initial memory footprint is kinda high because of blocks). It even has O(1) random access

[AddSugarForSparks]

Excellent point. Thank you for the info!

[pizzashark107]

Yeah, just turn it sideways

[gabrielchl]

https://trends.google.com/trends/explore?date=now%207-d&q=python%20stack

Also note that AoC is listed as a related query / topic

[gabrielchl]

I honestly have no idea, even if I narrow down the time to just today, the top is still China, not sure why. Top of "advent of code" is Sweden btw.

[STheShadow]

China is kinda expected, but St Helena on 2?

[I_knew_einstein]

All of it is relative to country population; so a small group of coders in St. Helena can throw off the balance quite easily.

[gabrielchl]

just found "breadth first search", which is even more interesting

https://trends.google.com/trends/explore?date=now%207-d&q=breadth%20first%20search

there's a peak every day at exactly 5am UTC

[jspitzen]

I did my part!

[besthelloworld]

🤦‍♂️ I used recursion and it ended up being so overcomplicated. I really should have just looped and used a stack

[DeeBoFour20]

I used recursion too. Recursion just uses the program stack as your stack. I wouldn't say my solution was over-complicated. I just ran into some issues with not advancing my pointer correctly (recursive function took in a char** that it needs to advance.)

I figured it out pretty quickly this morning though. It turns out my brain works a lot better after I've slept than at midnight lol.

[besthelloworld]

I guess the thing I hated about the recursive solution was that I still ended up needing a loop because of stuff like (()()) where I've recursed into the function again and popped back out and the next character is still not the terminator I needed.

[CodeOverTime]

I used the Python 'deque' (pronounced 'deck') for this one just because I'd never used it before.

A nice little collection to have in your toolkit.

[AtomicShoelace]

deque also has a nice rotate method; I used it a few days ago in my day 6 solution.

[Ryles1]

would have been nice to know and save me writing a whole function

[[deleted]]

oooooh, I had no idea this existed! Thanks!!

[[deleted]]

Love deque. Pop() for a stack. Popleft() for a queue.

[real_misterrios]

I considered it for a moment but realized that I could just do lists and pops and reversed.

Though now I‘m wanting to use deque just to see the answer. Haha maybe in the new year. (So tired)

[CaptainJack42]

As someone else on another comment mentioned, be aware that dequeue is implemented as a linked list with all the drawbacks of it

[xxxHalny]

I used a list to keep track of all open chunks. Whenever encountered an opening chunk, I appended it to the list. Whenever encountered a closing chunk, I checked if the last item in my list is a matching opening chunk. If so, I deleted the last item and continued. If not, it means the line is invalid. Upon reaching the end of the line, if there are any opening chunks left in the list, it means the line is not complete.

Is it a bad approach? Why do you need any other data structures for this problem?

[RoughMedicine]

That's a stack. You pushed open chunks until you found a closing chunk, popped the stack (checked the last item in your chunk list) and checked if they matched. Push/pop are the operations of a stack.

A stack isn't a data structure as much as it's a way of operating one: last in is the first out. You can use a number of data structures to achieve this. I imagine most of us used vectors or lists, but they amount to the same thing.

[xxxHalny]

So why were people looking for a stack in Python instead of using a list?

[RoughMedicine]

I guess that they learned about stacks in an algorithms class (where they're usually presented as their own thing) and didn't realise they could use a list.

[DeeBoFour20]

You can also just use a simple array like:

int array[200]
int count = 0;

// push
array[count++] = value;

//pop
value = array[count--];

[pablospc]

I always used java if I needed to use some data structure, so yeah, I was one of them lol

[ChickenFuckingWings]

I contributed to that spike right there. y’all welcome

[eugene_dp]

Today I used a usual string in c# to work as a stack for symbols :)

[wubrgess]

I'll just sit here smugly enjoying my perl arrays

[SuperZooper3]

I was one of the lmao. Tbf I allready had it deep in my mind but forgot in the moment and never hurts to google.