COMP_assignment

# COMP3308 Assignment 1 - 3 digit game
# Author: Jarod Reynolds
#
# Attempt 1 - Sun, 29th March, 12:50am

# Node data structure
# Each node will store the three digits, the digit that was changed,
# a reference to it's parent node, and it's heuristic value

import sys

class Node:
    def __init__(self, three_digits, last_changed=None, parent=None, heuristic=None):
        self.three_digits = three_digits # 3 element list
        self.last_changed = last_changed # digit index (0,1,2)
        self.parent = parent
        self.heuristic = heuristic
        self.expanded = False
    def set_parent(self, parent):
        self.parent = parent
    def get_parent(self):
        return self.parent
    def generate_children(self):
        # Generate children. At most 4 children for each node.
        # Order: dig0--, dig0++, dig1--, dig1++, dig2--, dig2++
        # Conditions:
        #   1. Cannot add to 9 or subtract from 0
        #   2. Cannot move to a forbidden number (don't bother generating a forbidden child)
        #   3. Cannot change same digit twice
        #
        # TODO: (maybe just check for duplicates in the fringe later)
        # Also don't create nodes that already exist:
        #   Identical nodes have the same 3 digits, and their parents have the same 3 digits
        children = []

        # Check conditions for i = 0,1,2 and create nodes accordingly
        # for i in range(3):
        #     print(i)
        #     if self.last_changed != i:
        #         if self.three_digits[i] != 0:
        #             temp = self.three_digits
        #             # dig--
        #             temp[i] -= 1
        #             print(temp)
        #             if temp not in forbidden:
        #                 #TODO: Check for duplicates? See method comments
        #                 # If not a duplicate:
        #                 children.append(Node(temp, i, self))
        #         if self.three_digits[i] != 9:
        #             # dig++
        #             temp = self.three_digits
        #             temp[i] += 1
        #             print(temp)
        #             if temp not in forbidden:
        #                 children.append(Node(temp, i, self))

        # if self.last_changed != 0:
        #     if self.three_digits[0] != 0:
        #         # dig0--
        #         if [self.three_digits[0]-1, self.three_digits[1], self.three_digits[2]]  not in forbidden:
        #             children.append(Node([self.three_digits[0]-1, self.three_digits[1], self.three_digits[2]], 0, self))
        #     if self.three_digits[0] != 9:
        #         # dig++
        #         if [self.three_digits[0]+1, self.three_digits[1], self.three_digits[2]]  not in forbidden:
        #             children.append(Node([self.three_digits[0]+1, self.three_digits[1], self.three_digits[2]], 0, self))
        #
        # if self.last_changed != 1:
        #     if self.three_digits[1] != 0:
        #         # dig0--
        #         if [self.three_digits[0], self.three_digits[1]-1, self.three_digits[2]]  not in forbidden:
        #             children.append(Node([self.three_digits[0], self.three_digits[1]-1, self.three_digits[2]], 1, self))
        #     if self.three_digits[1] != 9:
        #         # dig++
        #         if [self.three_digits[0], self.three_digits[1]+1, self.three_digits[2]]  not in forbidden:
        #             children.append(Node([self.three_digits[0], self.three_digits[1]+1, self.three_digits[2]], 1, self))
        #
        # if self.last_changed != 2:
        #     if self.three_digits[2] != 0:
        #         # dig0--
        #         if [self.three_digits[0], self.three_digits[1], self.three_digits[2]-1]  not in forbidden:
        #             children.append(Node([self.three_digits[0], self.three_digits[1], self.three_digits[2]-1], 1, self))
        #     if self.three_digits[2] != 9:
        #         # dig++
        #         if [self.three_digits[0], self.three_digits[1], self.three_digits[2]+1]  not in forbidden:
        #             children.append(Node([self.three_digits[0], self.three_digits[1], self.three_digits[2]+1], 1, self))

        if self.last_changed != 0:
            if self.three_digits[0] != 0:
                # dig0--
                children.append(Node([self.three_digits[0]-1, self.three_digits[1], self.three_digits[2]], 0, self))
            if self.three_digits[0] != 9:
                # dig++
                children.append(Node([self.three_digits[0]+1, self.three_digits[1], self.three_digits[2]], 0, self))

        if self.last_changed != 1:
            if self.three_digits[1] != 0:
                # dig0--
                children.append(Node([self.three_digits[0], self.three_digits[1]-1, self.three_digits[2]], 1, self))
            if self.three_digits[1] != 9:
                # dig++
                children.append(Node([self.three_digits[0], self.three_digits[1]+1, self.three_digits[2]], 1, self))

        if self.last_changed != 2:
            if self.three_digits[2] != 0:
                # dig0--
                children.append(Node([self.three_digits[0], self.three_digits[1], self.three_digits[2]-1], 2, self))
            if self.three_digits[2] != 9:
                # dig++
                children.append(Node([self.three_digits[0], self.three_digits[1], self.three_digits[2]+1], 2, self))
        return children

