{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.algo - D\u00e9coder du Morse sans espaces\n", "\n", "Le code [Morse](http://fr.wikipedia.org/wiki/Morse_(alphabet)) \u00e9tait utilis\u00e9 au si\u00e8cle dernier pour les transmissions. Chaque lettre est repr\u00e9sent\u00e9e par une s\u00e9quence de points et tirets. Comment d\u00e9coder ce code ? Notion abord\u00e9e : graphe, programmation dynamique, trie."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"data": {"image/png": "iVBORw0KGgoAAAANSUhEUgAAAUoAAAGpCAYAAADr+X8pAAAABmJLR0QA/wD/AP+gvaeTAAAgAElEQVR4nO2dd7gdVbmH35MEQkJAOqFpAgFCRAhSBAFBooAoKMhVwQJKU7qKigJeCzYUxEu5kSJFUVQUAZEoKF0wFEFqIBA6CU0JoaSd3D9+e9+zz5yZNbNnz+zZ5+zf+zz7Ocms+WZ9M7P22qt8BYwxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOMaZ0xwBLgxKoVGcR8DD3DratWpMPoxOfSiTqVwrCqFWgTywPHAbcBLwPzgUeAs4DJFeplimcy8A1gzYr1yMNg1t0MciYBj6NfvhuB7wJfA6YCTwKLKe4X0SPK1hkGLAP05JTfH72DLYpSqI3sT7LurT6XMuiaEeWIqhUomeWAPwKrAXsAV0TKlwKOBJZus16DjaVqfxe2oa5e4I021JOXdj6LRjr9uZhBzDHoF+8rGc9fCzgfmI2m5w8Bx9P35WhkfdQJvwq8CFwAvIX4EeUYNJKdWbvubOAc1IFn4bO1624OnAQ8i740f6ZvmnYM8BiwALgDeEfOe6vXtR1wZq2uXjQtXBY4BY3QFwLzgLuBLxR4v3GjlLpO2wD/03D//4ic9/3aedHP0Tl1Cz2LrDoBrA6cDtxbO+c1tAy0TxO6J43esrzXZnTNqm9IpyHHUB9R7oVe5FkZzl0VuBVYETWmR4D3At9GX4y9G85dHU3jl0ZfumeAPYHLYq47CrgWmFjT415gHeAIYHs0zXol4/2cgRruSaiDPBL4HXAVarRT0Ts9GrgSmAD8p8l7q3MR6oj3RV+6Z4CzgQ+jL9Fdtft/G/D2ku43Tqcr0LMeA/wImIZ+tJ6n7z1/BXUOM2r/n9mibnHPIqtOABsB7wH+gDqyZVGn80tgJOro0nSPo9n3mkXXrPqaIcTLwKMZz/0J6lR3jRw/o3Z8l8i5vQz8Jf09A0eUJwCLgK0i525cO55ltFsfEVxJ/zWqb9aOz0ANv86eteP7Neib9d7qdV0co8crwE9TdG31fkMjynMi525RO35ow7H9SV7na1a30LNoRqdRDFxbHA7cAjycUfe455L1vTajazP6ds2Icqjvei+HOsss7IFGGNMix39U+/vByLnT0a95I6fGXHcf1MD+hRbj65+ZaFT23oz6Qd8XoM4Ntb8XoGlwnWtrfzds0DfrvdX5Rcyxf6Pp27iAjkXeb5SLIv+/E/1gTcwon1e3uGfRjE6v0/+9jUQj0z+hUf+K2dQfQLPvNevzK0vfQctQn3rPQ6ZBaQxD64u/jimbhdYhx0fOvS7m3Psj/+8BNkC/xq8n1P2vDPrVeTLy/1cTjtc7zVE0d2+hugC+BJyHRun3ADejUfQ1tfKi7zfK85H/96K10lEZZFvRLe5ZNKNTD1om+TSywoiuC6+IfoSaIc97zfr8ytB3UDPUO8r70DSrqhfbU/tcDXw94ZzXmrjekiaPt2JKsjjm2K/RaPWDaE1vT+BzwG+Aj1L8/WYly322olvcs2hGp2+hDZapaLnkeTTV3wd1SFXP7KLPr9P1bTtDvaO8FK2fHAj8MHBeL9rJfWtM2Ti0mD0rcu5GMedOirnuo+iXPzpNbxfN3FsWnkObOmej9nMB2uQ4EY0yq77fpB+NKt/Ffmh6/LnI8Y9F/p+kexxFv9dGsurbNQz1X4apqDF9k4EL3qAv+pFodHQ52sGdEjnni7W/jTvaV6CRanRT4MiYOn6JpnwHJOi4SsLxImnm3pIYRv8NI9AoY3rt36Nrf6u+3/qyQ9ySS1W61df4GlkD+ETkWEj3OIp4r3Fk1bdrGOojyrnA7mgR+io0bbwRrd+8GfhA7e87ge8gc6JLkanFo8hEYh+0Dvfnhut+F001rwJORuYiHyJ+k+P7aPfx7Nr1rkNTuQ3QYvz5tXPKpJl7S2I0Wqu7FLgdbZJtABwFPIBsN6H6+70djcxOANZGdqV3IjOXqnS7HM1qfg78FdlsHoF+xFfOqHscRbzXVvQ1Q4wVUOO7A3WeC9C05Fz62wCujb4sc2rnPFyTizM43wB1wK8CLwEXkmxwvgzyNb8HbSS8ATyITG3ipvBR6uYdG0eOb107Hv2lH1E73rgLn/XekuoagYzN/4lGPouAp5D93+qRc1u535B5UFQnateOmr0chDqXhQw0OG9Gt1C9zei0LJrdvFAruwdtlBxdu8aEDLonmeJkea/NPr+s+naNeZAxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOMMcYYY0z3MRr4SNVKGGPKo+gI56uimI+vMzAadpQPobwcdS4mnN2vzroo0C7AjsCxTco0S5rsEcATTV5zR+L1/hF9mROb1SPL9fMQulYrz9WYQUPRHeXLKOXnzQVft5HGL+f1wA8i5XGJpsrsKB+guBwsx9I/iGsWPeLuN+655CV0LXeUpisoOhXEAhTtuxV2RblnHkcjzL3on150L2BLFE38dyi68l3AF4DHULTmz6Moza+j6N+NMkc0XGskig7deO6mKMT+qygk/lYZZD9ekx2JQvDPq/37vJpuJ9f+fx99+UyiTGg4b6eY8xrv4cqG+z0fpZHtQZkmDwDeVXsu10Tu5fyG6+1aq+Ne9Jw/g97fLxKudRcD30ujThcE6jJmUDO8pOt+Ck2lFwTOmYhycdxQ+//e6Iu9CrAScDhK4bACCm9fZz7wIgp3Pw6Fwp+N0hEcAuyGcrt8sXatcSjvSF2mkc/EnLs1Sr/6PdQ5zG9CdiuU9+Q4lLBsFhpt/hJ1QIfW7nG1mt43NVxvbsx5jelTG/WY0HC/e6B84l8BtkXvdFHt+htG7qWRCShh1OHAK7XnNilwrdkMfC/3Nuh0QKAuYwY1VWZhXET/Ee2I2jHoS7P5IsrJnYUZtb8bAu9HI5r30JcdMI64c38G7A/8BXUWzciORx0NqBMBJWM6H424NiA5OVPW8+rU73c8ymkCcDeaDtdJu5eZDX/Hp1wLwu8l63MzZtDRjiyMI1D6zeiU/EGU9AhgafQlfZaBCZCia3DRDrZOPSfyw7Vr1xMm9QA7JMjEnTsMTaXrHdfJTcgejBJU3YlGZ3NQ5/ELNEL8fcz91Ek7L3rf9fudhVKWTkfLBtc1nDM7ci+7R665Se3vprXrzAtcK0pPRKdoXXsS/96NGXQUPaIchr7om6Hc19ujKd5ZMefORB3KTWj6fQpKHZrGPegL/7OE8vPRTu1lwCUoy2KSTNy5BwN/QCO785qUvQgtO/weWK92P9cCh9Xub83AfaWdl6THBcAH0brlWJS4vk70XqKsjKbLh6B3FLpWHI06RetKeu/GGPP/I8EzgM2rVCSFXemfxtUYk0A7pt7dxFJoxxfgGWRTaowxxhhjjIGwq6bdOPs4pGoF2kxXvPuiN3PeBdyCPHN+nHLu1sCpEV2mF6xPu2nVU6UIT5cDkU1q0TS6au5If7fGPG6caeR5FvV7r6otbYeezW4FXW9HsrmPlukh1SkuvGWyIynPueiO8iHUWW6Ldj03akJ2Y2SkPpgpq6NMMilqJyFXzSLdOOu08iyrakvLIBOphW2oK0tHWUS76RQX3jJJddMtejNndsO/55PN3KfO/cjFD7K5Fs5moAveygx0F1wGmayMAp5DJjjRa09BHieLkU3nZcgO8BHkJROnzxTCLn1prpJp8o1uinFumY1fxjHInfNlNBU6P6HODyKPmnPQ6OuF2j1vD3wVuArYD9mzxuled9UMlZXxLEPukXH33tiW9o655zdi6uuN0avxGe+a4b4OqF33dWSDmudZxHWycec1Pp/h5Gs3g8mFN+t7bHR3LsxNtywXxm2AdwOnB85ZG/3y1231eukzos7iWhjngncVA90A9wGeRg3m8oRrzwfWQi/87ehLdyRqGL9BnUecTMilr5GkOkPyjW6KcW6Z9zVc/9O1Z3IcMq5/tPa8ojJL0A/HnbX7fK32TPZDXkZ/Rr+uabq/it7fBm16liH3yLh7v5e+tjQp5p4XxdS3fcoznpDzvpqVaaxzXOA5N7rlJrm3prWbweTCm/U9Nro7F+amW4Z50Fi01vChFq6xIfIFfwcaMfwRGTWfhAJAfLN2XqML3h5oRPkD9GtRdwNcHxmEh649F00hAJ6nrzG9ACwXkIm69M1p4n6yyM8IyDcyHjVukOthkswrCfqdjYzFPxtTFqq7Xc8y+u4bo1PF3XsjS2KOEVNf2jMm5301KxNH3Hkhj6es7Sbr9yyrTo3votGFN/qdjCPuvBcayrO+xyjRPmIe/dvLuvT/8Yhth0V3lEujX4TDUcOo19GsK1sW18IzGOiCtz8D3QAfQlOH+jpK3LV3CejSk1Em6tKXdj9Z5ENumY3MQp5Ad9b+PpcgsxNqzKAG8gJ6rl8Dvou+HN/JoPsOTdxX9B7zPIuQK2bcvTfyHwbec1a9spL1vvLWmeaWm7fdDCYX3qzvMUohbrpFb+Z8Cngr8EP6XBlDrmx71c67Bnhfw/HzSXcthIEueHFugBeiNYjL0cgp7tppZJVpxt2xSPmLgI+iRr1xQOam2rEzUGMBOAqt8f0QeRJNbKLurPfVzL3UCblHNhJ3743E3XMrehUpn1Um7rzG55O33cSVd6oLb9b3GKUoN91Bi13wjOk8OsmFt7A+wi6MxpiisAuvMcYYY4wxxnQNXeF/bNpH0bveGyGD5RvRVn/o+vb1Ll4eivf13pHq/Y1D9cbhFMKmUMrw9d4BWeUvQJ1hVuzr3dm+3nG0y984VG8cTiFsCqXoXe9G3+5RxBuFJmFf78709Q7dQ15/4+i7PD+lnk71P3YK4S6hDF/vXYBfI1/MMwPn2dd7cPh6j6N4f+Pou0x7Vp3qf+wUwl1CGelq/wxsgRrkB3JeI2sa2Wi61biUr+sDt6VcG9J9cuNksqbVzSufNQXveOBftX/fHZBJ8pc9G42gL8hxD0mEdA+ltnUK4b6/41OuBU4h3BaKnnovRd+U8GXk421f78Ht6x26h7z+xtF32egiNpj8j51CuEsoekT5XtSobkAv91Ls690O+TJ9vUM65PU3DvluZzm/U/yPnULYdDz29TZZ6ST/4xBu0x2Kfb3NUMf+x8YYY4wxJozdFU3plGEeBLJZTPOMsAtj8fJQXrraZijSO6RT3BXz0uqz2BG7K1ZOGR3lSGByDjm7MA4+F8Yk2tlRdnq61Fafhd0VO4AyNnM+DfwcOLFJObswdqYLY1qa1mUZ6GKX1Y1uMLkrbhHR61cxuk9hYJtMahN2VxxEFO3COAI4Bv0CHkif4W8cdmEcHC6MaWlaD2Cgi919ZHOjG0zuitH7SHqn0Tb5twT97a44iCh66r0vfakgW8EujKJTXBhDzybNxW6ouCtG9Up6J9E2GcLuioOEoqfeE9EU5cDav48GTscujEPBhTGOHuLd9bKmmh1M7orR+/hjTP27MLBNJrUJYs61u2KHUnRH+bWGf9+KdrUnovXKuJ3YvehzuTsZTZ1BL/pc9KVaiKYTW6GGOII+l7G6u9dKwH+h0eNX0TSm0YXx58i9cg6aukSvnUacPnHcgzqaDdDUrBX5xpF5nHyj4fRFtXO2Rs/zlgSZm9ASxHjgzegLWXdhPAt1EBNRB5CVC9CUdS800pmGRjv1+7iNge8tdF/R99zMM72odi8fRiO8a5AbYrRNxJF23sERva6MqR8GtslhCfrHnbuQgc/yXQGdG59N9DlPIPl7Z7oIu3uZOKp0V2ymTbr9DiLswmiGEnZXNMYYY4wxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOM6TLWARYDTwLDK9bFDD2uAy6JOb4xsATYrq3amK5mRAuyBwL3A+OB3YArmpBdCuhFHW0aPcAKTWuXzhLgPyVc13QOzbSzKKOA1zOeuzSwbI460lgAvFrCdU2bGI5GkgcCZ5O9k1wf+AvwBmoAvwfWSpF5E+rUiv64k+xsriP/iDJPO6vzX8AM1ME+C5xA+oBiX8ppoxdl1Nl0KLsDc9Gv6ObAImDtFJlVUMOLNoaH0K93Eu4ou5PryNdR5m1nAHvGyC0BTkmRc0c5xBmWU+5g9BJfBe4A/gkckCJzKDA25vj6GWSNyUor7eybCcePIvuI1AxB8nSUawPvA37acOx/USMMXW9SoOytOfQwJo687WwYsFGgbGJujcygJ89mzgFojfL2yPHhqAO9MkFuVuCaT+bQwwxt5hM/VR5d+/tGglzedtYLPAZMSCh/IiBrTD+GoQbzLbRW1Pj5DXBZQHY9YB4D12HmoHWlJLxG2Z38D1prXCpy/Ai0Jp5kCZG3nQEcHiO3BPhtipzXKE0/3o9+eeM2bnZDDXjNgPxO6Fe73hDuB7ZIqdMdZXcyCZnn/BbYBk2L9wNeQpYWIfK0M5Ap2gloNNvYWb0pRc4d5RCnp8nzLwNWBd4ZU7YU+tX+MfDtwDVGAJsAC4H7UMcbYgSwY5N6ZmER2lk1ncs7gW8A70BT7idQ53EisjEM0Ww7a2RFYEPgabItC41Fs6qimQ3cW8J1jTHGGGOMMcYYY4wxxgxhptJ/V+4N4E7kH2tMUVwGTE8oG40sFk5onzrGNMdU4AHkpTAR2BI4F+0olrHrZ7qT96Mf4rfFlO1PuhmaMYWSxzNnPvBgw/8fBj6D3MNCpgy7Am/OUV8a00j3mhiGTE3WQ5Fh/oG+iFlZC5mZPNekbpujL/tjwM21a5h0rkJmOQcBR0bKDkLeX8+kXGMtYFvUqd5Ec+/u7ci06HH03tJMkeqMrtW5BoqBcF8GmSq/F6YkpgJ3Nfx/aeALaAo+LkX2j5RjlPv+lHpXB26MyFwDrJQiB7A1Mlauy91GtpHzKOB3kTrvAtbNIGvEfwMvAiMbjk0i2zs/FBmr15/9y8BHMtTZynvbFJgZkT2b9KDWVX0vTIlMRdPsN2qfxcArwF4ZZKtqEJcmyP08Re7N6AsWlXsaGSSH+GFCnX+neSP/bmVtNBrct+HYj9EoKRR8ZZuaXPTZvw5skFLnSTFyWd7bSDRTiZP9Ykqd7iiHINE1ysnAsci39t0pslU0iDGoM4+TWwQsH5D9dqDOr6Tc6zMB2U1SZE0fVwDX1v49EngBjTRDnErys/9OiuzTAdnJAbltA3IPp9TpjnIQUMQa5V3AzqjzuDZWojpWJXn0MRx1pHMTyjcMXHdcoGw44Wn9yoEy05+z0A74BGArFAjj3BSZVQNlIZ/tVt5bqM4y0piYNpM3cG+UHmC5gq5VJLOQv2wcj6HoNEmEFuIfCpQtJtm05VVkTmWy8Sc0yjsAbeJcBTyVInNroOyWQNlitAYdRz1AdRK3k5yX5+8BOTNEiU69N0VT717Sp6NVTTH2ZuD0exGKnRliLJrqRet7FI1EQ2yF1nCjsoelyJmBfBP4N3p+u2c4fyRwNwOf/d9IHxhsSf739q0YuZeRpUUIT70HAXmm3hNRZwnqcB4FvoY2MELMrp1bNK+llF+Cwm6dgDJGzgS+jkyEQsxGUYvOQdFrQLvlh6A12RDTUVivE5F50DPAD9CXwjTHOcDxaCT5pwznz0f5dP4bhf7rRaHavk96BKHbkEnXd+h7byeRLXne19FM4wg0hb8dfS9mpchV9b0wpnBWJZs5kTHGGGOMMcYYY4wxxhhjTOWsgHYF70duYfOQfdrBpPu1GhPiYBQ4JGqTex8y21kmcvwRlK3RmI5iNeSS9TgKPLAlMp05HHnrbFedamYIsB4DbQDXQGZoTwFTGo6/pXbuHm3TznQtzdpRnor8ozelv8fLP1CklLiE9Y2yZXSkR6MwWiGmAB9HkYRuQ8EVXk6RqVLfbYBPA+sA/wROQcbvQ51H0I/wTiiUGrV/34mMyKcAf60dn4IcCa6Puc4INDp9Dxqh/gm4EHWsSYyhnKyc8whnEa2ynZkSGI2MeUOpaENU5YFwJDI0bpR5DFilQ/X9FAOj38yhnJiFnci56Mehzs+Qsfi+9HcS+AXx7orDgasZ+NzTcmRXlT/enjmDgGZ8vceh+JN3l6NKKayJPCuiIbLeUjveaSwHnM7Atd7V0MijG/grmrHUg1DshIKtXIsC6tYDW7ybvtFlI/uhkWSUfcnmAmnMAJrpKAdjHMWt6R/4tZGd26lIRt5OcnCRTtS3DP6K2tq70ZrlmmgK+Syamu8AbFQ7HtdR7hC4drc8Q1MwzaxRzkIh8TdF/tODgZBP9qtt0yI7If/cN9qmRbXMQSlFdkJuo9Ppe1fXorXJdZDFxc0x8qH3av9nk4tmRpSvoWjhB6GpYJSlCMf7q4JbSQ6zlrZmVQV3kxxEoRP1LYu/oo5yCv1jnNY7yp1QJzk/RvbyhGsuBn5doI7GJDIWTX8eRR3mZijaymeRrVto966qRev3Ai9FZK5E660hqtJ3G9S5N8pcT3pot6HE7ui+59I/cv5qaGPuFRTeL4kT6b+BtxDtAofwZo5JpFnzoNkofNiXUS6QcWiH9l/ATwgHTb2EcJbGvDySUn41Sgj2UbRB8A/6GmeIqvS9BWW0/Dj6YfonSniVFiJsKHE9aldL0z/Y7nPI0eGtxK9P1jkejSx3q13nD6S/y/koFF7RpC2ZVNXOjDHGGGOMMcYYY4wxxhhjjOlOptJnfrAIeBGl4zyOzrOhNIOXHrSrfQP9bX17gGmozTmkn2kbebIwPgjsiRrtiijM2udRtJbtgScS5MaiwBpFM5tsHhfDgWWRbZ7pbJYA+yOzsy/RZ7ZzBLAtMJnkPNpVt7NhyA01LTpVHKPRfcUZ0sfVMy5HHWn0oqAxpgWmAnfFHF8Npfa8NCBblWHtisD5yLWtlz73uCysBpyHOv9HgNNQmDnTHvZBncZkYBJyWzwgRaaqdrYscAYyhl+CUtdmjZW5MRo9L0JuwleR3glWZSBvMpDUUYIS1S8g+de8igZcn8JFZRYgj6IQY1AO8KjsbeQbiZt8/Ar9uN1J+Ie4TlUd5SUxMr309yyKY3Xg+RjZRwh7Y7mjbCPN+HqncQ/y9167wGu2ynbEjx6XQh17iM+h6DVRtkBBdU17OAy9h/HIbbYTmQR8OOZ4D0qbEuKzxMdGXZfOvd+uo8iOsh6GbUmB12yViTnLQCHPktgshy4mH59EbWp5NAXvRDYKlKW1s0mBsg1y6GJKoMgp5NvQlPapAq/ZKiF/11kpsk8Hyubk0MU0zyQU3fww9ON0HmpnnTY9fDRQluZz/XCg7LHmVTGdQGgz51kUvCGJKtaORqAgGHFrRzuk3OsmaCMhKjuX7knLUCVLo4Ag9XXJUcjiIi3cXFVr4X9JkPtgir5vQW0qKvcsiseZhNcoO5ipwANoOrERCgn2ebQrPAsFVE2iqkX2tVFyqfr5c4CPZLzfj9I/RNuzwC4ZZU1rfB+Z5KzacGxLFDIt9P6qamer0H9D59/AZ7LcKPBOtEtel/0n+qEO4Y6yjTSb3mEqcEjt34vRL+EM1DhPI2yjOIFyjNJnks1mbW1kKjQDLRFkZUVku7cYuJFw1HRTDNujjIgfAq6IlH0D2VNujH64olTdzsaiGdZDNBeVfhhak1xMeDpeZzjlrNkuJtmyxRhjjDHGGGOMMcYYY8wgoDF6UPRjtz5TFL9DO7/RBHDrIl/qI9qukTFNMBXZsm0c8zGmKFZGBv8/bDg2HIVXm0bz1hrGtESeUeAbtJY1bjwy/1iEsu2FPGBMd/IiCrN2Ve3zN+CrwPrIvnBJQHZv4n30W+US0r1slgN2BNYA7qh90qhC30koJXDR3M9Ac66uJBQ9KAtH0d/bZR7y5TUmjlOAJ1Fu9gXIrjKNqgzON0cuh40yPyd9MFKFvvuWVGea11TXkLRGeXsG2e3on5S+/nmDcGAA072MRMF7FwPnZJSpouMZRXxIviXAsR2orzvKJskTPeghFKCg8bNvBrn/In5taSTwiRx6mKHPfOB7qJ1+o1pVgmxB8vQ5LdCwGQTkWaN8nXzT77iYe3UcNdwksbD2d1GlWoRJC15hBjlFxqNM4+ZA2Y1t08KY4rmNvg49yg3tVMSUQ56OchRyxo9+ojZvUc5BDSrKNOA3OfQwplN4hviI+S+h5GhmkJNn6r0BMgaOsj5a0E5iAYoBeRxaaF6ETBhORgvBxhTBbMKBdPOSloHxO8jG+DAUQegfwPGkm79Voe+8kup8roRrGmOMMcYYY4wxxhhjjDHGGFM8SW6Mn61SKTPk2IJ0lzmH9jNtIW9Dm4GinjTiKECmSO5FObyjvAX4LYpZ2cneOmYIkbejzBtqbSngSOA9yJPhT8BZKFhGGusg491NUZSWqcAtKTK7Aifm0DONachGLkQefU0fcW1seeBXKHxZkg/1qSgAS9EcDdyUUDZY29kuwH4oLNztwEnA83kUNQPJG2ptOIo/GZ0+/T6D7FtRvuFGucXAx1PkqoqSkldfk8wI1HE8jAL7JtFN0XhaaWdHMzCa17PAWhlkTQbi1iiz5C8+OEau/tkzRfbPCXIvAWMCclU14Lz6mmTORM9vg5TzuqmjzNvOxqLvbJzsr1Lq7EryBsWIhlrbKoPM9oGynQJlw0ieSq0IbJmh7nYy2PQdDHweOBDYC7U901o72xKFN4xjSitKDVXyrlHmCbX2cqAs5Jfai3xTRyeUv9KkHmUz2PTtdPYAfoTWJK+rVpWOopV2Fiqbl1ujIUw7w6z9Hg3toywkfbiftI55D/EBOqpmsOnbqWwG/BL4AXB+tap0JHnb2XSUYiOOC1vSyPw/reTN+Toy6Whc28xif7kcGk00rqU8ihJNhahq7SivvqaPNYGnUGi+zYgP7bdMjFw3rVG20s62RZGLGmUvJz1cYleSJ+3nVGBr1FDzsAmwGxpJXo52MbMwDE3DNkFfoN+QPk2YDHwsn5pB7gIuTjknj76mj0+g5Fwh3sZAE6L9gYkl6HM+CqMWx2BtZykxQi0AAB8ZSURBVCsje+jV0Cjzz/nUNMYYY4wxxhhjjDHGGNNpvAn4FjJBeBXZVN6L/ETXrlAvY4wphWZ3vVdHqWVHIiPg21DSsHWQg/3SyIPCGGOGDM12lL8CdkSRSuIyrg1HTvlxjCXZi6AVZpPs2TMGmT4UzTyyZ5xbs3auQ4IZ0wWMBuYTn784C91kCAwKAvJc7fxXgR+jnOjGmEFGMy6M49DU+p7I8ZvQaGkRGt0Z+BTwU2DV2v9Ho7BW/1OZRsaY3BTh6/0p5JlwGg7NX+fYhOMHoB8cY8wgopmO8jG0cRMNz/8o2vWeU5BOg51hwPoJZT3Aem3UxRhTAM10lK8BlwIHAauUo86QoBeYGSh/tF2KGGOKodmp99HIbnI6ivqzORphfhhFKZ9fqHaDlx8kHP8ZMKudihhjqmEFlEjpXtRpvg7cD5wCvDkg12273oehYMVLUKSk0yjHPMoYUzJ5wqzlZQLy6imamSRHT18JGF9CnS+RbWS4DDLGfx4lgTLGGGOMMcYYY4wxxhhjjCmVpMRiY9Du7v5t1cYYY9pAO9PVGmPMoKQK3+wNUai2RcDfyG6A3QPshLLNPY4yxr2aUXYFYGdgDeAOFMgjK3n1NcZ0Ka1Ovb+KjK/rhtuvky3Q73LAX+lv9D0TmJRBdhvgmYjsJcBSGWTz6muM6WKmEvZY2T8g+27kBx2ViQu0EeX0hPr+SXj5YBQK5hEn+/WUOlvR1xgzhMizRvkQsFnk884McnsS7wm0FHI1DLF3wvHJwNsDclsBb0ko2z+lzlb0NcYMIfKsUb7OwOn3mAxyKwbKQvLD0NQ7iVBZyGUyTee8+hpjhhjt3PUObaBcFyjrBW5JKHsZuD0gOx1NleO4NiAH+fU1xnQ5rWzmjAD+zsA1v8tID86xMTA3IrcYRVdP40sxdT5HemrdVvQ1xnQxre56jwSOA25GaW+PRJkbszAOOA+NIC8H3pVRDhSKbRoaYZ6J0u5moRV9jTHGGGOMMcYYY4wxxhhjjDHGdDJJO+DGGDOkcJg1Y4xJod0d5TLILvFa4C8oT3hWN8r1gLOBfwC/RkErjDGmo2l26r0UcCsDPV2uIN3T5W3AvIhcL/Dp5lQ2xpj20mxH+TmSw7N9NEX2bwlycyknV7gxxvw/7Zx6bxso2z5QNgzYOqFsOcJh1owxpmXa2VG+FCibGyjrTSl/OZ86xhiTjXZ2lJeg6XKUBcBFKbK/Tjh+JzZRMsZ0MHnsKI9BHWN9jfE14DMZ5MagZGKN65MzgIlN1m+MMU3TSlzFqWjtcHKTchsCu6CshleijIpZ6AHeC2wKPIniQr7eZN3GGGOMMcYYY4wxxhhjjDHGGGOMQ6wZY7qIrJF7imYNYCHwQoZzh9O8CVIWFhPu7CdQjh/5TJK9iVYCxpdQ50vArBKua4wJkHdEuTVwP31G49OBSSkybyI5mEYrn/+k1PvHkup9f6DOfUuqM83zyRgToJ0ujOug3NobNRzbErgaWLGNehhjTFO0s6M8mPip7JrAQW3UwxhjmqKdHeUGgbIy1uWMMaYQ2tlRPhAoe7htWhhjTJO0s6OcSnxMylkoF44xxnQk7ewoZ6OEYLc1HLsWRQR6pY16GGNMU+QNs/ZTtGOdNw3DasiO8cUM5w4DxuWsJ0Qv8FigfCwwuoR6Z6M4nHGMQc+maOYBz5VwXWNMgMtQulljjDER1gM+AbwBfLliXYwxpiO5Gm3InAWMrFgXY4wxxhgzGInz8X4rymEzDW1GGFMk26I18SeR3/rx1apjupFWzYO2BW5EZj67o91VY4pkDAqk8gWcw91URCth1j4E/Ao4DfgK8Tm7G9mfctLLng88mHLOqsBuyK/8drTWmsb+VKev6ePPtQ/A/2aU6UGRmKagcH5/QqPSEMsCf8ijYAqvou9KEjfRP1BMUXwJ+FlC2U7AV0uo82/A9xLKqnq+lVCfeh+CGuBRTchWEbYM4F3AnIjMlaRvRlWlr0nmBdKn3j3A7xn43M9IkasqnF+0bRb1+UagzirC+VX1fAshz9R7I9Rhfhn4SbHqFM6y6OVFjbh3A45rvzqmDewL7Blz/FCUT96YpsnTUT6Fpq9HIbvKTmYrYO2Esk+0UxHTNqYEynZrmxZmSJGno3wFNcangBsoZ32lKEK78GW4J5rqWRQoW9g2LcyQIu+u91w0jXkAuB7YtDCNiuUfyIsojr+2UxHTNv6YcHwJ8Lt2KmKGDq2YB70KfADlvbkWBcnoNJ5Da6lLIsefQbuCpvMZjZLLTUaJ5sbW/p0UCPpy4MzIsSXAN4FbStLRDHFazcL4Blo4/yVwDdrRvSnh3JnAHS3WF0eabd1pyA7vUPQl+wdwIvGxMRupSl/Tn03o38EdVvvcAWyRIHMYcCn6IV+ERpJpneQC5JpbNK+nlF8PbFxCvf8KlM2knHudHiir6vkaY4wxxhhjjDHGGGOMMaZEDkWbg6+gjcPpdKBfrzFxxIVaM6YMrgG+BuxQ+1yEch29p0qlTPfRqnmQMWUS7RBvALZDJmnXZJAfjjrWqB1tFoajBHhZWBrFFSiaBcheOY4eYIUS6kwLNDEGWKqEeufRwZ5T7e4oR6MRwnvoC391MmoQSSxHOSPYV5Dhcog8+taZiAJvbIqyPZ6Jghub/AwHlgGeTzlvPLKf3QF1dtNQbII5GerYA9nZTkJuumeidx7qNPcmHDknL78EPp5QtjzptsB5eJlwB3wx5UTA+gCK6jVkyDv1XhoZCUfDJF1NOG1uVeGZ8uoLSuP7WozsISlyJsyJqJNcPXDOSsDTDHz296NONsTuMXJLgJNS5LopbJnDD2Ykb0d5GMkPaZ+AXFUNIq++ANclyL1Sux/TPF9AMQa2TTnvOJLf22EpsnclyC1CQZ+TcEc5xDvKVlNBNMM7A2Vpjb8K8uo7DHhHQtkYkt3uTDL/DXwdBWK5OeXctwXKQq6Cw1D+pziG09lRskzJtLOjfCFQNrdtWmQnr769wL8D5S/mU6cr6QFOAY5A6QuyBLV4LFD2VKCsF3g8UP5khrrNEKWdHeWvUWOMMh/4eRv1yEor+v4q4fh0wsEKTH9+imwpj0bvoh5FaHxA5lziAyW8UCsLkZQu4lLgoRRZY/oxFZhBX6Otf5KmLY0ciQyH6+sSc9H6Togqc23k0RdgFEpm1VjfPSSHBjPxzCP+3aUlqdqF/hs6DwNbZ6hvGNowWtggewmwcoqc1yiH+Bpl2u5tHFOJ372dg8KYpTEe2Bk1xmkoNmSIkWhEUTTzgVMznNesvo3siNbMnkKmD1nMikwxjAQ2Q2Y9/yQc+TzKasg86Ang0Qznj6WcUGmzgXsTykag9lU0i9BmZBKTgVVKqPcuwstdxhhjjDHGGGOMMcYYY4zpQD6FcsjPRZtpDwFfpb1mbcY0xVS0jR/nuP6RWllSalhj8vBfwH7IS+odwLGowzy2SqVM99GMedBUFOFjNWBd+ns5XI1sBFcnOfDABMrxc55JcmbDlQgbJ+flJWBWCdc16fwFGZR/MOW8Sci+cSFwIc29rw8CU5Dt68/JPgBYHvgksD5wBdlyxx8PbNiEblk5A7g1oWwKsH8Jdd6FIi11NVPRg58GnNBwfF1kk/htwg2qCkPVKgyBTTkMQ7EoXwIOTDn3fPq/r17g+xnqWB51qI2y8wj7/df5EP2dE5YAd5MeynAO5bTRbwTqPL2kOofs4CHPWs85wGfoG40egOI0Zon1Z0yzrIWMoOuG0D9EbTCJT6LpeiM9wFfQSCrENGBc5NiywFWEvyvLoziNIyPHN0GusGaQk6ejvAwFtH0P+rX8NHB2kUoZ08Ac5A2yJfAlFEbt8MD5IS+ub6TUtVXC8eUJ5+r5KAM7yTofSKnTDALyRDivr/kcgDrMegTpQwvUy5g6i+hz47sDrZEfh6aPcYTc60KRu0egcGpJhNa610u5rhnk5DWzOAf9wn4JOI/4KDvGlMHSKeV3Bsr+HihbhAIrJxEKxBEqs//yECBvRzkDhQzbhvTQVcbk5RSUj2YLFCz5BDTtPj8gcwDaXIwyF8W1DPHFhON/AB4JyN1K8g5zdL3UDEJaMdzdFViVcLBTY1phGNqt/jvKurg3sqE8LiDzEjLP+RcaJS5Endh40qM3nQ18DI0Ce1EGxJNR1sc0tgUuQKZLi1GUqZ1JTygX3Skv6hP3Y1F2nUPWjrpZO8rJJMf1Oxz4Ecl2lGPRmmbRzEaJvOIYg9a0imYe8FwJ1zXGGGOMMcYYY4wxxhhjjGmJegShMyPHV6gdD3kvGNMKH0ZtLCmHjDGlkcc86A3gIGBiwboYk8R44DTgb1UrYrqTPO5VdyNznB+QHuqqkcNRRsKiOR2FwwqxJrAHsAYKBFuPZGQ6n6VQYIlvoCATq2eQGYYCt0xBdpRXkZxrPcqqyDB9E2QjfC7Zc7FvjYIN19vZacjQvQx9lyU9bW8eXsUzw5aph1p7OzLI3aF2PMvUu6p8wO9BRsiNMn9FubdN53MK8Nvav08nferdg4JLR9vJ+RnqWo+BYc/mk21AcBAyNG+UfZR0O968+laZ796kUO8oQQFNb0MvulM7yjHAswlyWeITmmrZHXiMvmAWWTrK/UluK+9Lkb0iQe55wj+sqyInhDjZ80rS1x1lG2nFhfE4lPR9n4J0KYN3II+gODpZb6M4lOcAH6e5L++OgbJdA2XDArKrkByCDRQCbtmEsrTOOalOCOtr2kgrHeUTwE+A75Ici69qktwpoXN1NmIzNG29nr7AvYcCb639e48EuZC/8cJAWS/p/tFJhORCZWnXDelr2kir2ey+h35JjypAlzKYTrIfeFqwAlMt16PNv8kNn4tRjqTJwLUJcpcnHF9MerTxKxKOP4xiYSYxHcUciOPilDpb0dd0KI1rlHWOQJ1RJ65RAhzMwEX2xyknWIYplyxrlKCIP730ve9FwJczyK2E4lk2tpXZaGqdxs5oiaBR9jqybRrm0ddrlG2kiOjLU1FnuX7KeXdRznQ3LTDqWcB9aNq2CtqAOolsZhtmcPJFZDrzftTp/J5wQN86L6F17U+g9fdn0O7zixlk/4KWBT6JNnemo936LEGt8+i7ALXtonm9hGsaY4wxxhhjjDHGGGOMMWaIcgzxO7NJTgTGlEIeO8pVgFOBWWjn7XngEmDTAvUyps4sZE/Z+HEKWNPRrIF8bx8G9kURVnZGTv2vowAUxhTFMcCDLcgvTX4TuFaCpuRNoleVvqZgLkbRVaLG2j3An4CnSLaVvBjZqRX92Tmg794l1RmyX1u+pDofC9Q5VDkGufjNRT/Et5DuYACwIXA1ch98DbgUWCdjnR8BHkJT/DnAf6NQb2mMQobjLyEHh3vI7qtdhb6mJEajF3liQvn26GXtklBehWfOviXVeVGgTntMFMfOwH4oIMUUZMC9mPCP4yrImyb6/B4iOXBFnb1i5JagpaY0Lo6RWwxslyJXlb6mJCahl7B3QvlytfIjE8rdUbqjbJUe5EIb8tP/OsnP8IiU6/8rQW4xsHZAbmKgzptS6qxCX9MkrQbFMKadLEGugW8OnDMpZ9kwYKNA2YYB2Y1z1plWXpa+pkma6SgfQ7vcSbvb9eMzWlHImBS2AJ4MlD8aKHsiUNaLdtjzyIbqfCxQliZblr6mZC5G6ymrRI73oBBVT5O8meOpt6fezXIa2qzYAtgJtb9eYLeAzLrAKwx8fnMY2G6jHBYjt4T0UGk9KOxbnGzSUlWV+pqSqZsHPYga8EbAu4HL0K7kewOy7ijdUTbLT1F7W4hSLdwIfCCD3I5otFV/dvcCm2eQ6wG+hjYt67I/R+80jdXpn0riFeBzGeSq0tc0QU8OmVWB41HCpTWR6cb1wLdRKLUkdiW8tpSXaSRPMyagkUjRzCQ5derSKA9K0SwgW4IsI4Yj4/SFwANkC3dW500obOCzaJbUDOOBlWt1vtqEXFX6GmOMMcYYY4wxxhhjjDHGtMSqyLd+NtromIlzspsOZyp9Zgi9KMTaL3F8QFMOyyMHhhtQHu/NkXnQu6tUynQfeUI6PQjsiUyLJgFnoGgn22SUHw5sgLLNzUSdbpqOO+bQM41FKJ1oEpNJN/jNw11ki6e4Ru1zP4qg0418Cb3/ncn+DPYG1itBl0uAR1LOGY2CYKyB8oBnSa1bZ23gnchP+0bguSZkt0BulE8g3/IFGeVa0dcEmMpAW8mjUWeXZVT5XhSKrT4qnUF6zuSqDLirykO+BrINrZ//GnBUisxQ5T7U5i5AKWOfRrm9Q1F1qnpvm9L3w1//nIMGBmkcihw26nIvAx/LIDcK+F2kzrvI9kPRir4mhbiO8mD0kNOMyScg74poA3yegfEtG+mmjnIYmmbGyX00Rd+hyBuoAzkT2AyFFZuDRndJVPHeRtIXEzL6OSblHrdBs5uo3Oto5hXipIQ6byXsTNKKviYD0Y5yQ/SrPzOD7PdIboTHBeS6qaN8e0Dunyn6DkXmo6Wexi/9Z9DzWD1Bpor3tl1A7uGUezw1IPudFNmnA7KTS9K3K8kTZm1T9Au4GDXixaQ7/oNcu5Jw7DwRekZvaZsWncOzyJ1vScOx+2t/12q/OomE1rJXSJFdNVAW8tkeBqwUKF85UNaKvl1Jno5yBvq1ehtaT9uEsI93ndBC8X059BiKhJ5RNy6038jA6Wc9zmIn+TTfjgYMcdycIntroOyWQFkvcFtC2atocyaJVvQ1GYhbo8zKSmiEEB3qP0A4MVI3Tb0BfhEjs4jsVgVDiU3R9PuHaI27vhn464BMVe/tmzEyL5O+sTISuDtG9q+kB63ZAq3jRmUPS5FrRV+TgVY6StBLuAr9mi0EfoNGpSG6raNcBq3nzq2dfw/dbTc4BY2c5iOTmdMIZzk8B5nxFP3J8g4+jkaBDyP74nEZ73FZ9GNwP0rv8HUUhSoLk5B53kwUxStLGLo6efXtOpoNszYV2JrwQnEWRqKpw8IM5/ZQzrpJWmc5hnKy2c0j+32PprlQXcYYY4wxxhhjjDHGGGOK417iN8RsFG06nlWQN8Es5Hz/PHIpS0pja0xeJqBgD/XP29Fm2HerVMqYNOpZGB9GGQ43QZFdrkS+qe+pTDPTDeyDTMvGVayH6TKaNQ+6GNmTvY3+YaB6UGe5CbKVnB8je3hNrmhOR7aGcWwFHFBCndOBc1POGYkCWWyCflx+iwI6hKhS38HA9Sia0vsC55yKfJmL5mgUwiyOXYETS6hzGsp4GmIN4Avou/U4CnIc8spp5N3AJ2vXuB04Bfh3BrkRwGeRjetC4E8owtOSjPUOaUajDjCpQWyPHtQuCeXdktcbtDxxT0TmeRRvMERV+g4GJqJ7+VDKed3UzjZA4ecaZRaSLdLUociWuVH2KdLDJQ4HronR9ZcZ6hy0NOPrPQ55CyR55txd+7thQnk38WO0ptbIKsCFlGPE3g0cgvy7r6hakQ7iJwwMjDEChaUbE5BbDTiZgTPKtYAfpdS5HxpJRtkH+GCK7KAlT1CMJOoJ25udzg9Fdks4vh5KZ2CaYxn0BT2X5GAO3cYwNIuLYyXC7Wwr9EzjSNtn2CFQNmT3KJrpKB9Du9ybJJTXd70fbEWhIcAwwqNGjyib5yMof845VSvSQfSi9dokXg+Uhdxi01JuhGRD+gxqmukoX0PO9wcSHwfvy2hqdG0Beg1meoG/JZTNRovmpjkOQRsGT1atSIfxh4Tj9xHe0LkNeCahLG1d9NKE44sJR3Ua1DQ79f48GlXeiMLyr4+G/79DZkL7kT2x0VDm8yikXCNvAAcR/qU3A9kYbYL9tGpFOpCvMDBm5VNoJzu0RDEPbUBFk9xNA76VUufVaEO3t+HYQpRC4s4U2UFLs1kYn0XJwI5HpgRro12wZ1BsvFAA3ruQyUzRhDIazkY7dEWTFkR3FvqCH4PMNp5E4cEeSJGrSt9O5l6aW/e+hHLuN5SB8X7gByXUmRbS8N9ooLI3WhJ7EvgViiuZxvXAW9EmzCpolHkF2Ux8TgAuR2ZRvWiUeX9QwvA+NEo6oWpFjDGmDIrY9b4KTbuHkZ6J0RhjjDHGGGOMMcZ0DMsgD5Kn0M7qHOBsnFLVdDhT6fPt7EW7blfhEGumHE5GSdb2Ra6xH0S2ukPWXs90Js2aB4E8b/ZEJhtro+xx09BGTpakWcZkZQtkaF4PuDAD2VR+OCAzlnCWxrzMJtnzZAzyny6aefSP0tXIMMoJN9eLvPCyMAalUk7z5oljZeAlhmjEobh0tZ9GN/uWDPIrIYf9h5DN5Q9Rqs4Qy6MHWvTnsZL0NcXxRTSCrLvNrodsJE8OyHRL9KCq0jiDbIRvRp3kQuDPwPgMciCnlKdrdb0MfJ9kv/NBS7SjHItGk0+QPjodjUaj0RdzKzJaT6KqBpFXX1Ms36QvtfESFG8xZIDujrLc78VYFDIwKvco4YhFAB9LqPPMFLnKyWNHuSn6JVmEPHVWBXaq/T/E54gPwfYO5HLVaQw2fYciX0ABnz+BPJw+hLxB0kKBmfI4BHnyRBmPXHRDJDmlfJYOt8HO01HOACajUE3Ho2nR+hnkQmGftsyhR9kMNn2HGj1oNHkyWqN8ELgMfdk+D6xYnWpdzVsDZRsEyoYFynvI1odURp7NnDfo86W9E/2S/C96CKGAGLMDZS/l0KNsBpu+Q5GR9A++QO3/PSiItGk/MwJljwXKetH0PKmznJVXoU4kbjNnPJp2fyZF9u30rTM1fl4hvBBc1VpMXn1NcfwGrYfthXZ4d0FfqKTcNeA1yrK/F29GJltRuadJH+UfmFDnhSlyg464jhJk1/YA6VFePkX/h/w88IEUmSp39/Loa4pjeeAMFJ1qETKVuYCwKY47yvK/F9vQf6PzdrIlDuxB686v1uQWo8255TLIVkqzaRumAlujNcpGNkcPa0+Sg4nWWQ2Fk1+EgvymvZilgf2b1DMLC4DzM5zXrL6mWiagTqRoZpIcvmwlypllvETylHQ4A7+HRbCY9PBuoL5jA/S9CIWgi2M0MvV6Gi9jGWOMMcYYY4wxxhhjjDGDmtHAj9Gu93zgHsIBMYzpGFZAJhtPoR2vfwN/R8ExjCmSX6JOcnfkuXEocniYUqVSpvto1jwIlK5yIsrjfQ9yhH9H7e93MsgvjaKPLEKZ29J8xBtZEblQPU7zOZ7XBdZAOs9tUta0n1HIuP8o9MNc5yIUmCGps9wbmZ4UzSUkm8HsjmIDFM0dJPtHjwSOLqHO+cCpgfIqnm+d5VBciTWROeJtJehRCMsgQ9FDc8rvhlwD64aqjwLbZZAbjsIxLWqQvZx45/wo6wDXNci9ARzbpN6m/SyP3lfU4+sslPUzKYJTFQbnp5dUZ5INJVRncF7F8wXFV3giInMR+dywS2cY8k65hOaDo05EDTz6gF5EI70Qx8TI1TvLEMNRgvg42U80qb9pPzcDd9MXoHZb9EVeQvKPpDvKoddRjkKjzTi5r6boWwjNRg/qRW592wIvoIZ8GvDeDLKfJj5A50rAASmySdOa3VEHnMRmyJMoji+n1GmqZ1+0Bv4omglcCPy8VrakKqVM29kSLZ3FkdZ3FEKeMGtXoensrsBv0XrBVcCvUuTeEihbM1CWli98rZx1huRMZ/A4sCP6MZ1Q+7yOOk+7vnUPoWRyy7dDgTwdJWit8Aa06PthtGb5MRRxJ4m7A2X3BMp6gX8llC1GG0JJJMmllZnO4j/IymI0GmVehkeU3cTtJOfjuqEdCuTtKKM8UPsb6vn/FzX2KPcBP0u5/vHEfzF+gKKsJ/EwcF7M8cXAV1LqNNXzXrSZsyWK2nQ1Wnc+rkqlTNt5BvhGzPGX0P5F6TS7YzQC2UxeCPwDmW9sgMyCnq0dS+I/KIPe/6CF28VoU+gLyCQhxFVox/xkYBLaOT8J+EkGnQ9Bu2VHIPOiO5DJyfQMsqZaetAP2rqorf0ZjSifCcjMRmuaRZOUgRHUtsvIQPrvQFk9EG7RvJJSXsXzBfguCu12GLA66mu+jiIQdRw9wLeRknPRFHw2cDFaP8pKKyPZPLafRdRrjDHGGGOMMcYYY4wxxhjT0Ywh3Q3p9sq0M0OVDyMTsvnI3OugatUxJswwFPWn/vk86hx3aDhWRlQR073siMzITgA2RK6si4CPVKiT6UJaMbXZG7kwroFMhNI4lrDnTl6+D9xZwnVN9VyJ4gM0hlS7EKVG3SxB5lSyRaRqlqNJzie+K3BiCXVOQ84WcaxOOfaMCwjn5+6W59uPdoYo2o70UEp5uKCEa5rOYDv0Q9jINSjy03LEG0dPQOmTiyaUAnelkuqcEShbmuYjeGVhVEp5tzzfftgA23Qqo1HAg6iL6rNoJjS27RqZrsUdpTHGpOCO0nQqryE32WhQ57FoEzHLurgxheCO0nQyNzMwN84UFCIvLXiDMYXRkfkmjKnxIxRa7VhkYfFutJHzySqVMt1HOzvKm0gPpZSHUDxKM7j5GwoI/U3gWyjz5mGEo+lfAtxbgi6hDIH3o9ioRXNXoOwV4NYS6kwLedgtz9cYY4wxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOMMcYYY4wxxhhjjDHGGGOMMcYYYzqH/wO0Q0frzfwi1AAAAABJRU5ErkJggg==\n", "text/plain": [""]}, "execution_count": 3, "metadata": {}, "output_type": "execute_result"}], "source": ["from IPython.display import Image\n", "Image(\"330px-International_Morse_Code-fr.svg.png\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["On se propose de r\u00e9pondre \u00e0 deux questions :\n", "\n", "- [1](#exo1) Comment traduire un texte Morse lorsque celui-ci ne contient pas d'espace ?\n", "- [2](#exo2) En vous inspirant de ce graphe [Arbre mn\u00e9motechnique de d\u00e9codage](http://fr.wikipedia.org/wiki/Morse_(alphabet)#Arbre_mn.C3.A9motechnique_de_d.C3.A9codage), construire un nouvel alphabet Morse qui r\u00e9duise la transcription d'un texte en particulier. On appliquera l'algorithme \u00e0 :\n", " - [L'homme qui rit](http://www.gutenberg.org/files/5423/5423-0.txt)\n", " - [The man who laughs](http://www.gutenberg.org/cache/epub/12587/pg12587.txt)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Enonc\u00e9s"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Exercice 1 : Traduire un texte Morse qui ne contient pas d'espace\n", "\n", "Ce sujet est un exercice classique de programmation. Il est d\u00e9j\u00e0 r\u00e9solu et expliqu\u00e9 sur [Codingame](http://www.synbioz.com/blog/exercice_de_programmation_codingame). Mais on pourra par exemple commencer par utiliser une expression r\u00e9guli\u00e8re. Une autre option consiste \u00e0 utiliser un *trie*."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Exercice 2 : calculer l'alphabet qui minimise une transcription\n", "\n", "Cette optimisation est possible puisque l'alphabet Morse transcrit les lettres avec des codes de longueurs diff\u00e9rentes. Il faudra aussi v\u00e9rifier qu'une fois l'alphabet choisi, il n'autorise qu'un seul d\u00e9codage de la transcription. On suppose qu'on conserve les contraintes du Morse : chaque lettre de l'alphabet est constitu\u00e9e de traits courts et long et qu'il n'y a pas de s\u00e9paration entre lettres. Vous pouvez vous inspirez de cet article sur la [Compression de donn\u00e9es](http://fr.wikipedia.org/wiki/Compression_de_donn%C3%A9es) ou celui sur le [code de Huffman](http://fr.wikipedia.org/wiki/Codage_de_Huffman)."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Solutions\n", "\n", "On remarque que tous les chiffres sont cod\u00e9s sur cinq caract\u00e8res alors que les lettres non. Cela vient du fait que toutes les combinaisons de lettres ne sont pas possible. En alphabet morse ``H=EEE=ooo`` mais aucun mot ne contient de s\u00e9quence ``EEE``. En pratique *26 + 10 + 1 = 37* et $2^5 < 37 < 2^6$. Cela explique le choix des 5 traits ou points pour les chiffres au maximum. Les tailles sont plus courtes pour les lettres car toutes les combinaisons ne sont pas possibles. On voit aussi que les lettres fr\u00e9quentes sont des s\u00e9quences courtes en morse. La s\u00e9quence ``ooo-ooo`` peut dire ``EELE`` ou ``STS``."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Solution au probl\u00e8me 1"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": ["alphabet = dict(A='o-', B='-ooo', C='-o-o', D='-oo', E='o', F='oo-o', G='--o',\n", " H='oooo', I='oo', J='o---', K='-o-', L='o-oo', M='--', N='-o',\n", " O='---', P='o--o', Q='--o-', R='o-o', S='ooo', T='-', U='oo-',\n", " V='ooo-', W='o--', X='-oo-', Y='-o--', Z='--oo')\n", "alphabet.update({\n", " '0': '-----', '1': 'o----', \n", " '2': 'oo---', '3': 'ooo--', \n", " '4': 'oooo-', '5': 'ooooo', \n", " '6': '-oooo', '7': '--ooo', \n", " '8': '---oo', '9': '----o',\n", "})"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"data": {"text/plain": ["'-oo-o-ooo-oooo-o'"]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}], "source": ["def word2morse(word, alpha=None):\n", " \"Code un mot en morse\"\n", " if alpha is None:\n", " alpha = alphabet\n", " return \"\".join(alpha[c] for c in word)\n", " \n", "word2morse('XAVIER')"]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"data": {"text/plain": ["'o-ooooooo----o'"]}, "execution_count": 6, "metadata": {}, "output_type": "execute_result"}], "source": ["word2morse('LISON')"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"data": {"text/plain": ["('ooo-ooo', 'ooo-ooo')"]}, "execution_count": 7, "metadata": {}, "output_type": "execute_result"}], "source": ["word2morse('EELE'), word2morse('STS')"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Solution au probl\u00e8me 2 avec des expressions r\u00e9guli\u00e8res\n", "\n", "On utilise une expression r\u00e9guli\u00e8re pour d\u00e9couper en mot tout en sachant qu'on ne sait pas ce que les ambigu\u00eft\u00e9s pourraient devenir."]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"data": {"text/plain": ["'^((o-)|(-ooo)|(-o-o)|(-oo)|(o)|(oo-o)|(--o)|(oooo)|(oo)|(o---)|(-o-)|(o-oo)|(--)|(-o)|(---)|(o--o)|(--o-)|(o-o)|(ooo)|(-)|(oo-)|(ooo-)|(o--)|(-oo-)|(-o--)|(--oo)|(-----)|(o----)|(oo---)|(ooo--)|(oooo-)|(ooooo)|(-oooo)|(--ooo)|(---oo)|(----o))+$'"]}, "execution_count": 8, "metadata": {}, "output_type": "execute_result"}], "source": ["exp = \"^({})+$\".format(\"|\".join(\"({})\".format(v) for v in alphabet.values()))\n", "exp"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["-o -> N\n", "-o-o -> C\n", "-o -> N\n"]}], "source": ["import re\n", "\n", "rev_alpha = {v:k for k, v in alphabet.items()}\n", "reg_exp = re.compile(exp)\n", "for el in reg_exp.finditer(\"-o-o-o-o-o\"):\n", " for gr in el.groups():\n", " if gr is None:\n", " continue\n", " print(gr, '->', rev_alpha.get(gr, '?'))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Ce n'est pas hyperprobant. Je me souviens d'avoir lu quelque chose qui parlait des probl\u00e8mes de r\u00e9p\u00e9titions dans les expressions r\u00e9guli\u00e8res sans pouvoir vraiment m'en souvenir. Alors pour faire simple et pas efficace, j'ai d\u00e9cid\u00e9 de relancer une recherche apr\u00e8s avoir \u00f4t\u00e9 la premi\u00e8re trouv\u00e9e."]}, {"cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [{"data": {"text/plain": ["['-o', '-o-o', '-o-o']"]}, "execution_count": 10, "metadata": {}, "output_type": "execute_result"}], "source": ["dec_exp = '-o-o-o-o-o'\n", "\n", "res = []\n", "while len(dec_exp) > 0:\n", " for el in reg_exp.finditer(dec_exp):\n", " for gr in el.groups():\n", " if gr is None:\n", " continue\n", " res.append(gr)\n", " dec_exp = dec_exp[len(gr):]\n", " break\n", " break\n", "res"]}, {"cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [{"data": {"text/plain": ["['N', 'C', 'C']"]}, "execution_count": 11, "metadata": {}, "output_type": "execute_result"}], "source": ["[rev_alpha[r] for r in res]"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La fonction de d\u00e9codage pourrait se suffire des trois derni\u00e8res lignes, on v\u00e9rifie qu'elle d\u00e9code bien les lettres."]}, {"cell_type": "code", "execution_count": 11, "metadata": {"scrolled": false}, "outputs": [{"data": {"text/plain": ["('oooo', 'EEEE')"]}, "execution_count": 12, "metadata": {}, "output_type": "execute_result"}], "source": ["def decode_morse(word, reg=None, alpha=None):\n", " if alpha is None:\n", " alpha = alphabet\n", " rev_alpha = {v:k for k, v in alpha.items()}\n", " if reg is None:\n", " exp = \"^({})+$\".format(\"|\".join(\"({})\".format(v) for v in rev_alpha.keys()))\n", " reg = re.compile(exp)\n", " \n", " res = []\n", " while len(word) > 0:\n", " for el in reg_exp.finditer(word):\n", " for gr in el.groups():\n", " if gr is None:\n", " continue\n", " res.append(gr)\n", " word = word[len(gr):]\n", " break\n", " break\n", " return ''.join(rev_alpha.get(g, g) for g in res)\n", "\n", "word = \"EEEE\"\n", "word2morse(word), decode_morse(word2morse(word))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La fonction g\u00e8re mal les confusions comme le montre la table suivante."]}, {"cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [{"data": {"text/plain": ["('oo-o', 'EEN')"]}, "execution_count": 13, "metadata": {}, "output_type": "execute_result"}], "source": ["word = \"F\"\n", "word2morse(word), decode_morse(word2morse(word))"]}, {"cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["5 ooooo EEEEE\n", "6 -oooo EEEEE\n", "7 --ooo EB\n", "8 ---oo DEE\n", "9 ----o GN\n", "A o- A\n", "B -ooo B\n", "C -o-o C\n", "D -oo D\n", "E o E\n", "F oo-o EEN\n"]}], "source": ["for letter in sorted(alphabet)[5:16]:\n", " m = word2morse(letter)\n", " m += \" \" * (6 - len(m))\n", " print(letter, m, decode_morse(word2morse(letter)))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Pour am\u00e9liorer le d\u00e9codage, il faudrait am\u00e9liorer l'expression r\u00e9guli\u00e8re pour placer les lettres morses les plus longues."]}, {"cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [{"data": {"text/plain": ["('ooooo', 'EEEEE')"]}, "execution_count": 15, "metadata": {}, "output_type": "execute_result"}], "source": ["def decode_morse_longer_first(word, reg=None, alpha=None):\n", " if alpha is None:\n", " alpha = alphabet\n", " rev_alpha = {v:k for k, v in alpha.items()}\n", " if reg is None:\n", " keys = [k[1] for k in sorted([(len(k), k) for k in rev_alpha.keys()],\n", " reverse=True)]\n", " exp = \"^({})+$\".format(\"|\".join(\"({})\".format(v) for v in keys))\n", " reg = re.compile(exp)\n", " \n", " res = []\n", " while len(word) > 0:\n", " for el in reg_exp.finditer(word):\n", " for gr in el.groups():\n", " if gr is None:\n", " continue\n", " res.append(gr)\n", " word = word[len(gr):]\n", " break\n", " break\n", " return ''.join(rev_alpha.get(g, g) for g in res)\n", "\n", "word = \"5\"\n", "word2morse(word), decode_morse_longer_first(word2morse(word))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Ca ne marche pas mieux... J'ai la flemme de chercher pourquoi. La solution la plus simple me para\u00eet de simplifier l'expression r\u00e9guli\u00e8re pour \u00e9viter d'avoir des choses comme ``(aaaa|a)+`` mais plu\u00f4t ``a{1,4}``. Ca me para\u00eet plus dr\u00f4le d'\u00e9crire un algorithme qui compresse une liste de patrons en une expression r\u00e9guli\u00e8re ou de faire mon propre algorithme et de sortir toutes les interpr\u00e9tations possibles."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Solution au probl\u00e8me 2 : toutes les interpr\u00e9tations\n", "\n", "L'objectif est de sortir toutes les interpr\u00e9tations possibles. ``oo`` peut \u00eatre ``I`` ou ``EE``. La version qui suit est loin d'\u00eatre la plus efficace... La version actuelle n'est pas la plus efficace. On cherche simple \u00e0 trouver tous les chemins possibles reliant deux noeuds d'un graphe. On peut aussi utiliser des [Graph Transformer Network](https://leon.bottou.org/publications/pdf/cvpr-1997.pdf). On peut \u00e9galement voir cela comme un syst\u00e8me de [compl\u00e9tion](http://www.xavierdupre.fr/app/mlstatpy/helpsphinx//c_nlp/completion.html) (les listes d\u00e9roulantes de pr\u00e9fix dans les barres de saisie sur Internet). Dans ce second cas, les suggestions serait les lettres morses."]}, {"cell_type": "code", "execution_count": 15, "metadata": {"scrolled": false}, "outputs": [{"data": {"text/plain": ["['EE', 'I']"]}, "execution_count": 16, "metadata": {}, "output_type": "execute_result"}], "source": ["def decompose_morse(word, alpha=None):\n", " if alpha is None:\n", " alpha = alphabet\n", " rev_alpha = {v:k for k, v in alpha.items()}\n", " letters = list(sorted(alpha.values()))\n", "\n", " options = [([], 0)]\n", " addition = 1\n", " while addition > 0:\n", " addition = 0\n", " new_options = []\n", " for stack, pos in options:\n", " if pos == len(word):\n", " new_options.append((stack, pos))\n", " else:\n", " prefix = word[pos:]\n", " for w in letters: \n", " if prefix.startswith(w):\n", " path = stack.copy()\n", " path.append(w)\n", " new_options.append((path, pos + len(w)))\n", " addition += 1\n", " options = new_options\n", " \n", " unique = set()\n", " for stack, pos in options:\n", " if pos != len(word):\n", " continue\n", " path = tuple(stack)\n", " unique.add(''.join(rev_alpha.get(c, c) for c in path))\n", " \n", " return list(sorted(unique))\n", "\n", "decompose_morse('oo')"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Le code morse laisse plein d'ambigu\u00eft\u00e9s qu'il faut \u00e9liminer \u00e0 l'aide d'un dictionnaire."]}, {"cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [{"data": {"text/plain": ["['DK',\n", " 'DNT',\n", " 'DTA',\n", " 'DTET',\n", " 'NAA',\n", " 'NAET',\n", " 'NEK',\n", " 'NENT',\n", " 'NETA',\n", " 'NETET',\n", " 'NRT',\n", " 'TEAA',\n", " 'TEAET',\n", " 'TEEK',\n", " 'TEENT',\n", " 'TEETA',\n", " 'TEETET',\n", " 'TERT',\n", " 'TFT',\n", " 'TIK',\n", " 'TINT',\n", " 'TITA',\n", " 'TITET',\n", " 'TUA',\n", " 'TUET',\n", " 'XA',\n", " 'XET']"]}, "execution_count": 17, "metadata": {}, "output_type": "execute_result"}], "source": ["decompose_morse(word2morse('XA'))"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Vu l'explosion des possibilit\u00e9s, j'en d\u00e9duis que les t\u00e9l\u00e9graphes devaient marquer une sorte de pause entre les lettres."]}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 3}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.2"}}, "nbformat": 4, "nbformat_minor": 2}