pyramid_descent.py

from enum import Enum
from typing import Optional
from dataclasses import dataclass


class DIRECTION(Enum):
    LEFT = 'L'
    RIGHT = 'R'


@dataclass
class Node:
    data: int
    left: 'Node' = None
    right: 'Node' = None


def find_path(
    start_node: Node,
    product_so_far: int,
    product_to_find: int
) -> Optional[str]:
    product_so_far *= start_node.data
    if product_so_far > product_to_find:
        return None  # None to indicate no path can be found since the product so far is greater than the target
    if product_so_far == product_to_find:
        return '' # empty since if the path is found, you don't have to go left or right

    if start_node.left:
        left_path = find_path(
            start_node=start_node.left,
            product_so_far=product_so_far,
            product_to_find=product_to_find
        )
        if left_path is not None:
            return DIRECTION.LEFT.value + left_path  # left plus whatever path was taken further down the pyramid

    if start_node.right:
        right_path = find_path(
            start_node=start_node.right,
            product_so_far=product_so_far,
            product_to_find=product_to_find
        )
        if right_path is not None:
            return DIRECTION.RIGHT.value + right_path  # right plus whatever path was taken further down the pyramid

    return None  # None to indicate that no path was found either left or right


# simple sanity tests
def test_find_path():
    start_node = Node(
        data=2,
        left=Node(
            data=3,
            left=Node(data=20),
            right=Node(data=1),
        ),
        right=Node(
            data=5,
            left=Node(data=12),
            right=Node(data=7),
        ),
    )
    # test what happens when the product_to_find is the first thing
    assert (
        find_path(start_node=start_node, product_so_far=1, product_to_find=2)
        == ''
    )
    # it returns the shortest path - observe that LLR also has product 6
    assert (
        find_path(start_node=start_node, product_so_far=1, product_to_find=6)
        == 'L'
    )
    assert (
        find_path(start_node=start_node, product_so_far=1, product_to_find=10)
        == 'R'
    )
    assert (
        find_path(start_node=start_node, product_so_far=1, product_to_find=70)
        == 'RR'
    )
    # there are two ways to get 120 - but it returns the "leftmost" one
    assert (
        find_path(start_node=start_node, product_so_far=1, product_to_find=120)
        == 'LL'
    )
    # it couldn't find this
    assert (
        find_path(start_node=start_node, product_so_far=1, product_to_find=7)
        is None
    )


def make_start_node():
    number_of_lines = int(input())
    lines = []
    for _ in range(number_of_lines):
        line = input()
        lines.append(line)
    array = []
    for line in lines:
        array.append(
            list(map(int, line.split(',')))
        )
    nodess = [[] for _ in range(len(array))]
    for i, item in enumerate(array):
        for num in item:
            nodess[i].append(Node(data=num))

    for i in range(len(nodess)-1):
        for j in range(i+1):
            nodess[i][j].left = nodess[i+1][j]
            nodess[i][j].right = nodess[i+1][j+1]

    return nodess[0][0]


"""Sample input looks like this
720
5
2
4,3
3,2,6
2,9,5,2
10,5,2,15,5
"""


target = int(input())
start_node = make_start_node()
print(
    find_path(
        start_node=start_node,
        product_so_far=1,
        product_to_find=target
    )
)