<jupyter_start><jupyter_text>**cs3102 Fall 2019** Problem Set 1 (Jupyter Part): (Un)natural Numbers   **Purpose**  The goal of this part of Problem Set 1 is to explore our constructive recursive definition of Natural Numbers. The programs you will write will be similar to both "definitions" and "proofs", but as executable code. (Of course, one should be very careful in considering a "program" to be a "proof", especially without proving the program is correct.)   Defining Natural NumbersWe will use Python strings to represent our Natural Numbers. The main point of this is to show that the "0" and "S" used in the definition are just symbols: we only use string concatenation, extraction, and comparison to build our Natural Number represetation. Of course, this is a ridiculously silly way to represent Natural Numbers if we were actually doing computations on them (especially as Python already provides a built-in integer datatype, which could be naturally used to approximate the Natural Numbers).<jupyter_code>def makeZero():
    return '🍩' 

def isZero(n):
    return n == '🍩' 

def makeSuccessor(n):
    return '+' + n # String concatenation

def getPredecessor(n):
    assert n[0] == '+' # must be a S(p)
    return n[1:] # returns the rest of the string<jupyter_output><empty_output><jupyter_text>(feel free to replace the emojis we used to your favorites, but be wary of multi-byte unicode characters!)<jupyter_code>makeZero()
makeSuccessor(makeSuccessor(makeZero()))
assert(isZero(makeZero()))
assert(not isZero(makeSuccessor(makeZero())))
assert(isZero(getPredecessor(makeSuccessor(makeZero()))))
zero = makeZero()
one = makeSuccessor(zero)
one
print(getPredecessor(one))<jupyter_output>🍩<jupyter_text>Defining EqualtyHere's a definition of equality using our Natural Numbers, based on [Class 2](https://uvatoc.github.io/class2) (slide 36). (We could just defined equality using Python string equality, but that would be tied to our string representation and assume we know what Python's string equality does. Although we are using strings for our representation now, we don't want to rely on anything other than the `makeZero`, `isZero`, `makeSuccessor` and `getPredecessor` functions we defined.)<jupyter_code>def equalNumbers(n, m):
    """Returns true iff n and m represent the same number."""
    if isZero(n):
        return isZero(m)
    else:
        if isZero(m):
            return False
        else:
            return equalNumbers(getPredecessor(n), getPredecessor(m))
    
two = makeSuccessor(one)
three = makeSuccessor(two)
four = makeSuccessor(three)

assert(equalNumbers(zero, zero))
assert(not equalNumbers(one, zero))
assert(equalNumbers(four, four))
assert(not equalNumbers(four, three))
assert(not equalNumbers(three, four))<jupyter_output><empty_output><jupyter_text>**Problem J1.** Define a function `addNumbers` that takes as input two Natural Numbers (as represented here) and returns a Natural Number that represents the sum of the two inputs.<jupyter_code>def addNumbers(a, b):
    """Takes two Natural Numbers as input, and outputs a 
    Natural Number that represents their sum."""
    pass # fill in with your code for Problem J1
# Here are some examples to test your addNumbers function. None of the assertions should fail.
assert(equalNumbers(addNumbers(two, zero), two))
assert(equalNumbers(addNumbers(zero, two), two))
assert(equalNumbers(addNumbers(one, one), two))
assert(equalNumbers(addNumbers(two, two), four))
print ("All tests passed!")<jupyter_output><empty_output><jupyter_text>**Problem J2.** Define a function `greaterNumber` that takes as input two Natural Numbers (as represented here) and returns a Boolean that denotes whether the first input is greater than the second.<jupyter_code>def greaterNumber(a, b):
    """Takes two Natural Numbers as input, and outputs a Boolean indicating 
    if the number represented by the first input is greater than (>) the 
    number represented by the second."""
    pass # fill in your code for Problem J2
# Here are some examples to test your lessThanEq function. None of the assertions should fail.
assert(not greaterNumber(addNumbers(two, zero), two))
assert(not greaterNumber(addNumbers(zero, zero), two))
assert(not greaterNumber(four, four))
assert(greaterNumber(addNumbers(two, three), four))
print ("All tests passed!")<jupyter_output><empty_output><jupyter_text>Unnatural TreesNext, we explore a recursive constructive definition of trees. We will say that a Tree is either the _empty tree_, which we will represent with an acorn: '🌰', or it will be a pair of Trees.    Added 9 September: Our definition of trees is a bit non-standard here, since what we are calling the empty tree, and returning from makeEmptyTree is actually a tree with one root node. This leads to some confusion in the definition of treeHeight, which is different here from the standard definition used in Problem 2 (in the main assignment). We define the height of the _empty tree_, which is actually the tree with one root node, as 0, and increase the height for each level from there. This differs from the standard level where the empty tree has no nodes and height 0, the tree with one root node has height 1, and so on.<jupyter_code>def makeEmptyTree():
    """Returns the empty tree."""
    return '🌰'

def makeBranchedTree(l, r):
    """Takes two Trees as inputs, and outputs a Tree whose left branch is the
    first input, and whose right branch is the second input."""
    # Python note: this makes a tuple, which is essentially an immutable list. 
    return (l, r)

def getLeftBranch(t):
    """Takes a non-empty Tree as input, and outputs the left branch of that Tree.
    (Note that this is a partial function. It is not defined for the empty tree, 
    and fails with an error on that input.)"""
    assert(not isEmpty(t))
    return t[0]

def getRightBranch(t):
    """Takes a non-empty Tree as input, and outputs the right branch of that Tree."""
    assert(not isEmpty(t))
    return t[1]<jupyter_output><empty_output><jupyter_text>We can make a few example trees.<jupyter_code>emptyTree = makeEmptyTree()
print(emptyTree)

