.. _tdnote20201rst:

=================================
1A.e - Enoncé 22 octobre 2019 (1)
=================================


.. only:: html

    **Links:** :download:`notebook <td_note_2020_1.ipynb>`, :downloadlink:`html <td_note_2020_12html.html>`, :download:`python <td_note_2020_1.py>`, :downloadlink:`slides <td_note_2020_1.slides.html>`, :githublink:`GitHub|_doc/notebooks/exams/td_note_2020_1.ipynb|*`


Correction du premier énoncé de l’examen du 22 octobre 2019. L’énoncé
propose une façon de disposer des tables rondes dans une salle ronde.

.. code:: ipython3

    from jyquickhelper import add_notebook_menu
    add_notebook_menu()






.. contents::
    :local:





On sait d’après les dernières questions qu’il faudra tout répéter
plusieurs fois. On prend le soin d’écrire chaque question dans une
fonction. C’est un mariage dans une salle ronde. On veut disposer les
tables de sortes qu’elles soient éloignées le plus possible les unes des
autres et du bord de la salle. Les tables sont toutes rondes et toutes
la même taille.

Q1 - distance_table
-------------------

Ecrire une fonction qui calcule la distance entre deux tables rondes
dont on connaît le centre. Et comme ce sont des tables rondes, on
considère que la distance entre deux tables est la distance entre leurs
centres.

.. code:: ipython3

    def distance_table(x1, y1, x2, y2):
        return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5
    
    distance_table(0, 0, 2, 1)




.. parsed-literal::
    2.23606797749979



Q2 - distance_bord
------------------

Ecrire une fonction qui calcule la distance entre une table (son centre)
et le bord de la salle de rayon *R*.

.. code:: ipython3

    def distance_bord(x1, y1, R):
        dist = distance_table(x1, y1, 0, 0)
        return R - dist
    
    distance_bord(1, 1, 5)




.. parsed-literal::
    3.585786437626905



.. code:: ipython3

    distance_bord(10, 1, 5)




.. parsed-literal::
    -5.04987562112089



Q3 - table_alea
---------------

Ecrire une fonction qui tire aléatoirement une table dans le cercle de
rayon *R*.

.. code:: ipython3

    import random
    
    def table_alea(R):
        R2 = R ** 2
        dist = R2 * 2
        while dist > R2:
            x = random.uniform(-R, R)
            y = random.uniform(-R, R)
            dist = x ** 2 + y ** 2
        return x, y
    
    table_alea(5)




.. parsed-literal::
    (0.04023026006364461, -4.613278941761477)



On peut utiliser une autre façon en utilisant les coordonnées polaires.

.. code:: ipython3

    import math
    
    def table_alea_pol(C):
        t = random.uniform(0, math.pi)
        y = random.uniform(0, C)
        x = math.cos(t) * t
        y = math.sin(t) * t
        return x, y
    
    table_alea_pol(5)




.. parsed-literal::
    (0.2697993898932539, 0.07781479211233774)



Q4 - n_table_alea
-----------------

Ecrire une fonction qui tire aléatoirement *N* tables dans le cercle de
rayon *R*.

.. code:: ipython3

    def n_table_alea(N, R):
        return [table_alea(R) for n in range(N)]
    
    n_table_alea(3, 5)




.. parsed-literal::
    [(-2.104239515207136, -1.7109081402403072),
     (-0.46932352351540807, -0.3259610442266929),
     (-1.1743368223886739, 3.2821629999494295)]



Q5 - table_proches
------------------

Ecrire une fonction qui retourne la table la plus proche d’une table ou
du bord. La fonction doit retourner l’indice de la table la plus proche
ou -1 si c’est le bord, puis la distance associée. On ajoute un
paramètre *skip_i* pour éviter une table dans la liste ``list_tables``.

.. code:: ipython3

    def table_proches(x1, y1, list_tables, R, skip_i):
        proche = -1
        best = distance_bord(x1, y1, R)
        for i, table in enumerate(list_tables):
            if i == skip_i:
                continue
            dist = distance_table(x1, y1, table[0], table[1])
            if dist < best:
                best = dist
                proche = i
        return proche, best
    
    R = 5
    list_tables = n_table_alea(3, R)
    table_proches(1, 1, list_tables, R, None)




