Marathon d'algorithmes

Bonjour,

je me suis inspiré de ce topic pour la création de celui-ci.

Marathon d’algorithmes

Le but de ce topic est de s’entraîner à la réalisation d’algorithmes.

Déroulement du topic

• Je commence par énoncer un problème.
• Si un membre parvient à fournir un algorithme qui répond à mon problème sous trois jours, c’est à son tour de poser un problème.
• Sinon, alors je poste une solution à mon problème (en utilisant une balise secret) et je donne la main à un membre de mon choix.

Cas particulier

• Si un membre ayant trouvé un algorithme valide n’a aucun problème à poser en retour, alors il est en mesure de donner la main à n’importe qui d’autre.

Règles générales

• N’importe quel langage pourra être utilisé : n’oubliez ceci-dit pas de préciser le langage que vous utilisez !
• Les problèmes ne doivent pas porter sur un langage spécifique, on doit pouvoir apporter une réponse avec n’importe quel langage (ou du moins une grande majorité)
• Il peut exister plusieurs solutions à un problème avec différents niveaux de complexité. Libres à vous de proposer différentes solutions !

J’ouvre le bal avec un premier algorithme relativement simple :

Salut,

Je pense à :

const getMaxSubArray = (arr) => {
  let minPrefix = 0;
  let currentPrefix = 0;
  let maxValue = 0;
  for (let i = 0; i < arr.length; ++i) {
    currentPrefix += arr[i];
    if (currentPrefix < minPrefix) {
      minPrefix = currentPrefix;
    }
    maxValue = Math.max(maxValue, currentPrefix - minPrefix)
  }
  return maxValue;
}

Voici ma solution en $O(n^2)$ ^^:

int get_max_sub_arr(std::vector<int> arr) {
  int max {0}, test {0};
	for (int i = 0 ; i < arr.size() ; ++i) {
		for (int j = i ; j < arr.size(); ++j) {
			test += arr[j];
			if (max < test) max = test;
		}
		test = 0;
	}
	if (std::all_of(arr.begin(), arr.end(), [](int i) { return i < 0; })) {
		return 0;
	}
	return max;
}

@Jeph: Ta solution est très élégante.
J’essaye de comprend le principe.

Pourquoi la sommes cumulée des valeurs moins la plus petite sommes cumulée négative donnerait la somme maximal des sous tableaux ?

J’ai le sentiment qu’il y a quelque chose qui s’annule mais pas précisément quoi.

En notant $S_i$ la somme des éléments jusqu’à l’indice $i$, le somme des éléments dans l’intervalle $]i; j]$ est $S_j - S_i$. Pour maximiser $S_j - S_i$, il faut maximiser $S_j$ et minimiser $S_i$, tout en conservant $i < j$.

Dans le code de @Jeph, currentPrefix correspond à $S_j$ et minPrefix correspond à $S_i$.

Edit: ma solution en Haskell.

solve :: (Num a, Ord a) => [a] -> a
solve xs = impl_ 0 0 0 xs
  where impl_ _ _ best [] = best
        impl_ si sj best (x:xs) =
          impl_ (min (sj + x) si) (sj + x) (max (sj - si) best) xs

Ça parait bien plus claire comme ça ! Effectivement $S_j - S_i$ correspond bien à la somme du sous tableau de $i$ à $j$.

Merci

Il faudrait fournir des preuves de bon fonctionnement, au minimum avec les exemples proposés.

