Sistema de reg

Avís

Aquest exercici és de complexitat elevada.

Un agricultor vol muntar un sistema per a regar el blat. Ha canalitzat l’aigua fins a un cert punt de la plantació i disposa d’una sèrie de tubs i colzes per poder situar l’aspersor en algun punt del camp. Els tubs són rígids i de diverses llargades i els pot unir mitjançant colzes de 90 graus, com els de la figura:

Considereu que el camp és un pla infinit amb l’origen de coordenades en el punt inicial d’arribada de l’aigua. Els tubs només es poden disposar en direccions paral.les a l’eix x o a l’eix y. No es poden tallar ni doblegar. Suposeu també que es disposa d’un conjunt determinat de tubs però de tants colzes com es vulgui. L’objectiu del problema és calcular en quins punts del camp es pot col·locar l’aspersor, sempre en una extremitat del camp. Suposeu que les mides dels colzes no influeixen en el càlcul (els girs són «immediats»). No us oblideu dels casos en què no es facin servir tots els tubs ni d’aquells en què s’uneixen dos colzes seguits (per fer tornar l’aigua enrere).

Més específicament, definiu la funció següent, la qual, donada una llista de nombres corresponents a les llargades dels tubs disponibles, ha de retornar un conjunt de coordenades del pla, expressat com un set de Python de tuples de dues components:

def aspersor(llargades_tubs):
    """
    Donada la llista de nombres 'llargades_tubs',
    retorna el conjunt (set) de coordenades (tuples (x,y))
    on es pot col·locar l'aspersor.

    >>> aspersor([4]) == {(0, -4), (-4, 0), (0, 0), (4, 0), (0, 4)}
    True
    >>> aspersor([5,2]) == {(-5,0), (-2,0), (3,0), (0,7), (-7,0), \
        (-2,5), (0,3), (2,5), (0,-5), (0,-3), (-5,-2), (5,-2), (0,0), \
        (5,0), (0,5), (2,-5), (-2,-5), (7,0), (0,-7), (-3,0), (2,0), \
        (0,-2), (-5,2), (5,2), (0,2)} )
    True
    >>> aspersor([1,1,1,8]) == {(-9,-2), (1,-10), (-1,0), (-3,8), \
        (0,7), (1,6), (0,10), (-8,1), (-1,-7), (-2,0), (-9,-1), \
        (8,-1), (1,1), (-1,-6), (8,2), (-6,1), (-2,-1), (6,0), (2,-9), \
        (7,-2), (7,0), (0,-3), (0,1), (0,-1), (-1,-9), (-1,-2), \
        (6,-1), (2,-8), (0,-9), (0,-6), (-2,-9), (2,1), (-7,0), \
        (-2,-7), (7,2), (-1,1), (-8,-3), (1,-6), (1,-1), (9,-2), \
        (0,11), (-8,2), (-3,-8), (-1,-1), (1,10), (-10,0), (-5,0), \
        (-1,2), (7,1), (2,-1), (9,0), (0,5), (1,0), (0,8), (2,7), \
        (8,3), (9,2), (6,1), (-2,8), (-3,0), (-1,-8), (-9,0), (0,2), \
        (3,0), (2,8), (8,0), (-9,2), (-6,-1), (8,-3), (2,-7), (1,-2), \
        (0,-5), (-2,7), (-7,-2), (5,0), (-9,1), (10,0), (-2,9), \
        (-1,6), (3,-8), (-8,-2), (0,-11), (1,-7), (0,-10), (0,-8), \
        (-8,3), (1,9), (-7,2), (-10,1), (-7,-1), (1,-9), (7,-1), \
        (0,6), (1,7), (0,9), (-8,0), (-2,-8), (10,-1), (9,1), (-8,-1), \
        (-1,9), (-1,8), (0,3), (1,2), (2,9), (8,1), (-6,0), (8,-2), \
        (-1,10), (0,0), (-2,1), (-1,-10), (9,-1), (10,1), (0,-2), \
        (-1,7), (11,0), (1,-8), (-11,0), (0,-7), (3,8), (2,0), (1,8), \
        (-7,1), (-10,-1)
    True
    """