Concours fr.comp.lang.tcl

 

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 : 4

 Le 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




Catégorie Concours