CODEWITHSUNDEEP
pythonloopsrecursion
Jeremy Thomas
Jeremy Thomas

Reputation: 6684

Recursion results in unwanted looping

I am having some difficulty using recursion. Below, I have a block of code that is attempting to solve a puzzle. process() generates permutations, then solve() runs through those permutations and checks each one. If a solution fails at a certain position, the function then removes all possible solutions that begin the same way, and re-runs itself recursively. The test_it() function is called in solve() as a means of determining when a solution is incorrect.

This gives the correct result in the end, but when I added the print line: 

print 'Fail', combo, count

I noticed it the function seems to recognize the correct solution, but then continues iterating anyway. I think I may be messing something up with the nested loops because once it reaches the line:

return combo

it doesn't terminate.

import itertools

final_side = [{(1,2): [[1,0,1,1]]},\
              {(2,1): [[1,1,0,1]]},\
              {1: [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]},\
              {1: [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]}]

final_top = [{2: [[1,1,0,0],[0,1,1,0],[0,0,1,1]]},\
              {(1,1): [[1,0,1,0],[1,0,0,1],[0,1,0,1]]},\
              {(1,1): [[1,0,1,0],[1,0,0,1],[0,1,0,1]]},\
              {2: [[1,1,0,0],[0,1,1,0],[0,0,1,1]]}]

def process():
    # Generates all permutations
    possible = []
    possibilities = []
    a = []

    for dic in final_side:
        for values in dic.values():
            possible.append(len(values))            

    for number in possible:
        a.append([x for x in range(number)])

    b = map(list, itertools.product(*a))

    return b

def test_it(listx, final_top, final_side):

    length = len(listx)
    place = []    

    if length > 0:
        pot = map(list, zip(*listx))
        for j in range(len(pot)):
            x = final_top[j].values()[0]
            test = [x[i][:length] for i in range(len(x))]

            if pot[j] not in test:
                return False

            else:
                loc = [x for x,val in enumerate(test) if val== pot[j]]
                place.append(loc)
    return place


def solve(listx):

    solution = []     

    for combo in listx[:]:
        pos = -1
        temp = []
        count = 0
        for num in combo:
            pos += 1
            temp.append(final_side[pos].values()[0][num])
            place = test_it(temp, final_top, final_side)    

            if place == False:
                blah = combo[:pos+1]
                listx = [x for x in listx if not x[:pos+1] == combo[:pos+1]]
                print 'Fail', combo, count                 
                solve(listx)

            else:
                count += 1
                if count == 4:
                    return combo

def main():


    a = process()
    solution = solve(a)

    print solution

main()

Upvotes: 0

Views: 48

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1123400

You are ignoring the return value of recursive calls:

if place == False:
    blah = combo[:pos+1]
    listx = [x for x in listx if not x[:pos+1] == combo[:pos+1]]
    print 'Fail', combo, count                 
    solve(listx)

The return value of the solve() call there is dropped; it won't be passed to the next caller, nor are you ending the loop there.

Add a return to exit that level of your recursive calls:

if not place:
    blah = combo[:pos+1]
    listx = [x for x in listx if not x[:pos+1] == combo[:pos+1]]
    print 'Fail', combo, count                 
    return solve(listx)

I also replaced place == False with not place, a much better way to test for boolean false.

With these changes your script outputs:

$ bin/python test.py 
Fail [0, 0, 0, 0] 2
Fail [0, 0, 1, 0] 2
Fail [0, 0, 2, 0] 3
[0, 0, 2, 1]

Upvotes: 2

Related Questions