An algorithmic task with triangles

Question

I have a problem with an algorithmic task. There is content of it: "You have ten points on a plane and none three of them are collinear, each pair of different points is connected by line segment, which is green or blue. Calculate how many triangles have sides only in one colour." I tried a solution with n-ary trees but I get repeated triangles with cyclic permutations of integers on the result list.

Answer 1

Patryk, the problem is solvable with n-trees. However, to avoid cyclic permutations you need to skip symmetric line segments. If you create a line segment from 0 -> 1 you do not need to create a segment from 1 -> 0. Below is a complete code which solves the problem with n-trees with the recursive depth-first search. Excuse for Polish names of classes and methods. The interface is in English however. If you analyze the code you will get the point surely.

from random import choice
import copy

class Punkt:
    def __init__(self, numer):
        self.__numer = numer
        self.__odcinki = {}

    def dodaj_odcinek_wychodzący(self, punkt_docelowy, kolor):
        self.__odcinki[punkt_docelowy] = Odcinek(self.__numer, punkt_docelowy, kolor)

    def wez_odcinek_do_punktu_docelowego(self, punkt_docelowy):
        return (punkt_docelowy, self.__odcinki[punkt_docelowy].wez_kolor())

    def liczba_odcinkow(self):
        return len(self.__odcinki)

    def wez_kolor_punktu_docelowego(self, punkt_docelowy):
        return self.__odcinki[punkt_docelowy].wez_kolor()

    def lista_punktow_docelowych(self):
        return self.__odcinki.keys()


class Odcinek:
    def __init__(self, punkt_zrodlowy, punkt_docelowy, kolor):
        self.__punkt_zrodlowy = punkt_zrodlowy
        self.__punkt_docelowy = punkt_docelowy
        self.__kolor = kolor

    def wez_kolor(self):
        return self.__kolor


class Structure:
    def __init__(self, liczba_punktow=10):
        self.__punkty = [Punkt(i)
                         for i in range(liczba_punktow)]
        for i in range(liczba_punktow):
            for j in range(i + 1, liczba_punktow):
                self.__punkty[i].dodaj_odcinek_wychodzący(j, choice(["green", "blue"]))
        # for j in range(liczba_punktow):
        #     for i in range (j + 1, liczba_punktow):
        #         self.__punkty[j].dodaj_odcinek_wychodzący(*(self.__punkty[j].wez_odcinek_do_punktu_docelowego(i)))

    def wez_punkt(self, numer):

        return self.__punkty[numer]

    def wez_liczbe_punktow(self):

        return len(self.__punkty)


class Search:

    def __init__(self, struktura):

        self.__s = struktura

    def wez_liczbe_punktow(self):

        return self.__s.wez_liczbe_punktow()

    def wez_punkt(self, numer):

        return self.__s.wez_punkt(numer)

    def szukaj(self, kolor="green"):

        self.__szukany_kolor = kolor

        lista_trojkatow = []

        liczba_trojkatow = 0

        wszystkie_trojkaty = []

        for i in range(self.wez_liczbe_punktow()):

            lista_odwiedzonych_punktow = [i]

            lista_trojkatow = self.szukaj_z_punktu(i,lista_odwiedzonych_punktow,lista_trojkatow)

        return len(lista_trojkatow), lista_trojkatow

    def wez_szukany_kolor(self):

        return self.__szukany_kolor

    def szukaj_z_punktu(self, numer, trojkat, lista_trojkatow):

        if len(trojkat) == 3: # jeżeli zebraliśmy już trzy punkty to brakuje tylko zamykającego, czwartego

            if self.wez_punkt(trojkat[0]).wez_kolor_punktu_docelowego(
                trojkat[-1]) == self.wez_szukany_kolor(): # sprawdź czy do punktu zamykającego prowadzi odcinek o szukanym kolorze

                trojkat.append(trojkat[0]) # dodaj punkt zamykajacy do trójkąta

                lista_trojkatow.append(trojkat) # dodaj trojkąt do listy trójkątów

                # return lista_trojkatow # zwróć liste trójkątów obliczonych dotychczas
        else:

            potomkowie = []
            for punkt_docelowy in self.wez_punkt(numer).lista_punktow_docelowych():
                if self.wez_punkt(numer).wez_kolor_punktu_docelowego(punkt_docelowy) == self.wez_szukany_kolor():
                    potomkowie.append(punkt_docelowy)

            for potomek in potomkowie:
                trojkat_kopia = copy.copy(trojkat)
                trojkat_kopia.append(potomek)
                lista_trojkatow = self.szukaj_z_punktu(potomek, trojkat_kopia, lista_trojkatow)

        return lista_trojkatow


if __name__ == "__main__":

    s = Structure()

    for source_point in range(s.wez_liczbe_punktow()):

        for destination_point in s.wez_punkt(source_point).lista_punktow_docelowych():

            print(f"{source_point} -> {destination_point} = {s.wez_punkt(source_point).wez_kolor_punktu_docelowego(destination_point)}")

    color = "green"

    searching = Search(s)

    number_of_triangles, all_triangles = searching.szukaj("green")

    print(f"Number of triangles of color {color} = {number_of_triangles}")

    print(f"List of all triangles: {all_triangles}")