leetcode-problem-2-add-two-numbers.py

"""LeetCode Problem 2 - Add Two Numbers

This file requires the Abseil python library, absl-py.
"""

from typing import List, Optional, Text

from absl import app
from absl import flags
from absl import logging
from absl.testing import absltest

FLAGS = flags.FLAGS

LOG_VALUES = flags.DEFINE_boolean('log_values', False, 'Log values while testing')


class ListNode:

  def __init__(self, val=0, next=None):
    if val < 0 or val > 9:
      raise ValueError(f'Invalid value: {val} (should be single digit)')
    self.val = val
    self.next = next

  def __repr__(self) -> Text:
    return '[' + ', '.join(str(element) for element in self.as_list()) + ']'

  def as_list(self) -> List[int]:
    rest_of_list = self.next.as_list() if self.next else []
    return [self.val] + rest_of_list


def create_list_from_array(digits: List[int]) -> Optional['ListNode']:
  """Create list from array.

  This is a test-only function used to be able to define new test cases in a
  clean and simple way.
  """
  return ListNode(val=digits[0], next=create_list_from_array(digits[1:])) if digits else None


def create_array_from_list(l1: Optional['ListNode']) -> List[int]:
  """Create array from list.
  
  This is a test-only function used to be able to print out linked-list
  versions of numbers in a clean and easy way.
  """
  return [l1.val] + create_array_from_list(l1.next) if l1 else []


def create_number_from_list(l1: Optional['ListNode']) -> int:
  """Create number from a linked list.

  For simplicity, we should assume that we will never call this method on a
  null pointer.
  """
  rest_of_the_list = 10 * create_number_from_list(l1.next) if l1.next else None
  return l1.val + rest_of_the_list if rest_of_the_list else l1.val


