3
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ See heapq.merge() from the standard library. Look at the library source code to learn how it works. ''.join(heapq.merge(a, b)) \$\endgroup\$
    – RootTwo
    Jun 8 '20 at 6:31
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – Graipher
    Jun 8 '20 at 13:10
2
\$\begingroup\$

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()
\$\endgroup\$
7
  • \$\begingroup\$ itertools.zip_longest would probably help with handling the shorter iterable. \$\endgroup\$
    – AKX
    Jun 8 '20 at 10:42
  • \$\begingroup\$ @AKX: Not really, because you don't need pairs. E.g. for "AAA", "BBB", the output needs to be "AAABBB". \$\endgroup\$
    – Graipher
    Jun 8 '20 at 10:44
  • 1
    \$\begingroup\$ Ah yeah, true. And here I thought I had a neat 3-line version of this... :) \$\endgroup\$
    – AKX
    Jun 8 '20 at 10:45
  • 2
    \$\begingroup\$ @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 :) \$\endgroup\$
    – Graipher
    Jun 8 '20 at 10:47
  • \$\begingroup\$ @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? \$\endgroup\$ Jun 19 '20 at 20:31
2
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ very interesting concept (the next()). Thanks, I don't know how else I would've learned about it \$\endgroup\$ Jun 9 '20 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.