Maze algorithm python-CodePudding

Turn the four rings so that the sums of each four of the numbers that are located along the same radius are the same. Find what they are equal to? problem image

We can do it by Brute Force method but it will be dummy cause too many combinations. I had thoughts about DFS method but cant imagine how to consume it here truly. I dont need code for this problem, perhaps you can share your thoughts on this issue.

input data

1-st ring: 3 9 6 4 3 7 5 2 4 8 3 6
2-nd ring: 8 4 7 5 8 2 9 5 5 8 4 6
3-rd ring: 6 5 8 1 6 6 7 1 3 7 1 9
4-th ring: 9 2 4 6 8 4 3 8 5 2 3 7

CodePudding user response：

Not sure if this is what you mean by brute force, but I don't think you can avoid trying all combinations (which is exactly what a tree search does as well).

Note though that since only relative displacements matter, it is enough to search on displacements of 3 rings. You can do so using backtracking (which exactly corresponds to a tree search).

CodePudding user response：

Have done this problem without using any theoretical algorithm using python.

Just simple Brute Force method like walking through my rings starting from 2-nd one**

def find_radius(*args):
    arr = []
    for i in range(0, len(args[0])):
        sum_radius = args[0][i]   args[1][i]   args[2][i]   args[3][i]
        arr.append(sum_radius)

    return list(dict.fromkeys(arr))


def move_ring(arr):
    first_element = arr[0]
    arr.remove(first_element)
    arr.append(first_element)
    return arr


def print_all_rings(*args):
    print(args[0])
    print(args[1])
    print(args[2])
    print(args[3])


if __name__ == '__main__':
    # first example
    
    ring_1 = [3, 9, 6, 4, 3, 7, 5, 2, 4, 8, 3, 6]
    ring_2 = [8, 4, 7, 5, 8, 2, 9, 5, 5, 8, 4, 6]
    ring_3 = [6, 5, 8, 1, 6, 6, 7, 1, 3, 7, 1, 9]
    ring_4 = [9, 2, 4, 6, 8, 4, 3, 8, 5, 2, 3, 7]

    # second example
    
    # ring_1 = [4, 2]
    # ring_2 = [6, 8]
    # ring_3 = [9, 8]
    # ring_4 = [5, 8]

    first_round = 0
    second_round = 0

    while True:
        if first_round == len(ring_1):
            first_round = 0
            move_ring(ring_3)
            second_round  = 1

        if second_round == len(ring_1):
            second_round = 0
            move_ring(ring_4)

        if len(find_radius(ring_1, ring_2, ring_3, ring_4)) == 1:
            print("200 OK! All radius are the same")
            break
        else:
            print("404 Error!")

        move_ring(ring_2)
        first_round  = 1

    print(find_radius(ring_1, ring_2, ring_3, ring_4))
    print_all_rings(ring_1, ring_2, ring_3, ring_4)