Ttykuu

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?