# Quiz1 Practice for CMU 15-110 (written in f18)

import random

def convert_decimal_to_unsigned_ints():
    bits = random.randint(3, 6)
    n = random.choice(range(2**bits))
    answer = bin(n)[2:]
    answer = '0'*(bits - len(answer)) + answer
    return ('Represent %d as a %d-bit unsigned binary number.' % (n, bits), answer)

def convert_decimal_to_signed_ints():
    bits = random.randint(3, 6)
    n = random.choice(range(2**(bits-1)))
    answer = bin(n)[2:]
    answer = '1' + '0'*((bits-1) - len(answer)) + answer
    return ("Represent -%d as a %d-bit signed binary number in sign-magnitude" % (n, bits), answer)

def convert_string_to_zero_terminated_numbers():
    s = ''
    n = random.randint(1, 4)
    goodChars = [ 'A', 'B', 'C', 'D', 'a', 'b', 'c', 'd', '0', '1', '2', '3']
    for _ in range(n): s += random.choice(goodChars)
    answer = [ ord(c) for c in s ] + [0]
    answer = ', '.join([str(v) for v in answer])
    print("\nHint: here are some ascii values:  'A' is 65, 'a' is 97, and '0' is 48")
    return ("Represent the string '%s' using zero-terminated ints" % s,
            answer)

def convert_string_to_length_prefixed_numbers():
    s = ''
    n = random.randint(1, 4)
    goodChars = [ 'A', 'B', 'C', 'D', 'a', 'b', 'c', 'd', '0', '1', '2', '3']
    for _ in range(n): s += random.choice(goodChars)
    answer = [n] + [ ord(c) for c in s ]
    answer = ', '.join([str(v) for v in answer])
    print("\nHint: here are some ascii values:  'A' is 65, 'a' is 97, and '0' is 48")
    return ("Represent the string '%s' using length-prefixed ints" % s,
            answer)

def convert_floats_to_our_in_class_representation():
    leftPart = str(random.randint(1,99))
    rightPart = '0' * random.randint(0,2) + str(random.randint(1,99)) + str(random.randint(1,9))
    n = leftPart + '.' + rightPart
    mantissa = leftPart + rightPart
    exponent = len(rightPart)
    answer = '%s, %d' % (mantissa, exponent)
    return ("Represent the float %s as two unsigned ints\nusing the mantissa,exponent representation from class" % n,
            answer)

def largest_unsigned_int_in_k_bits():
    k = random.randint(1, 8)
    return ("What is the largest unsigned int that can be represented in %d bits?\nGive your answer in base 10" % k,
            ('1'*k + ' = %d') % (2**k-1))

def compute_n_minus_m_using_tens_complement():
    n = int(str(random.randint(5,9)) + '0' + str(random.randint(0,4)))
    m = int(str(random.randint(1,4)) + str(random.randint(0,9)) + str(random.randint(5,9)))
    assert(500 <= n <= 999)
    assert(100 <= m <= 499)
    tc999 = 999 - m
    tc1k = 1000 - m
    d = n - m
    question = "Show the work to compute %d - %d using 10's complement" % (n, m)
    answer = (("%d -> %d + 1 -> %d " % (m, tc999, tc1k)) +
              ("  (so %d equals %d in 10's complement)\n" % (tc1k, -m)) +
              ("  So: %d - %d = %d + %d (if we ignore the last carry)\n" % (n, m, n, tc1k)) +
              ("  Answer: %d\n" % d) +
              ("  Note: for credit, your work must show both %d and %d" % (tc1k, d))
              )
    return (question, answer)

