Complexité algorithmique, boucles et fonctions en Javascript

Cinquième corrigé des challenges de l’histoire originale Greenoïd, créée à l’occasion de la Battle Dev Thales 2024.

Il était question dans ce challenge de rechercher la séquence la + longue, en calculant la durée de différentes séquences et en les combinant (2 listes de séquences à disposition).

Analyse de la complexité algorithmique

Une première approche, retrouvée dans beaucoup de code produit durant la Battle Dev, consiste à chercher le maximum parmi toutes les combinaisons possibles. C’est à dire de combiner toutes les valeurs des 2 listes entre elles. Et ça fonctionne ! Mais…

Il existe en fait une façon + optimisée de le faire. La séquence la + longue est en fait la somme de plus longue séquence de la première liste avec la plus longue séquence de la seconde liste.

Donc s’il y a 10 séquence par liste, on peut trouver la solution en calculant la longueur des 20 séquences, et non en calculant les 100 (10×10) combinaisons !

Résolution en javascript

Le code ci-dessous est (à 99%) une réponse apportée par un des participants.

On commence par créer un tableau qui permettra de calculer la longueur des séquences :

const temps = {
    'P': 1,
    'H': 2,
    'C': 3,
    'D': 4,
}

Puis une fonction seqsum qui va calculer la longueur d’une séquence, en s’appuyant sur temps :

const seqsum = str => Array.from(str).reduce((a, b) => a + temps[b], 0);

Cette fonction prend une chaine de caractères en entrée, la transforme en tableau de caractères avec Array.from(str), et utilise reduce pour calculer la somme des valeurs associées aux caractères, via temps.

On initialise ensuite plusieurs variables puis en on recherche le maximum de chaque liste :

let seqcurmax = '', seqcurmaxt = 0;
let stocurmax = '', stocurmaxt = 0;

for (let sequence of sequences) {
    const sum = seqsum(sequence);
    if (seqcurmaxt < sum) {
        seqcurmax = sequence;
        seqcurmaxt = sum;
    }
}

for (let storage of storages) {
    const sum = seqsum(storage);
    if (stocurmaxt < sum) {
        stocurmax = storage;
        stocurmaxt = sum;
    }
}

Dans chaque boucle, on calcule la longueur de la séquence, puis on la compare à une valeur mémorisée pour déterminer s’il s’agit d’un « nouveau maximum ».

Et l’affichage de la réponse finale :

console.log(`${seqcurmax}${stocurmax}_${seqcurmaxt + stocurmaxt}`);

On affiche donc une chaîne qui combine la séquence ayant la plus grande somme de sequences avec la séquence ayant la plus grande somme de storages, suivie du total de leurs sommes additionnées.

Est ce qu’on peut encore optimiser ce code ?

La réponse est oui ! Il y a une répétition des boucles, on peut les « intégrer » dans une fonction qui sera chargée de parcourir un tableau de chaines de caractères, tout en retournant plusieurs informations.

Voici un exemple :

// Pas de changement
const temps = {
    'P': 1,
    'H': 2,
    'C': 3,
    'D': 4,
}

// Fonction générique pour trouver la chaîne avec la somme maximale
const findMaxSeq = arr => arr.reduce((max, seq) => {
    const sum = Array.from(seq).reduce((a, b) => a + temps[b], 0);
    return sum > max.sum ? { seq, sum } : max;
}, { seq: '', sum: 0 });

// Calcul du maximum pour sequences et storages
const maxSeq = findMaxSeq(sequences);
const maxStorage = findMaxSeq(storages);

// Affichage du résultat
console.log(`${maxSeq.seq}${maxStorage.seq}_${maxSeq.sum + maxStorage.sum}`);

Pour conclure, l’optimisation du code est un processus continu, et s’arrêter à une première solution n’est pas toujours optimal. En cherchant des moyens plus efficaces, comme dans ce cas où on est passé de la combinaison de toutes les séquences possibles à la recherche directe des maximums dans chaque liste, on réduit significativement la complexité et on améliore les performances. Une fois cette complexité bien travaillée, on peut optimiser aussi le code.