Puun tunnistus

Annettuna on ruudukko, joka kuvaa puun rakenteen. Tehtäväsi on tunnistaa ruudukossa oleva puu.

Ruudukossa voi olla seuraavia merkkejä:

• .: tyhjä ruutu
• 1–9: puun solmu
• /: yhteys alavasemmalle
• |: yhteys alaspäin
• \: yhteys alaoikealle

Jokaisella solmulla voi olla enintään kolme lasta. Solmun ja lapsen välissä on yksi tai useampi merkki, jotka esittävät yhteyden. Jokaista yhteyttä vastaa suora viiva, jossa ei ole käännöksiä.

Jos solmulla on yksi lapsi, se on suoraan alhaalla. Jos lapsia on kaksi, ne ovat alavasemmalla ja alaoikealla. Jos lapsia on kolme, ne ovat alavasemmalla, alhaalla ja alaoikealla.

Toteuta tiedostoon findtree.py funktio find_tree, jolle annetaan parametrina ruudukon kuvaus listana merkkijonoja. Funktion tulee palauttaa puun rakenne Node-luokan avulla esitettynä.

Voit olettaa, että ruudukon koko on enintään 20 \times 20 merkkiä ja se kuvaa jonkin puun, jossa on vähintään yksi solmu.

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children if children else []

    def __repr__(self):
        if self.children == []:
            return f"Node({self.value})"
        else:
            return f"Node({self.value}, {self.children})"

def find_tree(grid):
    # TODO

if __name__ == "__main__":
    grid = [r"...........",
            r"...........",
            r"......5....",
            r"...../.\...",
            r"....3...\..",
            r"....|....1.",
            r"....2......"]
    tree = find_tree(grid)
    print(tree)
    # Node(5, [Node(3, [Node(2)]), Node(1)])

    grid = [r"....1.....",
            r".../.\....",
            r"..2...\...",
            r"..|....3..",
            r"..7.../|\.",
            r"./.\.4.5.6",
            r"8...9....."]
    tree = find_tree(grid)
    print(tree)
    # Node(1, [Node(2, [Node(7, [Node(8), Node(9)])]), Node(3, [Node(4), Node(5), Node(6)])])

Tässä r"" tarkoittaa merkkijonoa, jossa merkkiä \ ei käsitellä escape-merkkinä vaan tavallisena merkkinä.