# ---------------------------------------------------------
# CSCI 246, Python Assignment
# John Paxton
# Last Modified: March 24, 2022
# ---------------------------------------------------------

# ---------------------------------------------------------
# power_set
# ---------------------------------------------------------
# unused: elements of the set that haven't been considered, a string
# my_set: the partial set constructed
# ---------------------------------------------------------
# Construct and return the power set of the original unused string
# ---------------------------------------------------------

def power_set(unused, my_set=""):
    if unused == "":        # base case, one of the subsets
        return [my_set]
    else:                   # general case, either include element or don't
        new_element = unused[0]
        unused = unused[1:]
        return power_set(unused, my_set + new_element) + power_set(unused, my_set)

# ---------------------------------------------------------
# hamming
# ---------------------------------------------------------
# number_1: the first number to consider
# number_2: the second number to consider
# ---------------------------------------------------------
# Calculate and return the hamming distance between the numbers
# ---------------------------------------------------------

def hamming(number_1, number_2):
    distance = 0
    while (number_1 != 0) or (number_2 != 0):
        if number_1 % 2 != number_2 % 2:    #do least significant bits differ?
            distance += 1
        number_1 = number_1 // 2
        number_2 = number_2 // 2
    return distance

# ---------------------------------------------------------
# reflexive
# ---------------------------------------------------------
# max_label: the points in the relation are labeled 0, 1, ... max_label
# points: the points in the relation, e.g. [[0,0],[2,3]]
# ---------------------------------------------------------
# Returns True if the relation is reflexive
# ---------------------------------------------------------

def reflexive(max_label, points):
    for label in range(max_label + 1):
        if [label, label] not in points:
            return False
    return True

# ---------------------------------------------------------
# symmetric
# ---------------------------------------------------------
# max_label: the points in the relation are labeled 0, 1, ... max_label
# points: the points in the relation, e.g. [[0,0],[2,3]]
# ---------------------------------------------------------
# Returns True if the relation is symmetric
# ---------------------------------------------------------

def symmetric(max_label, points):
    for point in points:
        new_point = [point[1], point[0]]
        if new_point not in points:
            return False
    return True

# ---------------------------------------------------------
# transitive
# ---------------------------------------------------------
# max_label: the points in the relation are labeled 0, 1, ... max_label
# points: the points in the relation, e.g. [[0,0],[2,3]]
# ---------------------------------------------------------
# Returns True if the relation is transitive
# ---------------------------------------------------------

def transitive(max_label, points):
    for point_1 in points:
        for point_2 in points:
            if point_1[1] == point_2[0]:
                new_point = [point_1[0], point_2[1]]
                if new_point not in points:
                    return False
    return True

# ---------------------------------------------------------
# print_set
# ---------------------------------------------------------
# original_set: a string that represents a set, e.g. "{1, 2}"
# power_set, a list of strings that represents the power set of
#            the original set in any order, e.g. ["", "1", "12", "2"]
# ---------------------------------------------------------
# Print out a numbered list of each subset.  Match the
# format of the sample output transcript exactly.
# ---------------------------------------------------------

def print_set(original_set, power_set):
    print("The power set of", original_set, "consists of")
    counter = 1
    for subset in power_set:
        print(str(counter) + ". {" + subset + "}")
        counter += 1
    print("----------------")

# ---------------------------------------------------------
# relation_properties
# ---------------------------------------------------------
# max_label: The label of the highest point, e.g. 3
#            Assume that points 0, 1, ... max_label exist
# points: A list of lists that shows all ordered pairs in the relation,
#         e.g. [[0,1], [2,3]] is a relation consisting of 2 points
# ---------------------------------------------------------
# Determine whether a relation is (1) reflexive, (2) symmetric
# and/or (3) transitive.  These three concepts are introduced
# in section 8.2.  Match the format of the sample output transcript.
# ---------------------------------------------------------

def relation_properties(max_label, points):
    print("Data Set:", points)
    print("Reflexive:", reflexive(max_label, points))
    print("Symmetric:", symmetric(max_label, points))
    print("Transitive:", transitive(max_label, points))
    print("----------------")

# ---------------------------------------------------------
# main
# ---------------------------------------------------------
# The main program to test the following functions that you
# write: (1) power_set, (2) hamming, (3) reflexive, (4) symmetric
# and (5) transitive.  Note that we will test your solution with
# a different main function so be sure that your solution is
# fully general.  Match the format of the sample output transcript.
# ---------------------------------------------------------

def main():
    # Power Sets are introduced in section 6.1
    print("Test case 1A")
    print_set("{}", power_set(""))
    print("Test case 1B")
    print_set("{a}", power_set("a"))
    print("Test case 1C")
    print_set("{a, b, c, d, e}", power_set("abcde"))

    # Hamming Distance is introduced in section 7.1
    print("Test case 2")
    print("2A. Hamming 0, 0 =", hamming(0, 0))
    print("2B. Hamming 100, 200 =", hamming(100, 200))
    print("2C. Hamming distance 44444444444444444, 333333333333333=",
          hamming(44444444444444444, 333333333333333))
    print("----------------")

    print("Test case 3")
    relation_properties(0, [])
    print("Test case 4")
    relation_properties(4, [[0,0],[0,1],[0,2],[0,3],[0,4],[4,0],[4,1],[4,2],[4,3],[4,4], \
                            [2,4],[2,3],[2,2],[2,1],[2,0],[3,4],[3,3],[3,2],[3,1],[3,0], \
                            [1,2],[1,4],[1,3],[1,1],[1,0]])
    print("Test case 5")
    relation_properties(4, [[0,0],[0,1],[0,2],[0,3],[0,4],[4,0],[4,1],[4,2],[4,3],[4,4], \
                            [2,4],[2,3],[2,2],[2,1],[2,0],[3,4],[3,3],[3,2],[3,1],[3,0]])
    print("Test case 6")
    relation_properties(10, [[9,7],[5,2],[2,5],[7,9]])
    print("Test case 7")
    relation_properties(10, [[9,7],[5,2],[2,5],[7,9],[2,2],[5,5],[7,7],[9,9]])
    print("Test case 8")
    relation_properties(10, [[9,7],[5,2],[2,5],[7,9],[2,2],[5,5],[7,7],[9,9], \
                             [0,0],[1,1],[3,3],[4,4],[6,6],[10,10],[8,8]])
   
# ---------------------------------------------------------

main()