.. parsed-literal::
    (0, 1.7403604958859722)



.. code:: ipython3

    table_proches(R * 0.9, 0, list_tables, R, None)




.. parsed-literal::
    (-1, 0.5)



Q6 - distance_n_tables_alea
---------------------------

Ecrire une fonction qui tire *N* tables aléatoirement et qui retourne la
distance minimum entre deux tables ou le mur et les tables.

.. code:: ipython3

    def distance_n_tables_alea(N, R):
        distrib = n_table_alea(N, R)
        best = R ** 2
        for i, table in enumerate(distrib):
            proche, dist = table_proches(table[0], table[1], distrib, R, skip_i=i)
            if dist < best:
                best = dist
        return best, distrib
    
    distance_n_tables_alea(3, R)




.. parsed-literal::
    (1.151393678876878,
     [(-0.0883943109284333, -3.2251498896276685),
      (1.9591970274173125, -0.8759281350069976),
      (0.8362221630472657, 3.7566611650530053)])



Q7 - meilleur_table_alea
------------------------

Ecrire une fonction qui tire *N* tables aléatoirement et qui retourne la
distance minimum entre deux tables ou le mur et les tables.

.. code:: ipython3

    def meilleur_table_alea(k, N, R):
        dist = 0
        best = None
        for i in range(k):
            d, distrib = distance_n_tables_alea(N, R)
            if d > dist:
                best = distrib
                dist = d
        return best, dist
    
    meilleur_table_alea(10, 3, R)




.. parsed-literal::
    ([(-1.0002849316792242, -3.5208215962264875),
      (1.537577072452744, -0.650373925673775),
      (2.339568894819979, 0.31652883529303466)],
     1.256221251336387)



Q8 - résultat numérique
-----------------------

Ecrire une fonction qui retourne le résultat pour 11 tables et une salle
de diamètre 1.

.. code:: ipython3

    best, dist = meilleur_table_alea(10, 11, 1)
    best, dist




.. parsed-literal::
    ([(0.5565818929001787, 0.05896867240161785),
      (-0.5288969098327476, 0.28733719348942466),
      (-0.6110699282390006, 0.32241732345580165),
      (-0.14909553247181195, -0.9356539992681199),
      (0.026230694145464417, -0.2908024901550055),
      (0.4975323234658624, -0.06918255935350293),
      (0.60937258121247, 0.16579629631884596),
      (0.22654870937824634, 0.12601838486539685),
      (-0.651232619461013, 0.05440550117493803),
      (-0.25693188063963546, 0.044795815889184576),
      (-0.07316443943516515, 0.8533292769508105)],
     0.0525413549133239)



Q9 - plot_tables
----------------

Ecrire une fonction qui représente la solution avec matplotlib en
partant de l’exemple donnée.

.. code:: ipython3

    %matplotlib inline

.. code:: ipython3

    import matplotlib.pyplot as plt
    from matplotlib.patches import Circle
    
    fig, ax = plt.subplots(1, 1, figsize=(4, 4))
    R = 1
    ax.set_xlim([-R, R])
    ax.set_ylim([-R, R])
    c = Circle((0, 0), 1, alpha=0.2)
    ax.add_artist(c)
    ax.plot([b[0] for b in best], [b[1] for b in best], 'o');



.. image:: td_note_2020_1_25_0.png


Q10 …
-----

Il est difficile de tomber sur une bonne répartition de tables en
partant du hasard et plus il y aura de tables, plus il faudra de
tirages. On peut aussi chercher à positionner les tables selon un
quadrillage hexagonal en formant une spirale et de chercher le meilleur
écartement. On peut aussi partir d’un tirage puis d’éloigner les deux
tables les plus proches. L’éloigner de combien, c’est une autre
question. C’est la première option et elle ne marche pas très bien.

