GameOfLife

Problem

https://leetcode.com/problems/game-of-life/

Solution

Observe that we can calulate the number of live neighbors by summing the surrounding \(\mathtt{board[i'][j']}\) values. Use a list comprehension to get the neighbor indices, only taking those where \(0 \leq i' < m\) and \(0 \leq j < n\). Make sure to calculate the number of live neighbors for each cell before updating the board.

Code

https://github.com/GeorgeRPu/tech-interview-prep/blob/main/solutions/AddTwoNumbers.py

>>> addTwoNumbers(l1, l2).to_list()
[7, 0, 8]
>>> l1 = ListNode.from_list([0])
>>> l2 = ListNode.from_list([0])
>>> addTwoNumbers(l1, l2).to_list()
[0]
>>> l1 = ListNode.from_list([9, 9, 9, 9, 9, 9, 9])
>>> l2 = ListNode.from_list([9, 9, 9, 9])
>>> addTwoNumbers(l1, l2).to_list()
[8, 9, 9, 9, 0, 0, 0, 1]
"""

from typing import Optional


class ListNode:
    """Node in a linked list.
    """

    def __init__(self, val: int, next: Optional[ListNode] = None):
        self.val = val
        self.next = next

    def to_list(self):
        list = []
        while self is not None:
            list.append(self.val)
            self = self.next
        return list

    @classmethod
    def from_list(cls, list: ListNode[int]) -> Optional[ListNode]:
        head: Optional[ListNode] = None
        for el in list:
            if head is None:
                head = ListNode(el)
                node = head
            else:
                node.next = ListNode(el)
                node = node.next
        return head


def addTwoNumbers(l1: Optional[ListNode], l2: Optional[ListNode]):
    """Add two numbers whose digits are stored in little endian linked lists.
    """
    head = None

    carry = 0
    while not (l1 is None and l2 is None and carry == 0):
        if l1 is not None:
            val1 = l1.val
            l1 = l1.next
        else:
            val1 = 0

        if l2 is not None:
            val2 = l2.val
            l2 = l2.next
        else:
            val2 = 0

        s = carry + val1 + val2
        digit = s % 10
        carry = s // 10

        if head is None:
            head = ListNode(digit, None)
            node = head
        else:
            node.next = ListNode(digit, None)
            node = node.next

    return head

Test

>>> from GameOfLife import gameOfLife
>>> board = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]
>>> gameOfLife(board)
>>> board
[[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]
>>> board = [[1, 1], [1, 0]]
>>> gameOfLife(board)
>>> board
[[1, 1], [1, 1]]

Functions

gameOfLife(board)

Advance the board for Conway's Game of Life by one step.