CODEWITHSUNDEEP
pythonalgorithmrecursioncombinatoricsstate-machine
Anny Fernando
Anny Fernando

Reputation: 11

How to recursively calculate all paths to a terminal state in an iterated system with two state variables?

Compute the number of ways to reach the terminal state (A = 1) using recursion.

Consider an iterated system with two state variables A and B.

The variables are initialized to (A,B) = (0,2). At each iteration, one of the two state variables can transition to one adjacent allowed values, i.e. for A 0 --> 1, 1-->0. For B, a value of 2 can transition as 2-->1 or 2-->3.
A terminal state is reached for A=1.

How many different ways are there to reach the terminal state after maximum iterations? I am supposed to write a method that computes this number recursively!

Example (A initial position ,B initial position, Current Step, Maximum Step) = (0,2,0,1) = 1

Here's my try:

def recurse(A, B, step, max_step):
    if A == 1:
        return 1
    if step > max_step:
        return 0
    ways = 0
    if A == 0:
        ways += recurse(1, B, step + 1, max_step)
    if B > 0:
        ways += recurse(A, B - 1, step + 1, max_step)
    if B < 4:
        ways += recurse(A, B + 1, step + 1, max_step)
    return ways

But as can be seen in this table, it fails:

Input Expected Output Actual Output
(0,2,0,1) 1 1
(0,2,0,2) 2 3
(0,2,0,3) 4 7

Upvotes: 1

Views: 135

Answers (1)

lastchance
lastchance

Reputation: 6720

You have mis-stated the question (see https://studyx.ai/homework/101689439-considet-an-iterated-system-with-two-stale-variables-a-and-b-acan-have-a-values-of-o-or-1 ). It must reach the final state at EXACTLY max_step stages (or, at least, when step==max_step). Thus, in trincot's example it is the last of the three that should not be counted, because this used just one step and not two.

Thus, the only thing wrong with your code is that you record a "success" automatically if A=1 (the termination state), whereas you should check that this occurs with the requisite number of steps. In your code change the line

return 1

to

return 1 if step == max_step else 0

This will then give you the desired output.

You can generally simplify the logic of your code. For example, with the B operations you can immediately return 0 if B<0 or B>4. With a bit of generalisation to more available states:

def recurse(A, B, step, max_step):
    Amin, Amax, Bmin, Bmax = 0, 1, 0, 4
    Atarget = 1
    if A < Amin or A > Amax or B < Bmin or B > Bmax: return 0
    if A == Atarget                                : return 1 if step == max_step else 0
    if step >= max_step                            : return 0
    return recurse( A - 1, B, step + 1, max_step) + recurse( A + 1, B, step + 1, max_step ) + recurse( A, B - 1, step + 1, max_step ) + recurse(A, B + 1, step + 1, max_step)

print( recurse( 0, 2, 0, 1 ) )
print( recurse( 0, 2, 0, 2 ) )
print( recurse( 0, 2, 0, 3 ) )

Output:

1
2
4

Upvotes: 0

Related Questions