.. code:: ipython3

    import numpy
    
    def improve_distrib(iter, tables, R, alpha=0.2):
        
        for it in range(iter):
            
            # On cherche la pair la plus proche.
            best = R ** 2
            pair = None
            for i, table in enumerate(tables):
                proche, dist = table_proches(table[0], table[1], tables, R, skip_i=i)
                if dist < best:
                    best = dist
                    pair = i, proche
            
            if it % 50 == 0:
                print(it, "paire", pair, "distance", best)
    
            # On choisit une table.
            if pair[0] == -1:
                i = 1
            elif pair[1] == -1:
                i = 0
            else:
                i = numpy.random.randint(0, 1)
            
            pi = pair[i]
            if pair[1-i] == -1:
                pjp = (0, 0)
                sign = 1
            else:
                pjp = tables[pair[1-i]]
                sign = -1
            
            # On calcule le vecteur entre les deux tables.
            dx, dy = (pjp[0] - tables[pi][0],
                      pjp[1] - tables[pi][1])
            
            # Un peu d'aléa.
            h = numpy.random.uniform(0, alpha)
            dx *= h * sign
            dy *= h * sign
            
            # On bouge la table.
            table = tables[pi]
            tables[pi] = (table[0] + dx, table[1] + dy)
            if distance_bord(tables[pi][0], tables[pi][1], R) < 0:
                # Table hors du cercle
                tables[pi] = (table[0] - dx, table[1] - dy)
    
    
    R = 1
    best_sol, dist = meilleur_table_alea(10, 11, R)
    improve_distrib(351, best_sol, R, alpha=0.5)


.. parsed-literal::
    0 paire (4, 5) distance 0.16110855450954664
    50 paire (4, 6) distance 0.13158100390586172
    100 paire (4, 5) distance 0.2384176552949989
    150 paire (4, 5) distance 0.218691822411302
    200 paire (4, 5) distance 0.19838094003303594
    250 paire (4, 5) distance 0.2162723387696761
    300 paire (4, 10) distance 0.20826241454101815
    350 paire (4, 5) distance 0.2094900548253301


.. code:: ipython3

    fig, ax = plt.subplots(1, 1, figsize=(4, 4))
    ax.set_xlim([-R, R])
    ax.set_ylim([-R, R])
    c = Circle((0, 0), 1, alpha=0.2)
    ax.add_artist(c)
    ax.plot([b[0] for b in best_sol], [b[1] for b in best_sol], 'o');



.. image:: td_note_2020_1_28_0.png


Q10 - Voronoï
-------------

On peut aussi écarter une table de ses voisins les plus proches, voisins
trouvés grâce à un diagramme de Voronoï ou à une triangulation de
`Delaunay <https://fr.wikipedia.org/wiki/Triangulation_de_Delaunay>`__.

.. code:: ipython3

    from scipy.spatial import Voronoi, voronoi_plot_2d, Delaunay
    points = numpy.array(best_sol)
    vor = Voronoi(points)
    dela = Delaunay(points)

.. code:: ipython3

    fig, ax = plt.subplots(1, 1, figsize=(4, 4))
    c = Circle((0, 0), 1, alpha=0.2)
    ax.add_artist(c)
    ax.plot([b[0] for b in best_sol], [b[1] for b in best_sol], 'o')
    voronoi_plot_2d(vor, ax=ax)
    ax.triplot(points[:,0], points[:,1], dela.simplices.copy(), "--", label="Delaunay")
    ax.set_xlim([-R, R])
    ax.set_ylim([-R, R])
    ax.legend();



.. image:: td_note_2020_1_31_0.png


On ajoute le bord.

.. code:: ipython3

    N = 12
    bords = []
    for i in range(0, N + 1):
        bords.append((R * math.cos(i / N * math.pi * 2),
                      R * math.sin(i / N * math.pi * 2)))
    points2 = numpy.vstack([points, bords])

.. code:: ipython3

    fig, ax = plt.subplots(1, 1, figsize=(4, 4))
    c = Circle((0, 0), 1, alpha=0.2)
    ax.add_artist(c)
    ax.plot([b[0] for b in best_sol], [b[1] for b in best_sol], 'o')
    vor2 = Voronoi(points2)
    dela2 = Delaunay(points2)
    voronoi_plot_2d(vor2, ax=ax)
    ax.triplot(points2[:,0], points2[:,1], dela2.simplices.copy(), "--")
    ax.set_xlim([-R, R])
    ax.set_ylim([-R, R]);



.. image:: td_note_2020_1_34_0.png


Le diagramme de Voronoï permet de construire un voisinage de points pour
qu’on peut rapprocher le plus possible d’en ensemble de triangles
équilatéraux ou rapprocher une table le plus possible de sa frontière la
plus éloignée. Après quelques essais, je ne peux pas que ce fut là la
meilleure inspiration.

