Estats d'un NPC
===============

.. py:module:: npc

Un *nonplayer-character* (NPC) és un personatge d'un videojoc que no està controlat per un jugador, sinó per l'ordinador, com ara un monstre que t'ataca d'un joc de rol, un personatge de suport que t'ajuda a lluitar o, en un joc de construcció, un robot llenyataire com el de la figura, que recull fusta i la duu al magatzem. El comportament d'un NPC es pot modelitzar amb un graf dirigit. Els nodes d'aquest graf són els diferents estats del NPC; les arestes, que indiquen canvis d'un estat a un altre, estan etiquetades amb informació de la condició o esdeveniment que provoca el canvi d'estat.

.. figure:: npc-llenyataire.svg
   :width: 90 %
   :align: center

   Graf d'estats d'un NPC llenyataire

Representarem el graf d'estats d'un NPC qualsevol mitjançant un :py:class:`networkx.DiGraph`. Les arestes tindran un atribut anomenat :py:const:`'canvi'`, un string que indica què provoca el canvi d'un estat a l'altre. Per tal de poder fer proves fàcilment us proporcionem el fitxer :download:`crea.py`, on hi ha funció :py:func:`graf_exemple` que crea i retorna el graf de l'exemple de la figura.


Funció `parelles` (2 punts)
---------------------------

Dissenyeu la següent funció i deseu-la al mòdul :py:mod:`npc` (fitxer :file:`npc.py`):

  .. py:function:: parelles(g)

     :param ~networkx.DiGraph g: graf d'estats d'un NPC
     :return: llista de parelles d'estats `(x, y)` tals que hi ha un canvi en `g` que duu directament de `x` a `y` i un altre que duu de `y` a `x`. Cadascuna de les parelles de la llista retornada ha de ser tal que `x` < `y`. A més, la llista ha d'estar ordenada lexicogràficament (l'ordre per defecte de Python).
     :rtype: llista de tuples de parelles de strings

Essent `g` el graf de la figura, aquesta funció ha de respondre així:

.. literalinclude:: tests-parelles.txt
   :language: pycon
   :start-after: --ini-enunciat
   :end-before: --fi-enunciat
                
Disposeu de més jocs de prova en el fitxer :download:`tests-parelles.txt`.


Funció `llista_canvis` (2 punts)
--------------------------------

Dissenyeu la següent funció i deseu-la al mateix mòdul :py:mod:`npc` (fitxer :file:`npc.py`):

  .. py:function:: llista_canvis(g, e1, e2)

     :param ~networkx.DiGraph g: graf d'estats d'un NPC
     :param str e1: un dels estats de `g`
     :param str e2: un dels estats de `g`     
     :return: llista més curta dels canvis que provoquen que el NPC passi de l'estat `e1` a l'estat `e2`. Si hi més d'una possibilitat amb el mínim nombre de canvis, la funció retorna qualsevol de les llistes de canvis més curtes. Si no hi ha cap possibilitat, cal retornar la llista buida.

Essent `g` el graf de la figura, aquesta funció ha de respondre així:

.. literalinclude:: tests-canvis.txt
   :language: pycon
   :start-after: --ini-enunciat
   :end-before: --fi-enunciat
                
Disposeu de més jocs de prova en el fitxer :download:`tests-canvis.txt`.