{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Tri tricolore - un petit exerice d'algorithmique\n", "\n", "On aligne $n$ boules, réparties en un nombre quelconque de boules de couleur bleue, blanche ou rouge.\n", "Ces boules sont disposees dans un ordre quelconque. La ligne de boules est representée par un tableau `B` de taille $n$, dont chaque ́element `B[i]` appartient à l’ensemble `{bleu, blanc, rouge}`\n", "\n", "**Question :** ́Ecrire un algorithme qui trie le tableau de telle facon que toutes les boules bleues apparaissent au debut, suivies des boules blanches puis des boules rouges.\n", "La contrainte est que le tri du tableau doit être realise en seul parcours (on ne peut tester qu’une seule fois la couleur de chaque boule) et en place (sans utiliser de deuxieme tableau).\n", "\n", "**Indication :** Les elements d’un tableau peuvent être réécrits." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Solution en Python : exemples et affichage" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "D'abord, quelques exemples de tableaux." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "ExecuteTime": { "end_time": "2020-10-20T13:04:13.896130Z", "start_time": "2020-10-20T13:04:13.893773Z" } }, "outputs": [], "source": [ "BLEU, BLANC, ROUGE = \"bleu\", \"blanc\", \"rouge\"" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "ExecuteTime": { "end_time": "2020-10-20T13:04:41.909364Z", "start_time": "2020-10-20T13:04:41.901252Z" } }, "outputs": [], "source": [ "boules1 = [BLEU, BLANC, ROUGE, ROUGE, BLANC, BLEU, BLANC, ROUGE, BLANC, BLEU, ROUGE]" ] }, { "cell_type": "code", "execution_count": 36, "metadata": { "ExecuteTime": { "end_time": "2020-10-20T13:13:18.756208Z", "start_time": "2020-10-20T13:13:18.749352Z" } }, "outputs": [], "source": [ "boules2 = [BLEU, BLANC, ROUGE, ROUGE, BLANC, BLEU, BLANC, ROUGE, BLANC, BLEU, ROUGE][::-1]" ] }, { "cell_type": "code", "execution_count": 37, "metadata": { "ExecuteTime": { "end_time": "2020-10-20T13:13:18.756208Z", "start_time": "2020-10-20T13:13:18.749352Z" } }, "outputs": [], "source": [ "boules3 = boules2 *2 + boules1 * 2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Et des cas spéciaux, sans forcément avoir des boules de chaque couleurs :" ] }, { "cell_type": "code", "execution_count": 79, "metadata": { "ExecuteTime": { "end_time": "2020-10-20T13:36:27.438034Z", "start_time": "2020-10-20T13:36:27.434012Z" } }, "outputs": [], "source": [ "boules4 = [BLEU, BLANC, BLEU, BLANC, BLEU, BLANC, BLEU, BLANC, BLEU, BLANC, BLEU, BLANC] # pas de rouges\n", "boules5 = [BLANC, ROUGE, BLANC, ROUGE, BLANC, ROUGE, BLANC, ROUGE, BLANC, ROUGE, BLANC, ROUGE] # pas de bleues\n", "boules6 = [ROUGE, BLEU, ROUGE, BLEU, ROUGE, BLEU, ROUGE, BLEU, ROUGE, BLEU, ROUGE, BLEU, ROUGE, BLEU] # pas de blanches" ] }, { "cell_type": "code", "execution_count": 88, "metadata": { "ExecuteTime": { "end_time": "2020-10-20T13:37:54.033429Z", "start_time": "2020-10-20T13:37:54.030903Z" } }, "outputs": [], "source": [ "boules7 = [BLEU] * 20 # que des bleues\n", "boules8 = [BLANC] * 20 # que des blanches\n", "boules9 = [ROUGE] * 20 # que des rouges" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Juste pour faire joli, je vais écrire des fonctions qui soient \"typées\" en Python, c'est-à-dire avec des indications de types. Python reste un langage dynamiquement typé, ces indications seront JUSTE là pour faire joli." ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "ExecuteTime": { "end_time": "2020-10-20T13:06:40.216119Z", "start_time": "2020-10-20T13:06:40.202498Z" } }, "outputs": [], "source": [ "from typing import List, Union\n", "\n", "Boule = Union[\"bleu\", \"blanc\", \"rouge\"]\n", "Boules = List[Boule]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Visualisation : je vais utiliser le petit module [`ipythonblocks`](http://www.ipythonblocks.org/about) :" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "ExecuteTime": { "end_time": "2020-10-20T13:11:25.426818Z", "start_time": "2020-10-20T13:11:25.421601Z" } }, "outputs": [], "source": [ "from ipythonblocks import BlockGrid\n", "\n", "c_bleu, c_blanc, c_rouge = (0, 0, 255), (215, 215, 215), (255, 0, 0)" ] }, { "cell_type": "code", "execution_count": 32, "metadata": { "ExecuteTime": { "end_time": "2020-10-20T13:12:29.492911Z", "start_time": "2020-10-20T13:12:29.475290Z" } }, "outputs": [], "source": [ "def boules_vers_grid(boules: Boules) -> BlockGrid:\n", " n = len(boules)\n", " grid = BlockGrid(n, 1, fill=(c_blanc))\n", " for i, boule in enumerate(boules):\n", " if boule == BLEU:\n", " grid[0,i].set_colors(*c_bleu)\n", " elif boule == BLANC:\n", " grid[0,i].set_colors(*c_blanc)\n", " elif boule == ROUGE:\n", " grid[0,i].set_colors(*c_rouge)\n", " return grid\n", "\n", "def print_boules(boules: Boules) -> None:\n", " boules_vers_grid(boules).show()" ] }, { "cell_type": "code", "execution_count": 81, "metadata": { "ExecuteTime": { "end_time": "2020-10-20T13:37:03.456600Z", "start_time": "2020-10-20T13:37:03.440656Z" } }, "outputs": [ { "data": { "text/html": [ "