Cinquième exercice en Python, JavaScript et APL

Exemple 1 : ~O~O~O~OP
Tous les rats vont bien vers le joueur de flûte, donc aucun n’est sourd. Valeur attendue = 0

Exemple 2 : PO~O~~OO~
Le rat souligné va dans la mauvaise direction, il est donc sourd. Valeur attendue = 1

Exemple 3 : ~OO~~O~OP~OO~O~
Cette fois il y a 2 rats sourds. Valeur attendue = 2

Séparer les rats à gauche et à droite du joueur de flûte

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 en Python/JavaScript ou en APL.

Python & Javascript

>> '~O~O~O~OP'.split('P')
['~O~O~O~O', '']

>> 'PO~O~~OO~'.split('P')
['', 'O~O~~OO~']

>> '~OO~~O~OP~OO~O~'.split('P')
['~OO~~O~O', '~OO~O~']

APL

      {('P'≠⍵) ⊆ ⍵} '~OO~~O~OP~OO~O~'
┌────────┬──────┐
│~OO~~O~O│~OO~O~│
└────────┴──────┘

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

for i in range(len(gauche)):
  if gauche[i] == 'O' and i%2 == 0:   # un 'O' à une position paire
    sourds += 1     

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).

retourner une chaine en Python

>> 'bonjour'[::-1]
'ruojnob'

Retourner une chaine en javascript

Javascript sait inverser un tableau mais pas une chaine. On va donc convertir la chaine en tableau, inverser ce tableau puis revenir à une chaine :

>>[...'bonjour']
['b', 'o', 'n', 'j', 'o', 'u', 'r']

>> [...'bonjour'].reverse()
['r', 'u', 'o', 'j', 'n', 'o', 'b']

>> [...'bonjour'].reverse().join('')
'ruojnob'

Si on a fréquemment besoin d’inverser une chaine en JavaScript, soit on trouve une bibliothèque (comme Esrever) contenant cette fonctionnalité, ou on crée un prototype :

>> String.prototype.reverse = function() {
  return this.split("").reverse().join("");
}

>> 'bonjour'.reverse()
'ruojnob'

en apl

      ⌽'bonjour'       ⍝ Admirez le symbole utilisé
ruojnob

version finale en python

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 :

>> list(enumerate('~OO~~O~O~O~OO~'))
[(0, '~'), (1, 'O'), (2, 'O'), (3, '~'), (4, '~'), (5, 'O'), (6, '~'), (7, 'O'), (8, '~'), (9, 'O'), (10, '~'), (11, 'O'), (12, 'O'), (13, '~')]

Vous avez tout pour comprendre cette version à tester ici :

def rats_sourds(town):
    [gauche, droite] = town.split('P')
    rats = gauche + droite[::-1]
    return sum([c == 'O' and i % 2 == 0 for i,c in enumerate(rats)])

>> rats_sourds('~O~O~O~OP')
0
>> rats_sourds('PO~O~~OO~')
1
>> rats_sourds('~OO~~O~OP~OO~O~')
2

Javascript

Nous avons besoin de parcourir une chaine et accumuler le nombre de rats sourds, cela fait penser à reduce que nous avons utilisé au premier exercice. Notre accumulateur a sera le nombre de rats sourds (initialisé à 0) qui incrémentera de 1 au fur et à mesure si besoin.

>> var rats_sourds = ville => {
    [gauche, droite] = ville.split('P');
    rats = gauche + [...droite].reverse().join('');
    return [...rats]
       .reduce((a, c, i) => i%2 == 0 && c == 'O' ? a + 1 : a, 0)}

>> rats_sourds('~O~O~O~OP')
0
>> rats_sourds('PO~O~~OO~')
1
>> rats_sourds('~OO~~O~OP~OO~O~')
2

Remarque : reduce existe aussi en Python, en utilisant la bibliothèque functools. Voici un exemple où l’on compte par accumulation le nombre de ‘e’ dans une liste de mots :

>> from functools import reduce
>> mots = ['hello', 'yes', 'no', 'eleve']   # Liste de mots

>> reduce(lambda a, c : a + c.count('e'), mots, 0)
5

A-t-on vraiment besoin de séparer la gauche et la droite ?

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.

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.

Python

Il est très facile de récupérer une lettre sur 2 en Python :

>> 'UneLettreSurDeux'[::2]
'UeeteuDu'

Et le programme final, beaucoup plus court suite à notre analyse :

>> def rats_sourds(ville):
    return ville[::2].count('O')

javascript

>> var rats_sourds = ville => [...ville]
       .reduce((a, c, i) => i%2 == 0 && c == 'O' ? a + 1 : a, 0)

On peut aussi utiliser un filtre pour ne garder que les ‘O’ qui sont à des positions paires puis compter le nombre d’éléments (length) :

>> var rats_sourds = ville => [...ville]
       .filter((c, i) => i%2 == 0 && c == 'O').length

>> rats_sourds('~O~O~O~OP')
0
>> rats_sourds('PO~O~~OO~')
1
>> rats_sourds('~OO~~O~OP~OO~O~')
2

apl

Pour sélectionner, en APL, des éléments d’une chaine, d’un vecteur ou d’une matrice, on utilise / et un vecteur booléen (constitué de 1 ou de 0). Par exemple :

      2 | ⍳7               ⍝ Restes des divisions de 1, 2..., 7 par 2
1 0 1 0 1 0 1
      (2 | ⍳7) / 'bonjour' ⍝ qui sert à sélectionner une lettre sur 2
bnor

Au lieu de 7 comme dans l’exemple, on utilisera ⍴⍵ pour récupérer la taille de la ville. On peut finalement repérer les ‘O’ qui sont aux positions paires :

      rats_sourds_version_0 ← {'O' = (2|⍳⍴⍵) / ⍵}

      rats_sourds_version_0 '~OO~~O~OP~OO~O~'
0 1 0 0 0 1 0 0         ⍝ Les 1 correspondent aux têtes des rats sourds

Et ensuite les compter, c’est-à-dire faire une réduction par la somme :

      rats_sourds_version_1 ← {+/ 'O' = (2|⍳⍴⍵) / ⍵}

      rats_sourds_version_1 '~OO~~O~OP~OO~O~'
2

Observez que l’on a fait des tests ( ‘O’ = …) qui donne des 0 ou des 1 puis l’addition de ces valeurs. De façon analogue, la fonction SOMMEPROD d’Excel fait des produits et ensuite leur somme. C’est ce qu’on appelle un produit interne. En voici quelques exemples (⌈ permet de récupérer le plus grand entre 2 nombres) :

    +/  2 6 × 4 5    ⍝ (2 × 4) + (6 × 5) = 38 (somme des produits)
38

   2 6  +.× 4 5      ⍝ Même résultat en utilisant un produit interne
38

    ×/  2 6 ⌈ 4 5    ⍝ (2 ⌈ 4) × (6 ⌈ 5) = 4 × 6 = 24
24

   2 6 ×.⌈ 4 5       ⍝ Produit des plus grands termes
24

Version finale en APL :

Lien pour tester directement le code ci-dessous :

      rats_sourds ← {'O' +.= (2|⍳⍴⍵) / ⍵}

      rats_sourds '~O~O~O~OP'
0
      rats_sourds 'PO~O~~OO~'
1
      rats_sourds '~OO~~O~OP~OO~O~'
2