#######################################################
###       TODO: TEST COMPARE FUNCTION                ##
#######################################################

# Compares two given nodes to check if they are duplicates.
# Identical nodes have the same 3 digits, and their parents have the same 3 digits
# Returns True if nodes are duplicates, False otherwise
def compare_nodes(node1, node2):
    if node1.three_digits == node2.three_digits:
        if node1.get_parent().three_digits == node2.get_parent().three_digits:
            return True
    return False

# Checks if the given node already exists in the expanded list
def duplicate(new_node, expanded_list):
    for node in expanded_list:
        if compare_nodes(node, new_node):
            return True
    return False

# Iterative DFS
# Returns two lists - solution path and expanded nodes
def DFS(root, goal, forbidden):
    # Empty lists for expanded, fringe nodes and solution path
    expanded = []
    fringe = []
    solution_path = []
    # Add the root node to the fringe
    fringe.append(root)

    while(len(fringe)):

        if(len(expanded) > 999):
            break

        # Expand the last node added to the fringe
        node = fringe[-1]
        while(duplicate(node, expanded)):
            fringe.pop()
            node = fringe[-1]
        fringe.pop()
        expanded.append(node)
        node.expanded = True

        if node.three_digits == goal:
            # print("goal found")
            break

        children = node.generate_children()
        children.reverse()

        for child in children:
            if child.three_digits not in forbidden:
                fringe.append(child)

    # Traverse back up the tree from the goal to find the solution path
    while node.three_digits != root.three_digits:
        solution_path.append(node.three_digits)
        node = node.get_parent()
    solution_path.append(node.three_digits)
    solution_path.reverse()

    return solution_path, nums_from_nodes(expanded)

# Iterative BFS
# Returns two lists - solution path and expanded nodes
def BFS(root, goal, forbidden):
    # Empty lists for expanded, fringe nodes and solution path
    expanded = []
    fringe = []
    solution_path = []
    # Add the root node to the fringe
    fringe.append(root)

    while(len(fringe)):

        if(len(expanded) > 999):
            print("No solution found.")
            break

        # Expand the last node added to the fringe
        node = fringe[0]

        while(duplicate(node, expanded)):
            fringe.pop(0)
            node = fringe[0]
        fringe.pop(0)
        expanded.append(node)
        node.expanded = True

        if node.three_digits == goal:
            # print("goal found")
            break

        children = node.generate_children()
        # children.reverse()

        for child in children:
            if child.three_digits not in forbidden:
                fringe.append(child)

    # Traverse back up the tree from the goal to find the solution path
    while node.three_digits != root.three_digits:
        solution_path.append(node.three_digits)
        node = node.get_parent()
    solution_path.append(node.three_digits)
    solution_path.reverse()

    return solution_path, nums_from_nodes(expanded)


def nums_from_nodes(list):
    nums = []
    for node in list:
        nums.append(node.three_digits)
    return nums

def make_string(list):
    path_string = []
    for num in list:
        string = []
        for dig in num:
            string.append(str(dig))
        path_string.append(''.join(string))
    return ','.join(path_string)

def main():

    # forbidden = []
    # root = Node([3,2,0])
    # goal = [1,1,0]
    # path, expanded = DFS(root, goal, forbidden)
    # print(make_string(path))
    # print(make_string(expanded), end='')

    algorithm = sys.argv[1]
    file_contents = open(sys.argv[2]).readlines()
    line1 = file_contents[0].strip()
    line2 = file_contents[1].strip()
    start, goal = [], []
    for i in range(3):
        start.append(int(line1[i]))
        goal.append(int(line2[i]))

    forbidden = []
    if len(file_contents) > 2:
        line3 = file_contents[2].strip().split(',')
        for number in line3:
            num = []
            for i in range(3):
                num.append(int(number[i]))
            forbidden.append(num)

    # print(start)
    # print(goal)
    # print(forbidden)

    root = Node(start)

    if algorithm == 'D':
        path, expanded = DFS(root, goal, forbidden)
    elif algorithm == 'B':
        path, expanded = BFS(root, goal, forbidden)

    print(make_string(path))
    print(make_string(expanded), end='')

if __name__ == "__main__":
    main()