sample_code.py

# From 2011-B sample.

# Q2
def transpose_graph(G):
  GT = {}
  for node in G:
    GT[node] = set()

  for node in G:
    for neighbor in G[node]:
      GT[neighbor].add(node)

  return GT

# Q3
def guessing_game():
  # For m=5, we get a (31, 26, 3) code.
  code = get_Hamming_code(5)

  # We want to get the codeword representing x from Zfania, which we decide it
  # to be code[x] arbitrarily. To get the i'th bit, we ask Tzfania if x belongs
  # to the set of values y such that code[y] has the i'th bit set.
  codeword = ""
  for i in range(31):
    S = {y for y in range(2**26) if code[y][i] == '1'}
    if tzfania(S):
      codeword += "1"
    else:
      codeword += "0"

  # The codeword is of distance at most 1 from code[x], meaning we can
  # correct the possible error.
  decode = {code[x]:x for x in range(2**26)}
  if codeword in decode:  # No errors at all.
    return decode[codeword]

  # Going over all possible single errors.
  swap = {"0": "1", "1": "0"}
  for i in range(31):
    c = codeword[:i] + swap[codeword[i]] + codeword[i+1:]
    if c in decode:
      return decode[c]

# Q4
def combine_sequence(parts):
  parts = list(parts)
  # prefix stores the index of a part according to its first 20 characters
  # suffix stores the index of a part according to its last 20 characters
  prefix = {}
  suffix = {}
  for i, part in enumerate(parts):
    prefix[part[:20]] = i
    suffix[part[-20:]] = i

  # We find the first part - which is the only part whose first 20
  # characters do not appear in the suffix dict.
  ordered = []
  for part in parts:
    if part[:20] not in suffix:
      ordered.append(part)
      break

  # We now add the parts according to their order, given the prefix dict.
  key = ordered[0][-20:]
  while key in prefix:
    next_part = parts[prefix[key]]
    ordered.append(next_part[20:])
    key = next_part[-20:]

  # We return the concatanation of all parts in their correct order.
  return "".join(ordered)