Double ended clear solution for Letter Queue by veky - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

Double ended solution in Clear category for Letter Queue by veky

def letter_queue(commands):
    import collections
    queue = collections.deque()
    for command in commands:
        if command.startswith("PUSH"):
            queue.append(command[-1])
        elif queue:
            queue.popleft()            
    return "".join(queue)

July 2, 2014

Comments:

weissesfleisch72 on July 23, 2014, 9:24 a.m.
Good solution! I saw deque mentioned in the python docs, but wasn't sure if I'd be able to import collections. I did it the slow way.

veky on July 23, 2014, 10:20 p.m.
Why wouldn't you be able to import collections? :-o

weissesfleisch72 on July 26, 2014, 1:48 a.m.
Some of these challenge type sites don't allow you to.

veky on July 26, 2014, 5:26 a.m.
Maybe, if it's some special kind of task, like forbidding keyword "for" or something like that. :-) But then it has to be specified in the text. May I ask for an example of "challenge type site" that by default doesn't allow you to import standard modules?

weissesfleisch72 on July 28, 2014, 4:10 a.m.
CodingBat for example, but those are very short problems. Maybe I'm just trying to import the wrong modules...like there is a matrix problem on this site that I tried to solve by importing numpy. Denied!

veky on July 28, 2014, 7:36 a.m.
ah. :-) I see what's going on. You see, Python (and many other languages) have a thing called "standard library". The point is that when people design a programming language, they usually give it a nice mechanism for extending (#include, import, use, \usepackage...). Then, when deciding what to put into the core language, they usually (if they are smart, which in modern days practically is equivalent to $language != PHP:)) realize that they can make core language a lot smaller, if they put some internally implementable things in such modules. Why would they do that? Well, the main reason is maintainability. Core language (embodied in a compiler/interpreter) is a pretty monolithic and giant structure, that many people are afraid to mess around with. But standard library is by definition modular, and every module is usually written in target language (or sometimes in implementation language, but with strict APIs). So it's much easier to add new features and fix bugs. So, there is a Python standard library. List of its modules can be found on <a href="https://docs.python.org/3.5/library/.">https://docs.python.org/3.5/library/.</a> It includes many things ("batteries included" is one of main reasons people love Python), but NumPy is not there. That leads to another question: why? Well, it's a much more complicated question, but my theory is that NumPy goes against some very basic tenets of Python philosophy - not because of lack of knowledge, these people know Python very well, but because of performance gains. Value semantics is a lot faster when you're doing numerics, since computers are built that way, back from the days of FORTRAN. But Python frowns on that, in my opinion justifiably. NumPy serves completely fine as a 3rd party library, and is extremely popular in certain circles, but it isn't and probably won't be endorsed by people developing "Python the language". * That doesn't mean that there won't be language enhancements to cater for the NumPy community. For the newest example, 3.5 has added @ as a matrix multiplication operator. As long as the additions are aligned with Python philosophy, they are ok. But the core idea of NumPy is probably not, at least for a foreseeable time. My guess is that Python4 will finally endorse value semantics in some awesome and ultimately correct way. :-) <hr /> BTW codingbat is incredibly archaic. It is still on Python 2.6, as far as I can see. Don't use it, it will teach you wrong. While I admit there are use cases for Python2, there should be no excuse for using anything less than 2.7.

weissesfleisch72 on Aug. 5, 2014, 2:27 a.m.
Thanks for the reply...I started poking around a bit and found the list of standard modules. I wasn't sure, because I mainly started learning Python for pen testing. They seem to use tons of third-party modules so I didn't realize there were standard ones.

lsdda on July 29, 2014, 4:59 a.m.
It's cool that you used deque which is fast on either side.

veky on July 29, 2014, 10:37 a.m.
It's the only reasonable queue in standard library. And really, once you have that implementation, of course it would be silly to write API only for FIFO usage.

ArchTauruS on Aug. 11, 2014, 1 a.m.
works, fine:)

veky on Aug. 11, 2014, 7:24 a.m.
That comma is really, interestingly placed. ;-P

artemrudenko on Aug. 19, 2014, 2:11 p.m.
Cool, as always. So far i made redundant check in my second if.

veky on Aug. 20, 2014, 5:33 p.m.
That's minor problem (and possibly even justified, for detecting invalid commands). Much bigger problem is that your solution has quadratic complexity with no good reason (stack.pop(0) has to move all the elements).

artemrudenko on Aug. 25, 2014, 8:21 a.m.
Thank you, never though about this. Will read more about deque module.

not_real on Aug. 13, 2015, 9:17 p.m.
You have convinced me. I have changed now queue.pop(0) by queue.popleft() in my solution

Eldin on Aug. 21, 2014, 4:27 p.m.
just for my info, why is it better to use deque instead of just a list where you do <blockquote> list.pop(0) ? </blockquote>

veky on Aug. 21, 2014, 6:33 p.m.
Imagine you have a list x of million items. What does x.pop(0) do? <ul> <li>it returns x[0]</li> <li>it sets x[0] to x[1]</li> <li>it sets x[1] to x[2]</li> <li>...</li> <li>it sets x[999998] to x[999999]</li> <li>it reduces len of x by 1 (deling x[999999])</li> </ul> You see the problem? :-) You do a million pointless steps. deque can be appended and popped from both ends in constant time.

silver659 on Nov. 3, 2014, 10:44 a.m.
I did not know this.

veky on Nov. 3, 2014, 10:54 a.m.
I'm glad you learned something new. ;-)

