4
\$\begingroup\$

Write a Program that determines where to add periods to a decimal string so that the resulting string is a valid IP address. There may be more than one valid IP address corresponding to a string, in which case you should print all possibilities. For example, if the mangled string is "19216811" then some of the corresponding IP addresses are 192.168.1.1 and 19.216.81.1

Elements of Programming Interviews Section 6.9 See Bottom of Page 82, asks the following as a variant to the above problem:

Now suppose we need to solve the analogous problem when the number of periods is a parameter k and the string length s is unbounded.

See attempt below, I am generating all permutations, see permute(s), of the string and then filtering later hence I end up doing unnecessary work. Can I do better?

def period_partition(s, k):
    slen = len(s)

    def is_valid_octet(s):
        # section ranges 0 - 255 and `00` or `000`, `01` are not valid but 0 is
        return slen == 1 or (s[0] != "0" and 0 <= int(s) <= 255)

    def permute(s):
        if len(s) > 0:
            for i in range(1, slen + 1):
                first, rest = s[:i], s[i:]
                for p in permute(rest):
                    yield [first] + p
        else:
            yield []

    results = set()

    for s in filter(
        lambda x: len(x) == k + 1 and all(is_valid_octet(i) for i in x), permute(s),
    ):
        results.add(".".join(s))

    return list(results)


if __name__ == "__main__":
    for args in [
        ("", 1),
        ("1234", 2),
        ("19216811", 3),
        ("192168111234", 3),
        ("192168111234", 4),
    ]:
        print(period_partition(*args))
        print()

Output:

[]

['1.23.4', '12.3.4', '1.2.34']

['1.92.168.11', '192.16.81.1', '19.216.81.1', '192.1.68.11', '192.16.8.11', '19.216.8.11', '19.2.168.11', '19.21.68.11', '192.168.1.1']

['192.168.111.234']

['192.16.81.11.234', '19.21.68.111.234', '19.2.168.111.234', '192.168.1.112.34', '192.168.11.12.34', '192.168.11.1.234', '192.168.111.23.4', '192.168.1.11.234', '192.1.68.111.234', '192.168.111.2.34', '19.216.81.112.34', '192.16.81.112.34', '19.216.81.11.234', '192.168.11.123.4', '192.16.8.111.234', '19.216.8.111.234', '1.92.168.111.234']

NB: This is just a toy problem and its connection to valid IP addresses, IPv4 and IPv6, I think, is just to provide constraints on valid octets as periods are assigned. So 1.23.4 is an unbounded string s, "1234", after being partitioned with periods k=2

\$\endgroup\$
6
  • \$\begingroup\$ An IPv4 address is a 32 bit number, "1.23.4" is a 24bit number and "192.16.81.11.234" is a 40 bit number. It's not IPv6 because your output is neither a 128 bit number or using colons. ① Please can you provide the source for this problem. ② Does the code work the way the problem specifies? \$\endgroup\$
    – Peilonrayz
    May 19, 2020 at 17:51
  • \$\begingroup\$ This is just a toy problem and its connection to valid IP addresses, IPv4 and IPv6, is just to provide constraints on valid octets as periods are assigned. Please see update to the question. So 1.23.4 is an unbounded string s, 1234, after being partitioned with periods k=2 \$\endgroup\$
    – Brayoni
    May 19, 2020 at 18:08
  • 1
    \$\begingroup\$ Ok, that makes sense. Please could you edit your question to add that. \$\endgroup\$
    – Peilonrayz
    May 19, 2020 at 18:16
  • 5
    \$\begingroup\$ As an aside I'm not sold on the validity of the book you're reading. I would take care to not trust the book too much. The following sentence is misleading at best and wrong at worst. "The total number of IP addresses is a constant (\$2^{32}\$), implying an \$O(1)\$ time complexity for the above algorithm." \$\endgroup\$
    – Peilonrayz
    May 19, 2020 at 18:27
  • 1
    \$\begingroup\$ I copy pasted your code and got a RecursionError. I'm pretty sure your slen = len(s) at the beginning is a bug, since you use slen where you probably want the length of a string other than the outer s. \$\endgroup\$
    – Alex Hall
    May 19, 2020 at 20:12

1 Answer 1

2
\$\begingroup\$

Use a generative approach

Iterating over all possible permutations and filtering out the invalid ones results in lots of wasted work. Move the filtering operation earlier so many invalid permutations are not generated in the first place.

For example, permute() contains for i in range(1, slen + 1), but we know that an octet can only be up to 3 digits long. Change the loop to for i in range(1, min(4, len(s)+1)). Also, if first is not a valid octet skip the recursive call (none will result in a valid address).

Something like this:

def period_partition(s, k):

    def is_valid_octet(s):
        # section ranges 0 - 255 and `00` or `000`, `01` are not valid but 0 is
        return s == '0' or not s.startswith('0') and 0 < int(s) < 256

    if s and k:
        for i in range(1, min(4, len(s)+1)):
            first, rest = s[:i], s[i:]
            if is_valid_octet(first):
                yield from (f"{first}.{p}" for p in period_partition(rest, k-1))

    elif s and is_valid_octet(s):
        yield s


testcases = [
    ("", 1),
    ("1234", 2),
    ("19216811", 3),
    ("192168111234", 3),
    ("192168111234", 4),
    ("19216811123444", 4),
    ("192168111234444", 4),
]

for s, k in testcases:
    print(f"\nperiod_partition({s!r}, {k})")

    for partition in period_partition(s, k):
        print(f"  {partition}")

Note: I modified period_partition() to be a generator yields all valid partitions. Use list() if you need an actual list.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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