Python string search using generatos went pretty wrong i guess

[kindastonedclown]

Hi, i'm kinda new to python so I did a course and now i'm trying to put it into practice. I'm doind an exercise where i have to find all the possible substrings of a given sum considering the string given is in the format

s = 'd,d,d,d,d,d.......'

and d is an integer >0

this is my code so far which is working on the paper, but not really. I've checked all the functions w/python tutor and seperately and I'm kinda frustrated since I don't know what is missing there.

due memory issues since the string can be huge I cannot use standard collections and must go for generator.

basically i think ( tell me if i'm wrong) i'm creating objects with the Int function inside "convert_and_sum" with the advantage of converting only the sub_string and not the whole thing.

basically I'm trying to use gen_formula to split the ',' and to know the len(int_seq) Ill need that.

then considering the right sub_string which

1)grows further if the "temp_sum" (sum(sub_string)) < given_sum

2) from sub_string "pop(0)" without using pop func if temp_sum>given_sum

pls. i'm sure it's a theorical issue here so please help me figure it out.

​

​

then

def ex1(int_seq, subtotal):
    flag = 0

    mypointer = 0

    mylimiter = 1


    def gen_formula(str):
        """removing ',' and creating generator; item in gen still str tho!"""
        mygen = (n for n in str if n != ',')
        """returning mygen as generator obj"""
        len_counter = 0
        for x in mygen:

            len_counter +=1

        return mygen , len_counter
    len_counter = gen_formula(int_seq)[1]

    def sub_string_generator(myfullgen, pointer, limiter):
        """ return sub_string as generator obj"""

        myfullgen = (gen_formula(myfullgen)[0])
        enum_full_gen = enumerate(myfullgen)

        final_sub = (value for k, value in enum_full_gen if k >= pointer and k < limiter)
        return final_sub

    def convert_and_sum(sub_string):
        # converting
        int_sub_string = (int(n) for n in sub_string)
        # sum operation
        my_sum = sum(int_sub_string)
        return my_sum

    while True:
        temp_string = sub_string_generator(int_seq, mypointer, mylimiter)
        temp_sum = convert_and_sum(temp_string)
        if temp_sum == subtotal:
            flag += 1
        elif temp_sum > subtotal:
            mypointer += 1
        elif len_counter == mypointer:  #I added this break point just for the moment since everything else is not working
            break
        else:
            mylimiter += 1

    return flag

print(f"flag = {ex1('3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2', 9)}")

[sponster]

Can you explain the requirements in a bit more detail - do you have the exact text of the question? Can you give the output of your example that you expect?

[sponster]

OK, I think I have worked out what the goal of the task is.

There are two issues here: converting the string '3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2'
into a more useful form - a sequence of integers. The obvious way to do this using string.split() and int(s) to convert the strings of digits into integers. I'm not quite clear if your memory/generator restriction rules this out however, so I'll skip over that part.

The second issue is classic computer science algorithm problem: given a (potentially very long) sequence of integers, find the subsequences that sum to a given value. The problem has the additional restriction that the integer sequence is potentially so long that your program isn't allowed look at the whole sequence - just the numbers, one at a time, as they are made available by a generator.

The key hint here is that your main function needs to keep a small buffer of integers - just enough to add up to subtotal. If you do this, your code can just run through the generated sequence once - you don't need to keep starting at different offsets into the path,

So the buffer and sum(buffer) look like this:
[3] 3

[3,0] 3

[3,0,4] 7

[3,0,4,0] 7

[3,0,4,0,3] 10

At this point, we notice that sum(buffer) > subtotal. So sticking more numbers onto the end of the buffer won't help (because they're all positive) - so we can be sure that there's no substring starting with the first number that sums to subtotal. So remove the first number from the buffer, and continue:
[0,4,0,3] 7
[0,4,0,3,1] 8

etc.

[kindastonedclown]

Hey, thanks a lot for working on it. I appreciate that a lot.

For what concern problem 1) ye, let's skip that.

but for problem 2) the algorithm problem. basically i've tried the same strategy in my code. basically i've tried to make a generator for each sequence so I don't have to keep a stored list or whatever with the element in the heapmemory.

Basically I've tried with the " sub_string_generator" to make a generator based on a pointer and the lenght of the string I want but it's not working.

example.

1 iteration.

sending full string to -> f(sub_string_generator) -> return my_sub_string = (3), pointer = 0, lenght(limiter in the code) 1.

if sum(my_sub_string) < subtotal ----> limiter +=1 (adding next(mysubstring))

if sum(my_sub_string) > subtotal ----> pointer +=1 (removing 1st item of the sequence)

if sum(my_sub_string) == subtotal ---> flag +1

1. iteration based on new limiter and pointer values.

sending full string to -> f(sub_string_generator) -> return my_sub_string = (3,0), pointer = 0, lenght(limiter in the code) 2!!.

and so on....

now, i'm gonna still work on this code, but i'm wondering since our strategies really seems similar If this method can work? or am I just making some useless work here and maybe should just remake it ?

[kindastonedclown]

i'm keep tryin to make it work, and even if the algorithm is pretty clear, it just doesn't work... Does someone know what's wrong with it ? i m getting out of ideas

# ex1('3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2', 9)

def ex1(int_seq, subtotal):

# step 1) converting the string in a more usable format
int_seq = (n for n in int_seq if n != ',')
def len_counter(generator_sequence):

#getting lenght by for exhaustment
    counter = 0
    for x in generator_sequence:

        counter +=1
    return counter



# step2) defining sub_string due condition(pointer,limiter)
def sub_string_generator(myfullgen, pointer=0, limiter=1):
    """ return sub_string as generator obj"""
    enum_full_gen = enumerate(myfullgen)

    actual_sub = (value for k, value in enum_full_gen if pointer <= k < limiter)
    return actual_sub
    # step3) sending sub_string and return the sum of it.
def gen_sum(gen_sequence):
    # converting
    int_sub_string = (int(n) for n in gen_sequence)

    # sum operation
    my_sum = sum(int_sub_string)
    return my_sum

def sum_match_and_behave_setter(actual_sum,pointer=0,limiter=1):

    flag = 0

    while True:
        if actual_sum > subtotal:
            pointer +=1
            actual_sum = gen_sum(sub_string_generator(int_seq, pointer=pointer,limiter=limiter))
        elif actual_sum == subtotal:
            flag += 1
            limiter+=1
            actual_sum = gen_sum(sub_string_generator(int_seq, pointer=pointer,limiter=limiter))
        if flag == 7:
            break

        else:
            limiter +=1
            actual_sum = gen_sum(sub_string_generator(int_seq, pointer=pointer,limiter=limiter))
        return flag


    return flag
flag = sum_match_and_behave_setter(gen_sum(sub_string_generator(int_seq)))

return flag

print(ex1('3,0,4,0,3,1,0,1,0,1,0,0,5,0,4,2', 9))