Eldin on Aug. 21, 2014, 7:50 p.m.
Thank you, I learned something today.

ljy95135 on May 27, 2016, 2:57 a.m.
Awesome, learn more about collections module and deque. :)

veky on May 27, 2016, 8:25 a.m.
While you're there, take a look at Counter. Extremely useful class. :-)

Mycroft0121 on Oct. 28, 2014, 9:16 a.m.
nice using collections!

veky on Oct. 28, 2014, 2:28 p.m.
Thanks. :-)

SplashDance on June 30, 2015, 2:40 a.m.
Quick question: Is there any benefit to writing `if command.startswith("PUSH"):` instead of something like `if "PUSH" in command:`?

veky on June 30, 2015, 4:44 a.m.
Here, since we know PUSH must be at the beginning, not much. (*There is a tiny bit of performance gain since you don't have to search the whole string, but please don't think about that.:) But usually, `.startswith` and `.contains` are different, of course. For example if you could have a PRINT command, then <pre class='brush: python'>PRINT "PUSH the button!" </pre> contains PUSH, but doesn't start with it. I wrote it in this style mostly as a habit, since I have experience of writing various command parsers in Python, and there you usually switch on the start of the command, not some arbitrary part of it.

Sedov on Aug. 25, 2015, 11:20 a.m.
Loved the line "elif queue:". Didn't think about using the boolean character of an empty list, settled for try/except instead, but I like your solution better :)

veky on Aug. 25, 2015, 1:04 p.m.
As I was already one if deep, this elif was really convenient. But even the PEP8 says <blockquote> use the fact that empty sequences are false. </blockquote> It often simplifies code. ;-) <hr /> EAFP solution would be much nicer if CiO allowed contextlib. <pre class='brush: python'>with contextlib.suppress(ValueError): queue.popleft() </pre> instead of 4 lines. Let's hope they enable it some day. ;-)

AMJ on Sept. 5, 2015, 11:42 a.m.
Why use deque collection? popleft() has same result as pop(0) use it instead and see my solution.

veky on Sept. 6, 2015, 8:38 a.m.
I suppose you've already seen the <a href="http://www.checkio.org/mission/letter-queue/publications/veky/python-3/double-ended/share/d1d2a0a6c9a81443d0be2e611f017b4d/#comment-17180">comments above</a>. But if not, <a href="https://docs.python.org/3.3/library/collections.html#collections.deque">official docs</a> are also fine. <blockquote> Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation. </blockquote>

Franky on Jan. 17, 2016, 7:28 a.m.
use -1 to get parameter is good for such well format input! and I forgot collections' emptiness can be used as condition, which is more concise way to check before pop(Saw above this is from PEP8). Learned from you.

Safwan_Samsudeen on Dec. 14, 2020, 11:34 a.m.
Nice! I did ``` queue = deque() for command in commands: try: MAPPING<a href="queue, *parts[1:]">(parts := command.split())[0]</a> except IndexError: pass return ''.join(queue) ```

veky on Dec. 15, 2020, 5:45 a.m.
This is exactly why walrus is killing Python. :-P You have lame names and indexing instead of writing Pythonic code. Isn't <pre class='brush: python'>command, *args = command.split() MAPPING[command](queue, args) </pre> so much nicer?

Safwan_Samsudeen on Dec. 15, 2020, 10:30 a.m.
It is. I didn't think of that at all, thanks.

robertabegg on Sept. 20, 2021, 11:12 p.m.
What happened to the veky who writes easy to expand on code? :) I guess this was the veky 2014 version. I went down the path of dict of f()s and arg lists for expansion of commands with multiple args.

veky on Sept. 21, 2021, 1:01 a.m.
He wrote <a href="https://py.checkio.org/mission/digit-stack/publications/veky/python-3/pointless/share/1a183ab9a4a35daf129b4583ef3a64c0/">this solution</a>. :-P [Yeah, it's a different mission, but really, it's not much different.:] Look, an important meta-lesson: I'm not always teaching the same thing. Sometimes I'm teaching how to use a data structure almost nobody knows about. Sometimes it's metaprogramming (as it should be done, not homoiconic nonsense of LISP;). Sometimes it's programming constructs that single out Python as the most expressive readable language there is. Sometimes it's something else entirely. But my programs are always meant to teach, or at least surprise, you. :-)

rybld2 on Jan. 1, 2023, 3:07 p.m.
It is always very difficult to comment on a master's solution. Here the beginner admires "for command in commands:" "queue.append(command[-1])" (doubly noteworthy) "elif tail:" excellent So just to critique, how is using a deque relevant? Wouldn't a simple list have fulfilled its role? Of course everyone writes as they want! That's the style! And Veky's is excellent.

veky on Jan. 4, 2023, 4:08 a.m.
<blockquote> how is using a deque relevant? Wouldn’t a simple list have fulfilled its role? </blockquote> Please read the comments above. For example, <a href="https://py.checkio.org/mission/letter-queue/publications/veky/python-3/double-ended/share/d1d2a0a6c9a81443d0be2e611f017b4d/#comment-35156">this one</a> or <a href="https://py.checkio.org/mission/letter-queue/publications/veky/python-3/double-ended/share/d1d2a0a6c9a81443d0be2e611f017b4d/#comment-17180">this one</a>. It will help your understanding.

rybld2 on Jan. 4, 2023, 7:39 a.m.
You could be sure there was good reason(s) for the deque. Decidedly pychekio allows us to progress

Strings Theory

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!