%% \documentclass{article}
%% \usepackage{amsmath, amssymb, latexsym}
%% \usepackage[dvips]{epsfig}
%% \usepackage{tdtpik}
%% \usepackage{listes}

\newcommand{\N} {\ensuremath{\mathbb{N}}}

%% \begin{document}
\section{Tetris}

Le but de cette partie est d'impl\'ementer quelques fonctions
permettant de programmer un jeu de {\tt Tetris} simplifi\'e.

On dispose d'un ``plateau'' de jeu qui est compos\'e de $n+1$
emplacements, num\'erot\'es de 0 \`a $n$ ($n\in\N$ fixe). Au-dessus de
chaque emplacement, on peut potentiellement empiler une infinit\'e de
pi\`eces. Les pi\`eces ont une forme rectangulaire~: elles sont de
hauteur~1 et de largeur un entier strictement positif. Les pi\`eces
tombent verticalement de haut en bas et s'arr\^etent d\`es le premier
obstacle rencontr\'e en restant en position horizontale. Les mouvements lat\'eraux ne sont pas autoris\'es (on supposera qu'avant la chute d'une pi\`ece, le joueur pr\'ecise l'emplacement sur lequel elle tombe
%ainsi, il n'y a jamais d'autre pi\`ece au dessus d'une pi\`ece qui vient de s'immobiliser
). Ceci est
illustr\'e par la figure~\ref{fig:tetris1}. On dit qu'une pi\`ece tombe \`a
l'emplacement $k$ si la partie la plus \`a gauche de la pi\`ece tombe
dans la colonne $k$; autrement dit, la pi\`ece s'\'etale de la colonne
$k$ \`a une colonne $k'\geq k$, $k'$ d\'ependant de sa largeur.

\begin{figure}[htbp]
  \centering
  {\epsfig{file=tetris1.eps, height=2.6cm}}
  \caption{Une situation possible dans le {\tt Tetris} simplifi\'e}
  \label{fig:tetris1}
\end{figure}

\begin{exercice}\label{exo:tetris1}
  On s'int\'eresse au {\em profil sup\'erieur\/} (ou {\em profil})
  d'un jeu, c'est-\`a-dire \`a la suite finie de $n+1$ entiers, tel que
  l'entier num\'ero $k$ est \'egal \`a la plus grande ordonn\'ee
  occup\'ee dans la colonne $k$. Ainsi, tant qu'aucune pi\`ece n'est
  tomb\'ee, le profil du jeu est $$p=(\underbrace{0,0,\ldots
  ,0}_{n+1}).$$ Si une pi\`ece de largeur~2 tombe \`a l'emplacement~1, le
  nouveau profil est $$p'=(0,1,1,\underbrace{0,0,\ldots ,0}_{n-2}).$$
  Si $p$ est un profil, on notera $p_i$ ($0\leq i\leq n$) la $i^{\text{e}}$
  composante de $p$.
\begin{Pabc}
  \item Proposer un type pour d\'ecrire un profil. On appellera {\tt
      profil} ce type.\bareme{1}
  \item Soit un profil $p$. On suppose qu'une pi\`ece de largeur $l$
  tombe \`a l'emplacement $c$. On veut calculer le nouveau profil $p'$
  du jeu. Pour chaque $i$ entre 0 et $n$, donner la valeur de
  $p'_i$.\bareme{1}
  \item Ecrire une fonction
\hop\begin{verbatim}
profil ajout_piece(profil p, int larg, int col);
\end{verbatim}
\hop qui renvoie le nouveau profil obtenu apr\`es la chute d'une pi\`ece de
largeur {\tt larg} \`a l'emplacement {\tt col} sur le profil {\tt p}.\bareme{1}
\end{Pabc}
\end{exercice}

\begin{exercice}
Quand une ligne du jeu est pleine, c'est-\`a-dire qu'\`a une hauteur
donn\'ee toutes les colonnes sont occup\'ees, on veut la faire
dispara\^{\i}tre du jeu et d\'ecaler d'une unit\'e vers le bas tout ce
qui se trouve au-dessus, cela en d\'efiant les lois de la pesanteur,
puisque certaines pi\`eces peuvent alors se trouver au-dessus d'un
trou sans y tomber. La figure~\ref{fig:tetris2} illustre ce principe.

\begin{figure}[htbp]
  \centering
  {\epsfig{file=tetris2.eps, width=\linewidth}}
  \caption{Disparition d'une ligne pleine}
  \label{fig:tetris2}
\end{figure}

\begin{Pabc}
  \item Pour pouvoir supprimer une ligne, on a besoin de savoir
  quelles sont les cases occup\'ees. Pour cela, on modifie le type
  {\tt profil} introduit \`a l'exercice~\ref{exo:tetris1}, pour qu'en
  plus de la hauteur associ\'ee \`a chaque colonne, on ait la liste
  des emplacements occup\'es (sous forme de listes
  cha\^{\i}n\'ees, une liste cha\^{\i}n\'ee par colonne). Ecrire ce
  nouveau type et adaptez la fonction
\hop\begin{verbatim}
profil ajout_piece(profil p, int larg, int col);
\end{verbatim}\hop de l'exercice~\ref{exo:tetris1} (sans suppression de
  ligne).\bareme{2}

D\'esormais, le type {\tt profil} est le nouveau type que vous venez
d'introduire.
  \item Ecrire une fonction
\hop\begin{verbatim}
bool case_occupee(profil p, int haut, int col);
\end{verbatim}
\hop qui renvoie {\tt true} si et seulement si la case de la colonne
{\tt col} \`a la hauteur {\tt haut} est occup\'ee dans le profil {\tt
  p}.\bareme{1}
  \item Ecrire une fonction
\hop\begin{verbatim}
bool ligne_occupee(profil p, int haut);
\end{verbatim}
\hop qui renvoie {\tt true} si et seulement si la ligne de hauteur {\tt
  haut} est enti\`erement occup\'ee.\bareme{1}
  \item Ecrire une fonction
\hop\begin{verbatim}
profil supprime_ligne(profil p, int haut);
\end{verbatim}
\hop qui renvoie le profil obtenu apr\`es suppression de la ligne de hauteur
{\tt haut} dans le profil {\tt p}.\bareme{1,5}
  \item Ecrire une fonction
\hop\begin{verbatim}
profil tetris(profil p, int larg, int col);
\end{verbatim}
\hop qui renvoie le nouveau profil obtenu apr\`es la chute d'une pi\`ece de
largeur {\tt larg} \`a l'emplacement {\tt col} sur le profil {\tt p} et
suppression des \'eventuelles lignes pleines.\bareme{1,5}
\end{Pabc}

\end{exercice}

%% \end{document}
