Programming Challenge from Kattis: Distinctive Characters

Question

I'm currently working on this problem from Kattis. In short, we're supposed to find the string that has the least similarity to any other string given. Every element of a string is either 0 or 1. Similarity between two strings is measured by increasing the similarity by 1 if both strings have the same character in the same position. E.g: "01001" "11110" has similarity 1, because they both have 1 in their 2nd position, and for every other position they have different characters. An input starts with one line giving two numbers N and P, being first the number of strings in the list, and then the length of each string. The rest of the input is then N lines of single strings. The output should be a string that has the least possible similarity to any string in the input.

I'd like suggestions on how to reduce the number of calls I'm doing in my solution to this problem. Likely by some algorithmic magic.

Example input:

3 5
01001
11100
10111

Example output:

00010

My code:

import sys
import itertools


def similarity(sx, sy):
    '''Naively calculates similarity between two
    strings.'''
    result = 0
    for i in range(n_feat):
        if sx[i] == sy[i]:
            result += 1
    return result


line_1 = sys.stdin.readline()
line_1 = line_1.split()
N = int(line_1[0])
n_feat = int(line_1[1])

characters = set()
for i in range(N):
    characters.add(str(sys.stdin.readline()))


# Generate all possible ways to write n_feat long string with alphabet {0,1}
all_pos_chars = ["".join(seq) for seq in itertools.product("01", repeat=n_feat)]
# Subset actually possible (removed ones have similarity == n_feat)
pos_chars = [pos_char for pos_char in all_pos_chars if pos_char not in characters]

# Impossibly high starting-point.
curr_min = n_feat+1
curr_small = ""
for pos_char in pos_chars:
    curr = max(similarity(pos_char, character) for character in characters)
    if curr == 0:
        curr_small = pos_char
        break;
    if curr <= curr_min:
        curr_min = curr
        curr_small = pos_char

print(curr_small)

This solution works fine for smaller inputs. For example, I ran python -m cProfile -s cumtime dischar.py < 1.in where 1.in is the example input given above and received this:

         300 function calls in 0.001 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.001    0.001 {built-in method builtins.exec}
        1    0.000    0.000    0.001    0.001 dischar2.py:1(<module>)
        1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
       31    0.000    0.000    0.000    0.000 {built-in method builtins.max}
      124    0.000    0.000    0.000    0.000 dischar2.py:34(<genexpr>)
       93    0.000    0.000    0.000    0.000 dischar2.py:5(similarity)
        4    0.000    0.000    0.000    0.000 {method 'readline' of '_io.TextIOWrapper' objects}
        1    0.000    0.000    0.000    0.000 dischar2.py:26(<listcomp>)
        2    0.000    0.000    0.000    0.000 cp1252.py:22(decode)
       32    0.000    0.000    0.000    0.000 {method 'join' of 'str' objects}
        1    0.000    0.000    0.000    0.000 dischar2.py:28(<listcomp>)
        2    0.000    0.000    0.000    0.000 {built-in method _codecs.charmap_decode}
        2    0.000    0.000    0.000    0.000 codecs.py:281(getstate)
        1    0.000    0.000    0.000    0.000 {method 'split' of 'str' objects}
        3    0.000    0.000    0.000    0.000 {method 'add' of 'set' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

But I was worried about the number of calls at line:34, which is this bit of code: curr = max(similarity(pos_char, character) for character in characters), and then onwards to line:5 which is the similartiy-function. I made a 6.in, where the first line is 10000 20, and the next 10000 lines are 20 zeros:

python -m cProfile -s cumtime dischar2.py < 6.in
11111111111111111111
         7360118 function calls in 9.280 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    9.280    9.280 {built-in method builtins.exec}
        1    0.756    0.756    9.280    9.280 dischar2.py:1(<module>)
  1048575    0.663    0.000    7.700    0.000 {built-in method builtins.max}
  3145725    0.777    0.000    7.037    0.000 dischar2.py:34(<genexpr>)
  2097150    6.260    0.000    6.260    0.000 dischar2.py:5(similarity)
        1    0.325    0.325    0.656    0.656 dischar2.py:26(<listcomp>)
  1048576    0.332    0.000    0.332    0.000 {method 'join' of 'str' objects}
        1    0.161    0.161    0.161    0.161 dischar2.py:28(<listcomp>)
    10001    0.004    0.000    0.005    0.000 {method 'readline' of '_io.TextIOWrapper' objects}
    10000    0.001    0.000    0.001    0.000 {method 'add' of 'set' objects}
       28    0.000    0.000    0.001    0.000 cp1252.py:22(decode)
       28    0.001    0.000    0.001    0.000 {built-in method _codecs.charmap_decode}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.print}
       28    0.000    0.000    0.000    0.000 codecs.py:281(getstate)
        1    0.000    0.000    0.000    0.000 {method 'split' of 'str' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

As you can see, this adds up quickly! I think my solution is sound, it provides the correct output for every case I can test for. But there has to be some trick that I'm not seeing, because Kattis expects the solution to run within 2 CPU-seconds. Any suggestions?

Answer 1

Line 34 is a wrong tree to bark on. The problem is in

    all_pos_chars = ["".join(seq) for seq in itertools.product("01", repeat=n_feat)]

which results in a list of \$2^{n\_feat}\$ characters. You have an exponential complexity right away.

An opportunistic optimization (removal of impossible characters) doesn't buy you anything; at the end of the day you still comparing each - possible or impossible - character against each input character. Notice that in a 5 feature case there are \$31 = 2^5 - 1\$ calls to max, and in a 20 feature case there are \$1048575 = 2^{20} - 1\$ of them.

Now, to get the problem right, you need to realize first that the features are independent. And second that a contribution of a particular feature only depends on how many characters have it. Hint: how would you solve the problem for just one feature?. I hope the hint is strong enough to reveal a linear time solution.

---

An obligatory code review note. Using an Impossibly high starting-point is often wrong, and may not even exist. A natural starting point is safely derived from the first element:

    curr = similarity(pos_char, character[0])

followed by iterating over character[1:]. Now the if curr == 0: special case disappear.