Python Code Fails

Question

The following code fails. throwing an exception and producing no output.

The constraints on the input are 1<=n<=1000, 1<=k<=n and s.length is equal to n. It is also guaranteed that the input is exactly as specified.

Also, the code works, when 1<=n<=20.

def conforms(k,s):
    k = k + 1
    if s.find("0" * k) == -1 and s.find("1" * k) == -1:
        return True
    else:
        return False


def brute(n,k,s):
    min_val = n + 1
    min_str = ""
    desired = long(s,2)
    for i in range (2 ** n):
        xor = desired ^ i # gives number of bit changes
        i_rep = bin(i)[2:].zfill(n) # pad the binary representation with 0s - for conforms()
        one_count = bin(xor).count('1')
        if one_count < min_val and conforms(k, i_rep):
            min_val = bin(xor).count('1')
            min_str = i_rep

    return (min_val,min_str)

T = input()
for i in range(T):
    words = raw_input().split() 
    start = raw_input()
    sol = brute( int(words[0]), int(words[1]), start)
    print sol[0]
    print sol[1]

`The following code fails and returns with an NZEC.` This is not SPOJ. Please explain what NZEC is. — thefourtheye, May 11 '15 at 17:06
Are you expecting the first line of `conforms` to modify the value of `k` in `brute`? It won't. — Daniel Roseman, May 11 '15 at 17:11
@EliKorvigo I guess OP can not do that, because he submits the code to an online judge system which runs it against set of inputs — Konstantin, May 11 '15 at 17:13
Specify the probable input for `T`, `words`, `start`. It feels like you might pass a string of characters to the `int` function. And what is the reason to use the `input` function? Recall `input` = `eval(raw_input)` — Eli Korvigo, May 11 '15 at 17:14
You want to run `i` all the way up to `2**1000`, but it fails around `2**20`? I can't say I'm too surprised, since a string of length `2**20` already has over a million digits; but how about you include the traceback so we can see exactly what goes wrong. — alexis, May 11 '15 at 17:29
@xrisk, it does, but if you try to execute `In [1]: range(2**(10**3))` you will get `OverflowError: range() result has too many items` and this seems to be the root of the problem — Konstantin, May 11 '15 at 17:31
@Alik never mind, I got what I wanted - why the code was failing. It was because of some language construct and not my algo itself. And this was the bruteforce solution anyway. I suggest you make it an answer. — xrisk, May 11 '15 at 17:35
@xrisk replace it with `while` loop. I think it will fail due to time limit though. — Konstantin, May 11 '15 at 17:38
@Alik Of course it will. 2**1000 ~ 10e301 And the time limit is 1 second. Thanks anyways. — xrisk, May 11 '15 at 17:40

Eli Korvigo · Accepted Answer · 2015-05-11T17:52:42.653

1

The thing is that range and xrange are written in C, hence they are prone to overflows. You need to write your own number generator to surpass the limit of C long.

def my_range(end):
    start = 0
    while start < end:
        yield start
        start +=1 


def conforms(k,s):
    k = k + 1
    if s.find("0" * k) == -1 and s.find("1" * k) == -1:
        return True
    else:
        return False


def brute(n,k,s):
    min_val = n + 1
    min_str = ""
    desired = long(s,2)
    for i in my_range(2 ** n):
        xor = desired ^ i # gives number of bit changes
        i_rep = bin(i)[2:].zfill(n) # pad the binary representation with 0s - for conforms()
        one_count = bin(xor).count('1')
        if one_count < min_val and conforms(k, i_rep):
            min_val = bin(xor).count('1')
            min_str = i_rep
    return (min_val,min_str)


T = 1
for i in range(T):
    words = [100, 1]
    start = '00000001'
    sol = brute(words[0], words[1], start)
    print sol[0]
    print sol[1]

edited May 11 '15 at 17:52

answered May 11 '15 at 17:27

Eli Korvigo

10,265
6
47
73

Huh, what did you do there? Where's the input? – xrisk May 11 '15 at 17:29
@xrisk I took one extreme case. – Eli Korvigo May 11 '15 at 17:46
What? How long did that take to run? 2*100 is impossible to run in a reasonable amount of time. Its ~10e300 cycles. A normal computer does 10e9 operations in 1 second. – xrisk May 11 '15 at 17:52
@xrisk indeed, but this has little to do with the language itself. In fact the error you had is a reminder of the C-ish guts of Python. – Eli Korvigo May 11 '15 at 17:54
Okay, cool. I guess that your solution will work. (eventually) – xrisk May 11 '15 at 17:56
@xrisk btw, never use `range` if you only need to use a number once, because `range` creates a full-blown list in memory before your `for` loop even starts. – Eli Korvigo May 11 '15 at 17:58
2

@xrisk `range` builds a list in memory, so Python throws exceptions if you pass big numbers to `range` in order to prevent memory overflows. Correct way to deal with this is to use `islice`. See [this](http://stackoverflow.com/a/15725522/471899) answer for more details – Konstantin May 11 '15 at 17:58
@EliKorvigo, memory is of no concern - speed is. – xrisk May 11 '15 at 17:59
@xrisk creating a huge list in memory takes more time than returning numbers one by one. – Eli Korvigo May 11 '15 at 17:59
Okay, thanks everybody - now to figure out the real solution. – xrisk May 11 '15 at 18:00
The correct way to deal with very large ranges is to use `xrange()` in python 2, or switch to python 3 (where `range()` is actually python 2's `xrange()`). `xrange()` gives you an iterator that only generates numbers as you need them. – alexis May 11 '15 at 22:49
@alexis `xrange` implementation uses a C long to store current value, hence it will overflow as well. Python 3 `range` will do, because it's based on Python (limitless) ints. – Eli Korvigo May 11 '15 at 23:00

Python Code Fails

1 Answers1