{
"cells": [
{
"cell_type": "markdown",
"id": "fe8d3904",
"metadata": {},
"source": [
"# Cinquième exercice en Python (Niveau Lycée)"
]
},
{
"cell_type": "markdown",
"id": "d4dba9e5",
"metadata": {},
"source": [
"![](\"https://blog.univ-angers.fr/mathsinfo/files/2022/06/image-4.png\")
"
]
},
{
"cell_type": "markdown",
"id": "1f899d69",
"metadata": {},
"source": [
"Exemple 1 : `~O~O~O~OP`\n",
"Tous les rats vont bien vers le joueur de flûte, donc aucun n'est sourd. Valeur attendue = 0\n",
"\n",
"Exemple 2 : `PO~O~~OO~`\n",
"Le rat souligné va dans la mauvaise direction, il est donc sourd. Valeur attendue = 1\n",
"\n",
"Exemple 3 : `~OO~~O~OP~OO~O~`\n",
"Cette fois il y a 2 rats sourds. Valeur attendue = 2"
]
},
{
"cell_type": "markdown",
"id": "dddcd526",
"metadata": {},
"source": [
"## Séparer les rats à gauche et à droite du joueur de flûte"
]
},
{
"cell_type": "markdown",
"id": "c1ee6357",
"metadata": {},
"source": [
"Une *première idée* est de récupérer les rats qui sont à **gauche** et à **droite** du joueur de flûte. Pour cela on utilise `split` :"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "dd8fa4ae",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['~O~O~O~O', '']"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"'~O~O~O~OP'.split('P')"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "f4f7ca5e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['', 'O~O~~OO~']"
]
},
"execution_count": 2,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"'PO~O~~OO~'.split('P')"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "afa05146",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['~OO~~O~O', '~OO~O~']"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"'~OO~~O~OP~OO~O~'.split('P')"
]
},
{
"cell_type": "markdown",
"id": "95b3da50",
"metadata": {},
"source": [
"Ensuite, un rat sera sourd dans la partie **gauche** s'il y a un 'O' à une position **paire** (puisque l'on est censé avoir déjà la queue du rat puis la tête ~O et pas l'inverse). De la même façon, dans la partie **droite**, un rat est sourd si on trouve un 'O' à une position **impaire**. On pourrait donc imaginer faire 2 boucles, chacune ressemblant à :\n",
"\n",
"for i in range(len(gauche)):\n",
" if gauche[i] == 'O' and i%2 == 0: # un 'O' à une position paire\n",
" sourds += 1 \n",
" \n",
"Une boucle suffit si on concatène **gauche** et **droite** (et que l'on retourne une des 2 chaines). C'est-à-dire passer de `['~OO~~O~O', '~OO~O~']` à l'unique chaine `'~OO~~O~O~O~OO~'` (on a retourné tous les rats qui étaient dans la partie **droite**). Les rats sourds sont ceux où il y a un 'O' à une position paire (rappel, en Python et JavaScript, le premier élément d'une chaine ou d'un tableau est à la position **0**). "
]
},
{
"cell_type": "markdown",
"id": "e4f99935",
"metadata": {},
"source": [
"Retourner une chaine en Python :"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "6708e3f4",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'ruojnob'"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"'bonjour'[::-1]"
]
},
{
"cell_type": "markdown",
"id": "10ec6782",
"metadata": {},
"source": [
"Il faut donc parcourir toutes les lettres de la chaine contenant les rats et regarder s'il y a un 'O' à une position paire. Pour cela on utilise `enumerate` qui permettra de récupérer à la fois le caractère et son rang :"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "172fd0dd",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(0, '~'),\n",
" (1, 'O'),\n",
" (2, 'O'),\n",
" (3, '~'),\n",
" (4, '~'),\n",
" (5, 'O'),\n",
" (6, '~'),\n",
" (7, 'O'),\n",
" (8, '~'),\n",
" (9, 'O'),\n",
" (10, '~'),\n",
" (11, 'O'),\n",
" (12, 'O'),\n",
" (13, '~')]"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(enumerate('~OO~~O~O~O~OO~'))"
]
},
{
"cell_type": "markdown",
"id": "ebcf5139",
"metadata": {},
"source": [
"Vous avez tout pour comprendre cette version :"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "07dc0d69",
"metadata": {},
"outputs": [],
"source": [
"def rats_sourds(town):\n",
" [gauche, droite] = town.split('P')\n",
" rats = gauche + droite[::-1]\n",
" return sum([c == 'O' and i % 2 == 0 for i,c in enumerate(rats)])"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "63631e8b",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"rats_sourds('~O~O~O~OP')"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "04291bed",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"rats_sourds('PO~O~~OO~')"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "c1ef39ce",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"rats_sourds('~OO~~O~OP~OO~O~')"
]
},
{
"cell_type": "markdown",
"id": "9196e4da",
"metadata": {},
"source": [
"## A-t-on vraiment besoin de séparer la gauche et la droite ?"
]
},
{
"cell_type": "markdown",
"id": "581605f5",
"metadata": {},
"source": [
"En observant un peu plus attentivement la chaine représentant une ville, par exemple `'~OO~~O~OP~OO~O~'`, on se rend compte que peu importe l'emplacement du joueur de flûte, il y aura un rat sourd dès qu'un `'O'` est observé à une position **paire**. Par exemple dans la ville `'P~OO~O~'`, la tête du rat sourd est bien à une position paire.\n",
"\n",
"*Finalement, il suffit de compter le nombre de 'O' qu'il y a dans la ville en n'ayant récupéré que les lettres qui sont aux positions paires.*"
]
},
{
"cell_type": "markdown",
"id": "518e6ccb",
"metadata": {},
"source": [
"Il est très facile de récupérer une lettre sur 2 en Python :"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "2956be03",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"'UeeteuDu'"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"'UneLettreSurDeux'[::2]"
]
},
{
"cell_type": "markdown",
"id": "88d73496",
"metadata": {},
"source": [
"Et le programme final, beaucoup plus court suite à notre analyse : "
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "5e5758d1",
"metadata": {},
"outputs": [],
"source": [
"def rats_sourds(ville):\n",
" return ville[::2].count('O')"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "75ddc5ec",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"rats_sourds('~OO~~O~OP~OO~O~')"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"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.9.6"
}
},
"nbformat": 4,
"nbformat_minor": 5
}