How to work with very long strings in Python?

Question

I'm tackling project euler's problem 220 (looked easy, in comparison to some of the others - thought I'd try a higher numbered one for a change!)

So far I have:

D = "Fa"

def iterate(D,num):
    for i in range (0,num):
     D = D.replace("a","A")
     D = D.replace("b","B")
     D = D.replace("A","aRbFR")
     D = D.replace("B","LFaLb")
    return D

instructions = iterate("Fa",50)

print instructions

Now, this works fine for low values, but when you put it to repeat higher then you just get a "Memory error". Can anyone suggest a way to overcome this? I really want a string/file that contains instructions for the next step.

Answer 1

If you think about how many "a" and "b" characters there are in D(0), D(1), etc, you'll see that the string gets very long very quickly. Calculate how many characters there are in D(50), and then maybe think again about where you would store that much data. I make it 4.5*10^15 characters, which is 4500 TB at one byte per char.

Come to think of it, you don't have to calculate - the problem tells you there are 10^12 steps at least, which is a terabyte of data at one byte per character, or quarter of that if you use tricks to get down to 2 bits per character. I think this would cause problems with the one-minute time limit on any kind of storage medium I have access to :-)

Answer 2

Since you can't materialize the string, you must generate it. If you yield the individual characters instead of returning the whole string, you might get it to work.

def repl220( string ):
    for c in string:
        if c == 'a': yield "aRbFR"
        elif c == 'b': yield "LFaLb"
        else yield c

Something like that will do replacement without creating a new string.

Now, of course, you need to call it recursively, and to the appropriate depth. So, each yield isn't just a yield, it's something a bit more complex.

Trying not to solve this for you, so I'll leave it at that.

Answer 3

The trick is in noticing which patterns emerge as you run the string through each iteration. Try evaluating iterate(D,n) for n between 1 and 10 and see if you can spot them. Also feed the string through a function that calculates the end position and the number of steps, and look for patterns there too.

You can then use this knowledge to simplify the algorithm to something that doesn't use these strings at all.

Answer 4

You could treat D as a byte stream file.

Something like:-

seedfile = open('D1.txt', 'w'); seedfile.write("Fa"); seedfile.close(); n = 0 while (n

warning totally untested

Answer 5

Python strings are not going to be the answer to this one. Strings are stored as immutable arrays, so each one of those replacements creates an entirely new string in memory. Not to mention, the set of instructions after 10^12 steps will be at least 1TB in size if you store them as characters (and that's with some minor compressions).

Ideally, there should be a way to mathematically (hint, there is) generate the answer on the fly, so that you never need to store the sequence.

Just use the string as a guide to determine a method which creates your path.