def compute_n_times_m_using_lattice_multiplication():
    n = random.randint(10, 99)
    m = random.randint(10, 99)
    a,b,c,d = (n//10,n%10,m//10,m%10)
    ac,ad,bc,bd = (a*c, a*d, b*c, b*d)
    e,f,g,h = (ac//10, ac%10, bc//10, bc%10)
    i,j,k,l = (ad//10, ad%10, bd//10, bd%10)
    p = l
    q = h + k + j
    c1, q = q//10, q%10
    r = c1 + g + f + i
    c2, r = r//10, r%10
    s = c2 + e
    z = 1000*s + 100*r + 10*q + p
    assert(z == n*m)
    assert(s <= 9)
    question = 'Show the work to compute %d * %d using lattice multiplication' % (n, m)
    answer = '''
         a       b
      ----------------
     |      /|      / |
     |  e  / | g   /  |
     |    /  |    /   |
   s |   /   |   /    |  c
     |  /  f |  /  h  |
     | /     | /      |
     |/      |/       |
      ----------------
     |      /|      / |
     |  i  / | k   /  |
     |    /  |    /   |
   r |   /   |   /    |  d
     |  /  j |  /  l  |
      ----------------
          q       p
So: n * m = z'''
    for v in 'abcdefghijklmnpqrsz':
        x = str(locals()[v])
        if (v not in 'mnz'): assert(ord('0') <= ord(x) <= ord('9'))
        answer = answer.replace(v, x)
    return (question, answer)

def compute_n_times_m_using_egyptian_multiplication():
    n = random.randint(2, 9)
    m = random.randint(16, 31)
    mbits = bin(m)[2:] # like: '11011'
    madds = len(mbits)-1 + mbits.count('1')-1
    nbits = bin(n)[2:]
    nadds = len(nbits)-1 + nbits.count('1')-1
    if (madds <= nadds): bits,adds = mbits,madds
    else: m,n,bits,adds = n,m,nbits,nadds
    question = "Show all %d additions (always only adding only two numbers) used\nto compute %d * %d using egyptian multiplication" % (adds, n, m)
    answer = ''
    for i in range(1, len(bits)):
        x = n * 2**(i-1)
        y = n * 2**i
        answer += "\n  %d + %d = %d (%d %d's)"  % (x, x, y, 2**i, n)
    answerParts = [ ]
    for i in range(len(bits)):
        if (bits[i]=='1'):
            answerParts.append(2**(len(bits)-1-i))
    bitsSum = ' + '.join(str(v) for v in answerParts)
    if (bits.count('1') == 1):
        answer += '''
 ---------
Now we note that %d is a power of 2, so we are done!''' % m
    else:
        answer += '''
 ---------
Now we note that %d = %s, so:
 ----------''' % (m, bitsSum)
        prevM = answerParts.pop()
        while (answerParts != [ ]):
            moreM = answerParts.pop()
            nextM = prevM+moreM
            answer += ("\n  %d + %d = %d (%d %d's + %d %d's -> %d %d's)" %
                      (n*prevM, n*moreM, n*nextM,
                       prevM, n, moreM, n, nextM, n))
            prevM = nextM
        answer += '\n ---------'
    answer += '\nSo we found %d * %d = %d in %d additions!' % (n, m, n*m, adds)
    return (question, answer)

def make2dList(rows, cols):
    a=[]
    for row in range(rows): a += [[0]*cols]
    return a

def find_flipped_bit_in_parity_card_trick():
    n = 2*random.randint(2,3)
    a = make2dList(n, n)
    for row in range(n-1):
        for col in range(n-1):
            a[row][col] = random.randint(0, 1)
    for col in range(n-1):
        a[n-1][col] = sum([a[row][col] for row in range(n-1)]) % 2
    for row in range(n):
        a[row][n-1] = sum([a[row][col] for col in range(n-1)]) % 2
    # now flip a bit
    solnRow = random.randint(0, n-2)
    solnCol = random.randint(0, n-2)
    a[solnRow][solnCol] = 1 - a[solnRow][solnCol]
    # now set up the board
    board = ''
    for row in range(n):
        board += '    '
        for col in range(n): board += ' %d ' % a[row][col]
        board += '\n'
    question = '''Say we saw this image from the Parity Card Trick website,
after we set up the board properly and after a bit was flipped,
where 0 is face-down and 1 is face-up:\n%s\
Which bit was flipped, in (row, col) notation, where we start counting
at 0 not 1 (so the top row is row 0, and the left column is col 0)?''' % board
    answer = '(%d, %d)' % (solnRow,solnCol)
    return (question, answer)

def cmd():
    prompt = 'Press Return (for more of this exercise type) or q --> '
    while True:
        reply = input(prompt)
        if (reply == ''): return True
        if (reply == 'q'): return False
        print('Illegal response.  Enter either Return or q.')
        prompt = 'Return to continue or q to quit --> '

def quiz1Practice():
    print('\nQuiz1 Practice!!!!')
    fns = [ convert_decimal_to_unsigned_ints,
            convert_decimal_to_signed_ints,
            convert_string_to_zero_terminated_numbers,
            convert_string_to_length_prefixed_numbers,
            convert_floats_to_our_in_class_representation,
            largest_unsigned_int_in_k_bits,
            compute_n_minus_m_using_tens_complement,
            compute_n_times_m_using_lattice_multiplication,
            compute_n_times_m_using_egyptian_multiplication,
            find_flipped_bit_in_parity_card_trick
          ]
    n = len(fns)-1
    while True:
        print('\n' + '-'*40)
        for i, fn in enumerate(fns):
            print('%d. %s' % (i, fn.__name__.replace('_', ' ')))
        print('-'*40)
        choice = input('Choice [0-%d or q to quit] --> ' % (len(fns)-1))
        if (choice == 'q'): return
        elif (choice == ''): n = (n + 1) % len(fns)
        else:
            try: n = int(choice)
            except: print('Illegal response, try again.\n'); continue
            if ((n < 0) or (n >= len(fns))): print('Out of range, try again.\n'); continue
        while True:
            question, answer = fns[n]()
            input('\nQuestion: ' + question + '...')
            print('Answer: ' + answer + '\n')
            if (not cmd()): break

quiz1Practice()