Q10 - KMeans
------------

Une autre idée consiste à recouvrir la salle de points puis à effectuer
un
`KMeans <https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html>`__
pour créer artificiellement des zones.

.. code:: ipython3

    def points_in_circle(N, R):
        points = numpy.empty(((N+1)**2, 2))    
        pos = 0
        for i in range(0, N + 1):
            for j in range(0, N + 1):
                points[pos, 0] = 1.0 * i / N * R * 2 - R
                points[pos, 1] = 1.0 * j / N * R * 2 - R
                pos += 1
        dist = points[:, 0] ** 2 + points[:, 1] ** 2
        points = points[dist <= R**2, :]
        return points
    
    R = 1
    points = points_in_circle(25, R)
    
    fig, ax = plt.subplots(1, 1, figsize=(4, 4))
    c = Circle((0, 0), R, alpha=0.2)
    ax.add_artist(c)
    ax.plot(points[:, 0], points[:, 1], '.');



.. image:: td_note_2020_1_37_0.png


.. code:: ipython3

    from sklearn.cluster import KMeans
    km = KMeans(n_clusters=11)
    km.fit(points)




.. parsed-literal::
    KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,
           n_clusters=11, n_init=10, n_jobs=None, precompute_distances='auto',
           random_state=None, tol=0.0001, verbose=0)



.. code:: ipython3

    pred = km.predict(points)

Les centres des clusters sont les emplacements des tables cherchées.

.. code:: ipython3

    fig, ax = plt.subplots(1, 2, figsize=(10, 4))
    c = Circle((0, 0), 1, alpha=0.2)
    ax[0].add_artist(c)
    ax[0].set_xlim([-R, R])
    ax[0].set_ylim([-R, R])
    ax[0].scatter(points[:, 0], points[:, 1], c=pred)
    
    c = Circle((0, 0), 1, alpha=0.2)
    ax[1].add_artist(c)
    ax[1].set_xlim([-R, R])
    ax[1].set_ylim([-R, R])
    ax[1].plot(km.cluster_centers_[:, 0], km.cluster_centers_[:, 1], 'o')
    vor2 = Voronoi(km.cluster_centers_)
    voronoi_plot_2d(vor2, ax=ax[1])
    ax[1].set_title("Centres des clusters - KMeans")
    ax[1].set_xlim([-R, R])
    ax[1].set_ylim([-R, R]);



.. image:: td_note_2020_1_41_0.png


.. code:: ipython3

    def distance_n_tables(distrib, R):
        best = R ** 2
        for i, table in enumerate(distrib):
            proche, dist = table_proches(table[0], table[1], distrib, R, skip_i=i)
            if dist < best:
                best = dist
        return best
    
    distance_n_tables(km.cluster_centers_, 1), distance_n_tables(best_sol, 1)




.. parsed-literal::
    (0.22015129672480682, 0.13834146640009876)



On essaye avec un mélange de lois normales.

.. code:: ipython3

    from sklearn.mixture import GaussianMixture
    gau = GaussianMixture(11)
    gau.fit(points)
    pred = gau.predict(points)

.. code:: ipython3

    fig, ax = plt.subplots(1, 2, figsize=(10, 4))
    c = Circle((0, 0), 1, alpha=0.2)
    ax[0].add_artist(c)
    ax[0].set_xlim([-R, R])
    ax[0].set_ylim([-R, R])
    ax[0].scatter(points[:, 0], points[:, 1], c=pred)
    
    c = Circle((0, 0), 1, alpha=0.2)
    ax[1].add_artist(c)
    ax[1].set_xlim([-R, R])
    ax[1].set_ylim([-R, R])
    ax[1].plot(gau.means_[:, 0], gau.means_[:, 1], 'o')
    vor2 = Voronoi(gau.means_)
    voronoi_plot_2d(vor2, ax=ax[1])
    ax[1].set_title("Centres des clusters - gaussian mixture")
    ax[1].set_xlim([-R, R])
    ax[1].set_ylim([-R, R]);



.. image:: td_note_2020_1_45_0.png


.. code:: ipython3

    distance_n_tables(km.cluster_centers_, 1), distance_n_tables(gau.means_, 1)




.. parsed-literal::
    (0.22015129672480682, 0.21874003784217044)