fullHeight1 = makeBranchedTree(emptyTree, emptyTree)
fullHeight2 = makeBranchedTree(fullHeight1, fullHeight1)
print(fullHeight2)

fullHeight3 = makeBranchedTree(fullHeight2, fullHeight2)
unbalancedHeight4 = makeBranchedTree(fullHeight1, fullHeight3)
print(unbalancedHeight4)<jupyter_output>🌰
(('🌰', '🌰'), ('🌰', '🌰'))
(('🌰', '🌰'), ((('🌰', '🌰'), ('🌰', '🌰')), (('🌰', '🌰'), ('🌰', '🌰'))))<jupyter_text>**Problem J3.** Define `treeSize`, `treeHeight`, and `leafCount` functions which that all take a single Tree as their input, and output an int (the regular Python integer type, not our (un)Natural Number type from the earlier problems) that represents the total number of nodes in the tree, the height of the tree, and the total number of leaves in the tree respectively. You may use standard int operations including `+`, `-`, `*`, `<`, etc.).(Hint: a _leaf_ is a Tree whose children are both empty trees, so it may be helful to write an `isLeaf` function, but it is not required.)<jupyter_code>def treeSize(t):
    """Takes a Tree as input, and outputs an int representing the total number of nodes in the tree."""
    pass # replace with your code
# Some tests for treeeSize
assert(treeSize(emptyTree) == 0)
assert(treeSize(fullHeight1) == 1)
assert(treeSize(fullHeight2) == 3)
assert(treeSize(fullHeight3) == 7)
assert(treeSize(unbalancedHeight4) == 9)
print("Zuka Zama!")
def treeHeight(t):
    """Takes a Tree as input, and outputs the height of that tree."""
    pass # replace with your code
assert(treeHeight(emptyTree) == 0)
assert(treeHeight(fullHeight1) == 1)
assert(treeHeight(fullHeight2) == 2)
assert(treeHeight(fullHeight3) == 3)
assert(treeHeight(unbalancedHeight4) == 4)
print("Wahoowa!")
def leafCount(t):
    """Takes a Tree as input, and outputs the total number of leaves of that tree."""
    pass # replace with your code
assert(leafCount(emptyTree) == 0)
assert(leafCount(fullHeight1) == 1)
assert(leafCount(fullHeight2) == 2)
assert(leafCount(fullHeight3) == 4)
assert(leafCount(unbalancedHeight4) == 5)
print("Yippee!")<jupyter_output><empty_output><jupyter_text>Optional Bonus Challenge: Code golf!    Code golf is a (to some, surprisingly popular!) game where the goal is to find the smallest correct implementation of a particular function (or set of functions, as in this case). For your main answers to problem J3, you should strive for simplicity and understandability in your code.             For an optional challenge, find the shortest implemention you can of the three functions. You can't change the names of the treeSize, treeHeight, and leafCount functions, or the tree representation, and should not make assumptions about the underlying tree representation (that is, your solution should not rely on our implementing the Tree using a tuple, but should only use the `isEmpty`, getLeftBranch`, and `getRightBranch` functions to access the tree). We know a solution that is 248 characters (4 lines) long. Any solution that is under 400 characters long will be worth bonus points, with extra bonuses possible for any solutions that are as short or shorter than our solution, as well as the shortest correct solution.            To be eligible, of course, your solution must be correct, including passing all of the tests above but also some additional generated tests.<jupyter_code># Optional: put your code golf definitions of treeSize, treeHeight, and leafCount here<jupyter_output><empty_output><jupyter_text>BijectionsWe can show two sets are the same size by demonstrating a bijection between the elements in these sets. Intuitively, a bijection shows two sets to be the same size because it being injective implies every input element maps to a unique output element, and surjective implies that every possible output element is mapped to by some input. Combined, these two properties cause elements to form matched pairs. Here, we are going to show that the number of binary strings of length n is equal to 2_n_ by giving a bijection with the natural numbers up to 2_n_, i.e., by making these matched pairs. To do this, your goal is to write a function `bitstringToNaturalNumber` which will convert a binary string to a Natural Number (using our constructive definition from earlier in this notebook). Your function should be a one-to-one mapping: there should be some binary string input that produces every natural number, and there should not be any two different binary string inputs that ouput the same natural number. (Note, however, that it is not necessary to assume any particular way of interpreting a bitstring as a number.) **Problem J4.** Write this `bitstringToNaturalNumber` function.<jupyter_code>def bitstringToNaturalNumber(binaryString):
    pass<jupyter_output><empty_output><jupyter_text>The following code checks that every bitstring of length n maps to a different natual number:<jupyter_code>def isOneToOne(n):
    allBitStrings = ['']
    for i in range (n):
        tempBitStrings = []
        for bitstring in allBitStrings:
            tempBitStrings.append(bitstring + '0')
            tempBitStrings.append(bitstring + '1')
        allBitStrings = tempBitStrings
    allNaturals = []
    for bitstring in allBitStrings:
        natural = bitstringToNaturalNumber(bitstring)
        if natural in allNaturals:
            return False
        allNaturals.append(natural)
    return True

assert(isOneToOne(0))
assert(isOneToOne(1))
assert(isOneToOne(4))
print("YESSSSS!!!")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.08410892795587728, 'fraction_numerical': 0.007238883143743537, 'mean_word_length': 4.9727225939269175, 'pattern_counts': {'":': 0, '<': 44, '<?xml version=': 0, '>': 44, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '133255', 'license': 'MIT', 'n_tokens_mistral': 3303, 'n_tokens_neox': 3139, 'n_words': 1458, 'path': 'src/public/ps/ps1-Copy1.ipynb', 'repo_name': 'jonahweissman/uvatoc.github.io', 'size': '11604'}