Salut, je pense qu’on a tous teste nos code sur les samples avant de les poster (:

Un truc amusant : en changeant les let par des var en en rajoutant un point-virgule à la ligne 10 de la solution de @Jeph, on obtient un corps de fonction qui fonctionne en JS et en JavaScript :

public int computeMaxSubListO1(int[] arr) {
    var minPrefix = 0;
    var currentPrefix = 0;
    var maxValue = 0;
    for (var i = 0; i < arr.length; ++i) {
        currentPrefix += arr[i];
        if (currentPrefix < minPrefix) {
            minPrefix = currentPrefix;
        }
        maxValue = Math.max(maxValue, currentPrefix - minPrefix);
    }
    return maxValue;
}

@Test
void computeMaxSubListO1() {
    Algo1 a = new Algo1();
    assertEquals(6, a.computeMaxSubListO1(new int[]{1, 2, 3}));
    assertEquals(3, a.computeMaxSubListO1(new int[]{-2, -1, 1, 2}));
    assertEquals(6, a.computeMaxSubListO1(new int[]{2, -1, 2, 3, -9}));
    assertEquals(11, a.computeMaxSubListO1(new int[]{-1, 2, 3, -9, 11}));
}

J’ai rajouté comme quoi il faudrait préciser le langage utilisé à chaque proposition d’algorithme.

Sinon, voici un équivalent python de la solution $\mathcal{O}(n^2)$ :

def get_max_sub_arr(*arr):
    max_sum = 0
    for index, i in enumerate(arr):
        sum_test = 0
	for j in arr[index:]:
	    sum_test += j
	    max_sum = max([sum_test, max_sum])
    return max_sum

Il me semble que la condition suivante dans le code de @imlambda soit inutile :

if (std::all_of(arr.begin(), arr.end(), [](int i) { return i < 0; })) {
    return 0;
}

En effet, si tu défini max à 0 avant d’entrer dans la première boucle, alors dans le cas où tous les éléments sont négatifs, jamais la condition sum > max ne sera vérifiée (car une somme d’entiers négatifs sera toujours inférieure à 0) et donc la fonction retournera max = 0.

Sinon, celle proposée par @Jeph est en effet très jolie !

Je lui donne donc la main.

Allons-y dans ce cas, avec quelque chose de simple également (je n’avais pas trop d’idées d’algo…) :

2 solutions en C++, $\mathcal{O}(n^2)$ et $\mathcal{O}(n)$.

Edit: correction, c’est du $\mathcal{O}(n^2)$ dans le pire cas. Faut que je réfléchisse s’il y a moyen de faire mieux.

Edit2: Trouvé en $\mathcal{O}(n)$.

bool solve(const std::vector<int>& arr) {
  if (arr.empty()) return false;

  std::vector<bool> visited(arr.size(), false);
  std::deque<int> to_visit;
  to_visit.push_back(0);
  while (!to_visit.empty() && !visited.back()) {
    const int i = to_visit.front();
    to_visit.pop_front();
    if (visited[i]) continue;
    visited[i] = true;
    for (int j = i + 1; j <= i + arr[i] && j < arr.size(); ++j) {
      if (!visited[j]) to_visit.push_back(j);
    }
  }
  return visited.back();
}

bool solve(const std::vector<int>& arr) {
  if (arr.empty()) return false;

  int max_reachable = 0;
  for (int i = 0; i <= max_reachable && max_reachable < arr.size() - 1; ++i) {
    max_reachable = std::max(max_reachable, i + arr[i]);
  }
  return max_reachable >= arr.size() - 1;
}

En Ruby.

def last_position(ary)
  max = 0
  i = 0
  while i <= max && i < ary.size
    max = [max, ary[i] + i].max
    i += 1 
  end
  return [max, ary.size - 1].min
end

L = [
  []
  [1, 0, 1],
  [1, 1, 1],
  [2, 0, 1],
  [2, 4, 0, 0, 1]
]

L.each { |ary| puts "#{ary} : #{last_position(ary) == ary.size - 1}" } 

@Berdes, ta première solution ne fonctionne pas sur un tableau vide, non ? EDIT : Ah non, c’est bon, tu as rajouté un test.

EDIT 2 : je crois que je suis fatigué… Pour moi, il faudrait renvoyer true sur le tableau vide ?

Mon interprétation, c’est que vu qu’il n’y a pas de "dernière case" dans un tableau vide, le joueur ne peut pas l’atteindre. Dans tous les cas, c’est plus une convention qu’autre chose.

Humm, je crois que j’ai pas compris un truc.

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>


static int max(int a, int b) { return a > b ? a : b; }

bool est_un_chemin(unsigned int* tab, size_t n) {
    int m = 0;

    if( n <= 1)
        return true;

    for(size_t i = 0 ; i <=m && i < n; ++i)
        m = max(tab[i] + i, m);

    return m >= (n - 1);
}

int main(void) {

    unsigned int tab_1[] = {1, 0, 1};
    unsigned int tab_2[] = {1, 1, 1};
    unsigned int tab_3[] = {2, 0, 1};
    unsigned int tab_4[] = {2, 4, 0, 0, 1};
    unsigned int tab_5[] = {3, 2, 1, 0, 0};

    unsigned int *tabs[] = {tab_1, tab_2, tab_3, tab_4, tab_5};
    unsigned int sizes[] = {3, 3, 3, 5, 5};

    for(size_t i = 0 ; i < 5 ; i++) {
        if( est_un_chemin(tabs[i], sizes[i]) )
            puts("True");
        else 
            puts("False");
    }

    return EXIT_SUCCESS;
}

Je considère du coup que pour le tableau [0], ben c’est vrai car la première est la dernière case. ¯_(ツ)_/¯

@Karnaj: J’ai regardé ta solution, on a le même algo je crois. Moi en C. Il te manque une virgule ligne 13.

Top ! Désolé pour le manque d’indication pour le cas du tableau vide.

Et pour un tableau qui contient un seul élément l’algo doit bien retourner True. Vos trois solutions sont similaires et fonctionnent toutes !

@ache Pour chipoter, ta condition ligne 11->12 n’est pas nécessaire puisque forcément vérifier par ta ligne 17

À ton tour de proposer un exercice @Berdes !

@Jeph, pour n == 1 oui, mais pour n == 0 (tableau vide) ça ne marche pas justement. Ça va faire un underflow. n - 1 == UINT_MAX or UINT_MAX > 0.

De plus, j’aime m’assurer que je ne déréférence pas un tableau vide.

Après, j’aurais pu utiliser des types signés. D’ailleurs m aurait du être unsigned int.

@Berdes: Effectivement ton interprétation pour le tableau vide me semble … Évidente. Et pourtant ce n’est pas ce que j’ai implémenté.

N’étant pas chez-moi hier, je n’ai pas pu me pencher sur le problème de @Jeph !

Du coup, il y a un truc que je ne comprends pas dans l’énoncé :

La position initiale du joueur est en 0.

Au début de chaque étape, le joueur est positionné sur une case i, il peut atteindre n’importe quelle case entre i et i + arr[i]

Quand tu parles de 0, tu parles de l’index 0, donc au début du tableau, c’est ça ?

Ensuite, quand tu dis que le joueur est positionné sur une case i, tu parles de l’index ou de la valeur de la case ?

Car ça change pas mal de choses selon le contexte.

Hello, super idée ce topic !

@Berdes : si je ne me trompe pas, ce problème ($P|\mathit{prec}|C_{\max}$ en notation de Graham) est NP-difficile au sens fort non ?

@Tchaïkovski: oui, je pense que le 0 représente la première case du tableau et pas une case qui contient 0. La deuxième interprétation n’est pas très intéressante puisque cela voudrais dire que le joueur ne peut jamais bouger.

@fifo: Je ne connaissait pas cette notation, mais oui, le problème n’a pas de solution (connu) en temps polynomial. Je ne pense pas qu’implémenter une solution soit si difficile que ça, mais vu que ça reste quand même nettement plus difficile que les problèmes précédents je vais un changer le problème pour passer d’une solution optimale à une "bonne" solution.