2
\$\begingroup\$

I want to add custom punctuations in a given string.

eg:

US 8012999 B2 --> US 8,012,999 B2
US 20170107206 A1 --> US 20170107206 A1
EP 2795605 B1 --> EP 2 795 605 B1
US 09700674 --> US 09/700,674

This is what I wrote

def punctuate(text, punctuations):
    """Given text and list of tuple(index, puncuation)
    returns punctuated text"""

    char_list = list(text)
    k = 0
    for i, char in punctuations:
        char_list.insert(i + k, char)
        k += 1
    return "".join(char_list)

In [53]: punctuate('US 8012999 B2', [(4, ','), (7, ',')])
Out[53]: 'US 8,012,999 B2'

In [54]: punctuate('US 20170107206 A1', [(7, '/')])
Out[54]: 'US 2017/0107206 A1'

In [55]: punctuate('US 09700674', [(5, '/'), (8, ',')])
Out[55]: 'US 09/700,674'

In [56]: punctuate('EP 2795605 B1', [(4, ' '), (7, ' ')])
Out[56]: 'EP 2 795 605 B1'

This works fine. Is this the best way to do it? The punctuations list will always be sorted one starting from lower to higher index.

\$\endgroup\$
  • \$\begingroup\$ Yeah, always. For now. I also thought of sorting it first regardless but it will again unnecessarily complicate thing here by creating x,y problem. \$\endgroup\$ – Rahul Patel Mar 15 at 15:29
  • \$\begingroup\$ Added. Thanks.. \$\endgroup\$ – Rahul Patel Mar 15 at 16:24
  • 2
    \$\begingroup\$ What is the reason for this code? what is the business requirement? Why do you need to add punctuations like this? \$\endgroup\$ – bhathiya-perera Mar 15 at 16:30
  • \$\begingroup\$ These are the punctuations used by USPTO and EPO. \$\endgroup\$ – Rahul Patel Mar 15 at 17:31
4
\$\begingroup\$

Here is a solution using a generator, which gives you linear time. Your current solution is not linear, because list.insert is already \$\mathcal{O}(n)\$.

def interweave(x, y):
    """
    Given an iterable `x` and an iterable `y` of indices and items, 
    yield from `x`, but interweave the items from `y` at the given indices.
    """
    y = iter(y)
    next_i, next_y = next(y, (-1, ""))
    for i, next_x in enumerate(x):
        if i == next_i:
            yield next_y
            next_i, next_y = next(y, (-1, ""))  # default value for when y is exhausted
        yield next_x

def punctuate(text, punctuations):
    return "".join(interweave(text, punctuations))

It passes all the given testcases:

In [98]: punctuate('US 8012999 B2', [(4, ','), (7, ',')])
Out[98]: 'US 8,012,999 B2'

In [99]: punctuate('US 20170107206 A1', [(7, '/')])
Out[99]: 'US 2017/0107206 A1'

In [100]: punctuate('US 09700674', [(5, '/'), (8, ',')])
Out[100]: 'US 09/700,674'

In [101]: punctuate('EP 2795605 B1', [(4, ' '), (7, ' ')])
Out[101]: 'EP 2 795 605 B1'
\$\endgroup\$
  • \$\begingroup\$ Thanks. It took time for me to fully understand it. This is amazing and also fast. Thanks. \$\endgroup\$ – Rahul Patel Mar 16 at 3:56
0
\$\begingroup\$

Knowing the context of a task is needed to determine whether this is the best way. At least, you would do refactoring of the existing solution.

def punctuate(text, punctuations):
    if not punctuations:
        return text
    i, char = punctuations.pop()
    return punctuate(text[:i], punctuations) + char + text[i:]

Less code and better performance.

\$\endgroup\$
  • \$\begingroup\$ I actually can't easily guess what's going on while looking at recursive solution. I have to see it on pythontutor. This is excellent. \$\endgroup\$ – Rahul Patel Mar 15 at 15:15
  • 4
    \$\begingroup\$ Welcome to CR numrut. Could you please specify why the recursive solution is better? I don't think mutating punctuations and recusing for this is a good idea. \$\endgroup\$ – bhathiya-perera Mar 15 at 15:25

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.