Week 6: Extra Practice (Optional)

These problems are optional and just for practice.

There is no new programming assignment this week, so you have a chance to catch up and make revisions to existing assignments. However, in case you want more practice with sets, dictionaries and general problem solving, here are a few problems you can try.

Both of these problems are drawn from LeetCode which is useful for preparing for coding interviews. Instead of using LeetCode’s interface for developing your solution, I would recommend creating a new file in your cs146 folder and develop your solutions there. There is nothing to submit to Gradescope, but some example inputs and outputs for testing your code are provided below.

Problem 1: Roman to Integer

Write a function called roman_to_integer which converts Roman numerals to an integer year. The conversion from symbols to values is given in the table below.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

Each character in the input string would be converted to its corresponding integer value and added to the final result. However, there are a few extra rules:

  1. If there is a I before a V or a X, the value should be 4 (if before V) or 9 (if before X).
  2. If there is a X before a L or a C, the value should be 40 (if before L) or 90 (if before C).
  3. If there is a C before a D or a M, the value should be 400 (if before C) or 900 (if before M).

Examples:

  1. roman_to_integer("III") should return 3.
  2. roman_to_integer("LVIII") should return 58.
  3. roman_to_integer("MCMXCIV") should return 1994.

Hint: process the input (str) from right-to-left.

SYMBOLS = {
  'I': 1,
  'V': 5,
  'X': 10,
  'L': 50,
  'C': 100,
  'D': 500,
  'M': 1000
}

def roman_to_int(s):
  """
  Converts roman numerals to an integer year.

  Args:
    s: year represented with Roman numerals as a string.

  Returns:
    Integer year.
  """
  result = 0
  last_c = None
  for c in s[::-1]: # process string in reverse
    result += SYMBOLS[c]
    if not last_c:
      last_c = c
      continue
    if last_c in 'VX' and c == 'I':
      result -= 2 # we added +1 but it should be -1, so -2
    if last_c in 'LC' and c == 'X':
      result -= 20 # we added +10 but it should be -10, so -20
    if last_c in 'DM' and c == 'C':
      result -= 200 # we added +100 but it should be -100 so -200
    last_c = c
  return result

Problem 2: Happy Numbers

A number n is determined to be “happy” by going through the following process:

  1. Step 1: Replace n with the sum of the squares of its digits (e.g. \(23\) would become \(2^2 + 3^2 = 13\)).
  2. Step 2: If n is equal to 1 the input number is happy. Otherwise, go back to Step 1 with the new value for n.

However, this could loop infinitely if we start cycling back and forth between numbers we have already encountered. If a number has already been encountered, then the number is sad.

Write a function called is_happy which returns True if an input number n is happy and False otherwise.

Examples:

  1. is_happy(1) returns True.
  2. is_happy(2) returns False.
  3. is_happy(11) returns False.
  4. is_happy(23) returns True.

Hint: what can you use to efficiently keep track of previously “seen” numbers?


def is_happy(n):
  """
  Determines whether a number is a happy number.
  
  Args:
    n: number to check.

  Returns:
    True if n is happy, False otherwise.
  """
  seen = set()
  if n == 1:
    return True
  while True:
    seen.add(n)
    s = str(n)
    n = 0
    for i in range(len(s)):
      n += int(s[-i -1]) ** 2
    if n in seen:
      return False
    if n == 1:
      return True