Python String Overflow?

Question

For some reason, the below results in an output of 0. I'm using a very large string (100,000 characters), and looking for a large integer, in the hundred billions, e.g 500,000,000,000. Is there something special I need to do? The goal is to find the number of sub-sequences of 1,2,3 in the first 100,000 digits of pi. I know the below is algorithmically correct. It's just not "code-correct."

pi100k = "3.14159[100,000 digits of pi]"
subSeqInit = 0
subSeqPair = 0
subSeqTotal = 0

for c in pi100k:
    if c == 1:
        subSeqInit = subSeqInit + 1
    elif c == 2 and subSeqInit > 0:
        subSeqPair = subSeqPair + 1
    elif c == 3 and subSeqTotal > 0:
        subSeqTotal = subSeqTotal + 1

print(subSeqTotal)

Maybe you should recheck your algorithm. I don't see how subSeqTotal can possibly change from its initial 0. — Ralph
– Ralph, Commented Jun 1, 2011 at 1:46

MRAB · Accepted Answer · 2011-06-01 02:02:32Z

4

The simplest and fastest way is probably this:

subSeqTotal = pi100k.count("123")

answered Jun 1, 2011 at 2:02

MRAB

20.7k6 gold badges44 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

GWW Over a year ago

LOL I wish I thought to use count sometimes I make things way too complicated.

GWW · Accepted Answer · 2011-06-02 01:11:25Z

3

pi100k = "3.14159[100,000 digits of pi]"
subSeqInit = 0
subSeqTotal = 0

for c in pi100k:
    if c == '1':
        subSeqInit = 1
    elif c == '2' and subSeqInit == 1:
        subSeqInit = 2
    elif c == '3' and subSeqTotal == 2:
        subSeqTotal = subSeqTotal + 1
        subSeqInit = 0

print(subSeqTotal)

Python does not implicitly convert string characters to integers. Furthermore, your algorithm is not sound, what I have above will work better.

EDIT:

You could make this much shorter by using the regular expression module

import re
subSeqTotal = len(re.findall('123',pi100k))\

EDIT 2: As MRAB pointed out the best thing to use is pi100k.count('123')

edited Jun 2, 2011 at 1:11

answered Jun 1, 2011 at 1:40

GWW

44.3k11 gold badges119 silver badges110 bronze badges

4 Comments

tzot Over a year ago

No need for re when str.count exists :)

GWW Over a year ago

I saw that in the other person's answer. I didn't want to copy his :P. I can't believe I forgot about str.count

tzot Over a year ago

Make your answer even more complete by including the str.count option and crediting MRAB for it. (People take the rep system far more seriously than they should. Reputation is a tool, not an end.)

GWW Over a year ago

@ΤΖΩΤΖΙΟΥ: I added it, I just don't want to get any angry :P

user427390 · Accepted Answer · 2011-12-28 03:06:57Z

It appears none of these solutions are correct. I don't think they search for the sub-sequence correctly.

I solved it recursively in C, with this algorithm:

/* global cstring for our pi data */
const char *g_numbers = 3.14........[100,000 digits];

/* global to hold our large total : some compilers don't support uint64_t */
uint64_t  g_total = 0;


/* recursively compute the subsequnces of 1-2-3 */
void count_sequences(const char c, unsigned int index)
{
    while (index < 100000){
        switch (g_numbers[index]){
            case '1': if (c == '1') count_sequences('2', index+1); break;
            case '2': if (c == '2') count_sequences('3', index+1); break;
            case '3': 
                      if (c == '3'){
                        g_total++;
                        count_sequences('3', index+1);
                        return;
                      }
            default: break;
        }
        index++;
    }
}

Sorry I can't hand out the Python solution-- but I hope this helps. It shouldn't be too hard to re-work. I tried the given answers in Python and they didn't seem to work.

Collectives™ on Stack Overflow

Python String Overflow?

3 Answers 3

1 Comment

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related