1
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ You are supposed to use bit operators \$\endgroup\$ – E.Coms Apr 6 at 12:03
  • \$\begingroup\$ Yes, I should. Thank you. But I believe using bit-operators would not help with the O(n^2)-nature of searching through every possible combination to find the string with the lowest maximum similarity. It would just make the n^2 operations a bit faster, or am I wrong? There's something conceptually wrong with what I'm doing, in terms of performance, I'm sure of it. The answer from @vnp is suggesting so also, but I haven't been able to decrypt the hint yet. But maybe this is more of a stackoverflow-question. \$\endgroup\$ – RoyM Apr 6 at 19:24
  • \$\begingroup\$ @E.Coms I think I might be getting it now. Thanks for your suggestion! \$\endgroup\$ – RoyM Apr 6 at 19:43
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Never mind, I have to rethink this a bit more. I judged too quickly. \$\endgroup\$ – RoyM Apr 6 at 6:35
  • \$\begingroup\$ Solving for one feature: If both 0 and 1 appear in the input-list, then 0 and 1 as output are equally valid. If only 1s appear in the list, then 0 has the smallest max-similarity, and vice versa for 0s. Maybe I could always select the one with the least appearances among the two – and just print either if they are equal? This is how I approached the problem in the beginning. I'm getting a "wrong answer" at test no.10, but I can't think of an example myself where it would be wrong. But the wrong answer convinced me that method must be wrong. \$\endgroup\$ – RoyM Apr 6 at 7:00
  • \$\begingroup\$ Come to think of it, an example where that would fail is where the list has these characters already: 00 and 11. By the reasoning in my last comment my program would print either 00 or 11 depending on what I decided to print where the number of 1s and 0s for a feature were equal. But that is the worst possible answer, because both have max similarity 2, whereas max similarity 1 is possible both for 01 and 10. Could you bump me a bit further? \$\endgroup\$ – RoyM Apr 6 at 7:04

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.