def create_list_from_number(number: int) -> Optional['ListNode']:
  if number > 9:
    return ListNode(val=number % 10, next=create_list_from_number(number // 10))
  return ListNode(val=number, next=None)


def add_numbers(l1: Optional['ListNode'], l2: Optional['ListNode']) -> Optional['ListNode']:
  a = create_number_from_list(l1)
  b = create_number_from_list(l2)
  r = a + b
  return create_list_from_number(r)


class Solution:
  def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    return add_numbers(l1, l2)


class ListNodeTest(absltest.TestCase):

  def test_negative_value_is_invalid(self) -> None:
    with self.assertRaises(ValueError):
      ListNode(val=-1)

  def test_double_digit_value_is_invalid(self) -> None:
    with self.assertRaises(ValueError):
      ListNode(val=10)


class CreateListFromArrayTest(absltest.TestCase):

  def test_single_number_list(self) -> None:
    with self.subTest():
      actual = create_list_from_array([0])
      expected = ListNode(val=0, next=None)
      self.assertEqual(actual.val, expected.val)
      self.assertIsNone(expected.next)

    with self.subTest():
      actual = create_list_from_array([1])
      expected = ListNode(val=1, next=None)
      self.assertEqual(actual.val, expected.val)
      self.assertIsNone(expected.next)

  def test_two_number_list(self) -> None:
    with self.subTest():
      actual = create_list_from_array([1, 2])
      expected = ListNode(val=1, next=ListNode(val=2, next=None))
      self.assertEqual(actual.val, expected.val)
      self.assertIsNotNone(actual.next)
      self.assertEqual(actual.next.val, expected.next.val)

    with self.subTest():
      actual = create_list_from_array([2, 4])
      expected = ListNode(val=2, next=ListNode(val=4, next=None))
      self.assertEqual(actual.val, expected.val)
      self.assertIsNotNone(actual.next)
      self.assertEqual(actual.next.val, expected.next.val)

  def test_three_number_list(self) -> None:
    with self.subTest():
      actual = create_list_from_array([1, 2, 3])
      expected = ListNode(val=1, next=ListNode(val=2, next=ListNode(val=3)))

      current_actual_node = actual
      current_expected_node = expected

      while current_actual_node:
        self.assertIsNotNone(current_expected_node)
        self.assertEqual(current_actual_node.val, current_expected_node.val)

        if current_actual_node.next is None:
          self.assertIsNone(current_expected_node.next)

        current_actual_node = current_actual_node.next
        current_expected_node = current_expected_node.next


class CreateArrayFromListTest(absltest.TestCase):

  def test_single_node_list(self) -> None:
    with self.subTest():
      actual = create_array_from_list(ListNode(val=0, next=None))
      expected = [0]
      self.assertCountEqual(actual, expected)

    with self.subTest():
      actual = create_array_from_list(ListNode(val=1, next=None))
      expected = [1]
      self.assertCountEqual(actual, expected)

  def test_two_element_list(self) -> None:
    with self.subTest():
      actual = create_array_from_list(ListNode(val=2, next=ListNode(val=1)))
      expected = [2, 1]
      self.assertCountEqual(actual, expected)

    with self.subTest():
      actual = create_array_from_list(ListNode(val=3, next=ListNode(val=2)))
      expected = [3, 2]
      self.assertCountEqual(actual, expected)

  def test_five_element_list(self) -> None:
    with self.subTest():
      actual = create_array_from_list(create_list_from_array([1, 2, 3, 4, 5]))
      expected = [1, 2, 3, 4, 5]
      self.assertCountEqual(actual, expected)


class CreateNumberFromListTest(absltest.TestCase):

  def test_single_element_list(self) -> None:
    with self.subTest():
      actual = create_number_from_list(create_list_from_array([0]))
      expected = 0
      self.assertEqual(actual, expected)
      
    with self.subTest():
      actual = create_number_from_list(create_list_from_array([1]))
      expected = 1
      self.assertEqual(actual, expected)

  def test_two_element_list(self) -> None:
    with self.subTest():
      actual = create_number_from_list(create_list_from_array([0, 1]))
      expected = 10
      self.assertEqual(actual, expected)
      
    with self.subTest():
      actual = create_number_from_list(create_list_from_array([2, 1]))
      expected = 12
      self.assertEqual(actual, expected)

  def test_three_element_list(self) -> None:
    with self.subTest():
      actual = create_number_from_list(create_list_from_array([2, 4, 3]))
      expected = 342
      self.assertEqual(actual, expected)
      
    with self.subTest():
      actual = create_number_from_list(create_list_from_array([5, 6, 4]))
      expected = 465
      self.assertEqual(actual, expected)
      
    with self.subTest():
      actual = create_number_from_list(create_list_from_array([7, 0, 8]))
      expected = 807
      self.assertEqual(actual, expected)


class CreateListFromNumberTest(absltest.TestCase):

  def both_lists_are_equal(self, actual: Optional[ListNode], expected: Optional[ListNode]) -> bool:
    if LOG_VALUES.value:
      logging.info('Actual: %s', actual)
      logging.info('Expected: %s', expected)
    
    current_actual_node = actual
    current_expected_node = expected
  
    while current_actual_node:
      self.assertIsNotNone(current_expected_node)
      self.assertEqual(current_actual_node.val, current_expected_node.val)
  
      if current_actual_node.next is None:
        self.assertIsNone(current_expected_node.next)
  
      current_actual_node = current_actual_node.next
      current_expected_node = current_expected_node.next

    self.assertIsNone(current_expected_node)

  def test_single_digit_number(self) -> None:
    with self.subTest():
      actual = create_list_from_number(0)
      expected = create_list_from_array([0])
      self.both_lists_are_equal(actual, expected)

    with self.subTest():
      actual = create_list_from_number(1)
      expected = create_list_from_array([1])
      self.both_lists_are_equal(actual, expected)
      
    with self.subTest():
      actual = create_list_from_number(2)
      expected = create_list_from_array([2])
      self.both_lists_are_equal(actual, expected)


  def test_double_digit_number(self) -> None:
    with self.subTest():
      actual = create_list_from_number(10)
      expected = create_list_from_array([0, 1])
      self.both_lists_are_equal(actual, expected)

    with self.subTest():
      actual = create_list_from_number(27)
      expected = create_list_from_array([7, 2])
      self.both_lists_are_equal(actual, expected)


  def test_three_digit_number(self) -> None:
    with self.subTest():
      actual = create_list_from_number(342)
      expected = create_list_from_array([2, 4, 3])
      self.both_lists_are_equal(actual, expected)
      
    with self.subTest():
      actual = create_list_from_number(465)
      expected = create_list_from_array([5, 6, 4])
      self.both_lists_are_equal(actual, expected)
      
    with self.subTest():
      actual = create_list_from_number(807)
      expected = create_list_from_array([7, 0, 8])
      self.both_lists_are_equal(actual, expected)


class SolutionTest(absltest.TestCase):

  def test_examples(self) -> None:
    with self.subTest(name='Example 1'):
      l1 = create_list_from_array([2, 4, 3])
      l2 = create_list_from_array([5, 6, 4])
      actual = create_array_from_list(add_numbers(l1, l2))
      expected = [7, 0, 8]
      self.assertCountEqual(actual, expected)

    with self.subTest(name='Example 2'):
      l1 = create_list_from_array([0])
      l2 = create_list_from_array([0])
      actual = create_array_from_list(add_numbers(l1, l2))
      expected = [0]
      self.assertCountEqual(actual, expected)

    with self.subTest(name='Example 3'):
      l1 = create_list_from_array([9, 9, 9, 9, 9, 9, 9])
      l2 = create_list_from_array([9, 9, 9, 9])
      actual = create_array_from_list(add_numbers(l1, l2))
      expected = [8, 9, 9, 9, 0, 0, 0, 1]
      self.assertCountEqual(actual, expected)

  def test_edge_cases(self) -> None:
    with self.subTest():
      l1 = create_list_from_array([1])
      l2 = create_list_from_array([1])
      actual = create_array_from_list(add_numbers(l1, l2))
      expected = [2]
      self.assertCountEqual(actual, expected)


if __name__ == '__main__':
  absltest.main()