Défis de programmation amicaux lancé sur le forum fr.comp.lang.tcl aussi connu sous le terme de Jeux Técleux.
Ecrire un code qui affiche toutes les années comprises entre 2000 et 2100 qui comportent un ou plusieurs mois avec 5 vendredi.
Ce jeux porte sur le calendrier : écrire une procédure qui prend en entrée le numéro d'un mois et l'année, et qui renvoie le nombre de jours contenus dans ce mois.
Ce jeux porte sur le tri des longueurs de listes en fonction de leur fréquence d'apparition.
Soit une liste contenant des sous-listes:
set l {{a b c} {d e} {f g h} {i j k l} {m n} o {p q r}}
Ecrire une procédure (TriFreqLong) qui trie cette liste en fonction
de la fréquence des longueurs des sous-listes de la moins fréquente
à la plus fréquente.
TriFreqLong $l
donne
{i j k l} o {d e} {m n} {a b c} {f g h} {p q r} Il s'agit d'écrire une procédure qui rend la monnaie
en Euro quand on achète quelquechose en minimisant
le nombre de billets et de pièces de monnaie.
Les données sont:
- L'ensemble des billets: {500 200 100 50 20 10 5}
- L'ensemble des pièces: {2 1 0.5 0.2 0.1 0.05 0.02 0.01}
- Le prix d'un produit p
- L'argent que l'on donne a (a > p)
proc RendMonnaie {p a} { .... }
Exemple:
RenMonnaie 12.99 20
renvoie:
billet 5
pièce 2 0.01 Le Jeux Tecleux de ce mois-ci porte encore sur la génomique ;-)
Je soumets à votre sagacité l'=E9criture d'un code optimisé concernant
la comparaison entre 2 séquences de protéines:
Seq1 ACD...FFFI.M
| | ||
Seq2 A.....FYFI.K
(note: les points ne sont pas des points de suspension)
Il s'agit de déterminer le pourcentage d'identité qu'il y a entre des séquences de protéine.
Pour cela on compte le nombre de lettres identiques qui se font face
pour 2 séquences données. Dans notre exemple ce nombre vaut 4.
Et on divise par le nombre de lettres de la plus petite des deux
séquences. Dans notre exemple le nombre de lettres vaut 6 (Seq2).
Donc le pourcentage vaut p =3D 4/6 =3D 0.6666
Ca parait simple, MAIS :
- les séquences font entre 1000 et 10 000 caractères de long
- on a en general entre 300 et 500 séquences, il faut le pourcentage
d'identité de tous les couples, soit par exemple, (300*299/2) paires
de séquences ...
L'aspect vitesse devient crucial !
Pour amorcer, je fournis une proc qui genere une liste de séquence
(aléatoire ici) qui peut s'apparenter a un cas réel ....
proc Data {} {
set ll [list A C D E F G H I K L M N P Q R S T V W Y . . . . . . . . . . . . . . . . . . . . .]
for {set n 0} {$n < 100} {incr n} {
set seq ""
for {set i 0} {$i < 1000} {incr i} {
append seq [lindex $ll [expr {round(40*rand())}]]
}
lappend Lseq $seq
}
return $Lseq
} Il existe un concours national d'informatique du nom de Prologin:
http://www.prologin.org/
Il s'agit de répondre aux 4 problèmes du questionnaire de sélection de la page 3:
http://www.prologin.org/files/prologin2010/Prologin_QCM2010.pdf
--------
Dans tous les exercices proposés, une séquence d'ADN sera une
suite finie constituée de lettres dans l'ensemble {A, T, G, C}.
Chaque élément de la séquence d'ADN sera appelé un nucléotide.
P1. Nucléotide
On vous donne en entrée une séquence d'ADN de longueur n.
Écrivez une fonction qui renvoie le nucléotide (la lettre)
le plus présent. Si c'est le cas de plusieurs, renvoyez
celle qui vient en premier dans l'ordre alphabétique.
Exemple :
Séquence d’ADN : ATTGCCATATCC
Réponse : C
P2. Les acides aminés
Lors de la transcription (simplifiée !) d’une séquence d’ADN
en suite d’acides aminés, chaque groupement de trois nucléotides
de la séquence d’ADN est transformé en acide aminé.
Écrivez une fonction qui, étant donné une séquence d’ADN de
longueur n et la table de transcription, renvoie la suite
d’acides aminés correspondante. On assure que tout le brin
d’ADN pourra être transcrit, et que n est multiple de 3.
Exemple :
Séquence d’ADN : ATTGCCTCC
Table de transcription : ATT -> isoleucine ; TCC -> serine ;
GCC -> alanine
Réponse : isoleucine alanine serine
P3. Sous-séquences
On cherche à analyser les fréquences d’apparition des
sous-séquences d’une séquence d’ADN donnée en entrée.
Écrivez une fonction qui renvoie la sous-séquence contiguë
de longueur L de la chaîne d’ADN la plus fréquente.
Dans le cas où plusieurs sous-séquences apparaissent un même
nombre de fois, affichez celle qui vient en premier dans
l’ordre alphabétique.
Exemple :
Séquence d’ADN : AATTCGGCCGATCGTCGAATTCGATA
L = 4
Réponse : AATT
P4. Mutations (Question bonus)
On vous donne en entrée deux séquences ADN de tailles n1 et n2.
On souhaite calculer le nombre minimal de transformations pour
passer de la première séquence à la deuxième. Les transformations
possibles sont la modification, l'ajout ou la suppression d'un
nucléotide. Les deux séquences sont très similaires ; on garantit
donc que l'on puisse passer de l'une à l'autre en moins de
100 transformations.
Écrivez une fonction renvoyant le résultat demandé.
Exemple :
Première séquence : ATTGCAAA
Seconde séquence : ATCTAAAT
Réponse : 4Le Jeux Técleux de ce mois-ci porte sur la conversion en chiffre romain et vice versa. Ecrire une procedure "romain" qui converti de notre système numérique en chiffre romain: % puts [romain 1881] % MDCCCLXXXI Ecrire une procedure "niamor" qui fait l'inverse: % puts [niamor CCLV] % 255 Pour rappel: I = 1 V = 5 X = 10 L = 50 C = 100 D = 500 M = 1000 Le jeux n'étant pas trop difficile, l'originalité de la solution porte sur le choix d'une structure de données (array, list, dict, ....) et sur une version récursive ou non. Cependant attention il existe des formes particulières en chiffre romain: IV = 4 IX = 9 XC = 90 XM = 990 CM = 900 IM = 99 On se limitera à des nombres n'allant pas au delà de 4999. Pour la culture voir sur: http://fr.wikipedia.org/wiki/Num%C3%A9ration_romaine
Allez, pour une fois on va faire un jeu qui ne sera pas complètement
inutile puisqu'il pourrait faire l'objet d'un package.
Le but :
Écrire une procédure proc Echeance {base ajout cible} qui
calculera ... une échéance (de facture en général), dont les arguments
s'entendent comme suit :
• base : date de départ du calcul au format JJ/MM/YYYY
• ajout : nombre de jours ajoutés (30, 45 ou 60 selon la nouvelle
législation française, voir http://www.dgccrf.bercy.gouv.fr/documentation/lme/delais_paiement.htm
pour une explication détaillée).
• cible : "fin de mois" ou "net"
Le résultat sera retournée sous la forme d'une date au format JJ/MM/YYYY.
Exemples :
% Echeance 04/02/2009 30 "fin de mois"
31/03/2009
% Echeance 04/02/2009 45 net
21/03/2009
Indices :
Vous allez probablement utiliser clock format, clock scan et clock add.
La différence se fera sûrement dans l'élégance / l'astuce du code
pour la partie "fin de mois".Il s'agit de créer un programme qui génère à partir d'un chiffre A une suite de N nombres de telle sorte que le prochain nombre se déduit du précédent en énoncant les chiffres contenus à haute voix. Bon, je crois que cela vaut la peine de donner un exemple: Donc avec A=1 et N=5: Suite 1 5 donnera: 1 soit (un,un) 11 soit (deux un) 21 soit (un deux, un un) 1211 soit (un un,un deux,deux un) 111221 soit (trois un,deux deux,un un) 312211
L'énoncé est très simple, il s'agit d'implémenter la méthode de compression run-length encoding. Soit une chaine de caractères: set s "aaaabbcdeeeeefaaajjjjjjjjmmmm" L'idée est de coder les répétitions consécutives de caractères pour obtenir la chaîne compressée: 4a2b1c1d5e1f3a8j4m Donc, écrire une procédure "encode" pour compresser la chaîne de caractère et une procédure "decode" pour décompresser une chaîne compressée. A quoi ça peut bien servir ? Voir: http://fr.wikipedia.org/wiki/Run-length_encoding
Que fait le code suivant:
if 0 {Quoi fait-ce ?}
proc a {b c d} {
for {set e 0} {$e<[llength $c]} {incr e [llength $b]} {
for {set f 0} {$f < [llength $b]} {incr f} {
uplevel [subst {
set [lindex $b $f] {}
set [lindex $b $f] [lindex $c [expr $e+$f]]
}]
}
uplevel $d
}
} Soit une liste de réels quelconques, par exemple :
set liste [list 12.6 0 9 -121.4 3.3 -18 9 12.601 -1]
Ecrire la procédure MAX telle que : expr {[MAX $liste]} retourne le nombre
le plus grand de $liste (soit 12.601 dans mon exemple).
Contraintes :
- l'expression retournée pas [MAX] ne doit utiliser que des opérateurs connus
de expr (+ * == x?y:z % etc..) Soit une liste de lettres distinctes.
Ecrire un code qui renvoi toutes les combinaisons possibles de n lettres prises parmi les éléments de la liste.
Exemple: set l [list a b c d]
Combi 3 $l
Résultat: {a b c} {a b d} {b c d} {a c d}
Remarque: l'ordre des éléments n'a pas d'importance.
Autrement dit {a b c}, {b a c} et {c a b} sont équivalents.Soit une liste quelconque de lettres: set l [list a a a a b b c c c a a d d d e e e e b b b f] Ecrire un code qui élimine les doublons consécutifs. Ce qui donne comme résultat: a b c a d e b f
Générer la séquence suivante: AA AB AC .... AZ BA BB BC .... BZ CA CB CC .... CZ .... ZA ZB ZC .... ZZ
Ecrire un code optimisé pour afficher la fractale :
XG a fait remarquer que l'image ci-dessus comporte quelques anomalies. La version juste devant plus ressembler à ça :
La réponse de [Pacalou] (normalisée pour la mesure)
package require Tk
image create photo im -width 256 -heig 256
proc pacalou {} \
{
set L {1 2 4 8 16 32 64 128}
set bcol 0
set tabcol(0) gray75
set tabcol(1) gray50
foreach e $L \
{
set e2 [expr {$e/2}]
set 2e [expr {2*$e}]
set col $tabcol($bcol)
for {set i $e2; set i2 [expr {$e+$e2}]} {$i < 256} {incr i $2e ; incr i2 $2e} \
{
for {set j $e2; set j2 [expr {$e+$e2}]} {$j < 256} {incr j $2e ; incr j2 $2e} \
{ im put $col -to $i $j $i2 $j2 }
#update; #juste pour faire patienter
}
set bcol [expr {1-$bcol}]
}
}
pacalou
puts [time pacalou]
pack [canvas .c -bg gray50]
.c create image 3 3 -anchor nw -image im