keypad.py

import string
from typing import List

graph = {
    '1': ['2', '4'],
    '2': ['1', '3', '5'],
    '3': ['2', '6'],
    '4': ['1', '5', '7'],
    '5': ['2', '4', '6', '8'],
    '6': ['3', '5', '9'],
    '7': ['4', '8'],
    '8': ['7', '5', '9', '0'],
    '9': ['6', '8'],
    '0': ['8'],
}


def unique_paths(startpoint: str, length: int) -> List[int]:
    '''
    startpoint needs to be between 0-9 inclusive
    length needs to be an int.
    this returns a list of int which represent paths.
    e.g
    f(5, 1) = [5]
    f(1, 3) = [121, 123, 125, 141, 145, 147]
    f(2, 3) = [ 212, 214, 232, 236, 254, 256, 252, 258 ]
    f(3, 3) = [ 321, 323, 325, 365, 363, 369 ]
    f(4, 3) = [ 454, 456, 452, 458, 412, 414, 478, 474 ]
    f(5, 2) = [ 54, 56, 52, 58 ]
    f(0, 4) = [ 0878, 0874, 0898, 0896, 0854, 0856, 0852, 0858, 0808 ]
    '''
    # Goal is to create a bfs algo that stops when the length is greater than length
    if startpoint not in string.digits:
        raise Exception('startpoint needs to be a string between 0 and 9 inclusive')
    paths = []
    queue = [startpoint]
    while queue:
        path = queue.pop(0)
        if len(path) > length:
            break  # break because all the paths left have a greater lenth than we want
        if len(path) == length:
            paths.append(path)
        for neighbor in graph[path[-1]]:
            queue.append(path+neighbor)
    return paths


def test_unique_paths():
    assert set(unique_paths(startpoint='5', length=1)) == set(['5'])
    assert set(unique_paths(startpoint='1', length=3)) == set(['121', '123', '125', '141', '145', '147'])
    assert set(unique_paths(startpoint='2', length=3)) == set(['212', '214', '232', '236', '254', '256', '252', '258' ])
    assert set(unique_paths(startpoint='3', length=3)) == set(['321', '323', '325', '365', '363', '369' ])
    assert set(unique_paths(startpoint='4', length=3)) == set(['454', '456', '452', '458', '412', '414', '478', '474' ])
    assert set(unique_paths(startpoint='5', length=2)) == set(['54', '56', '52', '58'])
    assert set(unique_paths(startpoint='0', length=4)) == set([ '0878', '0874', '0898', '0896', '0854', '0856', '0852', '0858', '0808'])