backtracking_vs_brute_force_lock_combos.py

"""
Completed backtracking code for week11, demonstrating bike-lock combos

Author: Gavin
Modifed by: Avi

"""
import itertools
from typing import List


def get_possible_remaining_char_in_code(solution_attempt, char_in_code: List[int],
                                        length_of_code: int):
    """
    Gets the possible chars that can be in the code, and makes sure that only one '1'
    present in the code. Eg, if length of th code is 3:
    1__
    _1_
    __1
    """
    if 1 in solution_attempt:
        return [i for i in char_in_code if i != 1]
    elif len(solution_attempt) == length_of_code - 1:
        return [1]
    else:
        return char_in_code


def backtracking(solution_attempt: List[List[int]], char_in_code: List[int],
                 len_of_code: int):
    """ Backtracking recursive function to generate a list of possible solutions.

    :param solution_attempt: list of current chars in solution attempt
    :param char_in_code: list of items that can be in the code
    :param len_of_code: the required length of the code
    :return: List of the solutions
    """
    chars_to_use_in_attempt = get_possible_remaining_char_in_code(solution_attempt,
                                                                  char_in_code,
                                                                  len_of_code)
    list_of_sol = []

    if len(solution_attempt) == len_of_code:
        # we have found a possible solution to the code!
        return [solution_attempt]

    elif len(chars_to_use_in_attempt) > 0:
        # we still need to add more chars to complete our solution to the code

        for potential_char in chars_to_use_in_attempt:
            current_sol = backtracking(
                solution_attempt + [potential_char],
                char_in_code,
                len_of_code
            )
            # Add our current solution to a list of the solutions
            list_of_sol += current_sol

    return list_of_sol


def get_possible_codes_with_backtracking(char_in_code: List[int], length_of_code: int):
    """Wrapper function to the recursive backtracking function

    eg, if get_possible_codes_with_backtracking(char_in_code: [1,2,3], length_of_code: 3)
    Makes recursive calls like the below:
                            [1??]
                              |
                           /     \
                          /       \
                    [12?]         [13?]
                      |              |
                    /   \          /   \
                   /     \        /     \
                [122]   [123]  [132]   [133]


    Each branch is 1 recursive call.
    The above is just one tree, there will be three such trees, each with '1' in
    a different location, eg [1??] [?1?] [??1]

    The leaf nodes of the trees will be returned as a list as the answer.

    :param char_in_code: the possible chars that can be used in the code
    :param length_of_code: the number of chars in th code
    :return: list of possible combinations
    """
    s = backtracking([], char_in_code, length_of_code)
    return s


def get_possible_codes_with_bruteforce(char_in_code, length_of_code):
    """Uses a bruteforce approach to generate all code combos

    :param char_in_code: the possible chars that can be used in the code
    :param length_of_code: the number of chars in th code
    :return: list of possible combinations
    """
    lock_combos = list(itertools.product(
        char_in_code,
        repeat=length_of_code)
    )
    return lock_combos


def main():
    char_in_code = [1, 2, 3]
    lenght_of_code = 3
    backtracking_possible_codes = get_possible_codes_with_backtracking(
        char_in_code=char_in_code,
        length_of_code=lenght_of_code
    )
    bruteforce_possible_codes = get_possible_codes_with_bruteforce(
        char_in_code=char_in_code,
        length_of_code=lenght_of_code
    )

    print(
        f"#combo with backtracking = {len(backtracking_possible_codes)}\n"
        f"Codes with backtracking: {backtracking_possible_codes}\n")

    print(
        f"#combo with bruteforce = {len(bruteforce_possible_codes)}\n"
        f"Codes with bruteforce: {bruteforce_possible_codes}")


if __name__ == '__main__':
    main()