Python Button Algorithm

user_11250902 0
Viewed 174

I'm currently trying to solve a puzzle programmatically with Python, I want to be able to solve it myself but I'm finding it hard to describe the problem so I can seek assistance with it through online resources. Below I'll describe the nature of the problem and any help given is really appreciated.

So there is a set of 4 coloured buttons and each of them are assigned a function which changes the colour of one or more of the buttons in a looping manner. A code representation of these buttons might be as follows:

# 1 = green, 2 = red, 3 = blue, 4 = purple
# goes 1->4 then loops
cstate = [1,3,4,1] # current state of the numbers

The four different functions a button can perform are:

  1. Increments itself by 1
  2. Increments itself and one other by 1
  3. Increments itself and 2 others by 1
  4. Increments all by 1

Each function is unique to each button, hence no two buttons can be assigned the same function.

My attempt at representing these functions was to create an array describing the index of the buttons that are affected by clicking each button, for example:

incArray =[[0,3],[0,1,3],[0,1,2,3],[3]]

Following this I created a function that applies the buttons functions to the cstate array described above:

def increment(currentState, whichClicked, whichEffects):
    
    retArr = currentState
    for click in whichClicked:
        for change in whichEffects[click]:
            if currentState[change] == 4:
                retArr[change] = 1
            else:
                retArr[change] += 1
        print(retArr)

    return retArr

Now in this particular example I fed the increment function with whichClicked = [2,2,2,1,0,3,3], as I know this to be the correct combination (or final state) to be fstate = [2,3,3,4].

What I'm trying to achieve is to write code to generate the whichClicked array described above, given the cstate and the fstate. Thanks in advance for any help provided!

algorithm python
1 Answers

I tend to develop these kind of algorithms by starting with a 'dumb' brute-force algorithm and then optimize it further

Brute force

You could implement this in a "brute-force" way by a kind of Breadth-first search algorithm, where you are going to just:

  • click all buttons on the initial state (4 options)
  • for all of the resulting states, you will click all buttons again (16 options)
  • etc. where you constantly check whether you reached the goal state.

Something like this:

from collections import deque
from dataclasses import dataclass

start_state = [1,3,4,1] # current state of the numbers
incArray =[[0,3],[0,1,3],[0,1,2,3],[3]]

@dataclass
class Node:
    path: list
    state: list

def apply_button(state, inc_array, button):
    new_state = state.copy()
    for affected_button in inc_array[button]:
        new_state[affected_button] = new_state[affected_button] % 4 + 1
    return new_state

def brute_force(start_state, inc_array, goal_state):
    iterations=0
    leafNodes = deque([Node([], start_state)])
    while True:
        node = leafNodes.popleft()
        for button in range(4):
            iterations+=1
            new_state = apply_button(node.state, inc_array, button)
            new_path = node.path + [button]
            if new_state==goal_state:
                print(f"iterations: {iterations}")
                return new_path
            leafNodes.append(Node(new_path, new_state))

print(brute_force(start_state,incArray,[2, 3, 3, 4]))
# OUTPUT:
# iterations: 7172
# [0, 1, 2, 2, 2, 3, 3]

First optimization

You will see that the resulting output is the same as the "whichClicked" array you provided in your example, but that all items are sorted. This is because the order of clicking the buttons does not affect the end result. You can use that knowledge to optimize your algorithm as it is evaluating tons of redundant options. (e.g. path [0,1] gives the same result as path [1,0])

So a new strategy could be to exclude these redundant options in your solution. If you draw the whole search graph on paper (or uncomment the # print(new_path) line), you see that following code only iterates over the "sorted" path:


def brute_force_opt(start_state, inc_array, goal_state):
    iterations=0
    leafNodes = deque([Node([], start_state)])
    while True:
        node = leafNodes.popleft()
        min_button = node.path[-1] if len(node.path) else 0
        for button in range(min_button, 4):
            iterations+=1
            new_state = apply_button(node.state, inc_array, button)
            new_path = node.path + [button]
            # print(new_path)
            if new_state==goal_state:
                print(f"iterations: {iterations}")
                return new_path
            leafNodes.append(Node(new_path, new_state))

print(brute_force_opt(start_state,incArray,[2, 3, 3, 4]))
# OUTPUT:
# iterations: 283
# [0, 1, 2, 2, 2, 3, 3]

As you see from the input, the number of iterations has been reduced from 7172 to 283

The first paths to be evaluated are now:

[0]
[1]
[2]
[3]
[0, 0]
[0, 1]
[0, 2]
[0, 3]
[1, 1]
[1, 2]
[1, 3]
[2, 2]
[2, 3]
[3, 3]
[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 0, 3]

edited

Second Optimization

A second optimization could be to take into account that there are 'cyclic' paths: e.g. after pressing the fourth button four times (path [3,3,3,3]), you will end up in the same state. A straighforward way to take this into account is to keep a list of states that you already encountered. If you end up in such a state again, you could just ignore it as it will not give a better solution (the path will always be longer getting to the solution via this cyclic path):

def brute_force_opt2(start_state, inc_array, goal_state):
    iterations=0
    encoutered_states = set()
    leafNodes = deque([Node([], start_state)])
    while True:
        node = leafNodes.popleft()
        min_button = node.path[-1] if len(node.path) else 0
        for button in range(min_button, 4):
            new_state = apply_button(node.state, inc_array, button)
            if tuple(new_state) not in encoutered_states:
                iterations+=1
                new_path = node.path + [button]
                # print(new_path)
                if new_state==goal_state:
                    print(f"iterations: {iterations}")
                    return new_path
                leafNodes.append(Node(new_path, new_state))
                encoutered_states.add(tuple(new_state))

print(brute_force_opt2(start_state,incArray,[2, 3, 3, 4]))
# OUTPUT:
# iterations: 213
# [0, 1, 2, 2, 2, 3, 3]

As you see, the number of iterations is now only 182. This number is, as could be expected, lower than the maximum number of unique states (4^4 = 256).

Analytical approaches

Suppose the complexity of this problem would have been much bigger (e.g. much more buttons and colors), a brute force approach might not be feasible and you could consider a more analytical approach where you e.g. calculate how many times every button must be incremented (modulo 4) to go from start to end state and find a combination of button clicks that fulfills this for all buttons.

user_101557400
Related