CMU 15-110: Principles of Computing
Unit 2: Optional/Advanced Topics

# 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)))