Geek asks and answers

Recursive function dies with memory error

Let's say that we have a function that translates morse characters:

  • . → -.
  • - → ...-

If we apply this function twice, we get, for example:

.→ -.→...--.

Given the input string and the number of repetitions, you need to know the length of the final string. (Problem 1 of the Flemish VPW programming contest , taken from these slides that provide a solution in Haskell).

For a given input file

4
. 4
.- 2
-- 2 
--... 50

We are awaiting a decision

44
16
20
34028664377246354505728

Since I don't know Haskell, this is my recursive solution in Python that I came up with:

def encode(msg, repetition, morse={'.': '-.', '-': '...-'}):
    if isinstance(repetition, str):
        repetition = eval(repetition)
    while repetition > 0:
        newmsg = ''.join(morse[c] for c in msg)
        return encode(newmsg, repetition-1)
    return len(msg)


def problem1(fn):
    with open(fn) as f:
        f.next()
        for line in f:
            print encode(*line.split())

which works for the first three inputs, but dies with a memory error for the last input.

How would you rewrite this in a more efficient way?

Edit

Rewrite based on the comments:

def encode(p, s, repetition):
    while repetition > 0:
        p,s = p + 3*s, p + s
        return encode(p, s, repetition-1)
    return p + s


def problem1(fn):
    with open(fn) as f:
        f.next()
        for line in f:
            msg, repetition = line.split()
            print encode(msg.count('.'), msg.count('-'), int(repetition))

-

+5
4

, , . , '.' '-' (, ".- 3" "-. 3" ).

, '.' "-" .

+7

. :

repetitions = 4
dots = 1
dashes = 0
for i in range(repetitions):
    dots, dashes = dots + 3 * dashes, dashes + dots

, .

+2

Per @Hammar (I had the same idea, but he explained it better than he could :-):

from sympy import Matrix

t = Matrix([[1,3],[1,1]])

def encode(dots, dashes, reps):
    res = matrix([dashes, dots]) * t**reps
    return res[0,0] + res[0,1]
+2
source

you put the number of dots in the dash and the number of dashes to the points in each iteration ...

def encode(dots, dashes, repetitions):
    while repetitions > 0:
        dots, dashes = dots + 3 * dashes, dots + dashes
        repetitions -= 1

    return dots + dashes

def problem1(fn):
    with open(fn) as f:
        count = int(next(f))
        for i in xrange(count):
            line = next(f)
            msg, repetition = line.strip().split()
            print encode(msg.count('.'), msg.count('-'), int(repetition))
+1
source

More articles:


All Articles