#
CMU 15-110: Principles of Computing

Unit 2: Optional/Advanced Topics

See:

**The Most Complex Machine (TMCM) by David Eck**- Download the entire TMCM website
- Download the TMCM labs

**Disjunctive Normal Form (DNF) (see here)****Functional Completeness of {And, Or, Not}, {Nand}, and {Nor}****Full Adder****N-bit Adder with Daisy-chaining****N-bit Subtractor with Two's Complement****Memory****Clock**

**Encoding Multiple Integers as Single Integers!**

# This is just a proof-of-concept.
# These mappings will fail for sufficiently large numbers
# (though this is easily fixable).
import math
def pairToInt(x, y):
# First find where this diagonal hits the x axis:
x0 = x + y
# Now, the x axis points are at 1 (0,0), 1+2 (1,0), 1+2+3 (2,0) ,...
# So the # of points up to and including x0 is:
# 1+2+...+(x0+1) = (x0+1)(x0+2)//2
ptsUpToX0 = (x0+1)*(x0+2)//2
# Now don't count those extra points we added to get to the x axis
return ptsUpToX0 - y - 1 # subtract 1 to be 0-based
def intToPair(n):
n += 1 # adjust to be 0-based
# Find the diagonal: 1+2+...+d =set= n = d(d+1)/2
# so d**2 + d - 2n = 0
d = (-1 + (1 + 8*n)**0.5)/2
# take ceiling to include this entire diagonal
d = math.ceil(d)
x0 = d-1
ptsUpToX0 = (x0+1)*(x0+2)//2
# walk back from the last point on the diagonal as needed
delta = ptsUpToX0 - n
return (x0 - delta, delta)
print('Here are the first several mappings:')
for i in range(10):
print(i, intToPair(i), pairToInt(*intToPair(i)))
print()
print('And here they are in reverse:')
for y in range(4,-1,-1):
for x in range(5):
print('%2d' % pairToInt(x, y), end=' ')
print()
print()
def listToInt(L):
assert(len(L) > 0)
result = L[0]
for value in L[1:]:
result = pairToInt(result, value)
return pairToInt(len(L), result)
def intToList(n):
count, result = intToPair(n)
L = [ ]
for _ in range(count-1):
result, value = intToPair(result)
L.append(value)
L.append(result)
return L[::-1]
print('Here we test intToList and listToInt:')
L = [2, 5, 18, 12]
print('L =', L)
print('listToInt(L) = ', listToInt(L))
print('And back to L: ', intToList(listToInt(L)))