# Using deque for composing a string from 2 alternating stacks

We have 2 strings, say "JACK" and "DANIELS". We create two stacks from these strings, and then loop over them comparing first elements: whichever of the 2 goes first in lexicographic order gets popped from its stack and added to a string (the second value is left alone). So it goes, until we end up with a string containing all the elements from both stacks. In this example it would be "DAJACKNIELS"

My solution takes advantage of the fact that min function, when applied to deque() objects, returns the one whose first element goes lexicographically first. As it happens, it works well enough for small testcases, but fails large ones, for it takes all the memory it can get and then some.

Perhaps, something can be improved in my code, or there's a better solution altogether (like, without a while loop).

def morgan(a, b):
string = ""
stack_a = deque()
stack_b = deque()

stack_a.extend(a)
stack_b.extend(b)
while True:
if len(stack_a) != 0 and len(stack_b) != 0:
if stack_a == min(stack_a, stack_b):
string += stack_a.popleft()
else:
string += stack_b.popleft()
elif len(stack_a) == 0 and len(stack_b) == 0:
break
elif len(stack_a) == 0:
string += stack_b.popleft()
elif len(stack_b) == 0:
string += stack_a.popleft()
return(string)


Example of a large testcase:

string a: https://pastebin.com/raw/pebMbcA6
string b: https://pastebin.com/raw/bwNEqJcr

• See heapq.merge() from the standard library. Look at the library source code to learn how it works. ''.join(heapq.merge(a, b)) Jun 8 '20 at 6:31
• @tinstaafl: I don't understand your problem. To me it seems like the code works in general. It works specifically on my machine for both test cases but not on the server of the programming challenge in case of the larger, because it runs ot of memory (or there is a limit). Therefore it needs improvement, specifically in how memory-efficient it is. This is specifically on-topic here, which is why the tag memory-optimization exists. Jun 8 '20 at 13:10

There is no need to read the whole string into a deque. Just iterate over the strings using iterators. The only gotcha is handling the fact that either of the strings can be empty at the beginning and that one can be exhausted before the other.

def _morgan(a, b):
a, b = iter(a), iter(b)
try:
x = next(a)
except StopIteration:
yield from b
return
try:
y = next(b)
except StopIteration:
yield x
yield from a
return
while True:
if x <= y:  # <= because that's what min does
yield x
try:
x = next(a)
except StopIteration:
yield y
yield from b
return
else:
yield y
try:
y = next(b)
except StopIteration:
yield x
yield from a
return

def morgan(a, b):
return "".join(_morgan(a, b))


Note that both the original strings and the resulting string still need to fit into memory for this to work. If you only need to iterate over the resulting string, use only the private function. In that case the original strings still need to fit into memory, unless you also have them as generators (e.g. by streaming the contents from the URLs):

import requests

def stream(url, chunk_size=1000):
with requests.get(url, stream=True) as r:
for chunk in r.iter_content(chunk_size=chunk_size, decode_unicode=True):
yield from iter(chunk)

if __name__ == "__main__":
a = stream("https://pastebin.com/raw/pebMbcA6")
b = stream("https://pastebin.com/raw/bwNEqJcr")
c = _morgan(a, b)
while (chunk := "".join(islice(c, 1000))):
print(chunk, end='')
print()


This works on my machine with the given strings, but so does the morgan function I defined above.

Note that you need Python 3.8+ for the walrus operator :=. With earlier Python versions it is slightly more verbose:

 if __name__ == "__main__":
a = stream("https://pastebin.com/raw/pebMbcA6")
b = stream("https://pastebin.com/raw/bwNEqJcr")
c = _morgan(a, b)
chunk = "".join(islice(c, 1000))
while chunk:
print(chunk, end='')
chunk = "".join(islice(c, 1000))
print()

• itertools.zip_longest would probably help with handling the shorter iterable.
– AKX
Jun 8 '20 at 10:42
• @AKX: Not really, because you don't need pairs. E.g. for "AAA", "BBB", the output needs to be "AAABBB". Jun 8 '20 at 10:44
• Ah yeah, true. And here I thought I had a neat 3-line version of this... :)
– AKX
Jun 8 '20 at 10:45
• @AKX: Yeah, right before posting I thought of that as well, thinking that my code was overkill. But then I realized it doesn't help. At least I can't see how :) Jun 8 '20 at 10:47
• @Graipher, @RootTwo, hey guys, so I've finally found the time to test your code, and there's good news and bad news: good news it's fast, bad news it produces wrong result. This goes for both your versions - they return the same stuff (long strings; compared them with ==), but it only sometimes coincides with HR's expected results for given testcases. Should I post this as a separate question here? CodeReview doesn't really seem to fit the issue, but I'm not sure. What say you? Jun 19 '20 at 20:31

### next(iterable, [ default ])

I find too many try-except block can be distracting. next() takes an optional second argument--a default value to return when the iteration finishes. Here is @Graipher's _morgan() function using the 2-argument form of next() instead of try-except.

def _morgan(a, b):
a = iter(a)
x = next(a, None)

b = iter(b)
y = next(b, None)

while x and y:
if x <= y:
yield x
x = next(a, None)
else:
yield y
y = next(b, None)

if x:
yield x
yield from a
else:
yield y
yield from b

• very interesting concept (the next()). Thanks, I don't know how else I would've learned about it Jun 9 '20 at 20:33